Структура списков
Списочные структуры
Дек
Операции
Для очереди должны быть определены следующие операции:
empty(<нач_очереди>):boolean - проверка очереди на пустоту;
add(<кон_очереди>,<нов_эл-т>):<кон_очереди> - добавление элемента в конец очереди;
take_beg(<нач_очереди>):<тип_эл-тов_очереди> - считывание значения первого элемента;
take_end(<кон_очереди>):<тип_эл-тов_очереди> - считывание значения последнего элемента;
del(<нач_очереди>):<нач_очереди> - удаление элемента из начала очереди.
Дональд Кнут ввел понятие усложненной очереди, которая называется дек (deque - Double-Ended QUEue - двухконцевая очередь). В каждый момент времени у дека доступны как первый, так и последний элемент, причем добавлять и удалять элементы можно и в начале, и в конце дека. Таким образом, дек - это симметричная двусторонняя очередь.
В терминах списков дек удобнее представлять двусвязным (разнонаправленным) линейным списком.
Набор операций для дека аналогичен набору операций для очереди, с той лишь разницей, что добавление и удаление элементов можно производить и в конце, и в начале структуры.
Если для каждой динамической переменной описывать и хранить ее "личный" указатель, то никакой выгоды на этапе выполнения программы получить не удастся: часть памяти, как и прежде, будет выделяться статически, а ее общий объем даже увеличится - ведь каждый указатель требует для себя четыре байта.
Следовательно, нужно сделать так, чтобы место под хранение адресов будущих переменных также выделялось динамически. Решением этой проблемы и служат списки - специальные динамические структуры. Списки применяются, например, в таких ситуациях:
• программист заранее ничего не знает о том, какой именно объем памяти может потребоваться его программе;
• некоторые (особенно "тяжелые") переменные нужны поочередно, и после того как первые "отработали свое", их можно смело стирать из памяти, не дожидаясь конца работы программы, - освобождать место для других "тяжелых" переменных;
• в процессе обработки данных нужно провести большую работу по перестройке всей структуры "на ходу"; и т.д.
Итак, каждый элемент создаваемого списка должен содержать:
1. информацию, которая может иметь любой формат: integer, real, array, record и т.п.;
2. специально выделенное поле (и, может быть, не одно), которое хранит адрес другого элемента этой же структуры.
Приведем примеры различных списочных структур:
a) Односвязный (линейный) список: структура, каждый элемент которой "знает" адрес только следующего за ним элемента (см. рис. 10.1 (a)). Очень удобно представлять таким списком стек и очередь.
b) Двусвязный линейный список: структура, каждый элемент которой "помнит" адрес не только следующего, но и предыдущего элемента списка. Этот список удобен для работы с деками.
c) Бинарное дерево может быть представлено двусвязным нелинейным списком: каждая вершина помнит обоих своих возможных потомков. Если каждой вершине необходимо помнить не только потомков, но и предка, то список становится трехсвязным.
d) Для представления ориентированного графа можно использовать иерархические списки - комбинацию из двух различных линейных списков.