5.2. Модели структуры данных.

Данные – представленная в формализованном виде конкретная информация об объектах предметной области, их свойствах и взаимосвязях, отражающая события и ситуации в этой области.

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

Структуры данных делятся на линейные и нелинейные структуры.

К линейным структурам данных относят: константы, переменные, массивы (одномерные и двумерные), стеки, очереди.

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

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

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

Массивом называется множество упорядоченных однотипных данных, объединенных одним именем. Массив может состоять из символов, целых чисел и т.д. На рис. 2.9. представлены вид одномерного массива.

1	Антонов
2	Бурмистров
3	Гуров
4	Климов
5	Кондаков
6	Кусков
7	Ледников
8	Махов

Рис. 2.9. Одномерный массив

При решении же ряда задач удобно оперировать двумерными массивами данных. Каждому элементу двумерного массива присваивается два индекса. Если двумерный массив представить в виде таблицы, то первый индекс рассматриваемого элемента укажет на строку и второй на стобец этой таблицы, на пересечении которых находится данный элемент. Ниже приведен рисунок, на котором представлен двумерный массив ST(2, 4) указывает на оценку второго студента по четвертому предмету.

ST (1.1)	ST (1.2)	ST (1.3)	ST (1.4)
ST (2.1)	ST (2.2)	ST (2.3)	ST (2.4)
ST (3.1)	ST (3.2)	ST (3.3)	ST (3.4)

Далее приводится рисунок примера двумерного символьного массива TEXT(4, 3):

	1	2	3
1	ю	а	ж
2	в	ж	К
3	л	ч	С
4	д	п	Л

Рис. 2.10. Двумерный массив

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

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

Некоторую совокупность информации, описывающую конкретный объект называют записью. Элементом записи является поле записи, которое описывает соответствующий признак объекта. Структуризация записи составляет одну из основных концепций баз данных.

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

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

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

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

Рис. 2.11 Структура данных типа «Очередь»

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

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

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

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

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

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

Исключение элемента исходный стек включение элемента

Рис. 2.12. Структура данных типа «Стек»

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

З апись: " Сегодня идет дождь"

Адрес1: "Да" Адрес2: "Нет"

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

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

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

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

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

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

Иерархическая модель данных организует данные в виде древовидной структуры и является реализацией логических связей: родо-видовых отношений или отношений "целое – часть".

Примером простого иерархического представления может служить административная структура нашего института: институт – филиал – группа – студент. (рис.2.13).

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

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

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

Рис. 2.13. Иерархическая модель данных

Сетевая модель данных. В основу сетевой модели данных (рис. 2.14.) положены сетевые структуры.

Рис.2. 14. Сетевая модель данных

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

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

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

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

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

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

• имя (например, Номер, Фамилия, дата, сумма);

• тип (например, текстовый, числовой, дата);

• длина (определяется максимальной длиной реквизита, например, 20 байт);

• точность для числовых данных (например, два числовых знака после запятой).

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

Таблица – совокупность одинаковых по структуре записей. Каждый экземпляр записи характеризуется уникальным ключом записи.

Содержимое таблицы СОТРУДНИКИ базы данных

Номер	Фамилия	Имя	Отчество	Дата	Оклад
135468	Иванов	Иван	Петрович	12.10.82	1900.00
246579	Петров	Петр	Михайлович	24.05.63	2500.00
357647	Сидоров	Семен	Алексеевич	10.01.81	2300.00