《2022年数据结构课程方案》由会员分享，可在线阅读，更多相关《2022年数据结构课程方案（10页珍藏版）》请在金锄头文库上搜索。
1、个人资料整理仅限学习使用中南民族大学数据结构课程设计报告姓名：康宇年级： 2018 学号： 10061014 专业：计算机科学与技术指导老师：宋中山2018 年 4 月 15 日精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 1 页，共 10 页个人资料整理仅限学习使用实习报告： 2.4 题马踏棋盘题目：设计一个国际象棋的马踏棋盘的演示程序班级：计科一班姓名：康宇学号：10061014完成日期： 2018.4.15 一、需求分析1、国际象棋的马踏棋盘的功能是：将马随机放在国际象棋的N*N 棋盘 boardNN的某个方格中，马按走棋规则进行移动。要求
2、每个方格只进一次，走遍棋盘上全部N*N 个方格。编制非递归程序，求出马的行走路线，并按求出的行走路线，将数字1,2 ，.,N*N依次填入一个N*N的方阵，输出之。 2 、测试数据： N由读者指定。马开始的位置也有读者指定x,y ）,1=x=N,1=y=N. 3、实现提示：下图显示了 N 为 6，马位于方格 3,3），8 个可能的移动位置。一般来说，马位于位置 x，y）时，可以走到下列8 个位置之一。但是，如果 ：struct Stack int i。 /行坐标 int j。 /列坐标 stackMaxMax 。 2、建立三个全局位置数组：int hi8=-2,-1,1,2,2,1,-1,-2。
3、int hj8=1,2,2,1,-1,-2,-2,-1。用来存放下一个可能位置的横纵坐标；int boardMaxMax。用来标记棋盘。 3、本程序包括 4 个模块 1）主程序： Void main( While(1 Input棋盘规格N。Input起始位置的x；Input起始位置的x；If( 起始位置在棋盘之内 Break。 调用栈函数InitLocation(x-1,y-1； 2）判断是否踏遍棋盘函数bool Find(int i,int j while( 栈不空 if( 踏遍了棋盘 return true。 for(k=0 。k 依次求 8 个方向；if(该位置存在且没走 寻找各方向的可
4、走路径数；ak存放各路径数；精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 3 页，共 10 页个人资料整理仅限学习使用 把各路径数按从小到大顺序排列for(k=0 。k if(有路可走 find=1 。break。 if(下一步有路可走 向下走一步； else/下一个位置无路 清除棋盘上一步的标记；倒退一步； return false。 3 输出函数void Print( for(i=0 。i for(j=0 。j printf(%4d,boardij。 printf(n 。 4）初始化栈函数void InitLocation(int i,int
5、 j 初始化栈；If(找到了踏遍棋盘的路 调用输出函数Print(。 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 4 页，共 10 页个人资料整理仅限学习使用三、详细设计#include #define Max 20 int hi8=-2,-1,1,2,2,1,-1,-2。int hj8=1,2,2,1,-1,-2,-2,-1。int N 。int boardMaxMax。/标记棋盘int top=0 。 /标记栈指针struct Stack int i。int j。stackMax*Max。bool Find(int i,int j/是否能踏
6、遍棋盘 /find 标记是否找到下一个位置，number 标记8 个位置的路径数，min 标记最少的路径int find,number,min 。int xi,yj,k,m 。int a8,b8 。/a标记各位置的路径数，b 标记由小到大的路径数对应的下标while(top-1 if(top=N*N-1/踏遍了棋盘 return true。 for(k=0 。k number=0。i=stacktop.i+hik。j=stacktop.j+hjk。if(boardij=0&i=0&i=0&j for(m=0 。m/ 寻找各方向的路径数 xi=i+him 。yj=j+hjm 。if(boardx
7、iyj=0&xi=0&xi=0&yj number+。 ak=number 。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 5 页，共 10 页个人资料整理仅限学习使用 for(k=0 。k/ 把各路径数按从小到大顺序排列 min=9。for(m=0 。m if(am min=am 。bk=m 。 abk=9 。 find=0 。for(k=0 。k i=stacktop.i+hibk。j=stacktop.j+hjbk。if(boardij=0&i=0&i=0&j find=1 。break。 if(find/ 下一步有路可走 top+。sta
8、cktop.i=i 。stacktop.j=j 。boardij=top+1 。 else/下一个位置无路 boardstacktop.istacktop.j=0。/清除棋盘的标记top-。/倒退一步 return false。 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 6 页，共 10 页个人资料整理仅限学习使用void Print(/ 输出棋盘 int i,j 。for(i=0 。 i for(j=0 。 j printf(%4d,boardij。 printf(n 。 printf(n 。 void InitLocation(int i
9、,int j/初始化栈并判断输出 stacktop.i=i 。stacktop.j=j 。boardij=top+1 。if(Find(i,j Print(。 int main( int x,y 。int i,j 。printf(Input N (N*N棋盘 : 。scanf(%d,&N 。for(i=0 。 i/ 初始化棋盘for(j=0 。 j boardij=0 。while(1 printf(Input x (1x :。scanf(%d,&x 。printf(Input y (1y :。scanf(%d,&y 。if(x=1&x=1&y break。printf(Your input
10、is wrong!n。 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 7 页，共 10 页个人资料整理仅限学习使用printf(begin with %d row, %d rol on board:nn,x,y。InitLocation(x-1,y-1 。return 0。 四、调试分析1. 本次作业比较简单，只有一个核心算法，即求下一步该怎么走，以及是否有路可走，所以总的调试比较顺利。在调试Find 算法时，遇到两个问题：一是没有考虑到马的这一步失败后的回溯，另一个是避免重复以前走过的路。2. 本程序模块简洁，在main( 函数里得到充分体现；
11、3. 用户可灵活控制棋盘的规模大小以及马踏的起始位置，本程序具有一定的通用性。五、用户手册1. 本程序运行环境为Windows操作系统，执行文件为：mata.exe 2.进入演示程序后显示的界面：六、测试结果精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 8 页，共 10 页个人资料整理仅限学习使用精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 9 页，共 10 页个人资料整理仅限学习使用精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 10 页，共 10 页
