Связь и интернет Архив Программирование
   
Сделать стартовойСделать закладку            
   ПОИСК  
   
Главная / Алгоритмы / Структуры данных и хэширование / Введение в абстрактные структуры / Cписки /
8  Perl
8  PHP
8  JavaScript
8  HTML
8  DHTML
8  XML
8  CSS
8  C / C++
8  Pascal и Delphi
8  Турбо Ассемблер
8  MySQL
8  CASE-технологии
8  Алгоритмы
8  Python
8  Обратная связь
8  Гостевая книга
Новости о мире


Реализация односвязного и двусвязного списков - Программирование от RIN.RU
Реализация односвязного и двусвязного списков




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


На всех рисунках сплошными линиями показаны связи, имевшиеся до выполнения и сохранившиеся после выполнения операции. Пунктиром показаны связи, установленные при выполнении операции. Значком "x" отмечены связи, разорванные при выполнении операции. Во всех операциях чрезвычайно важна последовательность коррекции указателей, которая обеспечивает корректное изменение списка, не затрагивающее другие элементы. При неправильном порядке коррекции легко потерять часть списка. Поэтому на рисунках рядом с устанавливаемыми связями в скобках показаны шаги, на которых эти связи устанавливаются.


В программных примерах подразумеваются определенными следующие типы данных:


  • любая структура информационной части списка:

    type data = ...;


  • элемент односвязного списка (sll - single linked list):


    type
    sllptr = ^slltype; { указатель в односвязном списке }
    slltype = record { элемент односвязного списка }
    inf : data; { информационная часть }
    next : sllptr; { указатель на следующий элемент }
    end;


  • элемент двухсвязного списка (dll - double linked list):


    type
    dllptr = ^dlltype; { указатель в двухсвязном списке }
    dlltype = record { элемент односвязного списка }
    inf : data; { информационная часть }
    next : sllptr; { указатель на следующий элемент (вперед) }
    prev : sllptr; { указатель на предыдущий элемент (назад) }
    end;




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


Эта операция, возможно, чаще других выполняется над линейными списками. При ее выполнении осуществляется последовательный доступ к элементам списка - ко всем до конца списка или до нахождения искомого элемента.


Алгоритм перебора для односвязного списка представляется программным примером 1.


{==== Программный пример 1 ====}
{ Перебор 1-связного списка }
Procedure LookSll(head : sllptr);
{ head - указатель на начало списка }
var cur : sllptr; { адрес текущего элемента }
begin
cur:=head; { 1-й элемент списка назначается текущим }
while cur <> nil do begin < обработка c^.inf >




Обрабатывается информационная часть того эл-та, на который указывает cur.


Обработка может состоять в:


  • печати содержимого инф.части;

  • модификации полей инф.части;

  • сравнения полей инф.части с образцом при поиске по ключу;

  • подсчете итераций цикла при поиске по номеру;

  • и т.д., и т.п.


cur:=cur^.next;

из текущего эл-та выбирается указатель на следующий эл-т и для следующей итерации следующий эл-т становится текущим; если текущий эл-т был последний, то его поле next содержит пустой указатель и, т.обр. в cur запишется nil, что приведет к выходу из цикла при проверке условия while

end; end;
{ конец примера }


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

cur:=cur^.prev;




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


Вперед  >>>
 1  2  3  4  5 


 8  Комментарии к статье  8 8  Обсудить в чате

 
  
  
    Copyright ©  RIN 2003 - 2004      * Обратная связь
Быстрая широкоформатная печать баннеров в рассрочку.