Алгоритмический язык Паскаль (стр. 18 из 31)

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

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

Иногда оно занимает более одной ячейки (байта) памяти, но простая переменная идентифицируется с первым адресом этой цепочки ячеек.

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

К простым типам данных относятся: числа (INTEGER, REAL), логические величины (BOOLEAN), символы (CHAR), цепочки литер (STRING), цепочки битов (BIT), указатели (POINTER). Последние два типа относятся к типам данных, образуемых самой системой, а не программистом.

Очевидно, что простые переменные можно условно отнести к структуре прямого доступа, т.к. всегда можно выйти на значение переменной по ее имени.

Массивы фиксированного размера являются наиболее распространенными структурами данных. Большинство языков обеспечивают такие массивы в качестве основного встроенного типа структур данных.

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

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

Значения элементов вектора хранятся физически в памяти также в виде последовательности, т.е. структура вектора однозначно отображается на структуру памяти ЭВМ. При этом индекс элемента массива означает адрес ячейки памяти, содержащей значение этого элемента, относительно адреса ячейки памяти, хранящей значение первого элемента данного массива.

Память	101	102	103	104	105	106	107
(ячейки)
Вектор Х	X[1]	X[2]	X[3]	X[4]	X[5]	X[6]	X[7]

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

	[1,1]	[1,2]	[1,3]	[1,4]	Двумерный массив
[2,1]	[2,2]	[2,3]	[2,4]	(матрица)
[3,1]	[3,2]	[3,3]	[3,4]
	[4,1]	[4,2]	[4,3]	[4,4]
Память
	[1,1]	[1,2]	[1,3]	[1,4]	[2,1]	[2,2]	[2,3]	[2,4]	[3,1]	[3,2]	…

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

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

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

Если в массиве фиксированного размера главной операцией был доступ к элементу, то здесь уже в качестве основных операций фигурируют включение новых элементов и исключение существующих. Доступ к элементам массивов чаще всего относительный: найти элемент, следующий (или предыдущий) по отношению к данному, найти первый (последний) элемент и т.д.

Очереди - это структуры данных, организованные по принципу "первым пришел - первым ушел". Обработка элементов очереди ведется последовательно, причем элемент, который первым попал в очередь, первым обрабатывается и покидает ее. Добавление новых элементов производится в конец очереди.

Элементы, находящиеся в середине очереди, недоступны для обработки. Следовательно, доступными являются только два элемента:

первый ("голова") и последний ("хвост"). Над первым элементом выполняются операции чтения и обработки, над последним – операция записи в очередь. Для отображения очереди используются как последовательные, так и связанные представления.

Для последовательного представления можно использовать одномерный массив А[1], А[2],..., А[N], причем длина N этого массива выбирается с таким запасом, чтобы длина очереди не превышала N.

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

На практике для отображения очереди применяют способ введения двух указателей (индексов), один из которых ссылается на элемент массива, хранящий "голову" очереди, а другой - на элемент массива, предназначенный для записи очередного элемента очереди ("хвост").

Пусть I - индекс элемента массива, хранящего "голову" очереди, а J - индекс первого свободного элемента массива, куда поступает новый элемент очереди ("хвост"). Тогда выборка очередного элемента очереди для обработки сводится к выполнению операций:

X:=А[I]; I:=I+1.

После этого индекс I указывает на следующий элемент очереди, т.е. "головой" ее становится следующий по порядку элемент. Запись нового элемента Y в очередь сводится к выполнению операций:

А[J]:=Y; J:=J+1.

Теперь индекс J снова указывает на первый свободный элемент массива.

Элементы очереди могут поступать и обрабатываться неравномерно, поэтому длина ее будет изменяться. В частности, возможен случай, когда очередь окажется пустой. Признаком этого может служить равенство I = J после чтения головного элемента очереди.

В процессе обработки очереди ее элементы будут смещаться к концу массива, т.к. J увеличивается после каждой записи в очередь. Поэтому возможен случай J > N после записи в очередь очередного элемента. При этом надо сместить очередь в начало массива, т.е. положить I = 1 и последовательно переписать все элементы очереди в элементы массива, начиная с А[1].

Чтобы избежать этой работы, можно замкнуть массив (очередь) по кольцу, т.е. элементом, следующим за последним элементом массива, считать его первый элемент:

	I голова		.	.	.	хвост	J
.	.	.
A[1]	A[2]	A[3]	A[N-2]	A[N-1]	A[N]

При такой закольцовке просто определить переполнение очереди. Признаком этого факта является условие J = I, т.е. признак того, что "хвост" совпал с "головою" очереди.

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

Очередь
Указатель начала
Указатель конца
	…

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