1.7 Типы и структуры данных
Данные, хранящиеся непосредственно в памяти ЭВМ, представляют собой совокупность нулей и единиц (битов). Биты объединяются в последовательности: байты, слова и т.д. Каждому участку оперативной памяти, который может вместить один байт или слово, присваивается порядковый номер (адрес).
Под структурой данных в общем случае понимают множество элементов данных и множество связей между ними.
Понятие физическая структура данных отражает способ физического представления данных в памяти машины и называется еще структурой хранения, внутренней структурой или структурой памяти.
Рассмотрение структуры данных без учета ее представления в машинной памяти называется абстрактной или логической структурой. В общем случае между логической и соответствующей ей физической структурами существует различие, степень которого зависит от самой структуры и особенностей той среды, в которой она должна быть отражена. Вследствие этого различия существуют процедуры, осуществляющие отображение логической структуры в физическую и, наоборот. Эти процедуры обеспечивают, кроме того, доступ к физическим структурам и выполнение над ними различных операций, причем каждая операция рассматривается применительно к логической или физической структуре данных.
Все данные необходимые для решения практических задач подразделяются на несколько типов, причем понятие типа связывается не только с представлением данных в адресном пространстве, но и со способом их обработки.
Любые данные могут быть отнесены к одному из двух типов: основному (простому, базовому, примитивному), форма представления которого определяется архитектурой ЭВМ, или сложному (структурированному, составному), который создается пользователем для решения конкретных задач.
Данные простого типа – это символы, числа и т.п. элементы, дальнейшее дробление которых на составные части, большие, чем биты не имеет смысла.
С точки зрения физической структуры важным является то обстоятельство, что в данной машинной архитектуре, в данной системе программирования всегда можно заранее сказать, каков будет размер данного простого типа и какова структура его размещения в памяти. С логической точки зрения простые данные являются неделимыми единицами.
Сложными называются такие структуры данных, составными частями которых являются другие структуры данных – простые или в свою очередь интегрированные.
В зависимости от отсутствия или наличия явно заданных связей между элементами данных следует различать несвязные структуры (векторы, массивы, строки, стеки, очереди) и связные структуры (связные списки).
Важный признак структуры данных − ее изменчивость − изменение числа элементов и (или) связей между элементами структуры. По признаку изменчивости различают структуры статические, полустатические, динамические, которые характерны для оперативной памяти и часто называются оперативными структурами. Файловые структуры соответствуют структурам данных для внешней памяти. Классификация структур данных по признаку изменчивости приведена на рис. 4.
Рис.
4. Классификация структур данных
При описании любых используемых констант, переменных, полей таблиц и функций явно или неявно указывается их тип. Выделим следующие категории типов [5]:
Встроенные типы данных, т.е. типы, предопределенные в языке программирования или языке БД (SQL). Обычно в состав встроенных типов данных включаются такие типы, операции над значениями которых поддерживаются командами компьютеров. В традиционный набор встроенных типов обычно входят следующие:
символьный тип CHARACTER (или CHAR) − это набор печатных символов из алфавита, зафиксированного в описании языка (для большинства языков англоязычного происхождения этот алфавит соответствует кодовому набору ASCII) либо произвольная комбинация нулей и единиц, размещаемых в одном байте.
логический тип BOOLEAN обычно содержит два значения - TRUE (истина) и FALSE (ложь). Несмотря на то, что для хранения значений этого типа теоретически достаточно одного бита, обычно переменные занимают один байт памяти. Над булевскими значениями возможны операции конъюнкции (& или AND), дизъюнкции (| или OR) и отрицания (~ или NOT).
тип целых чисел integer в общем случае включает подмножество целых чисел, определяемое числом разрядов, которое используется для внутреннего представления значений. При определении типа целых чисел обычно стремятся к тому, чтобы множество его значений было симметрично относительно нуля (это стимулируется и стандартными свойствами машинной целочисленной арифметики). Отрицательные целые числа обычно представляют в дополнительном коде.
Наряду со знаковыми целыми типами в языках часто поддерживаются беззнаковые целые. Для поддержки численных вычислений в языках обычно специфицируется встроенный тип чисел с плавающей точкой с базовым названием REAL или FLOAT.
Уточняемые типы данных – это типы, которые определены на основе встроенного типа данных, значения которого каким-либо образом упорядочены или ограничены.
Основной проблемой уточняемых типов является потребность в динамическом контроле значений, формируемых при вычислении выражений и возвращаемых функциями. Если для значений базовых типов (по крайней мере, числовых) такой контроль, как правило, поддерживается аппаратной частью компьютера, то для уточняемых типов требуется программный контроль, вызывающий серьезные накладные расходы.
Перечисляемые типы данных представляют явно определяемые целые типы с конечным числом именованных значений. Это очень простой и легко реализуемый механизм, часто являющийся очень полезным.
Обычно для любого перечисляемого типа предопределяются операции получения значения по его номеру и получения номера по значению. Кроме того, для перечисляемого типа предопределяются операции сравнения и получения следующего и предыдущего значения.
Конструируемые типы (составные) обладают той особенностью, что в языке предопределены средства спецификации таких типов и некоторый набор операций, дающих возможность доступа к компонентам составных значений. Любое значение конструируемого типа состоит из значений одного или нескольких других типов.
Наиболее распространенные разновидности конструируемых типов – это типы массивов, записей и множеств.
Массивы. Базовым типом массива может быть любой встроенный или определенный тип, в том числе и тип массива, тогда говорят о многомерных массивах или матрицах. Типы массивов позволяют работать с регулярными структурами данных, каждый элемент которых относится к одному и тому же базовому типу.
Записи. Позволяют определять и использовать нерегулярные структуры данных, элементы которых могут относиться к разным встроенным или явно определенным типам данных.
Множества. С использованием механизма множеств можно писать лаконичные и красивые программы, но нужно отдавать себе отчет в том, что для эффективной реализации множеств требуются серьезные ограничения их мощности. Обычно в реализациях языков допускаются множества, мощность базового типа которых не превосходит длину машинного слова, чтобы для выполнения операций над множествами можно было прямо использовать машинные команды.
Указательные типы дают возможность работы с типизированными множествами абстрактных адресов переменных, содержащих значения некоторого типа.
Понятие указателя в языках программирования является абстракцией понятия машинного адреса. Подобно тому, как зная машинный адрес можно обратиться к нужному элементу памяти, имея значение указателя, можно обратиться к соответствующей переменной. В любом случае для объявления указательных переменных служат так называемые указательные, или ссылочные типы.
Абстрактные (определяемые пользователями) типы данных. Наличие перечисляемых, уточняемых и конструируемых типов данных в сочетании со средствами выделения динамической памяти позволяет конструировать и использовать структуры данных, достаточные для создания сложных программ. Ограниченность этих средств состоит в том, что при определении типов и создании структур невозможно зафиксировать правила их использования.