Типы данных

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

В программировании используется правило, по которому тип явно указывается в описании константы, переменной или любой функции. Это правило особенно важно потому, что транслятор должен выбирать представление данного объекта в памяти машины. Ясно, что память, отводимая под значение переменной, должна выбираться в соответствии с диапазоном значений, которые может принимать переменная.

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

Итак, любое значение может быть отнесено к одному из двух типов: основному (простому), форма представления которого определяется структурой ЭВМ, или сложному, конструируемому пользователем для решения конкретных задач. Например, для нас многоугольники на плоскости - простые и вполне понятные данные, над которыми можно выполнять различную обработку: вычислять площадь, периметр, значение диагоналей и углов, осуществлять перемещение, поворот и масштабирование многоугольника на плоскости; определять фигуры, получаемые в результате пересечения или объединения таких многоугольников и т.п. Каким же образом в данном случае следует представлять многоугольники в памяти ЭВМ, чтобы иметь возможность такой обработки?

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

Элементами данных являются символы, числа и тому подобные данные, дальнейшее дробление которых не имеет смысла. Они используются в качестве структурных элементов сложных данных. К символам обычно относят буквы, цифры, знаки и спецсимволы. Многие типы чисел хорошо известны - натуральные, целые, десятичные числа с плавающей точкой и т.п. Максимальные и минимальные числа, представимые в машине, задают диапазон значений целых чисел, а также диапазон и точность представления вещественных чисел. Целые числа из диапазона 0 и 1 часто рассматривают как значения логического типа (переключатель, флажок). Значение физической единицы измерения числовой величины, например длины, времени или денежной единицы, устанавливает границы применимости операций, что позволяет избежать многих ошибок при программировании. Сказанное справедливо и для безразмерных величин, если известно, какой смысл приписывает человек обрабатываемым данным.

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

Табл.2.1 Структуры данных

Простые	Целые
	Логические
	Символьные
	Вещественные
Сложные	Массивы
	Массивы переменной длины	Кольцо
		Стек
		Очередь
		Дек
		Список
	Дерево
	Запись
	Множество

Рассмотрим их подробнее.

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

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

Кольцо представляет собой одномерный массив с замкну­тыми концами, т. е. массив, в котором концы отсутствуют (рис.2.1.а). Типичным примером такой структуры является таблица объектов, обработка которых производится путем последовательного обхода, например, входных сигналов, по­ступающих от терминалов, в системе с разделением времени. И в случае когда регистрируются новые данные (n элемен­тов данных), которые вводятся в процесс равномерно во вре­мени, и в случае когда поддерживается процесс выполнения плана, намеченного на каждый день из последующих три­дцати, начиная от данного дня, обычно используется кольцо. Итак, кольцо—это такая структурная организация массива данных, при которой целесообразнее перемещать границы массива, оставляя неподвижными его элементы. Если органи­зовать кольцо неопределенной длины, то его можно исполь­зовать как очень гибкую структуру, в нужное место которой можно вводить или исключать элементы данных.

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

Стек называли также магазинным списком, использовали и другие названия, которые в конце концов были унифицированы. В отличие от очереди, которая будет рассмотрена следующей, стек называли также списком, в котором первым считается элемент, записанный последним (LIFO—last-in first-out list). Смысл этого названия очевиден и отражает дисциплину обслуживания списка. Например, при заполнении магазина автоматического оружия используется принцип стека. Одинаковые патроны, точно вставленные в верти­кальную прорезь, поддерживаются пружиной, находящейся на дне магазина. При заполнении прорези патронами неза­висимо от их числа самый верхний, благодаря действию пружины, будет находиться на определенной высоте, удобной для того, чтобы использовать его для стрельбы. Здесь как раз исполь­зуется принцип стека.

Структура типа очередь также представляет собой одно­мерный массив переменной длины и аналогична очереди лю­дей перед окошком кассы, торговым автоматом или телефо­ном-автоматом. Включение и исключение данных выполня­ются на разных концах массива (см. рис. 2.1.в). В отличие от LIFO это список, в котором первым считывается элемент, записанный первым (FIFO—first-in-first-out list). Очереди широко используются в операционных системах, например, для организации одновременного использования устройств ввода-вывода многими пользователями или единственного центрального процессора несколькими программами.

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

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

Для рассмотрения такого важного понятия как список целесообразно рассмотреть представление данных в ЭВМ, поэтому мы рассмотрим это понятие в разделе, где будет рассмотрено представление структур в ЭВМ. А пока только ограничимся определением списка. Списком называется одномерный массив, который можно свободно изменять.

Рис. 2.1 Совокупности элементов данных: а—кольцо; б—стек; в—оче­редь; г—двусторонняя очередь; д—двусторонняя очередь с ограничен­ным входом (включение данных разрешено только на одном конце); е— двусторонняя очередь с ограниченным выходом (исключение данных раз­решено только на одном конце)

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

Совокупность элементов данных разного типа называют записью. В простейшем случае запись содержит постоянное число элементов (f1,f2,..., fk), называемых полями. Каждое поле fi представляет собой элемент данных определенного типа. Практическими примерами записей могут служить на­кладные и прочие документы в конторских операциях; одна накладная представляет собой отдельную запись. Пример записи показан на рис.2.2. Значением поля записи может быть последовательность символов произвольной длины. В та­ком случае одномерный массив с произвольным числом эле­ментов можно представить или одним полем, или совокуп­ностью полей. В первом случае получим записи с полями пе­ременной длины, а во втором—записи с переменным числом полей.

(Номер служащего фирмы (5-значное число), ХХХХХ

фамилия и имя (15 знаков), ХХХХХХХХХХХХХХХ

дата рождения (5-значное число), ХХХХХ

код подразделения (3-значное число), ХХХ

код профессии (3-значное число)) ХХХ

Рис. 2.2. Запись основного файла «Список служащих фирмы»

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

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

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

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

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

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

Дата добавления: 2014-12-16