7!а 3

Элементарные структуры данных

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

Структура данных не является пассивным объектом: необходимо принимать во внимание выполняемые с ней операции (и алгоритмы, используемые для этих операций). Эта концепция формально выражена в понятии типа данных (data type). В данной главе основное внимание уделяется конкретным реализациям базовых принципов, используемых для организации данных. Будут рассмотрены основные методы организации данных и управления ими, изучен ряд примеров, демонстрирующих преимущества каждого подхода, и сопутствующие вопросы, такие как управление областью хранения. В главе 4 обсуждаются абстрактные типы данных, в которых описание типов данных отделено от их реализации.

Ниже будет представлен обзор массивов, связных списков и строк. Эти классические структуры данных имеют широкое применение: посредством деревьев (см. главу 5) они формируют основу почти всех алгоритмов, рассматриваемых в данной книге. Рассматриваются различные

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

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

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

Изучаемые в этой главе структуры данных служат в качестве строительных блоков, которые можно использовать естественным образом в С++ и многих других языках программирования. В главе 5 рассматривается еше одна важная структура данных - дерево (tree). Массивы, строки, связные списки и деревья служат базовыми элементами большинства алгоритмов, о которых идет речь в книге. В главе 4 рассматривается использование конкретных представлений, разработанных на основе абстрактных типов данных. Эти представления могут применяться в различных приложениях. Остальная часть книги посвящена разработке различных вариантов базовых средств, деревьев и абстрактных типов данных для создания алгоритмов, решающих более сложные задачи. Они также могут служить основой для высокоуровневых абстрактных типов данных в различных приложениях.

3.1 Строительные блоки

в этом разделе рассматриваются базовые низкоуровневые конструкции, используемые для хранения и обработки информации в языке С++. Все обрабатываемые компьютером данные, в конечном счете, разбиваются на отдельные биты. Однако написание программ, обрабатывающих исключительно биты, слишком трудоемкое занятие. Типы позволяют указывать, как будут использоваться определенные наборы битов, а функции позволяют задавать операции, выполняемые над данными. Структуры С++ используются для группирования разнородных частей информации, а указатели (pointers) служат для непрямой ссылки на информацию. В этом разделе изучаются основные механизмы языка С++ в контексте представления основного принципа организации программ. Главная цель - заложить основу разработки структур высшего уровня (главы 3, 4 и 5), на базе которых будет построено большинство алгоритмов, рассматриваемых в данной книге.

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

подобных описаний - чисел и символов. В языке С++ программы построены на нескольких базовых типах данных:

Целые числа (int).

Числа с плавающей точкой (float).

Символы (char).

Принято ссылаться на эти типы по их именам в языке С++ (int, float и char), хотя часто используются обобщенные термины - целое (integer), число с плавающей точкой и символ (character). Символы чаще всего используются в абстракциях высшего уровня - например, для создания слов и предложений. Поэтому обзор cимвoльньtx данных будет отложен до раздела 3.6, а пока обратимся к числам.

Для представления чисел используется фиксированное количество бит. Таким образом, тип int относится к целым числам определенного диапазона, который зависит от количества бит, используемых для их представления. Числа с плавающей точкой приближаются к действительным числам, а используемое для их представления количество бит определяет точность этого приближения. В языке С++ путем выбора типа достигается оптимальное соотношение точности и занимаемого пространства. Для целых допускаются типы int. long int и short int, a для чисел с плавающей точкой - float и double. В большинстве систем эти типы соответствуют базовым аппаратным представлениям. Количество бит, используемое для представления чисел, а, следовательно, диапазон значений (для целых) или точность (для чисел с плавающей точкой) зависят от компьютера (см. упражнение 3.1). Тем не менее, язык С++ предоставляет определенные гарантии. В этой книге, ради простоты, обычно используются термины int и float, за исключением случаев, когда необходимо подчеркнуть, что задача требует применения больших чисел.

В современном программировании при выборе типов данных больше ориентируются на потребности программы, чем на возможности компьютера, прежде всего из соображений переносимости приложений. Например, тип short int рассматривается как объект, который может принимать значения от -32767 до 32767, а не 16-битный объект. Более того, концепция целых чисел включает операции, которые могут с ними выполняться: сложение, умножение и т.д.

Определение 3.1 7мл данных - это множество значений и набор операций с ними.

Операции связаны с типами, а не наоборот. При выполнении операции необходимо обеспечить, чтобы ее операнды и результат отвечали определенному типу. Пренебрежение этим правилом - распространенная ошибка программирования. В некоторых случаях С++ выполняет неявное преобразование типов; в других используется приведение (casting), или явное преобразование типов. Например, если х и N целые числа, выражение

((float) X) / N

включает оба типа преобразований: оператор (float) выполняет приведение - величина X преобразуется в значение с плавающей точкой. Затем для N выполняется неявное преобразование, в соответствии с правилами С++, чтобы оба аргумента оператора деления представляли значения с плавающей точкой.