数据结构-静态链表及其插入删除操作

「爱情、让人受尽委屈。」 2022-06-11 07:08 288阅读 0赞

## 什么是静态链表 ##

我们平常提及的链表一般指的是动态链表，是使用指针将一个一个的结点连起来，除了动态链表之外，还有静态链表，这种链表用数组来描述，主要为了解决没有指针或者不用指针的情况下具备链表插入删除操作便捷的特性。  
静态链表中有一些专属的概念，先贴上图：  
![这里写图片描述][SouthEast]  
这就是一个静态链表，首先他是一个数组（长度为8），数组的类型显然要根据需要定义，在上图中的类型为：

typedef struct 
    {
        ElemType data;
        int cur;  
    } Component,StaticLinkList[MAXSIZE];

一般我们定义一个有两个数据区域的结构体数组：  
一个区域（**data**）用来存放实际数据；  
另一个区域（**cur**）用来存放“指向”的下一个数据区域数组的**下标**（这里的指向并不指的是指针），cur也被称之为**游标**，它里面存放的是数组的下标（先不管存放的规则如何，存放的就是数组的下标）  
数组中的元素（除了第一个和最后一个）按照有没有被使用分类的，可以分为两类（就像上面的红色和绿色），这两类元素可以分别构成链，我们可以把没有使用的那个链叫做被**备用链**。  
数组中的**第一个元素**（下标0）与**最后一个元素**（下标n-1）是不存放数据的，第一个元素的**cur**存放备用链的第一个元素的下标，最后一个元素的**cur**存放使用的链表的第一个元素的下标。比如上图中最后一个元素中cur放的是1，1是第一个红色框的下标。  
至此，静态链表就构建完了。

## 静态链表的插入操作 ##

从上面的图可以看到，其实数组的最后一个元素的cur存的是一般都是1，因为在使用元素构建链表时从第二个元素开始顺序插入，而插入的位置在哪，其实是由cur决定的，都不是顺序存储中由位置决定。  
所以，假设已经有了如上图所示的链表，现在想在第i个元素前插入一个元素，可以这样来做：  
（1）从备用链里面找出来第一个元素的下标j，让备用链减一；  
（2）将要插入的值给j的data；  
（3）i是相对于使用链表的长度来说的，所以要判断使用的链表的长度，判断i是否在范围内；  
（4）找到i的前一个元素下标k；  
（5）k的cur先变成j的cur，因为k插入到j后面，j以前的后续要有k链接；  
（6）k的cur赋值为j，由于j是一个下标，j就是cur。  
**（5）（6）的思路和动态链表的插入很像，都是要先解决后面的东西，在插前面，如果（5）（6）对调，链表断开后，k的cur原来的数被j覆盖，链表将无法重新连接。**  
![这里写图片描述][SouthEast 1]

#define MAXSIZE 1000
    typedef int Status;          
    typedef char ElemType; 
    //定义数组的类型  
    typedef struct 
    {
        ElemType data;
        int cur;  
    } Component,StaticLinkList[MAXSIZE];
    //在备用表中找到并返回第一个元素的下标，并改变数组[0]的cur
    int Malloc_SSL(StaticLinkList space) 
    { 
        int i = space[0].cur;                                                               
        if (space[0]. cur)         
            space[0]. cur = space[i].cur;                                                                                      
        return i;
    }
    //获取使用链表的长度
    int ListLength(StaticLinkList L)
    {
        int j=0;
        int i=L[MAXSIZE-1].cur;
        while(i)
        {
            i=L[i].cur;
            j++;
        }
        return j;
    } 
    //插入操作
    Status ListInsert(StaticLinkList L, int i, ElemType e)   
    {  
        int j, k, l;   
        k = MAXSIZE - 1;
        //判断是否超范围   
        if (i < 1 || i > ListLength(L) + 1)   
            return 0;  
        //返回备用表第一个元素的下标 
        j = Malloc_SSL(L);   
    
        if (j)   
        {   
            L[j].data = E;
            //找到i前面的元素下标k  
            for(l = 1; l <= i - 1; l++)   
               k = L[k].cur;   
            //j继承k的cur        
            L[j].cur = L[k].cur;
            //给k   
            L[k].cur = j;          
            return 1;   
        }   
        return 0;   
    }

需要说明的是for循环的内容，第一次看到这个for循环时可能觉得很奇怪，用l在控制循环，但是下面的内容没有变量l的参与，这是因为for只控制循环的次数就好了，k从数组的最后一位开始，而数组\[MAXSIZE - 1\]的cur中存放的就是是用链表第一个元素的下标，第一个元素的cur中放的又是第二个元素的下标，每一次k都会变成链表中下一个元素的下标。

## 静态链表的删除操作 ##

删除操作是一样的，在插入中，插入一个元素影响了**使用链**和**备用链**。那么删除一个元素的话也会同时影响这两个链。  
![这里写图片描述][SouthEast 2]  
首先考虑备用链，由于原链表中一个元素被删除了，在上图中是下标3的元素，那么原备用链中第一个元素就不再是下标5了，而应该是3，也就是说再有插入操作的时候优先插入的位置是3。那么我们就可以写出一个和Malloc\_SSL函数功能相反的函数—Free\_SSL。

void Free_SSL(StaticLinkList space, int j) 
    {  
        space[j].cur = space[0].cur;    
        space[0].cur = j;               
    }

看下这个函数，再看下之前插入代码里面的这两行：

//j继承k的cur        
            L[j].cur = L[k].cur;
            //给k   
            L[k].cur = j;

你会发现这是一毛一样的操作，这就是在下标0与备用链第一个元素之间插了一个j，而之前的代码是在下标k与k后面的元素之间插了一个j。  
其次就是原链表的变化，要删除链表中i位置的元素，同样要找到这个位置的数组的前一个数组的下标k，而k位置的元素的cur存放着要删除的元素的下标j，j的cur里面又放着下一个元素的下标，我们需要做的就是把这个下标给k的cur，这样一来，j对应的元素就从原链表中删除了。

Status ListDelete(StaticLinkList L, int i)   
    { 
        int j, k;   
        if (i < 1 || i > ListLength(L))   
            return ERROR;   
        k = MAXSIZE - 1;   
        for (j = 1; j <= i - 1; j++)   
            k = L[k].cur;   
        j = L[k].cur;   
        L[k].cur = L[j].cur;   
        Free_SSL(L, j);   
        return OK;   
    }

拿上面的图解释一下这个过程，要删除下标为3的元素，通过for循环找到它前面的元素，此时（下面的“=”是数学里面相等的关系，不是赋值！！）：  
k=2；  
L\[2\].cur=3=j；  
L\[j\].cur=L\[3\].cur=4；  
L\[2\].cur=4；  
执行 Free\_SSL(L, 3);  
L\[3\].cur=5；  
L\[0\].cur=3；

[SouthEast]: /images/20220611/cba3de792e83477a8be6c3cc57c1b947.png
[SouthEast 1]: /images/20220611/030b6fe464a14f4bb4317c113382aaeb.png
[SouthEast 2]: /images/20220611/f5966e7de58646939ddba6908e0dde9f.png