С точки зрения компьютерной обработки различают структурированные и неструктурированные сообщения (исходные данные).
Неструктурированные вводятся, хранятся и передаются на естественном языке, а структурированные – на искусственном.
Понятие “структура” используется в том случае, если возникла необходимость представить множество каких-либо элементов и отношений (связей) между ними.
Поэтому обработка данных с помощью компьютера требует определения их структуры, то есть порядка размещения однотипных связанных данных в его памяти.
Структура данных зависит от цели их обработки и специфики отражаемых реальных объектов или событий. В дальнейшем под структурой данных будет пониматься совокупность элементов данных, между которыми указаны связи (отношения). Связи между элементами устанавливают порядок доступа к ним в процессе обработки. Элементы данных размещаются в ячейках памяти, имеющих адреса.
Так как структура данных указывает на способ их организации в памяти компьютера, поэтому, как правило, под структурой данных подразумевают структуру хранения данных. Известны следующие типовые структуры данных: линейные (одномерный массив, двумерный массив), и нелинейные (списочные структуры, древовидные и сетевые).
Линейные одномерные массивы
Данная структура предполагает размещение элементов данных в непрерывной последовательности ячеек памяти компьютера
Наиболее важными из однородных (линейных) структур данных являются очередь и стек. Очередь содержит элементы, выстроенные друг за другом в цепочку, у которой есть начало и конец. Добавлять новые элементы можно только в конец очереди, забирать элементы можно только из начала.
Двумерные массивы
На рис. 6.10б указан способ хранения данных в виде двумерного массива. Он применяется в том случае, если длина строки или столбца известны. Как правило, при обработке двумерных массивов известны и номера строк и номера столбцов (матрицы). Тогда для поиска нужного элемента достаточно указать номер строки и номер столбца.
Нелинейные структуры
Списочные структуры
Довольно часто данные в компьютере располагаются не в последовательных ячейках, а в произвольных частях памяти. Для того, что бы задать связь между различными элементами данных применяют указатели. Списочная линейная структура представлена на рис. 6.10а. В ней первая ячейка содержит адрес первого элемента данных, вторая элемент данных и адрес следующего элемента данных и т.д. Последняя ячейка содержит элемент данных и указатель конца списка.
Двухсвязный линейный список представлен на рис. 6.10б. Каждый элемент списка, кроме первого и последнего, содержит три поля, первое и третье из которых имеют указатели на предыдущий и последующий элементы.
Цикличный линейный список, представленный на рис. 6.10в, позволяет организовать переход с последнего элемента списка на первый. Образуется кольцо, выход из которого возможен после получения некоторого сигнала.
Древовидная структура используется в случае необходимости отражения отношений соподчиненности между объектами или процессами. Деревом называется множество элементов, называемых узлами, таких, что:
- между узлами имеет место отношение типа «исходный - порожденный».
- Есть только один узел, не имеющий исходного – корень.
- Все узлы, за исключением корня, имеют только один исходный.
- Ни один порожденный узел не может стать исходным.
На рис. 6.11 представлено две формы моделирования иерархических отношений: иерархическое дерево, отражающее отношение соподчиненности (а) и структура данных, позволяющая отразить эти отношения в памяти компьютера (б).
Узел иерархической структуры данных в данном случае содержит три поля: одно для размещения собственно данных и два для указателей (на подчиненный и на соседний узел).
В информатике существует ряд разновидностей деревьев.
С понятием «структура данных» тесно связано понятие «модель данных», что можно представить следующим образом:
Модель данных - это структура данных с заданными над ними операциями для обработки. Содержательно структура данных является составной частью модели данных.
Различают следующие базовые модели данных: реляционные (двумерные массивы), иерархические и сетевые. Кроме перечисленных известно множество моделей, отражающих цели их создателей (сущность-связь, бинарные модели, семантические сети и т.д.).
Реляционная модель основывается на понятии “отношение”, и представляется совокупностью таблиц. На рис. 6.15 приведены базовые понятия данной модели.
Домен – это множество значений, принимаемых свойствами (характеристиками) отражаемого объекта.
Атрибут – это имя множества значений, входящих в домен. Атрибуты используются в качества средства для обращения к доменам.
Кортеж – это множество элементов из доменов, составляющих одну строку отношения (таблицы).
Отношение – это множество кортежей, отражающих свойства объекта.
Таблицы, входящие в реляционную модель, строятся в рамках ограничений, диктуемых операциями их обработки. Это следующие ограничения:
- таблица должна иметь имя (например, ДЕТАЛЬ, ПОСТАВЩИК, ПОСТАВКИ);
- таблица должна быть простой, то есть не содержать составных столбцов, например, у поставщика должен быть только один номер телефона;
- в таблице не должно быть одинаковых строк;
- должен быть известен первичный ключ, используемый для поиска или выполнения других логических операций.
В компьютере таблицы реляционной модели обрабатываются с помощью операций реляционной алгебры.
