- •Лабораторна робота № 1
- •Короткі теоретичні відомості
- •Лабораторна робота № 2 Побудова|шикування| рекурсивних функцій
- •Короткі теоретичні відомості
- •Лабораторна робота № 3 Створення|створіння| і обробка масивів
- •Короткі теоретичні відомості
- •Лабораторна робота № 4 Робота з рядками|
- •Лабораторна робота № 5 Робота з|із| абстрактними типами даних(атд|): struct, union, enum
- •Короткі теоретичні відомості
- •Лабораторна робота № 6
- •Короткі теоретичні відомості Клас.
- •Приклади|зразки|.
- •Приклад|зразок|.
- •Список літератури Основна
- •Допоміжна
- •Деякі функції роботи з рядками із файлу string.H
- •39614, М. Кременчук, вул. Першотравнева, 20
Лабораторна робота № 5 Робота з|із| абстрактними типами даних(атд|): struct, union, enum
Мета. Отримати тримати практичні навички навички побудови та застосування абстрактних типів даних на С++
Короткі теоретичні відомості
Структура використовується для об'єднання різнотипних даних в одиночну іменовану змінну. Компоненти структури мають індивідуальні імена.
Загальний|спільний| синтаксис визначення структурного типу даних (шаблону АТД|):
struct таг _ структури
{
список членів структури, які можуть мати будь-який стандартний або абстрактний тип даних
};
В описі обов'язковий оператор «;» після|потім| «}». Далі як тип виступає|вирушає| таг_структури, тобто, щоб оголосити змінну, яка має організацію даних як шаблон структури, необхідно написати:
таг_структури ідентифікатор;
або таг_структури* ідентифікатор;
, якщо змінна повинна містити|утримувати| адресу змінної структурного типа.
Звернення до членів структури відбувається|походить| по імені, яке складається з імені змінно структурного типа і імені члена з|із| шаблону структури.
Приклад. Задати масив структур, кожна з яких містить|утримує| поля: ім’я_клієнта і сума_виплат.
# include < iostream. h>
void main ()
{ struct client {
char name 15;
int sum;
} ; // визначення структурного типу client
client mas 10; //виділення пам’яті під 10 елементів типу client
int i, num; // кількість осіб
cin >> num;
for (i = 0; i < num; i++)
{ cout << \ n введіть і’мя
cin >> mas i.name; //звернення до поля name
cout << “ сумму виплат”;
cin >> mas i.sum; //звернення до поля sum
} }
З|із| прикладу|зразка| видно|показно|, що для звернення до члена структури використовується оператор . (прямого доступу до членів абстрактного типу даних).
Якщо змінна є|з'являється,являється| покажчиком на структуру (містить|утримує| адресу структури), то до члена структури можна звернутися|обернутися| за допомогою оператора непрямого доступу до члена структури
Покажчик_на_структуру –> ім’я_члена_структури
або за допомогою оператора прямого доступу з використанням оператора переходу за адресою «*»:
|(*Покажчик_на_структуру). ім’я_члена_структури
Організація даних у формі списку дозволяє зберігати елементи списку в різних|перебувають| ділянках пам'яті, які, на відміну від масивів, не |поруч| знаходяться поряд. Для створення|створіння| елементу списку використовується структурний тип даних. При цьому одним з членів структури є|з'являється,являється| покажчик на створений структурний тип. Фактично цей покажчик містить|утримує| адресу |наступного| або попереднього елементу списку.
Приклад. Написати програму створення|створіння|, перегляду|проглядання| і видалення|віддалення| елементів списку, організованого за принципом LIFO(«last input, first output» – «останній прийшов,- перший пішов»).
#include <iostream.h>
#include <process.h>
#include <conio.h>
//визначення перелічуваного типу користувача boolean
enum boolean{true, false};
//визначення шаблону елемента списку за допомогою типу struct
struct stack{
char s;
stack* p;
};
//оператор typedef дозволяє створити тип користувача Stk, який є
//аналогом стандартного типу stack*
typedef stack* Stk;
Stk stk;
//функція reset() повертає порожній покажчик(адресу) вершини стеку,
//тобто відбувається “скидання” стеку
Stk reset()
{
return NULL;
}
//функція push(char c, Stk top) заносить символ с, що введено, на вершину //стеку, утворюючі новий елемент списку типу stack и повертає його //адресу як адресу першого елементу в списку
Stk push(char c, Stk top)
{ stk=new stack;
if(stk==NULL){ cout<<"\n Помилка при розподілі пам’яті";
exit(1);}
stk->s=c;
if(top!=NULL) stk->p=top;
return stk;
}
/*функція pop( Stk top) виштовхує елемент вершини, видає символ , що зберігається в вершині, на екран, замінює адресу попередньої вершини адресою вершини, що йде за нею, а місце, що було розподілене під попередню вершину звільняється (повертається до “купи” вільної пам’яті)*/
Stk pop( Stk top)
{ cout<<top->s;
stk=top;
top=top->p;
delete stk;
return top->p;
}
//функція empty( const Stk top) перевіряє, чи є стек порожнім, повертає
// константу false, якщо це так
boolean empty( const Stk top)
{ return (boolean)(top==NULL);
}
void main()
{ clrscr();
Stk top;
char str[]="fghg hfgt dtdt dtyd dtyf";
int i=0;
cout<<str<<endl;
top=reset();
while(str[i])
top=push(str[i++],top);
while(!empty(top))
top=pop(top);
getch();
}
Об'єднання (union) – це похідний тип від типу struct. Синтаксис визначення об’єднання такий же, як і у|в,біля| структур, за винятком того, що ключове|джерельне| слово union замінюється struct. Ці типи відмінні|розрізняти| за способом зберігання членів АТД|. Члени об'єднання сумісно| використовують пам'ять, тобто їх значення перекриваються. При цьому під об'єднання виділяється об'єм|обсяг| пам'яті, достатній для зберігання найбільшого члена об'єднання. Члени структур зберігаються подібно до масивів (послідовно у вигляді лінійної структури відповідно до їх оголошення усередині шаблону структури).
Ключове|джерельне| слово| enum використовується для оголошення особливого типу з|із| набором іменованих цілих констант, званих константами перелічуваного типу, або константами переліку|перерахування| (enumerators). Перелічуваний тип даних, має структуру оголошення таку ж, як struct, або union. Перелічувані константи за умовчанням нумеруються значеннями, починаючи|розпочинаючи,зачинаючи| з|із| нуля. Допускається явне призначення|присвоєння| цілого значення в перелічуваному наборі|перерахування| у вигляді|виді|: перелічувана_константа=значення.
Завдання до лабораторної роботи №5
Вивчити правила створення абстрактних типів даних(АТД) на прикладі програм, що розглянуті в п.п. «Короткі теоретичні відомості» та «Приклад виконання лабораторної роботи №5». Перевірити роботу наведених програм.
Пояснити основні принципи організації даних за допомогою списків. Модифікувати програму, яку наведено в п. «Приклад виконання лабораторної роботи №5», замінивши організацію списку LIFO на FIFO та навпаки.
|задачі|Написати програму, що дозволяє вирішити поставлену в індивідуальному завданні задачу з застосуванням АТД..
Приклад виконання лабораторної роботи №5
Постановка задачі. В базу даних заносяться дані про клієнтів фірми, а саме: прізвище клієнта та номер його ідентифікаційного коду. З метою більш ефективного використання пам’яті дані заносяться у вигляді списку, який має деревоподібну структуру: стовбур даного списку представляє собою список – каталог, який містить початкові букви прізвищ, кожна з гилок такого дерева представляє список структур даних, що мають однакову першу букву в прізвищі клієнта. Необхідно написати програму, яка б дозволяла організувати такий деревоподібний список даних, кількість яких заздалегідь невідома, а також вивести дані, що каталогізовано, на екран.
Приклад організації даних. Кожна з гилок деревоподібного списку сама по собі є списком, кожен вузол якого містить прізвище, номер ідентифікаційного коду, адресу сусіднього(попереднього або наступного) елемента списку. В даному випадку обираємо організацію FIFO, тобто кожен вузол містить адресу наступного елементу. Структуру, що описує такий список, наведено нижче:
struct list
{ char* surname;
char* id_cod;
list* next;
};
Тепер опишемо структуру каталогу. Він може бути представлений списком, кожен вузол якого містить наступні поля: першу букву прізвища, адресу першого елементу відповідного списку даних, адресу попереднього (або наступного) елемента списку - каталогу. Оскільки умови задачі не обмежують тип списку, обираємо організацію LIFO, тобто кожен вузол міститиме адресу попереднього елементу каталогу. Таким чином, список-каталог може бути описано:
struct katalog
{
char bukva;
list* first;
katalog* prev;
};
Приклад розподілу пам’яті під елементи списку.
Розподіл пам’яті організуємо у вигляді двох функцій: add_kat() - дозволяє додавати до списку нові елементи каталогу, add_list() – дозволяє додавати вузли списків прізвищ та відповідних номерів ідентифікаційних кодів.
//функція додавання нових букв до списку - каталогу
katalog* add_kat(katalog* head, char c)
//head – голова існуючого списку, c – параметр, що містить букву, яка //додаєтьсядо списку - каталогу
{katalog* temp=new katalog; //розподілити пам’ять під новий вузол списку, //адресу занести в змінну temp
if(!temp) { cout<<"\n Error of memory";
exit(1);//якщо пам’ять не розподілено – завершити виконання //програми
}
temp->bukva=c; //занести значення змінної c у відповідне поле bukva //структури temp
temp->first=NULL; //спочатку присвоїти покажчику на перший елемент // списку прізвищ нульове значення
temp->prev=head;//зв’язати новий вузол списку з вже існуючими. Для
//цього у поле prev змінної temp занести адресу попередньої голови списку
return temp; //новий вузол списку стає його головою, оператор return
// повертає адресу нової голови списку - каталогу
}
//функція додавання даних до списку прізвищ
list* add_list(char* surn, char* idc, list* first)
{ list* temp;
if (!first) {first=new list; temp=first;} //якщо покажчик first нульовий,
// розподілити пам'ять під перший елемент списку прізвищ, занести його
//адресу в змінні first та temp. В цьому випадку список прізвищ буде //представлено одним елементом
else //інакше
{ list* new_list=new list; //розподілити пам'ять під новий вузол списку
//прізвищ
temp=first; //адресу першого елемента занести в змінну temp
while (temp->next) temp=temp->next; //поступово перейти до останнього
//елементу існуючого списку
temp->next=new_list; //в поле next останнього елементу існуючого
//списку прізвищ занести адресу нового вузла списку. Це дозволяє //прив’язати новий вузол до всього списку
temp=new_list; //в змінну temp занести адресу нового елементу списку
}
temp->next=NULL;//покажчик на наступний елемент в новому вузлі //дорівнює нулю
temp->surname=new char[strlen(surn)+1]; //розподілити пам'ять під //прізвище
strcpy(temp->surname, surn); //записати прізвище у поле surname
temp->id_cod=new char[strlen(idc)+1]; //розподілити пам'ять під ід. код
strcpy(temp->id_cod, idc); //записати номер ід.коду в поле id_cod
return first; //повернути адресу першого елементу даного списку прізвищ
}
Приклад виводу на екран всіх даних зі списку.
Вивід даних організовано за допомогою функції print():
void print(katalog* head)
{ katalog* temp=head;
list* ptr;
while (temp) //поки покажчик на структуру catalog – вузол списку – //каталогу не нульовий
{ptr=temp->first;//в змінну ptr занести адресу першого вузла поточного //списку прізвищ – гилки дерева
cout<<"\n\n char "<<temp->bukva; //вивести першу букву прізвища. Саме //з неї починаються всі прізвища поточного списку
while (ptr) //поки покажчик ptr на поточний елемент списку прізвищ
//ненульовий
{cout<<"\n"<<ptr->surname<<"\t"<<ptr->id_cod; //вивести дані
ptr=ptr->next; //перейти до наступного вузла списку прізвищ
}
temp=temp->prev; // перейти до наступного вузла списку - каталогу
}
}
Приклад основної програми, що дозволяє організувати занесення даних та сформувати список – каталог та списки прізвищ.
#include <iostream.h>
#include <conio.h>
#include <string.h>
#include <process.h>
struct list
{ char* surname;
char* id_cod;
list* next;
};
struct katalog
{
char bukva;
list* first;
katalog* prev;
};
katalog* add_kat(katalog*,char);
list* add_list(char*,char*,list*);
void print(katalog*);
void main()
{clrscr();
char ans='y',bukv;
katalog* head=NULL, *kat_ptr;
list* ptr;
char Surn[20], Idc[20];
do
{cout<<"\n input data? "; //запит на введення даних
cin>>ans ;
if (ans=='n') cout<<"\nend of input";
else
{
cin.ignore(1);
cout<<"\ninput surname\t";
cin.getline(Surn,20); //занесення прізвища
cout<<"\ninput ID_Cod\t";
cin.getline(Idc,20); //занесення ідент. коду
kat_ptr=head; ptr=NULL;
while (kat_ptr)
{ if (kat_ptr->bukva==Surn[0]) {ptr=kat_ptr->first; break;}
kat_ptr=kat_ptr->prev;
} //пошук першої букви занесеного прізвища в списку – каталозі
//Якщо букву знайдено – адреса першого елементу відповідного списку //прізвищ заноситься в змінну ptr
if (ptr) add_list(Surn,Idc,ptr); //і додається новий вузол до списку прізвищ //з введеними даними
else //якщо букву не знайдено в списку - каталозі
{head=add_kat(head,Surn[0]); //додається новий елемент в список –
// каталог, head - голова оновленого списку
head->first=add_list(Surn,Idc,NULL); //формується новий список //прізвищ, котрий містить один вузол. Адреса цього вузла заноситься в //змінну head->first
}
}
}
while(ans!='n');
print(head);
getch();
}
За головною програмою необхідно розмістити функції add_kat(katalog*,char), add_list(char*,char*,list*) і print(katalog*), прототипи яких наведено в головній програмі, а визначення наведені в попередніх прикладах.
Зміст|вміст,утримання| звіту до лабораторної роботи №5
Титульний лист|аркуш|: назва дисципліни; номер і найменування роботи; прізвище, ім'я, по батькові студента; дата виконання.
Постановка завдання|задачі|. Слід дати конкретну постановку, тобто вказати, який АТД повинен бути реалізований, які під задачі повинні вирішуватись
Визначення основних змінних та функцій з|із| коментарями.
Реалізація функцій.
Лістинг основної програми, в якому повинно бути вказано, в якому місці і яка функція викликається|спричиняються|.
Варіанти завдань до лабораторної роботи №5
Примітка|тлумачення|. У варіантах завдань|задавань| на розробку баз даних передбачити файлову організацію і зберігання даних.
Організувати однозв'язний список для зберігання цілих чисел, кількість змінних наперед|заздалегідь| невідома. Написати функції пошуку елементу в списку і його видалення|віддалення|.
Написати програму організації зв'язного списку, в якому всі елементи розташовуються у порядку|ладі| зростання (використовувати вставку елементу на своє місце в списку).
Написати програму організації зв'язного списку за наступною|слідуючою| ознакою: якщо введений|запроваджений| символ - буква|літера|, то в кінці|у кінці,наприкінці| списку додається|добавляється| вузол, який містить|утримує| символ, інакше вузол додається|добавляється| в початок списку і містить|утримує| цифру.
Написати програму створення|створіння| двозв'язного списку (кожен вузол містить|утримує| два покажчики: на подальший|наступний| елемент і на попередній). Елементами списку є|з'являються,являються| рядкові змінні. Відсортувати елементи в списку по довжині рядків.
Написати програму створення|створіння| двозв'язного замкнутого списку (покажчик на наступний|такий| елемент в останньому вузлі списку повинен указувати|вказувати| на перший елемент, а покажчик на попередній елемент списку першого вузла повинен указувати|вказувати| на останній створений елемент ). Видалення|віддалення| вузлів списку організувати за наступним|слідуючим| правилом: видаляється кожен другий елемент| списку до тих пір, поки це можливо буде виконувати (у результаті список складатиметься тільки|лише| з одного елементу). Тип величин, що зберігаються у вузлах списку, вибрати самостійно.
Організувати двозв'язний список за принципом FIFO і видати на екран всі елементи списку, починаючи|розпочинаючи,зачинаючи| з|із| середнього, рухаючись|сунучись| одночасно в обидва напрями|направлення| за списком.
Організувати зв'язний список, кожен елемент якого має поле пріоритету. Дані витягуються із|із| списку відповідно до пріоритету.
Організувати двозв'язний список за принципом LIFO. Усередині елементу списку зберігається рядок довільних символів і ціле значення, яке рівне числу букв|літер| в рядку, що зберігається . Відсортувати елементи списку лінійним сортуванням у порядку|ладі| збільшення цілого, що зберігається (міняти|змінювати,замінювати| місцями значення, що зберігаються, а не самі вузли списку).
Створити чотирьохзв'язний список по топології тора. Реалізувати механізм пошуку в даній структурі.
Заданий список слів довільної організації. Написати програму сортування слів за абеткою|по алфавіту| і по довжині.
Написати програму створення|створіння| і обробки списку довільних даних за принципом: поточний елемент посилається на попередній і на наступний|слідуючий| елементи.
Створити список довільної організації, усередині елементів якого повинно зберігається значення будь-якого з типів {char char*, int int*} і можливо зберігання інших значень (вибір самостійний). Необхідно у файл вивести спочатку елемнты| списку типу char, |із| потім – char*, int, int*.
Створити замкнутий двозв'язний список, в якому парні (по номеру надходження|вступу| ) елементи заносяться | в кінець списку, а непарні – в початок.
Створити трьохзв'язний список, у|в,біля| якого перший покажчик|заслання| вказує на попередній елемент, другий – на елемент, який розташований|схильний| через один елемент від фіксованого, третій - на елемент, який розташований|схильний| через два елементи від фіксованих. Визначити функцію видалення|віддалення| довільного елементу списку. Тип значень, що зберігаються, в|із| області даних, вибрати самостійно.
Створити список довільної організації (вибір пояснити на захисті), у вузлах якого зберігаються два рядки. Необхідно для цього списку визначити функцію сортування (метод бульбашки) елементів списку у порядку|ладі| зменшення сумарної кількості цифр в рядках, що зберігаються.
Для замкнутого двозв'язного списку реалізувати швидке сортування “за збільшенням елементів” списку (ознаку впорядкування вибрати самостійно).
Написати програму для створення|створіння| і зберігання трирівневого генеалогічного|родовідного| дерева і відображення по запиту користувача всіх або одного рівня.
Написати програму для створення|створіння| і зберігання бінарного довідника. Реалізувати функції: додавання|добавки| або видалення|віддалення| вершини дерева або піддерева|.
Написати програму для створення|створіння| і зберігання двійково-трійкового дерева. Реалізувати функції: додавання|добавки| або видалення|віддалення| вершини дерева або піддерева|.
Створити список довільної організації. Областю даних кожного елементу є|з'являється,являється| рядок, який містить|утримує| назву геометричної фігури, і площу|майдан| цій фігурі. Відсортувати всі елементи списку у порядку|ладі| убування по назвах фігур (довжині рядка) і потім|і тоді| у порядку|ладі| зростання по величині займаної|позичати,посідати| площі|майдану| (маються на увазі однойменні фігури).
Написати програму, яка дозволить створити базу даних “Бібліотека” з|із| полями “Назва книги”, “Автор”, “Рік видання”, “Наявність на даний момент”. Організувати пошук по ключу|джерелу|, вставку даних і видалення|віддалення|.
Написати програму, яка дозволить створити наступну|слідуючу| базу даних про рух автобусів:
-
№ маршруту
Час відправлення
Місце призначення
час.
хв.
Вивести всі номери рейсів, що відправляються|вирушають| в місто N до полудня.
Представити|уявити| час у вигляді структури даних, що складається з трьох полів: годинник (112); хвилини (160); половина доби (АМ| або PМ). Реалізувати операцію складання часів (враховувати зміну доби).
Представити|уявити| комплексні числа у вигляді структури даних. Реалізувати складання і множення комплексних чисел і результат вивести на екран в стандартному вигляді|виді|.
Торгова|торгівельна| фірма виплачує продавцям комісійну винагороду у розмірі 5%, якщо товар продано на суму менше 1000 грв|. і 6%, якщо виручка складає 1000 грв|. і вище. Продавці, що пропрацювали у фірмі більше 10 років, одержують|отримують| комісійні на 1% більше. Видати на екран всі вхідні дані (ФІО продавця, час його роботи у фірмі, загальну|спільна| суму виручки), комісійні по кожному продавцю, загальні|спільні| підсумки по сумі виручки і загальну|спільну| суму комісійної винагороди.
Створити наступну|слідуючу| базу даних про співробітників відділу: ФІО (складається з трьох полів), дата народження (складається з трьох полів) і сімейний стан (union). Вивести на екран відомості по всіх співробітниках, які мають сім'ю і народилися до 1979 року.
Фірма “ALL FOR YOU”, що забезпечує водопостачанням населення встановила наступні|слідуючі| розміри платні|плати| за воду: 0.004$ за літр для перших 100 літрів і 0.003$ - за кожен подальший|наступний| літр. Вхідна інформація: ФІО споживача; попередні показання |показник,показання| лічильника|; нові дані|показник,показання| лічильника|. Вихідна інформація: спожита кількість води, розмір платні|плати| за першим і другим тарифами, загальна|спільна| платня|плата|. Написати програму, що забезпечує обробку даних по декількох споживачах.
Написати програму для створення|створіння| і зберігання трирівневого генеалогічного|родовідного| дерева і відображення по запиту користувача всіх або одного рівня.
Написати програму для створення|створіння| і зберігання бінарного довідника. Реалізувати функції: додавання|добавки| або видалення|віддалення| вершини дерева або піддерева|.
Написати програму для створення|створіння| і зберігання двійково-трійкового дерева. Реалізувати функції: додавання|добавки| або видалення|віддалення| вершини дерева або піддерева|.