3.3 Структура и формат данных. Статические, полустатические и динамические структуры

3.3 Структура и формат данных. Статические, полустатические и динамические структуры

На этапе определения спецификаций для разработки качественного программного обеспечения необходимо определить структуру и формат используемых в программах данных [41].

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

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

3.3.1 Классификация структур данных

С понятием структуры данных тесно связано понятие типа данных.

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

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

Между отдельными элементами структур могут наличествовать или отсутствовать явно заданные связи. В зависимости от этого следует различать: несвязные структуры (векторы, массивы, строки, стеки, очереди) и связные структуры (связные списки).

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

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

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

Рис. 3.1. Классификация структур данных

Указание типа данных четко определяет:

· размер памяти, отведенной под данную структуру и способ ее размещения в памяти;

· значения, допустимые для данного типа данных;

· операции, которые возможно над этими данными выполнять.

3.3.2. Простые структуры данных

Простые структуры данных служат основой для построения более сложных структур. Их называют также примитивными или базовыми структурами (типами данных). К ним относятся: числовые, битовые, логические, символьные, перечисляемые, интервальные, указатели. Структура простых типов данных для языка Pascal приведена на рис 3.2 (в других языках программирования набор и размеры простых типов могут отличаться от приведенного на рисунке). Размер каждого типа данных указан на рисунке в байтах через запятую от названия типа.

Рис.3.2. Структура простых типов PASCAL

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

На рис. 3.3 – 3.5 приведены примеры форматов числовых типов данных:

Рис. 3.3. Формат машинного представления беззнаковых чисел

Рис. 3.4. Формат машинного представления чисел со знаком

На рис. 3.4 s обозначает знаковый разряд числа (если s=0,то число положительное, если s=1 – число отрицательное).

Рис. 3.5. Формат представления вещественных чисел

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

3.3.3. Статические структуры данных

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

Векторы

С логической точки зрения вектор (одномерный массив) представляет собой структуру данных с фиксированным числом элементов одного и того же типа. Каждый элемент вектора имеет свой уникальный номер (индекс). Обращение к элементу вектора выполняется по имени вектора и номеру элемента.

С физической точки зрения элементы вектора размещаются в памяти в подряд расположенных ячейках памяти. Под элемент вектора выделяется количество байт памяти, определяемое базовым типом элемента этого вектора. Тогда размер памяти, отводимой для размещения вектора, будет определяться следующим соотношением: S = k * Sizeof(тип), где k – количество элементов (длина) вектора, а Sizeof(тип) – размер памяти, необходимой для хранения одного элемента вектора.

Рис. 3.6. Представление вектора в памяти

где @ Имя – адрес вектора или адрес первого элемента вектора.

Двумерные массивы

Двумерный массив (матрица) – это вектор, каждый элемент которого вектор. Поэтому то, что справедливо для вектора справедливо и для матрицы (аналогично, для n-мерных массивов).

Множества

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

Множество в памяти хранится как массив битов, в котором каждый бит указывает, является ли элемент принадлежащим объявленному множеству или нет. Таким образом, максимальное число элементов множества 256, а данные типа множество могут занимать не более 32-х байт.

Размер памяти (в байтах), выделяемых под множество, вычисляется по формуле: S = (max div 8)-(min div 8) + 1, где max и min - верхняя и нижняя границы базового типа данного множества, a div – целочисленное деление.

Рис. 3.7. Представление множества в памяти

Здесь @S - адрес данного типа множество.

Записи

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

Пример записи – набор сведений о сотруднике кафедры.

Объект «сотрудник» может обладать следующими свойствами:

· табельный номер – целое положительное число;

· фамилия-имя-отчество – строка символов и т.д.;

· пол – символ;

· ученая степень – строка символов;

· заработная плата – вещественное число;

· и др.

В памяти эта структура может быть представлена в одном из двух видов:

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

Рис. 3.8. Представление в памяти переменной типа запись в виде последовательности полей

· в виде связного списка с указателями на значения полей записи (см. рис. 3.9). При такой организации имеет место быстрый доступ к элементам, но очень неэкономичный расход памяти для хранения.

Рис.3.9. Размещение в памяти переменной типа запись в виде указателей

3.3.4. Полустатические структуры данных

Свойства полустатических структур данных:

· они имеют переменную длину и простые способы ее изменения;

· изменение длины структуры происходит в определенных пределах, не превышая какого-то максимального (предельного) значения.

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

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

К полустатическим структурам относятся стеки, очереди, деки, строки.

3.3.5. Динамические структуры данных

Динамические структуры не имеют постоянного размера, поэтому память под отдельные элементы таких структур выделяется в момент, когда они создаются в процессе выполнения программы, а не во время трансляции. Когда в элементе структуры больше нет необходимости, занимаемая им память освобождается (элемент «разрушается»).

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

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

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

· размер структуры ограничивается только объемом памяти компьютера;

· при изменении логической последовательности элементов структуры (удалении, добавлении элемента, изменении порядка следования элементов) требуется только коррекция указателей.

С другой стороны такие структуры обладают рядом недостатков:

· работа с указателями требует высокой квалификации программиста;

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

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

Связные линейные списки

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

На рис. 3.10 приведена структура односвязного списка. Здесь поле INF – информационное поле, содержащее данные, NEXT – указатель на следующий элемент списка. Голова списка – указатель на начало списка. Указатель на следующий элемент последнего элемента списка содержит значение nil, это является признаком последнего элемента.

Рис. 3.10. Структура односвязного списка

Двусвязные списки

Обработка односвязного списка не всегда удобна, так как невозможно двигаться в противоположную сторону. Такую возможность обеспечивает двухсвязный список, каждый элемент которого содержит два указателя: на следующий и предыдущий элементы. Структура линейного двухсвязного списка приведена на рис. 3.11, где поле NEXT - указатель на следующий элемент, поле PREV – указатель на предыдущий элемент. Первый и последний элементы такого списка содержат nil в указателе на предыдущий и последующий элемент соответственно.

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

Рис. 3.11. Структура двухсвязного списка

Дата добавления: 2015-08-27