Завдання на практичну роботу
Створити клас List для роботи зі структурою типу "односпрямований список". Тип елементу структури обрати самостійно. Передбачити функції для виконання наступних операцій:
– print() – вивести список на екран;
– isempty() – повернути значення true (тип bool), якщо список порожній.
Таблиця 1.1– Індивідуальні завдання
№ |
Завдання |
1 |
рutinbeg() – створити новий елемент списку у його початку |
2 |
рutinend() – створити новий елемент списку у його кінці |
3 |
getoutbeg() – добути і вилучити перший елемент списку |
4 |
findelem() – пошук заданого елементу за значенням |
5 |
getoutend() – добути і вилучити останній елемент списку |
6 |
insert() – вставити новий вузол після вузла з заданим ключем |
Індивідуальні завдання підвищеної складності
Створити клас List для роботи зі структурою типу "односпрямований список". Тип елементу структури обрати самостійно. Передбачити функції для виконання базових (табл. 1.1) та наступних операцій:
Таблиця 1.2 – Індивідуальні завдання підвищеної складності
№ |
Завдання |
1 |
sort() – відсортувати елементи списку методом вставки |
2 |
sort() – відсортувати елементи списку методом Шелла |
3 |
sort() – відсортувати елементи списку методом бульбашки |
4 |
remove() – видалити зі списку елемент під заданим номером |
Контрольні запитання
1. Що таке динамічна структура?
2. Які наступні характеристики динамічної структури даних можн виділити?
3. Що таке список?
4. Поняття лінійного односпрямованого списку.
5. Основні операції над односпрямованим списком.
Практична робота №2 Лінійні двоСПРЯМОВАНі списки
Мета роботи
Отримати практичні навики організації двоспрямованих (двозв’язних) списків та їх використання при розв’язанні задач.
Основні теоретичні відомості
Динамічний список, у якому кожний елемент (окрім першого і останнього) пов’язаний з попереднім і наступним за ним елементами, називається двозв’язним. Кожний елемент такого списку має два поля з покажчиками: одне поле містить посилання на наступний елемент, інше поле – посилання на попередній елемент і третє поле – інформаційне. Наявність посилання на наступну ланку і на попереднє дозволяє рухатися по списку від кожної ланки у будь-якому напрямку: від ланки до кінця списку або від ланки до початку списку, тому такий список ще називають двоспрямованим. Наприклад, рядок символів BETA представлений двоспрямованим списком:
Рисунок 2.1 – Рядок символів BETA представлений двоспрямованим списком
Перша ланка не має посилання на попередню, остання ланка не має посилання на наступну ланку (рис.2.1).
Рисунок 2.2 – Рядок символів BETA представлений кільцевим (циклічним) списком
Такий список (рис.2.2.) називають кільцевим (циклічним). Тут перша ланка має посилання на останню, а остання ланка – на першу. Тому починати обробку такого списку можна як з першої ланки, так і з останньої.
Основні операції, що виконуються над двозв’язним списком, такі ж, як і для однозв’язного списку. Так як двозв’язний список більш гнучкий, аніж однозв’язний, то при занесенні елемента до списку, можна використовувати покажчик як на елемент, за яким відбувається занесення, так і покажчик на елемент, перед яким відбувається занесення. При видаленні елемента зі списку можна використовувати як покажчик власне на елемент, що буде видалений, так і покажчик на елемент, що передує або йде наступним за елементом, який буде видалений. Але так як елемент двозв’язного списку має два покажчики, то при виконанні операцій вставки/видалення елемента потрібно змінювати більше зв’язків, ніж у однозв’язному списку. Пошук елемента у двозв’язному списку можна проводити таким чином:
– переглядаючи елементи від початку до кінця списку;
– переглядаючи елементи від кінця списку до початку;
– переглядаючи список у обох напрямках одночасно: від початку до середини списку і від кінця до середини (враховуючи те, що елементів у списку може бути парна або непарна кількість).
Приклад. Список складається із вузлів (елементів), що пов’язанні між собою покажчиками. Тому опишемо допоміжний клас для подання одного вузла списку:
class Node
{public:
char d; // дані
Node *next; // покажчик на наступний вузол
Node *prev; // покажчик на попередній вузол
Node (char dat = 0) { d = dat; next = 0; prev = 0;}// конструктор
};
class List2
{ Node *pbeg, *pend; // покажчики на початок та кінець списку
public:
List2() { pbeg = 0; pend = 0;} // конструктор
~List2(); // деструктор
void add(char d); // додавання вузла в кінець списку
void print(); // друк списку в прямому напрямку
};
Розглянемо реалізацію методів класу. Метод add виділяє пам'ять під новий об’єкт типу Node та приєднує його к списку, оновлюючи покажчики на його початок та кінець:
void List2::add(char d)
{ Node *pv = new Node(d); // виділення пам'яті під новий вузол
if(!pbeg) { pbeg = pend = pv; } // перший вузол
else { // зв’язування нового вузла з попереднім:
pv->prev = pend; pend->next = pv;
pend = pv; // оновлення покажчика на кінець списку
}
}
Метод друку списку в прямому напрямку поелементно переглядає список, переходячи по відповідним посиланням:
void List2::print()
{ Node *pv = pbeg;
cout << endl << " list: ";
while(pv) {cout << pv->d << " "; pv = pv->next; }
cout << endl; }
Деструктор списку звільняє пам'ять з-під усіх елементів списку:
List2::~List2()
{ If (pbeg) { Node *pv = pbeg;
while(pv) { pv = pv->next; delete pbeg; pbeg = pv; }}
}
Нижче наведений приклад програми, що використовує клас List2. Програма формує список рядку 'BETA' та друкує його на екран.
void main()
{ List2 l;
l.add('B');
l.add('E');
l.add('T');
l.add('A');
l.print();
getch(); }