有的开发语言并没有指针一说,那么就无法实现单链表,于是有人提出可以用数组的形式去描述单链表,称之为静态链表
同单链表的节点类似,数组的每一个元素都保存了两个值,数据和游标,游标类似于指针,其值是后继元素的下标。
静态链表的下标并不像普通数组那样代表顺序,而是每一个元素的cursor代表着顺序,比如要找到第二个元素,并不是下标为2的元素,而是第一个元素的cursor,这个cursor代表着第二个元素的下标值。
既然是数组,那么在分配内存的时候,内存大小是会大于数组大小的,为了防止数组的溢出,所以在静态链表中,有备用链表这么一说,没有保存数据的元素就是备用链表的一员。
同单链表一样,静态链表的第一个和最后一个元素也有着特殊意义,第一个元素的cursor指向的是备用链表的第一个元素的下标值,最后一个元素的cursor指向的是第一个有值的元素的下标。
单链表的定义
typedef struct StaticLinkList{
ElemType e;
int cur;
}StaticLinkList
单链表的插入
插入之前,要先做一件事,这个新插入的元素我们把它放在备用链表的第一个元素上,然后链表第一个元素的cursor指向后一个元素下标
int molloc_lls(StaticLinkList L) {
k = L[0].cursor;
if(k) {
L[0].cursor = L[k].cursor;
return k;
}
return 0;
}
下面实现插入的逻辑:
Status listInsert(StaticLinkList L, int i, ElemType e) {
// 先找到i之前那个元素的下标, k指向第i个之前元素的下标
k = MAXSIZE - 1;
for(int j = 0;j < i -1;j++) {
k = L[k].cursor;
}
// i之后元素的下标值
next = L[k].cursor;
m = mollac_lls(L);
L[m].data = e;
L[m].cursor = next;
L[k].cursor = m;
return Ok
}