2.8静态链表

由前面讨论可知，链表的形式多样，组织方式灵活，便于元素的插入和删除 操作，通常借助于高级语言中的指针数据类型来实现，但在实际应用中，有些语 言中并未提供“指针”类型，故采用数组模拟实现链表的方式—静态链表。

一.静态链表的基本特征

• 存储池：定义一个较大的结构数组作为备用结点空间
• 游标机制：每个结点应含有两个域：data 域和 next（或 cursor）域

●data 域用来存放结点的数据信息
●cursor 域为游标指示器，指示后继结点在结构数组中的相对位置（即数组下 标值）。数组的第 0个分量可以设计成表的头结点，头结点的 cursor 域指示了表 中第一个结点的位置，cursor 值为 0 表示静态单链表的结束。

• 结点结构：静态单链表可以借助结构体数组来描述：

#define  Maxsize   链表可能达到的最大长度 
typedef  struct 
{ElemType data;  int cursor; 
}Component, StaticList[Maxsize]; 

例：通过变量定义语句 StaticList S；定义的静态单链表 S 中存储着线性表 （ a，b，c，d，f，g，h，i），Maxsize=11，如图 2.18 所示。要在第 4 个元素 后插入元素 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。

缺点 ：上述例子中未考虑对已释放空间的回收，这样在经过多次插入和删除后， 会造成静态链表的“假满”。即表中有很多的空闲空间，但却无法再插入元素。 造成这种现象的原因是未对已删除的元素所占的空间进行回收

解决这个问题的方法：是将所有未被分配的结点空间以及因删除操作而回收的结 点空间用游标链成一个备用静态链表。当进行插入操作时，先从备用链表上取一 个分量来存放待插入的元素，然后将其插入到已用链表的相应位置。当进行删除 操作时，则将被删除的结点空间链接到备用链表上以备后用。这种方法是指在已 申请的大的存储空间中有一个已用的静态单链表，还有一个备用单链表。已用静 态单链表的头指针为 0，备用静态单链表的头指针需另设一个变量 av 来表示。

二.静态单链表的基本操作算法

1.初始化

【算法描述】：初始化为一个备用静态单链表。
【算法】：

void initial(StaticList space,int *av) 
{             int k; space[0].cursor=1;      /*设置已用静态单链表的头指针指向位置 0*/for(k=0;k<Maxsize-1;k++) space[k].cursor=k+1;    /*连链*/ space[Maxsize-1]. cursor=-1;    /*标记链尾*/ *av=1;  /*设置备用链表头指针初值*/ 
}/*initial    

2.分配结点
【算法描述】

/*从可用区申请新结点*/ 
int getnode(StaticList space,int *av) 
/*从备用链表摘下一个结点空间，分配给待插入静态链表中的元素*/ 
{int i;  i=av;  av=space[av].cur; /*av 指针为头指针的下一个*/  return i; /*返回可用新结点 i*/   
} 

对系统而言，在备用链表中分配结点相当于备用链表中减少一个结点 i，对使用者而言，相当于申请得到了一个可用的新结点 i。

3.结点回收

【算法描述】

/*备用区回收空闲结点*/ 
void   freenode(StaticList space ; int *av,int k)/*增加一个结点 k */ 
{space[k].cursor=*av;  *av=k; 
} 

对系统而言，备用链表回收空闲结点相当于备用链表中增加一个结点 k，对使用者而言，相当于释放了一个不用的结点 k。