小猪的数据结构辅助教程——2.3 线性表中的静态链表

标签（空格分隔）： 数据结构

碎碎念与本节学习路线图

我们前面学习了顺序表和单链表，顺序表有点类似于我们的数组，而链表则用的指针，那么
这里问个问题，如果是以前，还没有指针呢？前辈先人又是如何来实现单链表的呢？
答：机智的前人想出了这样的方法：数组下标 + 游标 的方式来实现单链表，
也就是本节要讲解的静态链表！当然你也可以直接跳过本节，毕竟考试什么的基本不会考静态链表。
这里的话我们学习的是一种思维方式，当条件限制了你不不允许使用某种方式，那么你
如何用另一种方式来解决同一的问题呢？

本节学习路线图：

学习要点：

本节只是一种思维的拓展，有兴趣可以看看，实际用得不多，考试也很少考！

1.什么是静态链表

2.静态链表的初始化

初始化流程：

• Step 1：使用for循环，为数组中的每个元素进行赋值
• Step 2：将最后一个结点的游标设置为0
• Step 3：返回OK代表初始化成功

实现代码：

Status InitList(StaticLinkList space)
{
    int i;
    for(i = 0;i < MAXSIZE - 1;i++)
    {
        //每个游标指向下一个下标,
        //比如第0个游标指向第一个下标结点 
        //第一个结点的游标指向第二个下标结点 
        space[i].cursor = i+1;                      
    }
    //最后一个结点需要结点的游标设置为0 
    space[MAXSIZE - 1].cursor = 0;  
    return OK;
}

2.获得备用链表的结点下标

int GET_Free(StaticLinkList space)
{
    int i = space[0].cursor;  
    //设置下一个结点为备用结点  
    if(space[0].cursor)
        space[0] = space[i].cursor;  
    return i;
} 

3.获得静态链表中的元素个数

int GetLength(StaticLinkList L)
{
    int j = 0;
    int i = L[MAXSIZE - 1].cursor;  //指向第一个链表的游标 
    while(i)
    {
        i = L[i].cursor;
        j++;
    }
    return j;
} 

就是遍历一次表而已,当获取到的值为0时,说明已经到达空闲结点,此时返回长度!

4.往静态链表中的第i个位置插入元素

Status ListInsert(StaticLinkList L,int i,ElemType e)
{
    int j,k,l;
    k = MAXSIZE - 1;  //数组的最后一个元素 
    //①判断插入位置是否合法
    if(i < 1 || i >GetLength(L) + 1)
    {
        return ERROR;
    } 
    //②获取空白结点的数据域
    j = GET_Free(L);
    if(j)
    {
        for(l = 1;l <= i - 1;i++)
        {
            //得到第i - 1个元素的下标
            //注意：不能直接用K = L[K - 1].cursor，因为元素可能是不相邻的
            k = L[k].cursor; 
        } 
        L[j].cursor = L[k].cursor;
        L[k].cursor = j;
        L[0].cursor = GetLength(L) + 1;  //让下标0的元素指向新的空白结点 
        return OK;
    }
    return ERROR;
}

流程解析：

我们举个例子吧，假如有一静态链表S，存储的数据为：{A,B,C,D,E}，而表的MAXSIZE = 10；
现在想往第三个位置后插入一个元素Q，下面我们来看看
插入前的静态链表：

首先，判断插入位置是否合法，i > 0且不大于链表当前元素个数 + 1
接着，我们需要获得一个当前的空白结点，用来放插入的数据，因为下标为0结点，我们是拿来
放空白结点的其实下标的，把下标获取到
再接着，通过循环我们得到第i - 1个元素的下标，这里是4，然后把值作为新结点的游标
而第四个元素的游标则设为j!最后把下标为0的结点指向下一个空白结点！插入后的静态链表：

可能我表达的不是很好，但是你自己画个表，代代数据，逻辑就清楚了！

5.删除静态链表中的第i个元素

流程解析：

我们那上面那个插入后的链表为例吧，比如我们想把第3个元素删除掉，
我们只需把第三个元素的游标给第二个元素，然后把第三个元素释放掉，不就可以了吗？
耶，突然觉得好简单啊！当然实现起来还有一些细节的地方需要考虑，具体看代码；
删除第三个元素后的静态链表：

代码实现：

Status ListDelete(StaticLinkList L,int i,ElemType e) 
{   
    int j = 0;
    if(i < 1 || i > ListLength(L))return ERROR;  //判断删除位置是否合法
    int k = MAXSIZE - 1;   //获取最后一个节点,因为它的cursor指向第一个有效结点
    //获取第i - 1个元素的下标
    for(j = 1 ; j < i ; ++j)                      
    {
        k = L[k].cursor   ;
    }
    j = L[k].cursor ;    //得到第i个元素的下标
    L[k].cursor = L[j].cursor ;  //将删除节点的cursor赋值给前一个结点
    Free_Node(L,j);     //释放到第i个元素,下标为j
    return OK;
}

//5.将下标为k的空闲结点回收为备用结点
void FreeNode(StaticLinkList space,int k)
{
    space[k].cursor = space[0].cursor;   //将之前的备用链表的第一个结点下标存放到L[k]的cursor中
    space[0].cursor = k;  //下标为k的元素称为第一个空闲结点
} 

6.静态链表的特点总结

有着和单链表类似的特性，比如插入删除元素不需要移动大量的额元素，只需修改游标；
同时也失去了顺序存储结构的随机存取的特性，而且没有解决数组带来的表长难以确定的问题！
说到底，只是为了给没有指针的编程语言提供一个链表功能的实现而已，有链表的话，一般都
是直接用的单链表，不过这种方式十分巧妙，很值得我们借鉴！

7.本节代码下载：

https://github.com/coder-pig/Data-structure-auxiliary-tutorial/blob/master/List/list3.c