数据结构与算法-马踏棋盘.doc

资源描述

精品资料合肥学院计算机科学与技术系课程设计报告 2012～2013学年第2学期课程数据结构与算法课程设计名称马踏棋盘学生姓名学号专业班级指导教师 2013 年6月目录数据结构课程设计报告————马踏棋盘 - 2 - 问题描述 - 2 - 1、问题分析与定义 - 2 - 2、数据结构的选择和概要设计 - 3 - 数据结构的选择 - 3 - 概要设计 - 3 - 3、详细设计和编码 - 4 - 4、上机调试过程 - 6 - 5、测试结果及分析 - 7 - 6、用户使用说明 - 9 - 7、参考文献 - 9 - 附录源程序 - 10 - 数据结构课程设计报告 ————马踏棋盘题目：【问题描述】设计一个国际象棋的马踏遍棋盘的演示程序。要求：将马随机放在国际象棋的8×8棋盘Board[8][8]的某个方格中，马按走棋规则进行移动。要求每个方格只进入一次，走遍棋盘上全部64个方格。编制非递归程序，求出马的行走路线，并按求出的行走路线，将数字1，2，…，64依次填入一个8×8的方阵，输出之。 1、问题分析与定义走棋规则：马走3×2格对角线，简单的说就是走L形棋盘如图所示，将马放在棋盘中的任意一个位置，按照马的走棋规则，我们能够发现，如果没有其他棋子的影响，它最多有8个出口，最少有2个出口。 0 1 2 3 4 5 6 7 0 8 1 1 7 2 2 H 3 6 3 4 5 4 5 6 7 马所在位置及其出口算法核心思想：本程序的核心算法是“贪心算法”。在每个结点对其子结点进行选取时，优先选择‘出口’最小的进行搜索，‘出口’的意思是在这些子结点中它们的可行子结点的个数，也就是‘孙子’结点越少的越优先跳，为什么要这样选取，这是一种局部调整最优的做法，如果优先选择出口多的子结点，那出口少的子结点就会越来越多，很可能出现‘死’结点（顾名思义就是没有出口又没有跳过的结点），这样对下面的搜索纯粹是徒劳，这样会浪费很多无用的时间，反过来如果每次都优先选择出口少的结点跳，那出口少的结点就会越来越少，这样跳成功的机会就更大一些。 2、数据结构的选择和概要设计数据结构的选择栈：本程序可以利用栈的知识来解决，当然，栈也包括链栈和顺序栈，由于本程序数据有限，并且顺序栈较链栈简单，所以该程序最终选择使用顺序栈来解决。贪心算法：在算法中采用逐步构造最优解。在每个阶段，都作出一个看上去最优的决策（在一定的标准下）。决策一旦作出就不可再更改。概要设计 Ⅰ、主程序模块： void main(){ 定义变量；接受命令；处理命令；退出； } Ⅱ、起始坐标函数模块——马儿在棋盘上的起始位置； Ⅲ、探寻路径函数模块——马儿每个方向进行尝试，直到试完整个棋盘； Ⅳ、输出路径函数模块——输出马儿行走的路径；流程图如下：主程序模块输入的初始位置是否正确否是起始坐标函数模块探寻路径函数模块输出路径函数模块块结束 3、详细设计和编码下图显示了马位于方格（2，3）时，8个可能的移动位置。一般来说，当马位于位置（i,j）时，可以走到下列8个位置之一 0 1 2 3 4 5 6 7 0 8 1 1 7 2 2 H 3 7 3 4 5 4 5 6 7 (i-2,j+1)、（i-1,j+2）、(i+1,j+2)、(i+2,j+1) (i+2,j-1)、(i+1,j-2)、(i-1,j-2)、(i-2,j-1) 但是，如果(i,j)靠近棋盘的边缘，上述有些位置可能超出棋盘范围，成为不允许的位置。8个可能位置可以用两个一维数组Htry1[0..7]和Htry2[0..7]来表示： 0 1 2 3 4 5 6 7 Htry1 -2 -1 1 2 2 1 -1 -2 0 1 2 3 4 5 6 7 Htry2 1 2 2 1 -1 -2 -2 -1 位于(i,j)的马可以走到的新位置是在棋盘范围内的(i+Htry[h],j+Htry2[h]),其中h=0,1,2,…,7。每次在多个可走位置中选择其中一个进行试探，其余未曾试探过的可走位置必须用适当结构妥善管理，以备试探失败时的“回溯”(悔棋)使用。流程图如下：开始 Int i、j i=0 i<N Board[i][j]=0 i ++ 输入棋子起始位置判断棋子是否出棋盘 Multiplex For循环从这个位置开始结束 4、上机调试过程（1）、本次实验的主要目的是在于掌握和理解栈的特性和它的应用。在编制该程序中遇到了很多问题。首先，在开始刚编制程序的时候遇到的问题是，程序编译都通不过，主要在一些细节的问题上，还有在程序的返回值在刚开始时也没有正确返回。经过编译慢慢调试，编译都能通过，没有错误和警告。（2）、虽然编译都能通过，但是运行时却出错，程序不能终止，只有通过人工方式结束程序，可能是在某些地方出现了无限死循环了，然后在仔细检查代码，发现没有标记马儿尝试的方向director，这样的话，马儿回溯的时候，下一次又有可能走那个方向，这样就出现了死循环。（3）、标记好马儿尝试的方向后，编译运行，但是运行结果却不符合程序所要求的结果，说明在算法上肯定有错误，检查发现，马儿走的坐标没有控制后，它的横纵坐标必须控制0到7之间，否则的话马儿就会踏出棋盘以外，这样输出的结果就不对。还有就是棋盘走过的位置要标记一下，以便下次走不重复走，当回溯的时候的记得把标记给清掉，这个地方有时候也很容易混淆。 5、测试结果及分析输入数据1：根据要求重新输入马的初始位置（9,9），由于输入数据不再要求范围之内,程序要求用户重新输入; 图（1）输入数据2：根据要求重新输入马的初始位置（1,1），结果如下图（2） = 图（3）测试结果如图（1）所示、当输入马的坐标为（9,9）时，由于该坐标不在8×8的棋盘内，所以程序提示要求重新输入；如图（2）所示，重新输入数据位（1,1）满足棋盘要求，得到在该位置的马踏棋盘的结果。如图（3）所示，当位置选定为（4,4）时的结果。结果分析：如图（3）所示，以数字递增顺序表示马的下一个出口位置。如图中，1表示初始位置，按照国际象棋中马的走棋规则并选择最优位置，即为2位置；3表示2位置的马的下一个出口位置。以此循环下去，直到数字遍及整个棋盘。注：马的走棋路线即为图中白线标记部分（仅标记了前4个位置）测试数据1:输入马的初始位置(9，9)，由于不符合要求，程序要求重新输入 6、用户使用说明用户需将源程序清单输入可运行C++的编辑平台，例如vc++, c++ Builder等等，然后进行编译，然后用户根据提示输入马的初始位置，程序会提示所输入马的初始位置必须在1-8之间，否则需要重新输入，直至输入的位置符合要求为止；输入正确之后，程序会输入马儿踏遍整个棋盘的具体执行步骤。注：阿拉伯数字1、2、3、4……62、63、64。下一个数字所在位置即为上一个位置马儿的出口。 7、参考文献 [1]王昆仑，李红.数据结构与算法.北京：铁道工业出版社，2007年6月第一版 [2].徐孝凯，魏荣《数据结构》,北京：机械工业出版社，1996年 [3].徐孝凯《数据结构简明教程》，北京:清华大学出版社，1995年 [4].陈文博，朱青《数据结构与算法》，北京：机械工业出版社，1996年 [5].许卓群，张乃孝，杨冬青，唐世渭《数据结构》，高等教育出版社，1988年 [6].李廉治，姜文清，郭福顺《数据结构》，大连理工大学出版社，1989年附录源程序 //（1）、定义头文件和预定义 #include<stdio.h> #define MAXSIZE 100 #define N 8 //（2）、数据类型定义 int board[8][8]; //定义棋盘 int Htry1[8]={1,-1,-2,2,2,1,-1,-2}; /*存储马各个出口位置相对当前位置行下标的增量数组*/ int Htry2[8]={2,-2,1,1,-1,-2,2,-1}; /*存储马各个出口位置相对当前位置列下标的增量数组*/ struct Stack{ //定义栈类型 int i; //行坐标 int j; //列坐标 int director; //存储方向 }stack[MAXSIZE]; //定义一个栈数组 int top=-1; //栈指针 //（3）、函数声明 void InitLocation(int xi,int yi); //马儿在棋盘上的起始位置坐标 int TryPath(int i,int j); //马儿每个方向进行尝试，直到试完整个棋盘 void Display(); //输出马儿行走的路径 //（4）、起始坐标函数模块 void InitLocation(int xi,int yi) { int x,y; //定义棋盘的横纵坐标变量 top++; //栈指针指向第一个栈首 stack[top].i=xi; //将起始位置的横坐标进栈 stack[top].j=yi; //将起始位置的纵坐标进栈 stack[top].director=-1; //将起始位置的尝试方向赋初值 board[xi][yi]=top+1; //标记棋盘 x=stack[top].i; //将起始位置的横坐标赋给棋盘的横坐标 y=stack[top].j; //将起始位置的纵坐标赋给棋盘的纵坐标 if(TryPath(x,y)) //调用马儿探寻函数，如果马儿探寻整个棋盘返回1否则返回0 Display(); //输出马儿的行走路径 else printf("无解"); } //（5）、探寻路径函数模块 int TryPath(int i,int j) { int find,director,number,min; //定义几个临时变量 int i1,j1,h,k,s; //定义几个临时变量 int a[8],b1[8],b2[8],d[8]; //定义几个临时数组 while(top>-1) //栈不空时循环 { for(h=0;h<8;h++) //用数组a[8]记录当前位置的下一个位置的可行路径的条数 { number=0; i=stack[top].i+Htry1[h]; j=stack[top].j+Htry2[h]; b1[h]=i; b2[h]=j; if(board[i][j]==0&&i>=0&&i<8&&j>=0&&j<8) //如果找到下一位置 { for(k=0;k<8;k++) { i1=b1[h]+Htry1[k]; j1=b2[h]+Htry2[k]; if(board[i1][j1]==0&&i1>=0&&i1<8&&j1>=0&&j1<8) //如果找到下一位置 number++; //记录条数 } a[h]=number; //将条数存入数组a[8]中 } } for(h=0;h<8;h++) //根据可行路径条数小到大按下表排序放入数组d[8]中 { min=9; for(k=0;k<8;k++) if(min>a[k]) { min=a[k]; d[h]=k; //将下表存入数组d[8]中 s=k; } a[s]=9; } director=stack[top].director; if(top>=63) //如果走完整个棋盘返回1 return (1); find=0; //表示没有找到下一个位置 for(h=director+1;h<8;h++) //向八个方向进行探寻 { i=stack[top].i+Htry1[d[h]]; j=stack[top].j+Htry2[d[h]]; if(board[i][j]==0&&i>=0&&i<8&&j>=0&&j<8) //如果找到下一位置 { find=1; //表示找到下一个位置 break; } } if(find==1) //如果找到下一个位置进栈 { stack[top].director=director; //存储栈结点的方向 top++; //栈指针前移进栈 stack[top].i=i; stack[top].j=j; stack[top].director=-1; //重新初始化下一栈结点的尝试方向 board[i][j]=top+1; //标记棋盘 } else //否则退栈 { board[stack[top].i][stack[top].j]=0; //清除棋盘的标记 top--; //栈指针前移退栈 } } return (0); } //（6）输出路径函数模块 void Display() { int i,j; for(i=0;i<N;i++) { for(j=0;j<N;j++) printf("\t%d ",board[i][j]); //输出马儿在棋盘上走过的路径 printf("\n\n"); } printf("\n"); } //（5）主程序模块 void main() { int i,j; int x,y; for(i=0;i<N;i++) //初始化棋盘 for(j=0;j<N;j++) board[i][j]=0; for(;;) { printf("请输入棋子起始坐标(1<=x<=8 and 1<=y<=8)\n"); printf("请输入行坐标 x = "); scanf("%d",&x); //输入起始位置的横坐标 printf("请输入列坐标 y = "); scanf("%d",&y); //输入起始位置的纵坐标 if(x>=1&&x<=8&&y>=1&&y<=8)break; printf("Your input is worng!!!\n"); } printf("从这里这个位置开始 %d :\n\n", 8*(x-1)+y); InitLocation(x-1,y-1); //调用起始坐标函数 } 可编辑修改

展开阅读全文