Структуры данных и их хранение. (Тема 9)

1. Уровни представления данных
Уровень реальных объектов
Логический уровень
Физический уровень

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

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

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

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

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

Массив - линейная структура данных фиксированного размера.
Каждый элемент массива идентифицируется одним или несколькими индексами.
Индекс - целое число, определяющее позицию элемента в массиве, используется для осуществления доступа к этому элементу.
Для массивов нет операций добавления и удаления элементов.
S(12) – одномерный массив S из 12 элементов.
S(5)=3 – элементу массива с индексом 5 присвоить значение 3.
D(11,18) - двумерный массив (матрица) -11 строк, 18 столбцов.

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

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

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

К нелинейным структурам относятся:
деревья,
графы,
списки

3. Хранение данных на внешних носителях
Для размещения данных на внешних носителях используют следующие типы файловых структур данных:
последовательные файлы;
прямые файлы;
индексно-последовательные файлы;
библиотечные файлы.
Для всех типов файлов возможны следующие режимы доступа:
последовательный;
произвольный.

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

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