数据结构课程设计之九宫格实验报告.doc

1、数据结构课程设计报告九宫问题 一、简介1设计目的：通过实践掌握用广度优先搜索解决问题的方法2问题的描述： 在一个3*3的九宫中，有18这8个数，及一个空格随机的摆放在其中的格子里。如下面左图所示。要求实现这样的问题：将九宫问题调整为如右图所示的形式。调整的规则是：每次只能将与空格（上、下或左、右）相邻的一个数字平移到空格中。要求：问你通过移动中间的空格是否能达到右图所示的状态，如果能，则输出所走的路径，如果不能，则输出：unsolvable。最好能画出九宫的图形形式，并在其上动态的演示移动过程。 二、 数据结构的设计：1：为了了解九宫格的状态所以需要记录九宫格的当前状态2：因为要采用是两端同时

2、开始搜索的方法，所以要记录结点是从那个方向搜索到的3：为了减少重复搜索，所以要记录当前状态是由父结点怎么移动得来的4：需要输出路径，所以得记录从根节点到当前结点空格的移动路径5：需要一个队列来实现广度优先搜索6：还需要以一种便于访问的方式记录下所有已经访问过的结点，所以构造一个哈希表7：便于找到答案后释放所用空间，还需要将所有已搜索过的结点构造成一个链表综上定义如下结构体：typedef struct LNodeint data;/用一个各位不相等的9位数来表示当前状态，9表示空格int flag;/0表示由初始状态生成，1表示由末状态生成int fangxaing;/表示双亲结点生成此结点时

