Завдання на практичну роботу

Створити клас List2 для роботи зі структурою типу "двоспрямований список". Тип елементу структури обрати самостійно. Передбачити функції для виконання наступних операцій:

– print() – вивести список на екран;

– isempty() – повернути значення true (тип bool), якщо список порожній.

Таблиця 2.1 – Індивідуальні завдання

№	Завдання
1	рutinbeg() – створити новий елемент списку у його початку
2	рutinend() – створити новий елемент списку у його кінці
3	getoutbeg() – добути і вилучити перший елемент списку
4	findelem() – пошук заданого елементу за значенням
5	getoutend() – добути і вилучити останній елемент списку
6	insert() – вставити новий вузол після вузла з заданим ключем

Індивідуальні завдання підвищеної складності

Створити клас List2 для роботи зі структурою типу «двоспрямований список». Тип елементу структури обрати самостійно. Передбачити функції для виконання базових (табл. 2.1) та наступних операцій:

Таблиця 2.2 – Індивідуальні завдання підвищеної складності

№	Завдання
1	sort() – відсортувати елементи списку методом вставки
2	sort() – відсортувати елементи списку методом Шелла
3	sort() – відсортувати елементи списку методом бульбашки
4	remove() – видалити зі списку елемент під заданим номером

Контрольні запитання

1. Поняття двоспрямованого списку.

2. Яким чином задається двонспрямований список?

3. Які існують основні операції над двоспрямованим списком?

Практична робота №3 Структури даних стеки і черги

Мета роботи

Сформувати практичні навики організації таких поширених структур як стеки та черги та їх використання при розв’язанні задач.

Основні теоретичні відомості

Стек – це частковий випадок односпрямованого списку, додавання елементів в який та виборка з якого виконуються з одного кінця, називаємого вершиною стека. Взяти елемент можна тільки з вершини стека, додати елемент можна тільки до вершини стека. При виборці елемент видаляється з стеку. Стек реалізує принцип обслуговування LIFO (last in – first out, останнім прийшов – першим пішов).

В динамічній пам’яті стек можна представити лінійним односпрямованим (перший елемент списку – вершина стека) та двоспрямованим списками. Щоб ініціалізувати стек достатньо покажчику на вершину стека задати значення NULL.

Основні операції над стеком: занести елемент у стек; вибрати елемент зі стеку; перевірка на порожність стеку; підрахувати кількість значень, що знаходяться у стеку.

Приклад 1. Програмна реалізація стеку у вигляді лінійного односпрямованого списку.

class Node

{ public:

char d; // дані

Node *next; // покажчик на наступний вузол

Node (char dat = 0) { d = dat; next = 0;} // конструктор

};

class Stack

{Node *top; // покажчик на вершину стека

public:

Stack() { top = 0;} // конструктор

~Stack(); // деструктор

void push(char d); // занесення елементу до стеку

void print(); // друк стеку

};

Розглянемо реалізацію методів класу. Метод push виділяє пам'ять під новий об’єкт типу Node та приєднує його до стеку, оновлюючи покажчики на його вершину:

void Stack::push(char d)

{

Node *pv = new Node(d); // виділення пам'яті під новий вузол

if(!top) { top = pv;} // формування вершини стеку

else // зв’язування нового вузла з попереднім:

{ pv->next= top;

top =pv;} // оновлення покажчика на вершину стеку

}

Метод друку стеку поелементно переглядає стек, переходячи по відповідним посиланням:

void Stack::print()

{ Node *pv = top;

cout << endl << " stack: ";

while(pv) { cout << pv->d << " ";

pv = pv->next; }

cout << endl;

}

Деструктор стеку звільняє пам'ять з-під усіх елементів стеку:

Stack::~Stack()

{ if(top)

{ Node *pv = top;

while(pv) {pv = pv->next;

delete top;

top = pv;}

}

}

Нижче наведений приклад програми, що використовує клас Stack. Програма формує стек рядку 'BETA' та друкує його на екран.

void main()

{

Stack S;

S.push('B');

S.push('E');

S.push('T');

S.push('A');

S.print();

getch();

}

Черга – це частковий випадок односпрямованого списку, додавання елементів в який виконується в один кінець, а виборка – з другого кінця. Розмістити елемент можна тільки в кінець черги, а взяти елемент тільки з її початку. При виборці елемент видаляється з черги. Черга реалізує принцип обслуговування FIFO (first in – first out, першим прийшов – першим пішов).

В динамічній пам’яті чергу можна представити лінійним односпрямованим списком з двома покажчиками (на початок та кінець черги) та двоспрямованим списком. Щоб ініціалізувати чергу достатньо покажчику на початок і/або на кінець черги присвоїти значення NULL. При виборі єдиного елемента з черги вона повинна виявитися порожньою.

Основні операції над чергою аналогічні операціям зі стеком (з урахуванням особливостей структури).

Приклад 2. Програмна реалізація черги у вигляді лінійного односпрямованого списку.

class Node

{public:

char d; // дані

Node *next; // покажчик на наступний вузол

Node (char dat = 0) { d = dat; next = 0;} // конструктор

};

class Queue

{ Node *pbeg, *pend; // покажчики на початок та кінець черги

public:

Queue() {pbeg = 0;} // конструктор

~Queue();// деструктор

void add(char d); // занесення елементу до черги

void print();// друк черги

};

Розглянемо реалізацію методів класу. Метод add виділяє пам'ять під новий об’єкт типу Node та приєднує його до черги, оновлюючи покажчики на її початок та кінець:

void Queue::add(char d)

{

Node *pv = new Node(d); // виділення пам'яті під новий вузол

if(!pbeg) {pbeg = pv; pend = pv;} // формування черги

else // зв’язування нового вузла з попереднім:

{pend->next=pv;

pend = pv;} // оновлення покажчика на кінець черги

}

Метод друку черги поелементно переглядає чергу, переходячи по відповідним посиланням:

void Queue::print()

{ Node *pv = pbeg;

cout << endl << " queue: ";

while(pv) {cout << pv->d << " ";

pv = pv->next; }

cout << endl;

}

Деструктор черги звільняє пам'ять з-під усіх елементів черги:

Queue::~Queue()

{ if(pbeg)

{ Node *pv = pbeg;

while(pv)

{ pv = pv->next;

delete pbeg;

pbeg = pv;

}

}

}

Нижче наведений приклад програми, що використовує клас Queue. Програма формує чергу рядку 'BETA' та друкує його на екран.

void main()

{

Queue Q;

Q.add('B');

Q.add('E');

Q.add('T');

Q.add('A');

Q.print();

getch();

}