静态链表

定义用数组描述的链表，即称为静态链表。

　　这种存储结构，仍需要预先分配一个较大的空间，但在作为线性表的插入和删除操作时不需移动元素，仅需修改指针，故仍具有链式存储结构的主要优点。

　　假如有如上的静态链表S中存储这线性表（a，b，c，d，k,f，g，h，i），Maxsize=11，如图所示，要在第四个元素后插入元素e，方法是：先在当前表尾加入一个元素e，即：S[9].data = e;然后修改第四个元素的游标域，将e插入到链表中，即：S[9].cursor = S[4].cursor; S[4].cursor = 9;，接着，若要删除第8个元素h，则先顺着游标链通过计数找到第7个元素存储位置6，删除的具体做法是令S[6].cursor = S[7].cursor。

　　#include<stdio.h>

　　#include"definition.h"

　　void Init(component *L)//初始化静态链表

　　{ unsigned short i;

　　for(i=0; i<MAXSIZE-1; i++)

　　L.cur=i+1;

　　L[MAXSIZE-1].cur=0;

　　}

　　component* Insert(component *L)//插入数据到链表

　　{ component *T, *temp1, *temp2;

　　unsigned short i;

　　ElemType ch;

　　if( i=Malloc(L) ){

　　T=temp1=&L;

　　T->cur=0;

　　} else

　　return 0;

　　while( (ch=getchar()) != '\n' ){

　　if( i=Malloc(L) ){

　　temp2=&L;

　　temp2->data=ch;

　　temp2->cur=0;

　　temp1->cur=i;

　　temp1=temp2;

　　} else

　　return 0;

　　}

　　return T;

　　}

　　short Malloc(component *L)//分配空间

　　{ unsigned short i;

　　i=L[0].cur;

　　if(L[0].cur){

　　L[0].cur=L.cur;

　　return i;//成功返回空间位置

　　}

　　return 0;//失败返回0

　　}

　　void Free(component *L, short i) //回收空间

　　{ L.cur=L[0].cur;

　　L[0].cur=i;

　　}

　　void Disp(component *T, component *L)//显示静态链表数据

　　{ while(T->cur){

　　T=&L[T->cur];

　　printf("%c", T->data);

　　} printf("\n");

　　}

　　void Purge(component *T, component *L) //删除重复数据

　　{ component *tmp, *temp;

　　for(T=&L[T->cur]; T->data; T=&L[T->cur]){//若T->data中没数据，则退出循环

　　for(temp=T, tmp=&L[T->cur]; tmp->data;){//若tmp->data中没数据，则退出循环

　　if(T->data==tmp->data){

　　temp->cur=tmp->cur;

　　Free(L, (short)(tmp-L));//回收空间

　　tmp=&L[temp->cur];

　　} else{

　　tmp=&L[tmp->cur];

　　temp=&L[temp->cur];

　　} }

　　} }

　　void Union(component *A, component *B, component *L)//(A-B)交(B-A)

　　{ component *T, *ta, *tb=B;

　　short flag;//用于判断是否进行了删除操作

　　B=&L;

　　while(B->data){//循环判断，直到B表中所有数据都和A表比较过后才结束

　　ta=T=A;

　　flag=1;//1代表没有进行删除

　　while(T->cur){//循环判断，直到A表中所有数据都和B->data比较过后才结束

　　T=&L[T->cur];

　　if(T->data==B->data){//如果相等，则删除

　　ta->cur=T->cur;

　　Free(L, (short)(T-L));

　　T=&L[ta->cur];

　　tb->cur=B->cur;

　　Free(L, (short)(B-L));

　　B=&L[tb->cur];

　　flag=0;//1代表进行了删除

　　break;

　　} else//不相等则把指针移动到一个数据

　　ta=&L[ta->cur];

　　} if(flag){//如果没有进行删除操作，则连接两个结点

　　T->cur=tb->cur;

　　tb->cur=B->cur;

　　B->cur=0;

　　B=&L[tb->cur];

　　} }

　　}

　　链表大家都知道吧，我就不废话了．．．所谓的静态链表就是在那些不能用指针的语言里用数组建立链表并用一个下标来维护．．．给个程序吧．．．

　　program static_link_list(input,output);

　　const maxl=10;

　　type elem=record

　　num,next:integer;

　　end;

　　tlist=array[0..maxl]of elem;

　　var list:tlist;

　　num,place,head,av:integer;

　　ch:char;

　　function get_node(var av:integer):integer;

　　begin

　　get_node:=av;

　　if av<>-1 then av:=list[av].next;

　　end;

　　procedure disp_node(var av:integer;k:integer);

　　begin

　　list[k].next:=av;

　　av:=k;

　　end;

　　procedure init(var av:integer);

　　var i:integer;

　　begin

　　for i:=0 to maxl-1 do

　　list.next:=i+1;

　　list[maxl].next:=-1;

　　av:=0;

　　end;

　　procedure print(head:integer);

　　begin

　　head:=list[head].next;

　　while head<>-1 do

　　begin

　　write(list[head].num,' ');

　　head:=list[head].next;

　　end;

　　writeln;

　　end;

　　procedure insert(head,num,place:integer;var av:integer);

　　var j,x:integer;

　　begin

　　j:=0;

　　while (head<>-1)and(j<place-1) do

　　begin

　　inc(j);

　　head:=list[head].next;

　　end;

　　if (head=-1)or(j>place-1) then

　　begin

　　writeln('Input Error!');

　　exit;

　　end;

　　x:=get_node(av);

　　if x=-1 then

　　begin

　　writeln('List has been full!');

　　exit;

　　end;

　　list[x].num:=num;

　　list[x].next:=list[j].next;

　　list[j].next:=x;

　　end;

　　procedure del(var av:integer;head,place:integer);

　　var j,k:integer;

　　begin

　　j:=0;

　　while (list[head].next<>-1)and(j<place-1) do

　　begin

　　inc(j);

　　head:=list[head].next;

　　end;

　　if (list[head].next=-1)or(j>place-1) then

　　begin

　　writeln('Input Error!');

　　exit;

　　end;

　　k:=list[head].next;

　　list[head].next:=list[list[head].next].next;

　　disp_node(av,k);

　　end;

　　begin

　　init(av);

　　head:=get_node(av);

　　list[head].next:=-1;

　　readln(ch);

　　while ch<>'E' do

　　begin

　　case ch of

　　'I':begin

　　readln(num,place);

　　insert(head,num,place,av);

　　end;

　　'D':begin

　　readln(place);

　　del(av,head,place);

　　end;

　　'P':print(head);

　　else writeln('Input Error!');

　　end;

　　readln(ch);

　　end;

　　end.