1.Запустите IDE Borland C++ 5.02. Подготовьте запуск исполнимых файлов в консольном режиме.
2. Откомпилируйте предложенную программу построения списков смежности, соответствующих ориентированному графу, вывод их на экран, добавление и удаление дуг.
#include <iostream.h>#define N 12 //Количество вершин графа.#define TRUE 1#define FALSE 0 typedef struct zveno *svqz;typedef struct zveno { int Key; //Вершина графа. svqz Sled; //Указатель на следующую смежную вершину. } Leader; class Spisok { private: svqz beg[N]; //Описание типа списков смежности. svqz res; //Указатель на найденное звено. void Poisk (svqz,int); void Udalenie (svqz *); public: Spisok (); svqz GetPoisk () { return res; } void MakeGraph (); void AddGraph (int,int); void DeleteGraph (int,int); void PrintGraph ();}; void main (){ Spisok A; int x; // Начало дуги. int y; // Конец дуги. A.MakeGraph (); // Построение списков смежности. // Вывод списков смежностей. cout<<"Представление графа списками смежности\n"; A.PrintGraph (); cout<<endl; // Добавление дуги к графу. cout<<"Добавим к графу новую дугу...\n"; cout<<"Введите начало дуги: "; cin>>x; cout<<"Введите конец дуги: "; cin>>y; A.AddGraph (x,y); cout<<"Представление графа списками смежности\n"; A.PrintGraph (); cout<<endl; //Удаление дуги из графа. cout<<"Удалим из графа заданную дугу...\n"; cout<<"Введите начало дуги: "; cin>>x; cout<<"Введите конец дуги: "; cin>>y; A.DeleteGraph (x,y); cout<<"Представление графа списками смежности\n"; A.PrintGraph (); cout<<endl;} void Spisok::Poisk (svqz uksp,int ment)// Поиск звена с информационным полем ment в // однонаправленном списке uksp. res - указатель// на найденное звено или NULL.{ svqz q; res = NULL; q = uksp; while ((q!=NULL)&&(res==NULL)) { if ((*q).Key==ment) res = q; q = (*q).Sled; }} void Spisok::AddGraph (int x,int y)// Добавление дуги (x,y) (если ее не было!) в граф,// представленный списками смежности beg.{ svqz ukzv,uzel; // Рабочие указатели. if (beg[x]!=NULL) { Poisk (beg[x],y); if (GetPoisk()==NULL) { //Добавление элемента в конец списка, заданного указателем beg[x]. uzel = new (Leader); (*uzel).Key = y; (*uzel).Sled = NULL; ukzv = beg[x]; while ((*ukzv).Sled!=NULL) ukzv = (*ukzv).Sled; (*ukzv).Sled = uzel; } } else { beg[x] = new (zveno);(*beg[x]).Key = y; (*beg[x]).Sled = NULL; }} void Spisok::MakeGraph ()// Построение списков смежности beg графа.{ int x,y; cout<<"Вводите начало дуги: "; cin>>x; cout<<"Вводите конец дуги: "; cin>>y; while (x!=0) { AddGraph (x,y); cout<< "Вводите начало дуги: "; cin>>x; cout<<"Вводите конец дуги: "; cin>>y; }} void Spisok::Udalenie (svqz *ukstr)//* Удаление звена, на которое ссылается указатель res,// из однонаправленного списка, заданного указателем *ukstr { svqz ukzv,z; if (((**ukstr).Sled==NULL)&&(res==*ukstr)) //В списке - один элемент! { *ukstr = NULL; delete res; } else if (res==*ukstr) // Удаляемый элемент - первый. { *ukstr = (**ukstr).Sled; delete res; } else { z = *ukstr; ukzv = (**ukstr).Sled; while (ukzv!=res) { z = ukzv; ukzv = (*ukzv).Sled; } (*z).Sled = (*res).Sled; delete res; }} void Spisok::DeleteGraph (int x,int y)// Удаление дуги (x,y) из списков смежности beg.{ if (beg[x]!=NULL) // Удаление звена из списка без заглавного звена. { // Вершины в графе есть. Poisk (beg[x],y); if (GetPoisk()!=NULL) Udalenie (&beg[x]); else cout<<"Такой дуги в графе нет!\n"; } else cout<<"Список пуст!\n";} void Spisok::PrintGraph (){ svqz ukzv; // Рабочий указатель. for (int i=1;i<N;i++) { cout<<"..."<<i; ukzv = beg[i]; if (ukzv==NULL) cout<<" Пустой список!\n"; else { while (ukzv!=NULL) { cout<<(*ukzv).Key; ukzv = (*ukzv).Sled; } cout<<endl; } }} Spisok::Spisok() { for (int i=0;i<N;i++) beg[i] = NULL; }
3.Откомпилируйте предложенную программу построения ортогональных списков смежности, соответствующих ориентированному графу, вывода на экран структуры ортогональных списков смежности, добавление и удаление дуг, добавление и удаление вершин.
#include <iostream.h>#define TRUE 1#define FALSE 0typedef int Boolean;typedef struct L *Lref; //Тип: указатель на заголовочный узел.typedef struct T *Tref; //Тип: указатель на дуговой узел. //Описание типа заголовочного узла.typedef struct L { int Key; //Имя заголовочного узла. int Count; //Количество предшественников. Tref Trail; //Указатель на список смежности. Lref Next; //Указатель на следующий узел в списке заголовочных узлов.} Leader; typedef struct T //Описание типа дугового узла.{ int Id; Tref Next; } Trailer; class Spisok{ private: Lref Head; //Указатель на начало списка заголовочных узлов. Lref Tail; //Указатель на фиктивный узел // в конце списка заголовочных узлов. void SearchGraph (int, Lref *); void Search (int, Lref *); public: Spisok () {//Инициализация списка заголовочных узлов. Head = Tail = new (Leader); } void MakeGraph (); void AddGraph (int, int); void DeleteGraph (int, int); void PrintGraph (); void DeleteY (int);}; void main (){ Spisok A; int x,y; //Начало и конец дуги //Построение и вывод структуры ортогональных списков. A.MakeGraph (); A.PrintGraph (); cout<<endl; //Добавление дуги к графу. cout<<"Добавим к графу новую дугу...\n"; cout<<"Введите начало дуги: "; cin>>x; cout<<"Введите конец дуги: "; cin>>y; A.AddGraph (x,y); A.PrintGraph (); cout<<endl; //Удаление дуги из графа. cout<<"Удалим из графа заданную дугу...\n"; cout<<"Введите начало дуги: "; cin>>x; cout<<"Введите конец дуги: "; cin>>y; A.DeleteGraph (x,y); A.PrintGraph (); cout<<endl; //Удаление вершины графа. cout<< "Введите удаляемую вершину: "; cin>>y; A.DeleteY (y); A.PrintGraph (); cout<<endl;} void Spisok::Search (int w, Lref *h)//Функция возвращает в *h указатель на заголовочный узел //ключом w. Если узел отсутствует, то функция возвращает NULL.{ *h = Head; (*Tail).Key = w; //Поиск "с барьером". while ((**h).Key!=w) *h = (**h).Next; if (*h==Tail) //В списке заголовочных узлов нет узла с ключом w. *h = NULL;} void Spisok::SearchGraph (int w,Lref *h)//Функция возвращает в *h указатель на заголовочный узел //с ключом w. Если заголовочный узел отсутствует, то он //добавляется в список.{ *h = Head; (*Tail).Key = w; while ((**h).Key!=w) *h = (**h).Next; if (*h==Tail) //В списке заголовочных узлов нет узла с ключом w. //Поместим его в конец списка *Head. { Tail = new (Leader); (**h).Count = 0; (**h).Trail = NULL; (**h).Next = Tail; }} void Spisok::MakeGraph ()//Функция возвращает указатель Head на ортогональные //списки смежности, соответствующую ориентированному графу.{ int x,y; Lref p,q; //Рабочие указатели. Tref t,r; // Рабочие указатели. Boolean Res; //Флаг наличия дуги. cout<<"Вводите начальную вершину дуги: "; cin>>x; while (x!=0) { cout<<"Вводите конечную вершину дуги: "; cin>>y; //Определим, существует ли в графе дуга (x,y)? SearchGraph (x,&p); SearchGraph (y,&q); r = (*p).Trail; Res = FALSE; while ((r!=NULL)&&(!Res)) if ((*r).Id==y) Res = TRUE; else r = (*r).Next; if (!Res) //Если дуга отсутствует, то поместим её в граф. { t = new (Trailer); (*t).Id = y; (*t).Next = (*p).Trail; (*p).Trail = t; (*q).Count++; } cout<<"Вводите начальную вершину дуги: "; cin>>x; }} void Spisok::AddGraph (int x,int y)//Добавление дуги (x,y) (если ее не было!) к связанной //структуре, соответствующей ориентированному графу Head.{ Lref p,q; //Рабочие указатели. Tref t,r; //Рабочие указатели. Boolean Res; //Флаг наличия в графе данной дуги. //Определим, существует ли в графе дуга (x,y)? SearchGraph (x,&p); SearchGraph (y,&q); r = (*p).Trail; Res = FALSE; while ((r!=NULL)&&(!Res)) if ((*r).Id==y) Res = TRUE; else r = (*r).Next; if (!Res) { //Если дуга отсутствует, то поместим её в граф. t = new (Trailer); (*t).Id = y; (*t).Next = (*p).Trail; (*p).Trail = t; (*q).Count++; }} void Spisok::DeleteGraph (int x,int y)//Функция возвращает указатель Head на связанную //структуру, соответствующую ориентированному графу//и полученную удалением дуги (x,y).{ Lref p,q; //Рабочие указатели. Tref t,r; //Рабочие указатели. Boolean Res; //Флаг наличия в графе данной дуги. //Определим, существует ли в графе дуга (x,y)? Search (x, &p); Search (y, &q); if ((p!=NULL)&&(q!=NULL)) { //Вершины x и y в графе есть. r = (*p).Trail; Res = FALSE; while ((r!=NULL)&&(!Res)) if ((*r).Id==y) Res = TRUE; else r = (*r).Next; if (Res) //Если дуга существует, то удалим её. if (r==(*p).Trail) { (*p).Trail = (*(*p).Trail).Next; delete r; (*q).Count--; } else { t = (*p).Trail; while ((*t).Next!=r) t = (*t).Next; (*t).Next = (*(*t).Next).Next; delete r; (*q).Count--; } }} void Spisok::PrintGraph ()//Вывод структуры смежности, заданной указателем //Head и соответствующей ориентированному графу.{ Lref p; //Рабочий указатель. Tref q; //Рабочий указатель. p = Head; while (p!=Tail) { cout<<"("<<(*p).Key; q = (*p).Trail; while (q!=NULL) { cout<<(*q).Id; q = (*q).Next; } cout<<")"; p = (*p).Next; cout<<" "; }} void Spisok::DeleteY (int y)//Функция возвращает указатель Head на связанную струк- //туру, соответствующую графу с удаленной вершиной y.{ Lref p,q; //Рабочие указатели. Tref r,s; //Рабочие указатели. int x; //Рабочая переменная. //Удаление всех дуг (x,y), оканчивающихся в вершине y. p = Head; while (p!=Tail) { x = (*p).Key; DeleteGraph (x,y); p = (*p).Next; } //Удаление списка смежности вершины y. SearchGraph (y, &p); r = (*p).Trail; while (r!=NULL) { s = r; r = (*r).Next; delete s; } //Удаление узла, содержащего вершину y, из списка заголовочных узлов. q = Head; if (q==p) { Head = (*Head).Next; delete q; } else { while ((*q).Next!=p) q = (*q).Next; (*q).Next = (*p).Next; delete p; }}
4.Откомпилируйте предложенную программу построения динамической структуры Вирта, соответствующей ориентированному графу, вывода на экран его структуры, добавления и удаления ребер, добавление и удаление вершин.
#include <iostream.h>#define TRUE 1#define FALSE 0typedef int Boolean;typedef struct L *Lref; //Тип: указатель на заголовочный узел.typedef struct T *Tref; //Тип: указатель на дуговой узел.//Описание типа заголовочного узла.typedef struct L { int Key; //Имя заголовочного узла. int Count; //Количество предшественников. Tref Trail; //Указатель на список смежности. Lref Next; //Указатель на следующий узел в //списке заголовочных узлов.} Leader; //Описание типа дугового узла.typedef struct T { Lref Id; Tref Next; } Trailer; class Spisok { private: Lref Head; //Указатель на список заголовочных узлов. Lref Tail; //Указатель на фиктивный элемент //в конце списка заголовочных узлов. Lref SearchGraph(int); Lref Search(int); public: Spisok () {//Инициализация списка заголовочных узлов. Head = Tail = new (Leader); } ~Spisok(); //Деструктор. void MakeGraph(); void AddGraph(int, int); void DeleteGraph(int, int); void PrintGraph(); void DeleteY(int); void Free1Graph(Lref *, Lref *); void Free2Graph(Tref *); }; void main (){ Spisok A; int x,y; //Начало и конец дуги. //Построение и вывод структуры Вирта. A.MakeGraph (); A.PrintGraph (); cout<<endl; cout<< "Добавим к графу новую дугу...\n"; cout<< "Введите начало дуги: "; cin>>x; cout<< "Введите конец дуги: "; cin>>y; A.AddGraph (x,y); A.PrintGraph (); cout<<endl; cout<< "Добавим к графу новое ребро...\n"; cout<< "Введите первую концевую вершину ребра: "; cin>>x; cout<< "Введите вторую концевую вершину ребра: "; cin>>y; A.AddGraph (x,y); A.AddGraph (y,x); A.PrintGraph (); cout<<endl; cout<< "Удалим из графа заданную дугу...\n"; cout<< "Введите начало дуги: "; cin>>x; cout<< "Введите конец дуги: "; cin>>y; A.DeleteGraph (x,y); A.PrintGraph (); cout<<endl; cout<< "Удалим из графа заданное ребро...\n"; cout<< "Введите первую концевую вершину ребра: "; cin>>x; cout<< "Введите вторую концевую вершину ребра: "; cin>>y; A.DeleteGraph (x,y); A.DeleteGraph (y,x); A.PrintGraph (); cout<<endl; cout<< "Введите удаляемую вершину: "; cin>>y; A.DeleteY (y); A.PrintGraph (); cout<<endl;} Spisok::~Spisok(){ //Очистка структуры Вирта. Lref t = Head; while (t!=Tail) { Free2Graph (&(*t).Trail); t = (*t).Next; } Free1Graph (&Head,&Tail); delete Tail;} Lref Spisok::SearchGraph (int w)//Функция возвращает указатель на заголовочный узел //с ключом w. Если заголовочный узел отсутствует, то он //добавляется в список. Head - указатель на структуру Вирта.{ Lref h; h = Head; (*Tail).Key = w; while ((*h).Key!=w) h = (*h).Next; if (h==Tail) //В списке заголовочных узлов нет узла с ключом w. //Поместим его в конец списка Head. { Tail = new (Leader); (*h).Count = 0; (*h).Trail = NULL; (*h).Next = Tail; } return h;} Lref Spisok::Search (int w)//Функция возвращает указатель на заголовочный узел //ключом w. Если узел отсутствует, то функция возвращает NULL.{ Lref h = Head; (*Tail).Key = w; //Поиск "с барьером". while ((*h).Key!=w) h = (*h).Next; if (h==Tail) //В списке заголовочных узлов нет узла с ключом w. h = NULL; return h;} void Spisok::MakeGraph ()//Функция возвращает указатель Head на структуру //Вирта, соответствующую ориентированному графу.{ int x,y; Lref p,q; //Рабочие указатели. Tref t,r; // Рабочие указатели. Boolean Res; //Флаг наличия дуги. cout<<"Вводите начальную вершину дуги: "; cin>>x; while (x!=0) { cout<<"Вводите конечную вершину дуги: "; cin>>y; //Определим, существует ли в графе дуга (x,y)? p=SearchGraph (x); q=SearchGraph (y); r = (*p).Trail; Res = FALSE; while ((r!=NULL)&&(!Res)) if ((*r).Id==q) Res = TRUE; else r = (*r).Next; if (!Res) //Если дуга отсутствует, то поместим её в граф. { t = new (Trailer); (*t).Id = q; (*t).Next = (*p).Trail; (*p).Trail = t; (*q).Count++; } cout<<"Вводите начальную вершину дуги: "; cin>>x; }} void Spisok::AddGraph (int x,int y)//Добавление дуги (x,y) (если ее не было!) к структуре//Вирта, соответствующей ориентированному графу Head.{ Lref p,q; //Рабочие указатели. Tref t,r; //Рабочие указатели. Boolean Res; //Флаг наличия в графе данной дуги. //Определим, существует ли в графе дуга (x,y)? p=SearchGraph (x); q=SearchGraph (y); r = (*p).Trail; Res = FALSE; while ((r!=NULL)&&(!Res)) if ((*r).Id==q) Res = TRUE; else r = (*r).Next; if (!Res) { //Если дуга отсутствует, то поместим её в граф. t = new (Trailer); (*t).Id = q; (*t).Next = (*p).Trail; (*p).Trail = t; (*q).Count++; }} void Spisok::DeleteGraph (int x,int y)//Функция возвращает указатель Head на структуру //Вирта, соответствующую ориентированному графу//и полученную удалением дуги (x,y).{ Lref p,q; //Рабочие указатели. Tref t,r; //Рабочие указатели. Boolean Res; //Флаг наличия в графе данной дуги. //Определим, существует ли в графе дуга (x,y)? p=Search (x); q= Search (y); if ((p!=NULL)&&(q!=NULL)) { //Вершины x и y в графе есть. r = (*p).Trail; Res = FALSE; while ((r!=NULL)&&(!Res)) if ((*r).Id==q) Res = TRUE; else r = (*r).Next; if (Res) //Если дуга существует, то удалим её. if (r==(*p).Trail) { (*p).Trail = (*(*p).Trail).Next; delete r; (*q).Count--; } else { t = (*p).Trail; while ((*t).Next!=r) t = (*t).Next; (*t).Next = (*(*t).Next).Next; delete r; (*q).Count--; } }} void Spisok::PrintGraph ()//Вывод структуры Вирта, заданной указателем //Head и соответствующей ориентированному графу.{ Lref p; //Рабочий указатель. Tref q; //Рабочий указатель. p = Head; while (p!=Tail) { cout<<"("<<(*p).Key; q = (*p).Trail; while (q!=NULL) { cout<<(*(*q).Id).Key; q = (*q).Next; } cout<<")"; p = (*p).Next; cout<<" "; }} void Spisok::DeleteY (int y)//Функция возвращает указатель Head на структуру Вирта, //соответствующую графу с удаленной вершиной y.{ Lref p,q; //Рабочие указатели. Tref r,s; //Рабочие указатели. int x; //Рабочая переменная. //Удаление всех дуг (x,y), оканчивающихся в вершине y. p = Head; while (p!=Tail) { x = (*p).Key; DeleteGraph (x,y); p = (*p).Next; } //Удаление списка смежности вершины y. p=SearchGraph (y); r = (*p).Trail; while (r!=NULL) { s = r; r = (*r).Next; (*(*s).Id).Count++; delete s; } //Удаление узла, содержащего вершину y, из списка заголовочных узлов. q = Head; if (q==p) { Head = (*Head).Next; delete q; } else { while ((*q).Next!=p) q = (*q).Next; (*q).Next = (*p).Next; delete p; }} void Spisok::Free1Graph (Lref *Head, Lref *Tail)//Очистка динамической памяти, занятой линейным списком, // заданным указателем *Head.{ if (*Head!=*Tail) { Free1Graph (&(**Head).Next,Tail); delete *Head; *Head = NULL; }} void Spisok::Free2Graph (Tref *X)//Очистка динамической памяти, занятой линейным списком, // заданным указателем *X.{ if (*X!=NULL) { Free2Graph (&(**X).Next); delete *X; *X = NULL; }}