用数组描述的链表叫做静态链表,这种描述方法叫做游标实现法
静态链表

  • 最后一个游标指向第一个有数据的元素的下标
  • 第一个游标指向数据后面第一个为空数据的下标
  • 其他每一个元素的游标都指向下一个的下标

静态链表存储结构

typedef int Status;
typedef int ElemType;

/* 静态链表存储结构 */
#define MAXSIZE 1000
typedef struct
{
    ElemType data;
    int cur;    // 游标
} Component, StaticLinkList[MAXSIZE];
  • 对数组的第一个和最后一个元素做特殊处理,其 data 不存放数据
  • 通常把未使用的数组元素称为备用链表
  • 数组的第一个元素,即下标为 0 的元素的 cur 就存放备用链表的第一个结点的下标
  • 数组的最后一个元素,即下标为 MAXSIZE - 1cur 存放第一个有数值的元素的下标,相当于单链表中的头结点作用。

静态链表初始化

/* 初始化(相当于初始化数组) */
Status InitList(StaticLinkList space)
{
    int i;
    for(i = 0; i < MAXSIZE - 1; I++)
        space[i].cur = i + 1;   // 给游标赋值,元素的游标指向下一个元素的下标

    space[MAXSIZE - 1].cur = 0; // 当前表是空的,最后一个游标指向 0

    return OK;
}

获取表的长度

/* 返回表中数据的个数 */
int ListLength(StaticLinkList L)
{
    int j = 0;
    int i = L[MAXSIZE - 1].cur;

    while(i)
    {
        i = L[i].cur;
        j++;
    }

    return j;
}

静态链表的插入

静态链表中要解决的是:如何用静态模拟动态链表结构的存储空间分配,也就是如何做到需要的时候申请(malloc),不需要的时候释放(free)。在静态链表中,操作的是数组,不存在像动态链表结点的申请和释放问题,所以需要自己实现这两个函数,才能够完成插入和删除操作。

上面说过,每一个元素指向下一个元素的下标,要在 A 后面插入一个元素 B,应该是如下:

  • 元素 A(下标 1)的游标指向插入的元素 B(下标 5)的游标 2
  • 元素 B(下标 5)的游标 2 指向元素 C(下标 2)的游标 3
  • 此时的第一个空元素(下标 0)的游标将是第一个空数据的下标 6

链表插入

/* 在表 L 中第 i 个元素插入新元素 e */
Status ListInsert(StaticLinkList L, int i, ElemType e)
{
    int j, k, l;

    k = MAXSIZE - 1;    // 数组的最后一个元素
    if(i < 1 || i > ListLength(L) + 1)
    {
        return ERROR;
    }

    j = Malloc_SLL(L);  // 获取空闲分量的下标

    if(j)
    {
        L[j].data = e;  // 在空闲分量中存放元素 e
        /* 修改游标 */
        for(l = 1; l <= i - 1; l++) // i-1 在第 i 个元素之前
        {
            k = L[k].cur;   // 将最后一个元素游标赋值给 k
        }
        L[j].cur = L[k].cur;    // 将下标为 k 的游标赋值给下标为 j (最后一个元素)的游标
        L[k].cur = j;

        return OK;
    }
    return ERROR;
}

静态链表的删除

删除的元素要放到备用链表里面

/* 删除第 i 个数据元素 */
Status ListDelete(StaticLinkList L, int i)
{
    int j, k;

    if (i<1 || i>ListLength(L))
        return ERROR;

    k = MAXSIZE-1;  // 最后一个,指向的是第一个有数据的游标

    for (j = 1; j<= i-1; j++)
    {
        k = L[k].cur;
    }

    j = L[k].cur;
    L[k].cur = L[j].cur;

    Free_SLL(L, j);

    return OK;
}
/* 将下标为 k 的空闲结点回收到备用链表 */
void Free_SLL(StaticLinkList space, int k){

    space[k].cur = space[0].cur;
    space[0].cur = k;
}

静态链表的优缺点

优点:

  • 在插入和删除操作时,只需要修改游标,不需要移动元素,改进了顺序存储结构中的插入和删除操作需要移动大量元素的缺点

缺点:

  • 没有解决连续存储分配(数组)带来的表长难以确定的问题
  • 失去了顺序存储结构随机存取的特性

静态链表是为了给没有指针的编程语言设计的一种实现单链表功能的方法,尽管可以用单链表,不用静态链表,但是这样的思考方式是值得我们去学习的。