数据结构--图的实验报告

图的实验报告
班级：电子091 学号：0908140620 姓名：何洁编号：19
（一）实验要求
创建一个图。

能够实现图的输入，插入顶点和边，利用队列进行深度和广度遍历。

（二）需求分析
功能：1，输入图的信息；2，插入一个顶点；3插入一个边；4，删除一个顶点；5，删除一个边；6，深度优先遍历；7，广度优先遍历；8退出。

（三）概要设计
本程序采用的是模板类，抽象数据类型有：T,E。

类：
template <class T,class E>
class Graphmtx {
friend istream & operator>>(istream& in,Graphmtx<T, E>& G);
friend ostream & operator<<(ostream& out, Graphmtx<T, E>& G);//输出
public:
Graphmtx(int sz=30, E max=0); //构造函数
~Graphmtx () //析构函数
{ delete []VerticesList; delete []Edge; }
T getValue (int i) {
//取顶点i 的值, i 不合理返回0
return i >= 0 && i <= numVertices ?
V erticesList[i] : NULL;
}
E getWeight (int v1, int v2) { //取边(v1,v2)上权值
return v1 != -1 && v2 != -1 ? Edge[v1][v2] : 0;
}
int NumberOfEdges(){return numEdges;} //返回当前边数
int NumberOfVertices(){return numVertices;} //返回当前顶点
int getFirstNeighbor (int v);
//取顶点v 的第一个邻接顶点
int getNextNeighbor (int v, int w);
//取v 的邻接顶点w 的下一邻接顶点
bool insertVertex (const T& vertex);
//插入顶点vertex
bool insertEdge (int v1, int v2, E cost);
//插入边(v1, v2),权值为cost
bool removeVertex (int v);
//删去顶点v 和所有与它相关联的边
bool removeEdge (int v1, int v2);
//在图中删去边(v1,v2)
int getVertexPos (T vertex) {
//给出顶点vertex在图中的位置
for (int i = 0; i < numVertices; i++)
if (VerticesList[i] == vertex) return i;
return -1;
}
//int numVertexPos(T vertex);
private:
int maxVertices;
int numEdges;
int numVertices;
T *VerticesList; //顶点表
E **Edge; //邻接矩阵
const E maxWeight;
};
（四）详细设计
函数通过调用图类中的函数实现一些功能。

