中国石油大学数据结构上机实验7.docx
《中国石油大学数据结构上机实验7.docx》由会员分享,可在线阅读,更多相关《中国石油大学数据结构上机实验7.docx(14页珍藏版)》请在冰点文库上搜索。
中国石油大学数据结构上机实验7
《数据结构》实验报告
学号
2015011512
姓名
胡明禹
专业
数学与应用数学
时间
2018.5.22
一、实验题目:
实验七图的遍历
二、实验目的
1.掌握图的逻辑结构与基本存储方法;
2.掌握有关图的操作算法并用高级语言实现;
3.熟练掌握图的两种搜索路径遍历方法。
三、算法设计分析
实验由8个函数共同组成。
其功能描述如下:
(1)主函数:
统筹调用各个函数以实现相应功能
voidmain()
(2)返回顶点下标函数
intLocateVex(MGraph&G,VertexTypech)
{
//返回顶点在G中顶点向量中的下标值
inti;
for(i=0;G.vexnum;i++)
if(ch==G.vexs[i])
returni;
return-1;
}
(3)返回第一个未被访问的相邻节点下标函数
intFirstAdjVex(MGraph&G,intv)
{
//得到第一个未被访问的相邻节点下标,若无,则返回-1
inti;
for(i=0;i{
if(!
visited[i]&&G.arcs[v][i].adj>0&&G.arcs[v][i].adjreturni;
}
return-1;
}
(4)返回v的(相对于w)下一个邻接顶点函数
intNextAdjVex(MGraph&G,intv,intw)
{
//返回v的(相对于w)下一个邻接顶点,若w是v的最后一个邻接顶点,返回空
inti;
for(i=w;i{
if(!
visited[i]&&G.arcs[v][i].adj>0&&G.arcs[v][i].adjreturni;
}
return-1;
}
(5)创建有向图的邻接矩阵函数
StatusCreateDG(MGraph&G)
{
//创建有向图的邻接矩阵
inti,j,k,w;
charv1,v2;
printf("请输入顶点数和边数:
");
scanf("%d%d",&G.vexnum,&G.arcnum);
visited=(int*)malloc(G.vexnum*sizeof(int));
for(i=0;ivisited[i]=0;
printf("\n请按次序输入%d个顶点字母标号(如ABCD等):
",G.vexnum);
getchar();//弹出缓冲区中上次最后出入的换行符,即最后按下的回车键
for(i=0;iscanf("%c",&G.vexs[i]);
getchar();//弹出缓冲区中上次最后出入的换行符,即最后按下的回车键
for(i=0;ifor(j=0;j{
G.arcs[i][j].adj=INFINITY;
G.arcs[i][j].info=NULL;
}
printf("\n输入边的顶点和权值(如AB1):
\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();//弹出缓冲区中上次最后出入的换行符,即最后按下的回车键
}
returnOK;
}
(6)输出邻接矩阵函数
StatusPrintArcs(MGraph&G)
{
//输出邻接矩阵
inti;
intj;
printf("邻接矩阵\n");//按行序依次输出
for(i=0;i{
for(j=0;j{
if(INFINITY==G.arcs[i][j].adj)
printf("%6s%","INF");
else
printf("%6d",G.arcs[i][j]);
}
printf("\n");
}
returnOK;
}
(7)从某点开始进行深度优先遍历函数
StatusDFS(MGraph&G,intv)
{
//从某点开始进行深度优先遍历
intw;
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
returnOK;
}
(8)菜单函数
voidmainmenu()//输出菜单,供用户进行操作选择
{
printf("\n菜单");
printf("\n********************************************\n\n");
printf("*1.创建有向图邻接矩阵*\n");
printf("*2.输出邻接矩阵*\n");
printf("*3.从某点开始的深度优先遍历*\n");
printf("*0.退出*\n");
printf("\n********************************************\n");
}
四、实验测试结果及结果分析
(一)测试结果(此处给出程序运行截图)
四、实验程序代码(该部分请加注释)
#include"stdio.h"
#include"stdlib.h"
#include"malloc.h"
#include
#defineOK1
#defineTRUE1
#defineINFINITYINT_MAX//最大值无穷
#defineMAX_VERTEX_NUM20//最大顶点个数
typedefintInfoType;
typedefintVRType;
typedefcharVertexType;
typedefintStatus;
int*visited;//记录顶点是否被访问
typedefstructArcCell
{
VRTypeadj;
InfoType*info;//该边相关信息的指针
}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
typedefstruct
{
VertexTypevexs[MAX_VERTEX_NUM];//顶点向量
AdjMatrixarcs;//邻接矩阵
intvexnum,arcnum;//图的顶点数和有向边数
}MGraph;
intLocateVex(MGraph&G,VertexTypech)
{
//返回顶点在G中顶点向量中的下标值
inti;
for(i=0;G.vexnum;i++)
if(ch==G.vexs[i])
returni;
return-1;
}
intFirstAdjVex(MGraph&G,intv)
{
//得到第一个未被访问的相邻节点下标,若无,则返回-1
inti;
for(i=0;i{
if(!
visited[i]&&G.arcs[v][i].adj>0&&G.arcs[v][i].adjreturni;
}
return-1;
}
intNextAdjVex(MGraph&G,intv,intw)
{
//返回v的(相对于w)下一个邻接顶点,若w是v的最后一个邻接顶点,返回空
inti;
for(i=w;i{
if(!
visited[i]&&G.arcs[v][i].adj>0&&G.arcs[v][i].adjreturni;
}
return-1;
}
StatusCreateDG(MGraph&G)
{
//创建有向图的邻接矩阵
inti,j,k,w;
charv1,v2;
printf("请输入顶点数和边数:
");
scanf("%d%d",&G.vexnum,&G.arcnum);
visited=(int*)malloc(G.vexnum*sizeof(int));
for(i=0;ivisited[i]=0;
printf("\n请按次序输入%d个顶点字母标号(如ABCD等):
",G.vexnum);
getchar();//弹出缓冲区中上次最后出入的换行符,即最后按下的回车键
for(i=0;iscanf("%c",&G.vexs[i]);
getchar();//弹出缓冲区中上次最后出入的换行符,即最后按下的回车键
for(i=0;ifor(j=0;j{
G.arcs[i][j].adj=INFINITY;
G.arcs[i][j].info=NULL;
}
printf("\n输入边的顶点和权值(如AB1):
\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();//弹出缓冲区中上次最后出入的换行符,即最后按下的回车键
}
returnOK;
}
StatusPrintArcs(MGraph&G)
{
//输出邻接矩阵
inti;
intj;
printf("邻接矩阵\n");//按行序依次输出
for(i=0;i{
for(j=0;j{
if(INFINITY==G.arcs[i][j].adj)
printf("%6s%","INF");
else
printf("%6d",G.arcs[i][j]);
}
printf("\n");
}
returnOK;
}
StatusDFS(MGraph&G,intv)
{
//从某点开始进行深度优先遍历
intw;
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
returnOK;
}
voidmainmenu()//输出菜单,供用户进行操作选择
{
printf("\n菜单");
printf("\n********************************************\n\n");
printf("*1.创建有向图邻接矩阵*\n");
printf("*2.输出邻接矩阵*\n");
printf("*3.从某点开始的深度优先遍历*\n");
printf("*0.退出*\n");
printf("\n********************************************\n");
}
voidmain()//主函数
{
MGraphG;
intchoose;
intv;
while
(1)
{
mainmenu();
printf("\n请输入你的选择:
");
scanf("%d",&choose);
switch(choose)
{
case1:
//在此插入创建有向图邻接矩阵函数
system("cls");
CreateDG(G);
system("PAUSE");
system("cls");
break;
case2:
//在此插入输出邻接矩阵函数
system("cls");
PrintArcs(G);
printf("\n");
system("PAUSE");
system("cls");
break;
case3:
//在此调用从某点开始深度优先遍历函数
system("cls");
printf("请输入开始结点:
");
scanf("%d",&v);
DFS(G,v);
system("PAUSE");
system("cls");
break;
case0:
//退出
exit(0);
break;
default:
//输入非法,提示用户重新输入
printf("\n输入错误,重新输入!
\n");
}
}
}