ДАННЫЕ И ИХ ОБРАБОТКА

Суть всех алгоритмов (и компьютерных программ) состоит в том, что они описывают преобразование некоторых начальных данных в конечные. Какие-то данные алгоритм (программа) может использовать как промежуточные. Естественно, что представление и организация данных имеет при разработке алгоритма первостепенное значение. Вопрос о том, как должны быть организованы данные, необходимо решать до того, как начинается разработка алгоритма (программы). Ведь прежде, чем выполнить какие-либо операции, надо иметь объекты, к которым они будут применяться, и четко представлять себе структуру объектов, которые будут получены.

Развитие вычислительной техники и программирования сопровождалось эволюцией представлений о роли данных и их организации. Одним из свойств компьютеров является способность хранить огромные объемы информации и обеспечивать легкий доступ к ней. Информация, подлежащая обработке, в некотором смысле представляет абстракцию фрагмента реального мира. Мы говорим о данных как об абстрактном представлении реальности, поскольку некоторые свойства и характеристики реальных объектов при этом игнорируются (как несущественные ддя данной задачи). Например, каждый сотрудник в списке сотрудников некоторого учреждения представлен множеством данных. Это множество может включать идентифицирующие данные (например, фамилию), данные, относящиеся к тому, что сотрудник делает или к тому, что делают для него. Однако маловероятно, что будут включены такие сведения, как цвет глаз или волос, рост и вес.

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

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

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

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

9.2. ПРОСТЫЕ (НЕСТРУКТУРИРОВАННЫЕ) ТИПЫ ДАННЫХ

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

Так, над целыми числами могут выполняться операции сложения (+), вычитания (-) и умножения (*). Существуют две различные операции, связанные с делением и не выводящие за границы множества целых чисел: 1) определение целой части от деления одного числа на другое; 2) определение остатка от деления одного числа на другое.

Целые числа, используемые компьютером, имеют те же свойства (подчиняются тем же аксиомам), что и целые числа в арифметике. Все вычисления с ними выполняются абсолютно точно (не приближенно). Имеется только одно отличие в свойствах компьютерных целых чисел от тех, которыми оперирует абстрактная математика, а именно ограниченность диапазона: для каждой компьютерной системы имеется самое большое допустимое в ней целое число М_+∞ (и самое малое, отрицательное М_-∞). Обычно выполняется соотношение

М_+∞ + 1 = М_-∞ (М_-∞ - 1 = М_+∞),

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

Над действительными (или вещественными) числами могут быть выполнены операции сложения (+), вычитания (-), умножения (*) и деления (/), так же, как и над математическими действительными числами. Однако, все операции над действительными числами выполняются с точностью, не превосходящей некоторого фиксированного значения, вследствие того, что представления чисел в памяти компьютера имеют ограниченную длину (зависящую от конкретного компьютера и используемой системы программирования). Так, например, в машинной арифметике может быть 1/3 = 0,33333333, тогда как математически точное десятичное представление дроби 1/3 - бесконечно длинное число.

Главным свойством литерных (символьных) данных является их упорядоченность, т.е. свойство быть сравнимыми. Обычным признаком значения символьной или текстовой величины являются кавычки, и справедливо 'а' < 'b', 'b' < 'с', 'с' < 'd' и т.д. Каждый символ имеет определенный числовой код (например, код символа латинской буквы "А" в большинстве кодировок 63) и упорядочение происходит в соответствии с этими числовыми кодами. Как правило, имеются функции, позволяющие получить по символу его код и символ по коду.

Для строчных величин единственной выполнимой операцией является конкатенация («сложение») строк. Например, 'abcd' + 'efg' = 'abcdefg'. В конкретных системах обычно определены функции, определяющие длину строк, вхождение в них тех или иных подстрок, вырезающие из строк некоторые фрагменты.

К логическим данным, способным принимать значения «истина» («true») или «ложь» («false»), применимы основные операции логики высказываний: конъюнкция (логическое «и» - «and»), дизъюнкция (логическое «или» - «or»), отрицание (логическое «не» - «not»). Иногда можно использовать операции импликации («если»), эквиваленции («если и только если») и т.п. Эти логические операции определяются таблицей истинности, табл. 1.9.

Таблица 1.9 Таблица истинности для логических операций

Часто при решении задач оказываются полезными определенные разработчиком типы данных, представляющие собой перечисление некоторых констант или ограниченный с обеих сторон диапазон определенных ранее данных. Например, создается тип данных из двух символов 'а' и 'b' или из целых чисел в диапазоне от 1 до 100 и т. д.