Классификация структур данных

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

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

линейные;

иерархические;

многосвязные.

Иерархические и многосвязные структуры иначе называют нелинейными.

Если элементы структуры связаны линейными отношениями соседства, то такая структура является линейной (рис.1.3,а). Линейная структура обычно называется линейным списком или просто списком (связным списком, цепным списком).

Подробные сведения о линейных структурах данных содержатся в главе 2.

Рис.1.3. а). Линейная структура; б). Иерархическая структура; в) Многосвязная структура

Если элемент связной структуры содержит несколько следующих за ним элементов, но только один предыдущий элемент, то такое отношение является отношением иерархии, а структура называется иерархической (рис. 1.3, б). В этом случае вводятся понятия родительского и дочерних элементов (узлов). Иерархические структуры данных рассматриваются подробно в главе 3.

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

Важным критерием классификации является способ доступа к данным:

прямой доступ по индексу;

последовательный доступ по ссылкам;

смешанные способы доступа.

На уровне рализации важную роль играет способ формирования структуры данных:

статический

динамический;

смешанный.

Например, массив — линейная структура с прямым доступом к данным, статически или динамически формируемая, линейный список на основе указателей — динамически формируемая линейная связная структура с последовательным доступом.

Перейдем теперь к обработке данных. Наиболее фундаментальным понятием в этой области является алгоритм.

1.4. Понятие алгоритма

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

Алгоритм — конечная последовательность инструкций, каждая из которых имеет чёткий смысл и может быть выполнена с конечными затратами ресурсов за конечное время. Составление алгоритма для решения задачи называется ее алгоритмизацией.

Имеется несколько синонимов для слова «алгоритм» — способ, метод, рецепт. Эти понятия очень близки по смыслу, но все-таки не идентичны понятию алгоритма. Уточним приведенное выше неформальное определение перечнем требованийк алгоритму(часть требований вытекает из определения):

q однозначность (определенность)— каждая инструкция алгоритма должна быть понятна исполнителю алгоритма и иметь однозначное толкование. Здесь очень важно отметить, что любой алгоритм предназначен для конкретного исполнителя, поэтому должен содержать только инструкции; которые этим исполнителем могут быть выполнены.

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

q   детерминированность — для одних и тех же входных данных алгоритм должен каждый раз выдавать один и тот же результат. (Замечание: если в алгоритме используются датчики случайных чисел, то, казалось бы, результаты будут получаться разные. Но на самом деле, эти числа можно тоже рассматривать как входные параметры);

q корректность (правильность) — алгоритм должен давать правильное решение задачи при различных входных данных;

q массовость (универсальность) — алгоритм обычно предназначен для решения не одной задачи, а множества задач, относящихся к некоторому классу (например, алгоритмы сортировки и поиска).