课程设计报告-马踏棋盘.docx

合肥老浣行靠机科学与技术系课程设计报告20122013 学年第二学期2013boardij=0：for (;)printf (z，Please input importpoint (l<=x<=8 and l<=y<=8) nnz，);printf (请输入起始位置的横坐标x二)；scanf (%d, &x);输入起始位置的横坐标printf(n);printf (输入起始位置的纵坐标y二)；scanf (%d, &y);输入起始位置的纵坐标printf(n);if(x>=l&&x<=8&&y>=l&&y<=8)break;printf (，zYour input is worng! ! n，?);printf (/zbegin with %d board: nn，z, 8*(x-l)+y); InitLocation(x-l, y-1); 调用起始坐标函数 return 0;1、问题分析和任务定义将马随机放在国际象棋的8义8棋盘的某个方格中，马按照走棋的规那么进行移动。每个方格只 进入一次，走遍棋盘的全部64个方格。编写算法，求出马的行走路线，并按求出的行走路线, 将1,2,64依次填入一个8义8的方阵，并输出。2、数据结构的选择和概要设计根据需求分析可知，我们所设计的程序要到达让马从任意一起点出发都不重复地遍历所有的 8义8棋格的功能。按照需求，并考虑到程序的可读性，我们按顺序共设计了以下六大模块：(1)定义头文件和宏定义模块：这是C程序必不可少的一个局部，通过头文件来调用程序所 需库函数，而通过宏定义进行宏替换。(2)数据类型定义模块：该模块定义了全局数据结构，它们的作用域为从定义开始到根源 文件结束，以便于让后面很多函数都可以用到它们，而不必再重新定义。(3)探寻路径函数模块：按照马的行走规那么对棋盘进行遍历，寻找马的行走路径，每次仅 访问一个棋格，保证每个棋格都访问到且每个棋格仅访问一次。(4)输出路径函数模块：对探寻路径函数模块中保存下来的顺序进行输出，输出格式按照 棋盘8义8的方阵格式。(5)起始坐标函数模块：将马的起始位置坐标与棋盘坐标联系起来，通过调用探寻路径函 数和输出路径函数到达预期效果。(6)主程序模块：主要是完成棋盘初始化，输入，调用等任务进而来完成马踏棋盘问题。另外，一般来说，当马位于(i,j)时，可以走以下8个位置之一：(i-2, j+1) (i-1, j+2) (i+1, j+2) (i+2, j+1)(i+2, j-1) (i+1, j-2) (i-1, j-2) (i-2, j-1)这 8 个可能的位置可以用两个 一维数组存放，利用一维数组表示马在棋盘内新位置。但是，如果(x,y)靠近棋盘的边缘，上 述位置可能超出棋盘范围，成为不允许的位置。(7) ,流程图图13、详细设计和编码(1)定义头文件和宏定义#include<stdio. h>ttdefine MAXSIZE 100#define N 8(2)数据类型定义int board 8 8;定义棋盘；int Htryl 8 = 1,-1,-2, 2, 2, 1,-1,-2；int Htry28 = 2, -2, 1, 1,-1,-2, 2,-l;Htryl 8和 Htry28分别表示马各个出口位 置相对当前位置的横坐标和纵坐标的增量数组；struct Stackint i;int j;int director;stackMAXSIZE;int top二T;这里是定义栈类型，其中i是横坐标，j是纵坐标，director是存储 方向，stack MAXSIZE表示定义一个栈数组，top二T表示栈指针，可以存储棋盘上的信息以及栈 中元素移动情况。(3)主函数在main。函数中，我们通过一个双重for循环控制棋盘的横纵坐标完成了对棋盘的初始化， 在通过一个三个表达式都为空的for循环来控制输入正确的横纵坐标，直到输入正确才跳出循环 在执行下面的语句，最后通过调用InitLocation(int xi, int yi)函数完整了整个马踏棋盘问题。(4)探寻路径函数定义一个TryPath(int i, int j)函数来探寻马的行走路径，此函数通过while (top>-l)语 句将程序控制在栈不为空的情况下进行循环，在while循环中，首先通过一个双重for循环记录 下当前位置的下一个位置的可行路径条数，在通过一个双重for循环将前面可行路径条数从小到 大排序存储在数组中，最后通过一个for循环来向8个方向进行探寻。(5)输出路径函数定义一个Display。函数来按照棋盘格式输出马的探寻路径，此函数通过一个双重for循环来 实现的，外循环控制横坐标的增加，内循环控制纵坐标的增加。(6)起始坐标函数定义一个InitLocation(int xi, int yi)函数将马的行走路径与棋盘坐标联系起来到达预期 效果，此函数是通过栈将马的起始位置与棋盘坐标联系起来的，并且调用了 TryPath(int i, int j) 函数和Display ()函数。时间复杂度分析：在main。函数中，棋盘初始化的时间复杂度为0 (M2),接着经过一个for循环，其时间复杂度为0(1),再往下调用InitLocation(xT, yT)函数时，要经过一个 while(top>-l),在while循环中还有双重for循环，因此时间复杂度比拟大，故总的时间复杂 度也比拟大。4 .上机调试过程刚开始写程序时，没有对a8中的可行路径条数进行排序，导致程序运行出错，运行结果只 显示所在位置,后来我根据可行路径条数从小到大排序，在ah=number; 将条数存入数组a8 中后添加for (h=0 ;h<8; h+)根据可行路径条数小到大按下表排序放入数组d 8中min=9;for(k=0;k<8;k+)if(min>ak)(min=ak;dh=k;将下表存入数组d8中s=k;) as=9; 程序就可以运行.测试结果及其分析结果1：I 匕Please input importpoint<1< =x< =8 and请输入起始位置的横坐标x = 3输入起始位置的纵坐标y = 1begin viith 17 board：l<=y<=8>3723918494412032173634019505138334835522142163162534447651631245346154432230156455462560711561328958232614291057Press any key to continue2427859图2首先就输入正确的初始位置横纵坐标的运行结果结果2：结果2：* 马 3 沓xy w.xxPlease input importpo int <1< =x< =8 andl<=y<=8请输入起始位置的横坐标x = 3输入起始位置的纵坐标yVour input is worng? ? ?Please input inportpo int<1< =x< =8 andl<=y<=8>睛输入起始位置的横坐标输入起始位置的纵坐标begin with 20 board：161322351811245315223541?1221365225141345710193326350552037582651303364495693144562294059384627643486184154447287423960=4yPress any keyto continue图.3首先就输入错误的初始位置横纵坐标的运行结果5 .用户使用说明运行环境：（1） WIND0WS2000/XP系统（2） Visual C+ 6.0编译环境或TC编译环境输入要求：横纵坐标必须大于等于1,小于等于8.7.参考文献1 .王昆仑，李红.数据结构与算法.北京：中国铁道出版社，2006年5月。2 .严蔚敏，吴伟民.数据结构（C语言版）.北京大学出版社，20063 .谭浩强.C语言程序设计教程.高等教育出版社，19988.附录定义头文件和宏定义#include<stdio. h>ttdefine MAXSIZE 100ttdefine N 8定义棋盘数据类型定义 int board88;int Htryl8>l,-l,-2, 2, 2, 1,-1,-2;存储马各个出口位置相对当前位置行下标的增量数组 int Htry28 = 2,-2, 1, 1,-1,-2, 2,-1;存储马各个出口位置相对当前位置列下标的增量数组struct Stack定义栈类型int i;int j;int director; stackMAXSIZE; int top=T;int i;int j;int director; stackMAXSIZE; int top=T;横坐标纵坐标存储方向定义一个栈数组栈指针探寻路径函数模块 int TryPath(int i, int j) int find, director, number, min; 定义几个临时变量 int il, jl, h, k, s;定义几个临时变量int a8,bl8,b28,d8;定义几个临时数组while (top>-l)栈不空时循环( for(h=0;h<8;h+)/用数组a8记录当前位置的下一个位置的可行路径的条数 number=0;i=stacktop. i+IItryl h; j二stacktop, j+Htry2h; bl h=i; b2h=j;if (board i j =0&&i>=0&&i<8&&j>=0&&j<8)如果找到下一位置(number+;for(k=0;k<8;k+) il=blh+Htryl k; jl=b2h+Htry2k; i f (board iljl =0&&i 1二 0&& il<8&&jl>=0&&jl<8) 如果找到下一位置 记录条数ah=number;ah=number;将条数存入数组a 8中for (h=0; h<8; h+)根据可行路径条数小到大按下表排序放入数组d 8中(min=9;for(k=0;k<8;k+) if(min>ak) (min=ak;d h=k;将下表存入数组d 8中s=k;)as=9;director=stacktop . director;if(top>=63)如果走完整个棋盘返回1return (1);find=0;表示没有找到下一个位置for (h=director+l; h<8; h+)向八个方向进行探寻(i=stacktop. i+Htryldh;j二stacktopj+Htry2dh;if (boardi j =0&&i>=0&&i<8&&j>=0&&j<8) 如果找到下一位置 (find=l;表示找到下一个位置break;if (find=l)如果找到下一个位置进栈stack top. director=director; 存储栈结点的方向top+;栈指针前移进栈stacktop. i=i;stacktop. j=j;stack top, director二T;重新初始化下一栈结点的尝试方向boardi j=top+l;标记棋盘else否那么退栈board stack top, i stacktop. j=0; 清除棋盘的标记 top-;栈指针前移退栈return (0);/输出路径函数模块 void Display()int i, j;for(i=0;i<N;i+)for (j=0：j<N;j+)printf (，zt%d，z, boardi j); 输出马儿在棋盘上路径printf(nn);)printf (n)：)起始坐标函数模块void InitLocation (intxi, int yi)int x, y;top+;stacktop. i=xi;stacktop. j=yi;定义棋盘的横纵坐标变量 栈指针指向第一个栈首 将起始位置的横坐标进栈 将起始位置的纵坐标进栈stack top. director=-l; 将起始位置的尝试方向赋初值boardxiyi=top+l;x二stacktop. i;y二stacktop, j;if (TryPath (x, y)标记棋盘将起始位置的横坐标赋给棋盘的横坐标将起始位置的纵坐标赋给棋盘的纵坐标调用马儿探寻函数，如果马儿探寻整个棋盘返回否那么返Display (); elseprintf ("无解);输出马儿的行走路径主程序模块 int main ()int x, y;int i, j;printf (*马踏棋盘*nri)；for(i=0;i<N;i+)for(j=0;j<N;j+)初始化棋盘