数据结构及算法--图结构及操作实验报告.doc

《数据结构与算法分析》
课 程 实 验 报 告
【实验目的】
1. 理解图形结构的逻辑和存储特点。
2. 掌握图形结构遍历递归算法。

【实验内容】
1. 用邻接矩阵或者邻接表存储一个图形结构。
2. 采用深度或者广度优先搜索算法，遍历一个图，并输出遍历结果。

【实验方式】
个人实验。
【实验设备与环境】
PC机，Windows XP操作系统，VC++6.0开发环境。
【数据结构及函数定义】
（1）类的定义：类的数据成员，成员函数
　　．．．．．．．．．．．．．．．．．．．

（2）主函数main（） 实现初始化操作，完成对子函数的调用
．．．．．．．．．．．．．．．．．．．

（3）子函数
　　　．．．．．．．．．．．．．．．．．．．

。
【测试数据与实验结果】
（ 请用截图的方式展示实验结果，并辅以必要的文字说明）

【源程序清单】
（请附上源程序）
#include<iostream>
using namespace std;
#include<string.h>

class Graph
{
public:
char Vtx[20];
double AdjMtx[20][20];
int CurrentVnum;
int CurrentEnum;
Graph(){CurrentVnum=CurrentEnum=0;}
int first_adj(int v);
int next_adj(int v1,int v2);
void visite(int v);
void DFS();
void DFS(int v,int visited[]);
~Graph(){}
};

int Graph::first_adj(int v)
{
for(int v1=0;v1<CurrentVnum;v1++)
if(AdjMtx[v][v1]>0)
return v1;
return -1;
}

int Graph::next_adj(int v1,int v2)
{
for(int vn=v2+1;vn<CurrentVnum;vn++)
if(AdjMtx[v1][vn]>0)
return vn;
return -1;
}

void Graph::visite(int v)
{
cout<<Vtx[v]<<" ";
}

void Graph::DFS()
{
int *visited=new int[CurrentVnum];
for(int i=0;i<CurrentVnum;i++)
visited[i]=0;
for(i=0;i<CurrentVnum;i++)
{
if(visited[i]==0)
DFS(i,visited);
}
delete[] visited;
}

void Graph::DFS(int v,int visited[])
{
visite(v);
visited[v]=1;
int w=first_adj(v);
while(w!=-1)
{
if(!visited[w])
DFS(w,visited);
w=next_adj(v,w);
}
}

int LocateVex(Graph G,char u)
{
int i;
for(i=0;i<G.CurrentVnum;i++)
if(u==G.Vtx[i])
return i;
return -1;
}

void creat(Graph &G)
{
int i,j,k;
char va,vb;
cout<<"请输入图的顶点数,弧数:";
cin>>G.CurrentVnum>>G.CurrentEnum;
cout<<"请输入"<<G.CurrentVnum<<"个顶点的值:";
for(i=0;i<G.CurrentVnum;i++)
cin>>G.Vtx[i];
for(i=0;i<G.CurrentVnum;i++)
for(j=0;j<G.CurrentVnum;j++)
G.AdjMtx[i][j]=0;
cout<<"请输入"<<G.CurrentEnum<<"条弧的弧尾,弧头(以空格作为间隔):\n";
for(k=0;k<G.CurrentEnum;k++)
{
cin>>va>>vb;
i=LocateVex(G,va);
j=LocateVex(G,vb);
if(i!=j)
{
G.AdjMtx[i][j]=1;
G.AdjMtx[j][i]=1;
}
else G.AdjMtx[i][j]=1;
}
}

void main()
{
Graph G;
creat(G);
cout<<"深度优先搜索序列:"<<endl;
G.DFS();
cout<<endl;