西安郵電學院

数据结构

课内实验报告书

一、实验题目：马踏棋盘

二、实验目的：

通过本次实验，熟练掌握抽象数据类型栈和队列的实现，学会使用栈和队列解决具体应用问题，从而体会栈和队列的特点。

三、实验要求：

设计一个国际象棋的马踏遍棋盘的演示程序。

要求：将马随机放在国际象棋的8×8棋盘Board[8][8]的某个方格中，马按走棋规则进行移动。要求每个方格只进入一次，走遍棋盘上全部64个方格。编制非递归程序，求出马的行走路线，并按求出的行走路线，将数字1，2，…，64依次填入一个8×8的方阵，输出之

四、设计与实现过程

（1）栈或队列的定义及其主要操作的实现

struct Chess

{

int x;

int y;

int h;/*h记录下一次需要试探的马字格式的下标值*/

}Chess1[65];

（2）主要算法的描述

void Handlechess(int m,int n)

{

int flag=1,i;

double j=0.0;/*增加了j用于统计while循环的执行次数，很好奇循环到底执行了多少次*/

int chessx[8]={-2,-2,-1,-1,1,1,2,2};/*马字的格式的8个位置，按下标序依次试探*/

int chessy[8]={-1,1,-2,2,-2,2,-1,1};

for(i=1;i<=64;i++)

       Chess1[i].h=0;/*赋初值*/

chess[m][n]=flag;

Chess1[flag].x=m;

Chess1[flag].y=n;

while(flag<64)

{    j+=1.0;

       for(i=Chess1[flag].h;i<8;i++)/*i的初值由Chess1[flag].h确定*/

…… …… 余下全文

《数据结构》

课程设计实验报告

课程名称：     《数据结构》课程设计  

课程设计题目： 马踏棋盘              

姓名：         邱可昉                 

院系：         计算机学院             

专业：         计算机科学与技术       

班级：         10052313               

学号：         10051319               

…… …… 余下全文

《数据结构》

课程设计报告

20##年 月 日

目        录

1、   程序设计的目的

2、   设计题目

3、   分析

4、   设计思想

5、   算法

6、   测试结果

7、   调试分析

8、   小结

1、   课程设计的目的

1、     熟练使用C++语言编写程序，解决实际问题；

2、     了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力；

3、     初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能；

4、     提高综合运用所学的理论知识和方法独立分析和解决问题的能力；

5、     学习并熟悉栈的有关操作；

6、     利用栈实现实际问题；

2、   设计题目

【马踏棋盘】

*问题描述：将马随机放在国际象棋的8X8棋盘Bo阿rd[0..7,0..7]的某个方格中，马按走棋规则进行移动。要求每个方格上只进入一次，走遍棋盘上全部64个方格。编制非递归程序，求出马的行走路线 ，并按求出的行走路线，将数字1，2，…，64依次填入8X8的方阵输出之。

*测试数据：由读者指定,可自行指定一个马的初始位置。

*实现提示：每次在多个可走位置中选择一个进行试探，其余未曾试探过的可走位置必须用适当结构妥善管理，以备试探失败时的“回溯”(悔棋)使用。并探讨每次选择位置的“最佳策略”，以减少回溯的次数。

…… …… 余下全文

实验题目：马踏棋盘

1.需求分析

*问题描述：将马随机放在国际象棋的8X8棋盘Bo阿rd[0..7,0..7]的某个方格中，马按走

棋规则进行移动。要求每个方格上只进入一次，走遍棋盘上全部64个方格。编制非递归程序，求出马的行走路线 ，并按求出的行走路线，将数字1，2，?，64依次填入8X8的方阵输出之。 

*测试数据：由读者指定,可自行指定一个马的初始位置。 

*实现提示：每次在多个可走位置中选择一个进行试探，其余未曾试探过的可走位置必须用适当结构妥善管理，以备试探失败时的“回溯”(悔棋)使用。并探讨每次选择位置的“最佳策略”，以减少回溯的次数。

2、概要设计

为了实现上述程序功能，可以采用顺序栈或者链栈来存储它的数据，本实验所需要的存储空间不是很大，不需动态的开辟很多空间，所以采用相对简单的顺序栈来存储数据，既方便有简单，而用链栈在实现上相对比顺序栈复杂的一点。本程序使用的是顺序栈。

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、探寻路径函数模块——马儿每个方向进行尝试，直到试完整个棋盘；

…… …… 余下全文

   计算机学院

《数据结构》课程设计报告

  课题名称：            马踏棋盘     

课题负责人（学号/姓名）： 黎贵涛 110520121          

同组成员名单（姓名）：    刘伟   110520131          

                         林建彪 110520104          

             

指导教师：            孔令寅            

评阅成绩：                             

…… …… 余下全文

数据结构课程设计报告

      题目：马踏棋盘

学    院   计算机            

专    业   计算机科学与技术 

年级班别   2009级 2班      

学    号   3109005935       

学生姓名   黄丽敏            

指导教师   吴伟民            

成    绩 ____________________

20##年7月

一、【问题描述】

设计一个国际象棋的马踏棋盘的演示过程。

基本要求:

将马随机放在国际象棋的8*8棋盘Board[8][8]的某个方格中，马按走棋规则进行移动，要求每个方格只进行一次，走遍整个棋盘的全部64个方格。编制非递归程序，求出马的行走路线，并按求出的行走路线，将数字1，2，…，64依次填入一个8*8的方阵，输出之。

测试数据：可自行制定一个马的初始位置（i，j），0<=I,j<=7。

…… …… 余下全文

一、问题描述

    问题描述：将马随机放在国际象棋的8X8棋盘Bo阿rd[0..7,0..7]的某个方格中，马按走棋规则进行移动。要求每个方格上只进入一次，走遍棋盘上全部64个方格。编制非递归程序，求出马的行走路线 ，并按求出的行走路线，将数字1，2，…，64依次填入8X8的方阵输出之。

    测试数据：由读者指定,可自行指定一个马的初始位置。

    实现提示：每次在多个可走位置中选择一个进行试探，其余未曾试探过的可走位置必须用适当结构妥善管理，以备试探失败时的“回溯”(悔棋)使用。并探讨每次选择位置的“最佳策略”，以减少回溯的次数。

二、实验目的

  熟练使用栈和队列解决实际问题；

（1）  了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力；

（2）  初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能；

（3）  提高综合运用所学的理论知识和方法独立分析和解决问题的能力；

三、设计过程

算法设计思想：

根据分析先建了2个结构体

struct PosType     //马的坐标位置类型

{

    int m_row;     //行值

    int m_col;      //列值

};

struct DataType     //栈的元素类型

{

    PosType seat;    //马在棋盘中的“坐标位置”

…… …… 余下全文