Реализация очередей с помощью указателей
Как и для стеков, реализация списков допустима для представления очередей, но учитывая особенность очереди (вставка новых элементов только с одного, заднего конца) можно выполнить оператор ENQUEUE более просто, чем при представлении списков. Вместо перемещения списка от начала к концу при каждом пополнении очереди указатель можно ставить на последний элемент очереди. А можно, как и со стеками, ставить указатель на начало списка. Для очередей это удобно при выполнении команд FRONT и DEQUEUE. После исключения из очереди оператором DEQUEUE элемента х, он из очереди исключается, но останется в поле ячейки заголовка.
Обход Неориентированных графов
Во многих задачах, связанных с графами, требуется организовать систематический обход всех вершин графа. Существуют два наиболее часто используемых метода обхода графов: поиск в глубину и поиск в ширину. Эти методы удобно использовать для поиска вершин, смежных с данной вершиной.
ПОИСК В ГЛУБИНУ
Пусть имеем список, содержащий следующие элементы:
Э1, Э2, Э3, Э4.
Реализацией этого списка будет структура последовательно связанных компонент, изображённая на рис.1
Каждая компонента этой структуры состоит из двух ячеек памяти. Первая ячейка содержит сам элемент[1], вторая – указатель следующего элемента (его адрес). Тогда эта структура может быть представлена в виде двух массивов, которые назовём ИМЯ (компонента) и СЛЕДУЮЩАЯ (компонента) (см. рис.2).
Указатель на компоненту (индекс)
Создание стеков с помощью массивов.
Стек – это специальный тип списка, в котором все вставки и удаления выполняются только на одном конце, называемом вершиной (top). Иногда стеки называют магазинами, а в иностранной литературе для их обозначения используют аббревиатуру LIFO (last-in-first-out) – последний вошёл – первый вышел.
Реализация стеков с помощью массивов:
Стеки с их операторами – это частный случай списков с их операторами. Представив стек в виде однонаправленного списка, операторы PUSH и POP будут работать только с ячейкой заголовка и первой ячейкой списка. Фактически заголовок может быть указателем или курсором, но не полноценной ячейкой, т.к. стеки не пользуются понятием «позиция».
Массивы реализуют стеки более удобно, если принять во внимание, что вставка и удаление элементов стека происходит только через вершину стека. Можно зафиксировать «дно» стека в самом низу массива, в ячейке с наибольшим индексом, и позволить стеку расти вверх массива (к ячейке с наименьшим индексом). Указатель с именем top (вершина) будет указывать положение текущей позиции первого элемента стека. Такое представление стека выглядит на рис. 7.
Переменная top является указателем последнего элемента, добавленного к стеку. Чтобы добавить новый элемент в стек, значение top увеличивают на 1, а затем помещают новый элемент в ячейку. Но т.к. массив элементов имеет конечную длину L, то перед попыткой вставить новый элемент, следует проверить, что top < L - 1. Чтобы удалить элемент из вершины стека, надо просто уменьшить значение top на 1. Причём, не обязательно физически стирать элемент, удаляемый из стека. Чтобы узнать, пуст ли стек, достаточно проверить, не имеет ли top значение, меньшее нуля.
Обход Неориентированных графов
Поиск в ширину (BFS, Breadth-first search) — метод обхода и разметки вершин графа.
Поиск в ширину выполняется в следующем порядке: началу обхода s приписывается метка 0, смежным с ней вершинам — метка 1. Затем поочередно рассматривается окружение всех вершин с метками 1, и каждой из входящих в эти окружения вершин приписываем метку 2 и т. д.
Если исходный граф связный, то поиск в ширину пометит все его вершины. Дуги вида (i, i+1) порождают остовный бесконтурный орграф, содержащий в качестве своей части остовное ордерево, называемое поисковым деревом.
Легко увидеть, что с помощью поиска в ширину можно также занумеровать вершины, нумеруя вначале вершины с меткой 1, затем с меткой 2 и т. Д
Реализация очередей с помощью указателей
Как и для стеков, реализация списков допустима для представления очередей, но учитывая особенность очереди (вставка новых элементов только с одного, заднего конца) можно выполнить оператор ENQUEUE более про-сто, чем при представлении списков. Вместо перемещения списка от начала к концу при каждом пополнении очереди указатель можно ставить на послед-ний элемент очереди. А можно, как и со стеками, ставить указатель на начало списка. Для очередей это удобно при выполнении команд FRONT и DE-QUEUE. После исключения из очереди оператором DEQUEUE элемента х, он из очереди исключается, но останется в поле ячейки заголовка.