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