Лабораторная работа №19 Шаблоны

Вариант 1. Задание 1 .

Написать функцию-шаблон последовательного поиска в массиве по ключу. Функция возвращает индекс первого, найденного элемента в массиве, равного ключу.

Задание 2.

Создать параметризованный массив с конструкторами, деструктором и перегруженными операторами [], =.

Вариант 2. Задание 1 .

Написать функцию-шаблон, вычисляющую максимальное значение в массиве.

Задание 2

Создать параметризованный стек.

Вариант 3. Задание 1 .

Написать функцию-шаблон, переставляющую элементы в массиве.

Задание 2.

Создать параметризованный массив с конструкторами, деструктором и перегруженными операторами [], =, вывода и ввода в поток.

Вариант 4. Задание 1 .

Написать параметризованную функцию сортировки методом отбора. Сортировка методом отбора заключается в следующем: алгоритм находит элемент с наименьшим значением и выполняет перестановку, меняя его местами с первым элементом массива. После этого из оставшихся n-1 элементов ищется наименьший, после чего осуществляется его перестановка со вторым элементом и так далее. Перестановка будет осуществляться до тех пор, пока не поменяются местами последние два элемента. Например, если бы строка "dcab" сортировалась методом отбора, то каждый из проходов давал бы результат:

Исходный массив	Dcab
Проход 1	Acdb
Проход 2	Abdc
Проход 3	Abcd

Задание 2.

Создать параметризованную очередь.

Вариант 5. Задание 1 .

Написать параметризованную функцию сортировки методом быстрой сортировки. Алгоритм быстрой сортировки построен на основе идеи разбиения массива на разделы. Общая процедура заключается в выборе пограничного значения, называемого компарандом, которое разбивает сортируемый массив на две части. Все элементы, значения которых больше пограничного значения, переносятся в один раздел, а все элементы с меньшими значениями - в другой. Затем это процесс повторяется для каждой из частей и так до тех пор, пока массив не будет отсортирован. Например, допустим, что необходимо отсортировать следующий массив: "fedacb". Если в качестве компарадера использовать "d", то после первого прохода алгоритм быстрой сортировки упорядочит массив следующим образом

Исходный массив	Fedacb
Проход 1	Bcadef

Затем этот подход повторяется для каждого раздела, а именно "bca" И "def".

Проход 2	Acb	Def
Проход 3	Abc	Def

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

Задание 2.

Создать параметризованный стек.

Вариант 6. Задание 1 .

Создать класс типа сигнал, как шаблон, чтобы на его основе реализовать и двухбайтовые данные, собранные с платы сбора данных, так и данные типа float, смоделированные программно. С сигналом определить конструктор по умолчанию, конструктор с параметром, конструктор копирования, деструктор. Переопределить операторы присваивания, [], +=, -=, +, -, *, сохранения в файле.

Задание 2.

Создать параметризованную циклическую очередь.

Вариант 7. Задание 1 .

Написать параметризованную функцию сортировки методом вставки. В методе вставки на первом шаге выполняется сортировка первых двух элементов массива. Далее алгоритм ставит третий элемент в порядковую позицию, соответствующую его положению относительно первых двух элементов. Затем в этот список вставляется четвертый элемент и т.д. Процесс продолжается до тех пор, пока все элементы не будут отсортированы. Например, если бы строка "dcab" сортировалась методом вставки, то каждый из проходов давал бы результат:

Исходный массив	Dcab
Проход 1	Cdab
Проход 2	Acdb
Проход 3	Abcd

Задание 2.

Создать параметризованный связный список с двойными связями.

Вариант 8. Задание 1 .

Создать шаблон функции прореживания: три параметра: откуда выбирать, куда выбирать и через сколько выбирать

Задание 2.

Создать параметризованный стек.

Вариант 9. Задание 1 .

Написать функцию-шаблон, вычисляющую среднее значение в массиве.

Задание 2.

Создать параметризованный класс - матрица. Определены конструкторы, деструктор и перегружены операторы =, [].

Вариант 10. Задание 1 .

Написать функцию-шаблон, вычисляющую максимальное значение в массиве.

Задание 2.

Создать параметризованный стек.

Вариант 11. Задание 1 .

Написать функцию-шаблон, вычисляющую минимальное значение в массиве.

Задание 2

Создать параметризованный массив с конструкторами, деструктором и перегруженными операторами =, -.

Вариант 12. Задание 1 .

Написать родовую функцию в виде функции-шаблон. Функция меняет местами два аргумента.

Задание 2.

Создать параметризованный массив с конструкторами, деструктором и перегруженными операторами + , =.

Вариант 13. Задание 1 .

Написать параметризованную функцию - сортировка методом Шелла. Метод построен на основе метода вставки с минимизацией промежуточных шагов. Рассмотрим таблицу

