数据结构实验报告马踏棋盘

时间:2024.4.5

目        录

1  课程设计的目的………………………………………………………………x

2 需求分析………………………………………………………………………x

3  课程设计报告内容……………………………………………………………x

1、概要设计……………………………………………………………………x

2、详细设计……………………………………………………………………x

3、调试分析……………………………………………………………………x

4、用户手册……………………………………………………………………x

5、测试结果……………………………………………………………………x

6、程序清单……………………………………………………………………x

4  小结 …………………………………………………………………………x

5  参考文献     ………………………………………………………………x

20##年5月23日

1、   课程设计的目的

(1)  熟练使用栈和队列解决实际问题;

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

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

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

2、   需求分析

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

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

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

3、课程设计报告内容

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

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

{

       int m_row;     //行值

       int m_col;              //列值

};

struct DataType     //栈的元素类型

{

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

       int di;                    //换方向的次数

};

chess::chess()

bool chess::chessPath(PosType start) //在棋盘中进行试探寻找下一步位置并同时记录位置,以及涉及到的入栈出栈

void chess::Print() //打印马走的路径

PosType chess::NextPos(PosType a,int di)//根据当前点的位置a和移动方向di,试探下一位置

4、总结

一、这次课程设计的心得体会通过实践我的收获如下:

1、巩固和加深了对数据结构的理解,提高综合运用本课程所学知识的能力。

2、培养了我选用参考书,查阅手册及文献资料的能力。培养独立思考,深入研究,分析问题、解决问题的能力。

二、根据我在实习中遇到得问题,我将在以后的学习过程中注意以下几点:

   1、认真上好专业实验课,多在实践中锻炼自己。

2、写程序的过程中尽量在正确的基础上追求简洁。

3、在做设计的时候要有信心,有耐心,切勿浮躁。

4、认真的学习课本知识,掌握课本中的知识点,并在此基础上学会灵活运用,不过也不能完全依赖课本。

5、在课余时间里多写程序,熟练掌握在调试程序的过程中所遇到的常见错误,以便能节省调试程序的时间。            

6、参考文献

(1)万健主编,数据结构实用教程(C++版),电子工业出版社,2011

(2)网上搜索相关程序作为参考

7、程序运行结果:

附件:

#include <iostream>

using namespace std;

#include "SqStack.h"

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

{

       int m_row;     //行值

       int m_col;              //列值

};

struct DataType     //栈的元素类型

{

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

       int di;                    //换方向的次数

};

class chess

{

       public:

                     chess();

                     bool chessPath(PosType);

                     void Print();

       private:

                     PosType NextPos(PosType c , int d );

                     int m_chess[8][8];    // 棋盘数组

      

};

chess::chess()

{

       int i,j;

       for(i=0;i<=7;i++)

       for(j=0;j<=7;j++)

       m_chess[i][j]=0;

}

bool chess::chessPath(PosType start)

{

       SqStack<DataType> path(64);     //创建栈

       PosType curpos;

       DataType e;

      

       curpos=start ;

       int curstep=1;   //第几次走的位置

              do{

                     if(curpos.m_row<=7 && curpos.m_row>=0 &&

                            curpos.m_col>=0 && curpos.m_col<=7)//走在棋盘之内

                     {     if(m_chess[curpos.m_row][curpos.m_col]==0){

             

                            m_chess[curpos.m_row][curpos.m_col]=curstep; //留下足迹,标注当前位置是马第几次走

             

                            e.seat.m_row=curpos.m_row;       

             

                            e.seat.m_col=curpos.m_col;

             

                            e.di=0;

                            path.Push(e);    //当前位置和方向入栈

                            curstep++;

                            if(curstep==65)

                            return true;

              curpos=NextPos(curpos,e.di); }

              else

                     curpos=NextPos(curpos,e.di++); //在棋盘之外自动进行下一次试探

       }

       else{                          //当前位置已走过 

              if(!path.Empty()){

                     e=path.Top();

                     path.Pop();

                     curstep--;

                     while(e.di==7 && !path.Empty()){    //该位置已无路可走

                            m_chess[e.seat.m_row][e.seat.m_col]=0;

                           

                            e=path.Top();                       //退回一步

                           

                            path.Pop();                  

                            curstep--;

                     }

                     if(e.di<7){         //没到可能的最后一个位置

                            e.di++;          //换下一个位置

                            path.Push(e);

                            curstep++;

                            curpos=NextPos(e.seat,e.di);

                     }

              }

       }

}while(curstep<=64); //马已经走的步数

return false;

}

void chess::Print()

