грамму 3.3) для обеспечения соответствия описания функции потребностям клиента. Смысл в том, чтобы клиентские программы вполне могли обрабатывать точки без необходимости принимать какие-либо допущения об их представлении. В главе 4 будет показано, как осуществить следующий этап разделения клиента и реализации.

Пример структуры point прост и включает два элемента одного типа. Обычно в структурах смешиваются различные типы данных. Подобные структуры будут часто встречаться в оставшейся части главы.

Структуры позволяют группировать данные. Кроме того, в языке С++ можно связывать данные с операциями, которые должны с ними выполняться, путем использования механизма классов. Подробности описания классов с множеством примеров приводятся в главе 4. С применением классов можно даже использовать программу, такую как 3.2, для обработки элементов типа point после описания соответствующих арифметических операций и преобразований типов для точек. Эта возможность использования ранее описанных операций высокого уровня абстракции даже для вновь созданных типов данных является одной из важных и выдающихся особенностей программирования на С++. Она основана на способности непосредственного описания собственных типов данных средствами языка. При этом не только связываются данные со структурой, но и точно задаются операции над данными (а также структуры данных и алгоритмы, которые их поддерживают) посредством классов. Классы формируют основу рассматриваемых в книге реализаций. Однако перед детальным обзором описания и использования классов (в главе 4) необходимо рассмотреть ряд низкоуровневых механизмов для управления данными и объединения их.

Помимо предоставления основных типов int, float и char, а также возможности встраивать их в составные типы с помощью оператора struct, С++ допускает косвенное управление данными. Указатель (pointer) - это ссылка на объект в памяти (обычно реализуется в виде машинного адреса). Чтобы объявить переменную а как указатель на целое значение, используется выражение int *а. Можно ссылаться на само целое значение с помощью записи *а. Допускается объявление указателей на любой тип данных. Унарный оператор & предоставляет машинный адрес объекта. Он удобен для инициализации указателей. Например, выражение *&а означает то же, что а.

Программа 3.4 Реализация структуры данных point

Здесь содержится описание функции distance, объявленной в программе 3.3. Используется библиотечная функция вычисления квадратного корня.

#include <inath.h>

#include Point.h

float distance(point a, point b)

{ float dx - a.x - b.x, dy = a.у - b.y; return sqrt(dx*dx + dy*dy);

Косвенная ссылка на объект через указатель часто удобнее прямой ссылки, а также может оказаться более эффективной, особенно для больших объектов. Множество примеров этого преимущества приводится в разделах с 3.3 по 3.7. Как будет показано, еще важнее возможность использования указателей на структуру данных способами, которые поддерживают эффективные алгоритмы обработки данных. Указатели служат основой многих структур данных и алгоритмов.

Простой и важный пример использования указателей связан с описанием функции, которая должна возвращать множество значений. Например, следующая функция (использующая функции sqrt и atanl из стандартной библиотеки) преобразует декартовы координаты в полярные:

polar(float X, float у, float *r, float *theta)

{ *r = sqrt(x*x + y*y); *theta = atan2(y, x) ; >

Аргументы передаются этой функции по значению - если функция присваивает новое значение переменной аргумента, эта операция является локальной и скрыта от вызывающей функции. Поэтому функция не может изменять указатели чисел с плавающей точкой г и theta, но способна изменять значения чисел с помощью косвенной ссылки. Например, если вызывающая функция содержит объявление float а, Ь, вызов функции

polar(1.0, 1.0, &а, &Ь)

приведет к тому, что для а установится значение 1.414214 (), а для b - значение 0.785398 (71/4). Оператор & позволяет передавать адреса а и b в функцию, которая обрабатывает эти аргументы как указатели.

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

polar(float X, float у, floats г, floats theta)

{ г = sqrt(x*x + y*y); theta = atan2(y, x) ; }

Запись float& означает ссылка на float . Ссылки можно рассматривать как встроенные указатели, которые автоматически сопровождаются при каждом использовании. Например, в этой функции ссылка на theta означает ссылку на любое значение float, используемое для второго аргумента вызывающей функции. Если вызывающая функция содержит объявление float а, Ь, как в примере из предыдущего абзаца, в результате вызова функции ро1аг(1.0, 1.0, а, Ь) переменной а будет присвоено значение 1.414214, а переменной b - значение 0.785398.

До сих пор речь в основном шла об описании отдельных информационных элементов, обрабатываемых программами. В большинстве случаев интерес представляет работа с потенциально крупными наборами данных, и сейчас мы обратимся к основным методам достижения этой цели. Обычно термин структура данных относится к механизму организации информации для обеспечения удобных и эффективных средств управления и доступа к ней. Многие важные структуры данных основаны на одном из двух элементарных решений, рассматриваемых ниже, либо на обоих сразу. Массив (array) служит средством организации объектов фиксированным и последовательным образом, что более применимо для доступа, чем для управления. Список (list) позволяет организовать объекты в виде логической последовательности, что более приемлемо для управления, чем для доступа.

Упражнения

> 3.1 Найти наибольшее и наименьшее числа, которые можно представить типами int, long int, short int, float и double в своей среде программирования.

3.2 Протестировать генератор случайных чисел в своей системе. Для этого сгенерировать случайных целых чисел в диапазоне от О до г - 1 с помошью функции rand() % г, вычислить среднее значение и среднеквадратичное отклонение для г= 10, 100 и 1000 wN = 10, 10, 10 и Ю.

3.3 Протестировать генератор случайных чисел в своей системе. Для этого сгенерировать случайных чисел типа double в диапазоне от О до 1, преобразуя их в целые числа диапазона от О до г - 1 путем умножения на г и усечения результата. Затем вычислить среднее значение и среднеквадратичное отклонение для г = 10, 100 и 1000 и Л= 10, \0\ 10 и 10.

о 3.4 Выполнить упражнения 3.2 и 3.3 для г = 2, 4 и 16.

3.5 Реализовать функции, позволяющие применять программу 3.2 для случайных разрядов (чисел, которые могут принимать значения только О и 1).

3.6 Описать структуру, пригодную для представления игральных карт.

3.7 Написать клиентскую программу, которая использует типы данных программ 3.3 и 3.4, для следующей задачи: чтение последовательности точек (пар чисел с плавающей точкой) из стандартного устройства ввода и поиск точки, ближайщей к первой.

3.8 Добавить функцию к типу данных point (программы 3.3 и 3.4), которая определяет, лежат ли три точки на одной прямой, с допуском 10 *. Предположите, что все точки находятся в единичном квадрате.

3.9 Описать тип данных для треугольников, находящихся в единичном квадрате, включая функцию вычисления площади треугольника. Затем написать клиентскую программу, которая генерирует случайные тройки пар чисел с плавающей точкой от О до 1 и вычисляет среднюю площадь сгенерированных треугольников.

3.2 Массивы

Возможно, наиболее фундаментальной структурой данных является массив, который определен как примитив в С++ и большинстве других языков программирования. В примерах главы 1 уже встречалось использование массива в качестве основы разработки эффективного алгоритма. В этом разделе представлен еще ряд примеров.

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

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