数据结构课程设计之九宫格(2)

int next(Linklist parent,Linklist *child,int flag) {

char tem[10]={0}; int temp;

sprintf(tem,\

*child=(Linklist)malloc(sizeof(LNode)); for(temp=0;temp<9;temp++)//找到空格所在位置 if(tem[temp]=='9')break; switch(flag) {

case

U:swap(&tem[temp],&tem[temp-3]);nextpath(parent,*child,temp-3);break; case

D:swap(&tem[temp],&tem[temp+3]);nextpath(parent,*child,temp+3);break; case

L:swap(&tem[temp],&tem[temp-1]);nextpath(parent,*child,temp-1);break; case

R:swap(&tem[temp],&tem[temp+1]);nextpath(parent,*child,temp+1);break; }

(*child)->flag=parent->flag;

sscanf(tem,\ (*child)->fangxaing=flag; return 0; }

int f(int n) {//哈希函数

int m=0,i,a[8]={40320,5040,720,120,24,6,2,1}; char tem[9];

sprintf(tem,\ for(i=0;i<8;i++) {

m=m+(tem[i]-49+check1(i,tem)-i)*a[i]; } //

a=((n/100000000)-1)*40320+(((n0000000)/10000000)-1)*5040+(((n000000)/1000000)-1)*720+(((n00000)/100000)-1)*120; //

m=a+(((n0000)/10000)-1)*24+(((n000)/1000)-1)*6+(((n00)/100)-1)*2+(((n0)/10)-1); return m+1; }

int inhxb(Linklist tem,Linklist a[])

{//哈希函数为所有比表示这个状态的各位不相等的九位数小的各位不相等的九位数的个数，所以不会产生冲突

//将tem放入正确的位置，并利用结点中的next构造一个头结点为hxb[0]的单链表便于之后释放空间 int n,m; n=tem->data; m=f(n); a[m]=tem;

tem->next1=a[0]; a[0]=tem; return 1; }

int bfs(Queue Q,Linklist parent,Linklist hxb[]) {//对结点tem进行宽度优先搜索，并将子状态入队列， int m,x,y;//x,y表示空格在3*3矩阵中的位置， char temp[9]; Linklist child; m=f(parent->data); if(hxb[m]!=0) {

if(hxb[m]->flag==parent->flag) return 1; else

return 0; }

inhxb(parent,hxb);//进入已搜索的列表 sprintf(temp,\ for(m=0;m<9;m++)//找到空格所在位置 if(temp[m]=='9')break; y=m%3+1;x=m/3+1;

if(x<3&&parent->fangxaing!=U) {

next(parent,&child,D); EnQueue(Q,child); }

if(x>1&&parent->fangxaing!=D) {

next(parent,&child,U); EnQueue(Q,child); }

if(y<3&&parent->fangxaing!=L) {

next(parent,&child,R); EnQueue(Q,child);

}

if(y>1&&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*)calloc(362881,sizeof(Linklist)); hxb[0]=(Linklist)malloc(sizeof(LNode)); hxb[0]->next1=0;

int flag1=1,flag2=1,i,j,k;//找到结果时flag=0；i,j,k作为计数量使用 char *b=\

InitLNode(&l1,a,0);//初始化节点l1,l2 InitLNode(&l2,b,1);

InitQueue(&m);//初始化队列m,n InitQueue(&n);

EnQueue(&m,l1);//l1,l2入队列 EnQueue(&n,l2); while(flag1&&flag2) {

dequeue(&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(hxb[i]->path)); strcpy((*path),temp1->path);

for(j=strlen(temp1->path),k=strlen(hxb[i]->path)-1;k>=0;j++,k--) (*path)[j-1]=hxb[i]->path[k]; } else {

i=f(temp2->data);

(*path)=(char*)malloc(strlen(temp2->path)+strlen(hxb[i]->path)+1); strcpy((*path),hxb[i]->path);

for(j=strlen(hxb[i]->path),k=strlen(temp2->path)-1;k>=0;j++,k--) (*path)[j-1]=temp2->path[k];

}

(*path)[j-1]=0; DestroyQueue(&m); DestroyQueue(&n); Destroylist(hxb[0]);

return 1; }

void move(char *data,char *path) {

int x,y,m,n,tem,a,b;//x,y,m,n用于计算光标位置，a储存当前空格所在，b储存空格将要移动位置 char *temp; temp=data; m=30; n=5;

HideCursor();//隐藏光标

for(tem=0;tem<9;tem++)//找到空格所在位置 if(temp[tem]=='9')break; temp[tem]=' '; 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(\│ │ │ │\ gotoxy(m,n++);printf(\└─┴─┴─┘\ n=tem;

for(x=1;x<4;x++) for(y=1;y<4;y++) {

gotoxy((m-1)+4*y,n+2*x); printf(\ }

a=(*path)-48;

path++;

while((*path)!=0) {

Sleep(1500); b=(*path)-48;

swap(&data[a],&data[b]); a=b; path++; temp=data;

for(x=1;x<4;x++) for(y=1;y<4;y++) {

gotoxy((m-1)+4*y,n+2*x); printf(\ } } }

void print(char *path) {

int x,y,m,i=0; while((*path)!=0) {

if((i%3)==0)printf(\ m=(*path)-48; y=m%3+1;x=m/3+1;

printf(\ path++; i++; }

printf(\ system(\}

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说教育文库数据结构课程设计之九宫格(2)在线全文阅读。