Лабораторна робота 7-8
Тема: Шаблони класів. Агрегація шаблонів та успадкування. Динамічні структури даних: списки, дерева.
Контрольні запитання:
Чи може шаблон класу успадковувати звичайний клас? Шаблон класу? А навпаки? Якщо так, то наведіть відповідні приклади.
Чи може шаблон бути параметром типу іншого шаблону? Якщо так, то наведіть приклад.
Нехай визначено шаблон класу Масив. Наведіть приклади створення масиву масивів з елементів деякого вбудованого типу.
Яка структура даних називаються однозв’язним списком? Двозв’язним списком? Проілюструйте схематично.
Переваги списків у порівняння з масивами(векторами).
Запишіть визначення класу (без реалізації методів) однозв’язного списку.
Що таке рекурсивна структура даних? Яким чином така структура даних використовується у списку?
Запишіть реалізації добавлення нового вузла на початок списку, у кінець списку.
Запишіть реалізацію методу виводу елементів списку.
Визначте істинність(хибність) тверджень
The programmer must know in advance how many nodes will be needed in a linked list.
It is not necessary for each node in a linked list to have a self-referential pointer.
In physical memory, the nodes in a linked list may be scattered around.
When the head pointer points to NULL, it signi es an empty list.
Linked lists are not superior to STL vectors.
Deleting a node in a linked list is a simple matter of using the delete operator free the node s memory
A class that builds a linked list should destroy the list in the class destructor.
Знайдіть помилки у методах, що реалізують операції із зв’язним списком:
void NumberList::appendNode(double num){
ListNode *newNode, *nodePtr;
// Allocate a new node & store num
newNode = new listNode;
newNode->value = num;
// If there are no nodes in the list
// make newNode the first node.
if (!head)
head = newNode;
else // Otherwise, insert newNode.
{
// Find the last node in the list.
while (nodePtr->next)
nodePtr = nodePtr->next;
// Insert newNode as the last node.
nodePtr->next = newNode;
}
}
void NumberList::deleteNode(double num)
{
ListNode *nodePtr, *previousNode;
// If the list is empty, do nothing.
if (!head)
return;
// Determine if the first node is the one.
if (head->value == num)
Review Questions and Exercises 1039
delete head;
else
{
// Initialize nodePtr to head of list.
nodePtr = head;
// Skip all nodes whose value member is
// not equal to num.
while (nodePtr->value != num)
{
previousNode = nodePtr;
nodePtr = nodePtr->next;
}
// Link the previous node to the node after
// nodePtr, then delete nodePtr.
previousNode->next = nodePtr->next;
delete nodePtr;
}
}
NumberList::~NumberList()
{
ListNode *nodePtr, *nextNode;
nodePtr = head;
while (nodePtr != NULL)
{
nextNode = nodePtr->next;
nodePtr->next = NULL;
nodePtr = nextNode;
}
}
Означення дерева. Бінарне дерево. Прямий, обернений та симетричний обходи дерева.
Дерево бінарного пошуку.
Алгоритм додавання вузла у дерево бінарного пошуку.
Як знайти найбільший елемент у дереві бінарного пошуку? Найменший? Заданий?
Запишіть визначення класу(шаблону класу) дерева бінарного пошуку.
Зобразіть дерево бінарного пошуку для послідовності чисел 10, 15, 12, 4, 7, 2. Напишіть послідовність вузлів, отриманих при прямому(preorder), оберненому(postorder), симетричному(inorder) обході дерева.
Запишіть реалізацію методу симетричного обходу бінарного дерева.
Визначте істинність(хибність) тверджень
Each node in a binary tree must have at least two children.
When a node is inserted into a tree, it must be inserted as a leaf node.
Values stored in the current node s left subtree are less than the value stored in the current node.
The shape of a binary tree is determined by the order in which values are inserted.
In inorder traversal, the node s data is processed rst, then the left and right nodes are visited.
Завдання 1. Оберіть варіант завдання за рівнем підготовки. Варіанти 1 – 3 для середнього рівня, 4-9 для достатнього рівня.
Варіанти:
Варіант 1-3.
Визначити шаблон класу ForwardList для реалізації однозв’язного лінійного списку. Передбачити наступні функції – елементи:
Додавання елемента у кінець списку
Додавання елемента у початок списку
Видалення заданого елемента
Вставка нового елемента до(після) заданого
Перегляд списку
Очистка списку
Перевірити роботу шаблону класу, створюючи однозв’язні списки для елементів типу int та деякого простого класу(Персона. Студент, Книга чи ін.).
Варіант 4-6.
Визначити шаблон класу List для реалізації двозв’язного лінійного списку. Передбачити наступні функції – елементи:
Додавання елемента у кінець списку
Додавання елемента у початок списку
Видалення заданого елемента
Вставка нового елемента до(після) заданого
Перегляд списку у обох напрямах
Очистка списку
Перевірити роботу шаблону класу, створюючи двозв’язні списки для елементів типу string та деякого простого класу(Персона. Студент, Книга чи ін.).
Варіант 7-9.
Визначити шаблон класу BinTRee для реалізації бінарного дерева пошуку у зв’язному зберіганні. Передбачити наступні функції – елементи:
Додавання елемента у дерево
Перегляд елементів дерева у симетричному порядку
Очистка дерева
Пошук вузла у дереві
Пошук найбільшого(найменшого) вузла у дереві
Перевірити роботу шаблону класу, створюючи бінарні дерева для елементів типу int та деякого простого класу(Персона. Студент, Книга чи ін.).
Завдання 2.
Варіанти:
Визначити шаблон класу Stack, що будується на основі класу, визначеного у завданні 1. Шаблон класу Stack повинен емулювати роботу відповідного класу бібліотеки STL(stack).
Визначити шаблон класу Queue, що будується на основі класу, визначеного у завданні 1. Шаблон класу Queue повинен емулювати роботу відповідного класу бібліотеки STL(queue).
Визначити шаблон класу PriorityQueue, що будується на основі класу, визначеного у завданні 1. Шаблон класу PriorityQueue повинен емулювати роботу відповідного класу бібліотеки STL(priority_queue).
Визначити шаблон класу Deque, що будується на основі класу, визначеного у завданні 1. Шаблон класу Deque повинен емулювати роботу відповідного класу бібліотеки STL(queue)/ ???
Визначити шаблон класу Set, що будується на основі класу BinTRee. Шаблон класу Set повинен емулювати роботу відповідного класу бібліотеки STL(set).
Визначити шаблон класу MultiSet, що будується на основі класу BinTRee. Шаблон класу MultiSet повинен емулювати роботу відповідного класу бібліотеки STL(multiset).
Визначити шаблон класу Map, що будується на основі класу BinTRee. Шаблон класу Map повинен емулювати роботу відповідного класу бібліотеки STL(map).
Визначити шаблон класу MultiMap, що будується на основі класу BinTRee. Шаблон класу MultiMap повинен емулювати роботу відповідного класу бібліотеки STL(multimap).