最近對樹型數據結構特別感興趣！
以下是我的Splay樹代碼：
#include<stdio.h>
#define maxn 10007
typedef struct
{
long data,fa,ls,rs;
}Node;
Node splay[maxn];
long m,root;
long n;
void Zig(long node)
{
long t=splay[node].fa;
splay[t].rs=splay[node].ls;
if(splay[node].ls)
splay[splay[node].ls].fa=t;
splay[node].fa=splay[t].fa;
splay[node].ls=t;
if(splay[t].fa)
{
if(t==splay[splay[t].fa].ls) splay[splay[t].fa].ls=node;
else splay[splay[t].fa].rs=node;
}
splay[t].fa=node;
}
void Zag(long node)
{
long t=splay[node].fa;
splay[t].ls=splay[node].rs;
if(splay[node].rs)
splay[splay[node].rs].fa=t;
splay[node].fa=splay[t].fa;
splay[node].rs=t;
if(splay[t].fa)
{
if(t==splay[splay[t].fa].ls) splay[splay[t].fa].ls=node;
else splay[splay[t].fa].rs=node;
}
splay[t].fa=node;
}
void Splay(long node)
{
long t;
while(splay[node].fa)
{
t=splay[node].fa;
if(splay[t].fa==0)
{
if(node==splay[t].ls) Zag(node);
else Zig(node);
break;
}
if(t==splay[splay[t].fa].ls)
{
if(node==splay[t].ls)
{Zag(t);Zag(node);}
else {Zig(node);Zag(node);}
}
else
{
if(node==splay[t].ls)
{Zag(node);Zig(node);}
else {Zig(t);Zig(node);}
}
}
root=node;
}
void Insert(long x)
{
long p,q;
m++;
splay[m].data=x;
splay[m].fa=splay[m].ls=splay[m].rs=0;
if(root==0)
{
root=m;return;
}
for(p=root;p; )
{
q=p;
if(x<=splay[p].data) p=splay[p].ls;
else p=splay[p].rs;
}
splay[m].fa=q;
if(x<=splay[q].data) splay[q].ls=m;
else splay[q].rs=m;
Splay(m);
}
int main()
{
freopen("data.in","r",stdin);
freopen("data.out","w",stdout);
scanf("%ld",&n);
m=root=0;
for(long i=1;i<=n;i++)
splay[i].data=splay[i].fa=splay[i].ls=splay[i].rs=0;
for(long i=1;i<=n;i++)
{
long t;
scanf("%ld",&t);
Insert(t);
}
Splay(1);
for(long i=1;i<=n;i++)
printf("No.%ld data.%ld fa.%ld ls.%ld rs.%ld\n",i,splay[i].data,splay[i].fa,splay[i].ls,splay[i].rs);
return 0;
}
posted on 2010-03-12 22:28
lee1r 閱讀(996)
評論(0) 編輯 收藏 引用 所屬分類:
算法與數據結構