数据结构课程设计之九宫格实验报告.docx
- 文档编号:16528079
- 上传时间:2023-07-14
- 格式:DOCX
- 页数:26
- 大小:197.89KB
数据结构课程设计之九宫格实验报告.docx
《数据结构课程设计之九宫格实验报告.docx》由会员分享,可在线阅读,更多相关《数据结构课程设计之九宫格实验报告.docx(26页珍藏版)》请在冰点文库上搜索。
数据结构课程设计之九宫格实验报告
九宫问题
一、简介
1.设计目的:
通过实践掌握用广度优先搜索解决问题的方法
2.问题的描述:
在一个3*3的九宫中,有1—8这8个数,及一个空格随机的摆放在其中的格子里。
如下面左图所示。
要求实现这样的问题:
将九宫问题调整为如右图所示的形式。
调整的规则是:
每次只能将与空格(上、下或左、右)相邻的一个数字平移到空格中。
要求:
问你通过移动中间的空格是否能达到右图所示的状态,如果能,则输出所走的路径,如果不能,则输出:
unsolvable。
最好能画出九宫的图形形式,并在其上动态的演示移动过程。
二、数据结构的设计:
1:
为了了解九宫格的状态所以需要记录九宫格的当前状态
2:
因为要采用是两端同时开始搜索的方法,所以要记录结点是从那个方向搜索到的
3:
为了减少重复搜索,所以要记录当前状态是由父结点怎么移动得来的
4:
需要输出路径,所以得记录从根节点到当前结点空格的移动路径
5:
需要一个队列来实现广度优先搜索
6:
还需要以一种便于访问的方式记录下所有已经访问过的结点,所以构造一个哈希表
7:
便于找到答案后释放所用空间,还需要将所有已搜索过的结点构造成一个链表
综上定义如下结构体:
typedefstructLNode{
intdata;//用一个各位不相等的9位数来表示当前状态,9表示空格
intflag;//0表示由初始状态生成,1表示由末状态生成
intfangxaing;//表示双亲结点生成此结点时空格的移动方向
char*path;//存放路径的数组下标,比实际值小1
structLNode*next,*next1;//next用于队列中,next1用于链表
}LNode,*Linklist;
typedefstruct{
Linklistfront,rear;
}LinkQueue,*Queue;
Linklist*hxb;//哈希表
hxb=(Linklist*)calloc(362881,sizeof(Linklist));
哈希函数为所有比表示这个状态的各位不相等的九位数小的各位不相等的九位数的个数,所以不会产生冲突
三、功能(函数)设计:
本程序的人物要求是完成九宫格的求解并输出结果,根据任务要求,总体上可以分为五个功能模块,分别为:
1:
程序功能介绍和操作提示模块:
在主函数intmain()中显示,用于程序功能的介绍和操作提示。
2:
检查输入九宫格是否有解的模块:
intcheck(chara[]);,用于检测是否有解;
3:
寻找答案模块:
intsearch(chara[],char**path);,用于寻找路径并记录;
4:
输出路径模块:
voidprint(char*path);将以字符串保存的路径转化为坐标输出;
5:
动态演示模块:
voidmove(char*data,char*path);完成动态演示;
功能模块图如下:
N
Y
四、界面设计:
初始界面:
然后根据界面的相关提示进行操作;根据相关操作,界面上显示相应操作结果。
五、程序设计:
1:
程序流程图如下:
N
Y
N
Y
N
Y
2:
函数功能介绍:
2.1:
intmain(void);用于程序功能的介绍和操作提示。
2.2:
intcheck(chara[]);检测数组a中存放的状态是否有解
2.3:
intcheck1(intn,chara[]);基础操作;返回a[0]到a[n-1]中比n大的数的个数;
2.4:
voidnextpath(Linklistparent,Linklistchild,intn);接收父节点以及表示移动方向的n生成子结点的路径;
2.5:
intnext(Linklistparent,Linklist*child,intflag);接收父节点以及表示方向的flag,生成子节点信息;
2.6:
intf(intn);基础操作;哈希函数。
返回n的哈希值;
2.7:
intinhxb(Linklisttem,Linklista[]);将结点tem插入到哈希表中,并将tem插入到链表中。
2.8:
intbfs(QueueQ,Linklistparent,Linklisthxb[]);对结点parent进行宽度优先搜索;
2.9:
intsearch(chara[],char**path);初始化队列,哈希表等为bfs做好前期工作,并在搜索后整合路径到path;
2.10:
voidmove(char*data,char*path);根据路径及初始状态进行动态演示;
2.11:
voidprint(char*path);将以字符串存储的路径转化为坐标输出;
2.12:
intInitLNode(Linklist*M,char*b,intn);基础操作,初始化结点;
2.13:
intInitQueue(QueueQ);基础操作,初始化队列;
2.14:
intEnQueue(QueueQ,Linklisttem);基础操作,将结点tem插入队尾;
2.15:
intdequeue(QueueQ,Linklist*tem);基础操作,用结点指针tem来返回队头元素,并移动队头指针,因为结点继续使用,所以不释放空间;
2.16:
intDestroyQueue(QueueQ);基础操作;销毁队列,释放空间;
2.17:
intDestroylist(Linklista);基础操作,销毁链表,释放空间;
2.18:
voidswap(char*a,char*b);基础操作,通过指针操作来交换a,b的值;
2.19:
voidgotoxy(intx,inty);基础操作,将光标移动至坐标(x,y);
2.20:
voidHideCursor();基础操作,隐藏光标;
3.函数调用关系如下:
……………………………………………
六、运行与测试:
1、测试的数据及其结果:
(1)输入;123456879;应输出unsolvable;
(2)输入:
123456987;应输出路径(1,3)(2,3)(3,3),并进行动态演示;
(3)输入数据应保证可以表示一个九宫格的初始状态,程序不对输入是否合法进行检测;
2、运行与测试期间遇到的问题及其解决办法。
(1).问题1:
输入状态是否有解的判定。
解决方法:
初步想法是先进行搜索,然后队列为空时判定无解。
后经查阅资料得知可以通过数学方法用逆置数来判定。
(2).问题2:
释放内存时出错。
解决方法:
设置断点,单步执行后发现,结点中只用一个next指针无法同时满足队列和链表操作的需求,后在结点中增设一指针解决;
(3).问题3:
单步调试时发现有大量的状态重复进入队列。
解决办法:
在结构体中增设一个变量来记录父结点生成它时空格的移动方向,来避免它的子节点与其父节点相同,重复入队列影响效率。
……………………………………………
七、课程设计总结:
两周的课程设计已经结束了,有收获,也有不足和遗憾,完成了题目的基本要求,也将开始时构思的双向搜索顺利完成,顺利但绝不算成功的构造了一个可以使用的哈希函数,算是基本完成了课程设计,但限于种种原因,还是留下了些许遗憾,因为没有构思出合适哈希函数的原因,哈希表整整使用了4倍于理论上最大值的空间,并且直到最后还没有找到一个合适的方法解决。
而最后关于双向搜索的想法,用优先搜索队列结点较多的一端来代替目前的两端交替搜索,也因为时间的关系没有实现。
八、设计后的思考:
通过本次课程设计,我主要有四点体会,首先是任何程序,无论它们有多复杂,都是由简单的C语句和精密的算法思想结合起来实现的。
只要我们有坚实的基础理论和解决问题的信心以及耐心,便可以把他们分解为一个个的功能模块,在分解为实现功能模块的一些函数,甚至在分解为一些简单基本操作。
把复杂的大问题转化为简单的易于上手的小问题;
第二,关于代码低耦合性的思考,我们实现一个功能函数的时候不能只考虑怎么实现它,还得考虑它的通用性,以及低耦合性,这次设计中使用的关于队列,链表,以及移动光标,隐藏光标的一些基本操作的函数,都是从之前的一些作品里直接拿出来的,只需要做少量甚至不需要修改便可以直接应用。
这次课程设计过程中有几次需要在结构体里加一些元素来满足程序的功能,因为有意识的降低了代码的耦合性,所以当时只需在结构体里加入元素,就可以扩展相应的功能了,而这并不影响之前的模块的正常运行;
第三,关于代码重用性的思考,代码重用性不光是以前做的代码现在可以使用,也包括在一个程序里面把实现功能的操作分解为一些简单基本操作,然后通过对这些基本操作的多次调用来实现相应的功能模块,从而优化了代码的结构,提高了代码的重用性。
并且,细分的操作越简单,出错的可能便越小,排错的难度也会相应的降低。
第四,关于数学知识在程序里的应用,首次有这个感觉是在之前在北大OJ做的一道题,当时在查到我用几十行来模拟过程出来的结果原来可以用一个数学定理用一行便可以得出时,当时就瞬间感觉到了数学的重要性,包括这次的课程设计,不管是利用逆置数判定是否有解,还是后面的哈希函数的构建,都充分证明了,把数学运用到程序里是一件很有必要的事情。
参考文献:
1、杨秀金等.数据结构(C语言版).西安电子科技大学出版社2004
2、谭浩强.C语言程序设计.清华大学出版社.2002
3、李春保.数据结构教程上机实验指导.清华大学出版社.2005
附源代码如下:
#include
#include
#include
#include
#defineU56//up
#defineD57//down
#defineL58//left
#defineR59//right
typedefstructLNode{
intdata;//用一个各位不相等的9位数来表示当前状态,9表示空格
intflag;//0表示由初始状态生成,1表示由末状态生成
intfangxaing;//表示双亲结点生成此结点时空格的移动方向
char*path;//存放路径的数组下标,比实际值小1
structLNode*next,*next1;//next用于队列中,next1用于链表
}LNode,*Linklist;
typedefstruct{
Linklistfront,rear;
}LinkQueue,*Queue;
voidgotoxy(intx,inty)
{
intxx=0x0b;
HANDLEhOutput;
COORDloc;
loc.X=x;
loc.Y=y;
hOutput=GetStdHandle(STD_OUTPUT_HANDLE);
SetConsoleCursorPosition(hOutput,loc);
return;
}
voidHideCursor()
{
CONSOLE_CURSOR_INFOcursor_info={1,0};
SetConsoleCursorInfo(GetStdHandle(STD_OUTPUT_HANDLE),&cursor_info);
}
intInitQueue(QueueQ)
{
Q->front=(Linklist)malloc(sizeof(LNode));
Q->rear=Q->front;
return1;
}
intEnQueue(QueueQ,Linklisttem)
{
Q->rear->next=tem;
Q->rear=tem;
return0;
}
intdequeue(QueueQ,Linklist*tem)
{
*tem=Q->front->next;
Q->front=Q->front->next;
return0;
}
intDestroyQueue(QueueQ)
{
Linklisttem,tem1;
if(Q->front==Q->rear)return0;
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);
return0;
}
intDestroylist(Linklista)
{
Linklisttem;
while(a->next1!
=0)
{
tem=a;
a=a->next1;
free(tem->path);
free(tem);
}
return1;
}
voidswap(char*a,char*b)
{
chartem;
tem=*a;
*a=*b;
*b=tem;
}
intInitLNode(Linklist*M,char*b,intn)
{
inttemp;
(*M)=(Linklist)malloc(sizeof(LNode));
sscanf(b,"%d",&(*M)->data);
(*M)->path=(char*)malloc(2*sizeof(char));
for(temp=0;temp<9;temp++)//找到空格所在位置
if(b[temp]=='9')break;
(*M)->path[0]=temp+48;
(*M)->path[1]=0;
(*M)->flag=n;
(*M)->fangxaing=0;
return0;
}
intcheck(chara[]);//检测初始状态是否有解
intsearch(chara[],char**path);//寻找解。
将路径存入path
voidprint(char*path);//输出路径
voidmove(char*data,char*path);//动态演示
intmain(void)
{
intflag=1;//flag为0时退出
chara[9]={0};
charb[9]={0};
char*path;
chartem;
while(flag)
{
printf("请以字符串形式输入九宫格初始状态,空格用9表示。
例如:
\n");
printf("初始状态┌─┬─┬─┐\n");
printf("\t│1│2│3│\n");
printf("\t├─┼─┼─┤\n");
printf("\t│4│5│6│\n");
printf("\t├─┼─┼─┤\n");
printf("\t│7│8││\n");
printf("\t└─┴─┴─┘\n");
printf("输入\"123456789\"\n");
scanf("%s",a);
getchar();//把回车吃掉
strcpy(b,a);
if(check(b))
{
printf("unsolvable\n");
printf("输入Y测试下一个九宫格,输入其他任意键退出\n");
}
else
{
printf("空格所经路径为\n");
search(a,&path);
print(path);
move(a,path);
gotoxy(30,13);
printf("输入Y测试下一个九宫格,输入其他任意键退出\n");
gotoxy(30,14);
}
tem=getchar();
getchar();//把回车吃掉
if(tem=='y'||tem=='Y')
{
system("cls");
}
else
{
flag=0;
}
}
return0;
}
intcheck1(intn,chara[])
{
inti,m=0;
for(i=0;i if(a[i]>a[n])m++; returnm; } intcheck(chara[]) { inti,tem=0; for(i=0;i<9;i++)//找到空格所在位置 if(a[i]=='9')break; while(i<6) { swap(&a[i],&a[i+3]); i=i+3; } while(i<8) { swap(&a[i],&a[i+1]); i=i+1; }//将空格置于右下角的位置来推算是否成立。 数学原理如下: /* 假设图中的a是3*3数字拼图标准的结果,则对于图b的状态是不可能变换成a的。 证明起来需要用到高等代数里逆序数的概念, 具体的说是用到了一个简单的定理。 定义: 在一个1,2,...,n的排列中,如果一对数的前后位置与大小顺序相反,即前面的数大于后面的数,那么它们就称为一个逆序。 一个排列中逆序的总数就称为这个排列的逆序数。 逆序数为偶数的排列称为偶排列;逆序数为奇数的排列称为奇排列。 如2431中,21,43,41,31是逆序,逆序数是4,为偶排列。 ——这是北大《高等代数》上的定义。 定理: 交换一个排列中的两个数,则排列的奇偶性发生改变。 (证明见任何一本《高等代数》) 我们将空格看成数字9(数字9对应空位),按正常顺序看a图,9个数字排列是123456789,其逆序数是0,是偶排列; b图是123456879,逆序数是1,是奇排列。 我们知道,我们能够移动空块相邻的块, 这里的移动相当于一种特殊的对换(相邻对换),例如: 对于b图,移动6就相当于9和6互换(9向上移动了), 移动7就相当于9和7互换(9向左移动了)。 现在假设从b图经过一系列的平移变到了a图, 则空格块9必然移动(对换)了偶数次(向左一次必然要再向右一次回来,向上一次必然要向下再回来,最终才能够回到右下角的位置), 根据上面的定理最终变成的排列必然是仍然是奇排列(和b相同), 然而a图是偶排列,因而产生矛盾,因此b图不可能通过平移变成最终的a图。 */ for(i=0;i<9;i++)//求逆置数 { tem=tem+check1(i,a); } returntem%2; } voidnextpath(Linklistparent,Linklistchild,intn) { child->path=(char*)malloc(strlen(parent->path)+2); strcpy(child->path,parent->path); child->path[strlen(parent->path)]=n+48; child->path[strlen(parent->path)+1]=0; } intnext(Linklistparent,Linklist*child,intflag) { chartem[10]={0}; inttemp; sprintf(tem,"%d",parent->data); *child=(Linklist)malloc(sizeof(LNode)); for(temp=0;temp<9;temp++)//找到空格所在位置 if(tem[temp]=='9')break; switch(flag) { caseU: swap(&tem[temp],&tem[temp-3]);nextpath(parent,*child,temp-3);break; caseD: swap(&tem[temp],&tem[temp+3]);nextpath(parent,*child,temp+3);break; caseL: swap(&tem[temp],&tem[temp-1]);nextpath(parent,*child,temp-1);break; caseR: swap(&tem[temp],&tem[temp+1]);nextpath(parent,*child,temp+1);break; } (*child)->flag=parent->flag; sscanf(tem,"%d",&((*child)->data)); (*child)->fangxaing=flag; return0; } intf(intn) {//哈希函数 intm=0,i,a[8]={40320,5040,720,120,24,6,2,1}; chartem[9]; sprintf(tem,"%d",n); for(i=0;i<8;i++) { m=m+(tem[i]-49+check1(i,tem)-i)*a[i]; } //a=((n/100000000)-1)*40320+(((n%100000000)/10000000)-1)*5040+(((n%10000000)/1000000)-1)*720+(((n%1000000)/100000)-1)*120; //m=a+(((n%100000)/10000)-1)*24+(((n%10000)/1000)-1)*6+(((n%1000)/100)-1)*2+(((n%100)/10)-1); returnm+1; } intinhxb(Linklisttem,Linklista[]) {//哈希函数为所有比表示这个状态的各位不相等的九位数小的各位不相等的九位数的个数,所以不会产生冲突 //将tem放入正确的位置,并利用结点中的next构造一个头结点为hxb[0]的单链表便于之后释放空间 intn,m; n=tem->data; m=f(n); a[m]=tem; tem->next1=a[0]; a[0]=tem; return1; } intbfs(QueueQ,Linklistparent,Linklisthxb[]) {//对结点tem进行宽度优先搜索,并将子状态入队列, intm,x,y;//x,y表示空格在3*3矩阵中的位置, chartemp[9]; Linklistchild; m=f(parent->data); if(hxb[m]! =0) { if(hxb[m]->flag==parent->flag) return1; else return0; } inhxb(parent,hx
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 课程设计 九宫 实验 报告
![提示](https://static.bingdoc.com/images/bang_tan.gif)