Логический уровень представления информации

 

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

Они получили название – структуры данных.

Структура данных – это способ объединения рада элементов данных в единый элемент: массив, файл, список.

 

Простые структуры данных:

1) Целые числа - числа со знаком, участвующие в обычных арифметических операциях

(integer) с заданной точностью.

2) Вещественные числа - наличие дробных чисел и ограниченная точность (результат

(real) округляется).

3) Символьные числа - это любой набор символов, определенных в двоичном стандарте

(Character) ASCII.

4) Булевы выражения - это двоичные коды, участвующие в логических операциях

(Boolean) дизъюнкций, конъюнкций, отрицания и их сочетаний.

 

Сложные структуры данных:

1) Массивы - это регулярная структура данных одного типа, где все компоненты могут

(array) выбираться произвольно и одинаково доступно.

 

Для свободного доступа к любому элементу массива вводится специальное число – индекс.

А [i]; B [i,j]; stol [s];

индекс

По размерности массивы могут быть: одномерные, двухмерные, трехмерные.

Для вещественных чисел – это соответственно будут: векторы, матрицы, тензоры.

В системах обработки данных к одномерным массивам относятся очереди и стеки.

 

Очередь – это одномерный массив переменной длины с определённой процедурой (queue) включения и исключения данных.

Для очереди характерна реализация принципа FIFO (first-in, first-out) – (первым вошел – первым вышел). (это напоминает обычную очередь) 1 2

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

 

Структура типа:

Стек – одномерный массив переменной длины, когда включение и исключение элементов (Stack) осуществляется только на одном конце массива, называемым вершиной стека.

Он функционирует по принципу LIFO (last-in, first-out) – (последним вошел – первым вышел). (Напоминает стопку тетрадей, когда тетрадь, положенная последней, будет лежать на вершине стопки).

 

2) Записи - это совокупность элементов, поименованных данных разного типа.

(Record) В простейшем случае – постоянное число элементов.

 

3) Последовательность – совокупность значений. В частном случае, когда последова- (Chain) тельность составляют записи одинаковой структуры, она называется файлом (file).

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

 

4) Множества – это неупорядоченная совокупность различных объектов (данных).

(1,8,10,12) – простое множество.

Операции: объединение, пересечение, вычетание и ряд других.

 

Сложные динамические структуры данных:

(Структура данных меняется в процессе функционирования). К динамическим структурам данных относят разновидности массивов (кольца и списки) и множеств (графы и деревья).

 

1) Кольца - представляет собой одномерный массив с замкнутыми концами, когда пос-

(Ring Structure) ледний элемент замкнут с первым, образуя кольцо.

 

….

 

Если неопределенной длины – то можно в любом месте включать или исключать элементы данных.

 

2) Списки - это одномерный массив произвольных упорядоченных элементов данных с

(List) возможностью их свободного изменения.

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

Пример: 1. (a, b, c)

2. (a, (m, 2.35), (b, k)) – списочная структура.

Основными операциями над списочными структурами являются следующие:

· исключение части списка;

· объединение (конкатенация) двух списков;

· Включение элемента в список.

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

 

3) Деревья - это конечное множество, состоящее из одного и более элементов, называемых

(Tree) узлами, таких что:

1. Имеется только один специальный узел, называемый корнем дерева T-root (t).

2. Остальные узлы (исключая корень) содержатся в m (m>0) попарно не пересекающих множествах Т₁, Т₂,..., Т_m, каждые из которых в свою очередь являются деревом.

Деревья Т₁, Т₂,..., Т_m называются поддеревьями данного корня.

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

Отношение «исходный - порожденный» действует только в одном направлении: от корня дерева к поддеревьям.

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

Отдельного узла определяет параметр, называемый

степеньюдерева.

В нашем примере степень равна 3, т.к. максималь-

ное число поддеревьев, принадлежащее

вершине В, равно трем.

 

В практике часто используют деревья, все узлы которых имеют степени не более двух. Такие деревья называются бинарнымидеревьями.