Как отмечалось в теме 1, структурой данных называется логически упорядоченный, организованный набор данных. Структуры данных делятся на линейные и нелинейные.
Наиболее общим линейным типом данных является список. Списком называют конечную упорядоченную последовательность элементов.
При обработке информации часто приходится встречаться с представлением данных в виде списков и операциями над ними. Рассмотрим операции над списками и способы представления (реализации) списков.
Можно выделить следующие операции над списками;
—получить доступ к заданному элементу списка;
—включить новый элемент в список;
—исключить элемент из списка;
—объединить несколько списков в один;
—разбить список на несколько списков;
—определить число элементов списка;
—выполнить сортировку списка;
—сделать копию списка.
В приложениях редко требуется выполнение всех перечисленных выше операций. Существует много способов реализации списков в зависимости от класса операций, которые необходимо выполнять наиболее часто. Очень часто встречаются списки, в которых включение, исключение или доступ к значению почти всегда производятся в первом или последнем элементе. Списки такого вида имеют специальные названия.
Стек — список, в котором все включения и исключения делаются в одном конце списка.
Очередь — список, в котором все включения делаются на одном конце, а все исключения — на другом.
Простейшей реализацией списка является расположение его элементов в последовательных ячейках памяти, то есть в виде массива. При этом выделение памяти под список осуществляется до начала выполнения программы, то есть статически. Однако в этом случае операции включения и исключения элементов оказываются дорогостоящими, так как приходится передвигать элементы списка в памяти компьютера. Но операции доступа к заданному элементу списка и получения копии списка можно осуществить легко.
Другая реализация списка заключается в сопоставлении каждому элементу списка пары (или тройки), одной частью которой является элемент списка, а другой — адрес (указатель) следующей пары (указатель на предыдущую и следующие тройки). Если элементу списка ставится в соответствие пара (тройка), то реализация называется связным (двусвязным) списком. Отметим, что включение нового элемента в список и исключение элемента из списка в этом случае существенно проще, чем в случае реализации списка в виде массива.
В качестве простейшей нелинейной структуры данных рассмотрим бинарное дерево. Бинарное дерево как структура данных получается из бинарного дерева с корнем как графа приписыванием его вершинам значений элементов структуры данных. Связи между элементами бинарного дерева можно задать в виде рассмотренных ранее матриц смежности и инцидентности (двумерных массивов). Однако более наглядным является следующая реализация бинарного дерева: вершине дерева ставим в соответствие запись, состоящую из приписанного этой вершине значения и адресов «левого» и «правого» потомков.
Наиболее распространенным способом хранения и обработки информации больших объемов являются базы данных. Тип организации базы данных определяется возможными связями между ее элементами (данными). Основными типами организации баз данных являются иерархический, сетевой и реляционный.
Иерархической базе данных можно сопоставить дерево с корнем, в котором вершинам соответствуют элементы базы данных, а ребрам — возможные связи между данными.
В сетевой базе данных нет ограничений на возможные связи между данными.
Наиболее распространенными являются реляционные (табличные) базы данных. Простейшей реляционной базой данных является таблица. Элементом таблицы является поле. Поля объединяются в записи (строки). Таблица состоит из однотипных записей; элементы столбца таблицы имеют одинаковый тип данных. Каждый столбец таблицы имеет название (атрибут). Элемент таблицы определяется записью и атрибутом. Реляционная база данных является совокупностью таблиц, вообще говоря, различного формата.