当前位置: 代码迷 >> C语言 >> [求助]八数码问题中open栈如何存储?
  详细解决方案

[求助]八数码问题中open栈如何存储?

热度:526   发布时间:2007-04-20 22:56:23.0
[求助]八数码问题中open栈如何存储?

题目:8数码问题
有左图变到右图最少需要几步?
2 7 1 2 3
5 8 4 4 5 6
1 6 3 7 8
下面是我的程序,不知道如何改了,马山就要上交了,急急急!!请高手快帮帮忙,谢谢了
给我重新编一个也行 ,最好帮我修改一下,然后指出错误在哪里?

/****************八数码问题*******************/
#include "stdio.h"
#include "malloc.h"
#include "stdlib.h"
#define N 10
#define MAX 2
#define listincrement 10
int a[N][N]={{2,9,7},{5,8,4},{1,6,3}},b[N][N]={{1,2,3},{4,5,6},{7,8,9}}; //数组a表示初始值,b表示目标数组
int n=3; //数码的大小
typedef struct qnode{ //用队列作存储结构
int magic[N][N];
//struct qnode *next;
}*qnode;
typedef struct queue{
qnode front;
qnode rear;
int listsize;
int lenth;
}linkqueue;
linkqueue *open,*closed;
linkqueue *madequeue()
{
linkqueue *q=NULL;
q=(linkqueue *)malloc(sizeof(linkqueue));
q->front=(qnode)malloc(MAX*sizeof(linkqueue));
q->listsize=MAX;
q->lenth=0;
if(!q->front)exit(0);
q->rear=q->front;
//q->rear=NULL;
return q;
}
qnode spread(qnode u,int *row,int *col,int i)
{
int r,c,temp;
r=*row;
c=*col;
switch(i)
{
case 0:r--;break; //上
case 1:c++;break; //右
case 2:r++;break; //下
case 3:c--;break; //左
}
temp=u->magic[*row][*col];
u->magic[*row][*col]=u->magic[r][c];
u->magic[r][c]=temp;
return u;
}
int notused(qnode v) //如果出现过则返回1
{
int i,j,t1=1,t2=1;
qnode p,q;
p=open->front; //判断vi是否在open表中出现过
q=open->rear;
while(p!=q)
{
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
if(p->magic[i][j]!=v->magic[i][j])
{
t1=0;
break; //仅跳出for循环吗?
}
}
}
if(t1==1)break; //t1=1表示open表中有元素与vi相同
t1=1;
p++;//=p->next;
}
p=closed->front; //判断vi是否在closed表中出现过
q=closed->rear;
while(p!=q)
{
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
if(p->magic[i][j]!=v->magic[i][j])
{
t2=0;
break;
}
}
}
if(t2==1)break; //t2=1表示closed表中有元素和vi相同
t2=1;
p++;//=p->next;
}
if(t1==1||t2==1)return 0;
else
return 1;
}
void addopen(qnode v)
{
int i,j;
qnode p,newbase;
p=open->rear;
for(i=0;i<n;i++)
for(j=0;j<n;j++)
{
if(open->lenth>=open->listsize)
{
newbase=(qnode )realloc(open->rear,(open->listsize+listincrement)*sizeof(linkqueue));
if(!newbase)exit(0);
open->listsize+=listincrement;
open->front=newbase;
}
open->rear->magic[i][j]=v->magic[i][j];
}
open->lenth++;
open->rear++;
//p->next=open->rear;
}
void addclosed(qnode u)
{
qnode newbase;
if(closed->lenth>=closed->listsize)
{
newbase=(qnode )realloc(closed->rear,(closed->listsize+listincrement)*sizeof(linkqueue));
if(!newbase)exit(0);
closed->listsize+=listincrement;
closed->front=newbase;
}
closed->front=u;
closed->rear++;
//closed->front->next=closed->rear;
}
int equel(qnode vi) //如果是目标结点则返回1;
{
int t=1,i,j;
for(i=0;i<n;i++)
for(j=0;j<n;j++)
{
if(vi->magic[i][j]!=b[i][j])
{
t=0;
return t;
}
}
return t;
}
int canmoveto(qnode u,int *row,int *col,int i)
{

int r,c;
r=*row;
c=*col;
switch(i)
{
case 0:r--;break; //上
case 1:c++;break; //右
case 2:r++;break; //下
case 3:c--;break; //左
}
if(r<0||r>=n||c<0||c>=n)
return 0; //若溢出则返回0
else
return 1;
}
void getdirection(qnode u,int *row,int *col)
{
int i,j;
for(i=0;i<n;i++)
for(j=0;j<n;j++)
if(a[i][j]==9)
{
*row=i;
*col=j;
break;
}

}
qnode takeoutopen()
{
int i,j;
qnode u,none=open->front;

u=(qnode)malloc(sizeof(int));
//q->front=(qnode)malloc(MAX*sizeof(linkqueue));
for(i=0;i<n;i++)
for(j=0;j<n;j++)
{
u->magic[i][j]=open->front->magic[i][j];
}
open->front++;//=open->front->next;
//free(none);
return u;
}
void initopen()
{
int i,j;
for(i=0;i<n;i++)
for(j=0;j<n;j++)
{
open->front->magic[i][j]=a[i][j];
}
open->lenth++;
open->rear++;
//open->front->next=open->rear;
}
void readdata()
{
int i,j;
printf("请输入数码的行数(或列数):");
scanf("%d",&n);
printf("请输入初始表:\n");
for(i=0;i<n;i++)
for(j=0;j<n;j++)
scanf("%d",&a[i][j]);
printf("请输入目标表:\n");
for(i=0;i<n;i++)
for(j=0;j<n;j++)
scanf("%d",&b[i][j]);
}
int search()
{
int row,col,f=0;
int i;
qnode u,vi;
initopen(); //初始化open栈
while(open->front!=open->rear)
{
u=takeoutopen(); //从open表中取出一个结点并删除该结点
addclosed(u); //u进入closed表
getdirection(u,&row,&col); //获取结点u中空格的行与列
f++; //记录每一次移动的最小步数
for(i=0;i<4;i++)
{
if(canmoveto(u,&row,&col,i)) //判断能否移动到i所指方向
{
vi=spread(u,&row,&col,i); //拓展新的结点
if(equel(vi)) //判断是不是目标结点,是就带回1
return(f);
if(!notused(vi)) //vi的状态与open表和closed表中的状态都不相同,出现过就带回1
addopen(vi);
}
}//for
}//while
return f;
}//search

void main()
{
int num;
//readdata();
open=madequeue();
closed=madequeue();
num=search();
printf("最优值为:%d\n",num);
}
/*
void search(); //搜索函数
linkqueue *madequeue(); //构造栈函数
void readdata(); //读入数据
void init(); //初始化
qnode takeoutopen(); //从open栈中取出一个元素,并把该元素从栈中删除
void getdirection(qnode,int *,int *) //获取空格元素的行和列
//qnode spread(qnode,int,int,int); //扩展结点
int canmoveto(qnode,int,int,int); //判断能否移动到该方向
int equel(qnode,int); //判断是否是目标结点
void addopen(qnode); //把该点加入到open表
void addclosed(qnode); //把该点加入到closed表*/

/*测试数据
初始结点297
584
163
目标结点123
456
789*/

搜索更多相关的解决方案: 数码  open  

----------------解决方案--------------------------------------------------------
  相关解决方案