Все о динамических структурах данных. Опции

[Altair]

Содержание:

• Указатели
• Списки
  + Модуль для работы со списками. + Двусвязные списки
  
• Стеки
  + Модуль для работы со стеками.
• Очереди
  + Модуль для работы с очередями.
• Деки (двусторонние очереди)
  + Модуль для работы с деками.
• Деревья
  + Модуль для работы с деревьями.
• Сортировка стека
• Сортировка очереди
• Демонстрационные программы с ДСД
• Двусвязные списки

Есть материал по теме? высылайте! ваша информация будет размещена здесь!

[Altair]

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

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

Тем не менее, использовать двусвязный список удобнее - потерять начало списка просто невозможно!

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

(одно из возможных расширений модуля - добавление функции поиска элемента, функции удаления элемента, добавленияв начало, и процедуры переворота...).

uses crt, dlist;
var
  l:tlist;
begin
 writeln('Программа,тестирующая модуль DList для работы с двусвязными списками');
 writeln('Добавляем первый элемент,список инициализируется автоматически...');
 InitListAndAddFirst(1,L);
 writeln('Теперь добавим элемент 2 после того,на который указывал L... (AddAfter)');
 AddAfter(2,l);
 writeln(' ... и перейдем к концу списка, чтобы добавлять после последнего...(GotoLast)');
 GotoLast(l);
 AddAfter(3,l); GotoLast(l); {...  }
 AddAfter(4,l); GotoLast(l); { ... }
 AddAfter(5,l); GotoLast(l); {  ...}
 writeln('Полученный список (после добавления в конец) (listprint)');
 ListPrint(L);
 writeln('... вставим после 4 элемент 6');
 writeln('Для этого идем в начало списка(GotoFirst) и ищем элемент 4 ... ');
 gotoFirst(l); {в начало}
 while (l^.data<>4)and (l^.next<>nil) do l:=l^.next; {ищем}
 writeln;
 writeln('Нашли, добавляем... ');
 addafter(6,l);
 writeln('...вот, что у нас получилось (ListPrint) :');
 ListPrint(L);
 writeln('Уничтожаем список, очищая память. (ListDestroy)');
 ListDestroy(L);
end.

Модуль:  DLIST.PAS ( 1.78 килобайт ) Кол-во скачиваний: 85255