数据结构课程设计报告(含流程图).doc

郑州轻工业学院课 程 设 计 任 务 书题目 校园导游程序 专业、班级网络工程07-1学号 200707030128 姓名 沈建荣主要内容、基本要求、主要参考资料等：课程设计按照教学要求需要一周时间完成，总共至少要上机调试程序10小时。对每个题目要有需求分析，在需求分析中，将题目中要求的功能进行叙述分析，并且设计解决此问题的数据存储结构，设计或叙述解决此问题的算法，描述算法建议使用流程图，进行算法分析指明关键语句的时间复杂度。给出实现功能的一组或多组测试数据，程序调试后，将按照此测试数据进行测试的结果列出来 。对有些题目提出算法改进方案，比较不同算法的优缺点。如果程序不能正常运行，写出实现此算法中遇到的问题，和改进方法；2 对每个题目要有相应的源程序（可以是一组源程序，即详细设计部分）： 源程序要按照写程序的规则来编写。要结构清晰，重点函数的重点变量，重点功能部分要加上清晰的程序注释。程序能够运行，要有基本的容错功能。尽量避免出现操作错误时出现死循环；3 最后提供的主程序可以象一个应用系统一样有主窗口，通过主菜单和分级菜单调用课程设计中要求完成的各个功能模块，调用后可以返回到主菜单，继续选择其他功能进行其他功能的选择。完 成 期 限： 指导教师签名： 课程负责人签名： 年 月 日目 录一、 设计题目（任选其一） 3二、 运行环境（软、硬件环境） 3三、 算法设计的思想 3四、 算法的流程图 4五、 算法设计分析 5六、 源代码 6七、 运行结果分析 7八、 收获及体会 13一、 设计题目：校园导游程序问题描述用无向网表示你所在学校的校园景点平面图，图中顶点表示主要景点，存放景点的编号、名称、简介等信息，图中的边表示景点间的道路，存放路径长度等信息。要求能够回答有关景点介绍、游览路径等问题。基本要求（1） 查询各景点的相关信息；（2） 查询图中任意两个景点间的最短路径。（3） 查询图中任意两个景点间的所有路径。（4） 增加、删除、更新有关景点和道路的信息。二、 运行环境：vc6.0三、 算法设计的思想看到这道题目就知道是有关图的存储和操作，尽管图论的算法有点难但是感觉具有实用价值，能借着实习的机会亲手写个使用的程序很划算，所以就挑了这个题目！首先开始就感觉要求（1）和（4）没有难度，就是基本的查找，修改，更新这类的操作，上学期c+实训就是做同学录之类的程序，里面都是这种操作，很熟悉；接着是（2）最短路书上有现成的算法Dijkstra算法，Bellman-ford算法和可以求各个顶点间最短路的Floyd-Warshall算法；总的来说(2)也好实现；最后是要求（3）求两个景点间的所有路径？没有搞错吧！开始的迷茫过后我开始查资料，和同学讨论向老师请教。终于小有收获，这属于搜索类的题目，具体到本题可以用bfs（）广搜，和dfs（）深搜，但是刚开始我一直没想好怎么用bfs（）控制结束，所有就用dfs（）回溯法实现了！后来想想广搜也可以控制只要想到，最多的长度是n-1就可以了（没有重复走一条路，否则将是无穷种可能）！四、 算法的流程图开始Floyd求最短路输入m n输入信息建图输入操作信息到strStr=checkcheckmin结束五、 算法设计分析上面算法都想好了，可以开始实现了！用什么存储图呢？考虑到这是校园景点，所以v肯定不多，而校园中的路肯定多，所以是个v少的稠密图，当然用邻接矩阵了！再加上最近对c+的容器感兴趣，就用了vector代替数组来实现可变容量的数组！上面虽然把每个要求都想好了，可是到具体实现是又遇到很多的难题：比如要求（2）求最短路我该用那个算法呢，是单源最短路的Dijkstra还是一劳永逸的Floyd-Warshall呢！从实际出发，考虑到这个导游程序查询最多的就是某两点间的最短了，而且顶点间的道路很少变化，就选了Floyd-Washall了。（但是后来实现顶点的删除和增加时又感觉这样也不是很妥当，不过实际上道路的修改肯定不会频繁的！）还有一个想法就是不行写菜单了，显得程序很笨拙！就想模拟以前dos下当然现在linux下流行的程序都是这样的，就是命令式的操作：下面是我定义的一些操作！输入格式：第一行两个整数n m ；分别表示景点的个数和道路的个数；接着n行每行包含三个数据：顶点编号 x，景点名称 xxx，景点简介 xxxxxxxx; 其中x为整型,xxx及xxxxxx为字符串再接下来m行每行包含三个整型数据: a b cost a,b表示顶点标号,cost为道路的长度之后的是对这个无向网的操作:目前暂时只定义三种操作check all /查看所有的节点信息check id /察看顶点id的信息min a b /察看景点a b之间的最短路径all a b /察看 a b 之间的所有路径update a 顶点编号 a，景点名称 xxx，景点简介 xxxxxxxx/更新a景点的信息deleteid a /删除a节点end / 终止操作输出格式:对于 checkall 要求输出所有景点的 名称 简介对于 check id 要求输出id景点的 名称 简介对于 min a b 要求输出 路径的长度和途径的顶点;对于 all a b 要求输出 路径的长度和途径的顶点;每个路径独占一行对于 deleteid a 输出id景点的 名称 简介 delete successfully !对于 update a a xxx xxxxxxxxx 输出 a updatesuccessfully !对于 end 结束操作六、 源代码#include#include#include#define Max_Vex 100#define MaxNum 0x7ffffffusing namespace std;struct nodeint id;char name20;char info50;vector vex;int mapMax_VexMax_Vex;int pathMax_VexMax_Vex;int each_costMax_VexMax_Vex;int n,m;/顶点个数和边的个数；int vexnum;/实际的大小int min(int a,int b,int cost);/a b 的最短路径int check(int a);/返回a顶点的信息void dfs(int x,int cost,int b);/深搜int all(int a,int b);/输出a b间的所有路径void Floyd_Washall();/求各个点最短路径int update(int a);/更新节点信息int validnum();/检测输入的是否为数字int deleteid(int a);/删除顶点aint help();/帮助命令int main()int j,i,a,b,cost;node t;system(cls);system(mode con:cols=40 lines=20);system(color 4f);scanf(%d%d,&n,&m);for(i=0;i=n;i+)/初始化map，使得任意点间没有路for(j=0;j=n;j+)/初始化each_costeach_costij=mapij=MaxNum;vexnum = n;/vex.push_back(t);for(i=0;in;i+)scanf(%d%s%s,&t.id,,);vex.push_back(t);for(i=0;im;i+)scanf(%d%d%d,&a,&b,&cost);/利用邻接矩阵存储mapab = mapba = cost;/each_costab = each_costba =cost;/floyd求各个点之间的最短路径保存在each_cost中Floyd_Washall();/路径保存在path中char str20;do/功能菜单scanf(%s,str);if(strcmp(str,check)=0)a=validnum();if(a!=-1)check(a);else if(strcmp(str,cls)=0)system(cls);else if(strcmp(str,help)=0)help();else if(strcmp(str,update)=0)a=validnum();if(a!=-1)update(a);else if(strcmp(str,deleteid)=0)a=validnum();if(a!=-1)deleteid(a);else if(strcmp(str,checkall)=0)for(i=1;i=n;i+)check(i);else if(strcmp(str,min)=0)scanf(%d%d,&a,&b);min(a,b,each_costab);else if(strcmp(str,all)=0)scanf(%d%d,&a,&b);all(a,b);else if(strcmp(str,end)=0)break;elseprintf(error input!nyou can type help for detail!n);while(1);return 0;int help()coutcheckall 输出所有景点的 名称 简介endlcheck id 输出id景点的 名称 简介endlmin a b 输出 路径的长度和途径的顶点;endlall a b 输出 路径的长度和途径的顶点endldeleteid a 删除a节点endlupdate a 更新a节点信息endlhelp 查看帮助endlcls 清屏操作endlcolor 修改背景颜色endlend 结束操作endlendl;return 0;int validnum()/若输入的是数字则返回数字，其他为非法输入，返回-1；char str10;scanf(%s,str);if(isdigit(str0) return atoi(str);else printf( error input!n);return -1;int deleteid(int a)for(int i=1;i=n;i+)mapai=MaxNum;for(i=1;i,a);while(i!=b) printf(%d-,i);i=pathbi;printf(%d cost %dn,b,cost);return 0;int check(int a)if(vexa.id!=-1)printf(%d%s%sn,vexa.id,,);return 1;/else printf(%d isnt in!n,a);return -1;int pMax_Vex;int usedMax_Vex;void dfs(int x,int cost,int b)pp0+ = x;/x加入路径； if(x=b)/找到一条路径则输出for(int i=1;i,pi);printf(%d cost %dn,pi,cost);return ;for(int j = 1;j=n;j+)if(mapxj!=MaxNum& !usedx)/x到j有路，并且x到j没走过cost+=mapxj;/记录总的花费usedx = 1;/标记已走dfs(j,cost,b);p0-;/去掉jcost-=mapxj;/恢复usedx = 0;/恢复int all(int a,int b)p0 = 1;memset(used,0,sizeof(used);dfs(a,0,b);/利用深搜找所有路径；return 0;void Floyd_Washall() int i,j,k; for(i=1;i=n;i+) for (j=1;j=n;j+) each_costij = mapij;pathij=i;for(i=1;i=n;i+) each_costii=0;pathii=0; for(k=1;k=n;k+)for(i=1;i=n;i+)for(j=1;jeach_costik+each_costkj) each_costij=each_costik+each_costkj;pathij=pathkj; 七、 运行结果分析举个具体的例子：42441135111436上图所示为：顶点2到5的所有路径删除顶点3后2，5点间的最短路和所有路径八、 收获及体会 经过将近一周的课程设计总的来说收获还是很大的！首先代码能力明显提高，有了想法基本都能顺利表达出来；再者就是数据结构的选择使用能力也有了很大的提高!所说平时的实验课我们也有用各种数据做题，但那些都是很明确的该做什么操作，存什么，我们的发挥空间不大一般照做就行，然而这次实习我们却是在自主的选择判断，这本身就是一个很大的提高！例如就拿我做的这个程序，是关于图的，我们都知道图有很多的存储结构，平时也听老师在课堂上讲过，但是具体到本道题，到底是用邻接表还是邻接矩阵呢，十字链表还是多重链表，这些都是我写程序前就考虑的东西！还有就是算法方面的学习有