?? algraph.cpp
字號:
//graph.cpp
#include<iostream>
#include "algraph.h"//引入頭文件
//graphmain.cpp
//#include <iostream>
#include <string>
//#include "graph.cpp"
using namespace std;
int visited[MaxSize];
/*
*前置條件：圖不存在
*輸 入：無
*功 能：圖的初始化
*輸 出：無
*后置條件：得到一個有向圖
*/
template <class T>
ALGraph<T>::ALGraph(T a[ ], int n, int e)
{
arcNum = e; //邊數(shù)
vertexNum=n; //頂點數(shù)
int i,j;
for (i=0; i<vertexNum; i++)
{
//VertexNode<T> t;
//t.vertex = a[i];
//t.firstedge = NULL;
//adjlist[i] = t;
adjlist[i].vertex=a[i];
adjlist[i].firstedge=NULL;//visited[i]=0;
}
for (int k=0; k<arcNum; k++) //依次輸入每一條邊，并在相應(yīng)邊表中插入結(jié)點
{
cout<<"請輸入邊所依附的兩個頂點的序號:"<<endl;
cin>>i>>j; //輸入邊所依附的兩個頂點的序號
ArcNode *s=new ArcNode; ArcNode *p=new ArcNode;s->adjvex=j; //生成一個邊表結(jié)點s
s->next=adjlist[i].firstedge; //將結(jié)點s插入到結(jié)點i的邊表的表頭
adjlist[i].firstedge=s;
p->adjvex=i; //生成一個邊表結(jié)點s
p->next=adjlist[j].firstedge; //將結(jié)點s插入到結(jié)點i的邊表的表頭
adjlist[j].firstedge=p;
}
}
//InsertArc(0,1); //插入邊
//InsertArc(0,2);
//InsertArc(0,3);
//InsertArc(1,3);
//InsertArc(1,4);
//InsertArc(2,0);
//InsertArc(2,4);
//InsertArc(3,1);
//InsertArc(3,4);
//InsertArc(4,2);
//InsertArc(4,3);
//}
/* 前置條件：圖已存在
* 輸 入：無
* 功 能：銷毀圖
* 輸 出：無
* 后置條件：釋放圖所占用的存儲空間
*/
template <class T>
ALGraph<T>::~ALGraph( )
{
for (int i=0; i<vertexNum; i++)
{
ArcNode * p=adjlist[i].firstedge;
while (p!=NULL) //循環(huán)刪除
{
adjlist[i].firstedge=p->next;
delete p; //釋放結(jié)點空間
p=adjlist[i].firstedge;
}
}
}
/*
*前置條件：圖已存在
*輸 入：頂點i
*功 能：輸出圖中頂點i的數(shù)據(jù)信息
*輸 出：圖中頂點i的數(shù)據(jù)信息
*后置條件：圖保持不變
*/
//template <class T>
/*T ALGraph<T>::GetVex(int i)
{
if ( i>vertexNum || i<0 ) throw "輸入頂點的位置不正確"; //頂點i不存在則拋出異常
return adjlist[i].vertex; //返回第i個頂點的數(shù)據(jù)域
}*/
/*
*前置條件：圖已存在
*輸 入：頂點i
*功 能：將圖中頂點i的數(shù)據(jù)域置為value
*輸 出：無
*后置條件：圖保持不變
*/
//template <class T>
/*void ALGraph<T>::PutVex(int i, T value)
{
if ( i>vertexNum || i<0 ) throw "輸入頂點的位置不正確"; //頂點i不存在則拋出異常
adjlist[i].vertex = value; //第i個頂點的數(shù)據(jù)域置為value
}*/
/*
*前置條件：圖已存在
*輸 入：頂點value,位置i
*功 能：在圖中i位置插入一個頂點name
*輸 出：如果插入不成功，拋出異常
*后置條件：如果插入成功，圖中增加了一個頂點
*/
//template <class T>
/*void ALGraph<T>::InsertVex(int i, T value)
{
if ( i>vertexNum || i<0 || i>MaxSize ) throw "輸入頂點的位置不正確"; //頂點i不存在則拋出異常
vertexNum++; //頂點數(shù)加1
VertexNode<T> tempvertex;
tempvertex.vertex = value;
tempvertex.firstedge = NULL;
adjlist[i] = tempvertex; //第i個頂點的數(shù)據(jù)域置為value
}*/
/*
*前置條件：圖已存在
*輸 入：頂點i
*功 能：在圖中刪除頂點i
*輸 出：如果刪除不成功，拋出異常
*后置條件：如果刪除成功，圖中減少了一個頂點,相應(yīng)頂點所建立的邊也消去
*/
//template <class T>
/*void ALGraph<T>::DeleteVex(int i)
{
if ( i<0 || i>MaxSize) throw "位置"; //頂點輸入錯誤則拋出異常
int k;
for ( k=0; k<vertexNum; k++) //刪掉入度邊
if(k!=i) DeleteArc(k, i);
ArcNode *s; //生成一個邊表結(jié)點s
if( adjlist[i].firstedge != NULL)
{
ArcNode *s;
s=adjlist[i].firstedge->next;
while(s!=NULL)
{
ArcNode *p;
p = s;
adjlist[i].firstedge->next = s->next;
s=s->next;
delete p; //刪除p結(jié)點
}
s=adjlist[i].firstedge;
adjlist[i].firstedge=NULL;
delete s;
}
for (k=i; k<vertexNum; k++)
{
adjlist[k]=adjlist[k+1]; //存儲頂點信息
}
vertexNum--; //頂點數(shù)減1
for (k=0; k<vertexNum; k++)
if( adjlist[k].firstedge != NULL )
{
s=adjlist[k].firstedge; //將結(jié)點s插入到結(jié)點i的邊表的表頭
while(s!=NULL)
{
if(s->adjvex > i) //搜索i結(jié)點
s->adjvex--;
s = s->next;
}
}
}*/
/*
*前置條件：圖已存在
*輸 入：頂點i、j
*功 能：在圖中插入頂點i、j及其所依附的邊
*輸 出：如果插入不成功，拋出異常
*后置條件：如果插入成功，圖中增加了一條邊
*/
//template <class T>
/*void ALGraph<T>::InsertArc(int i, int j)
{
if ( i>MaxSize || j>MaxSize) throw "位置";//頂點輸入錯誤則拋出異常
ArcNode *s=new ArcNode; s->adjvex=j; //生成一個邊表結(jié)點s
s->next=adjlist[i].firstedge; //將結(jié)點s插入到結(jié)點i的邊表的表頭
adjlist[i].firstedge=s;
}*/
/*
*前置條件：圖已存在
*輸 入：頂點i、j
*功 能：在圖中刪除頂點i、j 依附的邊
*輸 出：如果刪除不成功，拋出異常
*后置條件：如果刪除成功，圖中減少了一條邊
*/
//template <class T>
/*void ALGraph<T>::DeleteArc(int i, int j)
{
if ( i>MaxSize|| j>MaxSize) throw "位置"; //頂點輸入錯誤則拋出異常
ArcNode *s;
ArcNode *tempnode;
s = adjlist[i].firstedge;
tempnode = adjlist[i].firstedge;
while(s!=NULL && s->adjvex!=j)
{
tempnode = s;
s = s->next;
}
if(s!=NULL)
{
tempnode->next = s->next;
delete s;
}
}*/
/*
*前置條件：圖已存在
*輸 入：遍歷的起始頂點v
*功 能：從頂點v出發(fā)深度優(yōu)先遍歷圖
*輸 出：圖中頂點的一個線性排列
*后置條件：圖保持不變
*/
//template <class T>
//void ALGraph<T>::DFSTraverse(int v)
/*{
if ( v>vertexNum) throw "位置"; //頂點輸入錯誤則拋出異常
ArcNode * p;
int j;
//for(int k=0;k<MaxSize;k++)
// visited[k]=0;
cout<<adjlist[v].vertex<<" ";
visited[v]=1;
p=adjlist[v].firstedge;
while (p) //依次搜索頂點v的鄰接點j
{
j=p->adjvex;
if (visited[j]==0) DFSTraverse(j);
p=p->next;
}
}*/
ArcNode *s[MaxSize];
template <class T>
void ALGraph<T>::DFSTraverse(int v)
{ ArcNode * p; int j,top;
top=0;
cout<<adjlist[v].vertex<<" ";
visited[v]=1;
s[top++]=adjlist[v].firstedge;
while(top!=0)
{
p=s[--top];
if(p!=NULL)
{
s[top++]=p->next;
j=p->adjvex;
if(visited[j]==0)
{
visited[j]=1;
cout<<adjlist[j].vertex<<" ";
s[top++ ]= adjlist[j].firstedge;
}
}
}
}
/*
*前置條件：圖已存在
*輸 入：遍歷的起始頂點v
*功 能：從頂點v出發(fā)廣度優(yōu)先遍歷圖
*輸 出：圖中頂點的一個線性排列
*后置條件：圖保持不變
*/
template <class T>
void ALGraph<T>::BFSTraverse(int v)
{
if ( v>vertexNum) throw "位置"; //頂點輸入錯誤則拋出異常
int front,rear,j;
ArcNode * p; //生成一個邊表結(jié)點p
int Q[MaxSize];
front=rear=-1;
for(int k=0;k<MaxSize;k++)
visited[k]=0;//初始化隊列, 假設(shè)隊列采用順序存儲且不會發(fā)生溢出
cout<<adjlist[v].vertex<<" "; visited[v]=1; Q[++rear]=v; //被訪問頂點入隊
while (front!=rear)
{
v=Q[++front];
p=adjlist[v].firstedge; //邊表中的工作指針p初始化
while (p)
{
j= p->adjvex;
if (visited[j]==0) {
cout<<adjlist[j].vertex<<" "; visited[j]=1;Q[++rear]=j;
}
p=p->next;
}
}
}
//graphmain.cpp
//#include <iostream>
//#include <string>
//#include "graph.cpp"
//using namespace std;
//int visited[MaxSize];
void main( )
{
//int which;
//int j;
//string name;
//int choose=1;
//for(int j=0;j<MaxSize;j++)
//visited[j]=0;
string a[4] = {"A","B","C","D"};
ALGraph<string> aTest( a, 4, 3);
//aTest.PutVex(i, name);//構(gòu)造圖
cout<<"深度優(yōu)先遍歷:";
aTest.DFSTraverse(0);
cout<<endl;
cout<<"廣度優(yōu)先遍歷:";
aTest.BFSTraverse(0);
}
/*while ( choose==1 ) //控制
{
cout << "需要輸出頂點信息請按0" << endl; //輸入所要進行的操作的序號
cout << "需要輸出任意一個頂點信息請按1" << endl;
cout << "需要插入頂點請按2" << endl;
cout << "需要修改頂點請按3" << endl;
cout << "需要刪除頂點請按4" << endl;
cout << "需要深度優(yōu)先遍歷請按5" << endl;
cout << "需要廣度優(yōu)先遍歷請按6" << endl;
cout << "需要退出請按7" << endl;
cin >> which;
switch( which ) //功能選擇
{
case 0:
for(j=0;j<5;j++ )
cout<<algraphTest.GetVex(j)<<" "; //輸出頂點
cout<<endl;
break;
case 1:
int i;
cout<<"請輸入頂點："<<endl;
cin>>i;
try
{
cout<<algraphTest.GetVex(i)<<endl; //輸出i頂點的數(shù)據(jù)域
}
catch(char* s)
{
cout<<s<<endl;
}
break;
case 2: //在圖中的i位置插入一頂點值為name
cout<<"請輸入頂點及名字："<<endl;
cin>>i>>name;
try
{
algraphTest.InsertVex(i, name);
}
catch(char* s)
{
cout<<s<<endl;
}
break;
case 3: //修改圖中一頂點的值
cout<<"請輸入頂點及名字："<<endl;
cin>>i>>name;
try
{
algraphTest.PutVex(i, name);
}
catch(char* s)
{
cout<<s<<endl;
}
break;
case 4: //刪除圖中一頂點的值
cout<<"請輸入頂點："<<endl;
cin>>i;
try
{
algraphTest.DeleteVex(i);
}
catch(char* s)
{
cout<<s<<endl;
}
break;
case 5: //圖的深度優(yōu)先搜索
cout<<"請輸入頂點："<<endl;
cin>>i;
cout<<endl<<"從第"<<i<<"個頂點深度優(yōu)先遍歷圖"<<endl;
try
{
for (int ii=0; ii<MaxSize; ii++) visited[ii] = 0;
algraphTest.DFSTraverse(i);
}
catch(char* s)
{
cout<<s<<endl;
}
break;
case 6: //圖的廣度優(yōu)先搜索
cout<<"請輸入頂點："<<endl;
cin>>i;
cout<<endl<<"從第"<<i<<"個頂點廣度優(yōu)先遍歷圖"<<endl;
try
{
for (int ii=0; ii<MaxSize; ii++) visited[ii] = 0;
algraphTest.BFSTraverse(i);
}
catch(char*s)
{
cout<<s<<endl;
}
break;
case 7: //退出
choose=0;
break;
}
}*/
//}?? 快捷鍵說明
復(fù)制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -