Methods_AP_LABS_II

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*), прототипи яких наведено у головній програмі, а визначення наведено у попередніх прикладах.

7.3 Практичні завдання

Примітка. У варіантах завдань на розробку баз даних передбачити файлову організацію і зберігання даних.

1.Організувати однозв'язний список для зберігання цілих чисел,

кількість змінних наперед невідома. Написати функції пошуку елемента у списку і його видалення.

2.Написати програму організації зв'язного списку, в якому всі елементи розташовують у порядку зростання (використовувати вставку елемента на своє місце у списку).

3.Написати програму організації зв'язного списку за наступною ознакою:

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

4.Написати програму створення двозв'язного списку (кожний вузол містить два покажчики: на подальший елемент і на попередній). Елементами

списку є рядкові змінні. Відсортувати елементи в списку за довжиною

рядків.

5.Написати програму створення двозв'язного замкнутого списку (покажчик на наступний елемент в останньому вузлі списку має вказувати на перший елемент, а покажчик на попередній елемент списку першого вузла має вказувати на останній створений елемент). Видалення вузлів списку організувати за наступним правилом: видаляють кожний другий елемент списку доти, поки це можливо буде виконувати (у результаті список складатиметься тільки з одного елемента). Тип величин, що зберігаються у вузлах списку, вибрати самостійно.

6.Організувати двозв'язний список за принципом FIFO і видати на екран усі елементи списку, починаючи з середнього, рухаючись одночасно в обох напрямках за списком.

7.Організувати зв'язний список, кожний елемент якого має поле пріоритету.

Дані витягують зі списку відповідно до пріоритету.

8. Організувати двозв'язний список за принципом LIFO. Усередині елемента списку зберігається рядок довільних символів і ціле значення,

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

9.Створити чотиризв'язний список з топології тора. Реалізувати механізм пошуку в даній структурі.

10.Заданио список слів довільної організації. Написати програму сортування слів за абеткою і за довжиною.

11.Написати програму створення і оброблення списку довільних даних за принципом: поточний елемент посилається на попередній і на наступний елементи.

12.Створити список довільної організації, всередині елементів якого має зберігається значення будь-якого з типів {char char*, int int*} і можливо

зберігання інших значень (вибір самостійний). Необхідно до файла

вивести спочатку елементи списку типу char, потім – char*, int, int*.

13.Створити замкнутий двозв'язний список, в якому парні (за номером надходження) елементи заносять в кінець списку, а непарні – в початок.

14.Створити тризв'язний список, у якого перший покажчик вказує на попередній елемент, другий – на елемент, який розташовано через один елемент від фіксованого, третій на елемент, який розташовано через два елементи від фіксованих. Визначити функцію видалення довільного елемента списку. Тип значень, що зберігаються в області даних, вибрати самостійно.

15.Створити список довільної організації (вибір пояснити на захисті), у

вузлах якого зберігаються два рядки. Необхідно для цього списку визначити функцію сортування („метод бульбашки”) елементів списку у порядку зменшення сумарної кількості цифр у рядках, що зберігаються.

16.Для замкнутого двозв'язного списку реалізувати швидке сортування “за збільшенням елементів” списку (ознаку впорядкування вибрати самостійно).

17.Написати програму для створення і зберігання трирівневого генеалогічного дерева і відображення за запитом користувача всіх або одного рівня.

18.Написати програму для створення і зберігання бінарного довідника.

Реалізувати функції: додавання або видалення вершини дерева або

піддерева.

19.Написати програму для створення і зберігання двійково-трійкового дерева. Реалізувати функції: додавання або видалення вершини дерева або піддерева.

20.Створити список довільної організації. Областю даних кожного елемента

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

Відсортувати всі елементи списку у порядку спадання за назвами фігур

(довжиною рядка) і потім у порядку зростання за величиною займаної площі (мають на увазі однойменні фігури).

Вихідна інформація: спожита кількість води, розмір платні за першим і другим тарифами, загальна платня. Написати програму, що забезпечує оброблення даних щодо декількох споживачів.

28.Написати програму для створення і зберігання трирівневого генеалогічного дерева і відображення за запитом користувача всіх або одного рівня.

29.Написати програму для створення і зберігання бінарного довідника.

Реалізувати функції: додавання або видалення вершини дерева або

піддерева.

30.Написати програму для створення і зберігання двійково-трійкового дерева. Реалізувати функції: додавання або видалення вершини дерева або піддерева.

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

1.Описати синтаксис визначення структур.

2.Описати синтаксис визначення об’єднань.

3.Яка різниця між структурами та об’єднаннями?

4.Яке призначення типів користувачів?

7.5Порядок виконання лабораторної роботи

1.Вивчити правила створення абстрактних типів даних(АТД) на прикладі програм, що розглянуто в рр. 7.1 та 7.2. Перевірити роботу наведених програм.

