13 41 25 34 21 45 42

Рис 2.3.10. Представление сети в форме связанного списка.

На рис. 2.3. П приведен фрагмент программы на Фортране, с помощью которого можно получить списки смежности на рис. 2.3.10, е по ребрам, заданньм в порядке, указанном на рис. 2.3.10,6.

Стековые списки и стеки

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

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

ли произвольное выражение правильно построенным. В частности, нужно определять, правильно ли расставлены в выражении скобки. Например, последовательность

()(()())

представляет правильную последовательность скобок, а

()((()())

неправильную (есть лишние левые скобки). В более широком математическом контексте в арифметическом выражении обычно встречаются также квадратные скобки [ ] и фигурные скобки { }.

00 а I = iiioo

ADJ(I) = о NEXT(I) = О а CONTINUE

с ввод ЧИСЛА ВЕРШИН Р

READ<5tlOO0)P 1000 F0R4AT{2I3) С

1 = р+1 .

с ввод ребер (M,N) ДЛЯ G

100 READ(StlO00)HiN

С • - если М ОТРИЦАТЕЛЬНО, С БОЛЬШЕ ребер НЕТ

IF ( П .LT. О ) GOTO 200

ADJdl = и NEXT(I) = fJEXT(H». НЕХТ(И) = I 1 = 1+1 ADJ(I) = n ИЕХТ(1) г fJEXT(N) NEXT(N) s I I = 1*1

С ВВОД нового РЕБРА

GOTO 100

с ПРОДОЛЖЕНИЕ ГРОГРАИИЫ

200 •

Рис 2.3.11. Фрагмент программы для представления сети в форме связанного списка.

Предположим, что вас попросили разработать алгоритм определения того, что произвольная последовательность круглых, квадратных и фигурных скобок является правильно построенной. Что мы понимаем Под правильно построенной последовательностью? Обычное определение состоит в следующем:

1. Последовательности ( ), I ] и { } являются правильно построенньми.

2. Если последовательность х правильно построенная, то правильно построены и последовательности (х), \х\ и {-}

3. Если последовательности хм. у правильно построенные, то такова же и последовательность ху.

4. Правильно построенными являются лишь те последовательности, правильность которых следует из конечной последовательности применений правил 1, 2 и 3.

Это определение определяет правильно построенные последовательности конструктивно. Например, следующие последовательности являются правильно построенными:

Элемент

Последовательность

Образована с помощью правил

а б в г д е ж

( )

[( )]

{[( )]}

{[( )]}{ }

({[( )]}{ })

f ]({[( )]}{ })

{[ ]({[( )]}{ })}

2 и й 2 и б 1, 3 и в 2 и г I, 3 и д 2 и е

• Вершат

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

Для запоминания элемента данных в стеке элемент заносят в верхнее слово ТОР (ВЕРШИНА), сдвигая тем самьм вниз (по одному слову) все другие слова хранящиеся в стеке (совершенно аналогично тому, как в столовой складывают подносы в стопку). Выбор элементов данных из стека возможен лишь считыванием по одному за раз из слова ТОР, причем все остальные элементы данных сдвигаются вверх.

Мы не имеем права выбирать элементы данных внутри стека. (В столовой мы обычно не выбираем двадцатый поднос из стопки подносов.) Иногда термин «стек» обозначает стековую память, когда нам разрешено считьшать элементы, находящиеся ниже слова ТОР, но не разрешается изменять их значения или добавлять новые элементы ниже

Рис 2.3.12. Диаграмма стековой памяти.

слова ТОР.