Использование параллельных массивов

Значения всех элементов списка можно хранить в одном массиве, а ссылки на следующий элемент - в другом массиве. Массивов может потребоваться и больше: по количеству полей, если значение элемента списка состоит из нескольких полей. Разные поля каждого элемента располагаются в разных мас­сивах с одним и тем же индексом. Количество элементов в этих массивах оди­наково. Такие массивы на рисунках удобно изображать рядом ("параллельно"), и их называют параллельными.

В качестве ссылок используются индексы. Роль пустой ссылки может играть 0, -1 (чтобы можно было использовать нулевые элементы) или любое другое значение, не являющееся индексом. Одни и те же массивы образуют область памяти для хранения нескольких списков с одинаковым строением эле­ментов - так называемую кучу.

Предположим, что значением элемента списка является один символ. На рис. 2.12 показан такой список, содержащий текст "СЛОН" и расположенный в параллельных массивах zn и uk (имена взяты по аналогии с рис. 2.11).

Рис. 2.12. Организация списков с помощью параллельных массивов (со списком свободной памяти)

Для организации таких списков можно, например, по аналогии с приве­денными обозначениями для ссылочных переменных (пример 2.2) поместить в программу описания из примера 2.3.

Пример 2.3. Описание данных для списков с использованием параллель­ных массивов

#define N 1000 /* Максимальное кол-во элементов списков */

#define NOL 0 /* Пустой указатель */

typedef int ukaz; /* Тип указателя */

charzn[N+l]; /* Значения элементов (информация) */

ukazuk[N+l]; /* Указатели следующего элемента */

ukaz p; /* Указатель списка */

ukaz i,j; /* Указатели элементов списка */

char sim;

3.1. Очередь

Очередь - это упорядоченная последовательность элементов, в когорой выполняются операции включения и исключения элемента по принципу FIFO (First-In-First-Out) - "первым пришел - первым ушел", т.е. исключение всегда происходит в начале очереди, а включение - в конце (рис. 3.1).

Q[i]

Q[2]

...

Q[n]

Исключение Начало

элементов

Рис. 3.1. Очередь

Элементы данных помещаются в очередь, когда скорость поступления данных временно превышает скорость их обработки. Примером очереди явля­ется буфер ввода-вывода данных - область памяти для ввода-вывода записей файла параллельно с их обработкой. В операционных системах возникают мно­гочисленные очереди программ: на загрузку в память, на выполнение к процес­сору, на обработку файлов и т.д. Очередь можно рассматривать как механизм запоминания подзадач, возникающих при решении некоторой задачи, с после­дующим решением подзадач в порядке их возникновения. Пример такого при­менения очереди приведен в алгоритме 4.3 обхода дерева в ширину.

Типовые операции над очередью:

1. Инициализация очереди (создание, подготовка к работе).

2. Включение элемента в очередь.

3. Исключение элемента из очереди.

4. Проверка пустоты очереди.

5. Проверка переполнения очереди.

6. Доступ к началу и концу (получение/изменение значения мерного/последнего элемента).

Представление очереди в виде вектора Очередь удобно представлять в виде циклического (кольцевого) нектара (в котором за последним элементом следует первый) с указателями начали и конца (рис. 3.2).

а) Индекс начала меньше индекса конца б) Индекс начала больше индекса конца

Рис. 3.2. Хранение очереди в виде циклического вектора (показаны два состояния)

Пример 3.1. Описание данных для представления очереди циклическим вектором:

#defmeN 100 /* Максимальная длина очереди */

Тип-элемента q[N+l]; /* Отображающий вектор очереди */

int un; /* Указатель начала (индекс первого элемента) */

int uk; /* Указатель конца (индекс первого свободного элемента в конце очереди) */

Пример 3.2. Инициализация (создание) пустой очереди: un = uk= 0;

Пример 3.3. Исключение из очереди элемента и присваивание его величине х (обозначим эту операцию х<==Очередь):

Тип-элемента х; /* Значение исключенного элемента */

if (un!= uk) // В очереди есть элементы

{ х = q[un]; // Запоминание значения

if (un < N) un++; else un=0; /* Исключение элемента

}

else... /* Очередь пустая

Пример 3.4. Включение в очередь элемента, равного х (обозначим эту операцию Очередь<== х):

Тип-элемента х; /* Включаемое значение

int i; / */ */

if (uk < N) i=uk+l; else i=0; /* Новое значение uk */

if (i!= un) /* Есть место в очереди */

{ q[uk] = х; /* Включение в очередь значения х */

uk = i;

else … /* Переполнение очереди */

Представление в виде списка удобно для элементов переменного разме­ра, очереди труднопредсказуемого размера и для очереди с приоритетами.

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

Рассмотрим описание данных и алгоритмы типовых операций для пред­ставления очереди списком, как на рис. 3.4.

Пример 3.1 а. Описание данных для представления очереди в виде списка:

struct el_oeh /* Тип элемента списка */

{ Тип-элемепта inf; /* Информация */

struct cl och *sled; /* Ссылка на следующий элемент */

};

struct el_och f; /* Фиктивный начальный элемент */

struct el_och *uk; /* Указатель конца очереди */

Пример 3.2 а. Инициализация (создание) пустой очереди:

f'.slеd = NULL; /* Указатель начала очереди */

uk = &f; /* Указатель конца очереди */

Пример 3.3 а. Исключение из очереди элемента и присваивание его переменной х (обозначим эту операцию х<==Очередь):

Тип-элемента х; /* Значение исключенного элемента */

struct el_och *i; /* Указатель исключенного элемента */

if (f.sled!= NULL) /* В очереди есть элементы */

{ х = f.sled->inf; /* Запоминание значения */

i = f.sled;

f.sled = f.sled->sled; /* Исключение элемента */

free (i); /* Освобождение памяти */

if (f.sled == NULL) uk = &f; /* Очередь стала пустой */

}

else... /* Очередь пуста */

Пример 3.4 а. Включение в очередь элемента, равного х (обозначим эту операцию Очередь <== х):

Тип-элемента х; /* Включаемое значение */

struct el_och *i; /* Указатель включаемого элемента */

i = malloc (sizeof(struct el_och)); /* Получение памяти */

if(i!=NULL) /* Есть место' */

{ i->inf = х; /* Запись информации */

i->sled = NULL; /* Запись ссылки */

uk.slcd = i; /* Соединить *i с концом очереди */

uk = i; /* Новый указатель конца */

} else... /* Переполнение очереди */

Стек

Стек (stack) - это упорядоченная последовательность элементов, в кото­рой выполняются операции включения и исключения элемента по принципу LIFO (Last-In-First-Out) - "последним пришел - первым ушел", т.е. включение и исключение всегда происходят в одном конце (рис. 3.5). Этот конец называют верхом, противоположный - дном стека. Другие названия стека: магазин (но аналогии с магазином пистолета или автомата), очередь типа LIFO.

Рис. 3.5. Стек

Пример стека - стопка подносов в столовой, где подносы берутся и кла­дутся только сверху.

Типовые операции над стеком:

1. Инициализация (создание, подготовка к работе);

2. Вталкивание (включение) элемента - PUSH;

3. Выталкивание (исключение) элемента - POP;

4. Проверка пустоты стека;

5. Проверка переполнения стека;

6. Доступ к вершине (получение/изменение значения последнего посту­пившего элемента).

Представление стека в виде вектора

Чаще всего стек представляется в виде вектора с указателем (рис. 3.6). Часть вектора занимает стек, часть - свободное пространство. Указателем стека служит индекс последнего из поступивших элементов (либо индекс первой свободной позиции).

Рис. 3.6. Хранение стека в виде вектора

Указатель стека увеличивается на единицу при вталкивании элемента и уменьшается при выталкивании (или наоборот, если стек расположен в конце вектора).

Два стека удобно хранить в одном векторе, заполняя их навстречу друг Другу (рис. 3.7).

Рис. 3.7. Хранение двух стеков в одном векторе

Этот способ позволяет расти любому из двух стеков, пока есть хотя бы одна свободная ячейка. Максимальные размеры каждого стека и их суммы равны длине вектора. Для большего количества стеков подобного метода не сущест­вует.

Пример 3.5.Описание данных для представления стека вектором

tfdefme N100 /* Максимальная длина стека */

Тип-элемента st[N]; /* Отображающий вектор стека */

int ist; /* Указатель стека (индекс последнего элемента) */

Пример 3.6. Инициализация (создание) пустого стека:

ist = -1;

Пример 3.7.Выталкивание из стека элемента и присваивание его величине х (обозначим эту операцию х <== Стек; без запоминания элемента: <== Стек):

Тип-элемента х; /* Значение вытолкнутого элемента */

if(ist>=0) /* В стеке есть элементы */

{ х = st[ist]; /* Получение значения */

ist—; /* Выталкивание элемента */

}

else... /* Стек пуст */

Пример 3.8. Вталкивание в стек элемента, равного х (обозначим эту опе­рацию Стек <== х):

Тип-элемента х; /* Вталкиваемое значение */

if(ist<N-l) /* Есть место в стеке

{ ist++; /* Увеличение стека

st[ist] = х; /* Запись х в вершину стека

}

else.../* Стек переполнен

Представление стека в виде списка

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

Рис. 3.8. Стек в виде списка

СМ ЛЕКЦИИ ЖЕНИ

Дек

Дек (deque - double-ended queue: двусторонняя очередь) - это упорядо­ченная последовательность элементов, в которой включение и исключение элемента могут выполняться в обоих концах (рис. 3.9). Дек является обобщением очереди и стека.

Рис. 3.9. Дек

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

Операции с деком аналогичны операциям над очередью и стеком. Хра­нится дек подобно очереди, в виде циклического вектора или списка с двумя указателями.