Индексация позволяет также производить с помощью циклов 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 (СВЯЗЬ). Каждая пара называется ячейкой. Если мы хотим расположить ячейки в порядке Ci1,Ci2,...,Cin,то СВЯЗЬ (ij)=ij+1 для j=1,...,n-1,а СВЯЗЬ (in)=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 .[Выбор первой ячейки] SetPTR ←FIRST; PREV← 0/
Шаг 2. [Ячейка пуста ?] While PTR ≠0 doшаг 3od.
Шаг 3.[Это она?] IfINFO (PTR)=VALUE
then[Это первая ячейка?]
if PREV=0 then[удалить спереди]
setFIRST←LINK (PRT); andSTOP
else [удалить изнутри]
set LINK (PREV)←LINK(PTR);
andSTOP 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. [Выбор первой ячейки] SetPTR←FIRST; PREV←0
Шаг 2[Ячейка пуста ?]WhilePTR≠ doшаг 3 od.
Шаг 3. [Предшествует ли новая ячейка выбранной?] IfVALUE≤ INFO (PTR)
then[вносится спереди?]
ifPREV=0 then[внести новую ячейку спереди]
setFIRST←ROW;
LINK (ROW)←PTR;
and STOP
else [внести новую ячейку внутрь]
setLINK(PREV)←ROW;LINK (ROW)←PTR;andSTOP fi
else[Выбрать очередную ячейку]
set PREV← PTR;PTR←LINK(PTR) fi.
Шаг 4.[Список пуст?] IfPREV=0
then[внести новую ячейку как единственную ячейку в списке ]
set FIRST← ROW;LINK (ROW)←0;andSTOP
else [внести новую ячейку в конец списка]
setLINK(PREV)←ROW; LINK (ROW)←0; andSTOPfi.
Стековые списки и стеки
Мы увидели , что (линейные) связанные списки – это эффективная структура данных для моделирования ситуаций , в которых подвергаются изменениям упорядоченные массивы элементов данных . В частности . это справедливо для случая , когда модификациями являются главным образом внесение элементов в середину массивов или удаление элементов из середины массива . Когда модификации касаются лишь начала и конца , необходимость в связанных списках исчезает, и стонавятся достаточными простые линейные (одномерные) массивы.
В качестве примера рассмртрим следующую задачу. Во всех компиляторах с языков программирования требуется узнавать , является ли произвольное выражение правильно построенным . в частности , нужно определять , правильно ли расставлены в выражении скобки. Например, последовательность
( ) (( ) ( ))
представляет правильную последовательность скобок, а
( ) ((( ) ( ))
неправильную (есть лишние левые скобки).В более широком математическом контексте в арифметическом выражении обычно встречаются также квадратные скобки [ ] и фигурные скобки { }.
Предположим, что вас попросили разработать алгоритм определения того , что произвольная последовательность круглых, квадратных и фигурных скобок является правильно построенной .Что мы понимаем под правильно построенной последовательностью ? Обычное определение состоит в следующем:
1. Последовательности ( ), [ ] и { } являются правильно построенными.
2. Если последовательность х правильно построенная ,то правильно построены и последовательности (х),[x] и{x}.
3. если последовательности x и y правильно построенные , то такова же и последовательность xy.
4. Правильно построенными являются лишь те последовательности, правильность которых следует из конечной последовательности применений правил 1,2 и ,3.
Это определение определяет правильно построенные последовательности конструктивно. Например, следующие последовательности являются правильно построенными:
| |||||
|
| ||||
_____________________________________________________________________________________
Обычно ,чтобы установить, являются ли выражения такого типа правильно построенными , используют стековую память ( или просто стек ), которая представляет собой бесконечную в одну сторону последовательность слов памяти , как изображено на рис. 8
Для запоминания элементов данных в стеке элемент заносят в верхнее слово ТОР (ВЕРШИНА), сдвигая тем самым вниз (по одному слову) все другие слова, хранящиеся в стеке (совершенно аналогично тому,как в столовой складывают подносы в стопку ). Выбор элементов данных из стека возможен лишь считыванием по одному за раз из слова ТОР , причем все остальные элементы данных сдвигаются вверх.
Мы не имеем права выбирать элементы данных внутри стека. (В столовой мы обычно не выбираем двадцатый поднос из стопки подносов.) Иногда термин « стек» обозначает стековую память , когда нам разрешено считывать элементы , находящиеся ниже слова ТОР, но не разрешается изменять их значения или добавлять новые элементы ниже слова ТОР.
|
Покажем на примере ,как стековая память помогает нам легко определить, является ли такая последовательность, как g={[ ]({[( )]}{ })}, правильно построенной. Элементы g будем обозначать х1,х2,… ,хn , где xi есть одна из скобок {, } , ( , ), [ или ]. Элементы {, ( и [ назовем ЛЕВЫМИ символами ; скажем, что xi—левый партнер хj, если xi=[ и хj=] , или xi=( и xj=), или xi ={ и xj =}/
Algorithm WELLFORMED(ПРАВИЛЬНО ПОСТРОЕННАЯ). Определяет, является ли произвольная последовательность символов xix2...xn,где каждый xi—одна из скобок {, }, (, ), [, или ],авильно построенной .
Шаг 0. [Инициализация ]SetTOP ←0; I←1.
Шаг 1.[ Читается последовательность слева направо]
While I≤N do throughшаг 3 od/
Шаг 2.[Записывается в стек ЛЕВЫЙ символ]
Ifхi ЛЕВЫЙ символ then[ записывается xi]
else[выбирается символ из стека ]
ifTOP левый партнер хi
thenвыбирать элемент ТОР из памяти
elseНАПЕЧАТАТЬ « НЕПРАВИЛЬНО ПОСТРОЕННАЯ»; andSTOP fi fi
Шаг 3.[Прочесть следующий символ ] Set I ←I +1.
Шаг 4 . [Память пуста?] IfTOP=0 thenPRINT « ПРАВИЛЬНО ПОСТРОЕННАЯ»;
elsePRINT « НЕПРАВИЛЬНО ПОСТРОЕННАЯ» FI ; andSTOP.
Применим теперь алгоритм ПРАВИЛЬНО ПОСТРОЕННАЯ к последовательности
g={ [ ] ( { [ ( ) ] } { } ) }
1 2 3 4 5 6 7 8 9 10 11 12 13 14
На рис. 9. Приведено содержимое стека , соответствующее операциям 0чтения элементов из g слева направо . Целое значение над I-й конфигурацией стека указывает на то , что в данный момент читается xi-й символ.
Для реализации стека на Фортране мы возьмем одномерный массив 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. Приведены примеры рекурсивного дерева Т1 и нерекурсивного дерева Т2
На примере линейного массива ДЕРЕВО показано ,как комактно можно представить рекурсивное дерево Т1; ДЕРЕВО (I)=J обозначает , что вершина I смежна вершине J.
| ||
|
|