千金求 马踏棋盘 代码 急用～！
数据结果课程设计 马上要用可以提供完好代码者 马上送出1000分
谢谢了！
2005-06-22 15:44
2005-07-06 21:14
2005-07-10 21:24
2005-07-17 23:24
班级：02级计算机2班 姓名：刘晓明 学号：200201020219
完成日期：2004年11月20日
将马随即放在国际象棋的8×8棋盘Board[8][8]的某个方格中，马按走棋规则进行移动。要求每个方格只进入一次，走遍棋盘上全部64个方格。编制非递归程序，求出马的行走路线，并按求出的行走路线，将数字1,2,……,64依次填入一个8×8的方阵，输出之。
测试数据：由读者指定。可自行指定一个马的初始位置(i,j),0<=i,j<=7。
按照顺时针顺序，每次产生一个新的路点，并验证此路点的可用性，需要考虑的问题包括是否超出棋盘和此点已经走过与否。如新路点可用，则入栈，并执行下一步，每次按照上一路点的位置生成新路点。如一个路点的可扩展路点数为0，则走不下去了，进行回溯。
程序中使用了菜单式设计，操作的输入输出均有提示。主要文件分为dsoper.h和ui.h。分别负责数据结构操作和用户界面显示。
dsoper.h中的主要函数解释如下：
l void Calc(HorsePoint init)用于计算路程的入口函数
l HorsePoint GetNewPoint(HorsePoint *parent) 从parent节点产生一个新节点，方向按照parent.dir方向递增
l void PushStack(HorsePoint pos)入栈
l void PushStack(HorsePoint pos, int dir)入栈重载函数
l HorsePoint PopStack(void)出栈
l void initial(void) 初始化应用程序各个全局变量
ui.h中的主要函数解释如下：
l HorsePoint GetInitPoint(void) 请求输入马的初始位置
l CmdChar GetCommand(void) 显示菜单，并从其中获取菜单命令
l void ShowTable(void) 按照棋盘模型显示输出数据
l void ShowStep(void) 按照步进模型显示输出数据
l void SaveToFile(void) 保存到文件rt.txt中
数据结构定义：
typedef struct horsepoint
{
int x;
int y;
int dir; //下一步的走向，初始化-1，有效0-7
}HorsePoint;
其中dir分量用于指示相对于当前路点的下一路点方向，
全局变量定义：
bool Board[WIDTH][WIDTH] 定义棋盘中各点是否已经走过，未走为false
HorsePoint Path[MAX_LEN] 定义马的行走路径
int scount已经进入路径栈的元素个数
2005-09-13 15:44
文件main.cpp
/*
Name: main.cpp
Copyright: Copyright@1999-2004, Gashero Liu.
Author: Gashero Liu.
Date: 16-11-04 20:41
Description: 程序主文件，仅含main函数
*/
#include <iostream>
#include <stdlib.h>
#ifndef DATASTRUCT_H
#define DATASTRUCT_H
#include "datastruct.h"
#endif
#ifndef DSOPER_H
#define DSOPER_H
#include "dsoper.h"
#endif
#ifndef UI_H
#define UI_H
#include "ui.h"
#endif
using namespace std;
//--------------------------------全局变量定义 ---------------------------------
bool Board[WIDTH][WIDTH]; //定义棋盘中各点是否已经走过，未走false
HorsePoint Path[MAX_LEN]; //定义马的行走路径
int scount; //已经进入路径栈的元素个数
int main(int argc, char *argv[])
{
CmdChar cmd; //命令字符
HorsePoint init;//马的初始位置
initial();
while((cmd=GetCommand())!=CMD_EXIT)
{
switch(cmd)
{
case CMD_NEW:
{
init=GetInitPoint();
Calc(init);
break;
}
case CMD_TABLE:
{
ShowTable();
break;
}
case CMD_STEP:
{
ShowStep();
break;
}
case CMD_SAVE:
{
SaveToFile();
break;
}
}
}
//system("PAUSE");
return 0;
}
2005-09-13 15:46
文件dsoper.h:
/*
Name: dsoper.h
Copyright: Copyright@1999-2004, Gashero Liu.
Author: Gashero Liu.
Date: 16-11-04 12:48
Description: 数据结构的操作，包含栈和队列的操作
*/
#ifndef DATASTRUCT_H
#define DATASTRUCT_H
#include "datastruct.h"
#endif
//引用全局变量
extern bool Board[WIDTH][WIDTH];
extern HorsePoint Path[MAX_LEN];
extern int scount;
//结束引用全局变量
//---------------------------------function declaration-------------------------
void Calc(HorsePoint init);
/*计算路程的入口函数*/
HorsePoint GetNewPoint(HorsePoint *parent);
/*从parent节点产生一个新节点，方向按照parent.dir方向递增，如果无法产生新的
结点，则parent.dir==-1*/
void PushStack(HorsePoint pos);
void PushStack(HorsePoint pos, int dir);
/*结点pos入栈Path,入栈后scount++;相应Board对应点=true*/
HorsePoint PopStack(void);
/*给栈Path，出栈一个元素，并返回，scount--,对应点Board=false;*/
void initial(void);
/*初始化应用程序各个全局变量*/
//---------------------------------function defination--------------------------
void Calc(HorsePoint init) //-----------------------------------------------
{
int oc=0,wc=0;
HorsePoint npos; //下一结点
HorsePoint *ppos; //当前结点
initial();
ppos=&init;
PushStack(*ppos);
while(!(scount==0 || scount==MAX_LEN))
{
oc++;
if(oc==100000000)
{
oc=0;
wc++;
printf("已执行%d亿次，入栈深度%d\n",wc,scount);
//system("PAUSE");
}
ppos=&Path[scount-1];
npos=GetNewPoint(ppos);
if(ppos->dir!=INVALID_DIR)
{
PushStack(npos,ppos->dir);//产生了一个有效的下步结点，入栈
//printf("PushStack: (%d,%d),last.dir:%d,scount=%d\n",npos.x,npos.y,ppos->dir,scount);
//system("pause");
}
else
{
PopStack();//没有有效的下步结点，出栈
//printf("PopStack : scount:%d\n",scount);
}
//system("pause");
}
printf("共%亿零%d次,Scount:%d\n",wc,oc,scount);
}
HorsePoint GetNewPoint(HorsePoint *parent) //----------------------------------
{
int i;
HorsePoint newpoint;
int tryx[MAX_DIR]={ 1, 2, 2, 1,-1,-2,-2,-1};
int tryy[MAX_DIR]={-2,-1, 1, 2, 2, 1,-1,-2};
newpoint.dir=INVALID_DIR;
parent->dir=parent->dir+1;
for(i=parent->dir;i<MAX_DIR;i++)
{
newpoint.x=parent->x+tryx[i];
newpoint.y=parent->y+tryy[i];
if(newpoint.x<WIDTH && newpoint.x>=0 &&
newpoint.y<WIDTH && newpoint.y>=0 &&
Board[newpoint.x][newpoint.y]==false)
{
parent->dir=i;
//Board[newpoint.x][newpoint.y]=true;
return newpoint;
}
}
parent->dir=INVALID_DIR;//没有有效的下一步方向
return newpoint;//返回一个无关紧要的值
}
2005-09-13 15:46
void PushStack(HorsePoint pos) //------------------------------------------
{
Board[pos.x][pos.y]=true;
Path[scount]=pos;
scount++;
}
void PushStack(HorsePoint pos, int dir) //-------------------------------------
{
Path[scount-1].dir=dir;
PushStack(pos);
}
HorsePoint PopStack(void) //--------------------------------------------------
{
//std::cout << "PopStack" << std::endl;
HorsePoint pos;
scount--;
pos=Path[scount];
Board[pos.x][pos.y]=false;
Path[scount].dir=INVALID_DIR;
return pos;
}
void initial(void) //--------------------------------------------------------
{
int i,j;
for(i=0;i<WIDTH;i++)
{
for(j=0;j<WIDTH;j++)
{
Board[i][j]=false;
}
}
for(i=0;i<MAX_LEN;i++)
{
Path[i].x=0;
Path[i].y=0;
Path[i].dir=INVALID_DIR;
}
scount=0;
}
2005-09-13 15:47
文件ui.h：
/*
Name: ui.h
Copyright: Copyright@1999-2004, Gashero Liu.
Author: Gashero Liu.
Date: 16-11-04 12:54
Description: 用户交互操作头文件，另含文件存取
*/
#include <conio.h>
#ifndef DATASTRUCT_H
#define DATASTRUCT_H
#include "datastruct.h"
#endif
//引用全局变量
extern bool Board[WIDTH][WIDTH];
extern HorsePoint Path[MAX_LEN];
extern int scount;
//结束引用全局变量
//-----------------------function declaretion-----------------------------------
HorsePoint GetInitPoint(void);
/*请求输入马的初始位置*/
CmdChar GetCommand(void);
/*显示菜单，并从其中获取菜单命令*/
void ShowTable(void);
/*按照棋盘模型显示输出数据*/
void ShowStep(void);
/*按照步进模型显示输出数据*/
void SaveToFile(void);
/*保存到文件rt.txt中*/
//---------------------------------function defination--------------------------
HorsePoint GetInitPoint(void) //----------------------------------------------
{
HorsePoint pos;
do
{
for(int i=0;i<24;i++)
{
printf("\n");//产生24个换行符来屏蔽上一页的信息
}
printf("\t\t\t\t请输入马的初始位置x,y：");
scanf("%d,%d",&pos.x,&pos.y);
}while(pos.x>=WIDTH || pos.y>=WIDTH ||
pos.x<0 || pos.y<0);
pos.dir=INVALID_DIR;
return pos;
}
CmdChar GetCommand(void) //----------------------------------------------------
{
char cmd;
while(true)
{
printf("\n\n\n\n");
printf("\t\t\t\t马走棋盘演示程序\n");
printf("\t\t\t\t 版本:v1.2\n\n");
printf("\t\t\t\t [n]新游戏\n");
printf("\t\t\t\t [t]输出棋盘模型\n");
printf("\t\t\t\t [s]步进输出\n");
printf("\t\t\t\t [f]保存至文件rt.txt\n");
printf("\t\t\t\t [x]退出\n");
printf("\n\n\n\n\n\n\n\n\n\n\n\n\n\n");
/*使用n多个换行符来刷屏，因为我找不到可以跨平台的清屏函数*/
cmd=getch();
switch(cmd)
{
case 'n':
{
return CMD_NEW; //开始新游戏
break;
}
case 't':
{
return CMD_TABLE; //输出棋盘模型
break;
}
case 's':
{
return CMD_STEP; //输出步进模型
break;
}
case 'f':
{
return CMD_SAVE; //保存至文本文件rt.txt
break;
}
case 'x':
{
return CMD_EXIT; //退出本程序
break;
}
default:
{
cmd='\0';
continue;
}
}
}
}
2005-09-13 15:48
void ShowTable(void) //--------------------------------------------------------
{
int ft[WIDTH][WIDTH];
int step=0;
HorsePoint pos;
if(scount==MAX_LEN)
{
for(int i=0;i<MAX_LEN;i++)
{
step++;
pos=Path[i];
ft[pos.x][pos.y]=step;
}
for(int i=0;i<WIDTH;i++)
{
printf("\t\t\t\t");
for(int j=0;j<WIDTH;j++)
{
if(ft[i][j]<10)
{
printf(" ");//输出一个空格来保持对齐
}
printf("%d ",ft[i][j]);
}
printf("\n");
}
printf("\n\n\n\n\n\n\n\n");
system("pause");
}
else
{
printf("\t\t\t\t任务未完成或失败，没有有效数据\n");
system("pause");
}
}
void ShowStep(void) //--------------------------------------------------------
{
int ft[WIDTH][WIDTH];
int step=0;
HorsePoint pos;
char cmd;
if(scount==MAX_LEN)
{
for(step=0;step<MAX_LEN;step++)
{
printf("\n\n\n\n\n\n\n\n");
for(int i=0;i<WIDTH;i++)//清除输出数组内容
{
for(int j=0;j<WIDTH;j++)
{
ft[i][j]=0;
}
}
for(int i=0;i<step;i++)//只显示到step步的内容
{
pos=Path[i];
ft[pos.x][pos.y]=i+1;
}
for(int i=0;i<WIDTH;i++)
{
printf("\t\t\t\t");
for(int j=0;j<WIDTH;j++)
{
if(ft[i][j]<10)
{
printf(" ");
}
if(ft[i][j]==0)
{
printf(" ");
}
else
{
printf("%d ",ft[i][j]);
}
}
printf("\n");
}
printf("\n\n\n\n\n\n\n\n\n");
system("pause");
}
printf("\n\n\n\n\n\n\n\n");
system("pause");
}
else
{
printf("\t\t\t\t任务未完成或失败，没有有效数据\n");
system("pause");
}
}
2005-09-13 15:48
