数据结构运算的具体实现与定义是相关的，这样说升槐清吧，定义吵前只是写出了一个函数名，而具体实现就是来对这个函数进行具体 *** 作，写出了所有的 *** 作步骤，写出了定义的函数的具体功能和实明者现方法。。
#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 O1 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=0i<10i++ )
{ for(int j=0j<10j++ )
{
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=1i<=4i++) /*四个方向逐个行走，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)
}
我只有十五数码的.你春竖埋如果再给点分,我就给你个带堆和平衡树的.
program lk_A_3_1{十五数纤逗码}
const
dre:array[1..4,1..2] of shortint=((-1,0),(0,-1),(0,1),(1,0))
type
coo=array[1..2] of shortint
co=array[0..15] of coo
node=record
data:co{表示每一个数码的坐标}
de:shortint{移动方向1,2,3,4分别表示上，左，右，下}
next,from:pointer
depth:longint
f:real{估价函数值，包括深度}
end
pointer=^node
var
ans:co
ls:array[1..4,1..4] of shortint{棋盘}
h,t,p,q,v:pointer
i,j,k,n:longint
c:shortint
l:coo
procedure print
begin
n:=1
while q<>nil do
begin
fillchar(ls,sizeof(ls),0)
for k:=0 to 15 do
ls[q^.data[k,1],q^.data[k,2]]:=k
writeln('Step ',n)
for i:=1 to 4 do
begin
for j:=1 to 4 do
write(ls[i,j]:4)
writeln
end
q:=q^.from
inc(n)
end
close(input)
close(output)
halt
end
function compare(a,b:co):boolean
var
o,u:longint
begin
compare:=true
for o:=0 to 15 do
for u:=1 to 2 do
if a[o,u]<>b[o,u] then exit(false)
end
procedure init
begin
assign(input,'input.txt')
assign(output,'扒蚂output.txt')
reset(input)
rewrite(output)
for i:=1 to 4 do
for j:=1 to 4 do
begin
read(c)
ans[c,1]:=i
ans[c,2]:=j
end
new(h)
for i:=1 to 4 do
for j:=1 to 4 do
begin
read(c)
h^.data[c,1]:=i
h^.data[c,2]:=j
end
h^.next:=nil
h^.from:=nil
h^.de:=0
h^.f:=0
h^.depth:=0
if compare(h^.data,ans) then
begin
q:=h
end
end
function check:boolean
begin
check:=true
if p^.data[0,1]+dre[k,1] in [0,5] then exit(false)
if p^.data[0,2]+dre[k,2] in [0,5] then exit(false)
t:=p^.from
if t<>nil then
if k+t^.de=5 then exit(false)
end
procedure make
begin
n:=0
for i:=1 to 15 do
n:=n+abs(q^.data[i,1]-ans[i,1])+abs(q^.data[i,2]-ans[i,2])
q^.f:=q^.depth+n{/q^.depth}
end
procedure ins
begin
t:=p
while t^.next<>nil do
begin
v:=t^.next
if compare(q^.data,v^.data)=false then t:=t^.next
else
begin
dispose(q)
exit
end
end
t:=p
while t^.next<>nil do
begin
v:=t^.next
if q^.f>v^.f then t:=t^.next
else break
end
q^.next:=t^.next
t^.next:=q
end
procedure bfs
begin
p:=h
while p<>nil do
begin
for k:=1 to 4 do
if check then
begin
new(q)
q^.data:=p^.data
q^.from:=p
q^.depth:=p^.depth+1
for i:=1 to 15 do
if (q^.data[i,1]=p^.data[0,1]+dre[k,1])and(q^.data[i,2]=p^.data[0,2]+dre[k,2]) then break
l:=q^.data[i]
q^.data[i]:=q^.data[0]
q^.data[0]:=l
if compare(q^.data,ans) then print
make
ins
end
p:=p^.next
end
end
begin
init
bfs
end.
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）