Индексация позволяет также производить с помощью циклов DO и FOR автоматическую,

Быструю и эффективную обработку всех данных или выделенных подмножеств данных, хранимых в массивах.В эту работу входит инициализация, поиск, хранение и модификация.

 

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

 

 

 

 

Рассмотрим,например, N-элементный массив CS100(N), в котором содержатся лексикографически упорядоченные имена студентов,слушающих в данный момент курс программирования CS100(рис. 1,а).Если студенты Гридин и Сидоров перестают посещать курс, а новый студент Дроздов добавляется, то нам бы хотелось получить новый список слушателей, приведённый на рис. 1,б. Подумайте о трудности и стоимости написания и выполнения программы, которая смогла бы перестроить массив CS100 в соответствии с этими изменениями. С другой стороны, связанный список представляет собой структуру данных, которая требует дополнительной памяти, но позволяет легко вносить такие изменения.

 

 

Связанные списки

 

На рис. 2,а массив CS100 преобразован из одномерного в двумерный мссив CS100L. В столбце 1 массива CS100L по – прежнему содержатся фамилии студентов, зачисленных на курс CS100,хотя, как явствует из рис. 2,б, теперь уже не требуется, чтобы эти фамилии были упорядочены по алфавиту. В столбце 2 массива CS100L содержатся неотрицательные целые числа, называемые связями или указателями, значениями которых являются номера строк массива, содержащих фамилию следующего студента (в алфавитном порядке) в текущем

 

 

 

списке. Звездочкой (*) мы отметили те указатели, значения которых изменились в связи с удалением фамилий ГРИДИН и СИДОРОВ и добавлением ДРОЗДОВ. Заметим, что на рис. 2,б

 

 

АДАМОВ указывает на БЕЛЯЕВ {CS100L (1, 2)=2 и CS100L(2,1)= БЕЛЯЕВ}.

БЕЛЯЕВ указывает на ЖАРИКОВ {CS100L(2, 2) =4 и CS100L (4, 1)= ЖАРИКОВ}

КУЗНЕЦОВ указывает на ДРОЗДОВ.

ДРОЗДОВ указывает на ЛИПАТОВ и т.д.

 

Массив CS100L(I,J) размера N×2 работает как линейный связанный список. Линейный связанный список – это конечный набор пар, каждая из которых состоит из информационной части INFO (ИНФО) и указующей части LINK (СВЯЗЬ). Каждая пара называется ячейкой. Если мы хотим расположить ячейки в порядке C_i1, C_{i2,... ,} C_in,то СВЯЗЬ (i_j)=i_j+1 для j=1,...,n-1,а СВЯЗЬ (i_n)=0 и указывает на конец списка.

На рис. 3,а, приведена стандартная диаграмма линейного связанного списка;на рис 3,б,приведена диаграмма связанного списка с рис.2,б.Заметим, что ГРИДИН и СИДОРОВ отсутствуют в списке на рис 3,б., хотя они присутствуют на рис 2,б., как затемненные элементы. При реализации связанных списков участвует переменная FIRST(ПЕРВЫЙ) или HEAD (ГОЛОВА), значение которой есть адрес первой ячейки списка (рис 3,а.).

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

 

 

Первый алгоритм будет удалять заданный элемент из связанного списка. Этот процесс иллюстрируется на рис. 4,где мы ищем ячейку С _i, у которой ИНФО (i)=ТРИ, передвигая указатели PREV и PTR до тех пор, пока такая ячейка не найдена. Затем мы заменяем значение СВЯЗЬ в ячейке, на которую указывает PREV, на значение СВЯЗЬ в ячейке, на которую указывает PTR. Далее следуют блок-схема (рис. 5), формальное описание и реализация этого алгоритма.

 

Algorithm DELETE (УДАЛЕНИЕ). Удаляется ячейка С_i, у которой INFO(i)=VALUE из связанного списка, первая ячейка которого задается переменной FIRST.

Шаг 1. [Выбор первой ячейки] Set PTR ←FIRST; PREV← 0/

Шаг 2. [Ячейка пуста?] While PTR ≠0 do шаг 3 od.

Шаг 3. [Это она?] If INFO (PTR)=VALUE

