杭电数据结构马踏棋盘.doc

数据结构课程设计报告课程名称：数据结构课程设计课程设计题目：马塔棋盘姓 名： 院系：计算机学院专 业： 计算机科学与技术年 级： 大二学 号： 指导教师： 王立波2012年5月17日 目 录1 课程设计的目的x2 需求分析x3 课程设计报告内容x1、概要设计x2、详细设计x3、测试结果x4、程序清单x4 小结 x5 参考文献 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 Post int x; int y; int di;/该位置能走的方向;存储坐标信息。 测试结果：4、小结一、这次课程设计的心得体会通过实践我的收获如下：1、巩固和加深了对数据结构的理解，提高综合运用本课程所学知识的能力。2、培养了我选用参考书，查阅手册及文献资料的能力。培养独立思考，深入研究，分析问题、解决问题的能力。3、通过实际编译系统的分析设计、编程调试，掌握应用软件的分析方法和工程设计方法。二、根据我在实习中遇到得问题，我将在以后的学习过程中注意以下几点：1、认真上好专业实验课，多在实践中锻炼自己。2、写程序的过程中要考虑周到，严密。3、在做设计的时候要有信心，有耐心，切勿浮躁。4、认真的学习课本知识，掌握课本中的知识点，并在此基础上学会灵活运用。5、在课余时间里多写程序，熟练掌握在调试程序的过程中所遇到的常见错误，以便能节省调试程序的时间。 5、程序清单：#includeusing namespace std;#include#define lenx 8#define leny 8struct Post int x; int y; int di;/该位置能走的方向; class MaTapublic: MaTa(); MaTa(); bool Pass(Post );/该位置是否能走 void Sort(Post);/对newseat根据di的大小进行排序 void Deal(Post );/处理棋盘 void Print();/输出结果private: int *mata; /马踏棋盘数组 stack path;/构造函数,棋盘大小8*8 MaTa: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为-1continue; 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; else matae.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; else cout mataij; coutendl; int ma