Структуры данных

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

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

Простейший агрегативный тип – массивы, которые есть упорядоченный набор данных одного типа.

Структуры (в Паскале – записи) – поименованная совокупность данных различных типов.

Во многих языках есть только эти два типа агрегативных данных.

Полезно рассмотреть и другие возможные агрегативные структуры (могут быть организованы с помощью массивов).

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

Очереди – упорядоченный список, в один конец которого элементы добавляются, а из другого изымаются. Иначе – это список FIFO (First In, First Out) – поступивший первым обслуживается первым. Операции – добавить и удалить.

Стеки – упорядоченный список, в один конец которого элементы добавляются, и из него же изымаются. Список LIFO (Last In, First Out). Операции – поместить, извлечь, функция «пусто» = истина, если стек не заполнен.

Множество – совокупность переменных одного типа. Аналогичен списку, за исключением того, что порядок расположения переменных не имеет значения. Операции – добавить, удалить, функция «входит в» = истина, если данная переменная находится в множестве.

Граф – структура, состоящая из узлов и дуг, причем каждая дуга направлена от одного узла к другому.

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

Важное место при работе с агрегативными переменными занимают такие действия как поиск и сортировка данных. Рассмотрим основные методы таких действий.

Поиск

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

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

1. Линейный поиск.

Наиболее простой в реализации, хотя его выполнение занимает наибольшее время. Элементы проверяются последовательно, по одному, до тех пор, пока нужный элемент не будет найден. Если массив содержит N элементов, то каждый раз, в среднем, будет проверяться N/2 элементов. Легко программируется, подходит для коротких массивов.

2. Двоичный поиск.

Для ведения двоичного поиска ключи должны быть упорядочены по величине или алфавиту. Если такое упорядочивание произведено заранее, то среднее максимальное время поиска в массиве с N элементами будет log₂N.

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