УМП Информационные технологии
.pdf
№ |
Задание |
21.Классы управления взрывом ракеты, летящей по баллистической траектории и имеющей определенный радиус поражения1. Задав угол наклона траектории, направление и стартовую скорость снаряда, рассчитать момент взрыва для поражения цели с заданными координатами.
22.Классы для хранения массива прямоугольных окон на экране1. Написать метод, выбирающий пары пересекающихся окон и вычисляющий площадь их пересечения.
11.Шаблоны
-Вот представь: у тебя есть 1000 рублей...
Или нет, для круглого счета, пусть у тебя
1024 рубля...
11.1. Шаблоны функций
Шаблоны – это средство языка C++, предназначенное для кодирования обобщённых алгоритмов, без привязки к некоторым параметрам (например, типам данных, размерам буферов, значениям по умолчанию). В C++ возможно создание шаблонов функций и классов. Шаблоны начинаются со слова template, после которого идут угловые скобки, в которых перечисляется список параметров. Каждому параметру должно предшествовать зарезервированное слово class или typename.
template <class T> template <typename T>
template <typename T1, typename T2>
Ключевое слово typename говорит о том, что в шаблоне будет использоваться встроенный тип данных, такой как: int, double, float, char и т. д. А ключевое слово class сообщает компилятору, что в шаблоне функции в качестве параметра будут использоваться
пользовательские типы данных.
Например, нам нужно запрограммировать функцию, которая выводила бы на экран элементы массива. Задача не сложная, но, чтобы написать такую функцию, мы должны задать тип данных массива, который будем выводить на экран. А если требуется, чтобы функция выводила массивы различных типов – int, double, float и char? Можно воспользоваться перегрузкой функций (см. § 4.2), но придется написать целых 4 функции, которые отличаются только заголовком функции, тело у них абсолютно одинаковое!
Для этого в С++ и придуманы шаблоны функций. Мы создаем один шаблон, в котором описываем все типы данных. А какой тип данных использовать в конкретной реализации, будет определено позже при компиляции функции.
template <typename T>
void print_array(const T *array, int count)
{for (int ix = 0; ix < count; ix++) cout << array[ix] << " ";
cout << endl; }
int main()
{int iArray[10] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
double dArray[6] = {1.2345, 2.234, 3.57, 4.67876, 5.346, 6.1545}; float fArray[5] = {1.34, 2.37, 3.23, 4.8, 5.879};
char cArray[4] = {"MARS"};
cout << "\nМассив типа int:\n"; print_array(iArray, 10); cout << "\nМассив типа double:\n"; print_array(dArray, 6); cout << "\nМассив типа float:\n"; print_array(fArray, 5); cout << "\nМассив типа char:\n";print_array(cArray, 4);
return 0;
}
1 На базе класса, разработанного в индивидуальном задании по предыдущей лабораторной работе.
81
В листинге перед объявлением функции стоит запись template <typename T>. Как раз эта запись и говорит о том, что функция print_array() на самом деле является шаблоном функции, так как в первом параметре print_array() стоит тип данных const T*. Это определение шаблона с одним параметром – T, причем этот параметр будет иметь один из встроенных типов данных, так как указано ключевое слово typename.
По сути T – это даже не тип данных, это зарезервированное место под любой встроенный тип данных. То есть когда выполняется вызов этой функции, компилятор анализирует параметр шаблонированной функции и создает экземпляр для соответственного типа данных: int, char и так далее.
// шаблон функции для поиска максимального значения в массиве template <typename myType>
myType searchMax(const myType * array, int size)
{myType max = array[0]; // максимальное значение в массиве
for (int ix = 1; ix < size; ix++)
if (max < array[ix]) max = array[ix]; return max;
}
Шаблоны классов будут рассмотрены ниже в применении к динамическим структурам.
11.2. Динамические структуры. Список, очередь, стек
Созданию динамических структур данных посвящен значительный объем исследований [1 - 4, 9]. Цель этих исследований состоит в конструировании таких способов хранения данных, чтобы они позволяли оптимизировать место на диске и в памяти компьютера, а также обладали свойствами быстрого поиска и/или сортировки элементов.
Нам уже встречались динамические структуры данных при рассмотрении материала о построении двумерных динамических массивов (см. § 5.5). Массивы удобно использовать в том случае, когда наперед известно точное количество элементов для хранения, если же число элементов заранее не известно, то приходится или создавать заведомо больший массив, или постоянно переприсваивать элементы массивов из меньшего в больший. В первом случае мы нерационально обращаемся с памятью, во втором – со временем. Избежать этого позволяет самая простая динамическая структура – список. Рассмотрим класс:
class list {
char data; list *next;
public:
list (char d) { data= d; next= NULL; } |
// конструктор |
~list (); |
// деструктор |
void add_node (list *node) { node->next |
= this; } // добавление узла |
list* add_char (char d); |
// создание и добавление узла |
list *getnext() { return next; } |
// get-функции |
char getdata() { return data; } |
// визуализация |
void show(); |
};
Принцип хранения очень прост (см. Рис. 22). Элемент списка состоит из двух структурных ячеек: первая – для хранения данных (data), а вторая – для хранения указателя на следующий элемент списка (next). При создании первого элемента указатель next указывает на NULL, это и обозначает конец списка (Рис. 22, а). Указатель start указывает на первый элемент списка.
a) |
start |
data |
next |
|
|
|
… |
|
|
||
б) |
start |
|
|
|
|
|
|
|
|
|
|
|
data |
|
|
|
data |
|
data |
|
|||
|
|
|
|
|
Рис. 22. Список |
|
|
|
|||
Как обращаться к элементам такой конструкции? – Последовательно переходя от элемента к элементу. Ведь список пока не имеет оператора operator [ ], - его можно будет написать позже. А пока рассмотрим на листинге ниже реализацию метода show(), последовательно выводящего на экран элементы списка.
82
В первой строке подпрограммы указателю p присваивается адрес текущего элемента this – того объекта, который вызывает метод show(), например, указатель start. Затем в цикле производится вывод данных на экран при помощи метода p->getdata() и переход к следующему элементу списка при помощи метода p = p->getnext(). Эти действия повторяются пока указатель p не станет равным NULL. Все очень просто.
void list::show()
{list *p = this;
while(p) // пока указатель p не равен NULL
{ cout << p->getdata(); // вывести на экран поле data
p = p->getnext(); } // перейти к следующему элементу списка
}
Несколько сложнее выглядит процедура добавления и удаления элементов из списка. В нашем примере предложено два метода добавления элемента в список: метод добавления уже созданного ранее объекта void add_node (list *node) и метод одновременного создания и добавления list* add_char (char d). При этом, суть этих подпрограмм одна – ее демонстрирует Рис. 23.
start |
c |
b |
… |
a |
node |
d |
|
|
|
Рис. 23. Список. Добавление узла
Здесь с помощью оператора new создается объект – узел node, указателю node->next присваивается значение start, а указателю start присваивается значение node. Готово.
list* list::add_char (char d)
{list *node = new list(d); node->next = this; return node; }
Обратите внимание на различия между реализациями методов void add_node (list *node) и list* add_char (char d)., эти различия определяют то, как они используются в программе:
int main(int argc, char* argv[])
{list *q, *p;
list *start= new list('a'); // создание списка
for(int i=1; i<13; i++) // заполнение списка при помощи add_node()
{q = new list('a' + i); start->add_node(q); start= q; }
for(int i=13; i<26; i++) // заполнение списка при помощи add_char()
{start= start->add('a' + i); }
start->show(); // вывод списка delete start; // удаление списка
return 0;
}
Осталось рассмотреть реализацию деструктора класса. Разумеется, нельзя просто уничтожить указатель start, ведь в этом случае все остальные элементы списка останутся в памяти компьютера и обнаружить их адреса станет невозможно, т.к. start удален.
list::~list()
{list *p= this, *q= this; while(p)
{q= p->next; free(p);
p=q; }
}
83
На листинге видно, что в деструкторе используются два вспомогательных указателя – p и q, последовательно в цикле пробегающие весь список. Один из них служит для удаления текущего узла списка, а второй – для сохранения адреса следующего за ним элемента.
Способы доступа к данным: стек и очередь
По способу добавления элементов в динамическую структуру и удаления из нее списки подразделяются на структуры с независимым доступом (такие как массив, где можно обратиться к любому элементу списка по номеру) и структуры с последовательным доступом – стек и очередь. [9]
Стек – это динамическая структура данных, составленная по принципу «последним вошёл – первым вышел» (LIFO, Last In First Out). Для стеков обязательными операциями являются: операция постановки в стек push(x), где х-элемент, который засылается в вершину стека и операция извлечения pop()., возвращающая последний поставленный элемент из вершины.
Чаще всего принцип работы стека сравнивают со стопкой тарелок: чтобы взять вторую сверху, нужно снять верхнюю.
Очередь – структура данных с дисциплиной доступа к элементам «первый пришёл – первый вышел» (FIFO, First In First Out). Добавление элемента (принято обозначать enqueue(х) – поставить в очередь) возможно лишь в конец очереди, выборка – только из начала очереди (что принято называть dequeue() – убрать из очереди), при этом выбранный элемент из очереди удаляется.
push() |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
a) |
data |
|
data |
|
data |
|
data |
|
data |
data |
||||||
|
|
|
|
|
|
|
|
|
|
||||||
pop() |
|
next |
|
next |
|
next |
|
next |
|
next |
|
next |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
enqueue() |
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
б) |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
data |
|
data |
|
data |
|
data |
|
data |
|
data |
|
||
|
|
|
|
|
|
|
|
|
|||||||
|
|
next |
|
next |
|
next |
|
next |
|
next |
|
next |
|
|
|
dequeue()
Рис. 24. Способы добавления и удаления элементов: а) стек; б) очередь
Проанализировав предыдущий пример, можно убедиться, что доступ к элементам списка list организован по технологии LIFO – стек.
11.3. Сложные динамические структуры данных
Мы рассмотрели (см. § 11.2) самый простой из вариантов списка – простой список, называемый в литературе так же однонаправленным списком. Но динамических структур много больше и их исследование – отдельная наука. Перечислим кратко основные виды структур.
Двунаправленный список
a) start |
|
data |
|
|
next |
б) |
start |
data |
|
|
next |
|
|
prev |
data |
next |
data |
next |
prev |
data |
data |
data |
next |
next |
next |
data |
data |
data |
next |
next |
next |
prev |
prev |
prev |
data |
next |
data |
|
next |
end |
prev |
Рис. 25. Список: а) однонаправленный; б) двунаправленный
Двунаправленный список имеет в каждом элементе (узле) два указателя: один – next – указатель на последующий элемент списка, а второй – prev – указатель на предыдущий. Удобство такого списка состоит в том, что по нему можно двигаться в обоих направлениях –
84
как от указателя start до end (совершая в цикле переход node= node->next), так и от конца к началу – от указателя end до start (передвигаясь в цикле node= node->prev).
class double_list { char data;
double_list *next; // указатель на следующий элемент списка double_list *prev; // указатель на предыдущий элемент списка
public:
...
};
Кольцевые списки
Кольцевые списки бывают как однонаправленные, так и двунаправленные, суть кольцевых списков (ring) в том, что последний элемент указывает не на NULL, а на первый элемент списка.
a) start |
|
data |
|
|
next |
б) |
start |
data |
|
|
next |
|
|
prev |
data |
next |
data |
next |
prev |
data |
next |
data |
next |
prev |
data |
next |
data |
next |
prev |
data |
next |
data |
next |
prev |
data |
next |
data |
next |
prev |
Рис. 26. Кольцевые списки: а) однонаправленный; б) двунаправленный
На рисунке (Рис. 26) приведена структура однонаправленного (Рис. 26, а) и двунаправленного (Рис. 26, б) кольцевого списка. Имея такую структуру можно двигаться в одном (или в двух) направлениях бесконечно – по кольцу. Условие прохода и обработки элементов всего списка состоит не в том, чтобы встретить NULL, а в том, чтобы встретить начало – указатель start.
class ring_list { char data;
ring_list *next; // указатель на следующий элемент списка ring_list *prev; // указатель на предыдущий элемент списка
public:
ring_list (char d) { data= d; next= this; prev= this} // конструктор ring_list* add_char (char d);
...
};
ring_list* ring_list::add_char (char d)
{list *node= new list(d); // создать новый элемент списка
list *temp= this->Prev |
// запомнить указатель на последний элемент |
this->prev= node; |
|
node->prev= temp; |
|
node->next= this; |
|
temp->next= node; |
// вернуть указатель на новое начало списка |
return node; } |
Упорядоченное хранение данных
Рассмотренные выше структуры данных имели линейную конструкцию: после одного элемента списка располагался один следующий элемент и т.д. Кроме того, списочные структуры предназначены для хранения неупорядоченных данных – элементы располагаются в такой последовательности, в какой помещены в список (по технологии очередь или стек), что, разумеется, существенно усложняет подпрограммы поиска элементов и заставляет расходовать большое количество вычислительных ресурсов – памяти и времени.
85
Проблема поиска породила целое семейство алгоритмов [9] и технологий поиска и индексирования. В содержание данного курса не входит материал по алгоритмам сортировки и поиска, поэтому лишь кратко перечислим основные принципы ускоренного доступа к данным:
алгоритмы быстрого поиска;
предварительная сортировка и упорядоченное хранение данных в структуре;
индексация данных.
Смысл индексации состоит в том, чтобы вместе с данными, хранимыми в структуре размещать упорядоченные индексы, позволяющие ускорить сортировку и поиск.
Бинарное дерево
Из вышесказанного можно сделать вывод о том, что для более быстрого доступа к данным можно хранить их в списке уже в упорядоченном виде. То есть помещать элемент в список не в конец (или начало), как в стеке и очереди, а сразу за тем элементом, который «меньше» и/или перед тем, который «больше» данного.
Кроме того, существуют структуры данных, специально созданные для упорядоченного хранения. Элементы таких структур, как бинарное дерево (Рис. 27) принципиально предназначены для размещения в систематизированном виде. Бинарное дерево является рекурсивной структурой, поскольку каждое его поддерево само является бинарным деревом и, следовательно, каждый его узел в свою очередь является корнем дерева. Узел дерева, не имеющий потомков, называется листом. [9]
Как видно, каждый элемент бинарного (двоичного) дерева имеет две ветви наследников – «left» и «right» (или иначе «больше» и «меньше»). Любой элемент при добавлении в дерево размещается не где попало, а по следующему алгоритму – начиная с «корня» дерева новый элемент сравнивается с полем «data» очередного узла. Если это элемент больше, то осуществляется переход к правому узлу, если меньше – к левому, если узла справа (или слева) нет, то на это место и размещается новый элемент. На Рис. 27, б приведен пример добавления нового узла «17» в упорядоченное дерево.
а) |
|
data |
|
|
left |
|
|
data |
start |
|
rigt |
data |
left |
|
|
left |
rigt |
|
|
|
|
rigt |
data |
|
|
|
|
|
left |
|
|
data |
|
|
rigt |
|
|
left |
|
|
rigt |
|
б) |
|
12 |
|
|
data |
|
7 |
|
36 |
|
left |
|
|
|
||
|
|
|
|
|
|
rigt |
-3 |
|
30 |
|
45 |
|
|
|
|||
data |
-5 |
0 |
17 |
33 |
47 |
left |
|
|
|
|
|
rigt |
-4 |
5 |
32 |
|
46 |
Рис. 27. Бинарное древо
Аналогично производится поиск элементов в упорядоченном бинарном дереве – существенно быстрее, чем в списке. [9]
11.4.Шаблоны классов
Врассмотренном выше (см. § 11.2) примере элементами хранения данных в поле data списка является символьный тип char. Теоретически, класс для хранения любых элементов в виде простого списка ничем не будет отличаться от класса описанного выше кроме типа поля data. Разумно было бы применить шаблон (template) для создания универсального класса, позволяющего организовать хранение объектов произвольного типа. [1]
template <аргумент1, аргумент2, ...> class имя_класса
{
86
... внутренности ...
};
Для примера напишем шаблон класса для хранения элементов в массиве. Массив может оперировать различными типами данных, такими как int, long, double и т.д.
#include <stdlib.h> #include <iostream.h>
int pos=0; //Позиция внутри массива
template <class T> //Шаблон с класса с параметром T class Massiv //Наш класс
{T Array[10]; //Пусть тип объявленного массива - из Шаблона
int count; //Счетчик элементов public:
void Add(T &); //Метод с параметром-ссылкой на переменную типа Шаблон void Show(); //Метод для отображения массива на экране
};
template<class T> void Massiv<T>::Add(T &x)
{Array[pos]=x; //Присваиваем текущий элемент pos++; //Переходим к позиции следующего элемента
count=pos; //Счетчик равен текущей позиции элемента
}
template <class T> void Massiv<T>::Show()
{for (int i=0;i<count;i++)
cout<<Array[i]<<"t"; // вывод всех данных массива на экран cout<<endl;
pos=0; //После вывода данных обозначаем, что текущий элемент нулевой
}
Класс написан так, как будто он оперирует элементами типа T. Хотя на самом деле это не так. Если объявить экземпляр класса для типа int, будет сгенерирован исходный код класса, в котором тип T будет заменен на тип int. Следует также помнить, что шаблон нельзя откомпилировать заранее, т.е. он должен всегда находиться во включаемом h-файле, а не исходном cpp-файле.
Использование шаблонного класса:
void main()
{system("CLS"); // очистка экрана
Massiv <int> Arr; // переменная типа нашего класса, тип шаблона – int Arr.Add(100); //Добавляем элементы
Arr.Add(200);
Arr.Add(300);
Arr.Show(); //Отображаем массив на экране
Massiv <char *> A; // переменная типа нашего класса, тип шаблона – char*
Arr2.Add("Строка"); //Добавляем данные Arr2.Add("Начинаю понимать"); Arr2.Add("УРА");
Arr2.Show(); //Отображаем массив на экране
}
При объявлении каждого экземпляра класса Massiv компилятором генерируется отдельная копия класса, в котором вместо типа T подставляется реально требуемый тип. Фактически можно считать, что у нас на самом деле имеется два разных класса - для типа int и char* (и два разных исходных кода для каждого класса).
Для того, чтобы еще яснее показать, что мы используем два разных класса (и заодно упростить синтаксис), можно использовать оператор typedef:
typedef Massiv <int> MassivInt; typedef Massiv <char *> MassivCharPtr;
Теперь мы можем объявлять наши массивы так:
MassivInt M1;
MassivCharPtr M2;
87
Внешне все выглядит так, как будто на самом деле существует два отдельных класса –
MassivInt и MassivCharPtr.
Рассмотрим создание шаблона такого класса на примере бинарного дерева.
Построение бинарного дерева
Сначала мы должны определить структуру для создания корня и узлов дерева:
template <class T> struct TNode
{T data;
TNode *left, *right; //constructor TNode()
{ left = right = NULL;
}
};
Здесь поля left и right - это указатели на потомков данного узла, а поле data предназначено для хранения информации. Теперь мы можем написать рекурсивную функцию, которая будет вызываться при создании дерева:
template <class T>
void makeTree(TNode <T> **pp, T x) {
if(!(*pp)) // это лист – создать поддерево
{
TNode <T> *p = new TNode<T>(); p->data = x;
*pp = p;
}
else // это ветвь – перейти к поддереву
{
if((*pp)->date > x) makeTree(&((*pp)->left), x);
else
makeTree(&((*pp)->right), x);
}
}
Эта функция добавляет элемент x к дереву, учитывая величину x. При этом создается новый узел дерева.
Функция, выполняющая обход дерева, позволяет перебрать все элементы, содержащиеся в дереве. В приведенной ниже реализации функция обхода дерева будет просто выводить на экран значение поля data каждого узла дерева (включая его корень):
template <class T>
void walkTree(TNode<T>* p)
{
if(p)
{walkTree(p->left);
cout << p->data << ' '; walkTree(p->right);
}
}
При работе с деревьями обычно используются рекурсивные алгоритмы. Использование рекурсивных функций менее эффективно, поскольку многократный вызов функции расходует системные ресурсы. Тем не менее, в данном случае использование рекурсивных функций является оправданным, поскольку нерекурсивные функции для работы с деревьями гораздо сложнее и для написания, и для восприятия кода программы.
88
11.5. Лабораторная работа № 13. Шаблоны. Динамические структуры.
Продолжительность – 4 часа. Максимальный рейтинг – 8 баллов.
Цель работы
Получить компетенции в части создания динамических структур данных (списки, кольца, деревья); получить компетенции по методам доступа к данным (стек, очередь); научиться создавать унифицированный программный код (шаблоны функций, классов); освоить умения и навыки в технологии поиска и сортировки.
Закрепить навыки конструирования классов, выделения памяти под динамические объекты класса, освобождения памяти, обращения к их свойствам и методам.
Задание на лабораторную работу
1.Создать класс, реализующий динамическую структуру хранения данных в соответствии с индивидуальным заданием (Таблица 16).
2.Задать шаблон класса, для того, чтобы созданная динамическая структура могла хранить данные различного типа. Продемонстрировать применение созданной динамической структуры как минимум с двумя различными реализациями типа хранимых данных.
3.В созданном классе реализовать конструктор, деструктор, set- и get- методы. Доступ к элементам динамической структуры организовать в виде метода в соответствии с индивидуальным заданием (Таблица 17).
4.Написать метод, реализующий поиск элемента структуры по содержанию.
5.Написать методы, производящие вывод на экран, вывод в файл, чтение из файла всех элементов динамической структуры.
6.В отчете привести листинг программы, скриншоты тестирования программы, рисунок структуры класса. Листинг программы без комментариев не принимается.
Варианты индивидуальных заданий
Таблица 16 Варианты структуры
№ |
Структура хранения данных |
1.Двунаправленный линейный список
2.Одномерный динамический массив переменной длины
3.Однонаправленный линейный список
4.Двунаправленный кольцевой список
5.Упорядоченное бинарное дерево
6.Однонаправленный кольцевой список
Таблица 17 Варианты способа доступа к элементам
№ |
Способ доступа к элементам структуры |
1.Очередь, размещение элементов с хвоста
2.Стек, размещение элементов с головы
3.Упорядоченное размещение элементов по возрастанию
4.Очередь, размещение элементов с головы
5.Стек, размещение элементов с хвоста
6.Упорядоченное размещение элементов по убыванию
7.Индексация элементов, доступ по индексу
89
Список рекомендуемой литературы
1.Бьярне Страуструп Программирование: принципы и практика использования C++,
исправленное издание. / Programming: Principles and Practice Using C++. — М.: «Вильямс», 2011. — С. 1248. — ISBN 978-5-8459-1705-8
2.Герберт Шилдт С/С++ Справочник программиста. — М.: «Вильямс», 2003. — С. 432. — ISBN 5-8459-0459-5
3.Эндрю Кёниг, Барбара Э. Му Эффективное программирование на C++. Серия книг "C++ In-Depth"++. — М.: «Вильямс», 2002. — С. 384. ил. — ISBN 5-8459-0350-5
4.Стэнли Б. Липпман, Жози Лажойе. Язык программирования C++. Вводный курс. – Спб.:
Невский Диалект, ДМК пресс, 2002. – С. 444., ил. - ISBN 5-7940-0070-8, 5-94074-040-5
5.Богуславский А.А., Соколов С.М. Основы программирования на языке Си++: Для студентов физико-математических факультетов педагогических институтов. – Коломна:
КГПИ, 2007.
6.Демидович Е.М. Основы алгоритмизации и программирования. Язык СИ : Учебное пособие. – СПб.: БХВ-Петербург, 2006.
7.Дэвис С. С++ для «чайников». – К. : Диалектика, 2005.
8.Павловская Т.А. С/С++. Программирование на языке высокого уровня. – СПб: Питер, 2007.
9.Дональд Кнут Искусство программирования, том 3. Сортировка и поиск = The Art of Computer Programming, vol.3. Sorting and Searching. — 2-е изд. — М.: «Вильямс», 2007.
— С. 824. — ISBN 0-201-89685-0
90