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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1. Отношения порядка. По порядку данных структуры делятся на упорядоченные и неупорядоченные.

В упорядоченных структурах элементы размещаются по поряд­ку, т.е. каждый элемент имеет свой порядковый номер. При этом если весь набор имеет один общий идентифика­тор (например, М), то отдельным данным присваиваются собст­венные идентификаторы - индексы (например, М₅ или М_ь).

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

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

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

В линейных структурах все элементы равноправны (массив, множество, стек, очередь).

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

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

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

Дата добавления: 2014-01-06