当前位置:文档之家› 数据结构实验十一:图实验

数据结构实验十一:图实验

algraph *create_adjlistgraph(){ //建立邻接表函数
int n,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");
printf("%d-",alg->vextices[i].vexdata); //输出i头结点的值
p=alg->vextices[i].firstarc; //把i头结点所指的第一个结点给p
while(p!=NULL){ //当p不为空时
printf("%d-",p->adjvex); //输出给结点
scanf("%d",&e); //输入边得数目
printf("请输入弧的信息:\n");
for(i=0;i<e;i++){
printf("请输入边得两个结点:");
scanf("%d%d",&j,&k); //输入边的两个结点
p=(arcnode *)malloc(sizeof(arcnode)); //申请新的结点
return 1; //则返回1
}
p=p->nextarc; //p指向下一个结点
}
return 0;
}
void dfs_trave(algraph *alg,int x,int y){ //初始化遍历数组并判断有无通路函数
int i;
for(i=0;i<=alg->vexnum;i++)
visited[i]=0;
int flag=0; //设置标志,用来判断两点间是否为通路
int dfs(algraph *alg,int i,int n){ //深度优先搜索遍历函数
arcnode *p; //定义邻接表结点类型指针p
visited[i]=1; //将顶点i设置为已访问
p=alg->vextices[i].firstarc; //使p指向i头结点所指的第一个结点
a,主函数main()
b,用邻接表建立图函数create_adjlistgraph()
c,深度优先搜索遍历函数dfs()
d,初始化遍历数组并判断有无通路函数dfs_trave()
e,输出邻接表函数print()
f,释放邻接表结点空间函数freealgraph()
各函数间关系如右图所示:
四,详细设计
(1)邻接表中的结点类型定义:
一,实验题目
实验十一:图实验
采用邻接表存储有向图,设计算法判断任意两个顶点间手否存在路径。
二,问题分析
本程序要求采用邻接表存储有向图,设计算法判断任意两个顶点间手否存在路径,完成这些操作需要解决的关键问题是:用邻接表的形式存储有向图并输出该邻接表。用一个函数实现判断任意两点间是否存在路径。
1,数据的输入形式和输入值的范围:输入的图的结点均为整型。
八,测试结果
p->adjvex=k; //将k赋值给新申请的结点
p->nextarc=al->vextices[j].firstarc; //使新结点指向该头结点所指向的下一个结点
al->vextices[j].firstarc=p; //使头结点指向新结点
}
al->vexnum=n; //将顶点数n给al->vexnum
adjlist vextices[max];
int vexnum,arcnum;
}algraph;
(4)深度优先搜索遍历函数伪代码:
int dfs(algraph *alg,int i,int n){
arcnode *p; visited[i]=1;p=alg->vextices[i].firstarc;
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) //如果已被访问
p=alg->vextices[i].firstarc; //p指向i头结点所对应的第一个结点
while(p!=NULL){ //当p不为空时
q=p->nextarc; //q指向p的下一个结点
free(p); //释放p
p=q; //将q赋给p
}
}
}
int visited[max]; //定义深度优先搜索遍历数组
p=p->nextarc; //p指向下一个结点
}
printf("--\来自");} }void freealgraph(algraph *alg){ //释放邻接表结点空间函数
int i;
arcnode *p,*q; //定义两个邻接表结点型指针变量p,q
for(i=0;i<=alg->vexnum;i++){ //当结点个数不超出范围时
while(p!=NULL){if(visited[p->adjvex]==0){
if(p->adjvex==n){flag=1;}
dfs(alg,p->adjvex,n);
if(flag==1)return 1;}
p=p->nextarc;}
return 0; }
(5)初始化遍历数组并判断有无通路函数伪代码:
arcnode *firstarc; //定义一个arcnode型指针指向头结点所对应的下一个结点
}adjlist;
typedef struct{ //定义邻接表类型
adjlist vextices[max]; //定义表头结点数组
int vexnum,arcnum; //定点个数和弧的个数
}algraph;
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); //释放邻接表结点空间
return 0;
}
六,调试分析
在函数调用时,弄错了实参和形参的含义,导致出现错误。
七,使用手册
用户在使用时,根据界面提示,首先输入结点的个数,再输入边得个数,之后输入弧的信息,这时,图输入完成,输出该图的邻接表。再根据提示,输入任意两个结点,判断他们之间是否有路径。当输入的两结点为-1 -1时,输入结束。
typedef struct arcnode{
int adjvex;
arcnode *nextarc;
}arcnode;
(2)邻接表中头结点的类型定义:
typedef struct{
char vexdata;
arcnode *firstarc;
}adjlist;
(3)邻接表类型定义:
typedef struct{
void dfs_trave(algraph *alg,int x,int y){
int i;
for(i=0;i<=alg->vexnum;i++)visited[i]=0;
dfs(alg,x,y); }
五,源代码
#include "stdio.h"
#include "stdlib.h"
#include "malloc.h"
dfs(alg,x,y);
}
int main(){ //主函数
int m,n;
algraph *alg;
alg=create_adjlistgraph(); //创建图
print(alg); //输出该图
printf("请输入任意要判定有无通路的两个顶点(输入(-1 -1)时退出):");
scanf("%d%d",&m,&n);
#define max 100
typedef struct arcnode{ //定义邻接表中的结点类型
int adjvex; //定点信息
arcnode *nextarc; //指向下一个结点的指针nextarc
}arcnode;
typedef struct{ //定义邻接表中头结点的类型
相关主题