Информатика экзамен 1 курс
1.1 Основные понятия структур данных
Компьютер оперирует только с одним видом данных — с отдельными битами, или двоичными цифрами, и работает с этими данными только в соответствии с неизменным набором алгоритмов, которые определяются системой команд центрального процессора . Задачи, которые решаются с помощью компьютера, редко выражаются на языке битов. Как правило, данные имеют форму чисел, литер, текстов, символов и более сложных структур типа последовательностей, списков и деревьев.
Структура данных, рассматриваемая без учета ее представления в машинной памяти, называется абстрактной, или логической. Понятие «физическая структура данных» отражает способ физического представления данных в машинной памяти . Вследствие различия между логической и соответствующей ей физической структурами в вычислительной системе существуют процедуры, осуществляющие отображение логической структуры в физическую, и наоборот.
Например, доступ к элементу двумерного массива на логическом уровне реализуется указанием номеров строки и столбца в прямоугольной таблице, на пересечении которых расположен соответствующий элемент. На физическом же уровне к элементу массива доступ осуществляется с помощью функции адресации, которая при известном начальном адресе массива в машинной памяти преобразует номера строки и столбца в адрес соответствующего элемента массива. Таким образом, каждую структуру данных можно характеризовать ее логическим (абстрактным) и физическим (конкретным) представлениями, а также совокупностью операций на этих двух уровнях представления структуры (рисунок 1).
Очень часто, говоря о той или иной структуре данных, имеют в виду ее логическое представление, так как физическое представление обычно скрыто от программиста. Так как физическая структура данных реализуется вмашинной памяти, имеющей ограниченный объем, то при изучении такойструктуры должна учитываться проблема распределения и управления
памятью.
Под структурой данных в общем случае понимают множество элементов данных и множество связей между ними. Такое определение охватывает все возможные подходы к структуризации данных, но в каждой конкретной задаче используются те или иные его аспекты. Поэтому вводится дополнительная классификация структур данных, направления которой соответствуют различным аспектам их рассмотрения.
Понятие «физическая структура данных» отражает способ физического представления данных в памяти компьютера и называется еще структурой хранения, внутренней структурой или структурой памяти . Рассмотрение структуры данных без учета ее представления в памяти компьютера называется абстрактной, или логической, структурой. В общем случае между логической и соответствующей ей физической структурами существует различие, степень которого зависит от самой структуры и особенностей той среды, в которой она должна быть отражена. Вследствие этого различия существуют процедуры, осуществляющие отображение логической структуры в физическую и, наоборот, физической структуры в логическую. Эти процедуры обеспечивают, кроме того, доступ к физическим структурам и выполнение над ними различных операций, причем каждая операция рассматривается применительно к логической или физической структуре данных.
Различают простые структуры данных и интегрированные. Простыми называются такие структуры данных, которые не могут быть расчленены на составные части, большие, чем биты. Для физической структуры важным является то обстоятельство, что в данной машинной архитектуре и в данной системе программирования всегда можно заранее знать, каков будет размер выбранного простого типа и какова структура его размещения в памяти. С логической точки зрения простые данные являются неделимыми единицами.
Интегрированными называются такие структуры данных, составными частями которых являются другие структуры данных — простые или, в свою очередь, интегрированные. Интегрированные структуры данных конструируются программистом с использованием средств интеграции данных, предоставляемых языками программирования. В зависимости от отсутствия или наличия явно заданных связей между элементами данных следует различать несвязные структуры (векторы, массивы, строки, стеки, очереди) и связные структуры (связные списки).
Важный признак структуры данных — ее изменчивость, т.е. изменение числа элементов и (или) связей между элементами структуры. В определении изменчивости структуры не отражен факт изменения значений элементов данных, поскольку в этом случае все структуры данных имели бы свойство изменчивости.
По признаку изменчивости различают структуры базовые, статические, полу статические, динамические и файловые . Классификация структур данных (СД) по признаку изменчивости приведена в приложении1. Базовые структуры данных, статические, полустатические и динамические характерны для оперативной памяти и часто называются оперативными структурами. Файловые структуры соответствуют структурам данных для внешней памяти.
Вектор (одномерный массив) — структура данных с фиксированным числом элементов одного и того же типа.
Множество — такая структура, которая представляет собой набор неповторяющихся данных одного и того же типа.
Списком называется упорядоченное множество, состоящее из переменного числа элементов, к которым применимы операции включения, исключения. Список, отражающий отношения соседства между элементами, называется линейным .
По этому признаку структуры можно делить на линейно-упорядоченные, или линейные, и нелинейные структуры (рисунок 2) .
В зависимости от характера взаимного расположения элементов в памяти компьютера линейные структуры можно разделить на структуры с последовательным распределением их элементов в памяти (векторы, строки, массивы, стеки, очереди) и структуры с произвольным связанным распределением элементов в памяти (односвязные, двухсвязные и прочие списки).
Линейные СД — это структуры, в которых связи между элементами не зависят от выполнения какого-либо условия. Линейные структуры подразделяются натри типа: картезианские, строчные и списковые.
Картезианские, или прямоугольные, структуры названы так по способу записи данных в виде прямоугольных таблиц.
Строчные структуры — одномерные, динамически изменяемые структуры данных, различающиеся способами включения и исключения элементов (рисунок 3).
Стек — это последовательность, в которой включение и исключение элемента осуществляется с одной стороны последовательности.
Известные примеры стека – винтовочные патронный магазин, железнодорожный разъезд для сортировки вагонов.
Очередь — последовательность, в которую включают элементы с одной стороны, а исключают — с другой (рисунок 4). Структура функционирует по принципу FIFO (первым пришел — первым обслуживается).
Дек — линейная структура (последовательность), в которой операции включения и исключения элементов могут выполняться как с одного, так и с другого конца последовательности (рисунок 5).
В списковых структурах логический порядок данных определяется указателями. Любая списковая структура представляет собой набор элементов, каждый из которых состоит из двух полей: в одном из них размещен элемент данных или указатель на него, а в другом — указатель на следующий элемент списка.
Нелинейные структуры данных — это СД, у которых связи между элементами зависят от выполнения определенного условия. Примеры нелинейных структур — деревья, графы, многосвязные списки.
Древовидные структуры — это иерархические структуры, состоящие из набора «вершин и ребер, каждая вершина содержит определенную информацию и ссылку на вершину нижнего уровня. Дерево — это совокупность элементов, называемых узлами (один из которых определен как корень), и отношений, образующих иерархическую структуру узлов (рисунок 6) .
Вершина, располагающаяся в нулевом уровне, называется корнем дерева (нумерация уровней может начинаться с 1). В корень не входит ни одного ребра. Вершины, из которых не выходит ни одного ребра, называются листьями (вершины 8, 9, 5, 6, 7). Дерево, из каждой вершины которого выходит только по два ребра, называется бинарным (рисунок 7).
Графы представляют собой совокупность двух множеств: вершин и ребер. Граф — это сложная нелинейная многосвязная динамическая структура, отображающая свойства и связи сложного объекта (рисунок 8) .
Типичными графами являются схемы авиалиний и схемы метро, а на географических картах — изображение железных или автомобильных дорог. Выбранные точки графа называются его вершинами, а соединяющие их линии — ребрами.
Сплетение (многосвязный список, плекс) — это нелинейная структура данных, объединяющая такие понятия, как дерево, граф и списковая структура.
Основное свойство сплетений, отличное от других типов структур, — наличие у каждого элемента сплетения нескольких полей с указателями на другие элементы того же сплетения (рисунок 9) .
Рисунок 9 – Многосвязный список (сплетение)
Сплетение — связь элементов, основанная на сплетении указателей. Каждый элемент сплетения может содержать информацию о количестве полей с указателями и формате поля данных. Плексы (сплетения) используются для представления различных семейств связей между индивидуумами и владельцами, отражают производственные, отраслевые связи и т.п.
Описание типа данных может содержать ссылку на саму себя. Подобные структуры используются при описании списков и графов . Пример описания списка ( C++ ):
element_of_list *next; /* ссылка на следующий элемент того же типа */
int data; /* некие данные */
Источник