2.4.2 静态链表的实现

静态链表的基本操作如下（基本操作实现存放在“SLinkList.h”文件中）。

（1）静态链表的初始化。在初始化静态链表时，只需要把静态链表的游标cur指向下一个结点，并将链表的最后一个结点的cur域置为0。

（2）分配结点。分配结点就是要从备用链表中取下一个结点的空间，分配给要插入链表中的元素，返回值为要插入结点的位置。

（3）回收结点。回收结点就是将空闲的结点回收，使其称为备用链表的空间。

（4）插入操作。插入操作就是在静态链表中第i个位置插入一个数据元素e。首先从备用链表中取出一个可用的结点，然后将其插入到已用静态链表的第i个位置。

例如，要在图2.33的静态链表中的第5个元素后插入元素“Chen”。具体步骤是：

①为新结点分配一个结点空间，即静态链表的数组编号为8的位置，即k=L.av，同时修改备用指针L.av=L.list[k].cur。

②在编号为8的位置上插入一个元素“Chen”，即L.list[8].data="Liu"。

③修改第5个元素位置的cur域，即L.list[5].cur=L.list[8].cur，L.list[8].cur=6。

插入过程如图2.34所示。

插入操作的算法描述如下。

（5）删除操作。删除操作就是将静态链表中第i个位置的元素删除。首先找到第i-1个元素的位置，修改cur域使其指向第i+1个元素，然后将被删除的结点空间放到备用链表中。

例如，要删除图2.33所示的静态链表中的第3个元素，需要根据游标找到第2个元素，将其cur域修改为第4个元素的位置，即L.list[2].cur=L.list[3].cur。最后要将删除元素的结点空间回收。删除结点操作如图2.35所示。

删除操作的算法描述如下。