Общие сведения о структурах данных

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

F Структурированные данные — это упорядоченный набор элементарные данные с характеристиками и определенными связями между ними.

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

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

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

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

– сокращение количества одиночных данных и, следовательно, многих имен.

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

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

– физический уровень представления структур в ОЗУ — последовательные списки и связные списки, а на ВЗУ все структуры представляются в виде файлов;

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

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

В зависимости от характера взаимосвязей и отношений между данными в структуре можно выделить несколько классификационных признаков:

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

2. Однородность. Однородные структуры содержат элементарные данные только одного типа (массивы, множества, стеки). Неоднородные структуры объединяют данные разных типов (записи).

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

В организованной структуре каждый элемент данных приобретает адрес. При этом объем хранимых данных возрастает на число адресов (адреса тоже данные).

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

1. Массив — упорядоченная линейная совокупность однородных данных. Другими словами это пронумерованная, равноправная совокупность данных или массивов одного типа. Если элементами данного массива являются массивы данных, тогда они должны иметь одинаковую структуру и размер. Количество индексов, определяющих положение элемента в массиве, называется мерностью массива. Если индекс единственный (M[i]) массив называется одномерным (вектор, строка, столбец). Массив, элементы которого имеют два индекса (G[i,j]) называется двумерным или матрицей. Первый индекс является номером строки, а второй индекс — номером столбца, на пересечении которых находится данный элемент. Максимальная мерность массива может быть ограничена синтаксисом некоторых языков программирования, либо не иметь таких ограничений.

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

Допустимый набор операций над элементами массива определяется типом элементарных или структурированных данных, из которых массив сформирован.

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

2. Стек (магазин) и очередь являются упорядоченными, линейными, неоднородными структурами. Они реализуются в виде специальным образом организованных областей ОЗУ либо в качестве самостоятельных блоков памяти. Ячейки памяти стека (или регистры стековой памяти) соединяются друг с другом таким образом, что ввод данных возможен только в первую ячейку со сдвигом всех ранее записанных данных. При считывании — содержимое всех ячеек памяти стека сдвигается и выталкивает содержимое первой ячейки (рис. 37). Другими словами, вход в стек возможен только через первую ячейку (вершину стека), поэтому извлекаться первой будет та информация, которая была занесена последней, подобно пассажиру переполненного автобуса. Отличие очереди от стека только в том, что извлечение информации производится в порядке «первым вошел — первым вышел», т. е. со дна стека.

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

3. Дерево или иерархия является примером нелинейной структуры. В ней элемент каждого уровня (за исключением самого верхнего) входит в один и только один элемент следующего (более высокого) уровня. Элемент самого высокого уровня называется корнем, а самого нижнего уровня — листьями. Отдельные элементы могут быть однородными или нет. Примером подобной организации служат файловые структуры на ВЗУ компьютера. В иерархической структуре адрес каждого элемента определяется путем доступа (маршрутом), ведущим от вершины структуры к данному элементу.

Достоинства иерархических структур данных:

– они не создают проблем с обновлением данных;

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

Недостатки иерархических структур:

– относительная трудоемкость записи адреса элемента данных;

– упорядочение по форме сложнее, чем линейные и табличные структуры.

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

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

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

5. Таблица. Она относится к упорядоченной, линейной, неоднородной структуре. Отдельная строка таблицы называется записью (логической записью). Логическая запись — поименованная совокупность элементарных данных, имеющая смысловую завершенность. Смысловая завершенность означает, что данные характеризуют некоторую систему или объект, а не являются разрозненными по смыслу. Запись в целом отражает различные свойства (атрибуты) системы.

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

Поля записи связаны между собой. Связи между ними могут носить функциональный характер (значение одного поля посредством некоторого преобразования (правила) определяет значение другого; например, две первые цифры поля «Номер зачетной книжки» равны двум последним поля «Год поступления»), либо связи могут быть причинно-следственными (например, поле «Год рождения» определяется значением поля «Фамилия»).

Логические записи сами могут объединяться и образовывать структуры, которые определяются моделью данных. Например, совокупность записей для всех студентов, обучающихся в одной группе, образуют массив, который называется базой данных (реляционного (описательного) типа). Обращение к базе при сохранении и использовании осуществляется по ее идентификатору (например, ГРУППА 101). Возможны и более высокие структурные объединения. Например, структуры, элементами которых будут базы данных (объединение баз данных по всем группам факультета).

Схема многоуровневой иерархической структуры данных представлена на рис. 39.

F Программные системы, позволяющие создавать и использовать базы данных, называются системами управления базами данных (СУБД).

Логическая запись имеет собственный идентификатор, по которому можно обратиться к записи в целом (например, порядковый номер студента в группе). Поля также имеют идентификаторы, по которым они становятся доступны для просмотра или изменения значения. Идентификатор поля строится из идентификатора базы, идентификатора записи и собственно имени поля, например, ГРУППА_101(13).Фамилия.

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

Структура информационного массива определяется один раз на этапе его создания и в процессе использования уже не изменяется. В языках программирования это достигается описанием структуры в блоке описаний программы; в СУБД — установлением перечня и последовательности полей записи на начальном этапе создания базы данных. Всякое изменение структуры (например, введение дополнительного поля записи или удаление имеющегося) эквивалентно созданию новой структуры. Что же касается количества записей в структурированном информационном массиве, то при представлении его в ОЗУ компьютера возможны две ситуации: либо под него выделяется область ОЗУ фиксированного размера, либо размер области при необходимости может меняться.

В первом варианте в начале работы программы происходит резервирование областей ОЗУ для хранения информационных массивов. С этой целью в тексте программы указывается, какого типа и размера информационные массивы будут в дальнейшем использованы. В процессе выполнения программы могут меняться значения элементов информационного массива, но не его размер. По этой причине в случае, если размер (число элементов) массива не известен заранее (например, количество учеников в классе), приходится осуществлять избыточное резервирование, что, безусловно, приводит к нерациональному использованию памяти компьютера. Именно таким образом происходит резервирование памяти при описании массивов и других структурных данных в языке PASCAL. Отсутствие возможностей динамического описания массивов (т. е. введение новых массивов или изменение размеров имеющихся в процессе выполнения программы) считается одним из существенных недостатков языка программирования.