数据结构（3）线性表之静态链表

向右看齐 2023-10-10 10:02 31阅读 0赞

### 数据结构（3）线性表之静态链表 ###

*   *   *  前言
         *  用数组表示线性表
         *   *  顺序表示
             *  链式表示
         *  静态链表的具体设计
         *  静态链表的初始化
         *  静态链表的插入
         *   *  Malloc\_SL方法从备用链表中申请空间
             *  头部插入
             *  尾部插入
             *  按位置插入
         *  静态链表的删除
         *  注
         *  全部代码
         *   *  StaticList.h
             *  StaticList.cpp
             *  Main.cpp

### 前言 ###

静态链表，就是用数组描述的链表。静态链表在初始化时要确定数组的长度，所以需要预先分配空间，其空间大小一般是静态的，故名静态链表(这一点同之前所说的顺序表相似)。先前所说的单链表，是在创建和插入时调用malloc函数来申请空间，其空间大小是动态分配的，所以属于动态链表。

### 用数组表示线性表 ###

数组下标在某种意义上可以看作是地址，在一些没有指针的语言中(例如Basic、Fortran)，就能利用数组下标达到访问某个内存空间的效果，继而可以实现链式表示。(实际上，利用数组下标同样可以实现顺序表示）

#### 顺序表示 ####

用数组来实现顺序表示非常简单，只需要把数据存入数组中即可。我们之前所写的顺序表类似于自己实现了数组的相关操作。

![img\_1][img_1]

#### 链式表示 ####

用数组来实现链式表示，则数组中需要存储的是一个结构体，与链表相似，结构体由两个部分组成：一个保存数据的数据域和一个指向后继结点的指针域。只不过在数组中，这个指针域并不存放后继结点的地址，而是存放后继结点所在位置的下标。

![img\_2][img_2]

### 静态链表的具体设计 ###

*  采用有头结点的结构，则数组第一位为头结点，数据域不储存数据，cur存放首元结点的下标
 *  链表进行插入时，仍需申请空间，但是不再从整个内存中申请空间，而是从数组中申请空间(称未被使用的数组部分为备用链表)，因此还需要一个结点来存储备用链表第一个结点的下标。
    
    ![img\_3][img_3]

### 静态链表的初始化 ###

先前说，在插入链表时需要从pool中去申请空间，就是通过pool结点的cur值得到备用链表第一个结点的下标。那么pool结点如何知道备用链表从哪里开始呢？根据我们设计的结构，可以知道我们是从下标为2的地方开始存储数据，第一个方法是利用一个变量index来记录，初始值为2，每申请一个空间index便加1，当index值大于数组的大小时，说明已经没有多余空间了，申请失败。

第二个方法是，除头结点外，设置每个结点的cur值为它后一个位置的下标（pool也不例外，这样相当于初始化pool的cur为2）。这样在申请结点空间时，将pool的cur所指的结点拿来存放数据，再把该结点的cur值交给pool。相当于从备用链表中取出一个结点，再将下一个结点拿来备用。这样做要特别标识数组最后一位的cur值，以免越界。

![img\_4][img_4]  
这里我采用的是第二种方法，因此初始化链表主要包括三个部分的内容

*  设置头结点的cur值
 *  初始化除头结点外的结点的cur值
 *  设置数组最后一位的cur值
    
        void InitSList(StaticList space){ 
            //初始化除头结点外的结点的cur值
            for (int i = 1; i < MAX_SIZE; i ++) { 
                space[i].cur = i+1;
            }
            //设置数组最后一位的cur值
            space[MAX_SIZE-1].cur = 0;
            //设置头结点的cur值
            space[0].cur = -1;
        }

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

静态链表的插入操作主要分为两个部分

*  从备用链表处申请结点
 *  将数据存入申请来的结点中、设置有关cur值

但是，插入有多种方式：头部插入、尾部插入、按位置插入、按值插入……要实现不同的插入方式，和cur值的设置有关，和申请结点无关；如果要实现多个插入方式，这个操作无疑是重复了。所以为了效率起见，我们可以把它单独作为一个方法，这样在实现不同插入时就只需要调用函数获得结点即可。

#### Malloc\_SL方法从备用链表中申请空间 ####

int Malloc_SL(StaticList space){ 
        
        //获得备用链表第一个结点的下标
        int i = space[1].cur;
        
        if (space[1].cur != 0) { 
            //还有备用空间，取得备用空间
            space[1].cur = space[i].cur;
        }
        //将下标返回
        return i;
    }

#### 头部插入 ####

通过head处的cur值找到链表第一个结点，设置新生成结点的cur值为第一个结点的下标，再设置head处的cur值为新结点的下标

注：用-1表示到达链表尾部

![img\_5][img_5]

#### 尾部插入 ####

除第一次插入外，head处的cur值不用变，且新生成结点的cur值都为-1，只需要找到原有链表的最后一个结点，再修改该结点的cur值为新生成的结点即可

![img\_6][img_6]

#### 按位置插入 ####

回顾一下我们在数组中按位置插入的方法：找到要插入的位置，将从该位置起所有元素往后移一位(假设没有越界)，再将数据保存到要插入的位置上。

按理来说，静态链表是用数组实现的，应该也可以使用这个方式。但是，我们设计的结构里用游标(cur)来控制链表的逻辑顺序，数据实际在数组中的存放顺序可能是不同的。因此要挪动数据，不能像数组中一样简单地倒序遍历、存值，而是需要像链表一样一个个去找位置。由于我们使用的还是单向链表，这样的遍历就更为困难了。

好消息是，也正由于游标的存在，可以通过修改cur值来修改链表的逻辑结构，不需要移动大量的数据。这也是链表的普遍优点：在插入、删除时十分方便

![img\_7][img_7]

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

静态链表的删除也分为两个部分

*  修改cur的指向
 *  将被删除的结点回收到pool中

与插入类似，回收结点的操作也可以单独用一个函数来完成。这里只写了头部删除的操作。  
![img\_9][img_9]

### 注 ###

在编程实现时，不同资料里对函数参数的书写有所不同

void InitSList0(StaticList space);
    void InitSList1(ListNode *space);
    
    void InitSList2(StaticList &space);

常见的是 InitSList0 和 InitSlist2 这样的写法。我们对链表本身进行修改，所需要的是链表的地址，InitSList0 是将数组作为函数参数传递，实际上就是把数组的首地址(第一个元素的地址)传了过来，它本身是一个ListNode类型的地址，因此使用 InitSList1 这样的写法也同样可行。以上两种写法中，space都只是用于接收的形参名。

而 InitSlist2 这样的写法，传递的是数组的引用，相当于给数组起了一个别名space，无论是操作别名space还是操作数组本身的名字，实际上操作的是同一片空间的内容，所以达到的效果是一致的。

两者的区别可能在传递数组时不太明显，那么可以看下面的例子

![img\_8][img_8]  
要注意的一点是，C语言中并没有“引用”这一概念，这是C++才有的概念，如果按 InitSlist2 的方式书写并且能运行说明使用的是C++的编译器。

### 全部代码 ###

#### StaticList.h ####

#ifndef StaticList_h
    #define StaticList_h
    
    #include <stdio.h>
    
    #define MAX_SIZE 20
    #define ElemType char
    
    typedef struct ListNode{ 
        ElemType data;
        int cur;
    }ListNode;
    
    typedef ListNode StaticList[MAX_SIZE];
    
    //从pool中分配空间
    int Malloc_SL(StaticList space);
    //从pool中释放空间
    void Free_SL(StaticList space,int i);
    
    //初始化静态链表
    void InitSList(StaticList space);
    void InitSList1(ListNode *space);
    void InitSList2(StaticList &space);
    
    
    //头部插入
    void Insert_fount(StaticList space,ElemType x);
    //尾部插入
    void Insert_back(StaticList space,ElemType x);
    //按位置插入
    void Insert_pos(StaticList space,ElemType x,int pos);
    
    //展示
    void ShowSList(StaticList space);
    //删除
    void Delete(StaticList space);
    
    #endif /* StaticList_h */

#### StaticList.cpp ####

#include "StaticList.h"
    
    //从pool中分配空间
    int Malloc_SL(StaticList space){ 
        
        //获得备用链表第一个结点的下标
        int i = space[1].cur;
        
        if (space[1].cur != 0) { 
            //还有备用空间，取得备用空间
            space[1].cur = space[i].cur;
        }
        //将下标返回
        return i;
    }
    
    //从pool中释放空间
    void Free_SL(StaticList space,int i){ 
        space[i].cur = space[1].cur;
        space[1].cur = i;
    }
    
    //初始化静态链表
    void InitSList(StaticList space){ 
        //初始化除头结点外的结点的cur值
        for (int i = 1; i < MAX_SIZE; i ++) { 
            space[i].cur = i+1;
        }
        //设置数组最后一位的cur值
        space[MAX_SIZE-1].cur = 0;
        //设置头结点的cur值
        space[0].cur = -1;
    }
    void InitSList1(ListNode *space){ 
        //初始化除头结点外的结点的cur值
        for (int i = 1; i < MAX_SIZE; i ++) { 
            space[i].cur = i+1;
        }
        //设置数组最后一位的cur值
        space[MAX_SIZE-1].cur = 0;
        //设置头结点的cur值
        space[0].cur = -1;
    }
    
    void InitSList2(StaticList &space){ 
    	for(int i = 1;i < MAX_SIZE; i ++){ 
    		space[i].cur = i+1;
    	}
    	//设置数组最后一位的cur值
        space[MAX_SIZE-1].cur = 0;
        //设置头结点的cur值
        space[0].cur = -1;
    }
    
    
    //头部插入
    void Insert_fount(StaticList space,ElemType x){ 
        //从备用链表中申请空间
        int i = Malloc_SL(space);
        
        if (i == 0) { 
            //链表没有空间了
            printf("申请结点空间失败");
            return;
        }
        
        space[i].data = x;
        
        //判断是否是第一个结点
        if (space[0].cur == -1) { 
            //是第一个,把该结点的指向改为-1
            space[i].cur = -1;
            //修改head的指向
            space[0].cur = i;
        }else{ 
            space[i].cur = space[0].cur;
            //修改head的指向
            space[0].cur = i;
        }
    }
    
    //按位置插入
    void Insert_pos(StaticList space,ElemType x,int pos){ 
    	
    	//1.1从备用链表中申请空间
        int i = Malloc_SL(space);
    	
    	if (i == 0) { 
            //链表没有空间了
            printf("申请结点空间失败!\n");
            return;
        }
    
    
        //判断要插入的位置是否合法
        if (pos > i-1) { 
            printf("要插入的位置不合法!\n");
            return;
        }else if(pos == 1){ 
    		//直接进行头部插入
    		//如果不直接进行头部插入，也要额外判断，因为要修改head的cur值
    		Insert_fount(space,x);
    	}else{ 
    		//1.2存值
    		space[i].data = x;
    	
    
    		//2.1遍历链表,找到插入位置
    		int k = space[0].cur;
    		while(k != pos){ 
    			printf("pos = %d\n",pos);
    			printf("k = %d\n",k);
    			k = space[k].cur;
    		}
    
    		//2.2插入
    		space[i].cur = space[k].cur;
    		space[k].cur = i;
        
    	}
    
    }
    
    //尾部插入
    void Insert_back(StaticList space,ElemType x){ 
        //从备用链表中申请空间
        int i = Malloc_SL(space);
        
        if (i == 0) { 
            //链表没有空间了
            printf("申请结点空间失败");
            return;
        }
        
        space[i].data = x;
        space[i].cur = -1;
        
        //寻找到原有链表的最后一个结点
        int k = space[0].cur;
        while (space[k].cur != -1) { 
            k = space[k].cur;
        }
        //判断是否是第一个结点
        if (k == -1) { 
            //是，修改head的指向
            space[0].cur = i;
        }else{ 
            //将结点连接到最末尾
            space[k].cur = i;
        }
    }
    
    //展示
    void ShowSList(StaticList space){ 
        //获得第一个结点的位置
        int i = space[0].cur;
        
        //遍历链表
        while (i != -1) { 
            printf(" %c",space[i].data);
            
            //更改i的指向
            i = space[i].cur;
        }
        printf("\n");
    }
    
    //头部删除
    void Delete(StaticList space){ 
        int i = space[0].cur;
        
        space[0].cur = space[i].cur;
        
        //将该空间回收
    // space[i].cur = space[1].cur;
    // space[1].cur = i;
        Free_SL(space, i);
    }

#### Main.cpp ####

#include "StaticList.h"
    
    int main(int argc, const char * argv[]) { 
        StaticList SL;
    
        InitSList(SL);
    	//InitSList1(SL);
    	//InitSList2(SL);
        
        for (int i = 0; i < 5; i ++) { 
            Insert_back(SL, 'A'+i);
    		//Insert_fount(SL,'a'+i);
        }
        ShowSList(SL);
    
    	Insert_pos(SL,'Z',2);
    	ShowSList(SL);
        
        Delete(SL);
        ShowSList(SL);
        
        return 0;
    }

[img_1]: https://img-blog.csdnimg.cn/20190924194345534.png
[img_2]: https://img-blog.csdnimg.cn/20190924194414308.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjY0MzIxNg==,size_16,color_FFFFFF,t_70
[img_3]: https://img-blog.csdnimg.cn/20190924194510765.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjY0MzIxNg==,size_16,color_FFFFFF,t_70
[img_4]: https://img-blog.csdnimg.cn/20190924194643713.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjY0MzIxNg==,size_16,color_FFFFFF,t_70
[img_5]: https://img-blog.csdnimg.cn/20190924194746623.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjY0MzIxNg==,size_16,color_FFFFFF,t_70
[img_6]: https://img-blog.csdnimg.cn/20190924194828519.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjY0MzIxNg==,size_16,color_FFFFFF,t_70
[img_7]: https://img-blog.csdnimg.cn/20190926162144882.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjY0MzIxNg==,size_16,color_FFFFFF,t_70
[img_9]: https://img-blog.csdnimg.cn/20190926164558990.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjY0MzIxNg==,size_16,color_FFFFFF,t_70
[img_8]: https://img-blog.csdnimg.cn/2019092419515227.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjY0MzIxNg==,size_16,color_FFFFFF,t_70