静态链表

我们都知道，C 语言是一门伟大都语言，它都魅力在于指针都灵活性，使得它可以非常容易的操作内存中的地址和数据，这使得它比一些其他的高级语言更加灵活和方便，但是在一些高级语言当中，比如 Java 中的面向对象，就是使用对象引用机制间接的实现了指针的某些功能

静态链表其实是为了给没有指针的编程语言设计的一种实现单链表功能的方法，尽管我们可以使用单链表，但是静态链表的思想是非常巧妙的，应该有所了解

什么是静态链表

但是在 C 语言之前，只有原始的 Basic，Fortran 等早期的编程语言，这些语言当中并没有类似于 C 的指针功能，所以有人就想出了一种使用数组来代替指针用来描述单链表，这种用数组来描述的链表就叫做『静态链表』，这种描述的方法叫做『游标实现法』，如下图所示

对应的线性表的静态链表存储结构代码如下

#define MAXSIZE 1000

typedef struct {
  ElemType data;  // 数据
  int cur;        // 游标
} Component, StaticLinkList[MAXSIZE];

对静态链表进行初始化相当于初始化数组

Status InitList(StaticLinkList space) {
  int i;
  for(i = 0; i < MAXSIZE - 1; i++)
    space[i].cur = i + 1;
  space [MAXSIZE - 1].cur = 0;
  return OK;
}

下面是一些需要注意的地方

一般对数组的第一个和最后一个元素做特殊处理，他们的 data 不存放数据
通常把未使用的数组元素称为备用链表
数组的第一个元素，即下标为 0 的那个元素的 cur 就存放备用链表的第一个结点的下标
数组的最后一个元素，即下标为 MAXSIZE - 1 的 cur 则存放第一个有数值的元素的下标，相当于单链表中的头结点作用

下面我们就来看看静态链表如何模拟单链表进行插入和删除的操作

静态链表的插入操作

在静态链表中，我们主要解决的就是如何模拟动态链表结构的存储空间分配，也就是需要的时候申请，不需要的时候释放，在之前，我们提到过，为了辨明数组中哪些分量未被使用，解决的方法是将所有未被使用过的及已被删除的分量用游标链成一个备用的链表，每当进行插入时，便可以从备用链表上取得第一个结点作为待插入的新结点，我们以上面第示例来进行说明，比如我们要在 A 的后面插入 B，如下图

我们要做的首先是获得空闲分量的下标

int Malloc_SLL(StaticLinkList space) {
  int i = space[0].cur;
  if(space[0].cur) {
    space[0].cur = space[i].cur;  // 把它的下一个分量用来作为备用
    return i;
  }
}

/* 在静态链表 L 中第 i 个元素之前插入新第数据元素 */
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;
    for(l = 1; l <= i - 1; l++) {
      k = L[k].cur;
    }
    L[j].cur = L[k].cur;
    L[k],cur = j
    return OK;
  }
  return ERROR;
}

最终结果如下图所示

静态链表的删除操作

还是以上面的示例为例，这次我们来删掉 C 元素

/* 删除在 L 中的第 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;
}

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

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

  return j;
}

结果如下

静态链表的优缺点

静态链表的优点是在插入和删除操作时，只需要修改游标，不需要移动元素，从而改进了在顺序存储结构中的插入和删除操作需要移动大量元素的缺点，而缺点也比较明显，没有解决连续存储分配（数组）带来的表长难以确定的问题，失去了顺序存储结构随机存取的特性，即不能直接使用下标来找到指定的值了，因为它某些程度上来说，已经具备了一些单链表的特性了

# Essay

静态链表

什么是静态链表

静态链表的插入操作

静态链表的删除操作

静态链表的优缺点

评论

目录

分类

标签云

最新文章

归档

标签

Your browser is out-of-date!