Сайт Льва Волкова
  
· Доля заик среди населения Земли составляет 1%. На три четверти это мужчины.
 
      На главную  
 Личное
  Статьи
  Задачи 
 Ссылки
 АТ-531
www.levvol.ru    
 

Линейные списки

Напомним, что списком называется структура данных, каждый элемент которой посредством указателя связывается со следующим элементом.



Линейный список

Из определения следует, что каждый элемент списка содержит как минимум два поля: поле данных (назовем его data и для простоты считаем его типа Integer), оно может иметь сложную структуру, и поле ссылки на следующий элемент (назовем его next). Поле ссылки последнего элемента списка имеет значение Nil.

Основные операции с элементами списка

Описание элемента списка, используемого в дальнейшем, имеет вид:

Type 
   pt=^elem;{Указатель на элемент списка}
    elem=record
	data:integer;{Поле данных}
	next:pt;{Указатель на следующий элемент списка}
    end;
Var first:pt; {Указатель на первый элемент списка}		    

Основные операции с элементами списка:

  • вставка элемента в список;
  • просмотр элементов списка;
  • удаление элемента из списка.

вверх страницы
Вставка элемена в список

Вставка элемента в список возможна логически в его начало, конец и середину. Разберем эти случаи.



Вставка элемента в начало списка


 Procedure InputBegin(var z:pt; y:integer);
 Var p:pt;
 Begin
 New(p);  {1}
 p^.next=z; {2}
 p^.data=y;
 z:=p; {3}
 End;
 

Красными линиями на рисунке выделены действия, выполняемые в процедуре. Цифрами на рисунке и в тексте процедуры представлены действия соответствующих операторов.

Вставка в конец списка осуществляется с помощью следующей процедуры.

			 
 Procedure InputEnd_(var z:pt; y:integer);
 Var p,q:pt;
 Begin 
 {Запись в элемент q}
 New(q);  q^.next:=nil; q^.data:=y;
  if z=nil then  z:=q {Список пуст}
           else begin {Список не пуст}
            p:=z;					 
	{Проход по списку до конца}
	while p^.next<>nil do p:=p^.next;
	{Привызка нового элемента к последнему}
            p^.next:=q 
                end;
End;				

Указатель p просматривает список, пока не найдёт nil. После этого вставляемый элемент привязываетя к последнему элементу списка.

Очевидно, что для вставки элемента в список необходимо знать, как минимум, адрес предшествующего элемента списка, т.е. элемента после которого осуществляется вставка.

Пусть мы создаем упорядоченный по неубыванию список (информационная часть любого элемента списка меньше или равна информационным частям следующих за ним элементов.

Для того чтобы найти место для вставки очередного элемента списка, следует просматривать список до тех пор, пока вставляемый элемент больше информационной части текущего элемента.

			 
 Procedure InputMed(var z:pt; y:integer);
 Var p,q:pt;
 Begin 
   New(q); p:=z;
 While y>p^.next^.data do  p:=p^.next;
   q^.next:=p^.next;
   q^.data:=y
   p^.next:=q 
End;				

Конструкцияq^.next^.data - ссылка на информационное поле следующего элемента списка.

Общая логика вставки элемента в упорядоченный список. Здесь список описывается двумя указателями: на первый и последний элементы списка.

 	  
Procedure Input(var z_first,z_last:pt; y:integer);
If y<z_first^.data then InputBegin(z_first,y)
              else If y>z_last^.data then InputEnd(z_last,y) 
 else InputMed(z_first,y);
End;		

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

Procedure InputEnd(var z:pt; y:integer);
 Var p,q:pt;
 Begin
 new(z^.next);
 z:=z^.next;
 z^.data:=y;
 z^.next:=nil
 End;
 

Процедуру InputEnd необходимо описать перед процедурой Input.

Ввод исходных данных при создании упорядоченного списка осуществляется с клавиатуры. Признак конца ввода - ввод числа 0. Все действия по организации ввода представлены в процедуре:

  Procedure Solve(var first,last:pt);
  Var y:integer;
  Begin
  read(y);
  if y<>0 then begin
               first:=nil;
               InputBegin(first,y);
               last:=first
               end
         else begin
              first:=nil;
              last:=nil
              end;
  while y<>0 do begin
        read(y);
        if y<>0 then Input(first,last,y)
                end;
  End;
  

вверх страницы
Просмотр элементов списка

Просмотр списка возможен с начала или с конца:

Просмотр элементов списка с начала:

 Procedure PrintBegin_(z:pt);
 Begin
 while z<>nil do begin
 write(z^.data,' ');
 z:=z^.next;
 end; 
 End;  
 

Можно использовать рекурсию:

 Procedure PrintBegin(z:pt);
 Begin
 if z<>nil then begin
 write(z^.data,' ');
 PrintBegin(z^.next);
 end;
 End;  
 

При просмотре списка с конца дело обстоит сложнее, поскольку связи направлены только в одну сторону и невозможно продвигаться по ним в противоположном направлении. В этом случае нужно использовать двусвязанный, который имеет два указателя на соседа слева и на соседа справа. Более рациональным является применение рекурсии:

  Procedure PrintEnd(z:pt);
  Begin
  if z<>nil then begin
  PrintEnd(z^.next);
  write(z^.data,' ');
  end;
  End;  
 

вверх страницы
Удаление элемента из списка

Действия при удалении элемента из списка различны в зависимости от места удаляемого элемента: первый он или нет. Для сохранения структуры списка необходимо помнить удрес элемента списка, предшествующего удаляемому элементу (dx), а также помнить адрес удаляемого элемента для корректного применения процедуры Dispose.

Приведем процедуру удаления всех элементов спмска, информационная часть которых равна заданному числу (y).

	
 Procedure Del_y(var first:pt; y:integer);
 Var z,x,dx:pt;
 Begin
 z:=first; {Переменная  цикла}
 While z<>Nil do {Просмотр списка}
 if z^.data=y then {Совпадение}
   if z=first then begin {Если это первый элемент}
   {Удаляем первый элемент}
   x:=first; {Запоминаем его}
   {Указатель на первый элемент}
   first:=first^.next;
   Dispose(x); {Освобождаем место в куче}
   z:=first	{Переменная цикла изменила значение}
   end
              else begin 
	{Запоминаем адрес удаляемого элемента}		  
   x:=z;
   z:=z^.next; 
   {Удаление не должно нарушать структуру списка}
   dx^.next:=z;
   Dispose(x);
                  end
             else begin
  {Переход к следующему элементу списка.
   Адрес текущего запоминается в dx}		 
 dx:=z; z:=z^.next
                  end;
 End;
  

Приведем программу упорядочивания вводимых с клавиатуры целых чисел (признаком конца ввода является 0). После вывода упорядоченных данных программа удаляет из списка 2 и выводит новый список.

 Begin
  ClrScr;
  Writeln('End of input's 0 ');
  Solve(first,last);
  writeln('----------');
  PrintBegin(first);
  Del_Y(first,2);
  writeln;
  PrintBegin(first);
  repeat
  until KeyPressed;
  End.						 
  

Программный код вы можете скачать здесь tp24.pas. В программе приведены все рассмотренные процедуры.

Пример работы программы.

Ввод 2 3 4 5 2 9 8 7 2 12 0

Вывод: 2 2 2 3 4 5 7 8 9 12

       ---------------

       3 4 5 7 8 9 12

вверх страницы

 

[назад] [содержание]