数据结构马踏棋盘

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  

3、      7        二 概要设计为了实现上述程序功能，可以采用顺序栈或者链栈来存储它的数据，本实验所需要的存储空间不是很大，不需动态的开辟很多空间，所以采用相对简单的顺序栈来存储数据，既方便有简单，而用链栈在实现上相对比顺序栈复杂的一点。2.1顺序栈的抽象数据类型定义：ADT Stack数据对象：D=ai| ai（0，1，9），i=0,1，2，n，n0数据关系：R=< ai-1, ai >| ai-1, aiD,i=1,2，n ADT

4、 Stack2.2本程序包含三个模块：1、主程序模块：void main()定义变量；接受命令；处理命令；退出； 2、起始坐标函数模块马儿在棋盘上的起始位置；3、探寻路径函数模块马儿每个方向进行尝试，直到试完整个棋盘；4、输出路径函数模块输出马儿行走的路径； 2.3各模块之间的调用关系：主程序模块 输入的初始位置是否正确 否起始坐标函数模块 是 探寻路径函数模块 输出路径函数模块块 结束 三 详细设计3.1定义头文件和预定义#include<stdio.h>#define MAXSIZE 100#define N 83.2数据类型定义int board88; /定义棋盘int Ht

5、ry18=1,-1,-2,2,2,1,-1,-2; /*存储马各个出口位置相对当前位置行下标的增量数组*/int Htry28=2,-2,1,1,-1,-2,2,-1; /*存储马各个出口位置相对当前位置列下标的增量数组*/struct Stack /定义栈类型 int i; /行坐标int j; /列坐标 int director; /存储方向stackMAXSIZE; /定义一个栈数组int top=-1; /栈指针3.3函数声明void InitLocation(int xi,int yi); /马儿在棋盘上的起始位置坐标int TryPath(int i,int j); /马儿每个方向

6、进行尝试，直到试完整个棋盘void Display(); /输出马儿行走的路径3.4起始坐标函数模块void InitLocation(int xi,int yi)int x,y; /定义棋盘的横纵坐标变量top+; /栈指针指向第一个栈首stacktop.i=xi; /将起始位置的横坐标进栈stacktop.j=yi; /将起始位置的纵坐标进栈stacktop.director=-1; /将起始位置的尝试方向赋初值boardxiyi=top+1; /标记棋盘x=stacktop.i; /将起始位置的横坐标赋给棋盘的横坐标y=stacktop.j; /将起始位置的纵坐标赋给棋盘的纵坐标if(T

7、ryPath(x,y) /调用马儿探寻函数，如果马儿探寻整个棋盘返回1否则返回0Display(); /输出马儿的行走路径else printf("无解"); 3.5探寻路径函数模块int TryPath(int i,int j)int find,director,number,min; /定义几个临时变量int i1,j1,h,k,s; /定义几个临时变量int a8,b18,b28,d8; /定义几个临时数组while(top>-1) /栈不空时循环for(h=0;h<8;h+) /用数组a8记录当前位置的下一个位置的可行路径的条数number=0; i=s

8、tacktop.i+Htry1h; j=stacktop.j+Htry2h; b1h=i; b2h=j; if(boardij=0&&i>=0&&i<8&&j>=0&&j<8) /如果找到下一位置for(k=0;k<8;k+)i1=b1h+Htry1k; j1=b2h+Htry2k; if(boardi1j1=0&&i1>=0&&i1<8&&j1>=0&&j1<8) /如果找到下一位置 number+; /记录条数

9、 ah=number; /将条数存入数组a8中 for(h=0;h<8;h+) /根据可行路径条数小到大按下表排序放入数组d8中min=9; for(k=0;k<8;k+)if(min>ak) min=ak; dh=k; /将下表存入数组d8中 s=k; as=9; director=stacktop.director; if(top>=63) /如果走完整个棋盘返回1return (1);find=0; /表示没有找到下一个位置for(h=director+1;h<8;h+) /向八个方向进行探寻i=stacktop.i+Htry1dh; j=stacktop.

10、j+Htry2dh;if(boardij=0&&i>=0&&i<8&&j>=0&&j<8) /如果找到下一位置find=1; /表示找到下一个位置break;if(find=1) /如果找到下一个位置进栈stacktop.director=director; /存储栈结点的方向 top+; /栈指针前移进栈stacktop.i=i;stacktop.j=j;stacktop.director=-1; /重新初始化下一栈结点的尝试方向boardij=top+1; /标记棋盘else /否则退栈boardsta

11、cktop.istacktop.j=0; /清除棋盘的标记top-; /栈指针前移退栈return (0); 3.6输出路径函数模块void Display() int i,j; for(i=0;i<N;i+)for(j=0;j<N;j+)printf("t%d ",boardij); /输出马儿在棋盘上走过的路径printf("nn");printf("n");3.7主程序模块void main()int i,j;int x,y;for(i=0;i<N;i+) /初始化棋盘 for(j=0;j<N;j+) b

12、oardij=0;for(;)printf("Please input importpoint(1<=x<=8 and 1<=y<=8)n");printf("Input x = ");scanf("%d",&x); /输入起始位置的横坐标printf("Input y = ");scanf("%d",&y); /输入起始位置的纵坐标if(x>=1&&x<=8&&y>=1&&y<=8)

13、break;printf("Your input is worng!n");printf("begin with %d board:nn", 8*(x-1)+y);InitLocation(x-1,y-1); /调用起始坐标函数四 调试分析（1）本次实验的主要目的是在于掌握和理解栈的特性和它的应用。在编制该程序中遇到了很多问题。首先，在开始刚编制程序的时候遇到的问题是，程序编译都通不过，主要在一些细节的问题上，还有在程序的返回值在刚开始时也没有正确返回。经过编译慢慢调试，编译都能通过，没有错误和警告。（2）虽然编译都能通过，但是运行时却出错，程序不能终止

14、，只有通过人工方式结束程序，可能是在某些地方出现了无限死循环了，然后在仔细检查代码，发现没有标记马儿尝试的方向director，这样的话，马儿回溯的时候，下一次又有可能走那个方向，这样就出现了死循环。（3）标记好马儿尝试的方向后，编译运行，但是运行结果却不符合程序所要求的结果，说明在算法上肯定有错误，检查发现，马儿走的坐标没有控制后，它的横纵坐标必须控制0到7之间，否则的话马儿就会踏出棋盘以外，这样输出的结果就不对。还有就是棋盘走过的位置要标记一下，以便下次走不重复走，当回溯的时候的记得把标记给清掉，这个地方有时候也很容易混淆。（4）还有一点就是，该程序运算量大，算法复杂度高，所以运行的时候很慢，特别占内存，CPU的使用也很高，几乎都在70%到90%之间，配置低了可能还运行不了。五 测试结果结果1：结果2：六 实验体会通过本次实验的编写，能够掌握栈的性质以及它的应用。这次实验花了很多时间才完成，其实本应该早完成的，在检查的过程中有多多少少修改完美了一下，不过算法思想却没有改变。这个程序也让我头疼了几次，就是运行速度很慢，要等很久才能输出结果，这样的话很占内存资源，而且CPU的使用记录也很高，主要是它需要的运算太多，所以CPU 使用记录也是很高的。虽然我也参考了一些优化的算法，可以找到最优路进走，但是这些最优算法都和栈的应用失去了联系，