Зубенко, Омельчук - Програмування. Поглиблений курс

Розділ IV. АЛГОРИТМИ

Стандартні узагальнені алгоритми. У стандартній бібліотеці ша-

блонів STL визначені узагальнені алгоритми для роботи з контейнер- ними типами (табл. 4.1). Для використання алгоритмів, що не зміню- ють елементів послідовності модифікуючих і сортувальних алгорит- мів, у програму потрібно ввести заголовний файл <algorithm>, а для обчислювальних алгоритмів – заголовний файл <numeric> (табл. 4.2).

Усі алгоритми реалізовані як шаблони функцій (див. підрозд. 3.12) і обробляють вхідну послідовність елементів контейнера, задану парою ітераторів [first, last) (останнім елементом, що обробляється, є last-1). Багато алгоритмів реалізовано в кількох варіантах, для різних наборів параметрів, тому тут наведені лише їхні назви. Деякі з пере- лічених тут алгоритмів уже згадувалися вище.

Таблиця 4.1. Алгоритми, визначені в <algorithm>

521

ПРОГРАМУВАННЯ

522

523

ПРОГРАМУВАННЯ

524

*Література для CР:. динамічні структури даних і алгоритми на них – [8, 60, 65, 77, 95, 124, 125].

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

1.Що таке динамічні структури даних?

2.Що таке зв'язаний список?

3.Як реалізується однозв'язний список?

4.Які основні операції над однозв'язними списками?

5.Як реалізується двозв'язний список?

6.Як реалізуються стеки й операції на них?

7.Як реалізуються черги й операції на них?

8.Яка відмінність між стеком і чергою?

9.Яка відмінність зв'язаного списку від стеку й черги? 10. Як реалізується бінарне дерево?

11. Скільки всього є варіантів обходу бінарного дерева?

12. Що таке контейнер та ітератор?

13. Що таке послідовний контейнерний тип векторів?

14. Що таке послідовний контейнерний тип списків?

15. Що таке послідовний контейнерний тип двосторонніх черг? 16. Що таке асоційовані контейнерні типи відношень і множин? 17. Що таке стандартні узагальнені алгоритми?

18. Написати клас, що реалізує булеву алгебру множин цілих чи- сел з операціями та предикатами: введення-виведення, об'- єднання, перетин, різниця, симетрична різниця, включення, рівність, приналежність елемента множині. Множини подати

увигляді лінійного списку елементів.

525

ПРОГРАМУВАННЯ

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

20.Циклічним називається список, останній елемент якого міс- тить не NULL, а показує на його голову. Реалізувати основні

операції для роботи з такими списками.

21. Написати програму для розв'язання відомої задачі: n солда- тів стали в коло. Із k -го солдата починається рахування. Че- рез p солдатів той, на кого випало, виходить із кола, а раху-

вання починається знову з наступного солдата до тих пір, поки не залишиться останній. Знайти його номер. Застосу- вати циклічний список.

22.Написати програму для перетворення арифметичного вира- зу на форму ОПЗ, застосовуючи стек у вигляді масиву.

23.Реалізувати обчислення арифметичного виразу у формі ОПЗ.

24.Написати програму tail, що друкує n останніх введених ря- дків. За умовчанням n = 5 , але n може бути задано й у ко- мандному рядку. Командний рядок > tail - n викликає друкування останніх n рядків. У кожний момент зберігати в пам'яті не більше n рядків. Застосувати: а) чергу; б) цикліч- ний список у вигляді масивів.

25.Написати функції для роботи із чергами на основі лінійного списку, які здійснюють:

а) заміну k -го вузла в черзі;

б) вилучення k -го вузла із черги; в) конкатенацію кількох черг; г) розбиття черги на кілька черг; д) створення копії черги; е) визначення довжини черги;

є) пошук вузла(ів) черги із заданими властивостями.

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

а) каталог книг у бібліотеці; б) список студентів у групі; в) список товарів у магазині ; г) список клієнтів банку; д) телефонний довідник.

27.Для таблиць із попереднього завдання написати програму на основі двозв'язного списку, що дозволяє додавати й видаля-

526

Розділ IV. АЛГОРИТМИ

ти дані списку, шукати інформацію за ключем, зберігати список у файл і зчитувати його з файла.

28.Для таблиць із вправи 26 написати програму на основі біна- рного дерева пошуку (порядок лексикографічний за ключо- вим полем), що дозволяє додавати й видаляти дані списку, шукати інформацію за ключем, зберігати список у файл і зчитувати його з файла.

29.Для лінійного однозв'язного списку цілих чисел від кожного додатного числа відняти найменше з додатних. Процедуру продовжувати, поки всі елементи списку не стануть від'єм- ними. Зазначити кількість ітерацій у процедурі.

