Многие алгоритмы не зависят от типа данных, которые они обрабатывают. Например, перестановка двух переменных:
Type x, y, temp;
. . .
temp = x; x = y; y = temp;
будет работать для Type = int, для Type = double и для любого нового типа, определенного в программе с помощью класса. Логика алгоритма одинакова для всех типов данных. Эту ситуацию можно обобщить. Многие алгоритмы допускают отделение метода от данных. Программы, реализующие такие алгоритмы, можно отлаживать для данных одного типа, а затем применять для обработки данных других типов. Функции, реализующие эту возможность, называются параметризованными. Аргументы этих функций определяются с помощью ключевого слова template. Тип, который определяет это ключевое слово, называется шаблоном. Общая форма определения шаблона функции template приведена ниже:
template <class T> прототип функции (аргументы)
{
тело функции;
}
Здесь символ Т обозначает тип данных, используемый функцией, прототип функции состоит из типа возвращаемого значения и имени функции. Например, алгоритм перестановки значений двух аргументов можно реализовать следующим образом:
template <class Tswp> void swap(Tswp& x, Tswp& y)
{
Tswp temp;
temp = x; x = y; y = temp;
}
void main()
{
int a = 1, b = 2;
double c = 1.1, d = 2.2;
swap(a, b); // Перестановка целых чисел
swap(c, d); // Перестановка чисел с плавающей точкой
}
Таким образом, для объявления шаблона функции, функция описывается стандартным образом, но перед ее прототипом ставится ключевое слово template, за которым следует заключенный в угловые скобки список параметров. Каждый из этих параметров определяется с помощью ключевого слова class, за которым следует идентификатор. Идентификатор служит для замещения имени типа. При вызове функции предполагается, что ключевое слово class в контексте шаблонов означает любой тип, а не только класс.
Например, максимум двух значений типа Т можно вычислять с помощью функции:
template <class T> // Ключевое слово и параметр
const T& Max(const T& a, const T& b)
{
return a>b? a:b;
}
void main()
{
int i = 1, j = 2;
float r = 1.1, s = 1.2;
int k = Max(i, j);
float t = Max(r, s);
}
Параметризованные функции могут быть перегружены другими функциями, которые тоже могут быть параметризованы, например:
template <class T> const T& Max(const T&, const T&);
template <class T> const T& Max(const T*, int);
int Max(int, int);
Для определенных типов эти функции могут быть перегружены (и переопределены) для того, чтобы выполнять (или не выполнять) какие-либо действия, которые функции-шаблоны не выполняют (или выполняют), например:
const char* Max(const char* c, const char* d)
{
// Выполнить действия, специфичные для char*
}
Пример. Параметризованная функция бинарного поиска в отсортированном массиве.
#include <iostream.h>
#include <conio.h>
template <class Type>
int binsearch(Type* x, int count, Type key)
{
int low, high, mid; // Левый, правый и средний элементы
low = 0; high = count — 1;
while (low <= high)
{
mid = (low+high)/2; // Вычисление середины массива
if(key < x[mid]) high = mid — 1; // Если нужный элемент
// находится слева от середины
else if(key > x[mid]) low = mid + 1; // Если справа
else return mid; // Нашли
}
return -1; // Не нашли
}
void main()
{
clrscr(); // Очистка экрана
int nums[] = {1, 2, 3, 5, 7, 11, 13, 17}; // Массив, в котором ищем
cout << "5 находится на " << binsearch(nums, 8, 5)
cout << " месте в массиве.";
getch(); // Ожидание нажатия клавиши
}
Результаты работы программы
5 находится на 3 месте в массиве.
Пример. Приведём параметризованную подпрограмму (функцию) сортировки методом пузырьков и применим ее для упорядочения массива, состоящего из целых чисел, записанных в неупакованном BCD – формате. Ниже следует подпрограмма (функция) сортировки и программа тестирования.
#include <iostream.h>
#include <conio.h>
template <class Type>
void bubble (Type *x, int n) // Сортировка методом пузырьков
{
int i, j;
Type t;
for(i = 1; i < n; i++)
for(j = n-1; j >= i; —j)
{
if(x[j-1] > x[j])
{
t = x[j-1]; x[j-1] = x[j]; x[j] = t;
}
}
}
void main()
{
clrscr(); // Очистка экрана
int i;
int nums[] = {10, 12, 11, 3, 5, 12, 10}; // Исходный массив
cout << "Исходный массив: ";
for(i = 0; i < 7; i++) cout << nums[i] << " ";
cout << ‘n';
bubble (nums, 7); // Сортировка
cout << "Отсортированный массив: ";
for(i = 0; i < 7; i++) cout << nums[i] << " ";
getch(); // Ожидание нажатия клавиши
}
Результаты работы программы
Исходный массив: 10 12 11 3 5 12 10
Отсортированный массив: 3 5 10 10 11 12 12
В неупакованном BCD-формате старшим байтом представляется знак, младшая цифра числа записывается как нулевой элемент массива, следующая цифра – первый элемент массива и т.д.
Например, число 123 представляется байтами:
a[0] = ‘3’, a[1] = ‘2’, a[2] = ‘1’, a[n-1] = ‘-’.
Здесь n – количество разрядов числа.
Приведём пример программы для сортировки чисел, представленных в формате BCD. Для этого к параметризированной подпрограмме сортировки добавим определение класса чисел BCD и необходимые операции присваивания и сравнения. Получим следующий текст:
#include <iostream.h>
#include <string.h>
#include <conio.h>
template <class Type>
void bubble (Type *x, int n) // Сортировка методом пузырьков
{
int i, j;
Type t;
for(i = 1; i < n; i++)
for(j = n-1; j >= i; —j)
{
if(x[j-1] > x[j])
{
t = x[j-1]; x[j-1] = x[j]; x[j] = t;
}
}
}
// Класс BCD чисел
class Bcd
{
// Недоступные элементы класса
static int n; // Максимальный размер BCD чисел
char *a; // Массив под BCD число
public:
// Общедоступные элементы класса
// Перегрузка оператора =
void operator = (char *b);
// Перегрузка оператора >
int operator > (Bcd x);
void show(); // Вывод BCD числа на экран
};
// Перегрузка оператора =
void Bcd::operator = (char *b)
{
int i;
a = new char[n]; // Выделение памяти под BCD число
for(i = 0; i < n; i++)
a[i] = ‘0’; // Инициализация его нулями
i = strlen(b); // Определение длины присваиваемого числа
int k = i — 1; // Запоминаем её
// Копирование знака числа
if(b[0] == ‘+’ || b[0] == ‘-‘)
{
i—;
a[n — 1] = b[0];
}
else a[n — 1] = ‘+';
// Копирование самого числа
for(int j = 0; j < i; j++) a[j] = b[k — j];
}
// Перегрузка оператора >
int Bcd::operator > (Bcd x)
{
int i = 0;
// Если первое число положительное,
// а второе — отрицательное, то первое больше
if(this->a[n-1] == ‘+’ && x.a[n-1] == ‘-‘) return 1;
// Если первое число отрицательное,
// а второе — положительное, то первое меньше
if(this->a[n-1] == ‘-‘ && x.a[n-1] == ‘+’) return 0;
// Сравнение по отдельным цифрам
for(i = 1; i < n; i++)
{
if(this->a[n — 1 — i] > x.a[n — 1 — i])
{
if(x.a[n — 1] == ‘+’) return 1;
else return 0;
}
else if(this->a[n — 1 — i] < x.a[n — 1 — i])
{
if(x.a[n — 1] == ‘+’) return 0;
else return 1;
}
}
return 0;
}
// Вывод BCD числа на экран
void Bcd::show()
{
// Создание вспомогательной строки
char *str;
str = new char[n+1]; // Выделение под неё памяти
str[0] = a[n-1]; // Копирование знака
str[n] = ‘ '; // Постановка конечного нуля
// Копирование цифр
int i;
for(i=n-2; i>=0; i—) str[n-i-1] = a[i];
// Вывод строки на экран
cout << str;
delete str; // Освобождение памяти
}
Теперь вызываем параметризованную функцию для сортировки массива Bcd:
int Bcd::n = 15; // Максимальная длина BCD числа
void main()
{
clrscr(); // Очистка экрана
Bcd x[10]; // Создание массива bcd чисел
// Инициализация BCD чисел
x[0] = "1234"; x[1] = "924"; x[2] = "-92"; x[3] = "0";
x[4] = "-1"; x[5] = "10"; x[6] = "12"; x[7] = "1";
x[8] = "-2"; x[9] = "12345";
// Вывод неотсортированного массива
cout << "Неотсортированные BCD числа:n";
for(int i = 0; i < 10; i++)
{
x[i].show();
cout << ‘n';
}
bubble(x, 10); // Сортировка методом пузырьков
// Вывод отсортированного массива
cout << "Отсортированные BCD числа:n";
for(i = 0; i < 10; i++)
{
x[i].show();
cout << ‘n';
}
getch(); // Ожидание нажатия клавиши
}
Результаты работы программы
Неотсортированные BCD числа:
+00000000001234
+00000000000924
-00000000000092
+00000000000000
-00000000000001
+00000000000010
+00000000000012
+00000000000001
-00000000000002
+00000000012345
Отсортированные BCD числа:
-00000000000092
-00000000000002
-00000000000001
+00000000000000
+00000000000001
+00000000000010
+00000000000012
+00000000000924
+00000000001234
+00000000012345
Пример. Рассмотрим параметризованную подпрограмму (функцию) сортировки методом выбора. Сначала находим наименьший элемент массива и переставляем его с первым элементом. Затем из оставшихся элементов находим наименьший и переставляем его со вторым элементом и т.д. Для того чтобы не переставлять элемент сам с собой в том случае, когда он уже является наименьшим среди элементов подмассива, определим переменную exchange, которая будет равна 0, если перестановки не нужны. Получим следующую подпрограмму:
template <class Type>
void select(Type *x, int count)
{
int i, j, k, exchange;
Type t;
for(i=0; i<count-1; i++)
{
exchange=0;
k=i; t=x[i];
for(j=i+1; j<count; j++)
{
if(x[j]<t)
{
k=j; t=x[j]; exchange=1;
}
}
if(exchange)
{
x[k]=x[i]; x[i]=t;
}
}
}
Вызов подпрограммы осуществляется слудующим образом :
int nums[] = {1, 3, 8, -1, 12, -1, 15};
Select(nums, 7);
Пример. Рассмотрим параметризованную функцию быстрой сортировки Хоара. Алгоритм быстрой сортировки опирается на идею разбиения массива на две части с п
оследующим рекурсивным применением подпрограммы сортировки к каждой из этих частей. Перед разбиением выбирается некоторый элемент массива, значение которого называется компарандом.
Все элементы, значения которых меньше компаранда, переносятся в левую часть массива, а элементы, имеющие большее значение – в правую часть. Затем этот же процесс повторяется для каждой из частей. И так до тех пор, пока массив не будет отсортирован. Ниже приведён текст программы.
#include <iostream.h> //библиотека потокового ввода-вывода
#include <conio.h> //библиотека консольного ввода-вывода
//параметризованная функция быстрой сортировки Хоара
template <class Type>
void qs(Type *a, int left, int right)
{
int i, j; //левая и правая границы массива
Type x, y;
i = left; j = right;
x = a[(left+right)/2]; //определим "центр" массива
do
{
//произведём поиск элементов для перестановки
while(a[i]<x && i<right) i++;
while(x<a[j] && j>left) j—;
if(i<=j)
{
//выполняем перестановку
y=a[i]; a[i]=a[j]; a[j]=y;
i++; j—;
}
}
while(i<=j);
if(left<j) qs(a, left, j); //рекурсивный вызов для левой части
if(i<right) qs(a, i, right);//рекурсивный вызов для правой части
}
//основная программа
void main()
{
int i;
int nums[]={5, 10, 12, 3, 8, 9, 2, 1}; //массив чисел для сортировки
clrscr();
cout<<"Входные данные (неотсортированный массив):n";
for(i=0; i<8; i++) cout << nums[i] << " ";
qs(nums, 0, 7); //вызов подпрограммы сортировки
cout<<"nВыходные данные (отсортированный массив):n";
for(i=0; i<8; i++) cout << nums[i] << " ";//вывод результатов на экран
}
Результаты работы программы
Входные данные (неотсортированный массив):
5 10 12 3 8 9 2 1
Выходные данные (отсортированный массив):
1 2 3 5 8 9 10 12