头文件:
#include<iostream.h>
#include<assert.h>
const int maxSize=50;
const int DefaultVertices=30; //最大顶点数(=n) const int maxWeight=50;
其中顺序队列的实现:
template<class T>
class SeqQueue
{
//循环队列的类的定义
public:
SeqQueue(int sz=10); //构造函数
~SeqQueue(){delete[] elements;} //析构函数
bool EnQueue(const T& x);
//若队列不满，则将X进队，否则队溢出处理
bool DeQueue(T& x);
//若队列不为空，则函数返回TRUE及对头元素的值，否则返回FALSE
void makeEmpty(){front=rear=0;}
//置空操作：对头指针和队尾指针置0
bool IsEmpty()const{return(front==rear)?true:false;}
//判队列空否，若队列空，则函数返回TRUE，否则返回FALSE
bool IsFull()const
{return((rear+1)%maxSize==front)?true:false;}
//判队列满否，若队列满，则函数返回TRUE，否则返回FALSE protected:
int rear,front; //对头和队尾指针
T *elements; //存放队列元素的数组
int maxSize; //队列最大可容纳元素个数
};
template<class T>
SeqQueue<T>::SeqQueue(int sz):front(0),rear(0),maxSize(sz)
{
//建立最大具有Maxsize个元素的空队列
elements=new T[maxSize]; //创建队列空间
assert(elements!=NULL); //断言：动态存储分配成功与否
}
template<class T>
bool SeqQueue<T>::EnQueue(const T& x)
{
//若队列不满，则将元素X插入到该队列的队尾，否则出错处理
if(IsFull()==true)return false; //队列满则插入失败，返回
elements[rear]=x; //按照队尾指针指示位置插入
rear=(rear+1)%maxSize; //队尾指针加1
return true; //插入成功
}
template<class T>
bool SeqQueue<T>::DeQueue(T& x)
{
//若队列不空则函数推掉一个对头元素并返回TRUE，否则函数返回FALSE if(IsEmpty()==true)return false; //若队列空则删除失败，返回
x=elements[front];
front=(front+1)%maxSize; //对头指针加1
return true; //删除成功
}
类的实现:
template <class T, class E>
Graphmtx<T, E>::Graphmtx(int sz, E max):maxWeight(max){ //构造函数maxVertices=sz;
numVertices=0;
numEdges=0;
int i, j;
VerticesList = new T[maxVertices]; //创建顶点表
Edge = (int **) new int *[maxVertices];
for (i = 0; i < maxVertices; i++)
Edge[i] = new int[maxVertices]; //邻接矩阵
for (i = 0; i < maxVertices; i++) //矩阵初始化
for (j = 0; j < maxVertices; j++)
Edge[i][j]=(i==j)?0:maxWeight;
}
template <class T, class E>
int Graphmtx<T, E>::getFirstNeighbor (int v) {
//给出顶点位置为v的第一个邻接顶点的位置,
//如果找不到, 则函数返回-1
if (v != -1) {
for (int col = 0; col < numVertices; col++)
if (Edge[v][col] && Edge[v][col] < maxWeight)
return col;
}
return -1;
}
template <class T, class E>
int Graphmtx<T, E>::getNextNeighbor (int v, int w) {
//给出顶点v 的某邻接顶点w 的下一个邻接顶点
if (v != -1 && w != -1) {
for (int col = w+1; col < numVertices; col++)
if (Edge[v][col] && Edge[v][col] < maxWeight)
return col;
}
return -1;
}
界面：
cout<<" =================================="<<endl;
cout<<" |1、输入一个图2、插入一个顶点| "<<endl;
cout<<" |3、插入一个边4、删除一个顶点|"<<endl;
cout<<" |5、删除一个边6、深度优先遍历|"<<endl;
cout<<" |7、广度优先遍历8、退出|"<<endl;
cout<<" =================================="<<endl;
然后进入循环进行功能操作
Case1中，输入一个图：
其中有操作符的重载，使图的信息直接输入：
template<class T,class E>
istream& operator >> (istream& in,Graphmtx<T,E>& G){
//通过从输入流in输入n个顶点信息和e条无向边的信息建立用邻接矩阵的图G。

//邻接矩阵初始化的工作已经在构造函数中完成、
int i,j,k,n,m;
T e1,e2;
E weight;
in>>n>>m;
for(i=0;i<n;i++){
in>>e1;
G.insertVertex(e1);
}
i=0;
while(i<m){
in>>e1>>e2>>weight;
j=G.getVertexPos(e1);k=G.getVertexPos(e2);
if(j==-1||k==-1)
cout<<"边两端信息有误，重新输入！"<<endl;
else{
G.insertEdge(j,k,weight);i++;
}
}
return in;
}
cout<<"请输入图的信息："<<endl;
cin>>g1;cout<<endl;
break;
Case2中，是插入顶点，需要调用的函数有：
template<class T,class E>
bool Graphmtx<T,E>::insertVertex(const T& vertex){ //插入顶点vertex
if(numVertices==maxVertices)return false; //顶点表满，不插入
VerticesList[numVertices++]=vertex;
return true;
}
case 2:
cout<<"请输入要插入的顶点：";
cin>>v1;
g1.insertV ertex (v1);
cout<<g1;
cout<<"插入成功"<<endl;
break;
出现界面：
Case3中，是实现插入边的操作，需要调用的函数有：
template<class T,class E>
bool Graphmtx<T,E>::insertEdge (int v1,int v2,E cost){
//插入边(v1,v2),权值为cost
if(v1>-1&&v1<numVertices&&v2>-1&&v2<numVertices && Edge[v1][v2]==maxWeight){ Edge[v1][v2]=Edge[v2][v1]=cost;
numEdges++;
return true;
}
else return false;
}
然后执行调用：
case 3:
cout<<"请输入插入边的两个顶点的序号:";
cin>>e1>>e2;
cout<<endl;
cout<<"请输入权值：";
cin>>cost;
g1.insertEdge (e1,e2,cost);
cout<<g1;
break;
出现界面：
Case 6是进行深度优先遍历：
利用了队列，调用的函数有：
template<class T, class E>
void DFS(Graphmtx<T, E>& G, const T& v) {
//从顶点v出发对图G进行深度优先遍历的主过程
int i, loc,n;
n=G.NumberOfVertices(); //顶点个数
bool *visited=new bool[n]; //创建辅助数组
for (i = 0; i < n; i++) visited [i] = false;
//辅助数组visited初始化
loc = G.getVertexPos(v);
DFS (G, loc, visited); //从顶点0开始深度优先搜索
delete [] visited; //释放visited
}
template<class T, class E>
void DFS(Graphmtx<T, E>& G, int v, bool visited[]) {
cout << G.getValue(v) << ' '; //访问顶点v
visited[v] = true; //作访问标记
int w = G.getFirstNeighbor (v); //第一个邻接顶点
while (w != -1) { //若邻接顶点w存在
if ( !visited[w] ) DFS(G, w, visited);
//若w未访问过, 递归访问顶点w w = G.getNextNeighbor (v, w); //下一个邻接顶点
}
}
主函数中：
case 6:
cout<<"请输入一个顶点：";
cin>>v1;
cout<<"图的深度优先搜索为："<<endl;
DFS(g1,v1);
cout<<endl;
break;
界面出现：
Case7是现实广度优先遍历的操作，也需要利用到队列，
其函数体为：
template <class T, class E>
void BFS(Graphmtx<T, E>& G, const T& v) {
int i,w;
int n = G.NumberOfVertices();
//图中顶点个数
bool *visited = new bool[n];
for (i = 0; i < n; i++) visited[i] = false;
int loc = G.getVertexPos (v); //取顶点号
cout << G.getValue (loc) << ' '; //访问顶点v
visited[loc] = true; //做已访问标记
SeqQueue<int> Q; Q.EnQueue (loc); //顶点进队列, 实现分层访问
while (!Q.IsEmpty() ) { //循环, 访问所有结点
Q.DeQueue (loc);
w = G.getFirstNeighbor (loc); //第一个邻接顶点
while (w != -1) { //若邻接顶点w存在
if (!visited[w]) { //若未访问过
cout << G.getValue (w) << ' '; //访问
visited[w] = true;
Q.EnQueue (w); //顶点w进队列
}
w = G.getNextNeighbor (loc, w); //找顶点loc的下一个邻接顶点
}
} //外层循环，判队列空否
delete [] visited;
}
主函数中的调用：
case 7:
cout<<"请输入一个顶点：";
cin>>v1;
cout<<"图的广度优先搜索为："<<endl;
BFS(g1,v1);
cout<<endl;
break;
界面显示：
Case4中式删除顶点的操作;
函数的实现：
template<class T,class E>
bool Graphmtx<T,E>::removeVertex (int v){
//删去顶点v和所有与它相关的边
if(v<0||v>=numVertices)return false;
if(numVertices==1)return false;
int i,j;
VerticesList[v]=VerticesList[numVertices-1];
for(i=0;i<numVertices;i++)
if(Edge[i][v]<0&&Edge[i][v]<maxWeight)numEdges--;
for(i=0;i<numVertices;i++)
Edge[i][v]=Edge[i][numVertices-1];
numVertices--;
for(j=0;j<numVertices;j++)
Edge[v][j]=Edge[numVertices][j];
return true;
}
主函数中：
case 4:
cout<<"请输入要删除的顶点序号：";
cin>>e1;
g1.removeVertex(e1);
cout<<g1;
break;
界面显示：
Case5的操作是删除一条边：要调用的函数：
template<class T,class E>
bool Graphmtx<T,E>::removeEdge (int v1,int v2){
//在图中删除边(v1,v2)
if(v1>-1&&v1<numVertices&&v2>-1&&v2<numVertices&&Edge[v1][v2]>0&&Edge[v1][ v2]<maxWeight){
Edge[v1][v2]=Edge[v2][v1]=maxWeight;
numEdges--;
return true;
}
else return false;
}
在主函数中：
case 5:
cout<<"请输入要删除边的两个顶点序号：";
cin>>e1>>e2;
g1.removeEdge(e1,e2);
cout<<g1;
break;
界面显示：
Case8 的操作是退出
case 8:
return 0;
break;
界面显示：
（五）调试与测试
在调试过程中遇到很多问题，在定义变量的时候遇到一些问题，对于全局变量还是局部变量要区分一下。

还有，对于出现某种错误，如函数重载等，都可以解决了。