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

Основные понятия

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

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

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

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

Каждая операция или функция требует аргумента определенного типа, и результат будет также фиксированного типа.

Простейшие типы данных

Простейший тип данных определяется перечислением входящих в него значений. Такой тип называется перечисляемым и определяется следующим образом:

TYPE T = (С1, С2, ..., Cn) где Т - идентификатор, т.е. нечто, что идентифицирует что-то.

Ci - идентификаторы констант Сi - Cn

card (T) = n - количество возможных значений С1, С2,..., Сn , которое называется мощностью данного типа (данных значений С1, С2,..., Сn)

Пример:

TYPE color = (red, black, green)
TYPE stud = (Andrey, Semyn, Iordane)

Определение таких типов вводит идентификатор типа (например,color), а также идентификаторы значений этого типа (например, green, red), которые можно использовать в программе как константы.

Пример:

VAR A: color
А
:= red

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

INTEGER, REAL, BOOLEAN, CHAR.

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

сложение

вычитание

умножение

деление

Тип REAL обозначает подмножество вещественных чисел

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

Значения стандартного типа BOOLEAN обозначаются как TRUE и FALSE.

Булевы операции - это логическая коньюкция (&, and, Щ ), логическая дизъюнкция (+, or, Ъ), логическое отрицание (not), а также все операции сравнения дают результат типа BOOLEAN.

Тип CHAR содержит 26 прописных латинских букв и 26 строчных, 10 арабских цифр и некоторые другие символы ( . , - ...), кроме того ещё содержит непечатный символ (?разделитель¦ или пробел).

У всех из них есть коды.

Ограниченные типы (диапазоны)

Если переменной присваивается значение некоторого типа, лежащая только внутри определенного диапазона, то говорят, что переменная относится к ограниченному типу (диапазону).

TYPE T = [ min...max ], где min и max - это значения определяющие границы диапазона, это в основном константы.

Пример:

TYPE year = [1900...1999]
TYPE digit = [`0`... `9` ]

Массивы, записи и множества

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

T[1]

T[2]

T[3]

T[4]

T[5]

       

TYPE T = ARRAY [ Ti ] OF T0 , где

T0 - базовый тип ( всего массива).

Ti - тип индекса. Например:

TYPE NUN = ARRAY [ 1...5 ] OF INTEGER

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

Card(T) = card(T0) Card(Ti )

Компоненты массива принято называть компонентами с индексами (например, Х[i]), при этом переменный массив рассматривается как массив состоящий из переменных.

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

Пример:

a := 1;
b := 3;
Х[i] ;
i = a+b-1 = > X[a+b-1]

Объединение элементов произвольных типов позволяет получать элементы составных типов. К составным типам можно отнести, например, комплексные числа, состоящие из 2 вещественных чисел, либо координаты точки, состоящие из 2 и более чисел, или, например человек, описываемый несколькими характеристиками.

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

Мощность составного типа равно произведению мощностей составляющих тип. Данные приведенного характера носят название записи (record).

Тип Т с компонентами Т1, Т2,-, Тn обозначают так:

TYPE T = RECORD   S1 T1
                                    S2 T2
                                      -
                                    Sn Tn
                 END

Мощность множества: card (T) = card(T1) * card(T2)-*card(TN)

Пример:

TYPE data = RECORD  day: [1-.30];
                                        Month: [1-.12];
                                        Year: [1-.2000];
                      END

Величины S1, S2,-, SN - это имена, которые получают отдельные компоненты переменных данного типа.

Поле 1 1 S1
Поле 2 4 S2
Поле 3 1998 S3

Имена полей - S1, S2, -, SN.

Компоненты записи называются полями.

Имена полей называются идентификаторами полей.

Множество v ещё один из основных классов данных.

TYPE T = SET OF T0

Возможными значениями некоторой переменной X типа Т будут множества элементов типа Т0 .

Множество всех подмножеств из элементов множества Т0 называется множеством v степенью Т0.

Пример:

TYPE BITSET = SET OF [0-.15] ;
B: BITSET ;
B:{2,3,4,5,7,11}

Для всех множественных типов определены следующие элементарные операции:

* - пересечение множеств

+ - объединение множеств

- - вычитание множеств

IN v проверка на вхождение

Представление массивов, записей и множеств

Представление структуры массива заключается в отображении массива с элементами типа Т на память, которая представляет собой массив с элементами типа WORD.

Проблема представления данных заключается в отображении абстрактных структур на память машины. Эта память - массив отдельных ячеек, названных словами, индексы же этих слов называются адресами.

Массив следует отображать так, чтобы вычисление этих адресов было как можно простым.

Адрес I для J-ой компоненты массива вычисляется следующим образом:

I = I0 + J*S

I0 v адрес первого элемента,

S - число слов, занимаемых одним элементом.

Как правило, удобнее всего работать, если S = 1.

Если S не целое число, то его округляют до ближайшего целого в большую сторону.

Округление необходимого числа слов до следующего целого числа называется выравниванием (padding).

Коэффициентом использования памяти называется частное от деления минимального размера памяти, необходимого для представления некоторых данных на размер фактически занятой памяти:

U = S/[S], где [S]- фактически занятая память.

Упакованный формат:

 
 
   

S = 2.5
[S] = 3
U = 2.5/3 = 0.84

Обычный формат:

   
   
   

S = 1.5
[S] = 3
U = 1.5/3 = 0.5

Таким образом, нужно учитывать следующие соображения:

Выравнивание уменьшает используемую память

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

Коэффициент использования памяти можно увеличить, если в каждое слово укладывать более 1 элемента массива. Такой метод называется упаковкой (packing).

Записи в машине отображаются объединением отображений их полей. Адрес поля RI относительно начального адреса записи R называется смещением.

RI = S1 + S2 + - + S¦-1, где SJ - размер в словах j-ой компоненты

Если все элементы одного типа, то

Ri = (I-1)*S

<                         слово                       >

S1
S2 остаток
S3
S3 остаток
S4
S5 S6 S7 остаток

Слова имеют адреса; S1, S2,-, S7 v идентификаторы полей.

Ещё один тип данных v последовательность.

TYPE T = SEQUENCE OF T0

Все элементы последовательности имеют один и тот же тип.

Количество элементов последовательности называется её длиной, причем у массива число элементов фиксируется его описанием, а у последовательности остается открытым.

Последовательность рассматривается от одного элемента к другому строго последовательно. А формируется последовательным добавлением элементов в её конец.

Мощность такого типа данных бесконечна.

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

При работе с последовательностями используют следующие операции:

OPEN (S) v определяет S как пустую последовательность (последовательность длины 0).
WRITE (S, X) - добавляет элемент X в последовательность S
RESET(S) v устанавливает текущую позицию в начало последовательности S.
READ(S, X)- присваивает элемент X из текущей позиции и переводит указатель на следующий элемент.

Назад | Содержание | Вперед