Реализация списков посредством массивов

При реализации списков с помощью массивов элементы списка располагаются в смежных ячейках массива. На рис 6.1 представлена одна из возможных реализаций. В данном случае список представлен записью LIST, состоящей из поля last, указывающей на последний элемент списка и массива elements, в котором располагаются элементы списка. Поскольку элементы массива elements нумеруются с единицы, то значение last равно числу элементов списка. Длина массива elements храниться в константе maxlen.

Такое представление списка позволяет легко просматривать содержимое списка и вставлять новые элементы в его конец. Но вставка нового элемента в середину списка требует перемещения всех последующих элементов на одну позицию к концу массива, чтобы освободить место для нового элемента. Удаление элемента также требует перемещения элементов, чтобы закрыть освободившуюся ячейку.

Алгоритмы операторов INSERT, DELETE и LOCATE списка, реализованного на массиве, представлены блок-схемами на рис.6.2, 6.3 и 6.4 соответственно.

Реализацию остальных операторов списка сделайте самостоятельно.

Реализация списков с помощью указателей

Реализация списков с помощью указателей освобождает от использования непрерывной области памяти для хранения списка. Это позволяет избавиться от перемещения элементов списка при вставке или удалении элементов. Однако ценой за это удобство становится дополнительная память для хранения указателей. Структура списка, реализованного с помощью указателей, представлена на рис.6.5. Список представлен записью LIST, состоящей из двух полей: last и elements. В поле last хранится число элементов списка, а в поле elements - указатель на первый элемент списка. Элемент списка хранится в записи, состоящей из двух полей: element и next. Поле element содержит значение элемента списка, а поле next - указатель на следующий элемент списка.

Реализация операторов INSERT и DELETE представлена блок-схемами на рис.6.6 и 6.7 соответственно.

Реализацию остальных операторов списка сделайте самостоятельно.

Реализация списков с помощью курсоров

Некоторые языки программирования Fortran, Algol не имеют указателей. В этом случае указатели можно моделировать с помощью курсоров.

На рис. 6.8 показаны два списка M=a,b,c и L=d,e, вложенные в один массив SPACE длиной 10. Ячейки массива не занятые элементами списков образуют свободный список.

Реализация оператора INSERT списка, представленного с помощью указателей показана на рис.6.9.

Реализацию остальных операторов списка сделайте самостоятельно.

Стеки

Стек — это специальный тип списка, в котором все вставки и удаления выполняются только на одном конце, называемом вершиной (top). Стеки также иногда называют «магазинами», а в англоязычной литературе для обозначения стеков еще используется аббревиатура LIFO (last-in-first-out — последний вошел — первый вышел). Интуитивными моделями стека могут служить книги, сложенные в стопку, или стопка тарелок на полке буфета; во всех этих моделях взять можно только верхний предмет, а добавить новый объект можно, только положив его на верхний.

Абстрактные типы данных семейства STACK (cтек) обычно используют следующие пять операторов.

1. NULLSTACK(S). Делает стек S пустым.

2. TOP(S). Возвращает элемент из вершины стека S. Обычно вершина стека идентифицируется позицией 1, тогда TOP(S) можно записать в терминах общих операторов списка как RETRIVE(FIRST(S), S).

3. POP(S). Удаляет элемент из вершины стека (выталкивает из стека), в терминах операторов списка этот оператор можно записать как DELETE(FIRST(S),S). Иногда этот оператор реализуется в виде функции, возвращающей удаляемый элемент.

4. PUSH(x,S). Вставляет элемент x в вершину стека S (заталкивает элемент в стек). Элемент, ранее находившийся в вершине стека, становится элементом, следующим за вершиной, и т.д. В терминах общих операторов списка данный оператор можно записать как INSERT(x,FIRST(S),S).

5. EMPTYSTACK(S). Эта функция возвращает значение true (истина), если стек S пустой, и значение false (ложь) в противном случае.

Реализация стеков

Каждую реализацию списков можно рассматривать как реализацию стеков, поскольку стеки с их операторами являются частными случаями списков с операторами, выполняемыми над списками.

Однако реализация списков на основе массивов, рассмотренная в разд.2.4.3, приводит к тому, что каждое выполнение операторов POP(S) и PUSH(x,S) требует перемещения всех элементов стека. Поэтому время их выполнения пропорционально числу элементов в стеке. Более рациональное решение получится, если изменить вершину стека идентифицировать последней позицией списка. В этом случае реализация операций будет следующая:

TOP(S) = RETRIVE(LAST(S), S),

POP(S) = DELETE(LAST(S),S),

PUSH(x,S) = INSERT(x,ENDLIST(S),S).

Теперь операции POP(S) и PUSH(x,S) будут выполняться за одно действие.

Очереди

Другой специальный тип списка — очередь (queue), где элементы вставляются с одного конца, называемого задним (rear), а удаляются с другого, переднего (front). Очереди также называют «списками типа FIFO» (аббревиатура FIFO расшифровывается как first-in-first-out: первым вошел — первым вышел). Операторы, выполняемые над очередями, аналогичны операторам стеков. Существенное отличие между ними состоит в том, что вставка новых элементов осуществляется в конец списка, а не в начало, как в стеках. Кроме того, различна устоявшаяся терминология для стеков и очередей.