then [Это первая ячейка?]

if PREV=0 then [удалить спереди]

set FIRST←LINK (PRT); and STOP

else [удалить изнутри]

set LINK (PREV)←LINK(PTR);

and STOP fi

else [Выбор следующей ячейки]

set PREV←PTR; PTR←LINK(PTR) fi.

Шаг 4. [Не в списке ] НАПЕЧАТАТЬ «ЗНАЧЕНИЕ НЕ В СПИСКЕ»;

and STOP.

 

 

Следующий алгоритм будет вносить в связанный список новую ячейку. Предположим, что в списке ячейки упорядочены в порядке возрастания содержимого поля ИНФО(INFO).Этот алгоритм аналогичен алгоритму DELETE(УДАЛЕНИЕ) в том отношении, что при выполнении операции внесения используются указатели PREV и PTR.

На рис.6 Проиллюстрирован процесс внесения, причем мы предполагаем, что

ОДИН<ДВА<ТРИ<ЧЕТЫРЕ

На рис 7. и 8. приведены блок-схема и реализация следующего алгоритма:

Algorithm INSERT (ВНЕСЕНИЕ). Внести новую ячейку ROW(РЯД), где INFO(ROW)=VALUE,в упорядоченной связанный список, первая ячейка которого задаётся в FIRST(ПЕРВЫЙ).

Шаг 1. [Выбор первой ячейки] Set PTR ← FIRST; PREV ←0

Шаг 2 [Ячейка пуста?] While PTR ≠ do шаг 3 od.

Шаг 3. [Предшествует ли новая ячейка выбранной?] If VALUE≤ INFO (PTR)

then [вносится спереди?]

if PREV=0 then [внести новую ячейку спереди]

set FIRST←ROW;

LINK (ROW)←PTR;

and STOP

else [внести новую ячейку внутрь]

set LINK(PREV)←ROW;LINK (ROW)←PTR; and STOP fi

else [Выбрать очередную ячейку]

set PREV← PTR;PTR←LINK(PTR) fi.

Шаг 4. [Список пуст?] If PREV=0

then [внести новую ячейку как единственную ячейку в списке ]

set FIRST← ROW;LINK (ROW)←0; and STOP

else [внести новую ячейку в конец списка]

set LINK(PREV)←ROW; LINK (ROW)←0; and STOP fi.

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

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

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

() (() ())

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

