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

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

1. Приклад організації даних. Кожна з гилок деревоподібного списку сама по собі є списком, кожен вузол якого містить прізвище, номер ідентифікаційного коду, адресу сусіднього(попереднього або наступного) елемента списку. В даному випадку обираємо організацію FIFO, тобто кожен вузол містить адресу наступного елементу. Структуру, що описує такий список, наведено нижче:

struct list

{ char* surname;

char* id_cod;

list* next;

};

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

struct katalog

{

char bukva;

list* first;

katalog* prev;

};

2. Приклад розподілу пам’яті під елементи списку.

Розподіл пам’яті організуємо у вигляді двох функцій: 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; //повернути адресу першого елементу даного списку прізвищ

}

3. Приклад виводу на екран всіх даних зі списку.

Вивідданих організовано за допомогою функції 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; // перейти до наступного вузла списку - каталогу

}

}

4. Приклад основної програми, що дозволяє організувати занесення даних та сформувати список – каталог та списки прізвищ.

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