中国石油大学数据结构上机实验7

《数据结构》实验报告

学号2015011512 姓名胡明禹专业数学与应用数学时间2018.5.22

一、实验题目: 实验七图的遍历

二、实验目的

1. 掌握图的逻辑结构与基本存储方法；

2. 掌握有关图的操作算法并用高级语言实现；

3. 熟练掌握图的两种搜索路径遍历方法。

三、算法设计分析

实验由8个函数共同组成。其功能描述如下：

（1）主函数：统筹调用各个函数以实现相应功能

void main()

（2）返回顶点下标函数

int LocateVex(MGraph &G,VertexType ch)

{

//返回顶点在G中顶点向量中的下标值

int i;

for ( i = 0; G.vexnum; i++ )

if ( ch == G.vexs[i] )

return i;

return -1;

}

（3）返回第一个未被访问的相邻节点下标函数

int FirstAdjVex( MGraph &G,int v)

{

//得到第一个未被访问的相邻节点下标，若无，则返回-1

int i;

for ( i = 0; i < G.vexnum; i++ )

{

if ( !visited[i] && G.arcs[v][i].adj > 0 && G.arcs[v][i].adj

}

return -1;

}

（4）返回v的（相对于w）下一个邻接顶点函数

int NextAdjVex(MGraph &G,int v,int w)

{

//返回v的（相对于w）下一个邻接顶点，若w是v的最后一个邻接顶点，返回空

int i;

for (i=w; i

{

if (!visited[i] && G.arcs[v][i].adj>0 && G.arcs[v][i].adj < INFINITY) return i;

}

return -1;

}

（5）创建有向图的邻接矩阵函数

Status CreateDG(MGraph &G)

{

//创建有向图的邻接矩阵

int i,j,k,w;

char v1,v2;

printf("请输入顶点数和边数：");

scanf("%d%d",&G.vexnum,&G.arcnum);

visited = (int *)malloc(G.vexnum*sizeof(int));

for (i = 0; i < G.vexnum; i++ )

visited[i] = 0;

printf("\n请按次序输入%d个顶点字母标号(如ABCD等)：",G.vexnum);

getchar(); //弹出缓冲区中上次最后出入的换行符，即最后按下的回车键

for (i=0;i

scanf("%c",&G.vexs[i]);

getchar(); //弹出缓冲区中上次最后出入的换行符，即最后按下的回车键

for (i=0;i

for (j=0;j

{

G.arcs[i][j].adj=INFINITY;

G.arcs[i][j].info=NULL;

}

printf("\n输入边的顶点和权值(如A B 1):\n"); //构造邻接矩阵

for (k=0;k

{

scanf("%c %c %d",&v1,&v2,&w); //输入一条有向边的起点终点和权值

i = LocateVex(G,v1); //确定顶点在G中的位置

j = LocateVex(G,v2);

G.arcs[i][j].adj = w;

getchar();//弹出缓冲区中上次最后出入的换行符，即最后按下的回车键

}

return OK;

}

（6）输出邻接矩阵函数

Status PrintArcs( MGraph &G)

{

//输出邻接矩阵

int i;

int j;

printf("邻接矩阵\n"); //按行序依次输出

for ( i = 0; i < G.vexnum; i++ )

{

for ( j = 0; j < G.vexnum; j++ )

{

if ( INFINITY == G.arcs[i][j].adj)

printf("%6s%","INF");

else

printf("%6d",G.arcs[i][j]);

}

printf("\n");

}

return OK;

}

（7）从某点开始进行深度优先遍历函数

Status DFS(MGraph &G,int v)

{

//从某点开始进行深度优先遍历

int w;

printf("\n");

visited[v] = TRUE; //访问第v个顶点

printf("%-4c",G.vexs[v]);

for ( w = FirstAdjVex(G,v); w>=0; w=NextAdjVex(G,v,w) ) if (!visited[w])

DFS(G,w); //对v尚未访问的邻接顶点w调用递归DFS return OK;

}

（8）菜单函数

void mainmenu() //输出菜单,供用户进行操作选择

{

printf("\n 菜单");

printf("\n ********************************************\n\n");

printf(" * 1.创建有向图邻接矩阵 *\n");

printf(" * 2.输出邻接矩阵 *\n");

printf(" * 3.从某点开始的深度优先遍历 *\n");

printf(" * 0.退出 *\n");

printf("\n ********************************************\n");