Виды структур данных

Массивы – наиболее известная и широко распространенная структура данных. Массив состоит элементов одного типа (например, чисел, символов), поэтому является однородной структурой. Встречаются и сложные массивы, когда элементом массива является массив, тогда в этом случае термин «однородность» означает, что все элементы имеют одинаковую структуру и размер. Элементы массива равноправны, поэтому данная структура данных является линейной. Элементы массива пронумерованы индексом, т.е. структура также называется упорядоченной. Именно по индексу можно выделить нужный элемент структуры (рис. 3.2.1.1).
Рис. 3.2.1.1. Одномерный массив
Число индексов, определяющих положение элементов в массиве, называется мерностью массива. Мерность массива может быть ограничена синтаксисом некоторых языков программирования, а может и не иметь таких ограничений. Если индекс один, то массив является одномерным (вектор, строка или столбец), если два – двумерным (матрица), если индексов больше двух, то массив называется многомерным (n-мерным). Запись массивов выглядит следующим образом: для одномерного массива xi – i-й элемент массива x; также в языках программирования принята запись x[i] или x(i). Пример обозначения элемента двумерного массива: x[i,j], где i – номер строки элемента, j – номер столбца. Как видим, обращение к элементу массива состоит из имени массива x, к которому добавляется необходимое нам значение индекса i или i, j.
Размер массива определяется максимальным значением индекса. Размер массива указывается в блоке описания программы, так как под него резервируется необходимый объем памяти. Массив может быть статическим (размер массива в ходе выполнения программы остается фиксированным) и динамическим (определение и изменение размеров массива происходит в процессе выполнения программы).
Рассмотрим задание массивов на примере синтаксиса языка программирования PASCAL. N-мерный статический массив задается следующим образом:
Var
имя массива: array[тип_индекса1, ... , тип_индексаN] of базовый тип;
Для одномерного массива в объявлении используется только один тип индекса, поэтому синтаксис объявления одномерного массива имеет вид:
Var
имя_одномерного_массива: array[тип_индекса] of базовый_тип;
Например, оператор
Var
sampleArray: array[1..20] of Integer;
объявляет массив sampleArray, содержащий 20 чисел типа Integer, причем значение индексов изменяется от 1 до 20.
Далее объявляется двухмерный массив:
Var
sample2Array: array[1..20, 1..10] of Integer;
Как видим из формы объявления массива, двумерный массив можно представить как массив массивов.
Для объявления динамического массива используется оператор array of  без задания индексов

. Синтаксис объявления одномерного динамического массива имеет вид:
Var
имя_динамического_массива: array of базовый_тип;
Задание размера массива и выделение для него памяти выполняется с помощью процедуры SetLength().
SetLength(имя_динамического_массива, длина);
В этом синтаксисе выражение длина должно быть целого типа. Процедуру SetLength() в процессе выполнения программы можно вызывать произвольное количество раз. Каждый вызов приводит к изменению длины массива, причем содержимое массива сохраняется. Если при вызове SetLength() длина массива увеличивается, то добавленные элементы заполняются произвольными значениями. Если длина массива уменьшается, то содержимое отброшенных элементов теряется.
Следует обратить внимание на символьные массивы – строки (например, тип String в PASCAL). Данные массивы используются для хранения символов. Со строковыми данными возможен целый набор операций, таких как присваивание одной строки другой, объединения строк с формированием новой строки (конкатенация), коррекция символов строки.
3.2.2. Стек
Стек – это структура данных типа «список», элементы которой построены по принципу LIFO (last in — first out, «последним пришел – первым вышел»). Эти структуры реализуются в виде специальным образом организованных областей ОЗУ компьютера либо в качестве самостоятельных блоков памяти.
В стеке элементы соединяются таким образом, что при считывании данных содержимое стека сдвигается вверх по ячейкам, а при занесении данных в первую ячейку – вниз, как показано на рис. 3.2.2.1.
Рис. 3.2.2.1. Структура стека
Таким образом, получить доступ к элементам стека можно с одного конца, называемого вершиной стека. Сравнить принцип хранения данных в стеке можно со стопкой книг. Чтобы взять книгу, лежащую в самом низу, нужно поднять все вышележащие книги, а добавить новую книгу в стопку можно одним способом – положить ее поверх всех остальных. Другими словами, войти в стек можно только через первую ячейку, а извлекаться будет та информация, которая была занесена последней. Следовательно, структура данных стек является линейной и упорядоченной, так как структура имеет определенный порядок расположения элементов, и все элементы между собой равноправны