第1页 / 共7页
第2页 / 共7页
第3页 / 共7页
第4页 / 共7页
第5页 / 共7页
第6页 / 共7页
第7页 / 共7页
八数码问题C语言代码.doc
#include
#include
typedef struct Node {
int num[9]; //棋盘状态
int deepth; //派生的深度 g(n)
int diffnum; //不在位的数目 h(n)
int fvalue; //耗散值 f(n)=g(n)+h(n)
struct Node * pre;
struct Node * next;
struct Node * parent;
}numNode;
/* ---------- end of struct numNode ---------- */
int origin[9]; //棋盘初始状态
int target[9]; //棋盘目标状态
int numNode_num,total_step;
numNode *open,*close; //Open 表和 Close 表
numNode *create_numNode()
{
return (numNode *)malloc(sizeof(numNode));
}
numNode *open_getfirst(numNode *head); //返回第一项，并从 Open 表中删除
void open_insert(numNode *head,numNode *item); //向 Open 表中按序插入新节点
void close_append(numNode *head,numNode *item); //向 Close 表中插入新节点
int expand(numNode *item); //扩展节点
int print_result(numNode *item); //打印结果
numNode *copy_numNode(numNode *orgin);
char isNewNode(numNode *open,numNode *close,int num[9]);
//是否在 Open 表或 Close 表中
void print_num(int num[9]); //打印棋盘状态
int diff(int num[9]); //求不在位棋子的个数
void init (); //初始化，获得棋盘初始状态和目标状态
void swap(int *a,int *b);
int operate(int num[],int op);
void free_list(numNode *head);
int main ( int argc, char *argv[] )
{
//初始化 Open 表和 Close 表
open=create_numNode();
close=create_numNode();
open->pre=open->next=close->pre=close->next=NULL;
init(); //由用户输入初始和目标状态
//初始化初始节点
numNode *p1;
p1=create_numNode();
p1->parent=NULL;
p1->deepth=0;
int i=0;
for ( i=0; i<9; i++)
p1->num[i]=origin[i];
open_insert(open,p1);
numNode_num=1;
p1=open_getfirst(open);
while (p1!=NULL)
{
close_append(close,p1);
if(expand(p1))
return EXIT_SUCCESS;
p1=open_getfirst(open);
}
printf("No solution!\n");
return EXIT_SUCCESS;
}
/* ---------- end of function main ---------- */
void init ( )
{
while(1)
{
printf("Please input opriginal status:\nFor example:123456780 stands for\n"
"1
"4
"7
2
5
8
3\n"
6\n"
0\n");
char temp[10];
scanf("%s",&temp);
int i=0;
for ( i=0;i<9 && temp[i]-'0'>=0 && temp[i]-'0'<=8; i++)
origin[i]=temp[i]-'0';
printf("Please input target status:\n");
scanf("%s",&temp);
int j=0;
for ( j=0; j<9 && temp[j]-'0'>=0 && temp[j]-'0'<=8; j++)
target[j]=temp[j]-'0';
system("cls");
if ( i==9&&j==9)
break;
}
}
/* ----- end of function init ----- */
void open_insert (numNode *head,numNode *item)
{
numNode *p,*q;
p=head->next;
q=head;
while ( p!=NULL && item->fvalue > p->fvalue )
{
q=p;
p=p->next;
}
q->next=item;
item->pre=q;
item->next=p;
if(p!=NULL)
p->pre=item;
/* ----- end of function open_insert ----- */
}
numNode * open_getfirst (numNode *head)
{
numNode *p;
if ( head->next == NULL )
return NULL;
p=head->next;
head->next=p->next;
if ( p->next != NULL )
p->next->pre=head;
p->pre=NULL;
p->next=NULL;
return p;
}
/* ----- end of function open_getfirst ----- */
void close_append (numNode *head,numNode *item)
{
item->next=head->next;
item->pre=head;
head->next=item;
if ( item->next!=NULL )
item->next->pre=item;
/* ----- end of function close_append ----- */
}
int expand (numNode *p1)
{
numNode * p2;
int op=1;
for ( op=1; op<=4; op++)
{
p2=copy_numNode(p1);
operate(p2->num,op);
if(isNewNode(open,close,p2->num)=='N')
{
p2->parent=p1;
p2->deepth=p1->deepth+1;
p2->diffnum=diff(p2->num);
p2->fvalue=p2->deepth+p2->diffnum;
if(p2->diffnum==0)
{
total_step=print_result(p2);
printf("Total step: %d\n",total_step);
free_list(open);
free_list(close);
return 1;
}
else
{
numNode_num++;
open_insert(open,p2);
}
}
else
free(p2);
}
return 0;
}
/* ----- end of function expand ----- */
int operate(int m[], int op)
{
int blank;
blank=0;
while (m[blank]!=0 && blank<9 )
++blank;
if (blank==9)
return 1;
switch (op) {
case 1: /* up */
if (blank>2)
swap(m+blank,m+blank-3);
break;
case 2: /* down */
if (blank<6)
swap(m+blank,m+blank+3);
break;
case 3: /* left */
if (blank!=0 && blank!=3 && blank!=6)
swap(m+blank,m+blank-1);
break;
case 4: /* right */
if (blank!=2 && blank!=5 && blank!=8)
swap(m+blank,m+blank+1);
break;
default : return 1;
}
return 0;
}
void swap(int *a, int *b)
{
int c;
c=*a;
}
*a=*b;
*b=c;
numNode * copy_numNode (numNode *origin)
{
numNode *p;
p=create_numNode();
p->deepth=origin->deepth;
p->diffnum=origin->diffnum;
p->fvalue=origin->fvalue;
int i;
for ( i=0; i<9; i++)
(p->num)[i]=(origin->num)[i];
return p;
}
/* ----- end of function copy_numNode ----- */
int diff (int num[9])
{
int i,diffnum=0;
for(i=0;i<9;i++)
if(num[i]!=target[i])
diffnum++;
return diffnum;
}
/* ----- end of function diff ----- */
char isNewNode (numNode *open,numNode *close,int num[9])
{
numNode *p;
int i=0;
p=open->next;
while ( p!=NULL )
{
for ( i=0; i<9; i++)
{
if(p->num[i]!=num[i])
break;
}
if(i==9)
return 'O'; //Open
p=p->next;
}
p=close->next;
while ( p!=NULL )
{
for ( i=0; i<9; i++)
{
if(p->num[i]!=num[i])
break;
}
if(i==9)
return 'C'; //Close
p=p->next;
}
return 'N';
}
/* ----- end of function isNewNode ----- */
void free_list (numNode *head)
{
numNode *p,*q;
p=head->next;
while ( p!=NULL )
{
q=p->next;
free(p);
p=q;
}
free(head);
}
/* ----- end of function free_list ----- */
void print_num (int num[9])
{
int i;
for ( i=0; i<9; i++)
{
printf("%d\t",num[i]);
if((i%3)==2)
printf("\n");
}
}
/* ----- end of function print_num ----- */
int print_result ( numNode *item)
{
numNode *p;
int step;
p=item;
if(p!=NULL)
{
step=print_result(p->parent);
printf("\nStep %d:\n",step+1);
print_num(p->num);
return step+1;
}
else
return -1;
/* ----- end of function print_result ----- */
}
相关推荐
2023年江西萍乡中考道德与法治真题及答案.doc
2012年重庆南川中考生物真题及答案.doc
2013年江西师范大学地理学综合及文艺理论基础考研真题.doc
2020年四川甘孜小升初语文真题及答案I卷.doc
2020年注册岩土工程师专业基础考试真题及答案.doc
2023-2024学年福建省厦门市九年级上学期数学月考试题及答案.doc
2021-2022学年辽宁省沈阳市大东区九年级上学期语文期末试题及答案.doc
2022-2023学年北京东城区初三第一学期物理期末试卷及答案.doc
2018上半年江西教师资格初中地理学科知识与教学能力真题及答案.doc
2012年河北国家公务员申论考试真题及答案-省级.doc
2020-2021学年江苏省扬州市江都区邵樊片九年级上学期数学第一次质量检测试题及答案.doc
2022下半年黑龙江教师资格证中学综合素质真题及答案.doc