1. NULLQUEUE(Q) очищает очередьQ, делая ее пустой.

2. FRONT(Q) — функция, возвращающая первый элемент очереди Q. Можно реализовать эту функцию с помощью операторов списка как RETRIEVE(FIRST(Q),Q).

3. ENQUEUE(x,Q) вставляет элемент x в конец очереди Q. С помощью операторов списка этот оператор можно выполнить следующим образом: INSERT(x,END(Q),Q).

4. DEQUEUE(Q) удаляет первый элемент очереди Q. Также реализуем с помощью операторов списка как DELETE(FIRST(Q),Q).

5. EMPTYQUEUE(Q) возвращает значение true тогда и только тогда, когда Q является пустой очередью.

Реализация очередей

При реализации очередей, как и при реализации стеков, используется реализация списков.

Если реализация списков осуществлена на массивах, то реализация оператора удаления первого элемента очереди DEQUEUE(Q)=DELETE(FIRST(Q),Q) не эффективна т.к. требует перемещения всех элементов очереди.

Аналогичная ситуация возникала при реализации стека на списке созданного на массиве. В случае стека перемещения всех элементов удалось избежать путем идентификации вершины стека последней позицией списка. Поступим аналогично и при реализации очереди. В результате удаление первого элемента очереди будет осуществляться за одно действие DEQUEUE(Q)=DELETE(LAST(Q),Q). Однако вставка элемента в конец очереди будет осуществляться путем перемещения всех элементов очереди - ENQUEUE(x,Q)=INSERT(x,FIRST(Q),Q).

Таким образом, простым изменением идентификации первого элемента нельзя добиться выполнение обоих операторов ENQUEUE(x,Q) и DEQUEUE(Q) за одно действие. Поэтому при реализации очереди на массивах используют так называемые циклические массивы. В циклическом массиве считается, что за последним элементом следует первый элемент. Такая связь является логической и организуется программным способом.

Предложите способ реализации очереди на циклическом массиве.

Графы и деревья

Понятия теории графов широко используются при формализации различных задач. Термин "граф" ввел Д.Кенег в 1936 г.

Пусть V - непустое множество, V^{2} - множество всех его двухэлементных подмножеств. Пара (V,E), где ЕÍV^{2}, называется графом или неориентированным графом.

Элементы множества V называют вершинами графа, а элементы множества E – ребрами графа.

Ориентированным графом (орграфом), называется пара (V,E¢), где E¢ÍV´V= {(v₁,v₂)|v₁ÎV,v₂ÎV}.

То есть в ориентированном графе важен порядок вершин составляющих ребро. В ориентированных графах вместо термина «ребро» используют термин «дуга». [1]

Далее, если речь идет о графе G=(V,E) множество вершин будем обозначать VG, а множество ребер (дуг) - EG.

Граф G можно представить в виде некоторой геометрической структуры, состоящей из двух множеств: множества точек (вершин) VG и отрезков (ребер) ЕG, которые соединяют некоторые пары точек из VG. Если указаны начало и конец ребра, то отрезок заменяют направленным отрезком.

Две вершины u и v называются смежными, если множество {u,v} является ребром (дугой), и не смежными в противном случае. Также, в этом случае говорят, что u и v являются концевыми вершинами ребра e={u,v}. Для дуги e=(u,v) концевую вершину u называют началом, a v - концом дуги.

Ребра (дуги) называются смежными, если они имеют общую концевую вершину.

Вершина v и ребро (дуга) е называются инцидентными, если v концевая вершина е, и не инцидентными в противном случае.

Ребро e={v,v} или дуга e=(v,v) называется петлей.

Ребра e₁={u,v},e₂={u,v},...,е_k={u,v} называются кратными.

Дуги e₁=(u,v),e₂=(u,v),...,е_k=(u,v) называются параллельными.

Цепью называется любая последовательность попарно различных ребер (дуг), такая, что соседние ребра (дуги) в ней смежны. В орграфе если в цепи учтена ориентация дуг, то она называется путем.

Если не требовать, чтобы ребра (дуги) в упомянутой последовательности были различны, то получим понятие маршрута (ориентированного маршрута).

Циклом называется цепь, у которой начальная и конечная вершины совпадают.

Контуром называется путь, у которого начальная и конечная вершины совпадают.

Граф называется связным, если для каждой пары вершин найдется соединяющий их маршрут.

Граф, который не содержит циклов, называется ациклическим.

Связный неориентированный ациклический граф называется деревом, множество деревьев называется лесом.

Граф Н называется подграфом (или частью) графа G, если VHÍVG, ЕНÍEG. Если Н - подграф графа G, то говорят, что Н содержится в G.

Покрывающим (или остовным) деревом графа G называется дерево, являющееся подграфом графа G и содержащее все его вершины.

Если каждому ребру (дуге) графа поставлено в соответствие одно или несколько чисел, то такой граф называется взвешенным.