现在我们来看看如何实现元素的插入。

    静态链表中要解决的是：如何用静态模拟动态链表结构的存储空间的分配，需要时申请，无用时释放。

    我们前面说过，在动态链表中，结点的申请和释放分别借用malloc()和free()两个函数来实现。在静态链表中，操作的是数组，不存在像动态链表的结点申请和释放问题，所以我们需要自己实现这两个函数，才可以做插入和删除的操作。

    为了辨明数组中哪些分量未被使用，解决的办法是将所有未被使用过的及已被删除的分量用游标链成一个备用的链表，每当进行插入时，便可以从备用链表上取得第一个结点作为待插入的新结点。

    1. /* 若备用空间链表非空，则返回分配的结点下标，否则返回0 */
    2. int Malloc_SLL(StaticLinkList space) {
    4.     /* 当前数组第一个元素的cur存的值， */
    5.     /* 就是要返回的第一个备用空闲的下标 */
    6.     int i = space[0].cur;
    8.     /* 由于要拿出一个分量来使用了，所以我们 */
    9.     /* 就得把它的下一个分量用来做备用 */
    10.     if (space[0].cur)
    11.         space[0].cur = space[i].cur;
    13.     return i; 
    14. }

    这段代码有意思，一方面它的作用就是返回一个下标值，这个值就是数组头元素的cur存的第一个空闲的下标。从上面的图示例子来看，其实就是返回7。

    那么既然下标为7的分量准备要使用了，就得有接替者，所以就把分量7的cur值赋值给头元素，也就是把8给space[0].cur，之后就可以继续分配新的空闲分量，实现类似malloc()函数的作用。

    现在我们如果需要在“乙”和“丁”之间，插入一个值为“丙”的元素，按照以前顺序存储结构的做法，应该要把“丁”、“戊”、“己”、“庚”这些元素都往后移一位。但目前不需要，因为我们有了新的手段。

    新元素“丙”，想插队是吧？可以，你先悄悄地在队伍最后一排第7个游标位置待着，我一会就能帮你搞定。我接着找到了“乙”，告诉他，你的cur不是游标为3的“丁”了，这点小钱，意思意思，你把你的下一位的游标改为7就可以了。“乙”叹了口气，收了钱把cur值改了。此时再回到“丙”那里，说你把你的cur改为3。就这样，在绝大多数人都不知道的情况下，整个排队的次序发生了改变（如图3-12-3所示）。

    实现代码如下。

    1. /* 在L中第i个元素之前插入新的数据元素e */
    2. Status ListInsert(StaticLinkList L, int i, ElemType e){
    4.     int j, k, l;
    6.     /* 注意k首先是最后一个元素的下标 */
    7.     k = MAX_SIZE - 1;
    9.     if (i < 1 || i > ListLength(L) + 1)
    10.         return ERROR;
    12.     /* 获得空闲分量的下标 */
    13.     j = Malloc_SSL(L);
    15.     if (j){
    17.         /* 将数据赋值给此分量的data */
    18.         L[j].data = e;
    20.         /* 找到第i个元素之前的位置 */
    21.         for (l = 1; l <= i - 1; l++)
    22.             k = L[k].cur;
    24.         /* 把第i个元素之前的cur赋值给新元素的cur */
    25.         L[j].cur = L[k].cur;
    27.         /* 把新元素的下标赋值给第i个元素之前元素的cur */
    28.         L[k].cur = j;
    30.         return OK;
    32.     }
    34.     return ERROR;
    36. }
    • 当我们执行插入语句时，我们的目的是要在“乙”和“丁”之间插入“丙”。调用代码时，输入i值为3。
    • 第4行让k=MAX_SIZE-1=999。
    • 第7行，j=Malloc_SSL(L)=7。此时下标为0的cur也因为7要被占用而更改备用链表的值为8。
    • 第11～12行，for循环l由1到2，执行两次。代码k=L[k].cur;使得 k=999,得到k=L[999].cur=1，再得到k=L[1].cur=2。
    • 第13行，L[j].cur=L[k].cur;因j=7，而k=2得到L[7].cur=L[2].cur=3。这 就是刚才我说的让“丙”把它的cur改为3的意思。
    • 第14行，L[k].cur=j;意思就是L[2].cur=7。也就是让“乙”得点好处， 把它的cur改为指向“丙”的下标7。

    就这样，我们实现了在数组中，实现不移动元素，却插入了数据的操作（如图3-12-3所示）。没理解可能觉得有些复杂，理解了，也就那么回事。
    image.png