Вопрос 2-5. Структуры данных. Базы данных и основные типы их организации

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

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

При обработке информации часто приходится встречаться с представлением данных в виде списков и операциями над ними. Рассмотрим операции над списками и способы представления (реализации) списков.

Можно выделить следующие операции над списками;

—получить доступ к заданному элементу списка;

—включить новый элемент в список;

—исключить элемент из списка;

—объединить несколько списков в один;

—разбить список на несколько списков;

—определить число элементов списка;

—выполнить сортировку списка;

—сделать копию списка.

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

Стек — список, в котором все включения и исключения делаются в одном конце списка.

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

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

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

В качестве простейшей нелинейной структуры данных рассмотрим бинарное дерево. Бинарное дерево как структура данных по­лучается из бинарного дерева с корнем как графа приписыванием его вершинам значений элементов структуры данных. Связи между элементами бинарного дерева можно задать в виде рассмотренных ранее матриц смежности и инцидентности (двумерных массивов). Однако более наглядным является следующая реализация бинарного дерева: вершине дерева ставим в соответствие запись, состоящую из приписанного этой вершине значения и адресов «левого» и «правого» потомков.

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

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

В сетевой базе данных нет ограничений на возможные связи между данными.

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