搜索
郑州轻工业学院课程设计任务书题目校园导游程序专业、班级网络工程07-1学号200707030128姓名沈建荣主要内容、基本要求、主要参考资料等：课程设计按照教学要求需要一周时间完成，总共至少要上机调试程序10小时。对每个题目要有需求分析，在需求分析中，将题目中要求的功能进行叙述分析，并且设计解决此问题的数据存储结构，设计或叙述解决此问题的算法，描述算法建议使用流程图，进行算法分析指明关键语句的时间复杂度。给出实现功能的一组或多组测试数据，程序调试后，将按照此测试数据进行测试的结果列出来。对有些题目提出算法改进方案，比较不同算法的优缺点。如果程序不能正常运行，写出实现此算法中遇到的问题，和改进方法；2对每个题目要有相应的源程序（可以是一组源程序，即详细设计部分）：源程序要按照写程序的规则来编写。要结构清晰，重点函数的重点变量，重点功能部分要加上清晰的程序注释。程序能够运行，要有基本的容错功能。尽量避免出现操作错误时出现死循环；3最后提供的主程序可以象一个应用系统一样有主窗口，通过主菜单和分级菜单调用课程设计中要求完成的各个功能模块，调用后可以返回到主菜单，继续选择其他功能进行其他功能的选择。完成期限：指导教师签名：课程负责人签名：年月日2目录一、设计题目（任选其一）3二、运行环境（软、硬件环境）3三、算法设计的思想3四、算法的流程图4五、算法设计分析5六、源代码6七、运行结果分析7八、收获及体会133一、设计题目：校园导游程序[问题描述]用无向网表示你所在学校的校园景点平面图，图中顶点表示主要景点，存放景点的编号、名称、简介等信息，图中的边表示景点间的道路，存放路径长度等信息。要求能够回答有关景点介绍、游览路径等问题。[基本要求]（1）查询各景点的相关信息；（2）查询图中任意两个景点间的最短路径。（3）查询图中任意两个景点间的所有路径。（4）增加、删除、更新有关景点和道路的信息。二、运行环境：vc6.0三、算法设计的思想看到这道题目就知道是有关图的存储和操作，尽管图论的算法有点难但是感觉具有实用价值，能借着实习的机会亲手写个使用的程序很划算，所以就挑了这个题目！首先开始就感觉要求（1）和（4）没有难度，就是基本的查找，修改，更新这类的操作，上学期c++实训就是做同学录之类的程序，里面都是这种操作，很熟悉；接着是（2）最短路书上有现成的算法Dijkstra算法，Bellman-ford算法和可以求各个顶点间最短路的Floyd-Warshall算法；总的来说(2)也好实现；最后是要求（3）求两个景点间的所有路径？没有搞错吧！开始的迷茫过后我开始查资料，和同学讨论向老师请教。终于小有收获，这属于搜索类的题目，具体到本题可以用bfs（）广搜，和dfs（）深搜，但是刚开始我一直没想好怎么用bfs（）控制结束，所有就用dfs（）回溯法实现了！后来想想广搜也可以控制只要想到，最多的长度是n-1就可以了（没有重复走一条路，否则将是无穷种可能）！4四、算法的流程图开始Floyd求最短路输入mn输入信息建图输入操作信息到strStr==checkcheckmin结束5五、算法设计分析上面算法都想好了，可以开始实现了！用什么存储图呢？考虑到这是校园景点，所以v肯定不多，而校园中的路肯定多，所以是个v少的稠密图，当然用邻接矩阵了！再加上最近对c++的容器感兴趣，就用了vector代替数组来实现可变容量的数组！上面虽然把每个要求都想好了，可是到具体实现是又遇到很多的难题：比如要求（2）求最短路我该用那个算法呢，是单源最短路的Dijkstra还是一劳永逸的Floyd-Warshall呢！从实际出发，考虑到这个导游程序查询最多的就是某两点间的最短了，而且顶点间的道路很少变化，就选了Floyd-Washall了。（但是后来实现顶点的删除和增加时又感觉这样也不是很妥当，不过实际上道路的修改肯定不会频繁的！）还有一个想法就是不行写菜单了，显得程序很笨拙！就想模拟以前dos下当然现在linux下流行的程序都是这样的，就是命令式的操作：下面是我定义的一些操作！输入格式：第一行两个整数nm；分别表示景点的个数和道路的个数；接着n行每行包含三个数据：顶点编号x，景点名称xxx，景点简介xxxxxxxx;其中x为整型,xxx及xxxxxx为字符串再接下来m行每行包含三个整型数据:abcosta,b表示顶点标号,cost为道路的长度之后的是对这个无向网的操作:目前暂时只定义三种操作checkall//查看所有的节点信息checkid//察看顶点id的信息minab//察看景点ab之间的最短路径allab//察看ab之间的所有路径updatea顶点编号a，景点名称xxx，景点简介xxxxxxxx//更新a景点的信息deleteida//删除a节点end//终止操作输出格式:6对于checkall要求输出所有景点的名称简介对于checkid要求输出id景点的名称简介对于minab要求输出路径的长度和途径的顶点;对于allab要求输出路径的长度和途径的顶点;每个路径独占一行对于deleteida输出id景点的名称简介deletesuccessfully!!对于updateaaxxxxxxxxxxxx输出aupdatesuccessfully!!对于end结束操作六、源代码#includeiostream#includevector#includestring#defineMax_Vex100#defineMaxNum0x7ffffffusingnamespacestd;structnode{intid;charname[20];charinfo[50];};vectornodevex;intmap[Max_Vex][Max_Vex];intpath[Max_Vex][Max_Vex];inteach_cost[Max_Vex][Max_Vex];intn,m;//顶点个数和边的个数；intvexnum;//实际的大小intmin(inta,intb,intcost);//ab的最短路径intcheck(inta);//返回a顶点的信息voiddfs(intx,intcost,intb);//深搜intall(inta,intb);//输出ab间的所有路径voidFloyd_Washall();//求各个点最短路径intupdate(inta);//更新节点信息intvalidnum();//检测输入的是否为数字7intdeleteid(inta);//删除顶点ainthelp();//帮助命令intmain(){intj,i,a,b,cost;nodet;system(cls);system(modecon:cols=40lines=20);system(color4f);scanf(%d%d,&n,&m);for(i=0;i=n;i++){//初始化map，使得任意点间没有路for(j=0;j=n;j++){//初始化each_costeach_cost[i][j]=map[i][j]=MaxNum;}}vexnum=n;//vex.push_back(t);for(i=0;in;i++){scanf(%d%s%s,&t.id,t.name,t.info);vex.push_back(t);}for(i=0;im;i++){scanf(%d%d%d,&a,&b,&cost);//利用邻接矩阵存储map[a][b]=map[b][a]=cost;//each_cost[a][b]=each_cost[b][a]=cost;}//floyd求各个点之间的最短路径保存在each_cost中Floyd_Washall();//路径保存在path中charstr[20];do{//功能菜单scanf(%s,str);if(strcmp(str,check)==0){a=validnum();if(a!=-1)check(a);}elseif(strcmp(str,cls)==0){system(cls);}elseif(strcmp(str,help)==0){help();}elseif(strcmp(str,update)==0){a=validnum();if(a!=-1)update(a);}8elseif(strcmp(str,deleteid)==0){a=validnum();if(a!=-1)deleteid(a);}elseif(strcmp(str,checkall)==0){for(i=1;i=n;i++)check(i);}elseif(strcmp(str,min)==0){scanf(%d%d,&a,&b);min(a,b,each_cost[a][b]);}elseif(strcmp(str,all)==0){scanf(%d%d,&a,&b);all(a,b);}elseif(strcmp(str,end)==0){break;}else{printf(errorinput!!!\nyoucantype'help'fordetail!!\n);}}while(1);return0;}inthelp(){coutcheckall输出所有景点的名称简介endlcheckid输出id景点的名称简介endlminab输出路径的长度和途径的顶点;endlallab输出路径的长度和途径的顶点endldeleteida删除a节点endlupdatea更新a节点信息endlhelp查看帮助endlcls清屏操作endlcolor修改背景颜色endlend结束操作endlendl;return0;}intvalidnum(){//若输入的是数字则返回数字，其他为非法输入，返回-1；charstr[10];scanf(%s,str);if(isdigit(str[0]))returnatoi(str);elseprintf(errorinput!!\n);return-1;}intdeleteid(inta){for(inti=1;i=n;i++)map[a][i]=MaxNum;for(i=1;i=n;i++)map[i][a]=MaxNum;9//n--;Floyd_Washall();vexnum--;check(a);printf(deletesuccessfully!!!\n);vex[a].id=-1;//vex.erase(vex.begin()+a);return0;}intupdate(inta){nodet;scanf(%d%s%s,&t.id,t.name,t.info);vex[a]=t;return0;}intmin(inta,intb,intcost){inti=path[b][a];printf(%d--,a);while(i!=b){printf(%d--,i);i=path[b][i];}printf(%dcost%d\n,b,cost);return0;}intcheck(inta){if(vex[a].id!=-1){printf(%d%s%s\n,vex[a].id,vex[a].name,vex[a].info);return1;}//elseprintf(%disn'tin!\n,a);return-1;}intp[Max_Vex];10intused[Max_Vex];voiddfs(intx,intcost,intb){p[p[0]++]=x;//x加入路径；if(x==b){//找到一条路径则输出for(inti=1;ip[0]-1;i++)printf(%d--,p[i]);printf(%dcost%d\n,p[i],cost);return;}for(intj=1;j=n;j++){if(map[x][j]!=MaxNum&&!used[x]){//x到j有路，并且x到j没走过cos