{

       int i,j;

       for(i=0;i<8;i++)

              {for(j=0;j<8;j++)

             

              cout<<m_chess[i][j]<<'\t';  //输出对齐,水平制表

             

              cout<<endl;}

             

       cout<<endl;

      

}

PosType chess::NextPos(PosType a,int di)//根据当前点的位置a和移动方向di,试探下一位置

{

       PosType direct[8]={{2,1},{1,2},{-1,2},{-2,1},{-2,-1},{-1,-2},{1,-2},{2,-1}};

       //按照顺时针试探的8个位置

       a.m_row+=direct[di].m_row;

       a.m_col+=direct[di].m_col;

       return a;

}

void main()

{

       PosType first;

       chess chess;

       cout<<"请输入马的初始位置(第几行第几列):";

       cin>>first.m_row>>first.m_col;

       chess.chessPath(first);

       cout<<"马走过的一条路径如下:"<<endl;

    chess.Print();

}

#define _SQSTACK_H_

//定义顺序栈类

template <class ElemType>//声明一个类模板

class SqStack

{

public:                     //顺序栈类的各成员函数

       SqStack(int m = 100);    

       ~SqStack();

     void Clear();

       bool Empty() const;

     int Length() const;

     ElemType & Top() const;

     void Push(const ElemType &e);

     void Pop();

private:                       //顺序栈类的数据成员

    ElemType *m_base;     //基地址指针

    int m_top;            //栈顶指针

       int m_size;           //向量空间大小

};

//构造函数,分配m个结点的顺序空间,构造一个空的顺序栈。

template <class ElemType>

SqStack <ElemType>::SqStack(int m)

{

       m_top = 0;

       m_base = new ElemType[m];

       m_size = m;

}//SqStack

//析构函数,将栈结构销毁。

template <class ElemType>

SqStack <ElemType>::~SqStack()

{

       if (m_base != NULL) delete[] m_base;

}//~SqStack

//清空栈。

template <class ElemType>

void SqStack <ElemType>::Clear()

{

       m_top = 0;

}//Clear

//判栈是否为空,若为空,则返回true,否则返回false。

template <class ElemType>

bool SqStack <ElemType>::Empty() const

{

       return m_top == 0;

}//Empty

//求栈的长度。

template <class ElemType>

int SqStack <ElemType>::Length() const

{

       return m_top;

}//Length

//取栈顶元素的值。先决条件是栈不空。

template <class ElemType>

ElemType & SqStack <ElemType>::Top() const

{

       return m_base[m_top - 1];

}//Top

//入栈,若栈满,则先扩展空间。插入e到栈顶。

template <class ElemType>

void SqStack <ElemType>::Push(const ElemType &e)

{

    if(m_top >= m_size){                  //若栈满,则扩展空间。

              ElemType *newbase;

        newbase = new ElemType[m_size + 10];

        for(int j = 0; j < m_top; j++)

            newbase[j] = m_base[j];  

        delete[] m_base;

        m_base = newbase;

              m_size += 10;

    }

       m_base[m_top++] = e;

}//Push

//出栈,弹出栈顶元素。先决条件是栈非空。

template <class ElemType>

void SqStack <ElemType>::Pop()

{

       m_top--;

}//Pop    

      

      

      


第二篇:数据结构 马踏棋盘 设计 报告


1:实验题目:马踏棋盘,

2:实验目的:队列和栈的操作练习:

3:实验具体内容:

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

4:数据结构算法思想:

数据结构:简单的结构体和相关数组;

算法思想:a :首先定义一个8*8的数组用于存放马的跳步过程;定义方向结点;

b :获得马的第一个踩入点,调用findway()函数,该函数的while()语句将获得下一个要踩入的结点坐标,该过程调用pathnum()函数(注解:该函数给出了可踩入的所有结点各自的路径数目); 在findway()中,选择的要进入的下一个结点就是在pathway()中找到的结点(注解:该结点是可跳入的所有结的中路径最少的一个);

c : 在每步踩入前,将该结点的下标和踩入的次序做记录并输出; d : 读取最后一个结点的相关信息;

5:模块划分

6:详细设计及运行结果:

A:定义一个8*8的数组,用于存放每次踩入的结点位置;

B:获取第一个踩入点;

C:调用findway()函数

Findway() 函数功能介绍:定义一个结点类型数组,用于存放8个下一步可踩入结点的信息;期间调用pathnum() 函数,该函数功能是记录所有下一个可踩入结点的可执行路径数目);选择下一个结点中路径最少的结点为下一个踩入的结点;在进入下一个踩入点前,先保存该结点的信息并输出,然后依次寻找下一个结点;

D:寻找最后一个结点,并赋给相应信息;

