Поставлення задачі. До бази даних заносять дані про клієнтів фірми, а саме: прізвище клієнта та номер його ідентифікаційного коду. З метою більш ефективного використання пам’яті дані заносять у вигляді списку, який має деревоподібну структуру: стовбур даного списку являє собою список – каталог, який містить початкові букви прізвищ, кожна з гілок такого дерева являє собою список структур даних, що мають однакову першу букву в прізвищі клієнта. Необхідно написати програму, яка б дозволяла організувати такий деревоподібний список даних, кількість яких заздалегідь невідома, а також вивести дані, що каталогізовано, на екран.
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*), прототипи яких наведено у головній програмі, а визначення наведено у попередніх прикладах.
Зміст|вміст,утримання| звіту до лабораторної роботи №5
1. Титульна сторінка|аркуш|: назва дисципліни; номер і найменування роботи; прізвище, ім'я, по батькові студента; дата виконання.
2. Поставлення завдання|задачі|. Слід дати конкретне поставлення, тобто вказати, який АТД має бути реалізовано, які під задачі повинні розв’язувати
3. Визначення основних змінних і функцій з|із| коментарями.
4. Реалізація функцій.
5. Лістинг основної програми, де має бути вказано, в якому місці та яка функція викликається|спричиняються|.
