目 录
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();
}