四、线性表(五)、 静态链表

数据结构目录

在没有指针的时代，要描述静态链表是比较困难的，前人想到了使用数组与游标来表示单链表的方法，如下图

静态链表

在静态链表中，数组第一位的游标存放第一位没有数据的元素的下标，数组最后一位的游标存放第一位有数据的元素的下标。

这种用数组描述的链表叫做静态链表，这种描述方法叫做游标实现法。

1. 线性表的静态链表存储结构及初始化

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

Status InitList(StaticLinkList L)
{
    for (int i = 0; i < MAXSIZE-1; i++) {
        //初始化的时候除了最后一位，前面的游标都指向下一位，这样就串联成了备用链表
        L[i].cur = i+1;
    }
   //最后一位游标为0，因为没有有数据的项
    L[MAXSIZE-1].cur = 0;
    return OK;
}

静态链表备忘录

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

2.获取静态链表的长度

int ListLength(StaticLinkList L){
    //获取第一个有值结点的下标 如果没有有值的结点，那么i是0
    int i = L[MAXSIZE-1].cur;
    int sum = 0;
    while (i > 0) {
        sum++;
        //一直遍历，因为最后一个有值结点的游标一定是0
        i = L[i].cur;
    }
    return sum;
}

3.静态链表获取操作

Status GetElem(StaticLinkList L,int i,ElemType *e){
    //超出范围 直接报错
    if (i < 0 || i > ListLength(L)) {
        return ERROR;
    }
    //获取第一个有值结点的下标 如果没有有值的结点，那么i是0
    int j = L[MAXSIZE-1].cur;
    //空表直接返回错误
    if (j == 0) {
        return ERROR;
    }
    int order = 1;
    //不断遍历，获取到第i个位置的下标
    while (order < i) {
        order++;
        j = L[j].cur;
    }
    //返回值
    *e = L[j].data;
    
    return OK;
}

4.静态链表的插入操作

静态链表中要实现元素的插入，需要解决的是:如何用静态模拟动态链表结构的存储空间分配，也就是需要的时候申请，不需要的时候释放

在动态链表中，结点的申请和释放分别借用C语言的malloc()和free()两个函数来实现

在静态链表中，操作的是数组，不存在像动态链表的结点申请和释放的问题，所以我们需要自己实现这两个函数，才可以做到插入和删除操作。

另外，我们需要辨明数组中哪些分量未被使用，解决的方法是讲所有未被使用过的及已被删除的分量用游标链成一个备用的链表，每当进行插入时，便可以从备用链表上取得第一个节点作为待插入的新结点，如图所示，我们要在A后面插入B：

image

//获取空闲分量的下标
int Malloc_SLL(StaticLinkList L)
{
    int i = L[0].cur;
    if (i != 0) {
        //如果不是空链表,那么把备用链表的下一个分量作为备用链表的起始
        L[0].cur = L[i].cur;
    }
    //返回获取到的下标
    return i;
}
Status ListInsert(StaticLinkList L,int i,ElemType e){
    if (i < 1 || i < ListLength(L)) {
        return ERROR;
    }
    //获取备用链表的第一个分量下标
    int j = Malloc_SLL(L);
    //如果备用链表的第一个分量下标为0，表示链表已满，返回错误
    if (j == 0) {
        return ERROR;
    }
    //赋值
    L[j].data = e;
    
    //获取链表的第一个分量的下标
    int k = L[MAXSIZE-1].cur;
    int order = 1;
    //不断遍历，获取到第i-1个分量的下标
    while (order < i-1) {
        order++;
        k = L[k].cur;
    }
    L[j].cur = L[k].cur;
    L[k].cur = j;
    
    return OK;
}

5.静态链表的删除操作操作

删除如图示：

image

删除操作我们需要实现Free()函数，在调用Free()函数之前，将删除位置直接前驱结点的游标指向删除位置直接后继结点。

//释放结点
void Free_SLL(StaticLinkList space,int k){
    //让此结点游标指向备用链表的开始结点
    space[k].cur = space[0].cur;
    //备用链表的头指针指向此结点
    space[0].cur = k;
}

Status ListDelete(StaticLinkList L,int i,ElemType *e)
{
    if (i < 1 || i > ListLength(L)) {
        return ERROR;
    }
    //获取链表的第一个分量的下标
    int j = L[MAXSIZE-1].cur;
    if (j == 0) {
        return ERROR;
    }
    int order = 1;
    //通过遍历，获取到第i-1个元素的下标
    while (order < i - 1) {
        order++;
        j = L[j].cur;
    }
    //k就是第i个结点的下标
    int k = L[j].cur;
    L[j].cur = L[k].cur;
    Free_SLL(L, k);

    return OK;
}

6.静态链表优缺点总结

.优点

— 在插入和删除操作时，只需要修改游标，不需要移动元素，从而改进了在顺序存储结构中的插入和删除操作需要移动大量元素的缺点

.缺点

— 没有解决连续存储分配(数组)带来的表长难以确定的问题

— 失去了顺序存储结构随机存取的特性

.总的来说，静态链表其实是为了给没有指针的编程语言设计的一种实现单链表功能的方法

.尽管我们可以用单链表就不用静态链表了，但这样的思考方式是非常巧妙的，应该理解其思想，以备不时之需