Простые и составные структуры данных. Основные операции с данными.

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

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

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

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

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

 

Какие данные относят к простому типу?

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

o Целочисленные;

o Символьные;

o Логические;

o Вещественные.

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

Структура. Основные операции.

Статические - к этой группе относят векторы, массивы, записи.

Векторы

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

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

Массивы

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

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

«укладываются» в памяти одна за другой. При таком представлении, например, адрес i, j элемента двумерного массива, индексы которого ограничены значениями [n1, k1][n2, k2] вычисляется как @Имя + (i – n1) * Sizeof(тип)+(j-n2)* Sizeof(тип)*(k2-n2), где @Имя - адрес первого элемента массива. Как видно, при описанном способе представления в памяти многомерных массивов сложность операции доступа к элементу массива существенно повышается по мере роста его размерности (то есть вычисление адреса элемента многомерного массива может потребовать достаточно много времени).

Записи

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

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

 

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

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

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

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

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

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