九宫格实现算法.docx

该【九宫格实现算法 】是由【jiyudian11】上传分享，文档一共【9】页，该文档可以免费在线阅读，需要了解更多关于【九宫格实现算法 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。实验目的:通过visualC++进行算法编辑,准确掌握算法运行方式及流程。通过程序实现类似九宫格的拼图效果,也叫做八方块。用最快的时间实现最后的效果:123
456
780
实验原理:先实现一个三行三列数组,再依次比较第一个数与上下左右数值的大小,进行移动,最后实现效果图。计算出一共移动的步数和每移一步的效果。
实验内容:
程序代码如下:
//:定义控制台应用程序的入口点。
//
#inClude""
#inClude<>
#inClude<>
#inClude<>
#defineGOAL123804765//表示我们要找得目标状态struCtNode
{
shortstate[9];//存放结点的状态
shortpos;//空格所在的位置,在数组中用0代表空格
structNode*up;//空格上移后的状态
structNode*down;//空格下移后的状态
structNode*left;//空格左移后的状态
structNode*right;//空格右移后的状态
structNode*parent;//它是从哪一状态变换而来的
structNode*next;//表示在队列中的下一个状态
};
structTree
{
shortkey;//表示当前结点的数值
short*state;//表示当前状态的整个数组,当整颗树生成完毕后这一数组将被释放
shortindex;//表示当前数值在数组中的位置
boolvisited;//对于叶子结点而言,表示这一结点是否被访问过
structTree*next;//指向它的(下一个)兄弟结点,表示这一位置的下一个数structTree*down;//指向它的第一个孩子结点,表示下一位置的第一个数
};
structQueue//定义一个队列用于广度优先遍历
{
structNode*front;structNode*rear;
};
voidInitQueue(structQueue*Q);//初始化一个空队列boolQueueEmpty(structQueue*Q);//判断队列是否为空voidEnQueue(structQueue*Q,structNode*N);//
入队列structNode*DeQueue(structQueue*Q);//出队列,返回队结点voidClearQueue(structQueue*Q);//清空队列
structNode*GetBestPath(structNode*tree);/找到一个最短路径,并返回最后的状态结点,如果没有路径返回NULL
structTree*CreateCheckTree();//生成一个用于检查状态的查询树
voidCreateSubCheckTree(structTree*T);//生成状态检查子树
voidFreeCheckTree(structTree*checkTree);//释放状态检查树的空间
intcheckCount=0;//检查结点状态次数
intdeCount二0;//出队列次数
intenCount二0;//入队列次数
structTree*checkTree;
voidmain()
{
structNode*tree=newstructNode;tree->parent=NULL;
printf("输入0-8的任意一个排列,其中0表示空格所在的位置:\n");for(inti=0;i<=8;i++)
{
scanf("%d",&tree->state[i]);
}
for(inti=0;i<=8;i++)
{
if(tree->state[i]==0)
{
tree->pos=i;
}}tree->next=NULL;intc1=clock();structNode*result=GetBestPath(tree);intc2=clock();
doublet=(c2-c1)/;
printf("状态检查次数:%d,入队列次数:=%d,出队列次数:%d\n",checkCount,enCount,deCount);
if(result!=NULL)
{
intpath[200];
intcount=0;
structNode*N=result;
while(N!=NULL)
{path[count]=N->pos;
N=N->parent;count++;
}
printf("有最短路径,共须%d步。\n下面给出各步空格出现的位置(第一个数为初始位置):\n",count-1);
for(inti=count-1;i>=0;i--)
{
printf("%d",path[i]);
}
}
else
{
printf("不存在路径!");
}
printf("\n所用时间为:%f秒",t);
getchar();
getchar();
}
voidFreeCheckTree(structTree*checkTree)
{
if(checkTree->down!=NULL)
{
FreeCheckTree(checkTree->down);
}
if(checkTree->next!=NULL)
{
FreeCheckTree(checkTree->next);
}
deletecheckTree;
}
structTree*CreateCheckTree()
{
structTree*T=newstructTree;
T->index=0;
T->key=-1;
T->next=NULL;
T->down=NULL;
T->state=newshort[10];
T->state[0]=-1;
for(inti=1;i<=9;i++)
T->state[i]=i-1;
}
CreateSubCheckTree(T);
returnT;
}
voidCreateSubCheckTree(structTree*T)
{
if(T-〉index==8)//如果前八个数都排好了
{
T-〉down=newstructTree;T-〉down-〉key=T-〉state[9];
T-〉down-〉visited=false;T-〉down-〉down=NULL;T-〉down-〉next=NULL;
deleteT-〉state;
}
else
{
structTree*old=T;
for(inti=T-〉index+1;i<10;i++)
{
structTree*current=newstructTree;current-〉state=newshort[10];
for(intj=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所指处inttemp二current-〉state[current-〉index];//以下三句完成交换current-〉state[current-〉index]=current-〉state[i];current-〉state[i]=temp;
if(i==T-〉index+l)//如果是第一个孩子
{
T-〉down=current;old=current;
}
else
{
old-〉next=current;
old=current;
}
CreateSubCheckTree(current);
}deleteT->state;
}
}
boolcheckNode(structNode*N)
{
checkCount++;
structTree*current=checkTree;
for(inti=0;i<9;i++)
{
current=current->down;while(N->state[i]!=current->key)
{
current=current->next;
}
}
if(current->visited==false)
{
current->visited=true;
returntrue;
}
else
{
returnfalse;
}
}
structNode*GetBestPath(structNode*tree)//找到一个最短路径,并返回最后的状态结点,如果没有路径返回NULL
{
checkTree=CreateCheckTree();
// printf("分配完成!\n");
getchar();
inti;
structQueue*Q=newstructQueue;
InitQueue(Q);
EnQueue(Q,tree);while(!QueueEmpty(Q))
{
structNode*N=DeQueue(Q);
intindex=0;
for(i=0;i<=8;i++)
{
index=index*10+N->state[i];
}if(index==GOAL)
{
FreeCheckTree(checkTree);
ClearQueue(Q);
returnN;
}
if(N-〉pos〉=3)//空格可以往上移
{
structNode*up=newstructNode;
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//如果这一状态以前出现过,
{
deleteup;
N-〉up=NULL;
}
}//空格可以往上移
if(N-〉pos〈=5)//空格可以往下移
{
structNode*down=newstructNode;
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//如果这一状态以前出现过,
{
deletedown;
N->down=NULL;
}
}//空格可以往下移
f(N-〉pos!=0&&N-〉pos!=3&&N-〉pos!=6)//空格可以往左移
{
structNode*left=newstructNode;for(i=0;i<=8;i++)
{
left-〉state[i]=N-〉state[i];
}
left-〉state[N-〉pos]=left-〉state[N-〉posT];//完成上移left-〉state[N-〉posT]=0;//同上
left-〉pos=N-〉pos-1;
if(checkNode(left))//如果这一状态以前没有出现过,保留这一状态{
N-〉left=left;left-〉parent=N;EnQueue(Q,left);
}
else//如果这一状态以前出现过,
{
deleteleft;
N-〉left=NULL;
}
}//空格可以往左移
f(N-〉pos!=2&&N-〉pos!=5&&N-〉pos!=8)//空格可以往右移
{
structNode*right=newstructNode;for(i=0;i<=8;i++)
{
right-〉state[i]=N-〉state[i];
}
right-〉state[N-〉pos]二right-〉state[N-〉pos+l];//完成上移right-〉state[N-〉pos+l]=O;//同上right-〉pos=N-〉pos+1;
if(checkNode(right))//如果这一状态以前没有出现过,保留这一状态{
N->right=right;right->parent=N;EnQueue(Q,right);
}
else//如果这一状态以前出现过,
{
deleteright;N->right=NULL;
}}//空格可以往右移
}
FreeCheckTree(checkTree);
returnNULL;
}
voidInitQueue(structQueue*Q)//初始化一个空队列
{
structNode*head=newstructNode;
head->next=NULL;
Q->front=head;Q->rear=head;
};
boolQueueEmpty(structQueue*Q)//判断队列是否为空
{
if(Q->front==Q->rear)
{
returntrue;
}
else
{
returnfalse;
}
};
voidEnQueue(structQueue*Q,structNode*N)//入队列
{
enCount++;
Q->rear->next=N;
Q->rear=N;
};
structNode*DeQueue(structQueue*Q)//出队列,返回队结点{
deCount++;
if(Q->front==Q->rear)
{
printf("队列已空!!\n");returnNULL;
}
else
{
structNode*N=Q->front->next;Q->front->next=N->next;
if(Q->rear==N)
{
Q->rear=Q->front;
}
returnN;
}
}
voidClearQueue(structQueue*Q)//清空队列{
while(!QueueEmpty(Q))
{
delete(DeQueue(Q));
}
}
实验结果:
D:\8block\Debug\
输入0T的任意一个排列,其中0表示空格所在的位置:
157
248
S03
状态检查次数=278172,入队列次数==127017,岀队列次数=12701?肴最短路翟共须前歩。
下面给出各歩空格出现的位置伸一个数为初始位置〉:
741258741034125876341034
所用时间为=.