实验实现顺序栈或循环队列的存储.docVIP

实验二 实现顺序栈或循环队列的存储 题目：编制一个马踏棋盘算法实现的程序 班级：计科0603 姓名：李汉刚 学号：20064140303 完成日期：2008-4-20 一、实验目的 （1）、理解栈的特性“后进先出” 和队列的特性“先进先出”。 （2）、仅仅认识到栈和队列是两种特殊的线性表是远远不够的，本次实验的目的在于更深入的了解栈和队列的特性，以便在实际问题背景下灵活运用他们。 （3）、在了解他特性的基础上，还将巩固对这种结构的构造方法的理解。 二、实验环境 （1）Windows XP系统下 （2）编程环境：VC6.0++ 三、实验内容 （1）、要求：在国际象棋8×8棋盘上面，按照国际象棋规则中马的行进规则，实现从任意初始位置，每个方格只进入一次，走遍棋盘上全部64个方格。编制程序，求出马的行走路线，并按求出的行走路线，将数字1，2，…，64依次填入一个8×8的方阵，并输出它的行走路线（棋盘如图所示）。 （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 ? ? ? ? ? ? ? ? （3）、数据结构要求：采用顺序栈或者链栈实现。 四、实验步骤 为了实现上述程序功能，可以采用顺序栈或者链栈来存储它的数据，本实验所需要的存储空间不是很大，不需动态的开辟很多空间，所以采用相对简单的顺序栈来存储数据，既方便有简单，而用链栈在实现上相对比顺序栈复杂的一点。 （一）、概要设计 （1）、顺序栈的抽象数据类型定义： ADT Stack{ 数据对象：D={ai| ai∈（0，1，…，9），i=0,1，2，…，n，n≥0} 数据关系：R={ ai-1, ai | ai-1, ai∈D,i=1,2，…，n} } ADT Stack （2）本程序包含三个模块： 1、主程序模块： void main(){ 定义变量； 接受命令； 处理命令； 退出； } 2、起始坐标函数模块——马儿在棋盘上的起始位置； 3、探寻路径函数模块——马儿每个方向进行尝试，直到试完整个棋盘； 4、输出路径函数模块——输出马儿行走的路径； 各模块之间的调用关系： 输入的初始位置是否正确 否 是 （二）、详细设计 （1）、定义头文件和预定义 #includestdio.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();