Основни операции. Помощни програмни файлове

5.3.Основни операции. Помощни програмни файлове

• 
  обхождане на граф в ширина;
  
• 
  обхождане на граф в дълбочина;
  
• 
  топологично сортиране.
  

С цел да си улесним работата по създаването на програми, реализиращи горните операции, предварително ще подготвим два заглавни файла (по един за двата начина за вътрешно представяне на граф). Тези заглавни файлове ще ползваме както при създаване на програмите за обхождане на граф в ширина, за обхождане на граф в дълбочина и за топологично сортиране, така и при програмите за решаване на конкретни приложни задачи. В заглавните файлове са включени клас стек и клас опашка, защото, както ще видим, при обхожданията се ползват тези познати структури.

#include

#include

#include

#include

#include

unsigned BrV; //Брой върхове в графа

//Клас на стека

class clasSt{

public:

unsigned Br; //Брояч на елементите на стека

clasSt(){Br=0; mas=new unsigned[2*BrV];}

~clasSt() {delete []mas; cout<<"Стекът е изтрит.\n";}

int DobEl(unsigned &X);

int VzeEl(unsigned &X);

};

//Член-функция за добавяне на елемент към стек

{

if (Br==2*BrV) return 0;//В стека няма място за нов елемент

}

//Член-функция за отнемане на елемент от стек

{

if (Br==0) return 0; //Стекът е празен

}

//Клас на опашката

unsigned *mas, //Масивът, съхраняващ елементите от oпашката

firstFull, //Индекс на първия от заетите елементи в масива

firstFree; //Индекс на първия от свободните елементи в масива

public:

int Br; //Брояч на елементите в опашката

~clasOp() {delete []mas; cout<<"Опашката е изтрита.\n";}

int DobEl(unsigned &X);

int VzeEl(unsigned &X);

};
//Член-функция за добавяне на елемент към опашката.

int clasOp::DobEl(unsigned &X)

{

if (Br==BrV) return 0;//В опашката няма място за нов елемент

if (++firstFree==BrV) firstFree=0;

Br++; return 1;

}

////Член-функция за вземане на елемент от опашката.

{

if (Br==0) return 0; //Опашката е празна

if (++firstFull==BrV) firstFull=0;

Br--; return 1;

}

ifstream fin; //Глобален входен поток за четене от текстовия файл

class clasGraph{

int **A; //Матрица на съседство на графа

clasSt Stek; //Стек, който се използва при обхождане в дълбочина

clasOp Opashka;//Опашка, която се използва. при обхождане в ширина и топологично сортиране

public:

~clasGraph(); //Деструктор

void make_graf(); //Запълва матрицата на съседство

void display_graf(ostream &);// Извежда матрицата на съседство на екрана

//void display_grafTF();//Извежда матрицата на съседство в текст.файл

void BFS(); //Обхожда в ширина. Намира се във файл "ob_s_m.cpp"

void kraBFS(); //Намира най-кратък път в безтегл. граф - "najk_mat.cpp".

void DFS(); //Обхожда в дълбочина, като използва стек-"ob_d_m.cpp"

void DFS(unsigned i);//Обхожда в дълб., като използва рекурсия-"ob_d_m_r.cpp"

void vsiDFS(unsigned i, unsigned j);//Намира всички прости пътища от i-ия до j-ия връх, намира се във файл "allp_gr.cpp".

void hamDFS(unsigned i,unsigned nivo); //Най-кратка обиколка на всички върхове.

//Намира се във файл "ham_mat.cpp"

void top_sort();//Извършва топологично сортиране - "top_mas.cpp"

void dijkstra();//Най-кратък път oт здаден връх до всички други - "dejx_mat.cpp"

void OrgProekt();

};

//Конструктор за създаване и инициализация на матрицата на съседство

