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

#include #include #include #include

#include\#define U 56//up #define D 57//down #define L 58//left #define R 59//right typedef struct LNode{

int data;//用一个各位不相等的9位数来表示当前状态，9表示空格 int flag;//0表示由初始状态生成，1表示由末状态生成

int fangxaing;//表示双亲结点生成此结点时空格的移动方向 char *path;//存放路径的数组下标，比实际值小1

struct LNode *next,*next1;//next用于队列中，next1用于链表 }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};

SetConsoleCursorInfo(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; }

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(tem); }

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,\

(*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; return 0; }

int check(char a[]);//检测初始状态是否有解

int search(char a[],char **path);//寻找解。将路径存入path void print(char *path);//输出路径

void move(char *data,char *path);//动态演示

int main(void) {

int flag=1;//flag为0时退出 char a[9]={0}; char b[9]={0}; char *path; char tem; while(flag) {

printf(\请以字符串形式输入九宫格初始状态，空格用9表示。例如：\\n\ printf(\初始状态┌─┬─┬─┐\\n\ printf(\│ 1│ 2│ 3│\\n\ printf(\├─┼─┼─┤\\n\ printf(\│ 4│ 5│ 6│\\n\ printf(\├─┼─┼─┤\\n\ printf(\│ 7│ 8│ │\\n\ printf(\└─┴─┴─┘\\n\ printf(\输入\\\ scanf(\

getchar();//把回车吃掉 strcpy(b,a); if(check(b)) {

printf(\

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(\ } else {

flag=0; } }

return 0; }

int check1(int n,char a[]) {

int i,m=0;

for(i=0;i

if(a[i]>a[n])m++; return m; }

int check(char a[]) {

int i,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); }

return tem%2; }

void nextpath(Linklist parent,Linklist child,int n) {

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; }

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