Бьерн Страуструп - Язык программирования С++. Главы 5-8
Страница 88. Упражнения
|
|
Страница 88 из 88
8.9 Упражнения 1. (*2) Определите семейство списков с двойной связью, которые
будут двойниками списков с одной связью, определенных в $$8.3.
2. (*3) Определите шаблон типа String, параметром которого является
тип символа. Покажите как его можно использовать не только для
обычных символов, но и для гипотетического класса lchar, который
представляет символы не из английского алфавита или расширенный
набор символов. Нужно постараться так определить String, чтобы
пользователь не заметил ухудшения характеристик программы по
памяти и времени или в удобстве по сравнению с обычным строковым
классом.
3. (*1.5) Определите класс Record (запись) с двумя членами-данными:
count (количество) и price (цена). Упорядочите вектор из таких
записей по каждому из членов. При этом нельзя изменять функцию
сортировки и шаблон Vector.
4. (*2) Завершите определения шаблонного класса Map, написав
недостающие функции-члены.
5. (*2) Задайте другую реализацию Map из $$8.8, используя списочный
класс с двойной связью.
6. (*2.5) Задайте другую реализацию Map из $$8.8, используя
сбалансированное дерево. Такие деревья описаны в $$6.2.3 книги
Д. Кнут "Искусство программирования для ЭВМ" т.1, "Мир", 1978 [K].
7. (*2) Сравните качество двух реализаций Map. В первой используется
класс Link со своей собственной функцией размещения, а во второй
- без нее.
8. (*3) Сравните производительность программы подсчета слов из
$$8.8 и такой же программы, не использующей класса Map. Операции
ввода-вывода должны одинаково использоваться в обеих программах.
Сравните несколько таких программ, использующих разные варианты
класса Map, в том числе и класс из вашей библиотеки, если он там
есть.
9. (*2.5) С помощью класса Map реализуйте топологическую сортировку.
Она описана в [K] т.1, стр. 323-332. (см. упражнение 6).
10. (*2) Модифицируйте программу из $$8.8 так, чтобы она работала
правильно для длинных имен и для имен, содержащих пробелы
(например, "thumb back").
11. (*2) Определите шаблон типа для чтения различных видов строк,
например, таких (предмет, количество, цена).
12. (*2) Определите класс Sort из $$8.4.5, использующий сортировку
по методу Шелла. Покажите как можно задать метод сортировки
с помощью параметра шаблона. Алгоритм сортировки описан в [K]
т.3, $$5.2.1 (см. упражнение 6).
13. (*1) Измените определения Map и Mapiter так, чтобы постфиксные
операции ++ и -- возвращали объект Mapiter.
14. (*1.5) Используйте шаблоны типа в стиле модульного
программирования, как это было показано в $$8.4.5 и напишите
функцию сортировки, рассчитанную сразу на Vector<T> и T[]. |