算法与数据结构课程设计.docxVIP

*******************实践教学*******************兰州理工大学计算机与通信学院2016年秋季学期算法与数据结构课程设计题 目：1. 跳马问题2. 超市选址问题 专业班级： 软件工程(1)班 姓 名： 刘子栋 学 号： 1516270168 指导教师： 年福忠 成 绩：_______________ 目 录目 录2摘 要3一． 跳马问题41. 采用类语言定义相关的数据类型42. 算法设计43. 程序流程图64. 调试分析65. 测试结果66. 源代码（带注释）7二. 学校超市选址问题91. 采用类语言定义相关的数据类型92. 算法设计103. 函数的调用关系图134. 调试分析135. 测试结果136. 源代码（带注释）16总 结20参考文献21致 谢22摘 要国际象棋中的跳马问题是一个古老而著名的问题。跳马问题也称为骑士周游问题，是算法的设计中的经典问题。如果有这样一种走法，则称所走的这条线为马的周游路线。在8*8的方格棋盘中马的行走规则从棋盘的某一方格出发，开始在棋盘上周游，如果能不重复地走遍棋盘上的每一个方格，这样的一条周游路线在数学上被称为国际象棋棋盘上马的哈密尔顿链。本程序主要完成找出马的哈密尔顿链并在棋盘上动态的标注其行走的过程。关键词：马的遍历，迭代，最少出口。 校园超市选址用邻接矩阵（或邻接表）表示，主要功能有：校园平面图接矩阵（邻接表）的建立、路径的查询、从某一点到另一景的最短路径查找、按查找出的最短路径确定超市的地址、显示输出等功能。一般情况下，校园的道路是双向通行的，可设校园平面图是一无向网，边表示路径，边上的权值存放路径长度等相关信息。关键词：弗洛伊德，邻接矩阵，最短路径。 跳马问题要求在64个国际象棋格子,任意位置放一个马,如何不重复地把格子走完。采用类语言定义相关的数据类型#includeiostream.h#includestdio.hvoid main(){ int Movel[8]={-2,-1,1,2,2,1,-1,-2}; int Movev[8]={1,2,2,1,-1,-2,-2,-1}; int A[8][8];int l,v,l1,v1,l2,v2,m,n,s,b,d;算法设计 for(int t=2;t=64;t++) //开始马的遍历{ b=8; for(int p=0;p=7;p++) //判断马的路线，找出最短路线{ l1=l+Movel[p]; v1=v+Movev[p]; if(l1=0l1=7v1=0v1=7A[l1][v1]==0){ d=0; for(int q=0;q=7;q++){ l2=l1+Movel[q]; v2=v1+Movev[q]; if(l2=0l2=7v2=0v2=7A[l2][v2]==0) d++;} if(b=d){ b=d; s=p;}}} if(b=8){ l+=Movel[s]; v+=Movev[s]; A[l][v]=t;}}//打印出马的路线，coutendl;printf( ******************马的路线********************\n); for(m=0;m=7;m++){printf( ); for(n=0;n=7;n++){ printf(%6d,A[m][n]);} coutendl;} coutendl; 程序流程图 开始是 否 图1.1 程序流程图 调试分析 在选课问题中，我自己写的数组结果调试的时候，错误很多，才明白计算机语言有自己特定的格式，数据结构也有其特殊性；如果考虑不到的话那就无法通过编译。所以我找了大量的资料和参考程序帮助我修改自己的错误。测试结果输入坐标：（2,5），结果如下：输入起始位置（4,6），结果如下：源代码（带注释） for(int t=2;t=64;t++) //开始马的遍历{ b=8; for(int p=0;p=7;p++) //判断马的路线，找出最短路线{ l1=l+Movel[p]; v1=v+Movev[p]; if(l1=0l1=7v1=0v1=7A[l1][v1]==0){ d=0; for(int q=0;q=7;q++){ l2=l1+Movel[q]; v2=v1+Movev[q]; if(l2=0l2=7v2=0v2=7A[l2][v2]==0) d++;} if(b=d){ b=d; s=p;}}} if(b=8){ l+=Movel[s]; v+=Movev[s]; A[l][v]=t;}}//打印出马的路线，coutendl;printf( ******************马的路线********************\n); fo