运行结果如下:

#include<stdio.h>

#include "conio.h"

#include"stdlib.h"

//#include <time.h>

#define M 8

int board[M][M]; //定义棋盘数组;

// 内存区:

// 全局数据区:全局变量存储在内存的全局数据区,被默认初始化为0;

// 栈区 :存放 动态局部变量,函数参数,函数返回值等;

// 堆区 :比栈区分配内存慢,但堆区实现了动态分配; 如链表,二叉树等动态应用;

typedef struct direct

{

int r,c,pathnum ;

}dir ;

//用来计算当前位置可走的方向数目

int pathnum(int row,int cn)

{

int a,b,count=0 ;

a=row ;

b=cn ;

//当前位置可选方向可以走通,则数目加一

if(a-2>=0&&b-1>=0&&board[a-2][b-1]==0)

count++;

if(a-2>=0&&b+1<M&&board[a-2][b+1]==0)

count++;

if(a+2<M&&b-1>=0&&board[a+2][b-1]==0)

count++;

if(a+2<M&&b+1<M&&board[a+2][b+1]==0)

count++;

if(a-1>=0&&b+2<M&&board[a-1][b+2]==0)

count++;

if(a-1>=0&&b-2>=0&&board[a-1][b-2]==0)

count++;

if(a+1<M&&b+2<M&&board[a+1][b+2]==0)

count++;

if(a+1<M&&b-2>=0&&board[a+1][b-2]==0)

count++;

return count ;

}

//寻找路径函数

void findway(int m,int n)

{

dir f[8],path ;

int i,j,k, stepnum ;

stepnum=1 ;

i=m ;

j=n ;

while(stepnum<M*M && i>=0 && j>=0)

{

board[i][j]=stepnum;

printf("%d,%d,%d ",i,j,board[i][j]);

path.pathnum=8 ; //用来标志可走方向数的最小值 for(k=0;k<8;k++) //对方向数组赋初值 {

f[k].r=-1 ;

f[k].c=-1 ;

}

//如果第一个方向可走,则将坐标及可选方向数赋给f[0],以下同理 if(i-2>=0&&j-1>=0)

{

f[0].r=i-2 ;

f[0].c=j-1 ;

f[0].pathnum=pathnum(f[0].r,f[0].c);

}

if(i-2>=0&&j+1<M)

{

f[1].r=i-2 ;

f[1].c=j+1 ;

f[1].pathnum=pathnum(f[1].r,f[1].c);

}

if(i+2<M&&j-1>=0)

{

f[2].r=i+2 ;

f[2].c=j-1 ;

f[2].pathnum=pathnum(f[2].r,f[2].c);

}

if(i+2<M&&j+1<M)

{

f[3].r=i+2 ;

f[3].c=j+1 ;

f[3].pathnum=pathnum(f[3].r,f[3].c);

}

if(i-1>=0&&j+2<M)

{

f[4].r=i-1 ;

f[4].c=j+2 ;

f[4].pathnum=pathnum(f[4].r,f[4].c);

}

if(i-1>=0&&j-2>=0)

{

f[5].r=i-1 ;

f[5].c=j-2 ;

f[5].pathnum=pathnum(f[5].r,f[5].c);

}

if(i+1<M&&j-2>=0)

{

f[6].r=i+1 ;

f[6].c=j-2 ;

f[6].pathnum=pathnum(f[6].r,f[6].c);

}

if(i+1<M&&j+2<M)

{

f[7].r=i+1 ;

f[7].c=j+2 ;

f[7].pathnum=pathnum(f[7].r,f[7].c);

}

//寻找当前位置的八个方向中的可走方向数最少的方向作为新的方向

for(k=0;k<8;k++)

if(f[k].r>=0 && f[k].c>=0 && f[k].pathnum<=path.pathnum && board[f[k].r][f[k].c]==0 && f[k].pathnum>0)

{

path.pathnum=f[k].pathnum;

path.r=f[k].r ;

path.c=f[k].c ;

}

i=path.r ;

j=path.c ;

stepnum++;

}

board[i][j]=M*M-1 ; //倒数第二个踩入点;

// 寻找最后一个踩入点;

if(i-2>=0&&j-1>=0&&board[i-2][j-1]==0)

{

i=i-2 ;

j=j-1 ;

}

else if(i-2>=0&&j+1<M&&board[i-2][j+1]==0)

{

i=i-2 ;

j=j+1 ;

}

else if(i-1>=0&&j+2<M&&board[i-1][j+2]==0)

{

i=i-1 ;

j=j+2 ;

}

else if(i+1<M&&j+2<M&&board[i+1][j+2]==0)

