《哥尼斯堡的七桥问题.pdf》由会员分享，可在线阅读，更多相关《哥尼斯堡的七桥问题.pdf（17页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、 数据结构课程设计 题目：哥尼斯堡的“七桥问题”院系：班级：学号：姓名：2014-2015 年度 第 1 学期 哥尼斯堡的“七桥问题”一 题目：哥尼斯堡的“七桥问题”二 设计目标 帮助学生熟练掌握图和邻接表的使用，了解利用图能够解决生活中的那些实际问题。三 问题描述 在哥尼斯堡的一个公园里，有七座桥将普雷格尔河中两个岛及岛与河岸连接起来(如图)。问是否可能从这四块陆地中任一块出发，恰好通过每座桥一次，再回到起点?四 概要设计 1 构建用邻接表存储的图结构体：2 图的初始化 3 读入并存储一个图 G 4图 G 的深度优先搜索 5检查边的度是否全为偶数 五 详细设计（给出算法的伪码描述和流程图）总
2、体操作步骤：流程图设计：主流程图：1 构建用邻接表存储的图结构体：typedef struct int VisitedMAXV;/*顶点标记*/int EdgesMAXVMAXV;/*邻接表*/int VertexN,EdgeN;/*顶点和边数*/Graph;2 图的初始化：3 读入并存储一个图 G 4 图 G 的深度优先搜索:5 检查边的度是否全为偶数:6 主函数：代码分析：1 图的初始化：void InitializeG(Graph*G)int i,j;for(i=0;iMAXV;i+)for(j=0;jEdgesij=0;G-Visitedi=0;G-VertexN=G-EdgeN=0;
3、2 读入并存储一个图 G:void ReadG(Graph*G)/*读入并存储一个图 G*/int i,V1,V2;scanf(%d%d,&G-VertexN,&G-EdgeN);for(i=0;iEdgeN;i+)scanf(%d%d,&V1,&V2);G-EdgesV1-1V2-1=G-EdgesV2-1V1-1=1;3 图 G 的深度优先搜索:void DFS(Graph*G,int V)/*图 G 的深度优先搜索*/int W;G-VisitedV=1;/*将访问到的结点进行标记*/for(W=0;WVertexN;W+)if(G-EdgesVW&!G-VisitedW)DFS(G,W
4、);4 检查边的度是否全为偶数:int CheckG(Graph*G)/*检查边的度是否全为偶数*/int r,i,j;for(i=0;iVertexN;i+)r=0;for(j=0;jVertexN;j+)r+=G-Edgesij;if(r%2)return 0;/*发现奇数度的边则返回 0*/return 1;/*全是偶数度的边则返回 1*/5 主函数：int main()int i;Graph*G=malloc(sizeof(Graph);InitializeG(G);ReadG(G);DFS(G,0);/*检查连通性*/for(i=0;iVertexN;i+)if(!G-Visited
5、i)break;if(iVertexN)/*若有结点没被 DFS 访问到*/printf(0n);/*则图不连通*/else/*若图连通*/printf(%dn,CheckG(G);return 0;六 测试分析 白盒：查看代码完整性 黑盒：测试是否可以正确的创建，删除，插入，打印，查找等操作 七 使用说明 插入删除语句：删除 1 条内容 插入语句：插入一条信息 自动打印：打印内容 八 测试数据 注：学生在测试数据时，需要写出测试用例和截图 十课程设计总结 通过“哥尼斯堡的“七桥问题”这个题目，我认识到了图的使用，以及邻接表存储。在整个课程设计做完之后，我感觉到自己以前学到的东西还是理解不到位，通过这次课程设计反而学到了许多东西。以后我会继续保持之中状态在生活中多做练习，从而改进自己的不足！一 辈子时光在匆忙中流逝，谁都无法挽留。多少人前半生忙忙碌碌，奔波追逐，后半生回望过去，难免感叹一生的碌碌无为，恨时光短暂，荒废了最好的光阴。