线性表 – 静态链表

有的开发语言并没有指针一说,那么就无法实现单链表,于是有人提出可以用数组的形式去描述单链表,称之为静态链表

同单链表的节点类似,数组的每一个元素都保存了两个值,数据和游标,游标类似于指针,其值是后继元素的下标。

静态链表的下标并不像普通数组那样代表顺序,而是每一个元素的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 
}

静态链表的php模拟

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注