数据结构实验十一:图实验.doc
《数据结构实验十一:图实验.doc》由会员分享,可在线阅读,更多相关《数据结构实验十一:图实验.doc(5页珍藏版)》请在冰点文库上搜索。
一,实验题目
实验十一:
图实验
采用邻接表存储有向图,设计算法判断任意两个顶点间手否存在路径。
二,问题分析
本程序要求采用邻接表存储有向图,设计算法判断任意两个顶点间手否存在路径,完成这些操作需要解决的关键问题是:
用邻接表的形式存储有向图并输出该邻接表。
用一个函数实现判断任意两点间是否存在路径。
1,数据的输入形式和输入值的范围:
输入的图的结点均为整型。
2,结果的输出形式:
输出的是两结点间是否存在路径的情况。
3,测试数据:
输入的图的结点个数为:
4
输入的图的边得个数为:
3
边的信息为:
12,23,31
三,概要设计
(1)为了实现上述程序的功能,需要:
A,用邻接表的方式构建图
B,深度优先遍历该图的结点
C,判断任意两结点间是否存在路径
(2)本程序包含6个函数:
a,主函数main()
b,用邻接表建立图函数create_adjlistgraph()
c,深度优先搜索遍历函数dfs()
d,初始化遍历数组并判断有无通路函数dfs_trave()
e,输出邻接表函数print()
f,释放邻接表结点空间函数freealgraph()
各函数间关系如右图所示:
create_adjlistgraph()
dfs()
dfs_trave()
main()
print()
freealgraph()
四,详细设计
(1)邻接表中的结点类型定义:
typedefstructarcnode{
intadjvex;
arcnode*nextarc;
}arcnode;
(2)邻接表中头结点的类型定义:
typedefstruct{
charvexdata;
arcnode*firstarc;
}adjlist;
(3)邻接表类型定义:
typedefstruct{
adjlistvextices[max];
intvexnum,arcnum;
}algraph;
(4)深度优先搜索遍历函数伪代码:
intdfs(algraph*alg,inti,intn){
arcnode*p;visited[i]=1; p=alg->vextices[i].firstarc;
while(p!
=NULL){if(visited[p->adjvex]==0){
if(p->adjvex==n){flag=1; }
dfs(alg,p->adjvex,n);
if(flag==1) return1;}
p=p->nextarc; }
return0;}
(5)初始化遍历数组并判断有无通路函数伪代码:
voiddfs_trave(algraph*alg,intx,inty){
inti;
for(i=0;i<=alg->vexnum;i++)visited[i]=0;
dfs(alg,x,y);}
五,源代码
#include"stdio.h"
#include"stdlib.h"
#include"malloc.h"
#definemax100
typedefstructarcnode{//定义邻接表中的结点类型
intadjvex;//定点信息
arcnode*nextarc;//指向下一个结点的指针nextarc
}arcnode;
typedefstruct{//定义邻接表中头结点的类型
charvexdata;//头结点的序号
arcnode*firstarc;//定义一个arcnode型指针指向头结点所对应的下一个结点
}adjlist;
typedefstruct{//定义邻接表类型
adjlistvextices[max];//定义表头结点数组
intvexnum,arcnum;//定点个数和弧的个数
}algraph;
algraph*create_adjlistgraph(){//建立邻接表函数
intn,e,i,j,k;
arcnode*p;//定义一个邻接表结点型指针变量p
algraph*al;//定义邻接表表头结点指针al
al=(algraph*)malloc(sizeof(algraph));//为邻接表结点申请空间
printf("请输入节点数:
\n");
scanf("%d",&n);//输入结点数
for(i=0;i<=n;i++){
al->vextices[i].vexdata=(char)i;//给头结点赋值
al->vextices[i].firstarc=NULL;//初始化头结点
}
printf("请输入边数:
\n");
scanf("%d",&e);//输入边得数目
printf("请输入弧的信息:
\n");
for(i=0;i printf("请输入边得两个结点:
");
scanf("%d%d",&j,&k);//输入边的两个结点
p=(arcnode*)malloc(sizeof(arcnode));//申请新的结点
p->adjvex=k;//将k赋值给新申请的结点
p->nextarc=al->vextices[j].firstarc;//使新结点指向该头结点所指向的下一个结点
al->vextices[j].firstarc=p;//使头结点指向新结点
}
al->vexnum=n;//将顶点数n给al->vexnum
al->arcnum=e;//将边数e给al->arcnum
returnal;//返回该邻接表
}
voidprint(algraph*alg){//输出邻接表
inti;
arcnode*p;//定义一个邻接表结点型指针变量p
printf("该图的邻接表输出为:
\n");
for(i=1;i<=alg->vexnum;i++){//当在结点个数范围内时
printf("%d-",alg->vextices[i].vexdata);//输出i头结点的值
p=alg->vextices[i].firstarc;//把i头结点所指的第一个结点给p
while(p!
=NULL){//当p不为空时
printf("%d-",p->adjvex);//输出给结点
p=p->nextarc;//p指向下一个结点
}
printf("--\n");
}}
voidfreealgraph(algraph*alg){//释放邻接表结点空间函数
inti;
arcnode*p,*q;//定义两个邻接表结点型指针变量p,q
for(i=0;i<=alg->vexnum;i++){//当结点个数不超出范围时
p=alg->vextices[i].firstarc;//p指向i头结点所对应的第一个结点
while(p!
=NULL){//当p不为空时
q=p->nextarc;//q指向p的下一个结点
free(p);//释放p
p=q;//将q赋给p
}
}
}
intvisited[max];//定义深度优先搜索遍历数组
intflag=0;//设置标志,用来判断两点间是否为通路
intdfs(algraph*alg,inti,intn){//深度优先搜索遍历函数
arcnode*p;//定义邻接表结点类型指针p
visited[i]=1;//将顶点i设置为已访问
p=alg->vextices[i].firstarc;//使p指向i头结点所指的第一个结点
while(p!
=NULL)//当p不为空时
{
if(visited[p->adjvex]==0)//如果p结点未被访问
{
if(p->adjvex==n)//如果n=p结点的值
{
flag=1;//则将标志位设置为1
}
dfs(alg,p->adjvex,n);//递归调用深度优先搜索遍历函数
if(flag==1)//如果已被访问
return1;//则返回1
}
p=p->nextarc;//p指向下一个结点
}
return0;
}
voiddfs_trave(algraph*alg,intx,inty){//初始化遍历数组并判断有无通路函数
inti;
for(i=0;i<=alg->vexnum;i++)
visited[i]=0;
dfs(alg,x,y);
}
intmain(){//主函数
intm,n;
algraph*alg;
alg=create_adjlistgraph();//创建图
print(alg);//输出该图
printf("请输入任意要判定有无通路的两个顶点(输入(-1-1)时退出):
");
scanf("%d%d",&m,&n);
while(m!
=-1&&n!
=-1){
dfs_trave(alg,m,n);//调用初始化遍历数组并判断有无通路函数
if(flag==1)
printf("顶点%d和%d之间存在路径\n",m,n);
else
{
printf("顶点%d和%d之间不存在路径\n",m,n);
flag=0;
}
printf("请输入任意要判定有无通路的两个顶点(输入(-1-1)时退出):
");
scanf("%d%d",&m,&n);
}
freealgraph(alg);//释放邻接表结点空间
return0;
}
六,调试分析
在函数调用时,弄错了实参和形参的含义,导致出现错误。
七,使用手册
用户在使用时,根据界面提示,首先输入结点的个数,再输入边得个数,之后输入弧的信息,这时,图输入完成,输出该图的邻接表。
再根据提示,输入任意两个结点,判断他们之间是否有路径。
当输入的两结点为-1-1时,输入结束。
八,测试结果