{

i=i+1 ;

j=j+2 ;

}

else if(j+2<M&&i+1<=M&&board[i+2][j+1]==0)

{

i=i+2 ;

j=j+1 ;

}

else if(i+2<M&&j-1>=0&&board[i+2][j-1]==0)

{

i=i+2 ;

j=j-1 ;

}

else if(i+1<M&&j-2>=0&&board[i+1][j-2]==0)

{

i=i+1 ;

j=j-2 ;

}

else if(i-1>=0&&j-2>=0&&board[i-1][j-2]==0)

{

i=i-1 ;

j=j-2 ;

}

board[i][j]=M*M ;

printf("%d,%d,%d",i,j,board[i][j]);

}

void main()

{

int r,c,i,j ;

printf("请输入马在棋盘上的首位置,例如 3,4 ,注意两个数之间用逗号隔开且都要小于等于7:\n");

scanf("%d,%d",&r,&c);

findway(r,c);

printf("\n"); //输出棋盘上的路径 for(i=0;i<M;i++) { for(j=0;j<M;j++) printf("%4d",board[i][j]); printf("\n");

}

getch();

}

更多相关推荐:
马踏棋盘实验报告

西安郵電學院数据结构课内实验报告书院系名称实验题目学生姓名专业名称班级学时号间计算机学院马踏棋盘计算机科学与技术20xx年10月10日曾艳指导教师一实验题目马踏棋盘二实验目的通过本次实验熟练掌握抽象数据类型栈和...

马踏棋盘课程设计实验报告

数据结构课程设计实验报告课程名称数据结构课程设计课程设计题目马踏棋盘姓名邱可昉院系计算机学院专业计算机科学与技术班级10052313学号10051319指导老师王立波20xx年5月18日1目录1课程设计的目的3...

马踏棋盘实验报告

数据结构课程设计报告课程名称课程设计题目姓名院系专业年级学号指导教师数据结构课程设计20xx年月日目录1程序设计的目的2设计题目3分析4设计思想5算法6测试结果7调试分析8小结1课程设计的目的123456熟练使...

马踏棋盘实验报告

实验题目马踏棋盘1需求分析问题描述将马随机放在国际象棋的8X8棋盘Bo阿rd0707的某个方格中马按走棋规则进行移动要求每个方格上只进入一次走遍棋盘上全部64个方格编制非递归程序求出马的行走路线并按求出的行走路...

马踏棋盘实验报告单(含代码)

计算机学院数据结构课程设计报告课题名称马踏棋盘课题负责人学号姓名黎贵涛110520xx1同组成员名单姓名刘伟110520xx1林建彪110520xx4指导教师孔令寅评阅意见评阅成绩提交报告时间20xx年4月13...

数据结构课程设计-马踏棋盘实验报告(仅供参考)

数据结构课程设计报告题目马踏棋盘学院计算机专业计算机科学与技术年级班别20xx级2班学号3109005935学生姓名黄丽敏指导教师吴伟民成绩20xx年7月一问题描述设计一个国际象棋的马踏棋盘的演示过程基本要求将...

数据结构课程设计-马踏棋盘实验报告(仅供参考)

一问题描述问题描述将马随机放在国际象棋的8X8棋盘Bo阿rd0707的某个方格中马按走棋规则进行移动要求每个方格上只进入一次走遍棋盘上全部64个方格编制非递归程序求出马的行走路线并按求出的行走路线将数字1264...

马踏棋盘课程设计实验报告

数据结构实验报告课程名称数据结构课程设计题目马踏棋盘姓名柳煜颖系别计算机学号1005131920xx年10月13日11问题分析问题描述将马随机放在国际象棋的8X8棋盘的某个方格中马按走棋规则进行移动要求每个方格...

ERP沙盘实验报告完整版

ERP综合实训中心企业资源计划沙盘实验报告企业名称FERP班级指导教师温雅丽李春艳学期20xx20xx2企业总体经营分析报告总经理CEO为期两天的ERP沙盘模拟很快就结束了由原来的懵懂求教到后来的循序渐进我们从...

管理学沙盘实验报告

课程实验报告专业年级课程名称指导教师周新刚学生姓名学号实验日期实验地点101实验室实验成绩教务处制20xx年4月20日

ERP沙盘实验报告

ERP沙盘实验课程实验报告

沙盘个人实验报告

实验报告课程名称企业行为模拟班级代码组别C3班第14组专业工商管理任课教师龙文学号12250101211姓名实验日期20xx20xx学年第2学期广东财经大学教务处制企业行为模拟沙盘推演与ERP应用个人实验报告C...

马踏棋盘实验报告(13篇)