课程设计报告-马踏棋盘2

1、合肥老浣必靠机科学与技术系课程设计报告20122013 学年第二学期2013一、课程设计目的“数据结构与算法课程设计”是计算机科学与技术专业学生的集中实践性环节之一，是 学习“数据结构与算法”理论和实验课程后进行的一次全面的综合练习。其目的是要到达理 论与实际应用相结合，提高学生组织数据及编写程序的能力，使学生能够根据问题要求和数 据对象的特性，学会数据组织的方法，把现实世界中的实际问题在计算机内部表示出来并用 软件解决问题，培养良好的程序设计技能。二、课程设计名称及内容名称：马踏棋盘内容：将马随机放在国际象棋的8义8棋盘的某个方格中，马按照走棋的规那么进行移动。 每个方格只进入一次，走遍棋盘

2、的全部64个方格。编写算法，求出马的行走路线，并按求 出的行走路线，将1,2,64依次填入一个8X8的方阵，并输出。三、数据结构的选择和概要设计根据需求分析可知，我们所设计的程序要到达让马从任意一起点出发都不重复地遍历所 有的8X8棋格的功能。按照需求，并考虑到程序的可读性，我们按顺序共设计了以下六大 模块：(1)定义头文件和宏定义模块：这是C程序必不可少的一个局部，通过头文件来调用 程序所需库函数，而通过宏定义进行宏替换。(2)数据类型定义模块：该模块定义了全局数据结构，它们的作用域为从定义开始到 根源文件结束，以便于让后面很多函数都可以用到它们，而不必再重新定义。(3)探寻路径函数模块：按

3、照马的行走规那么对棋盘进行遍历，寻找马的行走路径，每 次仅访问一个棋格，保证每个棋格都访问到且每个棋格仅访问一次。(4)输出路径函数模块：对探寻路径函数模块中保存下来的顺序进行输出，输出格式 按照棋盘8X8的方阵格式。(5)起始坐标函数模块：将马的起始位置坐标与棋盘坐标联系起来，通过调用探寻路 径函数和输出路径函数到达预期效果。(6)主程序模块：主要是完成棋盘初始化，输入，调用等任务进而来完成马踏棋盘问 题。另外，一般来说，当马位于(i,j)时，可以走以下8个位置之一：(i-2, j+1) (i-1, j+2) (i+1, j+2) (i+2, j+1)1、(i+2, j-1) (i+1, j

4、-2) (i-1, j-2)(i-2, j-1)这 8 个可能的位置可以用两个一维数组存放，利用一维数组表示马在棋盘内新位置。但是，如果(x,y)靠近棋盘 的边缘，上述位置可能超出棋盘范围，成为不允许的位置。四、详细设计方案及流程图(1)定义头文件和宏定义#includettdefine MAXSIZE 100ttdefine N 8(2)数据类型定义int board8 8;定义棋盘；int Htryl 8 = 1, -1, -2, 2, 2, 1, -1, -2；int Htry28 = 2, -2, 1, 1,-1,-2, 2,-l;Htryl8和 H宜y28分别表示马各个出 口位置相对

5、当前位置的横坐标和纵坐标的增量数组；struct Stack(int i;int j;int director;stackMAXSIZE;int top=-l;这里是定义栈类型，其中i是横坐标，j是纵坐标，director是 存储方向，stackMAXSIZE表示定义一个栈数组，top=-l表示栈指针，可以存储棋盘上的 信息以及栈中元素移动情况。(3)主函数在mainO函数中，我们通过一个双重for循环控制棋盘的横纵坐标完成了对棋盘的初始 化，在通过一个三个表达式都为空的for循环来控制输入正确的横纵坐标，直到输入正确才 跳出循环在执行下面的语句，最后通过调用InitLocation(int

6、xi, int yi)函数完整了整个 马踏棋盘问题。(4)探寻路径函数定义一个TryPath(int i, int j)函数来探寻马的行走路径，此函数通过while (top-l) 语句将程序控制在栈不为空的情况下进行循环，在while循环中，首先通过一个双重for 循环记录下当前位置的下一个位置的可行路径条数,在通过一个双重for循环将前面可行路 径条数从小到大排序存储在数组中，最后通过一个for循环来向8个方向进行探寻。(5)输出路径函数定义一个Display。函数来按照棋盘格式输出马的探寻路径，此函数通过一个双重for 循环来实现的，外循环控制横坐标的增加，内循环控制纵坐标的增加。(6)

7、起始坐标函数定义一个InitLocation(int xi, int yi)函数将马的行走路径与棋盘坐标联系起来到达 预期效果，此函数是通过栈将马的起始位置与棋盘坐标联系起来的，并且调用了 TryPath(int i, int j)函数和 Display ()函数。时间复杂度分析：在main。函数中，棋盘初始化的时间复杂度为0 (M2),接着经过一 个for循环，其时间复杂度为0 (1),再往下调用InitLocation(xT,y-l)函数时，要经过 一个while(topT),在while循环中还有双重for循环，因此时间复杂度比拟大，故总的 时间复杂度也比拟大。（7）流程图开始v录入横坐

8、标x= 1 &x= 1 &y=8探索路径lllll5、测试结果及其分析:KM XX X X X X X X X X 马踏xxxxxxxxxxxxxxPlease input importpoint1 =x =8 and l=y请输入起始位置的横坐标x = 3输入起始位置的纵坐标y = 1begin viith 17board：37239184944120321736340195051383348355221421631625344476516312453461544322301564554625607115613289582326142910572427859Press any key to

9、continue图2首先就输入正确的初始位置横纵坐标的运行结果结果2：* 马 区沓xy w.xxPlease input importpoint1 =x =8 and l=y请输入起始位置的横坐标x = 3输入起始位置的纵坐标y = 9Vour input is worng? ? ?Please input inportpo int1 =x =8 and l=y请输入起始位置的横坐标x = 3输入起始位置的纵坐标y = 4begin with 20 board：245316132235181115223541?1221365225141345710193326350552037582651303364495693144562294059384627643486184154447287423960Press any key to continue图3首先就输入错误的初始位置横纵坐标的运行结果6、用户使用说明运行环境：(1) WINDOWS/XP系统