很久就知道鏈表可以用數(shù)組來(lái)模擬（其實(shí)很多數(shù)據(jù)結(jié)構(gòu)數(shù)組都可以實(shí)現(xiàn)），一開(kāi)始感覺(jué)用數(shù)組模擬還不簡(jiǎn)單嗎？于是很長(zhǎng)的一段時(shí)間內(nèi)都沒(méi)有去寫(xiě)這個(gè)程序。今天突然想到了，想去實(shí)現(xiàn)它，結(jié)果竟然思考了大概20min才想起如何構(gòu)造數(shù)據(jù)結(jié)構(gòu)，看來(lái)程序還得多動(dòng)手實(shí)踐。
以下是我的代碼：
insert(a,b)：在鏈表中值為b的元素前面插入a，如果找不到b，將a插入鏈表末端；
print()：遍歷整個(gè)鏈表，并輸出。
#include<stdio.h>
#include<string.h>
#define maxn 1007
long n,a[maxn],next[maxn];
void insert(long x,long y)
{
long p=0;
n++;a[n]=x;
while(next[p]&&a[next[p]]!=y)
p=next[p];
next[n]=next[p];
next[p]=n;
}
void print()
{
long p=next[0];
bool first=true;
while(p)
{
if(first) first=false;
else printf(" ");
printf("%ld",a[p]);
p=next[p];
}
}
int main()
{
freopen("data.in","r",stdin);
freopen("data.out","w",stdout);
long m,a,b;
char cmd[maxn];
n=0;
memset(next,0,sizeof(next));
scanf("%ld",&m);
while(m--)
{
scanf("%s",cmd);
if(cmd[0]=='I')
{
scanf("%ld%ld",&a,&b);
insert(a,b);
}
else
{
print();putchar('\n');
}
}
return 0;
}
posted on 2010-03-16 22:39
lee1r 閱讀(1877)
評(píng)論(0) 編輯 收藏 引用 所屬分類(lèi):
算法與數(shù)據(jù)結(jié)構(gòu)