九宫格实现算法.doc

实验目的：通过visual c++进行算法编辑，准确掌握算法运行方式及流程。
通过程序实现类似九宫格的拼图效果，也叫做八方块。用最快的时间实现最后的效果：1 2 3
4 5 6
7 8 0
实验原理：先实现一个三行三列数组，再依次比较第一个数与上下左右数值的大小，进行移动，最后实现效果图。计算出一共移动的步数和每移一步的效果。
实验内容：
程序代码如下：
// 8block.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define GOAL 123804765//表示我们要找得目标状态

struct Node
{
short state[9];//存放结点的状态
short pos;//空格所在的位置,在数组中用0代表空格
struct Node *up;//空格上移后的状态
struct Node *down;//空格下移后的状态
struct Node *left;//空格左移后的状态
struct Node *right;//空格右移后的状态
struct Node *parent;//它是从哪一状态变换而来的
struct Node *next;//表示在队列中的下一个状态
} ;
struct Tree
{
short key;//表示当前结点的数值
short * state;//表示当前状态的整个数组,当整颗树生成完毕后这一数组将被释放
short index;//表示当前数值在数组中的位置
bool visited;//对于叶子结点而言，表示这一结点是否被访问过
struct Tree * next;//指向它的(下一个)兄弟结点，表示这一位置的下一个数
struct Tree *down;//指向它的第一个孩子结点，表示下一位置的第一个数
};
struct Queue//定义一个队列用于广度优先遍历
{
struct Node * front;
struct Node * rear;
};
void InitQueue(struct Queue *Q);//初始化一个空队列
bool QueueEmpty(struct Queue *Q);//判断队列是否为空
void EnQueue(struct Queue *Q,struct Node *N);//入队列
struct Node * DeQueue(struct Queue *Q);//出队列，返回队结点
void ClearQueue(struct Queue *Q);//清空队列

struct Node * GetBestPath(struct Node *tree);//找到一个最短路径，并返回最后的状态结点，如果没有路径返回NULL
struct Tree * CreateCheckTree();//生成一个用于检查状态的查询树
void CreateSubCheckTree(struct Tree * T);//生成状态检查子树
void FreeCheckTree(struct Tree * checkTree);//释放状态检查树的空间

int checkCount=0;//检查结点状态次数
int deCount=0;//出队列次数
int enCount=0;//入队列次数

struct Tree * checkTree;
void main()
{
struct Node* tree=new struct Node;
tree->parent=NULL;
printf("输入0-8的任意一个排列，其中0表示空格所在的位置:\n");
for(int i=0;i<=8;i++)
{
scanf("%d",&tree->state[i]);
}
for(int i=0;i<=8;i++)
{
if(tree->state [i]==0)
{
tree->pos =i;
}
}
tree->next =NULL;
int c1=clock();
struct Node *result=GetBestPath(tree);
int c2=clock();
double t=(c2-c1)/1000.0;
printf("状态检查次数:%d,入队列次数:=%d,出队列次数:%d\n",checkCount,enCount,deCount);
if(result!=NULL)
{
int path[200];
int count=0;
struct Node *N=result;
while(N!=NULL)
{
path[count]=N->pos;
N=N->parent;
count++;
}
printf("有最短路径，共须%d步。\n下面给出各步空格出现的位置(第一个数为初始位置)：\n",count-1);
for(int i=count-1;i>=0;i--)
{
printf("%d ",path[i]);
}
}
else
{
printf("不存在路径!");
}
printf("\n所用时间为:%f秒",t);
getchar();
getchar();
}
void FreeCheckTree(struct Tree * checkTree)
{
if(checkTree->down!=NULL)
{
FreeCheckTree(checkTree->down);
}
if(checkTree->next!=NULL)
{
FreeCheckTree(checkTree->next);
}
delete checkTree;
}
struct Tree * CreateCheckTree()
{
struct Tree *T = new struct Tree;
T->index =0;
T->key =-1;
T->next =NULL;
T->down =NULL;
T->state =new short[10];
T->state[0]=-1;
for(int i=1;i<=9;i++)
{
T->state [i]=i-1;
}
CreateSubCheckTree(T);
return T;
}
void CreateSubCheckTree(struct Tree * T)
{
if(T->index==8)//如果前八个数都排好了
{
T->down =new struct Tree;
T->down->key =T->state[9];
T->down->visited =false;
T->down ->down =NULL;
T->down ->next =NULL;
delete T->state;
}
else
{
struct Tree *old=T;
for(int i=T->index+1;i<10;i++)
{
struct Tree *current=new struct Tree;
current->state =new short[10];
for(int j=0;j<=9;j++)
{
current->state [j]=T->state [j];
}
current->index =T->index +1;//将指针前移
current->next =NULL;
current->down =NULL;
current->key=current->state[i];//将关键字设置为当前i所指处
int temp=current->state[current->index];//以下三句完成交换
current->state[current->index]=current->state[i];
current->state[i]=temp;
if(i==T->index+1)//如果是第一个孩子
{
T->down=current;
old=current;
}
else
{
old->next =current;
old=current;
}
CreateSubCheckTree(current);
}
delete T->state;
}
}
bool checkNode(struct Node *N)
{
checkCount++;
struct Tree *current=checkTree;
for(int i=0;i<9;i++)
{
current=current->down;
while(N->state[i]!=current->key)
{
current=current->next;
}
}
if(current->visited==false)
{
current->visited =true;
return true;
}
else
{
return false;
}
}
struct Node * GetBestPath(struct Node *tree)//找到一个最短路径，并返回最后的状态结点，如果没有路径返回NULL
{
checkTree=CreateCheckTree();
// printf("分配完成!\n");
getchar();
int i;
struct Queue *Q=new struct Queue;
InitQueue(Q);
EnQueue(Q,tree);
while(!QueueEmpty(Q))
{
struct Node *N=DeQueue(Q);
int index=0;
for(i=0;i<=8;i++)
{
index=index*10+N->state[i];
}
if(index==GOAL)
{
FreeCheckTree(checkTree);
ClearQueue(Q);
return N;
}
if(N->pos>=3)//空格可以往上移
{
struct Node *up=new struct Node;
for(i=0;i<=8;i++)
{
up->state [i]=N->state [i];
}
up->state[N->pos]=up->state [N->pos-3];//完成上移
up->state [N->pos-3]=0;//同上
up->pos =N->pos-3;

if(checkNode(up))//如果这一状态以前没有出现过,保留这一状态
{
N->up =up;
up->parent =N;
EnQueue(Q,up);
}
else//如果这一状态以前出现过，
{
delete up;
N->up =NULL;
}
}//空格可以往上移
if(N->pos<=5)//空格可以往下移
{
struct Node *down=new struct Node;
for(i=0;i<=8;i++)
{
down->state [i]=N->state [i];
}
down->state[N->pos]=down->state [N->pos+3];//完成下移
down->state [N->pos+3]=0;//同上
down->pos =N->pos+3;

if(checkNode(down))//如果这一状态以前没有出现过,保留这一状态
{
N->down =down;
down->parent =N;
EnQueue(Q,down);
}
else//如果这一状态以前出现过，
{
delete down;
N->down =NULL;
}
}//空格可以往下移
if(N->pos!=0 && N->pos!=3 && N->pos!=6)//空格可以往左移
{
struct Node *left=new struct Node;
for(i=0;i<=8;i++)
{
left->state [i]=N->state [i];
}
left->state[N->pos]=left->state [N->pos-1];//完成上移
left->state [N->pos-1]=0;//同上
left->pos =N->pos-1;

if(checkNode(left))//如果这一状态以前没有出现过,保留这一状态
{
N->left =left;
left->parent =N;
EnQueue(Q,left);

}
else//如果这一状态以前出现过，
{
delete left;
N->left =NULL;
}
}//空格可以往左移
if(N->pos!=2 && N->pos!=5 && N->pos!=8)//空格可以往右移
{
struct Node *right=new struct Node;
for(i=0;i<=8;i++)
{
right->state [i]=N->state [i];
}
right->state[N->pos]=right->state [N->pos+1];//完成上移
right->state [N->pos+1]=0;//同上
right->pos =N->pos+1;

if(checkNode(right))//如果这一状态以前没有出现过,保留这一状态
{
N->right =right;
right->parent =N;
EnQueue(Q,right);

}
else//如果这一状态以前出现过，
{
delete right;
N->right =NULL;
}
}//空格可以往右移
}
FreeCheckTree(checkTree);
return NULL;

}
void InitQueue(struct Queue *Q)//初始化一个空队列
{
struct Node * head=new struct Node;
head->next =NULL;
Q->front =head;
Q->rear=head;
};

bool QueueEmpty(struct Queue *Q)//判断队列是否为空
{
if(Q->front ==Q->rear )
{
return true;
}
else
{
return false;
}
};

void EnQueue(struct Queue *Q,struct Node *N)//入队列
{
enCount++;
Q->rear->next=N;
Q->rear=N;
};

struct Node * DeQueue(struct Queue *Q)//出队列，返回队结点
{
deCount++;
if(Q->front ==Q->rear )
{
printf("队列已空!!\n");
return NULL;
}
else
{
struct Node *N=Q->front->next;
Q->front->next=N->next;
if(Q->rear==N)
{
Q->rear =Q->front;
}
return N;
}
}
void ClearQueue(struct Queue *Q)//清空队列
{
while(!QueueEmpty(Q))
{
delete(DeQueue(Q));
}
}
实验结果：