Связанные списки
Связанный список - это линейный набор ссылающихся на себя структур, называемых узлами, и объединенных указателем-связкой, отсюда и название - «связанный» список. Доступ к связанному списку обеспечивается указателем на первый узел списка. Доступ к следующим узлам производится через связывающий указатель, хранящийся в каждом узле. По общему соглашению связывающий указатель в последнем узле списка устанавливается в NULL,отмечая конец списка. Данные хранятся в связанном списке динамически - каждый узел создается по мере необходимости. Узел может содержать данные любого типа, включая другие структуры. Стеки и очереди также принадлежат к линейным структурам данных, и, как мы увидим, являются специальными вариантами связанных списков. Деревья же являются нелинейными структурами данных.
Списки данных могут храниться в массивах, однако связанные списки дают определенные преимущества. Связанный список удобен, когда заранее не известно, сколько элементов данных будет содержать структура. Связанные списки являются динамическими, поэтому длина списка при необходимости может увеличиваться или уменьшаться.
Стеки
Стек - это упрощенный вариант связанного списка. Новые узлы могут добавляться в стек и удаляться из стека только сверху. По этой причине, стек часто называют структурой вида последним пришел - первым вышел (LIFO). На стек ссылаются через указатель на верхний элемент стека. Связывающий элемент в последнем узле стека установлен равным NULL, чтобы пометить границу стека.
Разница между стеком и связанными списками в том, что вставку и удаление в связанных списках можно выполнять в любом месте, а в стеке только сверху.
Основные функции, используемые при работе со стеками - push и pop. Функция push создает новый узел и помещает его на вершину стека. Функция pop удаляет верхний узел стека, освобождает память, которая была выделена изъятому узлу, и возвращает изъятое значение.
Стеки имеют множество разнообразных применений. Например, всякий раз, когда происходит вызов функции, вызванная функция должна знать, как вернуться к вызывающей, поэтому адрес возврата помещается в стек. В случае, когда происходит целый ряд последовательных вызовов, адреса возврата размещаются в стеке в порядке последним пришел - первым вышел, так что после завершения выполнения каждой функции происходит переход к функции, ее вызывавшей.
Дата добавления: 2015-07-16; просмотров: 57 | Нарушение авторских прав
| <== предыдущая страница | | | следующая страница ==> |
| Динамическое распределение памяти | | | Очереди |