30.Написати функцію, що читає з клавіатури дужковий вираз і перевіряє його на приналежність мові Діка: а) для дужок ( , ); б) для дужок (,),[,],{,}. Використати стек у динамічній пам'яті.

31.Написати функції для роботи із загальними списками з ато- мами-ідентифікаторами: 1) створення й виведення списку;

2)пошуку всіх атомів списку; 3) пошуку частоти входжень усіх атомів у список; 4) усунення й заміни одного атома на інший.

32.Для завдань 18-30 використати відповідні контейнерні типи. Проаналізувати, який із варіантів програми простіший для реалізації й розуміння.

4.4.Динамічні таблиці

¾Таблиці як масиви структур

¾Таблиці у вигляді зв'язаних списків

¾Підвищення ефективності при пошуку в таблицях

¾Пряма адресація

¾Хеш-таблиці з колізіями

¾Відкрите хешування

¾Закрите хешування

¾Таблиці у вигляді дерев пошуку

Ключові слова: таблиця як масив, рядок таблиці, операції з таблицями, до- давання й видалення рядка, пошук рядка, таблиця як зв'язаний список рядків, хеш- таблиця, хеш-функція, таблиця з прямою адресацією, колізія, відкрите й закрите хешування, лінійне хешування.

527

ПРОГРАМУВАННЯ

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

то її рядок можна описати таким чином:

typedef struct student { char *key;

int rate;

float estimationsult; }Student;

Основні операції з таблицями: додавання й видалення рядка, мо- дифікація рядка, пошук рядка за ключем.

Реалізація операцій над таблицями залежить від способу подання таблиць. Розглянемо ці способи.

4.4.1. ТАБЛИЦІ ЯК МАСИВИ СТРУКТУР

Найпростішим є подання таблиць у вигляді динамічних масивів їх- ніх рядків:

Student tableStArray[n];

Приклад 4.26. Таблиця як масив структур:

Лістинг.

#include <stdio.h> #include <stdlib.h> #include <string.h> #include <conio.h>

#int countLine=50;/*задає максимальну кількість рядків у таблиці*/

typedef struct student { char name[10];

int rate;

float estimationsult; }Student;

528

Розділ IV. АЛГОРИТМИ

typedef Student *StudentPtr;

Student tableStArray[countLine];

Student emptyCellArray;

/*ініціалізація інформації про студента*/ Student setEmtySt(Student st)

{

st.estimationsult=0; strcpy(st.name," "); st.rate=0;

return st;

}

/*друкування таблиці*/ void printArrayTable(void)

{

for(int i=0; i<countLine; i++) printf("\n%s\t%f\t%d", tableStArray[i].name,

tableStArray[i].estimationsult, tableStArray[i].rate);

}

/*ініціалізація таблиці*/ void ArrayTableInit(void)

{

emptyCellArray=setEmtySt(emptyCellArray); for(int i=0; i<countLine; i++)

tableStArray[i]=emptyCellArray;

}

/*пошук рядка в таблиці за ключовим полем name; результат – індекс рядка, якщо його знайдено, або countLine, якщо відповідного рядка немає*/

int ArrayTableFind(char key[10])

{

int i=0;

while((i<countLine)&&(strcmp(tableStArray[i].name, key))!=0) i++;

return i;

}

/*перевірка на рівність двох рядків*/ int StructEqual(Student st1, Student st2)

{

if((st1.rate==st2.rate)&&(st1.estimationsult==st2.estimation sult)&&(strcmp(st1.name, st2.name)))

return 1;

529

ПРОГРАМУВАННЯ

else return 0;

}

/*додавання рядка на першу вільну позицію в таблиці*/ void ArrayTableInsert(Student st)

{

int pos=ArrayTableFind(emptyCellArray.name); if(pos==countLine)

printf("\nТаблиця переповнена. Запис не відбув-

ся!!!\n");

else tableStArray[pos]=st;

}

/*видалення рядка за ключем*/

void ArrayTableDelete(char key[10])

{

int pos=ArrayTableFind(key); if(pos==countLine)

printf("Елемент для видалення не знайдено!"); else tableStArray[pos]=emptyCellArray;

}

■

4.4.2. ТАБЛИЦІ У ВИГЛЯДІ ЗВ'ЯЗАНИХ СПИСКІВ

Гнучкішим із погляду модифікації таблиць є їхнє подання у вигляді зв'язаних списків (див. підрозд. 4.3.1). Розглянемо реалізацію основ- них табличних операцій на основі однозв'язного списку.

Приклад 4.27. Таблиця як зв'язаний лінійний список:

#include <stdio.h> #include <stdlib.h> #include <ctype.h> #include <conio.h>

typedef struct item { char name[10];

int rate;

float estimationsult;

struct item *next; /*покажчик на наступний елемент списку*/ } Item;

typedef Item *Itemptr;

/*друкування значень елементів списку, start – голова списку*/ void display(Itemptr start)

530