数据结构笔记03

静态链表(游标实现)

系列文章

静态链表的概念

许多语言都不支持指针。如果想不使用指针实现链表，就需要使用静态链表。这种链表是通过游标访问元素的。

链表的指针实现中有两个必须实现的特性：

  1. 每个结点都是一个结构，一个结构包含数据以及指向下一个结构体的指针。
  2. 一个新的结构体可以调用 malloc() 从内存中得到，并可以通过 free() 释放。

游标方法必须能够模仿这两条特性。

下图展示了游标方法实现静态链表的原理：

满足条件1的逻辑方式是要有一个全局的结构体数组，对于该数组中的单元，其数组下标可以用来代表一个地址。

下面给出了静态链表的游标实现的声明：

#define SPACE_SIZE 32
typedef struct node_t {
    int elememt;
    int cursor;
} node;
node linkspace[SPACE_SIZE];

模拟条件2的方法是，除了数据本身通过游标组成的链表外，在静态链表中还需要有一条连接各个空闲位置的链表，称为备用链表。

备用链表 freespace 数组中的闲置单元可以执行 malloc() 和 free() 。对于 cursor 游标，0 的值等价于 NULL 指针。

通常将 linkspace[0] 作为备用链表的表头使用，linkspace[1] 作为数据链表的表头使用。这样，对应的C语言代码为：

/* remove first node of freespace */
int cursor_alloc(void) {
    int position = linkspace[0].cursor;
    linkspace[0].cursor = linkspace[position].cursor;
    return position;
}
/* insert this node to first position of freespace */
void cursor_free(int posi) {
    linkspace[posi].cursor = linkspace[0].cursor;
    linkspace[0].cursor = posi;
}

注意，如果没有可分配的空间，它会正确返回位置 0 以供判断。

有了以上实现，就可以很容易地判断一个静态链表是否为空，或一个结点是否位于静态链表末尾了：

/* return true if link list is empty
   header position assumed */
int isempty(int header) {
    return linkspace[header].cursor == 0;
}
/* return true if this node is the last position */
int islast(int posi) {
    return linkspace[posi].cursor == 0;
}

静态链表的增删查改

查找

首先是最容易编写的 find() 例程，它通过从表头逐个遍历 cursor 指向的结点来查找值：

/* return position of elem in link list, 0 if not found */
int find(int elem, int list) {
    int posi = linkspace[list].cursor;
    while (posi && linkspace[posi].elememt != elem)
        posi = linkspace[posi].cursor;
    return posi;
}

删除

删除的原理和指针链表一致，即找出前驱元素的位置 prev ，然后调用语句：
linkspace[prev].cursor = linkspace[linkspace[prev].cursor].cursor
即可完成删除。删除后还需要 free 当前位置的结点。

查询前驱元素结点的函数 findp() 的实现为：

/* if previous node is not found, last returned */
int findp(int elem, int list) {
    int prev = linkspace[list].cursor;
    while (prev && linkspace[linkspace[prev].cursor].elememt != elem)
        prev = linkspace[prev].cursor;
    return prev;
}

那么删除的例程为：

/* delete first occurence of elem from a list
   assume use of a header node */
void delete(int elem, int list) {
    int tmp;
    int posi = findp(elem, list);
    if (!islast(posi)) {
        tmp = linkspace[posi].cursor;
        linkspace[posi].cursor = linkspace[tmp].cursor;
        cursor_free(tmp);
    }
}

注意比较与指针链表的异同点。指针链表的 this->next 等价于静态链表的 linkspace[this].cursor 。

插入

发现了指针链表与静态链表的共通之处后，就可以参照编写静态链表的 insert() 例程了。相应的实现如下：

/* insert after prev, header implementation assumed */
void insert(int value, int prev) {
    int temp = cursor_alloc();
    if (temp == NULL) {
        /* raise warnings */
        return;
    }
    linkspace[temp].elememt = value;
    linkspace[temp].cursor = linkspace[prev].cursor;
    linkspace[prev].cursor = temp;
}

指针链表的核心是 node* 指针，用来在内存中找出下一个节点所在的位置。静态链表的核心是 int 值，用来在 linkspace 中找出下一个节点所在的位置。

理解了这一点，便不难理解链表与静态链表的关系了。