静态链表
我们学了顺序表和单链表,也知道他们的优点了,那我们有没有一种方法将两种链表的有点结合起来。
静态链表,也是线性表的一种,它兼顾了顺序表和单链表的优点于一身。
使用静态链表存储数据,数据全部存储在数组中,(和顺序表一样),但存储位置是随机的,数据之间“一对一”的逻辑关系通过一个整型变量(称为“游标”,和指针功能类似)维持(和链表类似)。
这样就通过数组加游标的方式将静态链表表达出来
静态链表中的节点
通过上面的学习我们知道,静态链表存储数据元素也需要自定义数据类型,至少要包含两部分信息:
- 数据域:用于存储我们存放的值。
- 游标:其实就相当于数组的下标,指向后继元素的位置。
因此静态链表的节点构成和单链表的节点构成大体一样。
typedef struct{
int data;//数据域
int cur;//游标
}component;
备用链表
在静态链表中除去数据本身通过游标组成的链表之外,还要有一条链接各个空闲空间位置的链表,被称为备用链表。
备用链表的作用是回收数组中未使用或之前使用过(目前未使用)的存储空间,留待后期使用。也就是说,静态链表使用数组申请的物理空间中,存有两个链表,一条连接数据,另一条连接数组中未使用的空间。
在通常的情况下,备用链表的表头一般位于下标为0(a[])