Курсова работа по САА

Русенски Университет
"Ангел Кънчев"
Катедра ЕЕА
Курсова работа 1 по Синтез и Анализ на Алгоритми

на ………………….
студент … курс
специалност: Компютърни системи и технологии
гр. … ,фак.№ ….

Русе,
……….. г.
Разработил:.............. Проверил:..............

Условие на задачата:
3. Телефонен указател се въвежда от клавиатурата в следния формат:
Name: David Goss
Surname: Burns
Tel: 230239
Name: John Silver
Surname:Adams
Tel: 436784
Name: Ana Nowak
Surname:Burns
Tel: 213154
…
Да се разработи програма,която изпълнява следните функции:
- Създава двоично дърво на търсене,съдържащо информация само за фамилиите и честотата им на срещане в указателя(ключ на търсене – фамилия);
· Извежда информация(от създаденото двоично дърво на търсене)за броя на лицата със зададена(от клавиатурата) фамилия;
[Извежда информация (от създаденото двоично дърво на търсене) за броя на лицата с най-често срещаната фамилия. ]
· Извежда информацията, сортирана във възходящ ред на ключа(речникова подредба);

Код на програмата:

#include <iostream>
#include <string>
using namespace std;

struct Item { //структура , един елемент от дървото.

char sname[31];
int broi;
Item *L, *R;
};
typedef Item* Point; // Указател към елементите на дървото.
Point root; // Коренът на дървото , от тип указател

void Add_S_tree(char x[31], Point &p) // Създаване на дървото
{
if (p==NULL) {
p= new Item;
strcpy (p->sname,x);
p->broi=1;
p->L=NULL; p->R=NULL;
}
else if (strcmp (x,p->sname)<0) Add_S_tree (x,p->L);
else if (strcmp (x,p->sname)>0) Add_S_tree (x,p->R);
else p->broi++;
}

int CountF(char k[31],Point p) { // функция за извеждане на броя повторения на дадено име К.
if (p) {
if(strcmp(p->sname,k)==0){
return p->broi;
}else return CountF(k,p->R)+CountF(k,p->L);
} else return 0;
}

void print(Point p) { //принтиране във възходящ ред

if (p) {

print(p->L);
cout<<p->sname<<endl;
print(p->R);}
}

void main(){
root=NULL;
char ch;
char x[31];

int j=0;
while(j==0) {
cout<<" Shte Vyvejdate li? (Y/N) "; cin>>ch;
if (ch=='n' || ch=='N') j++; else {
cout<<"Vavedete Familno ime: "; cin>>x;
Add_S_tree(x,root);
}
}
char k[31];

cout<<"Tyrsene broi lica po familiq? (Y/N)";cin>>ch;
if (ch=='n' || ch=='N') {} else {
cout<<"Vavedete Familiq za tyrsene na broi: "; cin>>k;
cout<<"Broqt e: "<<CountF(k,root)<<endl;
}

cout<<"Printirane na informaciqta? (Y/N)";cin>>ch;
if (ch=='n' || ch=='N') {} else {
cout<<"Printirane vyv vyzhodqsht red: "<<endl; print(root);
}
cout<<endl;
system ("pause");
}

72a5109LLR3RRRЗа реализация на програмата са използвани две процедури и една функция. Те обработват дървото на търсене което се състои от елементи от тип Struct със полета sname от тип char за въвеждане на фамилиите , broi от тип integer за съхранение на броят на срещане на дадено име и L,R които са указатели които ще сочат към съответно левия или десния наследник на елемента.
Едно от условията е да се изведе съдържанието на дървото в низходящ ред по ключ. Тъй като ключът е от тип char ( фамилно име) използваме #include<string> за да сравняваме низове. За улеснение дървото се сортира по време на въвеждането от потребителя. Ако елементът който въвежда потребителя е по-голям от предходния (е по-надоло в речника) той се позиционира в дясно на текущия елемент , ако е по-малък се въвежда в ляво.Възможно е елементът вече да съществува , но не може да имаме два елемента с един и същ ключ. Поради тази причина ако въведения елемент съвпада с друг , той не се въвежда а единствено се увеличава броят на срещане на дадения елемент (broi++) . Началната стойност на броя за всеки елемент е единица и се увеличава с 1 при всяко въвеждане на нов елемент със същия ключ.
Извеждането на броя на повторения на дадено име се получава сравнително лесно. Полето sname на всеки елемент се сравнява с променлива от тип char , K която представлява името което търсим. Функцията CountF обхожда дървото търсейки елемента и си присвоява стойност – неговия брой. След това в главната функция се извежда стойността на функцията.
Принтирането във възходящ ред се осъществява с функция на 4 реда благодарение на това , че дървото се сортира по време на въвеждане. Функцията просто принтира цялото дърво като започва от най-левия елемент (най-малкия) и преминава към дясната част на дървото (най-големите елементи).

Описание на използваните функции
Вид на функцията: void Add_S_tree
Действие:Добавяне и сортиране на елементи.
Параметри:
char x[31] : фамилията на елементът който се въвежда.
Point &p : Указател към текущия елемент. Псевдоним за да се променя по време на изпълнението на процедурата.
Използвани глобални променливи: няма
Извиквани функции: Add_S_tree
Вид на функцията: CountF
Действие: Изжежда брой повторения в дървото на зададено предварително име.
Параметри: char k[31] , Point p
Използвани глобални променливи: няма
Извиквани функции: CountF

Вид на функцията: void print
Действие: Принтиране на дървото
Параметри: Point p
Използвани глобални променливи: няма
Извиквани функции: няма
Снимки от изпълнението на програмата: