【静态链表】

本文围绕以下四个部分展开：

一、静态链表
二、插入
三、删除
四、优缺点






一、静态链表

        1. 概念

        C语言有指针，Java、C#等有对象引用机制，因此也间接实现了指针的某些作用。但对于像Basic、Fortran等早期的高级语言，是没有指针的。

        若不使用指针，如何处理链表结构？使用数组来代替指针，来描述单链表。

        这种用数组描述的链表叫做静态链表。（给没有指针的高级语言设计的一种实现单链表能力的方法。）

        游标实现法：

        让数组的元素均由两个数据域组成：data（数据域）和cur（游标）。即：数组的每个下标都对应一个data和一个cur。

        data：用来存放数据元素（要处理的数据）。

        cur：相当于单链表的next指针，存放该元素的后继在数组中的下标。


        2. 静态链表存储结构





        3. 注意

        （1）通常将数组建立得大一些，以便有一些空闲空间可以便于插入时不至于溢出。

        （2）数组的第一个和最后一个元素不存数据，作为特殊元素处理。

        4. 例子

二、插入

        例子：上图中，在乙和丁之间插入丙。

        （1）动态链表中，结点的申请使用的是malloc()函数。在静态链表中，操作的是数组，因此必须自己实现这样的函数，用来做插入操作。

        解决办法：将所有未被使用过的及已被删除的分量用游标链成一个备用链表。每当插入时，从备用链表上取得第一个结点作为待插入的新结点。

        （2）插入的算法如下：






三、删除

        例子：上图中，删除甲。

        （1）动态链表中，结点的申请使用的是free()函数。在静态链表中，操作的是数组，因此必须自己实现这样的函数，用来做删除操作。




        其中，j=L[999].cur=1, L[k].cur=L[j].cur，即：L[999].cur=L[1].cur=2。意思是：甲已删除，现在乙是第一个元素。

        代码中的：Free_SSL(L,j);如下。

        代码中，space[1].cur=space[0].cur=8，意思是：把8给“甲”所在下标为1的分量的cur。space[0].cur=k=1，意思是：让删除的位置成为第一个优先空位，把它存入第一个元素（下标为0）处的cur中。

四、优缺点

整理时重点参考：《大话数据结构》程杰著