数据结构08图的基本操作.docx
- 文档编号:3217477
- 上传时间:2023-05-05
- 格式:DOCX
- 页数:15
- 大小:52.16KB
数据结构08图的基本操作.docx
《数据结构08图的基本操作.docx》由会员分享,可在线阅读,更多相关《数据结构08图的基本操作.docx(15页珍藏版)》请在冰点文库上搜索。
数据结构08图的基本操作
附录实验报告参考规范
《数据结构》实验报告
院系____________________专业____网络工程________________
姓名___林桢曦_________学号___106052010235_________电话____________
__________级__________班_______年____月____日
1.实验题目
图的基本操作
2.需求分析
编写图基本操作函数,建立图的邻接表,邻接矩阵。
邻接表表示的图的递归深度优先遍历,邻接矩阵表示的图的递归深度优先遍历,邻接表表示的图的广度优先遍历,邻接矩阵表示的图的广度优先遍历。
并调用上述函数实现相关操作。
3.概要设计
(1)为了实现上述程序功能,需要定义一个简化的线性表抽象数据类型:
ADTGraph{
数据对象V:
V是具有相同特性的数据元素的集合,称为顶点集
数据关系R:
R={VR}VR={
谓词P(v,w)定义了弧
基本操作:
Create_Graph(LGraphlg,MGraphmg)
操作前提:
lg是一个邻接表表示的图,mg是一个邻接矩阵表示的图
操作结果:
建立图的邻接表,邻接矩阵
LDFS(LGraphg,inti)
操作前提:
g是一个已初始化的邻接表表示的图
操作结果:
对图g进行递归深度优先遍历
MDFS(MGraphg,inti,intvn)
操作前提:
g是一个已初始化的邻接矩阵表示的图
操作结果:
对图进行递归深度优先遍历
LBFS(LGraphg,ints,intn)
操作前提:
g是一个已初始化的邻接表表示的图
操作结果:
对图进行递归深度优先遍历
MBFS(MGraphg,ints,intn)
操作前提:
g是一个已初始化的邻接矩阵表示的图
操作结果:
对图进行递归深度优先遍历
}
(2)本程序包含6个函数:
•主函数main()
•建立图的邻接表,邻接矩阵函数Create_Graph()
•邻接表表示的图的递归深度优先遍历函数LDFS()
•邻接矩阵表示的图的递归深度优先遍历函数MDFS()
•邻接表表示的图的广度优先遍历LBFS()
•邻接矩阵表示的图的广度优先遍历MBFS()
各函数间调用关系如下:
主函数调用其他函数
(3)主函数的伪码
main()
{
定义变量LGraphlg;
MGraphmg;
intn,i;
令n=Create_Graph(lg,mg);
For循环(i=0;i visited[i]=0; printf("\n邻接表表示的图的递归深度优先遍历\n"); 调用LDFS(lg,0); getch(); For循环(i=0;i visited[i]=0; printf("\n邻接矩阵表示的图的递归深度优先遍历\n"); 调用MDFS(mg,0,n); getch(); printf("\n邻接表表示的图的广度优先遍历\n"); 调用LBFS(lg,0,n); getch(); printf("\n邻接矩阵表示的图的广度优先遍历\n"); 调用MBFS(mg,0,n);} } 4.详细设计 (1)类型定义 typedefstructnode{ intvno; structnode*next; }EdgeNode; typedefEdgeNode*LGraph[MAX]; typedefintMGraph[MAX][MAX]; 基本操作的伪码算法 1.建立图的邻接表,邻接矩阵 Create_Graph(LGraphlg,MGraphmg){ 定义变量intvn,en,k,i,j; EdgeNode*p; While循环 (1){ vn=en=0; printf("输入图的顶点数[1-10]\n"); 调用fflush(stdin); scanf("%d",&vn); 如果(vn<1||vn>10) continue; printf("输入图的边数[0-%d]\n",vn*(vn-1)/2); scanf("%d",&en); 如果(en>=0&&en<=vn*(vn-1)/2) break; } For循环(k=0;k lg[k]=NULL; For循环(k=0;k For循环(i=0;i mg[k][i]=0; For循环(k=0;k i=j=-1; printf("输入一对相连的两条边[1-%d]的顶点: ",vn); scanf("%d%d",&i,&j); 如果(i<1||j<1||i>vn||j>vn){ printf("输入错误,边范围为[1-%d]\n",vn); 继续; } k++; i--; j--; p=(EdgeNode*)malloc(sizeof(EdgeNode)); p->vno=j; p->next=lg[i]; lg[i]=p; p=(EdgeNode*)malloc(sizeof(EdgeNode)); p->vno=i; p->next=lg[j]; lg[j]=p; mg[i][j]=mg[j][i]=1; } 返回vn;} 2.递归深度优先遍历输出图的邻接表 LDFS(LGraphg,inti) { 定义变量EdgeNode*t; printf("%4d",i+1); visited[i]=1; t=g[i]; While循环(t! =NULL){ 如果(visited[t->vno]==0) 调用LDFS(g,t->vno); t=t->next; } } 3.递归深度优先遍历输出图的邻接矩阵 MDFS(MGraphg,inti,intvn) { 定义变量intj; printf("%4d",i+1); visited[i]=1; For循环(j=0;j 如果(g[i][j]==1&&visited[j]==0) 调用MDFS(g,j,vn); } } 4.图的广度优先遍历输出图的邻接表 LBFS(LGraphg,ints,intn){ 定义变量inti,v,w,head,tail; EdgeNode*t; For循环(i=0;i visited[i]=0; head=tail=0; 输出("%4d",s+1); visited[s]=1; queue[tail]=s; While循环(head v=queue[head++]; For循环(t=g[v];t! =NULL;t->next){ w=t->vno; 如果(visited[w]==0){ 输出("%4d",w+1); visited[w]=1; queue[tail++]=w; } } } } 5.图的广度优先遍历输出图的邻接矩阵 MBFS(MGraphg,ints,intn){ 定义变量inti,j,v,head,tail; For循环(i=0;i visited[i]=0; head=tail=0; 输出("%4d",s+1); visited[s]=1; queue[tail++]=s; While循环(head v=queue[head++]; For循环(j=0;j 如果(g[v][j]==1&&visited[j]==0){ 输出("%4d",j+1); visited[j]=1; queue[tail++]=j; } } } } 5.调试分析 调试中遇到分号在中文输入情况下输入,调试不通过,还有空指针问题。 (略) 6.使用说明 按要求输入图的顶点数,在输入图的边数,接着输入相连两条边的顶点,输入范围屏幕有显示,最后屏幕显示四种遍历结果。 7.测试结果 8.参考文献 数据结构 9.附录 源程序文件如下: #include"stdio.h" #include"stdlib.h" #include"conio.h" #defineMAX10 typedefstructnode{ intvno; structnode*next; }EdgeNode; typedefEdgeNode*LGraph[MAX]; typedefintMGraph[MAX][MAX]; intvisited[MAX]; intqueue[MAX]; intCreate_Graph(LGraphlg,MGraphmg) { intvn,en,k,i,j; EdgeNode*p; while (1){ vn=en=0; printf("输入图的顶点数[1-10]\n"); fflush(stdin); scanf("%d",&vn); if(vn<1||vn>10) continue; printf("输入图的边数[0-%d]\n",vn*(vn-1)/2); scanf("%d",&en); if(en>=0&&en<=vn*(vn-1)/2) break; } for(k=0;k lg[k]=NULL; for(k=0;k for(i=0;i mg[k][i]=0; for(k=0;k i=j=-1; printf("输入一对相连的两条边[1-%d]的顶点: ",vn); scanf("%d%d",&i,&j); if(i<1||j<1||i>vn||j>vn){ printf("输入错误,边范围为[1-%d]\n",vn); continue; } k++; i--; j--; p=(EdgeNode*)malloc(sizeof(EdgeNode)); p->vno=j; p->next=lg[i]; lg[i]=p; p=(EdgeNode*)malloc(sizeof(EdgeNode)); p->vno=i; p->next=lg[j]; lg[j]=p; mg[i][j]=mg[j][i]=1; } returnvn; } voidLDFS(LGraphg,inti) { EdgeNode*t; printf("%4d",i+1); visited[i]=1; t=g[i]; while(t! =NULL){ if(visited[t->vno]==0) LDFS(g,t->vno); t=t->next; } } voidMDFS(MGraphg,inti,intvn) { intj; printf("%4d",i+1); visited[i]=1; for(j=0;j if(g[i][j]==1&&visited[j]==0) MDFS(g,j,vn); } } voidLBFS(LGraphg,ints,intn) { inti,v,w,head,tail; EdgeNode*t; for(i=0;i visited[i]=0; head=tail=0; printf("%4d",s+1); visited[s]=1; queue[tail]=s; while(head v=queue[head++]; for(t=g[v];t! =NULL;t->next){ w=t->vno; if(visited[w]==0){ printf("%4d",w+1); visited[w]=1; queue[tail++]=w; } } } } voidMBFS(MGraphg,ints,intn) { inti,j,v,head,tail; for(i=0;i visited[i]=0; head=tail=0; printf("%4d",s+1); visited[s]=1; queue[tail++]=s; while(head v=queue[head++]; for(j=0;j if(g[v][j]==1&&visited[j]==0){ printf("%4d",j+1); visited[j]=1; queue[tail++]=j; } } } } voidmain() { LGraphlg; MGraphmg; intn,i; n=Create_Graph(lg,mg); for(i=0;i visited[i]=0; printf("\n邻接表表示的图的递归深度优先遍历\n"); LDFS(lg,0); getch(); for(i=0;i visited[i]=0; printf("\n邻接矩阵表示的图的递归深度优先遍历\n"); MDFS(mg,0,n); getch(); printf("\n邻接表表示的图的广度优先遍历\n"); LBFS(lg,0,n); getch(); printf("\n邻接矩阵表示的图的广度优先遍历\n"); MBFS(mg,0,n); } 注意事项: ●每位同学必须完成实验任务,并提交实验报告。 杜绝抄袭和拷贝,一经发现该次实验雷同报告均以零分计。 ●请将实验报告以电子文档提交,“网络工程”专业请发送到fjsdwlgc@信箱中,“电子信息”专业请发送到fjsddzxx@信箱中,请附上程序清单.C源程序文件、和实验报告WORD文档两部分,以打包压缩文件形式提交,每次实验为一个文件夹的打包压缩文件,文件夹名统一为*⊙⊙⊙? ? .rar或*⊙⊙⊙? ? .zip,其中*为你的学号(全部号码),⊙⊙⊙为你中文姓名,? ? 分别为01,02,03……11表示第几次实验。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 08 基本 操作