实现顺序栈或循环队列的存储一、实验目的(1)、理解栈的特性“后进先出”和队列的特性“先进先出”。
(2)、仅仅认识到栈和队列是两种特殊的线性表是远远不够的,本次实验的目的在于更深入的了解栈和队列的特性,以便在实际问题背景下灵活运用他们。
(3)、在了解他特性的基础上,还将巩固对这种结构的构造方法的理解。
二、实验环境(1)Windows XP系统下(2)编程环境:VC6.0++三、实验内容(1)、要求:在国际象棋8×8棋盘上面,按照国际象棋规则中马的行进规则,实现从任意初始位置,每个方格只进入一次,走遍棋盘上全部64个方格。
编制程序,求出马的行走路线,并按求出的行走路线,将数字1,2,…,64依次填入一个8×8的方阵,并输出它的行走路线(棋盘如图所示)。
(2)、输入:任意一个起始位置;输出:无重复踏遍棋盘的结果,以数字1-64表示行走路线。
(3)、数据结构要求:采用顺序栈或者链栈实现。
四、实验步骤为了实现上述程序功能,可以采用顺序栈或者链栈来存储它的数据,本实验所需要的存储空间不是很大,不需动态的开辟很多空间,所以采用相对简单的顺序栈来存储数据,既方便有简单,而用链栈在实现上相对比顺序栈复杂的一点。
(一)、概要设计(1)、顺序栈的抽象数据类型定义:ADT Stack{数据对象:D={a i| a i∈(0,1,…,9),i=0,1,2,…,n,n≥0}数据关系:R={< a i-1, a i >| a i-1, a i∈D,i=1,2,…,n}} ADT Stack(2)本程序包含三个模块:1、主程序模块:void main(){定义变量;接受命令;处理命令;退出;}2、起始坐标函数模块——马儿在棋盘上的起始位置;3、探寻路径函数模块——马儿每个方向进行尝试,直到试完整个棋盘;4、输出路径函数模块——输出马儿行走的路径;(二)、详细设计(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(); //输出马儿的行走路径elseprintf("无解");}(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) //如果走完整个棋盘返回1return (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("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)break;printf("Your input is worng\n");}printf("begin with %d board:\n\n", 8*(x-1)+y);InitLocation(x-1,y-1); //调用起始坐标函数}五、调试分析(1)、本次实验的主要目的是在于掌握和理解栈的特性和它的应用。
在编制该程序中遇到了很多问题。
首先,在开始刚编制程序的时候遇到的问题是,程序编译都通不过,主要在一些细节的问题上,还有在程序的返回值在刚开始时也没有正确返回。
经过编译慢慢调试,编译都能通过,没有错误和警告。
(2)、虽然编译都能通过,但是运行时却出错,程序不能终止,只有通过人工方式结束程序,可能是在某些地方出现了无限死循环了,然后在仔细检查代码,发现没有标记马儿尝试的方向director,这样的话,马儿回溯的时候,下一次又有可能走那个方向,这样就出现了死循环。
(3)、标记好马儿尝试的方向后,编译运行,但是运行结果却不符合程序所要求的结果,说明在算法上肯定有错误,检查发现,马儿走的坐标没有控制后,它的横纵坐标必须控制0到7之间,否则的话马儿就会踏出棋盘以外,这样输出的结果就不对。
还有就是棋盘走过的位置要标记一下,以便下次走不重复走,当回溯的时候的记得把标记给清掉,这个地方有时候也很容易混淆。
(4)、还有一点就是,该程序运算量大,算法复杂度高,所以运行的时候很慢,特别占内存,CPU的使用也很高,几乎都在70%到90%之间,配置低了可能还运行不了。
六、运行结果结果1:结果2:七、实验体会通过本次实验的编写,能够掌握栈的性质以及它的应用。
这次实验花了很多时间才完成,其实本应该早完成的,在检查的过程中有多多少少修改完美了一下,不过算法思想却没有改变。
这个程序也让我头疼了几次,就是运行速度很慢,要等很久才能输出结果,这样的话很占内存资源,而且CPU的使用记录也很高,主要是它需要的运算太多,所以CPU 使用记录也是很高的。
虽然我也参考了一些优化的算法,可以找到最优路进走,但是这些最优算法都和栈的应用失去了联系,本次的实验主要目的就是要了解栈,所以不用栈来写该程序就失去了该实验的意义。