3、空格的移动方向char *path;/存放路径的数组下标，比实际值小1struct LNode *next,*next1;/next用于队列中，next1用于链表LNode,*Linklist;typedef struct Linklist front,rear;LinkQueue,*Queue;Linklist *hxb;/哈希表hxb=(Linklist*)calloc(362881,sizeof(Linklist);哈希函数为所有比表示这个状态的各位不相等的九位数小的各位不相等的九位数的个数，所以不会产生冲突三、 功能（函数）设计：本程序的人物要求是完成九宫格的求解并输出结果，根据任务要

4、求，总体上可以分为五个功能模块，分别为：1：程序功能介绍和操作提示模块：在主函数int main()中显示，用于程序功能的介绍和操作提示。2：检查输入九宫格是否有解的模块：int check(char a);，用于检测是否有解；3：寻找答案模块：int search(char a,char *path);，用于寻找路径并记录；4：输出路径模块：void print(char *path);将以字符串保存的路径转化为坐标输出；5：动态演示模块：void move(char *data,char *path);完成动态演示；功能模块图如下： int main（）int check(char a)i

5、nt search(char a,char *path)void print(char *path)void move(char *data,char *path)End N Y 四、界面设计：初始界面： 然后根据界面的相关提示进行操作；根据相关操作，界面上显示相应操作结果。五、 程序设计：1：程序流程图如下： N Y N Y N Y 2：函数功能介绍：2.1：int main（void）；用于程序功能的介绍和操作提示。2.2：int check（char a）；检测数组a中存放的状态是否有解2.3：int check1（int n，char a）；基础操作；返回a0到an-1中比n大的数的个

6、数；2.4：void nextpath（Linklist parent,Linklist child,int n）；接收父节点以及表示移动方向的n生成子结点的路径；2.5：int next(Linklist parent,Linklist *child,int flag)；接收父节点以及表示方向的flag，生成子节点信息；2.6：int f(int n)；基础操作;哈希函数。返回n的哈希值；2.7：int inhxb(Linklist tem,Linklist a)；将结点tem插入到哈希表中，并将tem插入到链表中。2.8：int bfs(Queue Q,Linklist parent,Li

7、nklist hxb)；对结点parent进行宽度优先搜索；2.9：int search(char a,char *path)；初始化队列，哈希表等为bfs做好前期工作，并在搜索后整合路径到path；2.10：void move(char *data,char *path)；根据路径及初始状态进行动态演示；2.11：void print(char *path)；将以字符串存储的路径转化为坐标输出；2.12：int InitLNode(Linklist *M,char *b,int n)；基础操作，初始化结点；2.13：int InitQueue(Queue Q)；基础操作，初始化队列；2.14

8、：int EnQueue(Queue Q,Linklist tem)；基础操作，将结点tem插入队尾；2.15：int dequeue(Queue Q,Linklist *tem) ；基础操作，用结点指针tem来返回队头元素，并移动队头指针，因为结点继续使用，所以不释放空间；2.16：int DestroyQueue(Queue Q)；基础操作；销毁队列，释放空间；2.17：int Destroylist(Linklist a)；基础操作，销毁链表，释放空间；2.18：void swap(char *a,char *b)；基础操作，通过指针操作来交换a，b的值；2.19：void gotoxy

9、(int x, int y)；基础操作，将光标移动至坐标（x，y）；2.20：void HideCursor()；基础操作，隐藏光标；3. 函数调用关系如下：六、运行与测试：1、测试的数据及其结果：（1）输入；123456879；应输出unsolvable；（2）输入：123456987；应输出路径(1,3)(2,3)(3,3),并进行动态演示；（3）输入数据应保证可以表示一个九宫格的初始状态，程序不对输入是否合法进行检测；2、运行与测试期间遇到的问题及其解决办法。（1）问题1：输入状态是否有解的判定。解决方法：初步想法是先进行搜索，然后队列为空时判定无解。后经查阅资料得知可以通过数学方法用逆

10、置数来判定。（2） 问题 2：释放内存时出错。解决方法：设置断点，单步执行后发现，结点中只用一个next指针无法同时满足队列和链表操作的需求，后在结点中增设一指针解决；（3） 问题3：单步调试时发现有大量的状态重复进入队列。解决办法：在结构体中增设一个变量来记录父结点生成它时空格的移动方向，来避免它的子节点与其父节点相同，重复入队列影响效率。七、 课程设计总结：两周的课程设计已经结束了，有收获，也有不足和遗憾，完成了题目的基本要求，也将开始时构思的双向搜索顺利完成，顺利但绝不算成功的构造了一个可以使用的哈希函数，算是基本完成了课程设计，但限于种种原因，还是留下了些许遗憾，因为没有构思出合适哈希

11、函数的原因，哈希表整整使用了4倍于理论上最大值的空间，并且直到最后还没有找到一个合适的方法解决。而最后关于双向搜索的想法，用优先搜索队列结点较多的一端来代替目前的两端交替搜索，也因为时间的关系没有实现。八、 设计后的思考：通过本次课程设计，我主要有四点体会，首先是任何程序，无论它们有多复杂，都是由简单的C语句和精密的算法思想结合起来实现的。只要我们有坚实的基础理论和解决问题的信心以及耐心，便可以把他们分解为一个个的功能模块，在分解为实现功能模块的一些函数，甚至在分解为一些简单基本操作。把复杂的大问题转化为简单的易于上手的小问题；第二，关于代码低耦合性的思考，我们实现一个功能函数的时候不能只考虑

12、怎么实现它，还得考虑它的通用性，以及低耦合性，这次设计中使用的关于队列，链表，以及移动光标，隐藏光标的一些基本操作的函数，都是从之前的一些作品里直接拿出来的，只需要做少量甚至不需要修改便可以直接应用。这次课程设计过程中有几次需要在结构体里加一些元素来满足程序的功能，因为有意识的降低了代码的耦合性，所以当时只需在结构体里加入元素，就可以扩展相应的功能了，而这并不影响之前的模块的正常运行；第三，关于代码重用性的思考，代码重用性不光是以前做的代码现在可以使用，也包括在一个程序里面把实现功能的操作分解为一些简单基本操作，然后通过对这些基本操作的多次调用来实现相应的功能模块，从而优化了代码的结构，提高了

13、代码的重用性。并且，细分的操作越简单，出错的可能便越小，排错的难度也会相应的降低。第四，关于数学知识在程序里的应用，首次有这个感觉是在之前在北大OJ做的一道题，当时在查到我用几十行来模拟过程出来的结果原来可以用一个数学定理用一行便可以得出时，当时就瞬间感觉到了数学的重要性，包括这次的课程设计，不管是利用逆置数判定是否有解，还是后面的哈希函数的构建，都充分证明了，把数学运用到程序里是一件很有必要的事情。参考文献：1、杨秀金等. 数据结构（C语言版）. 西安电子科技大学出版社20042、谭浩强. C语言程序设计. 清华大学出版社. 20023、李春保. 数据结构教程上机实验指导. 清华大学出版社.

14、 2005附源代码如下：#include#include#include#include #define U 56/up#define D 57/down#define L 58/left#define R 59/righttypedef struct LNodeint data;/用一个各位不相等的9位数来表示当前状态，9表示空格int flag;/0表示由初始状态生成，1表示由末状态生成int fangxaing;/表示双亲结点生成此结点时空格的移动方向char *path;/存放路径的数组下标，比实际值小1struct LNode *next,*next1;/next用于队列中，next

15、1用于链表LNode,*Linklist;typedef struct Linklist front,rear;LinkQueue,*Queue;void gotoxy(int x, int y)int xx=0x0b;HANDLE hOutput;COORD loc;loc.X=x;loc.Y=y;hOutput = GetStdHandle(STD_OUTPUT_HANDLE);SetConsoleCursorPosition(hOutput, loc);return;void HideCursor() CONSOLE_CURSOR_INFO cursor_info = 1, 0; Set

16、ConsoleCursorInfo(GetStdHandle(STD_OUTPUT_HANDLE), &cursor_info);int InitQueue(Queue Q)Q-front=(Linklist)malloc(sizeof(LNode);Q-rear=Q-front;return 1;int EnQueue(Queue Q,Linklist tem)Q-rear-next=tem;Q-rear=tem;return 0;int dequeue(Queue Q,Linklist *tem)*tem=Q-front-next;Q-front=Q-front-next;return 0

17、;int DestroyQueue(Queue Q)Linklist tem,tem1;if(Q-front=Q-rear)return 0;dequeue(Q,&tem);while(Q-front!=Q-rear)tem1=Q-front;dequeue(Q,&tem);free(tem1-path);free(tem1);free(Q-rear-path);free(Q-rear);return 0;int Destroylist(Linklist a)Linklist tem;while(a-next1!=0)tem=a;a=a-next1;free(tem-path);free(te

18、m);return 1;void swap(char *a,char *b)char tem;tem=*a;*a=*b;*b=tem;int InitLNode(Linklist *M,char *b,int n)int temp;(*M)=(Linklist)malloc(sizeof(LNode);sscanf(b,%d,&(*M)-data);(*M)-path=(char*)malloc(2*sizeof(char);for(temp=0;temppath0=temp+48;(*M)-path1=0;(*M)-flag=n;(*M)-fangxaing=0;return 0;int c

19、heck(char a);/检测初始状态是否有解int search(char a,char *path);/寻找解。将路径存入pathvoid print(char *path);/输出路径void move(char *data,char *path);/动态演示int main(void)int flag=1;/flag为0时退出char a9=0;char b9=0;char *path;char tem;while(flag)printf(请以字符串形式输入九宫格初始状态，空格用9表示。例如：n);printf(初始状态n);printf(t 1 2 3n);printf(tn);p

20、rintf(t 4 5 6n);printf(tn);printf(t 7 8 n);printf(tn);printf(输入123456789n);scanf(%s,a);getchar();/把回车吃掉strcpy(b,a);if(check(b)printf(unsolvablen);printf(输入Y测试下一个九宫格,输入其他任意键退出n);elseprintf(空格所经路径为n);search(a,&path);print(path);move(a,path);gotoxy(30,13);printf(输入Y测试下一个九宫格,输入其他任意键退出n);gotoxy(30,14);te

21、m=getchar();getchar();/把回车吃掉if(tem=y|tem=Y)system(cls);elseflag=0;return 0;int check1(int n,char a)int i,m=0;for(i=0;ian)m+;return m;int check(char a)int i,tem=0;for(i=0;i9;i+)/找到空格所在位置if(ai=9)break;while(i6)swap(&ai,&ai+3);i=i+3;while(i8)swap(&ai,&ai+1);i=i+1;/将空格置于右下角的位置来推算是否成立。数学原理如下：/*假设图中的a是3*3

22、数字拼图标准的结果，则对于图b的状态是不可能变换成a的。证明起来需要用到高等代数里逆序数的概念，具体的说是用到了一个简单的定理。定义：在一个1,2,.,n的排列中，如果一对数的前后位置与大小顺序相反，即前面的数大于后面的数，那么它们就称为一个逆序。一个排列中逆序的总数就称为这个排列的逆序数。逆序数为偶数的排列称为偶排列；逆序数为奇数的排列称为奇排列。如2431中，21，43，41，31是逆序，逆序数是4，为偶排列。这是北大高等代数上的定义。定理：交换一个排列中的两个数，则排列的奇偶性发生改变。（证明见任何一本高等代数）我们将空格看成数字9（数字9对应空位），按正常顺序看a图，9个数字排列是12

23、3456789，其逆序数是0，是偶排列；b图是123456879，逆序数是1，是奇排列。我们知道，我们能够移动空块相邻的块，这里的移动相当于一种特殊的对换（相邻对换），例如：对于b图，移动6就相当于9和6互换（9向上移动了），移动7就相当于9和7互换（9向左移动了）。现在假设从b图经过一系列的平移变到了a图，则空格块9必然移动（对换）了偶数次（向左一次必然要再向右一次回来，向上一次必然要向下再回来，最终才能够回到右下角的位置），根据上面的定理最终变成的排列必然是仍然是奇排列（和b相同），然而a图是偶排列，因而产生矛盾，因此b图不可能通过平移变成最终的a图。*/for(i=0;ipath=(ch

24、ar*)malloc(strlen(parent-path)+2);strcpy(child-path,parent-path);child-pathstrlen(parent-path)=n+48;child-pathstrlen(parent-path)+1=0;int next(Linklist parent,Linklist *child,int flag)char tem10=0;int temp;sprintf(tem,%d,parent-data);*child=(Linklist)malloc(sizeof(LNode);for(temp=0;tempflag=parent-f

25、lag;sscanf(tem,%d,&(*child)-data);(*child)-fangxaing=flag;return 0;int f(int n)/哈希函数int m=0,i,a8=40320,5040,720,120,24,6,2,1;char tem9;sprintf(tem,%d,n);for(i=0;idata;m=f(n);am=tem;tem-next1=a0;a0=tem;return 1;int bfs(Queue Q,Linklist parent,Linklist hxb)/对结点tem进行宽度优先搜索，并将子状态入队列，int m,x,y;/x,y表示空格在3

26、*3矩阵中的位置，char temp9;Linklist child;m=f(parent-data);if(hxbm!=0)if(hxbm-flag=parent-flag)return 1;elsereturn 0;inhxb(parent,hxb);/进入已搜索的列表sprintf(temp,%d,parent-data);for(m=0;m9;m+)/找到空格所在位置if(tempm=9)break;y=m%3+1;x=m/3+1;if(xfangxaing!=U)next(parent,&child,D);EnQueue(Q,child);if(x1&parent-fangxaing

27、!=D)next(parent,&child,U);EnQueue(Q,child);if(yfangxaing!=L)next(parent,&child,R);EnQueue(Q,child);if(y1&parent-fangxaing!=R)next(parent,&child,L);EnQueue(Q,child);return 1;int search(char a,char *path)LinkQueue m,n;/分别用于从初始状态，以及末状态同步开始的两路搜索Linklist l1,l2,temp1,temp2;Linklist *hxb;/哈希表hxb=(Linklist*

28、)calloc(362881,sizeof(Linklist);hxb0=(Linklist)malloc(sizeof(LNode);hxb0-next1=0;int flag1=1,flag2=1,i,j,k;/找到结果时flag=0；i,j,k作为计数量使用char *b=123456789;InitLNode(&l1,a,0);/初始化节点l1,l2InitLNode(&l2,b,1);InitQueue(&m);/初始化队列m,nInitQueue(&n);EnQueue(&m,l1);/l1,l2入队列EnQueue(&n,l2);while(flag1&flag2)dequeue

29、(&n,&temp2);flag2=bfs(&n,temp2,hxb);dequeue(&m,&temp1);flag1=bfs(&m,temp1,hxb);if(0=flag1)i=f(temp1-data);(*path)=(char*)malloc(strlen(temp1-path)+strlen(hxbi-path);strcpy(*path),temp1-path);for(j=strlen(temp1-path),k=strlen(hxbi-path)-1;k=0;j+,k-)(*path)j-1=hxbi-pathk;elsei=f(temp2-data);(*path)=(c

30、har*)malloc(strlen(temp2-path)+strlen(hxbi-path)+1);strcpy(*path),hxbi-path);for(j=strlen(hxbi-path),k=strlen(temp2-path)-1;k=0;j+,k-)(*path)j-1=temp2-pathk;(*path)j-1=0;DestroyQueue(&m);DestroyQueue(&n);Destroylist(hxb0);return 1;void move(char *data,char *path)int x,y,m,n,tem,a,b;/x,y,m,n用于计算光标位置，

31、a储存当前空格所在，b储存空格将要移动位置char *temp;temp=data;m=30;n=5;HideCursor();/隐藏光标for(tem=0;tem9;tem+)/找到空格所在位置if(temptem=9)break;temptem= ;tem=n;gotoxy(m,n+);printf(动态演示：);gotoxy(m,n+);printf();gotoxy(m,n+);printf( );gotoxy(m,n+);printf();gotoxy(m,n+);printf( );gotoxy(m,n+);printf();gotoxy(m,n+);printf( );gotox

32、y(m,n+);printf();n=tem;for(x=1;x4;x+)for(y=1;y4;y+)gotoxy(m-1)+4*y,n+2*x);printf(%c,*temp+);a=(*path)-48;path+;while(*path)!=0)Sleep(1500);b=(*path)-48;swap(&dataa,&datab);a=b;path+;temp=data;for(x=1;x4;x+)for(y=1;y4;y+)gotoxy(m-1)+4*y,n+2*x);printf(%c,*temp+);void print(char *path)int x,y,m,i=0;while(*path)!=0)if(i%3)=0)printf(n);m=(*path)-48;y=m%3+1;x=m/3+1;printf(%d,%d) ,x,y);path+;i+;printf(n);system(Pause);29