Ссылочные типы в ТП

Однонаправленные списки

1. Определение однонаправленного списка. Описание и обращение к элементам однонаправленного списка

   Главная возможность, которую предоставляет наличие ссылочных типов и ссылочных переменных в Паскале, - это возможность построения с их помощью объектов со сложной, меняющейся структурой, простейшим из которых является однонаправленный список.
   Структура «однонаправленный список» строится подобно очереди на прием к врачу: клиенты сидят на любых свободных местах, но каждый из них знает, за кем он стоит (т.е. данные размещаются на свободных местах в памяти, но каждый элемент содержит ссылку на предыдущий или следующий элемент).
   Однонаправленный список – это цепочка звеньев данных, где вместе с элементами указывается адрес следующего (или предыдущего) элемента.

   

   Каждое звено списка обычно является записью, состоящей из двух частей:

   1. информационная часть (одно или несколько полей).
   2. Ссылочная часть содержит ссылку на следующее (или предыдущее) звено списка.

   При описании списка возникает проблема, что раньше описывать: звено, представляющее запись и содержащее поле-ссылку, или ссылку на звено? В Паскале принято сначала описывать ссылку на звено, например:
   Type te=тип инф.части;
   Ss=^zveno; {ссылка на звено}
   Zveno=record {звено в виде записи}
   Inf: te; {информационная часть звена}
   Sled:ss {ссылочная часть звена}
   End;
   Var p,u:ss;

   Для обращения к информационной части звена, на которое ссылается указатель P, используется следующая запись: P^.inf.
   Соответственно, чтобы обратиться к указателю на следующее звено, необходимо воспользоваться записью P^.sled.

   Для облегчения работы со звеньями списка, принято вводить в употребление заглавное звено списка. Ссылочная часть заглавного звена содержит ссылку на первое звено списка, таким образом, у каждого звена списка будет “предыдущее” звено.
   Информационную часть заглавного звена можно не использовать или использовать для побочных целей, например, для хранения величины – количества звеньев списка.

2. Основные операции со списком

   1. Формирование списка
      Натуральные чисела вводятся с клавиатуры. Ввод числа 0 означает окончание формирования списка. Пусть u и p – имена ссылок на заглавный и текущий звенья списка.

      Алгоритм:

      Сначала выделяем место в памяти для заглавного звена New(u), текущая ссылка - р вначале указывает на заглавное звено.
      Далее, если вводится число неравное нулю, то с помощью ссылки p^.sled формируется очередное звено списка, и текущий указатель р переводится на это звено.

      Procedure form;
      var s:integer;
      Begin
      New(u); p:=u; u^.sled:=nil; Writeln(‘введите список натуральных чисел, окончание ввода - 0’);
      Readln(s);
      While s<>0 do
      begin
      new (p^.sled);p:=p^.sled; p^.inf:=s; p^.sled:=nil;
      readln(s);
      end;
      writeln
      End;

      Вывод содержимого (просмотр элементов) списка на экран

      Алгоритм:

      Текущую ссылку р связываем с первым звеном списка (u^.sled -имя указателя на первое звено);

      Затем связываемся со вторым звеном, изменив значение р на значение p^.sled, и продолжаем цикл просмотра элементов списка, пока выполняется условие p<>nil. Если список был пустым (было выполнено отношение p=nil), то тело цикла не выполнится ни разу и не будет выведено ни одного числа.

      Procedure print;

      Var p:ss;

      Begin p:=u^.sled;

      While p<>nil do

      begin write (p^.inf, ‘ ‘);

      P:=p^.sled;

      end;

      writeln;

      End;

      Удаления звена из списка

      Напишем процедуру, удаляющею звено из списка с помощью ссылки р на звено, за которым следует удаляемое звено.

      Операция удаления звена из списка требует изменения лишь одной ссылки, что геометрически выглядит как изменение одной стрелки:

      Список до удаления звена с элементом с:

      

      Список после удаления звена с элементом с:

      

      Удаляемое звено теперь можно уничтожить, освобождая занимаемый им участок памяти для других целей.

      Алгоритм:

      Надо изменить одну ссылку p^.sled:=p^.sled^.sled;

      В процедуре нужна локальная ссылка g для удаления ненужного звена.

      Procedure del(p:ss);

      var g:ss;

      Begin

      g:=p^.sled;

      p^.sled:=p^.sled^.sled;

      dispose(g);

      End;

      Включение (вставка) нового звена в список

      Напишем процедуру, добавляющую к списку новое звено g с элементом m после звена, на которое указывает ссылка р.

      Операция вставки нового звена требует изменения двух ссылок, геометрически – двух стрелок:

      Список до вставки звена с элементом m:

      

      Список после вставки звена с элементом m:

      

      Алгоритм:

      Необходимо определить две новые ссылки g^.sled и p^.sled.

      Чтобы вставить в список новое звено на первое место, достаточно в качестве ссылки р взять ссылку на заглавное звено.

      Procedure vstavka(p:ss;m:integer);

      var g:ss;

      Begin

      new(g);

      g^.inf:=m;

      g^.sled:=p^.sled;

      p^.sled:=g;

      End;

      Процедура поиска звена в списке

      Необходимо найти звено с заданным элементом. Результатом поиска будет ссылка rp на найденное звено с элементом m или пустая ссылка (rp=nil).

      Алгоритм:

      Необходимо организовать просмотр элементов списка (р – ссылка на звено с которого начинается просмотр, текущая ссылка).

      Просмотр следует закончить, когда найден нужный элемент p^.inf=m или просмотрен весь список p=nil.

      Рrocedure poisk(m:integer;p:ss; var rp:ss);

      Begin

      while (p^.inf<>m) and (p<>nil) do

      p:=p^.sled;

      rp:=p;

      End;

3. Пример программы

   Сформировать список натуральных чисел. Вывести список и количество элементов списка. Вставить в список нулевой элемент после элемента, равного 4. Если в списке нет элемента, равного 4, то удалить из списка второй элемент.

   program spisok;
   uses crt;
   type
   ss=^zveno;
   zveno=record
   inf:integer;
   sled:ss
   end;
   var p,f,u:ss; i,m:integer;

   Procedure form;
   var s:integer;
   Begin
   New(u); p:=u; u^.inf:=0; u^.sled:=nil;
   Writeln('input chislo');
   Readln(s);
   While s<>0 do
   begin new (p^.sled);p:=p^.sled; p^.inf:=s; p^.sled:=nil;
   inc(u^.inf); readln(s);
   end;
   writeln
   End;

   Procedure print;
   begin
   writeln(' spisok');
   p:=u^.sled;
   while p<>nil do
   begin write(p^.inf,' ');
   p:=p^.sled
   end;
   writeln;
   end;

   Procedure vstavka(p:ss;m:integer);
   var g:ss;
   begin
   new(g);
   g^.inf:=m;
   g^.sled:=p^.sled;
   p^.sled:=g;
   inc(u^.inf);
   end;

   Procedure del(p:ss);
   var g:ss;
   begin
   g:=p^.sled;
   p^.sled:=p^.sled^.sled;
   dispose(g);
   dec(u^.inf);
   end;

   Procedure poisk(m:integer;p:ss; var rp:ss);
   begin
   while (p^.inf<>m) and (p<>nil) do
   p:=p^.sled;
   rp:=p;
   end;

   BEGIN clrscr;
   form;
   print; writeln('kol-vo=', u^.inf);
   p:=u^.sled;
   poisk(4,p,f);
   if f<>nil then vstavka(f,0) else del(s^.sled);
   print; writeln('kol-vo=', u^.inf);
   readln;
   END.

Назад

Далее