资源描述：
《《数据结构课程设计》实习报告——马踏棋盘》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、数据结构实习报告题目：设计一个国际象棋的马踏棋盘的演示程序一、需求分析1.用8x8的棋盘boardrSlfS]模拟国际象棋，其屮的格子存放马的位子，马按走棋规则进行移动。每个方格只进去一次，走遍棋盘上全部的64个方格。用非递归的程序，求得马的行走路线，将数字1,2,...64依次填入board[8][8]数组。2.每次在多个可走位置中选择其中一个进行试探，每次选择位置的“最佳策略”，即可走位置最少的作为下一个试探位置。这样可以减少冋溯次数。其余未曾试探过的可走位置用栈管理，以备试探失败时的“回溯”使用。3.演示程序以用户与计算机的对话方式执行，用户输入马初始的位置（i,j）,输出结果显示
2、在其后，即为马的行走路线。测试数据：马的初始位置马的初始位置马的初始位置马的初始位置4.⑴⑵⑶⑷（i,j）（i,j）（i,j）（i,j）为:为:为:为:20153047二、概要设计为实现上述程序功能，需要顺序栈。1.顺序栈的抽象数据类型定义为：ADTSqStack{数据对象：D={ai
3、aiPos,i=1,2,...,n,n^0}数据关系：Rl={
4、ai-lWD,i=2,...,n}基本操作：intInitStack（SqStack&S）操作结果：构造一个空栈SintStackEmpty（SqStackS）操作结果：若栈S为空栈，则返回1,否则返回0intPush（Sq
5、Stack&S,PosTypee）操作结果：插入元素e为新的栈顶元素intPop（SqStack&S,PosType&e）操作结果：插入元素e为新的栈顶元素}2.本程序中包括的四个基本模块：1）主程序模块：Voidmain（）{初始化；求解行走路线;//ChessBoardPath（b,start）;}2）栈模块：实现顺序栈的抽象数据结构3）求下一位置模块：用最优策略求下一个探测位置4）求棋盘行走路线模块：do{若当前位置可通，则{将当前位置纳入栈顶；并将b[i][j]相应位置的值置为当前编号；若当前位置的编号为64,则结束；否则切换当前位置的最优探测方向作为新的当前位置；}否则{若栈不
6、空且栈顶位置尚有其他方向未被探索，则设定新的当前位置为下一个最优位置；若栈不空且栈顶位置的四周均不可走，贝'J{b[i][j]ffi应位置的值置为0；删去栈顶位置；若栈不空，则重新测试新的栈顶位置，直到找到下一个可走位置或出栈至栈空；}}}while(栈不空)；三、详细设计1.棋盘坐标结点类型、栈的结构体typedefstruct{inti;intj;intdir;(PosType;//棋盘坐标位置类型typedefstruct{PosType*base;PosType*top;intstacksize;JSqStack;//顺序栈2.用顺序栈保存走过的路径，基本操作函数如下：intIn
7、itStack(SqStack&S){//构造一个空栈Sif(!(S.base=(PosType*)malloc(STACKJNIT_SIZE*sizeof(PosType))))exit(OVERFLOW);S.top=S.base;S.stacksize=STACK_INIT_SIZE;return1;}intStackEmpty(SqStackS){//若栈S为空栈，则返回1,否则返回0if(S.top==S.base)return1;return0;}intPush(SqStack&S,PosTypee){//插入元素e为新的栈顶元素if(S.top-S.base>=S.stac
8、ksize){S.base=(PosType*)realloc(S.base,(S.stacksize+STACKlNCREMENT)*sizeof(PosType));if(!S.base)exit(OVERFLOW);S.top=S.base+S.stacksize;S.stacksize+=STACKINCREMENT;}*(S.top)++=e;return1;}intPop(SqStack&S,PosType&e){//若栈不空，则删除S的栈顶元素，用e返冋其值，并返回1；否则返回0if(S.top==S.base)return0;e=*—S.top;return1;}1.关于
9、行走路径的其他函数：intPass(PosTypep){//判断当前位置是否可走if(p.i>=0&&p.i<=7&&p.j>=0&&p.j<=7&&b[p.i][p.j]==O)//p(i,j)要在b[8][8]数组范围内，并且该位置不在当前路径中return1;elsereturn0;}intPassCount(PosTypep){//计算可走位置的个数intcount二0,k;for(k=0;kv&k++){p.i+=HTry
