|
5.2.2. Структуры данных
Структуры данных – это абстрактные структуры или классы, которые используются для организации данных и предоставляют пользователям различные операции над этими данными.
Наиболее распространенной и общеизвестной структурой данных является массив (array), который содержит непрерывную совокупность элементов данных, к которым можно получить доступ.
В любом языке программирования массивы имеют несколько общих свойств:
- Содержимое массива хранится в непрерывной области памяти.
- Все элементы массива имеют одинаковый тип; поэтому массивы называют однородными (homogeneous) структурами данных.
- Существует пряммой доступ к элементам массива. (В случае других структур данных это необязательно так. Например, в структуре данных скип-список (SkipList) для доступа к конкретному элементу скип-списка нужно предварительно осуществить поиск среди других элементов скип-списка, пока не найдется требуемый элемент. В случае с массивами, если необходимо получить доступ к i-му элементу массива, можно сделать это одной операцией: arrayName[i].)
Типичные операции для массивов включают:
- Выделение элемента(Allocation).
- Доступ к элементу (Accessing).
- Изменение размеров массива (Redimensioning).
Когда в C# объявляется массив, его значение равняется null. Например, следующая строчка кода просто создает переменную с именем booleanArray , которая равна null: bool [ ] booleanArray.
Прежде чем начать работу с массивом, следует выделить определенное количество элементов. Синтаксически это выглядит так:
booleanArray = new bool[10],
или более обобщенно:
arrayName = new arrayType[allocationSize].
Массивы являются превосходной структурой данных, если требуется хранить коллекцию однородных типов, к которым нужно иметь прямой доступ. Поиск в неотсортированном массиве занимает линейное от размера массива время. Это приемлемо, если мы работаем с маленькими массивами, или когда нам нужно лишь изредка производить поиск внутри массива. Если же приложение хранит большие массивы, в которых часто производится поиск, то существуют структуры данных гораздо лучше приспособленные к таким ситуациям.
Многомерные массивы, как и одномерные требуют постоянного времени для доступа к своим элементам. Время поиска в n-элементном массиве равно O(n). Для двумерного массива размером nxn время поиска будет равно O(n2), потому что процедура поиска должна будет просмотреть n2 элементов. В более общем случае время поиска в k-мерном массиве есть O(nk).
Несмотря на то, что обычные массивы, безусловно, находят широкое применение, они накладывают определенные ограничения на программиста, поскольку каждый массив может хранить данные только одного типа (однородность) и вдобавок перед использованием массива требуется выделять (allocate) определенное количество элементов.
Массивы позволяют хранить непрерывный блок однородных типов. Основное их преимущество состоит в исключительно малом времени доступа к своим элементам для чтения и записи. Слабое место массивов – дороговизна поиска в них, т.к. при поиске в неотсортированном массиве требуется потенциально посетить каждый элемент массива.
Структура данных 'стек'. Стеком будем называть последовательность элементов, упорядоченных по времени их поступления. Эта последовательность доступна только с одного конца (вершины стека). Для работы со стеком необходим указатель вершины стека. Основные операции над стеком следующие: "запомнить в стеке" и "извлечь из стека" (причем извлекается последний из занесенных в стек элементов - то есть элемент с вершины стека). Поэтому говорят, что стек – это структура типа 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;
|