Данные. Понятие типа данных

Данные. Алгоритм, реализующий решение некоторой конкретной задачи, всегда работает с данными. Данные — это любая информация, представленная в формализованном виде и пригодная для обработки алгоритмом.

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

Данные делятся на переменные и константы.

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

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

S = pR².

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

Идентификатор (по определению) представляет собой последовательность букв и цифр, начинающаяся с буквы.

Типы данных. С данными тесно связано понятие типа данных. Любой константе, переменной, выражению (с точки зрения обработки на ЭВМ) всегда сопоставляется некоторый тип. Тип данных характеризует множество значений, к которым относится константа и которые может принимать переменная или выражение. Например, если переменная в некотором алгоритме может принимать только значения из множества целых чисел, то ей ставится в соответствие целый тип данных.

Типы данных принято делить на простые (базовые) и структурированные.

К основным базовым типам относятся:

• целый (INTEGER) — определяет подмножество допустимых значений из множества целых чисел;

• вещественный (REAL) — определяет подмножество допустимых значений из множества вещественных чисел;

• логический (BOOLEAN) — множество допустимых значений — истина и ложь;

• символьный (CHAR) — цифры, буквы, знаки препинания и пр.

Тип INTEGER задает подмножество целых чисел, мощность которого зависит от такой характеристики ЭВМ, как размер машинного сло­ва. Если для представления целых чисел в машине используется п раз­рядов (причем один из них отводится под указание знака числа), то до­пустимые числа должны удовлетворять условию -2^n-1 2^n-1. Считается, что все операции над данными этого типа выполняются точ­но и соответствуют обычным правилам арифметики. Если результат выходит за пределы допустимых значений, то вычисления будут пре­рваны. Такое событие называется переполнением. Четыре арифметические операции считаются стандартными: сложение (+), вычитание (-), умножение (*) и деление (/). Для целых чисел может быть определен дополнительный стандартный тип — целое без знака, задающий подмножество целых положи­тельных чисел. Если для представления целых без знака используется п разрядов, то переменным такого типа можно присваивать значения, удовлетворяющие условию

Тип REAL обозначает подмножество вещественных чисел, границы, изменения которых также определяются характеристиками конкретной ЭВМ. И если считается, что арифметика с данными типа INTEGER дает точный результат, то допускается, что аналогичные действия со значениями типа REAL могут быть неточными, в пределах ошибок округлений, вызванных вычислениями с конечным числом цифр. Это принципиальное различие между типами REAL и INTEGER. Два значения базового типа BOOLEAN обозначаются идентификаторами TRUE FALSE. В базовый тип CHAR входит множество печатаемых символов и символов-разделителей в соответствии с кодом ASCII.

Приведем пример представления числовой информации в различных типах данных применительно к ЭВМ с 16-разрядным машинным словом.

Пусть задано число 12345.

Если этой константе поставлен в соответствие тип INTEGER, то внутренняя стандартная форма представления в памяти (для обработки в двоичной арифметике) — 0011000000111001. Объем — 2 байт, 16 двоичных разрядов. Если для константы определен тип REAL, то число представляется в форме с плавающей точкой и занимает объем 4 байта, 32 двоичных разряда. И, наконец, если число рассматривается как последовательность символов типа CHAR (символьное представление), то каждая его цифра представляется байтом в соответствии с кодом ASCII. Представление 12345 есть —00110001 00110010 00110011 00110100 00110101. Объем — 5 байтов. Переменные и типы данных вводятся для того, чтобы использовать их в различных алгоритмах обработки. Следовательно, нужно иметь еще и множество операций, которые можно применять к данным того или иного типа. Так, к переменным типа REAL и INTEGER применимы арифметические операции, к переменным типа BOOLEAN — логиче­ские (см. п. 1.3), к символьным переменным применима операция конка­тенации — «соединения» символов. Операции отношения или сравне­ния применяются к данным любого типа, но правила их применения различны. Рассмотрим, например, результат применения некоторых операций к значениям 123 и 45 в зависимости от их типа:

Знак	Операция	Запись	Типданных	Результат
+	Сложение	123+45	INTEGER
Конкатенация	«123»+ «45»	CHAR	«12345»
>	Больше	123 > 45	INTEGER	Истина (TRUE)
«123»> «45»	CHAR	Ложь (FALSE)

Таким образом, тип данных — это такая характеристика данных, которая, с одной стороны, задает множество значений для возможного изменения данных и, с другой стороны, определяет множество операций, которые можно к этим данным применять, и правила выполнения этих операций. До сих пор мы говорили о переменных, хранящих только одно значение, и рассматривали возможности различного представления и использования этого значения при решении конкретных задач. На самом деле, огромное количество алгоритмов требует одновременного хранения в памяти целых наборов однородных объектов, при­чем длина этих наборов может быть заранее неизвестна. Например, пусть необходимо обрабатывать данные о среднесуточной температуре за год для вычисления максимальной и минимальной температур, среднемесячной и среднегодовой температуры и т.п. Для реализации таких алгоритмов необходимо обеспечить хранение каждого отдельного значения среднесуточной температуры. Если иметь при этом в виду переменные базового типа Real, то таких переменных потребова­лось бы 365.

Рассмотрим другой пример. Пусть решение некоторой задачи тре­бует вводить и обрабатывать следующие данные о студентах: фамилия, имя, отчество, дата рождения, год поступления в вуз, номер студенче­ского билета. При этом алгоритм должен обеспечить возможность ввода произвольного количества данных. Здесь речь идет об обработке одно­родных объектов, которые можно условно назвать «Информация о сту­денте», представляющих собой совокупность разнородных данных или атрибутов (фамилия, имя и т.д.). Для решения подобных задач применяются структуры данных, поддерживаемые множеством структурированных типов данных.

Структурированные типы описывают наборы однотипных или разнотипных данных, с которыми алгоритм должен работать как с од­ной именованной переменной.

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

Рис. 4. Сортировка массива из 5 элементов

Метод сортировки посредством простого выбора предполагает циклический просмотр элементов массива, начиная с i-го (i= 1,2,..., N— 1), поиск минимального элемента и перестановку найденного минимально­го элемента с i-м. За N — 1 проход по массиву (элемент с номером N останется на своем месте) числа будут отсортированы (рис. 1.4).

Подобный алгоритм, очевидно, состоит из трех этапов:

• ввод элементов массива;

• цикл обработки массива;

• вывод отсортированных чисел из массива.

Цикл обработки массива представляет собой совокупность двух «вложенных» циклов: первый цикл (с переменной цикла i) обеспечивает «внешний» проход по элементам массива, начиная с 1-го и кончая элементом с номером N - 1, который должен заканчиваться на каждом шаге перестановкой элементов; второй цикл (с переменной циклау) реа­лизует поиск минимального элемента среди элементов с номерами от i + 1 до N (т.е.у меняется от i + 1 до N). Блок-схема предлагаемого алгоритма сортировки представлена на рис. 5.

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

Рис. 5. Блок-схема алгоритма сортировки элементов массива по возрастанию

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

z типа Complex — объект, описывающий комплексное число, с по­лями re и im типа Real;

d типа Date — объект, описывающий дату, с полями day, month и year со значениями из подмножеств типа Integer (например, day может быть целым числом в интервале от 1 до 31);

р типа Person — объект «Информация о студенте» с полями family, firstname, secondname, Date, year, num.

Таблица 1.2. Типы и структуры данных в некоторых языках

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