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

#include <stdlib.h> #include Item.h #include exch.h #include Array.h inain(int argc, char *argv[]) { int N = atoi(argv[l]), sw = atoi(argv[2]);

Item *a = new Item[N] ;

if (sw) rand(a, N) ; else scan(a, N) ;

sort(a, 0, N-l);

show (a, 0, N-l) ;

Программа 6.7. Интерфейс для данных типа массив.

Интерфейс Array.h определяет высокоуровневые функции для массивов абстрактных элементов: инициализирует случайными значениями, инициализирует значениями, считанными из стандартного ввода, распечатывает содержимое и выполняет сортировку содержимого.

tenlate <class Item>

void rand (Item a[], int N) ; ten5>late <class Item>

void scan(Item a[], int &N); ten>late <class Item>

void show(Item a[] , int 1, int r); tenlate <class Item>

void sort(Item a[] , int 1, int r);

Интерфейс программы 6.7. определяет примеры высокоуровневых операций, которые можно выполнять над массивами. Требуется реализовать возможность инициализировать массив значениями ключей, которые имеют случайное распределение или поступают из стандартного ввода; кроме того необходимо иметь возможность сортировать вхождения (а как же!) и, наконец, иметь возможность печатать содержимое массивов. Это только лишь несколько примеров; в конкретном приложении может возникнуть необходимость определять и другие операции (класс Vector в библиотеке стандартных шаблонов является одним из подходов, обеспечивающим обобщенный интерфейс этого вида). Пользуясь программой 6.7, можно подставлять различные реализации той или иной операции без необходимости внесения изменений в клиентскую программу, которая использует этот интерфейс - в данном случае, в функцию main программы 6.6. Исследуемые здесь различные реализации сортировок могут служить реализациями функции sort. В программе 6.8 имеются простые реализации других фуккций. Модульная организация программы позволяет подставлять другие реализации в зависимости от приложения. Например, можно воспользоваться реализацией функции show, которая печатает только часть массива при проверке сортировки массивов очень больших размеров.

Программа 6.8. Реализация типа данных массива

Приведенный ниже код представляет собой реализацию функций, определенных в программе 6.7. Эта реализация использует типы Item и обрабатывающие их базовые функции, которые определены в отдельном интерфейсе (см. программу 6.9).

#include <iostream.h> #include <stdlib.h> #include Array.h template <class Item> void rand(Item а[] , int N)

{ for (int i = 0; i < N; i++) rand(a[i]); } template <class Item> void scan(Item a[], int &N)

{ for (int i = 0; i < N; i++) if (!scan(a[i])) break; N = i;

template <class Item> void show(Item a[], int 1, int r) { for (int i = 1; i <=r; i++) show (a [i]) ; cout endl ;

Подобным же образом, чтобы иметь возможность работать с конкретными типами элементов и ключей, мы даем определения их типов и объявляем все необходимые операции над ними в явном интерфейсе, а затем следуют реализации этих операций, определенных в интерфейсе элемента. Например, рассмотрим приложение в виде некоторого бухгалтерского отчета, в котором могут быть использованы ключи, соответствующие номеру счета клиента, и числа с плавающей точкой, соответствующие сумме на счетах клиента. Программа 6.9 являет собой пример интерфейса, который определяет тип данных для такого рода приложения. Код этого интерфейса объявляет операцию <, которая нужна для сравнения ключей, а также для функций, которые генерируют случайные значения ключей, считывают ключи и выводят значения ключей на печать. В программе 6.10 содержатся реализации функций, используемых в этом простом примере. Разумеется, можно приспособить эти реализации под конкретные приложения. Например, Item может иметь абстрактный тип данных (АТД)), определенный в виде класса С++, а ключи могут быть функциями-членами класса, а не элементами данных соответствующей структуры. Такие АТД рассматриваются в главе 12.

Программа 6.9. Пример интерфейса для данных типа Item

Файл Item.h, включенный в программу 6.6, дает определение типа данных сортируемых элементов. В этом примере элементами являются небольшие записи, состоящие из целочисленных ключей, и связанная с ними информация, представленная числами с плавающей точкой. Мы объявляем, что перегруженная операция operator< будет реализована отдельно, равно как и три функции: scan (считывает Item в своем аргументе), rand (сохраняет случайный Item в своем аргументе), show (печатает item).

typedef struct record { int key; float info; } Item;

int operator<(const Item&, const Item&);

int scan(Item&); void rand(Item&) ; void show(const Item&);

Распечатано программой FmePnnt -1

Программы 6,6-6.10 вместе с любыми подпрограммами сортировки из числа представленных в разделах 6.2-6.6, тестирует сортировку небольших по размерам записей. Построение такого рода интерфейсов и реализаций для других типов данных позволяет применять рассмотренные выше методы для сортировки различных видов данных - таких как комплексные числа (см. упражнение 6.50), векторы (см. упражнение 6.55) или полиномы (см. упражнение 6.56) - и при этом вообше без каких-либо изменений в кодах программ сортировки. Для более сложных типов элементов интерфейсы и реализации также должны быть более сложными, однако решение проблем реализации полностью отделено от вопросов построения алгоритмов сортировки, которые были предметом наших исследований. Одни и те же механизмы можно задействовать для большинства методов сортировки, рассматриваемых в данной главе, а также тех, которые будут изучаться в главах 7-9. В разделе 6.10 мы подробно проанализируем одно очень важное исключение - в результате анализа станет ясно, что целое семейство алгоритмов сортировки, которое должно иметь совсем другое конструктивное оформление, заслуживает того, чтобы стать предметом изучения в главе 10.

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

Программа 6.10. Пример реализации типа данных

Этот программный код является реализацией перегруженной операции operatoK и. функций scan, rand и show, которые объявлены в программе 6.9. Поскольку записи представляет собой структуры небольших размеров, можно сделать так, чтобы функция exch использовала встроенный оператор присваивания без ненужных забот относительно затрат на копирование элементов.

#include <iostreain.h> #include <stdlib.h> #include Item.h

int operator<(const Itemfi A, const Itemfi B)

{ return A.key < B.key; } int scan(Item& x)

{ return (cin x.key x.info) != 0; } void rand(Item& x)

{ x.key = 1000*(1.0*rand()/RAND MAX); x.info 1.0*rand()/RAND MAX; } void show(const Item& x)

{ cout x.key x.info endl; }