① 求A* 演算法C語言源程序
#include <string.h>
#include <stdio.h>
#include <malloc.h>
#include <time.h>
#define NULL 0
const int nmax = 200;
const int nend = 99; /*終點坐標的代表點*/
static char achar[10][10];
static int npayo = 0; /*0 表示空 1為非空*/
static int npayc = 0; /*0 表示空 1為非空*/
static int npay_x = 0; /*起點*/
static int npay_y = 0;
static int nend_x = 9; /*終點*/
static int nend_y = 9;
static int nnewpay_x;
static int nnewpay_y;
static int ndian = 101;
static int nh;
static long i = 10000000L;
struct Spaydian
{
int ng;
int nf; /*路徑評分*/
int nmy_x; /*自己位置*/
int nmy_y;
int nfatherx; /*父節點*/
int nfathery;
int nflag; /* 0 wei O; 1 wei @ */
};
static struct Spaydian spaydian[200];
/* open close list 表 */
typedef struct spaylist
{
int n_f;
int n_x;
int n_y;
int nfather_x;
int nfather_y;
struct spaylist *next;
};
static struct spaylist *open_list, *close_list;
static void smline();
static int sjudge(int nx,int ny,int i); /*判斷在第nx列ny行向第i個方向走是否可以,可以返回1否則返回0。
i=1表示向右，2表示向下，3表示向左，4表示向上*/
static void spath();
static void spayshow(int nxx,int nyy);
static int sifopen( int nx,int ny); /*判斷點是否在 open 表上*/
static int sifclose(int nx,int ny); /*判斷點是否在 close 表上*/
static int snewx(int nx,int i);
static int snewy(int ny,int i);
static spaylist *creat(); /*建立鏈表*/
static spaylist *del(spaylist *head,int num_x,int num_y); /*刪除鏈表的結點*/
static spaylist *snewdianx(spaylist *head);/*新的點*/
static spaylist *snewdiany(spaylist *head);
static spaylist *insert(spaylist *head,int ndian); /* 點插入鏈表 */
static spaylist *srebirth(spaylist *head,int ndian); /*更新表*/
int main()
{
FILE *fp ;
char ach ;
int ni = 0 ; /*統計個數*/
int nii = 0; /*achar[nii][njj]*/
int njj = 0;
if ((fp=fopen("route.txt","rt")) == NULL) /* 判斷打開文件是否為空 */
{
printf("文件為空！~\n");
return 0;
/* exit(1);*/
}
ach = fgetc(fp);
while(ach != EOF)
{
if(ach == 'O' || ach == '@') /*當值為@或O時候*/
{
spaydian[ni].ng = 0;
spaydian[ni].nf = nmax;
spaydian[ni].nmy_x = njj;
spaydian[ni].nmy_y = nii;
spaydian[ni].nfathery = -1;
spaydian[ni].nfatherx = -1;
if(ach == '@')
{
spaydian[ni].nflag = 1;
}
else if(ach == 'O')
{
spaydian[ni].nflag = 0;
}
ni++;
achar[nii][njj] = ach;
njj++;
if(njj == 10)
{
nii++;
njj = 0;
}
} /*end if*/
ach = fgetc(fp);
}/*end while*/
smline(); /* a*演算法 */
fp=fopen("answer.txt","w");
for(int i=0;i<10;i++ )
{ for(int j=0;j<10;j++ )
{
printf("%c",achar[i][j]);
if(j==9)
printf("\n");
fprintf(fp,"%c",achar[i][j]);
if (j==9)
fprintf(fp,"\n");
}
}
fclose(fp);
return 0;
}
/* a* 演算法 */
static void smline()
{ close_list = open_list = NULL;
open_list = creat();
while(open_list != NULL) /* 當open 表不為空時 */
{
open_list = del(open_list,npay_x,npay_y); /*刪除open 鏈表的結點*/
if(npay_x == 9 && npay_y == 9)
{
achar[9][9] = '=';
spath(); /*尋找並畫出路徑*/
break;
}
for (int i=1; i<=4; i++) /*四個方向逐個行走，i=1向右 2向下 3向左 4向上*/
{
if (sjudge(npay_x,npay_y,i))
{
nnewpay_x = snewx(npay_x,i);
nnewpay_y = snewy(npay_y,i);
if(open_list != NULL)
npayo = sifopen(nnewpay_x,nnewpay_y) ; /*判斷點是否在 open 表中*/
else
npayo = 0;
if(close_list != NULL)
npayc = sifclose(nnewpay_x,nnewpay_y) ; /*判斷點是否在 close 表中*/
else
npayc = 0;
ndian = 10*nnewpay_x+nnewpay_y ;
if (npayo == 0 && npayc == 0 ) /*點不在open表也不在close表中*/
{
spaydian[ndian].ng = spaydian[10*npay_x+npay_y].ng + 1; /*更新點的基本信息*/
nh = (nend - ndian)/10 + (nend - ndian)%10 ;
spaydian[ndian].nf = spaydian[ndian].ng+nh;
spaydian[ndian].nfathery = npay_y;
spaydian[ndian].nfatherx = npay_x;
spaydian[ndian].nmy_y = nnewpay_y;
spaydian[ndian].nmy_x = nnewpay_x;
open_list = insert(open_list,ndian);/*點插入open 表中*/
}
else if (npayo == 1) /*點在open表中*/
{
spaydian[ndian].ng = spaydian[10*npay_x+npay_y].ng + 1;
nh = (nend - ndian)/10 + (nend - ndian)%10 ;
if(spaydian[ndian].nf > (spaydian[ndian].ng+nh) && spaydian[ndian].nf != nmax)
{
spaydian[ndian].nf = spaydian[ndian].ng+nh;
open_list = srebirth(open_list,ndian); /*點插入open 表中*/
}
}
else if(npayc == 1) /*新生成的點在close表中*/
{
spaydian[ndian].ng = spaydian[10*npay_x+npay_y].ng + 1;
nh = (nend - ndian)/10 + (nend - ndian)%10 ;
if(spaydian[ndian].nf > (spaydian[ndian].ng+nh) && spaydian[ndian].nf != nmax)
{
spaydian[ndian].nf = spaydian[ndian].ng+nh;
close_list = srebirth(close_list,ndian);
close_list = del(close_list,nnewpay_x,nnewpay_y); /*刪除close鏈表的結點*/
open_list = insert(open_list,ndian);/*點插入open 表中*/
}
}/*end else if*/
}/*end if*/
}/*end for*/
close_list = insert(close_list,(10*npay_x+npay_y));/*點插入close 表中*/
if(open_list != NULL)
{
npay_x = open_list->n_x;
npay_y = open_list->n_y;
}
}/*end while*/
if(open_list == NULL)
{printf("無路可走 \n");}
}
/*建立鏈表*/
spaylist *creat(void)
{
spaylist *head;
spaylist *p1;
int n=0;
p1=(spaylist*)malloc(sizeof(spaylist));
p1->n_f = 18;
p1->n_x = 0;
p1->n_y = 0;
p1->nfather_x = -1;
p1->nfather_x = -1;
p1->next = NULL;
head = NULL;
head=p1;
return(head);
}
/*刪除結點*/
spaylist *del(spaylist *head,int num_x,int num_y)
{
spaylist *p1, *p2;
if(head == NULL)
{
printf("\nlist null!\n");
return (head);
}
p1 = head;
while((num_y != p1->n_y ||num_x != p1->n_x )&& p1->next != NULL)
{
p2=p1;
p1=p1->next;
}
if(num_x == p1->n_x && num_y == p1->n_y )
{
if(p1==head)
head=p1->next;
else
p2->next=p1->next;
}
return (head);
}
/*輸出*/
static void spath()
{
int nxx;
int nyy;
nxx = spaydian[nend].nfatherx;
nyy = spaydian[nend].nfathery;
spayshow(nxx,nyy) ;
}
/*遞歸*/
void spayshow(int nxx,int nyy)
{ achar[nxx][nyy] = '=';
if( nxx != 0 || nyy != 0 )
{
int nxxyy = 10*nxx+nyy;
nxx = spaydian[nxxyy].nfatherx;
nyy = spaydian[nxxyy].nfathery;
spayshow(nxx,nyy);
}
}
/* 判斷周圍四個點是否可行 */
static int sjudge(int nx,int ny,int i)
{
if (i==1) /*判斷向右可否行走*/
{
if (achar[nx][ny+1]=='O' && ny<9)
{
return 1;
}
else
return 0;
}
else if (i==2) /*判斷向下可否行走*/
{
if (achar[nx+1][ny]=='O' && nx<9)
{
return 1;
}
else
return 0;
}
else if (i==3)/*判斷向左可否行走 */
{
if (ny > 0&&achar[nx][ny-1]=='O')
{
return 1;
}
else
return 0;
}
else if (i==4)/*判斷向上可否行走 */
{
if (nx > 0&&achar[nx-1][ny]=='O')
{
return 1;
}
else
return 0;
}
else
return 0;
}
/* 求新的x點 */
static int snewx(int nx,int i)
{
if(i == 1)
nx = nx;
else if(i == 2)
nx = nx+1;
else if(i == 3)
nx = nx;
else if(i == 4)
nx = nx-1;
return nx;
}
/* 求新的y點 */
static int snewy(int ny, int i)
{
if(i == 1)
ny = ny+1;
else if(i == 2)
ny = ny;
else if(i == 3)
ny = ny-1;
else if(i == 4)
ny = ny;
return ny;
}
/*判定點是否在open表中*/
int sifopen(int nx,int ny)
{
spaylist *p1, *p2;
p1 = open_list;
while((ny != p1->n_y || nx != p1->n_x )&& p1->next != NULL)
{
p2 = p1;
p1 = p1->next;
}
if(nx == p1->n_x && ny == p1->n_y)
return 1;
else
return 0;
}
/*判定點是否在close表中*/
int sifclose(int nx,int ny)
{
spaylist *p1, *p2;
p1 = close_list;
while((ny != p1->n_y ||nx != p1->n_x )&& p1->next != NULL)
{
p2=p1;
p1=p1->next;
}
if(nx == p1->n_x && ny == p1->n_y)
return 1;
else
return 0;
}
/*插入結點*/
spaylist * insert(spaylist *head,int ndian)
{
spaylist *p0,*p1,*p2;
p1=head;
p0=(spaylist*)malloc(sizeof(spaylist));
p0->n_f = spaydian[ndian].nf;
p0->n_x = spaydian[ndian].nmy_x;
p0->n_y = spaydian[ndian].nmy_y;
p0->nfather_x = spaydian[ndian].nfatherx;
p0->nfather_x = spaydian[ndian].nfathery;
p0->next = NULL;
if(head==NULL)
{
head=p0;
p0->next=NULL;
}
else
{
while((p0->n_f > p1->n_f)&&(p1->next!=NULL))
{
p2=p1;
p1=p1->next;
}
if(p0->n_f <= p1->n_f)
{
if(head==p1)
head=p0;
else
p2->next=p0;
p0->next=p1;
}
else
{
p1->next=p0;
p0->next=NULL;
}
}
return (head);
}
/* 更新鏈表 */
spaylist * srebirth(spaylist *head,int ndian)
{
spaylist *p1, *p2;
p1=head;
while(spaydian[ndian].nmy_x!=p1->n_x&&spaydian[ndian].nmy_x!=p1->n_x&&p1->next!=NULL)
{
p2=p1;
p1=p1->next;
}
if(spaydian[ndian].nmy_x==p1->n_x&&spaydian[ndian].nmy_x==p1->n_x)
{
p1->n_f = spaydian[ndian].nf;
}
return (head);
}