Реферат: Линейные списки. Стек. Дек. Очередь
а) неопределенное заранее число элементов;
б) необходимость хранения в оперативной памяти.
Средство для реализации таких структур дает аппарат динамических переменных. Простейшей из обсуждаемых структур является однонаправленный список. Он строится подобно очереди на прием к врачу: пациенты сидят на любых свободных местах, но каждый из них знает, за кем он в очереди (т.е. данные размещаются на свободных местах в памяти, но каждый элемент содержит ссылку на предыдущий или следующий элемент). Поскольку количество пациентов заранее не очевидно, структура является динамической.
Другая подобная структура - стек. Его моделью может служить трубка с запаянным концом, в которую вкатывают шарики. При этом реализуется принцип «последним вошел - первым вышел». Возможное количество элементов в стеке не фиксировано.
Остановимся на примере стека и покажем его программную реализацию. Технически при этом следует решить ряд задач, из которых наиболее специфическими являются
а) связывание последующих компонентов стека;
б) смещение ссылок при каждом движении по стеку.
 |
??-?? ????????????? ??????? ?? ?????? ???????? ??????? ????????, ?? ? ???????????????? ?????? ?? ??????????? ???????, ?????? ?? ????????? ????? ??????? ? ???? ??????????? ??????, ? ??????? ?????? ???? - ???????? ????????, ? ?????? - ?????? ?? ????????? ???????. ???????????? ??? ????????? ????? ??????? ?????????? ???????
(элементу, который пришел первым, ссылаться не на что, о чем свидетельствует «пустая ссылка» nil).
Ниже приведены примеры создания и уничтожения списков, добавление и удаление элементов из списка на Delphi. Рассмотрены только для однонаправленного и двунаправленного списков для остальных даны примеры в демонстрационной программе.
Type
List = ^Spisok; - Однонаправленный
Spisok = record
Info: Integer; - Информационное поле
Next: List; - Ссылка на следующий элемент
end;
ListTwo = ^SpisokTwo; - Двунаправленный
SpisokTwo = record
Info: Integer; - Информационное поле
Next: ListTwo; - Ссылка на следующий элемент
Prev: ListTwo; - Ссылка на предыдущий элемент
end;
Создание списка
procedure CreateLists; - процедура создания списка
begin
X := Random(101); Определяем значение первого элемента
Uk := nil; Указателям присваиваем nil.
q := nil;
AddToList (X, Uk); Добавляем элемент Х в список.
q := Uk; Формируем указатель на начало списка .