Структура списков

Списочные структуры

Дек

Операции

Для очереди должны быть определены следующие операции:

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) Для представления ориентированного графа можно использовать иерархические списки - комбинацию из двух различных линейных списков.

Дата добавления: 2014-01-20