|
Программирование >> Составные структуры данных
Упражнения 6.49. Напишите свою версию программ 6.9 и 6.10, в которых выполняется перегрузка операций operator<< и operator>> вместо того, чтобы пользоваться функциями scan и show, а также внесите соответствующие изменения в профамму 6.8, обеспечивающие использование созданного интерфейса. 6.50. Напишите интерфейс и реализацию типа данных обобщенных элементов для поддержки метода сортировки комплексных чисел х + iy, использующих качестве ключа модуль + Совет: игнорирование операции извлечения квадратного корня, по-видимому, повысит эффективность. о 6.51. Напишите интерфейс, который дает определение абстрактного типа данных первого класса для обобщенных элементов (см. раздел 4.8) и построить реализацию, в которой, как и в предыдущем упражнении, элементами являются комплексные числа. Протестируйте созданный интерфейс с программами 6.3 и 6.6. [> 6.52. Добавить функцию check в тип данных array в программах 6.8 и 6.9, которые проверяют, упорядочен ли массив с помощью сортировки. 6.53. Добавить функцию testinit в тип данных array в программах 6.8 и 6.7, которая генерирует данные для тестирования в соответствии с распределениями, подобными показанным на рис. 6.13. Ввести целочисленный аргумент, посредством которого клиентская программа сможет выбирать соответствующее распределение. 6.54. Внести в программы 6.7 и 6.8 такие изменения, которые позволили бы реализовать тип данных abstract. (Ваша реализация должна распределять и поддерживать массив именно так, как это делают наши реализации стеков и очередей в главе 3.) о 6.55. Напишите интерфейс и реализацию для обобщенного типа данных Item с таким расчетом, чтобы известные методы сортировки можно было использовать с целью сортировки многомерных векторов из d целых чисел, размещая их в таком порядке: сначала идут векторы с наименьшей первой компонентой, из векторов с равными первыми компонентами первым идет тот, у которого меньше вторая компонента, из векторов с равными первыми и вторыми компонентами первым идет тот, у которого меньше третья компонента и т.д. 6.56. Напишите интерфейс и реализацию для обобщенного типа данных Item с таким расчетом, чтобы известные методы сортировки можно было использовать для сортировки полиномов (см. раздел 4.9). В рамках этой задачи пофебуется определить соответствующий порядок. 6.8 Сортировка по индексам и указателям Разработка данных типа строка, подобного используемым в программах 6.9 и 6.10, представляет особый интерес, поскольку строки символов широко используются как ключи в процессе сортировки. Более того, поскольку строки могут иметь различные длины и вообще быть очень длинными, построение, удаление и сравнивание строк может потребовать значительных затрат ресурсов, так что следует проявить особую осторожность и позаботиться о том, чтобы выбранная реализация не приводила к излишним и необязательным операциям этого вида. С этой целью применяется такое представление данных, которое состоит из указателя (на массив символов), - это стандартное представление строки в стиле языка С. Далее, первая строка программы 6.9 изменяется на typedef struct { char *str; } I tern; ЧТО обеспечивает ее преобразование в интерфейс для строк. Этот указатель помещается в структуру struct, поскольку С++ не позволяет перегружать операцию operator< для встроенных типов, каковыми являются указатели. Подобного рода ситуации не являются чем-то необычным в С++: класс (или struct), который приспосабливает интерфейс для другого типа данных называется классом-оболочкой. В рассматриваемом случае мы не требуем слишком многого от класса-оболочки, тем не менее, в некоторых случаях возможны более сложные реализации. Вскоре будет рассмотрен еще одии пример. Программа 6.11 представляет собой реализацию, ориентированную на строковые элементы. Перегруженная операция operator< легко реализуется с помощью функции сравнения строк из библиотеки С, но реализация функций scan (и rand) представляет собой более трудную задачу, поскольку нельзя упускать из виду распределение памяти для строк. Программа 6.11 использует метод, который изучался в главе 3 (программа 3.17), содержащий буфер в реализации этого типа данных. Другие варианты предусматривают динамическое распределение памяти для каждой строки, использование реализации класса, подобного классу String из библиотеки стандартных шаблонов, либо организацию буфера в клиентской программе. Можно воспользоваться любым из этих подходов (с соответствующими интерфейсами) для сортировки строк символов, используя любую из реализаций сортировки из рассмотренных выше. Мы сталкиваемся с необходимостью подобного выбора управления памятью всякий раз, когда пытаемся придавать программе модульную структуру. Кто должен нести ответственность за управление памятью, соответствующее конкретной реализации некоторых типов объектов: клиентская программа, реализация типа данных или система? Не существует однозначного и готового ответа на этот вопрос (некоторые разработчики языков программирования вообще становятся суеверными, когда этот вопрос возникает). Некоторые из современных систем программирования (включая конкретные реализации С++) содержат обобщенные механизмы, обеспечивающие автоматическое управление памятью. Мы еще раз столкнемся с этой проблемой в главе 9, когда приступим к изучению реализации более сложных абстрактных типов данных. Программа 6.11 представляет собой пример сортировки по указателю, к рассмотрению которой в обобщенном виде мы сейчас перейдем. Другой простой подход к проблеме сортировки без (непосредственных) перемещений элементов заключается в построении индексного массива, причем доступ к ключам элементов осуществляется только для того, чтобы выполнить операцию сравнения. Предположим, что сортируемые элементы находятся в массиве data[0],...,data[N-l] и мы не хотим перемещать их в силу тех или иных причин (возможно, из-за их офомных размеров). Чтобы получить эффект сортировки, используется второй массив, массив а индексов элементов. Мы начинаем с инициализации a[i] значениями i для i=0,...,N-l. Другими словами, 1ы начинаем с того, что а[0] получает значение индекса первого элемента данных. а[1] - второго элемента данных и т.д. Целью сортировки является переупорядочение массива индексов таким образом, что а[0] дает индекс элемента данных с наименьшим значением ключа, а[1] - индекс элемента данных с минимальным значением ключа из числа оставшихся и т.д. После этого эффект сортировки достигается за счет доступа к ключам через индексы - например, таким способом можно вывести массив в порядке выполненной сортировки. Программа 6.11. Реализация типов данных для строковых элементов Эта реализация позволяет выполнять сортировку строк в языке С. Для представления данных используется структура, которая содержит указатель на символ (см текст программы), благодаря чему сортировка осуществляется для массива указателей на символы, переупорядочивая их таким образом, что строки, на которые они указывают, следуют друг за другом в алфавитно-цифровом порядке. Чтобы подробно показать процесс управления памятью, мы даем определение буфера памяти фиксированных размеров, в который данный модуль помещает символы сортируемых строк; по-видимому, динамическое распределение памяти подходит больше. Реализация функции rand здесь опущена. #include <iostream.h> #include <stdlib.h> #include <string.h> #include Item.h static char buf[100000]; static int cnt = 0 ; int operator<(const Item& a, const Item& b) { return strcmp(a.str, b.str) < 0; } void show(const Item& x) { cout X. str ; } int scan(Item& x) { int flag = (cin (x.str = &buf[cnt])) != 0 ; cnt += strlen (x.str)+1, return flag; Требуется точно определить, что выбранный вид сортировки выполняет упорядочивание массива индексов, а не простые целые числа. Тип Index следует определить так, чтобы можно было перегрузить операцию operator< следующим образом: int operator<(const Index& i, const Index& j) { return data[i] < data[j]; } Если мы получим в свое распоряжение массив объектов типа Index, то любая задействованная функция сортировки так переупорядочит индексы в массиве а, что значение a[i] определит число ключей, меньших по значению, чем ключ элемента data[i] (индекс a[i] в отсортированном массиве). (Для простоты в этом обсуждении предполагается, что данные суть ключи, а не элементы в полном объеме - этот принцип можно распространить на более крупные и сложные элементы, внося в операцию operator< такие изменения, которые позволяют осуществлять доступ к специфическим ключам таких элементов, либо воспользоваться функцией-членом класса для вычисления такого ключа.) Для определения объектов типа Index используется класс-оболочка:
|
© 2006 - 2024 pmbk.ru. Генерация страницы: 0.001
При копировании материалов приветствуются ссылки. |