杭电数据结构马踏棋盘

数据结构课程设计报告课程名称：数据结构课程设计课程设计题目：马塔棋盘姓 名:院系：计算机学院专业：计算机科学与技术年级：大二学 号:指导教师：王立波2012年5月17日1 课程设计的目的 ,x2 需求分析x3 课程设计报告内容 ,x1、概要设计,x2 、详细设计,x3、测试结果,x4、程序清单,xI / J I 口 I4 小结 ,x7 -口八5 参考文献 ,x1、课程设计的目的（1）熟练使用C+语言编写程序，解决实际问题；（ 2） 了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力；（ 3） 初步掌握软件开发过程的问题分析、 系统设计、 程序编码、 测试等基本方法和技能；（ 4） 提高综合运用所学的理论知识和方法独立分析和解决问题的能力；2、需求分析1 、任务：（一）：设置一个含有 x,y,di 变量的结构体。定义马向八个方向走的所在位置坐标的变化int htrxlenx=-2,-1,1,2,2,1,-1,-2; htryleny=1,2,2,1,-1,-2,-2,-1;（二）：初始化数组 mata88 ，全部赋为 0。（三）：判断该位置是否能走（是否已走过，或超出 8X8 的矩阵）（四）：对马走的下一个可能方向按一定顺序进行处理。将马可能走的下一个方向按照下下 个方向能走的度进行从大到小的顺序压入栈中（不能通过的标记为-1）(五) ：处理棋盘。马的行走路线 ，并按求出的行走路线，将数字 1，2，,， 64 依次填入 8X8 的方阵输出之。定义 curstep=1， mataxy=1;(x,y) 为用户输入的初始数据 ) 判断 path 是否为空，若不为空，判断 path 的栈顶元素的 di 是否小于 0若 di 小于 0，退栈。否则若 mataxy 0(x,y) 为栈顶元素的坐标 ) mataxy=0( 清除走 过痕迹 )Curstep- ；步伐值减一， 出栈 否则 mataxy=+curstep; 对马走过的位置进行标记 根据此位置，重新对马走的下一个可能方向进行排序。 若已走完 64 个位置输出“马在此位置能走遍全部的格子” 则打印 mata88 数组 若 path 为空，则输出“马在此位置不能走遍全部的格子”2、测试数据在 8*8 的矩阵中输出 164 的数，且没有重复3、课程设计报告内容概要设计 (1)在分析题目要求的基础上，我首先设计了一个结构体，定义如下 struct Postint x;int y;int di;/ 该位置能走的方向 ;存储坐标信息。测试结果： :-二:d C : .- ,：3. :请输入开始位置的坐标；0 0马走遍所有格子的路径1142?5211161964303712152863101713251385318592036314049關2762935啊35543?6021263241484524578614744334556252242334654423S67请按任意键继续请输入开始位置的坐标1 1马走遍所有格子的路径37145312392463105413825511402315361352416296425542592657224S351633565144183235043602746211734B30194872S43118496292047请按任意键继续4、小结一、这次课程设计的心得体会通过实践我的收获如下：1巩固和加深了对数据结构的理解，提高综合运用本课程所学知识的能力。2、培养了我选用参考书，查阅手册及文献资料的能力。培养独立思考，深入研究，分析问 题、解决问题的能力。3、通过实际编译系统的分析设计、编程调试，掌握应用软件的分析方法和工程设计方法。二、根据我在实习中遇到得问题，我将在以后的学习过程中注意以下几点：1认真上好专业实验课，多在实践中锻炼自己。2、写程序的过程中要考虑周到，严密。3、在做设计的时候要有信心，有耐心，切勿浮躁。4、认真的学习课本知识，掌握课本中的知识点，并在此基础上学会灵活运用。5、在课余时间里多写程序，熟练掌握在调试程序的过程中所遇到的常见错误，以便能节省 调试程序的时间。5、程序清单：#in clude using namespace std;#include#define lenx 8#define leny 8struct Postint x;int y;int di;/ 该位置能走的方向;class MaTa public:MaTa();MaTa();bool Pass(Post );/该位置是否能走void Sort(Post);/ 对 newseat 根据 di 的大小进行排序void Deal(Post );/ 处理棋盘void Print();/ 输出结果private:int *mata; / 马踏棋盘数组 stack path;/构造函数 ,棋盘大小 8*8MaTa:MaTa()mata=new int*leny;for(int i=0;ilenx;i+) matai=new intleny;for(int j=0;jleny;j+) mataij=0;/ 表赋空MaTa:MaTa()for (int i = 0; i =0 & c.x=0 & c.yleny & matac.xc.y=0); void MaTa:Sort(Post c)Post newseat8,temp;int htrxlenx=-2,-1,1,2,2,1,-1,-2;int htryleny=1,2,2,1,-1,-2,-2,-1;for(int i=0;ilenx;i+)/ 得到下一个可能的位置 newseati.x=c.x+htrxi; newseati.y=c.y+htryi; if(!Pass(newseati)newseati.di=-1;/ 不能通过 di 为 -1 continue;newseati.di=0;for(int j=0;jleny;j+)/newseati 这个位置上可走的方向 di temp.x=newseati.x+htrxj;temp.y=newseati.y+htryj; if(Pass(temp)newseati.di+;for(int i=0;ilenx;i+)for(int j=i;jleny;j+)if(newseati.dinewseatj.di)/ 从大到小排列temp=newseati; newseati=newseatj;newseatj=temp;for(int i=0;ilenx;i+)/ 将所有可能的位置按顺序圧栈 path.push(newseati);void MaTa:Deal(Post start)/ 处理棋盘Post e;int curstep=1; matastart.xstart.y=curstep;Sort(start);while(!path.empty()e=path.top();if (e.di0)matae.xe.y = 0;path.pop();-curstep;elsematae.xe.y = + curstep; Sort(e);if(curstep=lenx*leny)Print();break;if(path.empty()cout 马不能走遍全部 64 个格子 endl; void MaTa:Print()cout 马走遍所有格子的路径 endl;for(int i=0;ilenx;i+)for(int j=0;j=0 & mataij10) cout mataij;elsecout mataij;coutendl;int main()MaTa m_mata;Post start;cout 请输入开始位置的坐标： start.xstart.y;m_mata.Deal(start);system(pause);return 0;5、参考文献C+版)1 万健、王立波、赵葆华、吴志芳 编著 . 数据结构实用教程(