《2022年实验二实现顺序栈或循环队列的存储资料 .pdf》由会员分享，可在线阅读，更多相关《2022年实验二实现顺序栈或循环队列的存储资料 .pdf（7页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第 1 页 共 7 页实验二 实现顺序栈或循环队列的存储题目：编制一个马踏棋盘算法实现的程序班级：计科0603 姓名：李汉刚学号：20064140303 完成日期：2008-4-20 一、实验目的（1）、理解栈的特性“后进先出”和队列的特性“先进先出”。（2）、仅仅认识到栈和队列是两种特殊的线性表是远远不够的，本次实验的目的在于更深入的了解栈和队列的特性，以便在实际问题背景下灵活运用他们。（3）、在了解他特性的基础上，还将巩固对这种结构的构造方法的理解。二、实验环境（1）Windows XP 系统下（2）编程环境：VC6.0+三、实验内容（1）、要求：在国际象棋88 棋盘上面，按照国际象棋规则
2、中马的行进规则，实现从任意初始位置，每个方格只进入一次，走遍棋盘上全部64 个方格。编制程序，求出马的行走路线，并按求出的行走路线，将数字1，2，,，64 依次填入一个88 的方阵，并输出它的行走路线（棋盘如图所示）。（2）、输入：任意一个起始位置；输出：无重复踏遍棋盘的结果，以数字1-64 表示行走路线。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 名师资料总结-精品资料欢迎下载-名师精心整理-第 1 页，共 7 页 -第 2 页 共 7 页（3）、数据结构要求：采用顺序栈或者链栈实现。四、实验步骤为了实现上述程序功能，可以采用顺序栈或者
3、链栈来存储它的数据，本实验所需要的存储空间不是很大，不需动态的开辟很多空间，所以采用相对简单的顺序栈来存储数据，既方便有简单，而用链栈在实现上相对比顺序栈复杂的一点。（一）、概要设计（1）、顺序栈的抽象数据类型定义：ADT Stack 数据对象：D=ai|ai（0，1，,，9），i=0,1，2，,，n，n0 数据关系：R=|ai-1,ai D,i=1,2，,，n ADT Stack（2）本程序包含三个模块：1、主程序模块：void main()定义变量；接受命令；处理命令；退出；2、起始坐标函数模块马儿在棋盘上的起始位置；3、探寻路径函数模块马儿每个方向进行尝试，直到试完整个棋盘；4、输出路径
4、函数模块输出马儿行走的路径；各模块之间的调用关系：输入的初始位置是否正确否是主程序模块起 始 坐 标 函 数 模探寻路径函数模结束输出路径函数模名师资料总结-精品资料欢迎下载-名师精心整理-第 2 页，共 7 页 -第 3 页 共 7 页（二）、详细设计（1）、定义头文件和预定义#include#define MAXSIZE 100#define N 8（2）、数据类型定义int board88;/定义棋盘int Htry18=1,-1,-2,2,2,1,-1,-2;/*存储马各个出口位置相对当前位置行下标的增量数组*/int Htry28=2,-2,1,1,-1,-2,2,-1;/*存储马各
5、个出口位置相对当前位置列下标的增量数组*/struct Stack /定义栈类型int i;/行坐标int j;/列坐标 int director;/存储方向stackMAXSIZE;/定义一个栈数组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;/定义棋盘的横纵
6、坐标变量top+;/栈指针指向第一个栈首stacktop.i=xi;/将起始位置的横坐标进栈stacktop.j=yi;/将起始位置的纵坐标进栈stacktop.director=-1;/将起始位置的尝试方向赋初值boardxiyi=top+1;/标记棋盘x=stacktop.i;/将起始位置的横坐标赋给棋盘的横坐标y=stacktop.j;/将起始位置的纵坐标赋给棋盘的纵坐标if(TryPath(x,y)/调用马儿探寻函数，如果马儿探寻整个棋盘返回1 否则返回0 Display();/输出马儿的行走路径else printf(无解);（5）、探寻路径函数模块int TryPath(int i
7、,int j)名师资料总结-精品资料欢迎下载-名师精心整理-第 3 页，共 7 页 -第 4 页 共 7 页 int find,director,number,min;/定义几个临时变量int i1,j1,h,k,s;/定义几个临时变量int a8,b18,b28,d8;/定义几个临时数组while(top-1)/栈不空时循环 for(h=0;h=0&i=0&j8)/如果找到下一位置 for(k=0;k=0&i1=0&j18)/如果找到下一位置number+;/记录条数 ah=number;/将条数存入数组a8 中 for(h=0;h8;h+)/根据可行路径条数小到大按下表排序放入数组d8 中
8、 min=9;for(k=0;kak)min=ak;dh=k;/将下表存入数组d8 中 s=k;as=9;director=stacktop.director;if(top=63)/如果走完整个棋盘返回1 return(1);find=0;/表示没有找到下一个位置for(h=director+1;h=0&i=0&j8)/如果找到下一位置 find=1;/表示找到下一个位置break;if(find=1)/如果找到下一个位置进栈 stacktop.director=director;/存储栈结点的方向top+;/栈指针前移进栈stacktop.i=i;stacktop.j=j;stacktop.
9、director=-1;/重新初始化下一栈结点的尝试方向boardij=top+1;/标记棋盘 else /否则退栈 boardstacktop.istacktop.j=0;/清除棋盘的标记top-;/栈指针前移退栈 return(0);（6）输出路径函数模块void Display()int i,j;for(i=0;iN;i+)for(j=0;jN;j+)printf(t%d ,boardij);/输出马儿在棋盘上走过的路径printf(nn);printf(n);（5）主程序模块void main()int i,j;int x,y;名师资料总结-精品资料欢迎下载-名师精心整理-第 5 页，
10、共 7 页 -第 6 页 共 7 页for(i=0;iN;i+)/初始化棋盘 for(j=0;jN;j+)boardij=0;for(;)printf(Please input importpoint(1=x=8 and 1=y=1&x=1&y=8)break;printf(Your input is worng!n);printf(begin with%d board:nn,8*(x-1)+y);InitLocation(x-1,y-1);/调用起始坐标函数 五、调试分析（1）、本次实验的主要目的是在于掌握和理解栈的特性和它的应用。在编制该程序中遇到了很多问题。首先，在开始刚编制程序的时候遇
11、到的问题是，程序编译都通不过，主要在一些细节的问题上，还有在程序的返回值在刚开始时也没有正确返回。经过编译慢慢调试，编译都能通过，没有错误和警告。（2）、虽然编译都能通过，但是运行时却出错，程序不能终止，只有通过人工方式结束程序，可能是在某些地方出现了无限死循环了，然后在仔细检查代码，发现没有标记马儿尝试的方向director，这样的话，马儿回溯的时候，下一次又有可能走那个方向，这样就出现了死循环。（3）、标记好马儿尝试的方向后，编译运行，但是运行结果却不符合程序所要求的结果，说明在算法上肯定有错误，检查发现，马儿走的坐标没有控制后，它的横纵坐标必须控制0 到 7 之间，否则的话马儿就会踏出棋
12、盘以外，这样输出的结果就不对。还有就是棋盘走过的位置要标记一下，以便下次走不重复走，当回溯的时候的记得把标记给清掉，这个地方有时候也很容易混淆。（4）、还有一点就是，该程序运算量大，算法复杂度高，所以运行的时候很慢，特别占内存，CPU的使用也很高，几乎都在70%到 90%之间，配置低了可能还运行不了。六、运行结果结果 1：名师资料总结-精品资料欢迎下载-名师精心整理-第 6 页，共 7 页 -第 7 页 共 7 页结果 2：七、实验体会通过本次实验的编写，能够掌握栈的性质以及它的应用。这次实验花了很多时间才完成，其实本应该早完成的，在检查的过程中有多多少少修改完美了一下，不过算法思想却没有改变
13、。这个程序也让我头疼了几次，就是运行速度很慢，要等很久才能输出结果，这样的话很占内存资源，而且CPU的使用记录也很高，主要是它需要的运算太多，所以CPU 使用记录也是很高的。虽然我也参考了一些优化的算法，可以找到最优路进走，但是这些最优算法都和栈的应用失去了联系，本次的实验主要目的就是要了解栈，所以不用栈来写该程序就失去了该实验的意义。在该程序的编制过程中留下了一些思考的问题，就是马儿从一个起点位置开始探寻，最后马儿探寻成功的路径会不会是不只一条路径，可能还有多条路径，由于时间和精力的限制没有去深究，但是这应该值的思考的。在用顺序栈来实现该程序之前，也尝试过用链栈来做，但是发现如果用链栈来做的话，在存储调用的时候不是很方便，或许用链栈来做应该是对自己的一种挑战。尽管没有用链栈做不过，用顺寻栈来做在编制该程序中也收获不小。名师资料总结-精品资料欢迎下载-名师精心整理-第 7 页，共 7 页 -