#include <stdlib.h>
#include <malloc.h>
struct node
{
int sign;//標識,0什麽都不在,1在open中,2在closed中
int flag;//標誌位 0/1,0可以走,1不可以走
int f,g,h;//判斷函數
int x,y;//坐標
int old;//是否old節點,0非,1是
};
struct link
{
node fnode;
link *next;
link *pri;
};
link *open,*closed,*bestnode,*successor,*p,*q,*r,*s;
int maze_flag[7][7]={ {0,1,0,0,0,0,0},
{0,1,0,1,0,1,0},
{0,1,0,0,0,1,0},
{0,1,0,1,0,1,0},
{0,0,0,1,0,0,0},
{1,1,0,1,0,1,0},
{0,0,0,0,0,1,0}};//表示迷宮的數組,0可以走,1不可以走
node maze[7][7];
int judge(node n)//判斷函數,判斷n節點是否可以走
{
if(n.flag==1)
return(1);
else
return(0);
}
void in_open(node n)//將n節點放入open表
{
p=open;
while(p->next!=open)
{
if(n.f>=p->fnode.f)
{
p->next->pri=(link *)malloc(sizeof(link));
p->next->pri->pri=p;
p=p->next;
p->pri->next=p;
p->pri->pri->next=p->pri;
p=p->pri;
p->fnode.flag=n.flag;
p->fnode.f=n.f;
p->fnode.g=n.g;
p->fnode.h=n.h;
p->fnode.x=n.x;
p->fnode.y=n.y;
p->fnode.old=n.old;
p->fnode.sign=n.sign=1;
}
else
p=p->next;
}
open->pri=(link *)malloc(sizeof(link));
open->pri->pri=p;
open->pri->next=open;
p->next=open->pri;
p=p->next;
p->fnode.flag=n.flag;
p->fnode.f=n.f;
p->fnode.g=n.g;
p->fnode.h=n.h;
p->fnode.x=n.x;
p->fnode.y=n.y;
p->fnode.old=n.old;
p->fnode.sign=n.sign=1;
}
void out_open(node n)//將n節點從open表中移出
{
p=open;
while(p->next!=open)
{
if(n.f=p->fnode.f)
{
link *p1;
p1=p->next;
p->next=p->next->next;
p->next->pri=p;
free(p1);
n.sign=0;
}
else
p=p->next;
}
}
void in_closed(node n)//將n節點放入closed表
{
while(q->next!=closed)
{
if(n.f>=q->fnode.f)
{
q->next->pri=(link *)malloc(sizeof(link));
q->next->pri->pri=q;
q=q->next;
q->pri->next=p;
q->pri->pri->next=q->pri;
q=q->pri;
q->fnode.flag=n.flag;
q->fnode.f=n.f;
q->fnode.g=n.g;
q->fnode.h=n.h;
q->fnode.x=n.x;
q->fnode.y=n.y;
q->fnode.old=n.old;
q->fnode.sign=n.sign=2;
}
else
q=q->next;
}
closed->pri=(link *)malloc(sizeof(link));
closed->pri->pri=q;
closed->pri->next=closed;
q->next=closed->pri;
q=q->next;
q->fnode.flag=n.flag;
q->fnode.f=n.f;
q->fnode.g=n.g;
q->fnode.h=n.h;
q->fnode.x=n.x;
q->fnode.y=n.y;
q->fnode.old=n.old;
q->fnode.sign=n.sign=2;
}
void out_closed(node n)//將n節點從closed表中移出
{
q=closed;
while(q->next!=closed)
{
if(n.f=q->fnode.f)
{
link *q1;
q1=q->next;
q->next=q->next->next;
q->next->pri=q;
free(q1);
n.sign=0;
}
else
q=q->next;
}
}
void in_bestnode(node n)//將n節點設為bestnode節點
{
while(r->next!=bestnode)
{
if(n.f>=r->fnode.f)
{
r->next->pri=(link *)malloc(sizeof(link));
r->next->pri->pri=r;
r=r->next;
r->pri->next=r;
r->pri->pri->next=r->pri;
r=r->pri;
r->fnode.flag=n.flag;
r->fnode.f=n.f;
r->fnode.g=n.g;
r->fnode.h=n.h;
r->fnode.x=n.x;
r->fnode.y=n.y;
r->fnode.old=n.old;
}
else
r=r->next;
}
bestnode->pri=(link *)malloc(sizeof(link));
bestnode->pri->pri=r;
bestnode->pri->next=bestnode;
r->next=bestnode->pri;
r=r->next;
r->fnode.flag=n.flag;
r->fnode.f=n.f;
r->fnode.g=n.g;
r->fnode.h=n.h;
r->fnode.x=n.x;
r->fnode.y=n.y;
r->fnode.old=n.old;
}
void out_bestnode(node n)//將n節點的bestnode去掉
{
r=bestnode;
while(r->next!=bestnode)
{
if(n.f=p->fnode.f)
{
link *r1;
r1=r->next;
r->next=r->next->next;
r->next->pri=r;
free(r1);
}
else
r=r->next;
}
}
void in_successor(node n)//將n節點設置為successor節點
{
s=successor;
while(s->next!=successor)
{
if(n.f>=s->fnode.f)
{
s->next->pri=(link *)malloc(sizeof(link));
s->next->pri->pri=s;
s=p->next;
s->pri->next=s;
s->pri->pri->next=s->pri;
s=s->pri;
s->fnode.flag=n.flag;
s->fnode.f=n.f;
s->fnode.g=n.g;
s->fnode.h=n.h;
s->fnode.x=n.x;
s->fnode.y=n.y;
s->fnode.old=n.old;
}
else
s=s->next;
}
successor->pri=(link *)malloc(sizeof(link));
successor->pri->pri=s;
successor->pri->next=successor;
s->next=successor->pri;
s=s->next;
s->fnode.flag=n.flag;
s->fnode.f=n.f;
s->fnode.g=n.g;
s->fnode.h=n.h;
s->fnode.x=n.x;
s->fnode.y=n.y;
s->fnode.old=n.old;
}
void out_successor(node n)//將n節點的successor去掉
{
s=successor;
while(s->next!=successor)
{
if(n.f=p->fnode.f)
{
link *s1;
s1=s->next;
s->next=s->next->next;
s->next->pri=s;
free(s1);
}
else
s=s->next;
}
}
void print(link *n)//輸出link類型的表n
{
link *forprint;
forprint=n;
printf("the key is ");
while(forprint->next!=n)
printf("(%d,%d)\n",forprint->fnode.x,forprint->fnode.y);
}
int main()
{
//初始化部分
//這部分的功能是將二維的整形數組賦值給node型的二維數組
int i=0,j=0;
for(i=0;i<7;i++)
for(j=0;j<7;j++)
{
maze[i][j].x=i;
maze[i][j].y=j;
maze[i][j].flag=maze_flag[i][j];
if(maze[i][j].flag==0)
{
maze[i][j].h=6-i+6-j;
maze[i][j].sign=maze[i][j].f=maze[i][j].g=maze[i][j].old=0;
}
else
maze[i][j].h=-1;
}
for(i=0;i<7;i++)//輸出迷宮示意圖
{
for(j=0;j<7;j++)
{
printf("%2d",maze_flag[i][j]);
}
printf("\n");
}
//這部分的功能是將open,closed,bestnode表初始化,都置為空表
p=open=(link *)malloc(sizeof(link));
open->next=open;
open->pri=open;
q=closed=(link *)malloc(sizeof(link));
closed->next=closed;
closed->pri=closed;
r=bestnode=(link *)malloc(sizeof(link));
bestnode->next=bestnode;
bestnode->pri=bestnode;
//將第壹個元素即(0,0)節點放入open表,開始算法
in_open(maze[0][0]);
maze[0][0].f=maze[0][0].h;
link *s2;
s2=successor;
if(open->next!=open)//open表為空時則失敗退出
{
while(1)
{
in_bestnode(open->fnode);//將open表的第壹個元素放入bestnode中
in_closed(maze[open->fnode.x][open->fnode.y]);//將open表的第壹個元素放入closed中
maze[open->fnode.x][open->fnode.y].g++;//將open表的第壹個元素的g值加壹,表示已經走了壹步
out_open(maze[open->fnode.x][open->fnode.y]);//將open表的第壹個元素刪除
if(bestnode->fnode.x==6&&bestnode->fnode.y==6)//若bestnode是目標節點,則成功退出
{
printf("succes!!\nthen print the key:\n");
print(closed);
break;
}
else//若bestnode不是目標節點,則擴展其臨近可以走的節點為successor
{
if(i==0||j==0||i==6||j==6)
{
if(i==0&&j==0)//若為(0,0),則判斷右邊和下邊的元素
{
if(judge(maze[i][j+1])==0)
in_successor(maze[i][j+1]);
if(judge(maze[i+1][j])==0)
in_successor(maze[i+1][j]);
}
else if(i==0&&j==6)//若為(0,6),則判斷左邊和下邊的元素
{
if(judge(maze[i-1][j])==0)
in_successor(maze[i-1][j]);
if(judge(maze[i+1][j])==0)
in_successor(maze[i+1][j]);
}
else if(i==6&&j==0)//若為(6,0),則判斷左邊和上邊的元素
{
if(judge(maze[i-1][j])==0)
in_successor(maze[i-1][j]);
if(judge(maze[i][j-1])==0)
in_successor(maze[i][j-1]);
}
else if(i==6&&j==6)//若為(6,6),則判斷左邊和上邊的元素
{
if(judge(maze[i-1][j])==0)
in_successor(maze[i-1][j]);
if(judge(maze[i][j-1])==0)
in_successor(maze[i][j-1]);
}
else if(i==0)//若為第壹行的元素(不在角上),則判斷左邊,下邊和右邊
{
if(judge(maze[i][j+1])==0)
in_successor(maze[i][j+1]);
if(judge(maze[i][j-1])==0)
in_successor(maze[i][j-1]);
if(judge(maze[i+1][j])==0)
in_successor(maze[i+1][j]);
}
else if(i==6)//若為第七行的元素(不在角上),則判斷左邊,上邊和右邊
{
if(judge(maze[i][j+1])==0)
in_successor(maze[i][j+1]);
if(judge(maze[i][j-1])==0)
in_successor(maze[i][j-1]);
if(judge(maze[i-1][j])==0)
in_successor(maze[i-1][j]);
}
else if(j==0)//若為第壹列的元素(不在角上),則判斷右邊,下邊和上邊
{
if(judge(maze[i+1][j])==0)
in_successor(maze[i+1][j]);
if(judge(maze[i-1][j])==0)
in_successor(maze[i-1][j]);
if(judge(maze[i][j+1])==0)
in_successor(maze[i][j+1]);
}
else if(j==6)//若為第七列的元素(不在角上),則判斷左邊,上邊和上邊
{
if(judge(maze[i+1][j])==0)
in_successor(maze[i+1][j]);
if(judge(maze[i-1][j])==0)
in_successor(maze[i-1][j]);
if(judge(maze[i][j-1])==0)
in_successor(maze[i][j-1]);
}
}
else//若為中將的元素,則判斷四個方向的節點
{
if(judge(maze[i][j-1])==0)
in_successor(maze[i][j-1]);
if(judge(maze[i][j+1])==0)
in_successor(maze[i][j+1]);
if(judge(maze[i-1][j])==0)
in_successor(maze[i-1][j]);
if(judge(maze[i+1][j])==0)
in_successor(maze[i+1][j]);
}
}
while(s2->next!=successor)//對所有的successor節點進行下列操作
{
maze[s2->fnode.x][s2->fnode.y].g=bestnode->fnode.g+bestnode->fnode.h;//計算g(suc)=g(bes)+h(bes,suc)
if(s2->fnode.sign==1)//若在open表中,則置為old,記下較小的g,並從open表中移出,放入closed表中
{
s2->fnode.old=1;
if(s2->fnode.g<maze[s2->fnode.x][s2->fnode.y].g)
{
maze[s2->fnode.x][s2->fnode.y].g=s2->fnode.g;
maze[s2->fnode.x][s2->fnode.y].f=maze[s2->fnode.x][s2->fnode.y].g+maze[s2->fnode.x][s2->fnode.y].h;
out_open(maze[s2->fnode.x][s2->fnode.y]);
in_closed(maze[s2->fnode.x][s2->fnode.y]);
maze[s2->fnode.x][s2->fnode.y].old=0;
}
else
continue;
}
else if(s2->fnode.sign==2)//若在closed表中,則置為old,記下較小的g,並將old從closed表中移出,將較小的g的節點放入closed表中
{
s2->fnode.old=1;
if(s2->fnode.g<maze[s2->fnode.x][s2->fnode.y].g)
{
maze[s2->fnode.x][s2->fnode.y].g=s2->fnode.g;
maze[s2->fnode.x][s2->fnode.y].f=maze[s2->fnode.x][s2->fnode.y].g+maze[s2->fnode.x][s2->fnode.y].h;
out_closed(maze[s2->fnode.x][s2->fnode.y]);
in_closed(maze[s2->fnode.x][s2->fnode.y]);
maze[s2->fnode.x][s2->fnode.y].old=0;
}
else
continue;
}
else//若即不再open表中也不在closed表中,則將此節點放入open表中,並計算此節點的f值
{
in_open(maze[s2->fnode.x][s2->fnode.y]);
maze[s2->fnode.x][s2->fnode.y].f=maze[s2->fnode.x][s2->fnode.y].g+maze[s2->fnode.x][s2->fnode.y].h;
}
s2=s2->next;
}
s2=successor;
}
}
else
printf("error!!This maze does not have the answer!");
return(0);
}