数据结构实验十一：图实验.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时，输入结束。
八，测试结果
升级会员 