Void main(). // Формування першого елементу списку

{

// Формування першого елементу списку

Node *pbeg = first(1);

Node *pend = pbeg;

//Додавання в кінець списку чотирьох елементів 2, 3, 4 та 5

for (int i = 2; i<6; i++) add(&pend, i);

// Вставка елементу 200 після елементу 2

insert(pbeg, &pend, 2, 200);

// Видалення елементу 5

if(!remove (&pbeg, &pend, 5)) cout << "не знайдений";

Node *pv = pbeg;

while (pv)

{

// виведення списку на екран

cout << pv->d << " ";

pv = pv->next;

}

}

// Формування першого елементу

Node* first(int d)

{

Node *pv = new Node;

pv->d = d;

pv->next = 0;

pv->prev = 0;

return pv;

}

// Додавання в кінець списку

void add(Node **pend, int d)

{

Node *pv = new Node;

pv->d = d;

pv->next = 0;

pv->prev = *pend;

(*pend)->next = pv;

*pend = pv;

}

// Пошук елементу по ключу

Node* find(Node * const pbeg, int d)

{

Node *pv = pbeg;

while (pv)

{

if(pv->d == d) break;

pv = pv->next;

}

return pv;

}

// Видалення елементу

bool remove(Node **pbeg, Node **pend, int key)

{

if(Node *pkey = find(*pbeg, key)) //1

{

if (pkey == *pbeg)

{ // 2

*pbeg = (*pbeg)->next;

(*pbeg)->prev =0;

}

else if (pkey == *pend)

{// 3

*pend = (*pend)->prev;

(*pend)->next =0;

}

else

{ // 4

(pkey->prev)->next = pkey->next;

(pkey->next)->prev = pkey->prev;

}

delete pkey;

return true; // 5

}

return false; // 6

}

// Вставка елементу

Node *insert (Node* const pbeg,Node **pend,int key,int d)

{

if(Node *pkey = find(pbeg,key))

{

Node *pv = new Node;

pv->d = d;

// 1 - встановлення зв'язку нового вузла з наступним

pv->next = pkey->next;

// 2 - встановлення зв'язку нового вузла з попереднім

pv->prev = pkey;

// 3 - встановлення зв'язку попереднього вузла з новим

pkey->next = pv;

// 4 - встановлення зв'язку наступного вузла з новим

if(pkey!=*pend) (pv->next)->prev = pv;

// Оновлення вказівки на кінець списку

// якщо вузол вставляється в кінець

else *pend = pv;

return pv;

}

return 0;

}

Результат роботи програми:

1 2 200 3 4

Всі параметри, не змінні всередині функцій, повинні передаватися з модифікатором const. Вказівки, які можуть змінитися (наприклад, при видаленні із списку останнього елементу вказівку на кінець списку потрібно скорегувати), передаються за адресою.

Розглянемо докладніше функцію видалення елементу із списку remove. Її параметрами є вказівки на початок і кінець списку і ключ елементу, який треба видалити. У рядку 1 виділяється пам'ять під локальну вказівку ркеу, якій привласнюється результат виконання функції знаходження елементу по ключу find. Ця функція повертає вказівку на елемент у разі успішного пошуку та 0, якщо елементу з таким ключем в списку немає. Якщо ркеу набуває ненульового значення, умова в операторі if стає істинною (елемент існує), і управління передається оператору 2, якщо немає – виконується повернення з функції із значенням false (оператор 6).

Видалення із списку відбувається по-різному залежно від того, знаходиться елемент на початку списку, в середині або в кінці. У операторі 2 перевіряється, чи знаходиться елемент, що видаляється, на початку списку – в цьому випадку слід скорегувати вказівку pbeg на початок списку так, щоб вона вказувала на наступний елемент в списку, адреса якого знаходиться в полі next першого елементу. Новий початковий елемент списку повинен мати в своєму полі вказівку на попередній елемент значення 0.

Якщо елемент, що видаляється, знаходиться в кінці списку (оператор 3), потрібно змістити вказівку pend кінця списку на попередній елемент, адресу якого можна отримати з поля prev останнього елементу. Крім того, потрібно обнулити для нового останнього елементу вказівку на наступний елемент. Якщо видалення походить з середини списку, то єдине, що треба зробити, – забезпечити двобічний зв'язок попереднього і наступного елементів. Після корегування вказівок пам'ять з-під елементу звільняється, і функція повертає значення true.

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

За допомогою шаблонів можна створювати родові функції (generic functions). У родовій функції тип даних, з яким функція працює, задається у якості параметру. Це дозволяє одну й ту ж функцію використовувати з декількома різноманітними типами даних та без необхідності програмувати нову версію функції або класу для кожного конкретного типу даних. Таким чином шаблони дають можливість створювати багатократно використовуємі програми.

Родова функція визначає базовий набір операцій, які будуть застосовуватись до різних типів даних. Родова функція працює з тим же типом даних, який вона отримує у якості параметру. Як відомо, багато алгоритмів логічно однакові, незалежно від того, для обробки яких типів даних вони призначені. Наприклад, алгоритм швидкого сортування однаковий як для масивів цілих, так і для масивів дійсних чисел. Це той випадок, коли данні, що сортуються відрізняються тільки по типам. За допомогою створення родової функції можна незалежно від типу даних визначити сутність алгоритму. Після того як це зроблено, компілятор автоматично генерує правильний код для фактично використовуваного при виконанні функції типу даних. При створенні родової функції – створюється функція, яка може автоматично перевантажуватися сама.

Родова функція створюється за допомогою ключового слова template. Нижче представлено типову форму визначення функції-шаблону:

template <class Фтип> повертаєме_значення ім’я_функції (список параметрів)

{

//тіло функції

}

Тут замість Фтип вказується тип використовуваних функцією даних. Цей тип можна вказувати усередині визначення функції. Однак, він є фіктивним, його компілятор автоматично замінить реальним типом даних при створенні конкретної версії функції.

Наведемо приклад програми в якій створюється родова функція, яка міняє місцями значення двох змінних, що передаються їй в якості параметрів. Оскільки процес обміну двох значень не залежить від типу змінних – його реалізація ефективна за допомогою родової функції.

#include <iostream>

using namespace std;

//Функція-шаблон

template <class A> void swap1(A&x, A&y)

{

A temp;

temp = x;

x = y;

y = temp;

}