Структуры данных

Путь: Олимпиадные задачи по программированию » Структуры данных

Структуры данных

Предварительные сведения.

Какие бывают структуры данных?

Структура данных 'стек'.

Стеком будем называть последовательность элементов, упорядоченных по времени их поступления. Эта последовательность доступна только с одного конца (вершины стека). Для работы со стеком необходим указатель вершины стека. Основные операции над стеком следующие: "запомнить в стеке" и "извлечь из стека" (причем извлекается последний из занесенных в стек элементов - то есть элемент с вершины стека). Поэтому говорят, что стек -- это структура типа LIFO - "Last In - First Out" - "последним зашел - первым вышел". Для представления стека в программе обычно используется одномерный массив (назовем его B), нумерация элементов которого начинается с нуля. В этом нулевом элементе массива хранится индекс первого свободного места в массиве (т.е. увеличенный на 1 индекс вершины стека). Если массив пуст, то указатель равен 1 (B[0]=1).

Добавление элемента X в стек реализуется очень просто - на первое свободное место (индекс которого хранится в B[0]) помещается X, после чего индекс первого свободного места увеличивается на 1:

B[B[0]]:=x; { Занести в стек }
B[0]:=B[0]+1; { Увеличить указатель }

Если необходимо извлечь элемент x из стека, то берется последний из занесенных элементов (естественно, только в том случае, если стек непуст), и указатель на первое свободное место уменьшается на 1:

if B[0]<>1 { Если стек не пуст }
then
begin
x:=B[B[0]]; { Взять элемент }
B[0]:=B[0]-1; { Уменьшить указатель }
end;

Структура данных 'список'.

Каждый элемент списка имеет указатель на следующий за ним элемент (другими словами -- хранит информацию о расположении следующего элемента), а если список двусвязный (двунаправленный), то имеет также указатель и на предшествующий элемент. Кроме того есть переменная, указывающая на первый элемент списка. Например, двунаправленный список может быть реализован с помощью двумерного массива A[1..3,1..N], где содержимое A[2,i] определяет позицию (индекс, адрес) элемента, предшествующего элементу A[1,i], а содержимое A[3,i] определяет позицию элемента, следующего за A[1,i].

Основные операции над списком следующие: "удалить из списка" и "поместить в список".

Например, помещение в список элемента х после элемента A[1,i] может выглядеть так:

A[1,j]:=x; { Занести в массив }
A[2,j]:=i; { Изменить указатели }
A[3,j]:=A[3,i];
A[3,i]:=j;

Здесь j - адрес свободной позиции в массиве А.

Структура данных 'очередь'.

Очередь в программировании, как и очередь в магазине, имеет начало и конец. Если приходит новый элемент, то он становится в конец очереди, если необходимо взять элемент из очереди, то он берется из ее начала. Очередь будем представлять в виде массива. Пусть у нас есть индекс первого - BEG и последнего - FIN элементов очереди (если очередь пуста, то BEG=FIN+1; сначала же BEG=1, FIN=0).

Очередь опишем так: var Queue=array[1..MaxQ] of element;

Тут MaxQ - максимальное число элементов в очереди, element какой-то тип данных. В качестве element можно взять структуру следующего вида:

type element = record
x: byte;
y: byte;
end;

где element - это запись, состоящая из x-овой и y-овой координаты.

С очередью можно проводить операции:

вставка в очередь InQueue,

удаление из очереди OutQueue.

Procedure InQueue (x : element);
begin
FIN:=FIN+1;   { на первое свободное место}
Queue[FIN]:=x;  { ставим элемент x }
end;
 Procedure OutQueue (var x : element);
begin
x:=Queue[BEG]; { берем первый элемент }
BEG:=BEG+1;  { и изменяем указатель }
{ на следующий за ним }
end;

Задача 1

Вводится последовательность, состоящая из N пар символов (a_i,b_i). Каждая пара определяет порядок предшествования символов, например, пара (b,с) означает, что символ "b" предшествует символу "с". Из порядка (b,с) и (с,a) следует порядок (b,a). Необходимо определить, является ли введенная последовательность:

а) полной, т.е. все использованные для формирования пар символы (выбросив повторяющиеся) можно выстроить в цепочку (A₁,A₂,...,A_s) в порядке предшествования;

б) противоречивой, т.е. для некоторых символов x,y можно

получить одновременно порядок как (x,y) так и (y,x);