Главная  Полное построение алгоритма 

[0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [ 22 ] [23] [24] [25] [26] [27] [28] [29] [30] [31] [32] [33] [34] [35] [36] [37] [38] [39] [40] [41] [42] [43] [44] [45] [46] [47] [48] [49] [50] [51] [52] [53] [54] [55] [56] [57] [58] [59] [60] [61] [62] [63] [64] [65] [66] [67] [68] [69] [70] [71] [72] [73] [74] [75] [76] [77] [78] [79] [80] [81] [82] [83] [84] [85] [86] [87] [88] [89] [90] [91] [92] [93] [94] [95] [96] [97] [98] [99] [100] [101] [102] [103] [104] [105] [106] [107] [108] [109] [110] [111] [112] [113] [114] [115] [116] [117]

Покажем на примере, как стековая память помогает нам легко определить, является ли такая последовательность, как g={[ ] ({[( )й{ })}• правильно построенной. Элементы g будем обозначать

Хи Хг.....Хп, где Xi есть одна из скобок {, ), (, ), [ или ].

Элементы {, ( и [ назовем ЛЕВЫМИ символами; скажем, что Xi - мвый партнер Xj, если Xi=[ и xj=], ила Xi={ и Xj-=), или

Xi={ и Xj=}.

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

Шаг 0. [Инициализация] Set ТОРч-0; /1. Шаг 1. [Читается последовательность слева направо] While /<iV do through шаг 3 od. Шаг 2. [Записывается в стек ЛЕВЫЙ символ]

И Xi ЛЕВЫЙ символ then [записывается else [выбирается символ из стека] if ТОР левый партнер Xj

then выбрать элемент ТОР из памяти else НАПЕЧАТАТЬ «НЕПРАВИЛЬНО ПОСТРОЕННАЯ»; and STOP fi fi. Шаг 3. [Прочесть следующий символ] Set / /-f 1. Шаг 4. [Память пуста?] К ТОР=0 then PRINT «ПРАВИЛЬНО ПОСТРОЕННАЯ»;

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

STOP.

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

g={ [](([()]} { } ) } 1 2 3 4 5 6 7 8 9 10 11 12 13 14

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

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

ТОР = ТОР+1

IF (ТОР. GT. М) GO ТО 100 STORE (ТОР) =Х(1) GO ТО 200

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



CONTINUE

>

>

Рис 2.3.13. Конфигурации стековой памяти при работе алгоритма WELL-FORMED (ПРАВИЛЬНО ПОСТРОЕННАЯ).

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

IF (ТОР. EQ. 0) GO ТО 300 X(I) = STORE(TOP) ТОР = ТОР -1 GO ТО 400 300 PRINT «СТЕК ПУСТ» 400 CONTINUE

Очереди

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



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

F=0 В=0

Рис. 2.3.14. Реализация очереди с использованием линейного массива.

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

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

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



[0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [ 22 ] [23] [24] [25] [26] [27] [28] [29] [30] [31] [32] [33] [34] [35] [36] [37] [38] [39] [40] [41] [42] [43] [44] [45] [46] [47] [48] [49] [50] [51] [52] [53] [54] [55] [56] [57] [58] [59] [60] [61] [62] [63] [64] [65] [66] [67] [68] [69] [70] [71] [72] [73] [74] [75] [76] [77] [78] [79] [80] [81] [82] [83] [84] [85] [86] [87] [88] [89] [90] [91] [92] [93] [94] [95] [96] [97] [98] [99] [100] [101] [102] [103] [104] [105] [106] [107] [108] [109] [110] [111] [112] [113] [114] [115] [116] [117]

0.0012