{

int i,j;

for (i=0; i

for (i=0; i

for (j=0; j

}

//Деструктор, който изтрива матрицата на съседство

{

for (int i=0; i

delete []A; cout<<"\nМатрицата на съседство е изтрита.\n";

}

//Член-функция за запълване на матрицата на съседство

{

char kod_or,kod_teg; int i,j,teg;

cout<<"Графът тегловен ли е /D,d,Д,д/? "; cin>>kod_teg;

for (;;) {

fin>>i>>j;if (fin.fail()) break;

if (kod_teg=='D'||kod_teg=='d'||kod_teg=='Д'||kod_teg=='д') fin>>teg;

else teg=1;

A[i][j]=teg;

if (kod_or!='D'&&kod_or!='d'&&kod_or!='Д'&&kod_or!='д') A[j][i]=teg;

}

fin.close();

//Член-функция за извеждане на матрицата на съседство на екрана

//или в текстов файл

void clasGraph::display_graf(ostream &p=cout)

{

if (p!=cout) fout.open("DopInf",ios::out);

p<<"\n MATРИЦА НА СЪСЕДСТВО\n";

p<<" ";

for (i=0;i

for (i=0;i

p<

for (j=0;j

p<

if (p!=cout){

fout.close();

cout<<"\nОтрорете текст. файл DopInf.\n";

}

}

Програмата включва само познати неща: класовете стек, опашка и граф, както и член-функциите на тези класове.

#include

#include

#include

#include

unsigned BrV; //Брой на върховете в графа

//Структура rebro. Всеки елемент от списък на съседство, стек или опашка е

//обект от тази структура.

struct rebro{int nom, teg; rebro *next;};

// Клас стек

class clasSt{

rebro *first; //Указател към върха на стека

public:

int Br; //Брояч на елементите в стека

int DobEl(unsigned X);

int VzeEl(unsigned &X);

};
//Член-функция за добавяне на елемент в стек

{

rebro *p;

p->nom=X; p->next=first;

first=p;Br++;return 1;

}
//Член-функция за вземане на елемент от стека

int clasSt::VzeEl(unsigned &X)

{

rebro *p;

p=first;

delete p; Br--; return 1;

}
// Клас oпашка

class clasOp{

rebro *first,*last;

public:

clasOp::clasOp() { Br=0; first=last=0;}

int DobEl(unsigned X);

int VzeEl(unsigned &X);

};
//Член-функция за добавяне на компонента в опашка

int clasOp::DobEl(unsigned X)

{

rebro *p;

p->nom=X;

if (!last) first=p;

else last->next=p;

last=p;

Br++;

}
//Член-функция за вземане на компонента от опашката

int clasOp::VzeEl(unsigned &X)

{

rebro *p;

p=first;

if (first==last) last=0;

first=first->next;

delete p; Br--; return 1;

}

ifstream fin; //Глобален входен поток за четене от текстовия файл

//Структура връх от граф

struct vrah { rebro *first; };

//Клас граф

class clasGraph {

private:

clasSt Stek;

clasOp Opashka;

public:

~clasGraph();//Деструктор за изтриване на граф

void make_graf();

void display_graf(ostream &);

void BFS(); //Обхожда в ширина. Намира се във файл "ob_s_s.cpp"

void kraBFS(); //Намира най-кратък път в безтегл. граф - "najkr_sp.cpp".

void DFS(); //Обхожда в дълбочина, като използва стек - "ob_d_s.cpp"

void DFS(unsigned i); //Обхожда в дълбочина, като използва рекурсия - "ob_d_s_r.cpp"

void vsiDFS(unsigned, unsigned); //Намира всички прости пътища от i-ия до j-ия връх -файл "allp_sp.cpp".

void hamDFS(unsigned, unsigned); //Най-кратка обиколка на всички върхове – "ham_sp.cpp"

void top_sort();//Извършва топологично сортиране - "top_sp.cpp"

void dijkstra();//Най-кратък път oт здаден връх до всички други - "dejx_sp.cpp"

};

// Конструктор за създаване и инициализация на граф

{

a=new vrah[BrV];

}

//Деструктор за изтриване на графа

clasGraph::~clasGraph()

{

rebro* p;

for (int i=0;i

while (a[i].first){

p=a[i].first;

a[i].first=p->next;

delete p;

}

}

delete []a; cout<<"\nМасивът от списъци e изтрит."<

}

char kod_teg;

//Член-функция за изграждане на масива от списъци на съседство

void clasGraph::make_graf()

{

rebro *p; char kod_or; unsigned i,j,teglo;

cout<<"Графът ориентиран ли е /D,d,Д,д/? "; cin>>kod_or;

if (kod_or=='D'||kod_or=='d'||kod_or=='Д'||kod_or=='д') kod_or=1;

else kod_or=0;

cout<<"Графът тегловен ли е /D,d,Д,д/? "; cin>>kod_teg;

if (kod_teg=='D'||kod_teg=='d'||kod_teg=='Д'||kod_teg=='д') kod_teg=1;

else kod_teg=0;

for (;;) {

fin>>i>>j; if (fin.fail()) break;

if (kod_teg) fin>>teglo;

else teglo=1;

p=new rebro; p->nom=j; p->teg=teglo; p->next=a[i].first; a[i].first=p;

if (!kod_or) {

p=new rebro; p->nom=i; p->teg=teglo; p->next=a[j].first; a[j].first=p;

}

}

fin.close ();

}

//Член-функция за визуализaция на масива от списъци на съседство

void clasGraph::display_graf(ostream &pp=cout)

{

if (pp!=cout) fout.open("DopInf",ios::out);

int i; rebro *p;

pp<<"\n МАСИВ ОТ СПИСЪЦИ НА СЪСЕДСТВО\n";

for (i=0;i

pp< ";

p=a[i].first;

while (p!=0){

pp<nom; if (kod_teg) pp<teg; pp<<" -> ";

p=p->next;

} pp<

}

if (pp!=cout){

fout.close();

cout<<"\nОтрорете текст. файл DopInf.\n";

}

}
Програмата включва само познати неща: класовете стек, опашка и граф, както и член-функциите на тези класове. Новото е, че към член-данните на класовете стек и опашка е добавен брояч на елементите. Той е необходим за повечето от програмите, които ползват заглавния файл.

Изтегляне 0.63 Mb.

Сподели с приятели: