Списочные структуры данных обычно понимаются как структуры, где каждый элемент указывает, как правило, на другие элементы структуры. К таким структурам относят списки, однонаправленные и двунаправленные, стеки, очереди, деревья, графы. Для многих типов списков определены понятия текущего, предыдущего, следующего элемента. Типы списков различаются конфигурацией (на какие элементы ссылается каждый конкретный элмент) и набором базисных операций, которые выполняются над списками. К базисным операциям над списками обычно относят следующие операции:
- создание пустого списка,
- проверка списка на пустоту,
- выборка значения текущего элемента,
- удаление текущего элемента из списка,
- замена текущего элемента,
- выбор нового текущего элемента (предыдущего или последующего),
- добавление нового элемента в список (после текущего или перед текущим элементом),
Таким образом, каждый элемент списочной структуры должен содержать информационную часть и один или более указателей на другие элементы структуры. В примерах которые будут рассматриваться ниже, списочные структуры будут изменяться, т.е. будут изменяться значения указателей. Поэтому с целью упрощения указатели на списочные структуры будут передаваться в функции как глобальные переменные.
6.1 Очереди и стеки
Ограничивая набор базисных операций над списками можно получить такие структуры, как очереди и стеки. Очередь реализует дисциплину обработки элементов списка "first in - first out"(первый вошел - первый вышел), когда добавление элементов осуществляется в один конец очереди, а удаление - из другого конца. Очередь можно представить следующим образом:
Element * Left = NULL;
Element * Right = NULL;
Указатель Left - начал очереди, т.е указывает на первый элемент, доступный для обработки или удаления. Указатель Right - конец очереди, адрес последного элемента, после которого могут добавляться новые элементы. Нулевые значения указателей соответствуют пустой очереди.Таким образом, при удалении элемента из очереди будет изменяться указатель Left, а при добавлении - указатель Right. Набор базисных операций обычно включает четыре операции:
- создание пустой очереди,
- проверка очереди на пустоту,
- выборка первого элемента очереди с одновременными удалением его из очереди,
- занесение нового (последнего) элемента в очередь.
В отличие от очереди стек реализует дисциплину "first in - last out"(первым вошел, последним выщел) , стек имеет единственную точку входа, используемую как для добавления, так и для удаление элементов. Объявить стек можно очень просто
Element * Top = NULL;
Указатель Top - адрес первого элемента списка, доступного для обработки и удаления. Добавление и удаление элементов изменяют значение указателя Тор. Набор базисных операций обычно включает пять операций:
- создание пустого стека,
- проверка стека на пустоту,
- выборка последнего (верхнего) элемента стека с одновременными удалением его из
- выборка последнего (верхнего) элемента стека без удаления его из стека,
- занесение нового (последнего) элемента в стек.
