(完整word版)数据结构与算法课程设计-求解最短路径(word文档良心出品).doc

综合实验任务书姓名学号班级课程名称数据结构与算法课程性质专业必修课设计时间2008年12月15日——2009年1月2日设计名称求解最短路径设计要求能够完成以下功能：1)建立图2)实现Dijkstra单源点最短路径算法3)实现Floyd算法，实现求解每对结点之间的最短路径问题4)有错误提示功能，例如非法输入时，会有报错。设计思路与设计过程根据系统功能要求，可以将问题解决分为以下步骤：（1）分析问题实质；（2）抽取问题实质，进行抽象；（3）确定数据结构；（4）选择合适的算法，进行算法设计；（5）完成系统的应用模块；（6）功能调试；（7）修改不完善的功能，增强程序健壮性；（8）根据实际添加所需功能；计划与进度由简单到复杂，争取15天左右完成任课教师意见说明设计名称：求解最短路径日期：2009年1月2日设计内容：设计一个系统，实现以下功能：1：建立图2：实现Dijkstra单源点最短路径算法3：实现Floyd算法，实现求解每对结点之间的最短路径问题4：退出系统设计目的与要求：（1）达到理论与实际应用相结合，能够根据数据对象的特性，学会数据组织的方法，能把现实世界中的实际问题在计算机内部表示出来，并培养良好的程序设计技能。（2）在实践中认识为什么要学习数据结构，掌握数据结构、程序设计语言程序设计技术、之间的关系。通过设计，在数据结构的逻辑特性和物理表示、数据结构的选择应用、算法的设计及其实现等方面加深对课程基本内容的理解和综合运用。设计环境或器材、原理与说明：MicrosoftVisualC++6.0设计过程（步骤）或程序代码：#include<stdio.h>#include<iostream.h>#defineMAX10000#defineMAXLEN20#defineMAX_VERTEX_NUM20typedefstruct{charvexs[MAX_VERTEX_NUM];//顶点表intarcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM];//邻接矩阵intvexnum,arcnum;//图的顶点数和弧数}MGRAPH;MGRAPHcreate_mgraph()//建立有向图的邻接矩阵结构{inti,j,k,h;MGRAPHmg;printf("\n\n输入顶点数和边数(用逗号隔开):");while(1)//判断输入是否合法{if(scanf("%d,%d",&i,&j)==2&&getchar()=='\n'&&i<MAX_VERTEX_NUM&&j<MAX_VERTEX_NUM)break;else{while(getchar()!='\n');cout<<"输入不合法！"<<endl;printf("请重新输入顶点数和边数(用逗号隔开):");}}mg.vexnum=i;//存放顶点数在mg.vexnum中mg.arcnum=j;//存放边点数在mg.arcnum中fflush(stdin);//清空缓冲区for(i=0;i<mg.vexnum;i++){printf("输入顶点%d的值:",i+1);//输入顶点的值while(1)//判断选择是否合法{if(scanf("%d",&mg.vexs[i])==1&&getchar()=='\n')break;else{while(getchar()!='\n');cout<<"输入不合法！"<<endl;printf("请重新输入顶点%d的值:",i+1);}}fflush(stdin);}for(i=0;i<mg.vexnum;i++)//邻接矩阵初始化for(j=0;j<mg.vexnum;j++)mg.arcs[i][j]=MAX;for(k=1;k<=mg.arcnum;k++){printf("输入第%d条边的起始顶点和终止顶点(用逗号隔开):",k);while(1)//输入弧的起始顶点和终止顶点，并判断输入是否合法{/*scanf("%d,%d",&i,&j)的作用：判断是否成功输入如果i和j都被成功读入，那么scanf的返回值就是2如果只有i被成功读入，返回值为1如果i和j都未被成功读入，返回值为0*/if(scanf("%d,%d",&i,&j)==2&&getchar()=='\n'&&i>0&&i<=mg.vexnum&&j>0&&j<=mg.vexnum)break;else{while(getchar()!='\n');cout<<"输入不合法！"<<endl;printf("请重新输入起始顶点和终止顶点(用逗号隔开):");}}fflush(stdin);while(i<1||i>mg.vexnum||j<1||j>mg.vexnum){printf("输入错，重新输入:");scanf("%d,%d",&i,&j);}