资源描述：
《数据结构 马踏棋盘.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、实现顺序栈或循环队列的存储一需求分析1.1理解栈的特性“后进先出”和队列的特性“先进先出”。仅仅认识到栈和队列是两种特殊的线性表是远远不够的，本次实验的目的在于更深入的了解栈和队列的特性，以便在实际问题背景下灵活运用他们。在了解他特性的基础上，还将巩固对这种结构的构造方法的理解。1.2要求：在国际象棋8×8棋盘上面，按照国际象棋规则中马的行进规则，实现从任意初始位置，每个方格只进入一次，走遍棋盘上全部64个方格。编制程序，求出马的行走路线，并按求出的行走路线，将数字1，2，…，64依次填入一个8×8的方阵，并输出它的行走路线（
2、棋盘如图所示）。输入：任意一个起始位置；输出：无重复踏遍棋盘的结果，以数字1-64表示行走路线。 012345670 8 1 1 7 2 2 H 3 6 3 4 5 4 5 6 7 二概要设计为了实现上述程序功能，可以采用顺序栈或者链栈来存储它的数据，本实验所需要的存储空间不是很大，不需动态的开辟很多空间，所以采用相对简单的顺序栈来存储数据，既方便有简单，而用链栈在实现上相对比顺序栈复杂的一点。82.1顺序栈的抽象数据类型定义：ADTStack{数据对
3、象：D={ai
4、ai∈（0，1，…，9），i=0,1，2，…，n，n≥0}数据关系：R={
5、ai-1,ai∈D,i=1,2，…，n}}ADTStack2.2本程序包含三个模块：1、主程序模块：voidmain(){定义变量；接受命令；处理命令；退出；}2、起始坐标函数模块——马儿在棋盘上的起始位置；3、探寻路径函数模块——马儿每个方向进行尝试，直到试完整个棋盘；4、输出路径函数模块——输出马儿行走的路径；2.3各模块之间的调用关系：主程序模块输入的初始位置是否正确否起始坐标函数模块是探寻路径函数模块输出路径函
6、数模块块结束8三详细设计3.1定义头文件和预定义#include#defineMAXSIZE100#defineN83.2数据类型定义intboard[8][8];//定义棋盘intHtry1[8]={1,-1,-2,2,2,1,-1,-2};/*存储马各个出口位置相对当前位置行下标的增量数组*/intHtry2[8]={2,-2,1,1,-1,-2,2,-1};/*存储马各个出口位置相对当前位置列下标的增量数组*/structStack{//定义栈类型inti;//行坐标intj;//列坐标intdirec
7、tor;//存储方向}stack[MAXSIZE];//定义一个栈数组inttop=-1;//栈指针3.3函数声明voidInitLocation(intxi,intyi);//马儿在棋盘上的起始位置坐标intTryPath(inti,intj);//马儿每个方向进行尝试，直到试完整个棋盘voidDisplay();//输出马儿行走的路径3.4起始坐标函数模块voidInitLocation(intxi,intyi){intx,y;//定义棋盘的横纵坐标变量top++;//栈指针指向第一个栈首stack[top].i=xi;/
8、/将起始位置的横坐标进栈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否则返回0Display();//输出马儿的行走路径elseprintf("无解");}83.5探寻路径函
9、数模块intTryPath(inti,intj){intfind,director,number,min;//定义几个临时变量inti1,j1,h,k,s;//定义几个临时变量inta[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
10、(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
