Как следует из приведенного выше определения, структурирование данных предполагает существование (или установление) между ними каких-то отношений (связей). В зависимости от характера этих отношений можно выделить несколько классификационных признаков структур данных.
Первым из них рассмотрим отношение порядка. По порядку данных структуры делятся на упорядоченные и неупорядоченные.
В упорядоченных структурах элементы размещаются по порядку в соответствии со значением некоторого признака. Наиболее простым признаком является порядковый номер элемента:, установление порядка в соответствии с номером называется нумерацией. При этом если весь набор имеет один общий идентификатор (например, М), то отдельным данным присваиваются собственные идентификаторы - индексы (например, М5 или Мb). Чаще всего индекс задается целым числом, хотя это необязательно -в качестве индекса может выступать любой знак из конечного алфавита. Лексикографический порядок индексов определяет отношение следования между элементами структуры, т.е. элемент М6 следует за элементом М5, а элемент Ма располагается перед элементом Мb. Примером структур, в которых упорядочение производится по номеру элемента, являются массивы. Порядковый номер элемента можно считать внешним признаком, который может присваиваться элементу независимо от его значения. Например, регистрационный номер документа определяется только временем его поступления в учреждение, а не его содержанием. Помимо нумерации в структурах данных используется упорядочение по значению некоторого внутреннего признака, например, размещение фамилий в алфавитном порядке или группы предприятий в порядке убывания их рентабельности -такое упорядочение называется ранжированием.
Примером неупорядоченных структур являются, множества - в них не определен порядок элементов; единственное, что можно установить для каких-то конкретных данных, так это их принадлежность (или не принадлежность) выбранному множеству.
Следующим классификационным признаком структур является однородность. К однородным относятся структуры, содержащие элементарные данные только одного типа. Неоднородные структуры объединяют данные разных типов. Примерами однородных структур являются массивы, множества, стеки. К неоднородным структурам относятся записи.
Еще одним признаком является характер отношений между элементами. По взаимной подчиненности элементов структуры данных подразделяются на линейные и нелинейные.
В линейных структурах все элементы равноправны. К ним относятся массив, множество, стек, очередь.
В нелинейных структурах между элементами существуют отношения подчиненности или они могут быть связаны логическими условиями. К ним относятся деревья, графы, фреймы.
Основываясь на выделенных классификационных признаках, рассмотрим и охарактеризуем некоторые структуры данных.
Массив
Массив - упорядоченная линейная совокупность однородных данных.
Комментарии к определению:
· термин «упорядоченная» означает, что элементы массива пронумерованы;
· термин «линейная» свидетельствует о равноправии всех элементов;
· термин «однородных» означает следующее: в том случае, когда массив формируется из элементарных данных, это могут быть данные лишь одного какого-то типа, например, массив чисел или массив символов; однако, возможна ситуация, когда элементами массива окажутся сложные (структурные) данные, например, массив массивов - в этом случае «однородных» означает, что все элементы имеют одинаковую структуру и размер.
Количество индексов, определяющих положение элемента в массиве, называется мерностьюмассива.
Так, если индекс единственный, массив называется одномерным; часто такой массив называют также вектором, строкой или столбцом. Для записи элементов одномерного массива используется обозначение mi; в языках программирования приняты обозначения m(i) или m[i].
Массив, элементы которого имеют два индекса, называется двумерным или матрицей. Пример обозначения: G [3,5]; при этом первый индекс является номером строки, а второй индекс - номером столбца, на пересечении которых находится данный элемент.
Массивы с тремя индексами называются трехмерными и т.д. Максимальная мерность массива может быть ограничена синтаксисом некоторых языков программирования, либо не иметь таких ограничений.
Максимальное значение индексов определяет размер массива. Размер массива указывается в блоке описания программы, поскольку при исполнении программы для хранения элементов массива резервируется необходимый объем памяти. Если в процессе исполнения программы размер массива не изменяется (или не может быть изменен), то в этом случае говорят о массивах фиксированного размера; если определение размеров массива или их изменение происходит по ходу работы программы, то такие массивы называются динамическими (динамически описываемыми).
Допустимый набор операций над элементами массива определяется типом данных (элементарных или структурированных), из которых массив сформирован. В некоторых языках программирования над массивом в целом определена операция присваивания М := <выражение> - в этом случае всем элементам массива присваивается одинаковое значение, равное вычисленному значению выражения; возможна также операция присваивания для двух одинаковых по типу, размеру и размерности массивов М2:= М1 - производится поэлементное присваивание значений (M2(i,j,k...) := M1(i,j,k...)).
Особое место занимают символьные массивы - они называются строками или строковыми данными (например, тип String в PASCAL'e). С ними возможен целый набор операций, неопределенных для одиночных символьных данных. В первую очередь, это операция конкатенации (объединения) строк с сформированием новой строки. Помимо этого имеются операции замещения части строки, а также определения ее числовых характеристик.
Стек, очередь
Стек (магазин) и очередь являются упорядоченными, линейными, неоднородными структурами. Эти структуры реализуются в виде специальным образом организованных областей ОЗУ компьютера либо в качестве самостоятельных блоков памяти. В стеке ячейки памяти (или регистры стековой памяти) соединяются друг с другом таким образом, что при занесении данных в первую ячейку содержимое всех остальных сдвигается в соседние вниз, при считывании - содержимое сдвигается вверх по ячейкам, как показано на рис. 6.2. Другими словами, вход в стек возможен только через первую ячейку (вершину стека), поэтому извлекаться первой будет та информация, которая была занесена последней*, подобно пассажиру переполненного автобуса.
* Часто стек называют памятью типа LIFO (Last-In First-Out: «последним вошел - первым вышел»).
Отличие очереди от стека только в том, что извлечение информации производится в порядке «первым вошел - первым вышел», т.е. со дна стека.
Таким образом, данные имеют порядок расположения и они равноправны - поэтому структура является упорядоченной и линейной. Однако в общем случае в ячейках стека могут содержаться данные разных типов - по этому признаку структура оказывается неоднородной.
Описанный способ организации данных оказывается удобным при работе с подпрограммами, обслуживании прерываний, решении многих задач.
Дерево
Дерево или иерархия является примером нелинейной структуры. В ней элемент каждого уровня (за исключением самого верхнего) входит в один и только один элемент следующего (более высокого) уровня. Элемент самого высокого уровня называется корнем, а самого нижнего уровня - листьями.
Схема такой структуры показана на рисунке. Отдельные элементы могут быть однородными или нет. Примером подобной организации служат файловые структуры на внешних запоминающих устройствах компьютера.
Граф
Часто отношения между данными представляются в виде графа -совокупности точек и линий, в которой каждая линия соединяет две точки. В информатике точка получает смысл элемента структуры (системы, данных и пр.), а линии - смысл отношения между элементами. Познакомимся с рядом терминов, связанных с использованием графов.
Точки называются вершинами графа, линии - ребрами. Если ребро соединяет две вершины, то говорят, что ребро инцидентно этим вершинам, а сами вершины называются смежными. Число ребер, инцидентных вершине, называется степенью вершины. Если два ребра инцидентны одной и той же паре вершин, они называются кратными. Ребро, у которого совпадают обе вершины, называется петлей.
На рис. 6.3,а. граф 1 задается списком вершин {1,2,3,4} и списком ребер, в котором для каждого ребра указывается пара инцидентных ему вершин: а(1,2); b(1,4); с(2,.4); 6(2,3); е(3,4); f(2,3); g(4,4).
Смежные пары вершин: (2,3), (2,4), (1,2), (1,4), (3,4). Ребро д является петлей; ребра d и f - кратные. Степени вершин 2 и 4 равны 4; вершины 3-3; вершины 1 - 2.
Ребро, соединяющие вершины, может иметь направление - тогда оно называется ориентированным и изображается стрелкой. Граф, в котором все ребра ориентированные, называется ориентированным; его ребра часто называют дугами. Дуги называют кратными, если они соединяют одни и те же вершины и совпадают по направлению. При обозначении дуги всегда сначала указывается вершина, из которой она начинается, например, на рис. 6.3,б (2,3).
Маршрут - это последовательность ребер, в котором конец предыдущего ребра совпадает с началом следующего, например, а, с, е на графе 1. Маршрут, в котором конечная вершина совпадает с начальной, называется циклом, например, с, е, d на графе 2. Граф называется связным, если между любыми двумя его вершинами имеется маршрут. Связный граф с п вершинами содержит не менее п-1 ребер.
По рассмотренной ранее классификации граф является упорядоченной, нелинейной, неоднородной структурой. Понятие графа благодаря его наглядности и высокой общности в информатике выступает в качестве основного средства описания структур данных, систем, порядка выполнения действий. Примером может служить блок-схема программы.
С точки зрения практического использования большой интерес представляет еще один тип данных, образующих упорядоченную, линейную, неоднородными структуру. Такую структуру можно рассматривать как массив неоднородных структурированных данных.
Структура называется таблицей, а ее отдельная строка - записью (логической записью). Ввиду большой значимости данной структуры она будет рассмотрена более подробно.