静态链表

我们学了顺序表和单链表,也知道他们的优点了,那我们有没有一种方法将两种链表的有点结合起来。

静态链表,也是线性表的一种,它兼顾了顺序表和单链表的优点于一身。

使用静态链表存储数据,数据全部存储在数组中,(和顺序表一样),但存储位置是随机的,数据之间“一对一”的逻辑关系通过一个整型变量(称为“游标”,和指针功能类似)维持(和链表类似)。 这样就通过数组加游标的方式将静态链表表达出来

静态链表中的节点

通过上面的学习我们知道,静态链表存储数据元素也需要自定义数据类型,至少要包含两部分信息:

  1. 数据域:用于存储我们存放的值。
  2. 游标:其实就相当于数组的下标,指向后继元素的位置。

因此静态链表的节点构成和单链表的节点构成大体一样。

typedef struct{
  int data;//数据域
  int cur;//游标
}component;

备用链表

在静态链表中除去数据本身通过游标组成的链表之外,还要有一条链接各个空闲空间位置的链表,被称为备用链表。

备用链表的作用是回收数组中未使用或之前使用过(目前未使用)的存储空间,留待后期使用。也就是说,静态链表使用数组申请的物理空间中,存有两个链表,一条连接数据,另一条连接数组中未使用的空间。

在通常的情况下,备用链表的表头一般位于下标为0(a[])

Posts in this Series