2.Пояснити основні принципи організації даних за допомогою списків. Модифікувати програму, яку наведено у р. 7.2, замінивши організацію списку LIFO на FIFO та навпаки.

3.Написати програму, що дозволяє розв’язати поставлену в індивідуальному завданні задачу (розділ 7.3) із застосуванням АТД.

4.Відповісти на питання розділу 7.4.

5.Виконати 3 завдання з розділу 7 [13] на вибір викладача.

Лабораторна робота №8. Робота з рядками в C++.

Мета роботи: ознайомитися з методами роботи з рядками та навчитися використовувати їх для написання програм мовою C++.

8.1. Теоретичні відомості

Символьна константа складається з одного символа ASCII між

Стринги є одним з найбільш корисних та важливих типів даних мови С.

Символьний рядок (стринг) — це масив символів, замкнений у лапки ("). Він має тип char. Нульовий символ (\0) автоматично додається останнім байтом символьного рядка та виконує роль ознаки його кінця. Кількість елементів у масиві дорівнює кількості символів у стрингу плюс один,

оскільки нульовий символ також є елементом масива. Кожна стрингова константа, навіть у випадку, коли вона ідентична іншій стринговій константі,

зберігається у окремому місці пам'яті. Якщо необхідно ввести у рядок символ лапок ("), то перед ним треба поставити символ зворотного слешу

(\). У стринг можуть бути введені будь-які спеціальні символьні константи,

перед якими стоїть символ \.

Прототипи всіх функцій, що працюють з рядками символів, містяться у файлі string.h. Всі функції працюють з рядками, що закінчуються нульовим символом. Ось деякі з них:

int strcat( char *, char *) — з'єднати два стринги;

int strcpy(char *s1, char *s2) — копіювати рядок s2 у

рядок s1;

int strlen(char *s) — визначити довжину рядку (кількість символів без нульового символа).

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

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

memcpy() — копіювання символів з одного буфера у другий, поки не буде скопійований заданий символ або не буде скопійовано визначену кількість символів

memcmp() — порівнює вказану кількість символів з двох буферів

У файлі ctype.h описано прототипи функцій, що призначені для перевірки літер. Ці функції повертають ненульове значення (істина), коли її аргумент задовольняє заданій умові або належить вказаному класу літер, та нуль в іншому випадку. Наприклад:

int islower(int с) — символ с є малою літерою; int isupper(int c) — символ с є великою літерою; int isalnum(int c) — символ с є буквою або цифрою; int isalpha(int c) — символ с є буквою;

int tolower(int c) — перетворення літери у нижній регістр; int strtol(int c) — перетворення стрингу у довге ціле число.

Лістинг 8.1. Обчислити вираз з дужками, десятковими цифрами та знаками +, -, *, /.

#include <ctype.h>

#include <math.h>

isdig(char c) {return ((isdigit(c)) || 'с'=='.');}

double val(char **);

double getdig(char ** s)

{

double res;

if(**s=='(') res=val(++*s);

else {res=atof(*s); while(isdig(*++*s));}; return res;

}

double multi(char** s)

{

double res=getdig(s); while((**s=='*') || (**s=='/')) if(**s=='*') res*=getdig(++*s); else res/=getdig(++*s);

}

double val(char** s)

{

double res=multi(s); while((**s!=')') && (**s!='\0')) if(**s=='+') res+=multi(++*s); else res-=*(++*s);

if(**s==')') ++*s; return res;

}

double getsvalue(char* s) {char** l; *l=s; return val(l);}

main()

{

char* s="2-4/2+25/(2+3)/5+(-1)*(2*4/8-2)*(-1)+5"; cout << getsvalue(s);

}

Для роботи із символьними даними розроблений ряд бібліотечних функцій. Розглянемо деякі з них:

Функція char *strchr(const char *s, int c); - переглядає рядок у прямому напрямку для відшукання в ньому заданого символу.

Функція strchr() шукає перше входження символу с у рядок s. Символ кінця рядка вважається частиною рядка, тому - strchr(strs, 0) поверне значення покажчика на нульовий кінцевий символ рядка strs. Функція strchr() повертає покажчик на перше входження символу с в s, якщо c не виявлений у s, то strchr() повертає нуль.

int strcmp(const char *s1, const char *s2); - здійснює беззнакове порівняння рядків s1 і s2, починаючи з першого символу кожного рядка, доти, поки чергові відповідні символи в рядках не будуть різні чи поки не будуть досягнуті кінці рядків. Функція strcmp() повертає значення:

–< 0, якщо s1 менше ніж s2;

–= = 0, якщо s1 дорівнює s2;

–> 0, якщо s1 більше чим s2.

int strcmpi(const char *s1, const char *s2); - порівнює один рядок з іншим аналогічно strcmp(), але без розділення великих і маленьких букв. Функція strcmpi() визначена як макрос у string.h і

перетворює виклики strcmpi() на виклики strcmp(). Макрос забезпечує сумісність з іншими компіляторами С.