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

1. Классификация и примеры структур данных

2. Понятие логической записи

Можно указать ряд причин, поясняющих необходимость и удобство организации данных в некоторую структуру:

• Отражение в организации данных логики задач, объективно существующей взаимосвязи и взаимообусловленности между данными;

• Оптимизация последовательности обработки данных;

• Неудобство использования большого количества одиночных данных, поскольку это ведет к необходимости использования многих имен (идентификаторов).

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

Относительно структур данных необходимо сделать следующие общие замечания:

• Логический уровень организации данных отражается в тексте программы – логическим уровнем определяется порядок обработки данных;

• Физический уровень представления структур в ОЗУимеет всего две разновидности:последовательные спискиисвязные списки; наВЗУ(внешних запоминающих устройствах) все структуры данных представляются в видефайлов;

• Обработкаданных возможна только после их размещения вОЗУ; сВЗУ определены только операциичтения изаписи;

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

1. Классификация и примеры структур данных

Структурирование данных предполагает существование (или установление) между ними каких-то отношений (связей). В зависимости от характера этих отношений можно выделить несколько классификационных признаковструктур данных:

• Отношение порядка;

• Однородность;

• Характер отношений между элементами.

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

Примером неупорядоченных структур являются множества – в них не определен порядок элементов; единственное, что можно установить в этом случае для каких-то конкретных данных, так это их принадлежность (или непринадлежность) выбранному множеству.

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

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

Далее рассмотрим и охарактеризуем некоторые структуры данных: массив, стек, очередь, дерево,граф.

Массив. Упорядоченная линейная совокупность однородных данных называется массивом.

Комментарии к определению:

• Термин «упорядоченная» здесь означает, что элементы массива пронумерованы;

• Термин «линейная» свидетельствует о равноправности всех элементов массива;

• Термин «однородных» подчеркивает следующее: в том случае, когда массив формируется из элементарных данных, это могут быть данные лишь одного типа, например, массив вещественных чисел или массив символов; если же элементами массива окажутся сложные (структурые) данные, например, массив массивов – в этом случае «однородных» означает, что все массивы, являющиеся элементами сложного массива, должны иметь одинаковую структуру и размер.

Мерность (размерность) массива – это количество индексов (сам индекс – величина переменная), определяющих положение элемента в массиве.

Так, если индекс единственный, массив называется одномерным; часто такой массив называютвектором,строкойилистолбцом. Для обозначения элементов ономерного массива используется обозначение, в языках программирования приняты обозначенияm[i]илиm(i).

Массив, элементы которого имеют два индекса, называется двумернымилиматрицей. Элементы матрицы обозначаются,m[i,j]илиm(i,j). Первый индекс (i) – это номер строки, второй индекс (j) – это номер стобца, на пересечении которых находится данный элемент массива. Массивы с тремя индексами называютсятрехмерными, с четырьмя –четырехмернымии так далее Максимальная мерность массива либо может быть ограничена синтаксисом языка программирования, либо может не иметь такого ограничения.

Размермассива – это максимальные значения индексов элементов. Размер массива указывается в блоке описания программы; при исполнении программы для хранения элементов массива резервируется необходимый объем памяти. Если в процессе исполнения программы размер массива не изменяется (или не может быть изменен), то в этом случае говорят остатическоммассиве (массивефиксированного размера). Если определение размера массива происходит по ходу выполнения программы, то такой массив называетсядинамическим(илидинамически описываемым).

Допустимый набор операций над элементами массива определяется типом данных (элементарных или структурированных, в зависимости от ситуации), из которых массив сформирован. В некоторых языках программирования над массивом в целом определена операция присваивания M:=<значение>, когда всем элементам массива присваивается одинаковое значение. Возможна операция присваивания для двух одинаковых по типу, размерности и размеру массивовM2:=M1, когда производитсяпоэлементноеприсваивание значений, то есть, где,.

Существуют символьные массивы– они называютсястрокамиилистроковыми данными(например, типStringв языке программированияPASCAL). С ними возможен целый набор операций, неопределенных для одиночных символьных данных: операцияконкатенации(объединения) строк с формированием новой строки, операция замещения части строки, определения числовых (количественных) характеристик строки.

Стек. Существует структура данных, в которой элемент, помещенный в нее первым, выходит последним, и наоборот, тот элемент, который последним входит, выходит первым (рис. 14). Такая структура данных получила названиестек (илимагазин– по сходству с магазином стрелкового оружия). «Стек» на аглийском означает «стопка».

Рис. 14. Стек

Эти структуры реализуются в виде специальным образом организованных областей ОЗУ компьютера. Часто стек называют памятью типа LIFO(Last-InFirst-Out). В стеке ячейки памяти (или регистры стековой памяти) соединяются друг с другом таким образом, что занесение данных в стек возможно только через первую ячейку (вершину стека), при этом содержимое остальных ячеек сдвигается вниз, по направлению к дну стека по мере его заполнения. Извлекаться первым будет содержимое ячейки, которая была заполнена последней – то есть ячейки, ближайшей к вершине стека.

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

Очередь. Отличиеочередиот стека в том, что извлечение информации из очереди производится по принципу «первым вошел – первым вышел», то есть со дна структуры. Извлекается первым содержимое той ячейки, которая была заполнена первая (рис. 15).

Рис. 15. Очередь

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

Дерево. Деревоилииерархияявляется примером нелинейной структуры. В ней элемент каждого уровня (за исключением самого верхнего) входит в один и только один элемент более высокго уровня. Элемент самого высокого уровня называетсякорнем, а элементы самых нижних уровней называютсялистьями (рис. 16):

Рис. 16. Дерево

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

Граф. Часто отношения между данными представляются в видеграфа– совокупности точек и линий, причем каждая линия соединяет две точки. Точка получает смысл элемента структуры (данных), а линии – смысл отношения между элементами.

Точки называются вершинамиграфа, линии называютсяребрамиграфа.

Ребро, соединяющее две конкретные вершины, называется инцидентнымэтим вершинам, а сами эти вершины называютсясмежными; причем они инцидентны этому ребру.

Число ребер, инцидентных вершине, называется степеньювершины.

Если два ребра инцидентны одной и той же паре вершин, то эти ребра называются кратными.

Ребро, у которого совпадают обе вершины, называется петлей.

Граф задается списком вершин и списком ребер, в котором для каждого ребра указывается пара инцидентных для него вершин.

Например, для графа на рис. 17: список вершин{1,2,3,4}; список ребер:a(1,2), b(1,4), c(2,4), d(2,3), e(3,4), f(2,3), g(4,4); смежные пары вершин:(2,3), (2,4), (1,2), (1,4), (3,4); реброgявляется петлей; ребраdиf– кратные; степени вершин 2 и 4 равны 4; степень вершины 3 равна 3; вершины 1 – равна 2.

Рис. 17. Неориентированный граф

Ребро, соединяющее вершины, может иметь направление – тогда это ребро называется ориентированными изображается стрелкой (рис. 18).

Граф, в котором все ребра ориентированные, называется ориентированным; ребра ориентирванного графа называютсядугами.

Дуги называются кратными, если они соединяют одни и те же вершины и совпадают по направлению. При обозначении дуги всегда первой указывается вершина, из которой дуга начинается, например, (2,3) нарис. 18.

Рис. 18. Ориентированный граф

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

Граф называется связным, если между любыми двумя его вершинами имеется маршрут.

Граф является упорядоченной,нелинейной,неоднороднойструктурой.

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