Finally. Close(fDat); Close(fRes);

Close(fDat); Close(fRes);

end;

end.

Тема 2. Односвязные и двусвязные
линейные списки

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

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

Начало

Число элементов списка не ограничено. Список, в котором нет ни одного элемента, называется пустым. Стеки, очереди и деки, рассмотренные в теме 1, являются частными случаями линейного списка, поскольку имеют ограниченную дисциплину обслуживания.

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

2. Операции над линейным списком

Над линейным списком l могут быть выполнены все операции, определенные для стека, очереди и дека (тема 1), а также следующие операции:

1) включение элемента со значением v в список после элемента с заданным адресом p – InsertAfter (l, p, v);

2) включение элемента со значением v в список l перед элементом с заданным адресом p – InsertBefore (l, p, v);

3) исключение из списка l элемента с адресом p – Delete (l, p);

4) исключение из списка l элемента, следующего за элементом с адресом p – DeleteAfter (l, p);

5) поиск в списке l элемента с заданным значением v – Search (l, v) и возвращение его адреса.

3. Реализация линейного списка в виде односвязной динамической структуры

Список, реализованный предложенным способом, называется односвязным линейным списком, т.к. каждый элемент этого списка содержит ссылку только на один соседний элемент. Описание класса tList:

Type

tValue= Real; // тип значения элемента списка - вещественный

pItem= ^tItem; // тип указателя на элемент списка

tItem= record // тип элемента списка

Value: tValue; // содержательная часть элемента списка

Next: pItem; // указатель на следующий элемент списка

end; // recordtItem

tList = class // класс - список