版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
1、数据结构实验报告实验题目:无序图的存储并分别实现深度和广度优先遍历实验目的:理解并掌握以邻接表的方式存储图,以及图的非递归的深度和广度优先遍历实验内容:首先将图的元素输入并以邻接表的方式存储,然后分别进行递归和非递归遍历。 一、需求分析1、输入的形式和输入值的范围:输入图的顶点元素和边;输入数字选择要进行的操作:深度遍历,广度遍历或结束操作。2、输出的形式:按深度或者广度优先顺序输出各节点的编号3、程序所能达到的功能:(1)以邻接表的方式存储图(2)对图进行深度优先的非递归遍历(3)对图进行广度优先的非递归遍历4、测试数据:输入各结点元素:a,b,c,d,e,f,g,h;输入图中的各边:1,2
2、 1,3 2,4 2,5 3,6 3,7 4,8 5,8操作选项 输入1进行深度优先遍历;遍历结果为:1 3 7 6 2 5 8 4操作选项 输入2进行广度优先遍历;遍历结果为:1 3 2 7 6 5 4二 概要设计(1)抽象数据类型定义:#define MaxVerNum 100/边表结点typedef struct nodeint adjvex;struct node *next;EdgeNode,*ENode;顶点表结点;typedef struct vnodechar vertex;EdgeNode *firstedge;VertexNode;typedef VertexNode Ad
3、jListMaxVerNum;定义图;typedef structAdjList adjlist;int n,e;AlGraph;AlGraph G;(2)主程序的流程:1. 根据提示输入顶点个数和边的个数;2. 输入图的各边; 3. 输入数字执行相关操作(3)其函数之间调用关系如下:main()模块 (开始创建链表)Create()创建图输入1输入2按广度优先遍历按深度优先遍历 输入0结束操作 执行结束后,重新执行判定操作和循环。三 详细设计1.元素类型#define MaxVerNum 100typedef struct nodeint adjvex;struct node *next;E
4、dgeNode,*ENode;typedef struct vnodechar vertex;EdgeNode *firstedge;VertexNode;typedef VertexNode AdjListMaxVerNum;typedef structAdjList adjlist;int n,e;AlGraph;AlGraph G;2每个模块的分析:(1)主程序模块:int main() int a,v; /创建图Create(G); printf(请选择要进行的操作:n 选择深度优先请输入1;n 选择广度优先请输入2;n结束操作请输入0n); scanf(%d,&a); while(a
5、!=0) printf(请输入开始遍历顶点的坐标n); scanf(%d,&v); if(a=1) /深度优先遍历 DfsTravel(G,v); else if(a=2) /广度优先遍历 BfsTravel(G,v); printf(请选择要进行的操作:n 选择深度优先请输入1;n 选择广度优先请输入2;n结束操作请输入0n); scanf(%d,&a); return 0;(2)深度优先遍历void DfsTravel(AlGraph &G,int v)ENode stackMaxVerNum;ENode p;int visitedMaxVerNum,top=-1,i;for(i=0;ia
6、djvex=1)p=p-next;elseprintf(%d ,p-adjvex);visitedp-adjvex=1;top+;stacktop=p;p=G.adjlistp-adjvex.firstedge;if(top!=-1) p=stacktop; top-; p=p-next;printf(n);(3)广度优先遍历void BfsTravel(AlGraph &G,int v)int visitedMaxVerNum;int queueMaxVerNum;int front=-1,rear=-1; EdgeNode *p; int i; for(i=0;iadjvex=0)prin
7、tf(%d ,p-adjvex); visitedp-adjvex=1;rear=rear+1;queuerear=p-adjvex;p=p-next;printf(n);(4)创建图void Create(AlGraph &G)int i,j,k;EdgeNode *s,*r;printf(请依次输入无向图顶点个数和边的个数n);scanf(%d,%d,&(G.n),&(G.e);getchar();printf(请输入各顶点信息n);for(i=0;iG.n;i+)scanf(%c,&(G.adjlisti.vertex);getchar(); G.adjlisti.firstedge=N
8、ULL;printf(请输入各边的信息,输入格式为i,jn); for(k=0;kadjvex=j;s-next= G.adjlisti.firstedge;G.adjlisti.firstedge=s; r=(EdgeNode*)malloc(sizeof(EdgeNode);r-adjvex=i;r-next= G.adjlistj.firstedge;G.adjlistj.firstedge=r;四 使用说明、测试分析及结果输入各结点元素:a,b,c,d,e,f,g,h;输入图中的各边:1,2 1,3 2,4 2,5 3,6 3,7 4,8 5,8操作选项 输入1进行深度优先遍历;遍历结果为:1 3 7 6 2 5 8 4操作选项 输入2进行广度优先遍历;遍历结果为:1 3 2 7 6 5 41.程序使用说明;(1)本程序的运行环境为VC6.0。(2)进入演示程序后即显示提示信息:请输入顶点个数和边的个数:2、测试结果与分析;输入各结点元素:a,b,c,d,e,f,g,h;输入图中的各边:1,2
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 夏天里的成长课件
- 算力中心建设现状分析
- 口腔护士个人简历
- 智能交通事故预警与处理技术应用方案
- 小学学困生帮扶工作计划范文(19篇)
- 元宇宙产业定位与核心价值界定
- 求职面试英文自我介绍(集合15篇)
- 数据中心持续改进与创新实施方案
- 排水防涝综合治理项目建设方案
- 硫化钠行业特征
- 2022-2023学年湖南省邵阳市武冈市八年级下期末数学试卷附答案解析
- 赞助提成方案
- 全球汽车玻璃升降器行业调查分析2024年
- 技术合作意向协议书
- 2024年高考政治重难点专练(新高考专用)热点02“一带一路”倡议提出10周年(解析版)
- 2024考研英语二试题及答案解析(word版)
- 青马工程培训班试题库附有答案
- 口服用药的健康宣教
- DB3302-T 1149-2023 中药饮片代煎服务规范
- 采耳师培训课件
- 《动态向日葵》课件
评论
0/150
提交评论