Проход1	F	D	A	C	B	E
Проход1	C	B	A	F	D	E
Проход1	A	B	C	F	D	E
Результат	A	B	C	D	E	F

Сначала выполняется сортировка элементов, отстоящих друг от друга на три позиции. После этого сортируются элементы, отстоящие друг от друга на две позиции. Наконец, выполняется сортировка смежных элементов. Точная последовательность изменения приращений может изменяться. Единственным требованием остается равенство последнего приращения 1. Например, хорошо себя зарекомендовала последовательность 9, 5, 3, 2, 1, которую и предлагается использовать.

Задание 2.

Создать параметризованный класс бинарного дерева. С методами - добавить элемент в дерево, прохождение по дереву в нисходящем и в восходящем порядке. Осуществить поиск по дереву.

Вариант 14. Задание 1 .

Написать функцию-шаблон бинарного поиска. Если данные, по которым требуется провести поиск, отсортированы, то можно использовать бинарный поиск. Поэтому, первоначально надо написать функцию сортировки (или использовать ту функцию, которую написали в задании №5.1 по практическим занятиям). При использовании бинарного метода на первом шаге проверяется срединный элемент. Если он больше ключа поиска, то проверяется срединный элемент второй половины массива. Эта процедура повторяется до тех пор, пока не будет найдено совпадение, или до тех пор, пока больше не останется элементов, которые можно было бы проверять.

Задание 2.

Создать параметризованный класс односвязного списка.

Параметрический полиморфизм. Шаблоны.

План

1. Шаблон класса

1. Шаблон функций

1. Совпадение сигнатуры и перегрузка

1. Шаблоны классов - Дружественность

1. Шаблоны классов - Статические члены

1. Шаблоны классов - Аргументы шаблона класса

1. Шаблоны классов - Наследование.

1. Исключения

1. Исключения в С++

1. Философия восстановления после ошибок

 

С++ использует ключевое слово template для того, чтобы обеспечить параметрический полиморфизм. Параметрический полиморфизм позволяет одному и тому же коду использоваться относительно различных типов, где тип - параметр тела кода. Параметрический полиморфизм особенно полезен при определении контейнерных классов. Обработка данных в контейнерном классе имеет одну и ту же форму, независимо от типа. Шаблоны определения класса и шаблоны определения функции дают возможность многократно использовать код простым способом, безопасным по отношению к типу, который позволяет компилятору автоматизировать процесс реализации типа. Полиморфизм обеспечивает многократное использование кода.

Шаблон класса

Рассмотри пример реализации шаблона stack

template <class TYPE>

class stack {

enum { EMPTY=-1};

TYPE *s;

int len, top;

public:

stack: len(1000) { s=new TYPE[1000]; top=EMPTY; }

stack(int size): len(size) { s=new TYPE[size]; top=EMPTY; }

~stack() { delete s; }

void reset() { top=EMPTY; }

void push(TYPE c) { s[++top]=c; }

TYPE pop() { return s[top--]; }

TYPE top_of() { return s[top]; }

boolean empty() { return boolean(top==EMPTY); }

boolean full() { return boolean(top==len); }

};

Синтаксис объявления класса предваряется

 

template <class идентификатор>

 

где идентификатор - параметр шаблона, который, по существу, заменяет произвольный тип. Через определение класса аргумент шаблона может использоваться как имя типа. Этот аргумент создается при реализации экземпляра в фактических объявлениях. Вот пример использующего его объявления стека:

 

stack <char> stk_ch; // stack из 1000 элементов char

stack <char *> stk_str(200); // stack из 200 элементов char *

stack <complex> stk_cmplx(100); // stack из 100 элементов complex

 

Этот механизм спасает от трудоемкого переписывания объявлений классов в том случае, когда единственным отличием является объявление типа. Эта схема - альтернатива к использованию void * в качестве универсального типа указателя.

При обработки такого типа код всегда должен содержать угловые скобки в виде части объявления.

// Реверсирование последовательности char * представляемых строками

void reverse(char *str[], int n) {

stack <char *>stk(n);

for(int i=0; i<n; i++) stk.push(str[i]);

for(i=0; i<n; i++) str[i]=stk.pop();

}

// Инициализация стека комплексными числами из массива

void init(complex c[], stack <complex> stk, int n) {

for(int i=0; i<n; i++) stk.push(c[i]);

}

Функции-члены, объявленные и определенные внутри класса, как и ранее, обычно являются inline. При внешнем определении должно использоваться полное объявление в угловых скобках. Так top_of() при определении вне класса шаблона, будет записано как

 

template <class TYPE> TYPE stack<TYPE>::top_of() { return s[top]; }