() ((() ())

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

 

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

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

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

3. если последовательности x и y правильно построенные, то такова же и последовательность xy.

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

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

 

		Образована с помощью правил
	Элемент		Последовательность

 

_____________________________________________________________________________________

 

 

 

 

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

 

 

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

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

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

 

Покажем на примере,как стековая память помогает нам легко определить, является ли такая последовательность, как g={[ ]({[()]}{ })}, правильно построенной. Элементы g будем обозначать х₁,х ₂,…, х _n, где x _i есть одна из скобок {, }, (,), [ или ]. Элементы {, (и [ назовем ЛЕВЫМИ символами; скажем, что x_i—левый партнер х_j, если x_i= [ и х_j =], или x_i =(и x_j =), или x _i ={ и x_j =}/

 

Algorithm WELLFORMED (ПРАВИЛЬНО ПОСТРОЕННАЯ). Определяет, является ли произвольная последовательность символов x_ix₂...x_n, где каждый x_i —одна из скобок {, }, (,), [, или ],авильно построенной.

Шаг 0. [Инициализация ] Set TOP ←0; I←1.

Шаг 1. [ Читается последовательность слева направо]

While I≤ N do through шаг 3 od/

Шаг 2. [Записывается в стек ЛЕВЫЙ символ]

If х _i ЛЕВЫЙ символ then [ записывается x_i ]

else [выбирается символ из стека ]

if TOP левый партнер х_i

then выбирать элемент ТОР из памяти

else НАПЕЧАТАТЬ «НЕПРАВИЛЬНО ПОСТРОЕННАЯ»; and STOP fi fi

Шаг 3. [Прочесть следующий символ ] Set I ←I +1.

Шаг 4. [Память пуста?] If TOP=0 then PRINT «ПРАВИЛЬНО ПОСТРОЕННАЯ»;

else PRINT «НЕПРАВИЛЬНО ПОСТРОЕННАЯ» FI; and STOP.

 

 

Применим теперь алгоритм ПРАВИЛЬНО ПОСТРОЕННАЯ к последовательности

g={ [ ] ({ [ () ] } { }) }

1 2 3 4 5 6 7 8 9 10 11 12 13 14

 

На рис. 9. Приведено содержимое стека, соответствующее операциям 0чтения элементов из g слева направо. Целое значение над I- й конфигурацией стека указывает на то, что в данный момент читается x_i- й символ.

Для реализации стека на Фортране мы возьмем одномерный массив STORE[ описанный как STORE (M)] и целую переменную с именем ТОР. Всегда, когда нам нужно поместить на вершину стека элемент Х(I), мы выполняем следующие простые команды:

TOP = TOP +1

IF (TOP. GT.M) GO TO 100

STORE (TOP)=X(I)

GO TO 200

100 PRINT «ПЕРЕПОЛНЕНИЕ СТЕКА»

200 CONTINUE

 

 

Далее для выбора элемента выполняются следующие команды:

IF (TOP. EQ.0) GO TO 300

X (I) =STORE (TOP)

TOP=TOP-1

GO TO 400

300 PRINT «СТЕК ПУСТ»

400 CONTINUE

Очереди

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

 

Для моделирования очереди,как правило, используют линейный массив [например, QUEUE(500)] и две целые переменные FRONT и REAR, которые указывают на первые и последние элементы очереди соответственно. Вначале REAR≥FRONTреди добавится свыше 500 элементов, то, по-видимому,некоторые записи будут удалены из начала очереди. Если это так, то, чтобы не допустить переполнения массива, мы присваиваем REAR=1 и продолжаем заполнять очередь с начала массива. Впрочем,REAR никогда не должен перегонять FRONT.

На рис.10. показано то, что называется ситуацией одна очередь-одно обслуживание. В этом примере емкость очереди 5, конкретные клиенты помечены метками от А до Н, первый ожидающий в очереди клиент обслуживается за три единицы времени, после чего он покидает очередь. В момент Т=0 очередь пуста, и значения FRONT (F) и REAR(F) равны нулю. В момент Т=1 прибывает А,ждет 3 единицы времени и покидает очередь в момент Т=4. Клиенты B,C,D,E,G и H прибывают в моменты времени 2,3,4,7,8 и 9 соответственно.С ждет 4 единицы, прежде чем продвинуться в начало очереди, и покидает ее в момент Т=10. Когда прибывает G,в момент Т-8, конец очереди находится в массиве в положении 5.Здесь мы помещаем G в положение 1 очереди и присваиваем R=1. Когда в момент Т=9 прибываем Н, в Rзасылается 2, в этот момент очередь полностью заполнена. Теперь конец очереди сравнялся с ее началом, и, пока С не покинет очередь, в нее становится нельзя.

ПодпрограммаQADD(рис. 11) добавляет элемент VALUE к очереди. Предполагается, что, когда очередь пуста, FRONT=REAR=0.Процесс удаления элемента из очереди аналогичен. Подпрограмма QDELET(рис.12) выполняет эту работу; при удалении из очереди последнего элемента программа присваивает величинам FRONT и REAR значения, равные 0.

 

 

Деревья

Линейные массивы можно также использовать для компактного представления деревьев определенного вида.Пусть Т-дерево с М вершинами, в котором вершины помечены целыми числами 1,2,..., М. Говорят,что дерево Т рекурсивно помечено( или рекурсивное), если каждая вершина с меткой больше 1 смежа ровно с одной вершиной, у которого метка имеет меньшее зна чение. На рис. 13. Приведены примеры рекурсивного дерева Т₁ и нерекурсивного дерева Т₂

 

 

 

На примере линейного массива ДЕРЕВО показано,как комактно можно представить рекурсивное дерево Т₁; ДЕРЕВО (I)=J обозначает, что вершина I смежна вершине J.

 

	1 2 3 4 5 6 7 8 9 10
	0 1 1 1 2 4 5 4 5 1

 

TREE