静态链表的介绍及实现

谁践踏了优雅 2022-10-30 05:21 147阅读 0赞

**上一篇博客：[并查集][Link 1]**

>  写在前面：大家好！我是`AC-fun`,我的昵称来自两个单词`Accepted`和`fun`。我是一个热爱ACM的蒟蒻。如果博客中有不足或者的错误的地方欢迎在评论区或者私信我指正，感谢大家的不吝赐教。我的唯一博客更新地址是：[https://ac-fun.blog.csdn.net/][https_ac-fun.blog.csdn.net]。非常感谢大家的支持。一起加油，冲鸭！  
>  `用知识改变命运，用知识成就未来！加油 (ง •̀o•́)ง (ง •̀o•́)ง`

### 文章目录 ###

*  简介
 *  初始化
 *  头插法插入数据
 *  在任一合法位置插入数据
 *  删除节点
 *  说明
 *  例题
 *   *  题目信息
     *   *  题目描述
         *  输入格式
         *  输出格式
         *  数据范围
         *  输入样例
         *  输出样例
     *  解题代码

# 简介 #

用数组描述的单链表叫做静态链表，它兼顾了顺序表和链表的优点于一身，可以看做是顺序表和链表的升级版。使用静态链表存储数据，数据全部存储在数组中（和顺序表一样），但存储位置是随机的，数据之间"一对一"的逻辑关系通过一个整形变量（称为"游标"，和指针功能类似）维持（和链表类似）。

使用一个数组 **e\[N\]** 来存储数据，**e\[i\]** 表示节点 **i** 的值。 **ne\[N\]** 表示当前节点的 **next** 指针，**ne\[i\]** 表示节点 **i** 的 next 指针是多少。使用 `head` 表示头指针，用来存储头结点的下标，初始状态下 `head` 指向尾结点，使用 **-1** 表示尾结点。使用 `idx` 表示当前已经用到了那个点，从第 **0** 个点开始。

例如第一个节点存储的数据为 `6`，它的下一个节点的编号为 **1** ，编号为 **1** 的节点存储的数据为 `9` ，下一个节点为尾结点。那么可以表示为：  
![静态链表的表示][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNTc1NTA3_size_16_color_FFFFFF_t_70]

# 初始化 #

初始状态下头指针 `head` 指向尾结点，表示空链表。尾结点可以使用 **-1** 来表示。一个节点也没有分配，所以 `idx` 初始状态下为 **0**。这里的 `idx` 可以想象为当前分配的内存空间的地址。

// 静态链表初始化
    void init() { 
        head = -1; // 初始条件下头指针指向尾结点
        idx = 0;   // idx 表示当前分配的内存空间的地址
    }

# 头插法插入数据 #

假设当前链表中已经有了写数据，表示为下图：  
![静态链表的表示][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNTc1NTA3_size_16_color_FFFFFF_t_70]  
现在要求在第一个节点之前插入一个新的节点，节点的值为 **9** 。当前状态下头指针指向第一个节点的地址 **0**。`idx = 2`，表示要插入节点的编号为 **2**。首先将数值存入到单链表中即 `e[2] = 9`；先让编号为 **2** 的节点的指针指向第一个节点，即 `ne[2] = 0`；然后再让头指针指向编号为 **2** 的点，即 `head = 2`，最后将 `idx++` 表示下一个新节点的将要使用的内存地址。

// 向链表头插入一个元素
    void addToHead(int x) { 
        e[idx] = x;
        ne[idx] = head;
        head = idx;
        idx++;
    }

这里的最后两步可以直接简写为一步使 `idx` 先赋值后加一，即 `head = idx++;`。因此头插法的代码可以写为：

// 向链表头插入一个元素
    void addToHead(int x) { 
        e[idx] = x;
        ne[idx] = head;
        head = idx++;
    }

# 在任一合法位置插入数据 #

静态链表不仅支持在头结点的位置插入元素，还可以支持在任一一个合法的位置插入一个节点。只要是单链表可以实现的操作静态链表都可以实现。以在下标为 **k** 的节点的后面插入一个节点为例：

首先将数据 **x** 存储到新申请到的节点中，即 `e[idx] = x;`，再使新节点的 **next** 指针指向第 **k** 个节点的下一个节点的地址，即 `ne[idx] = ne[k - 1]` 因为下标是从 **0** 开始的，所以第 **k** 个节点的下标为 **k - 1**。最后使 `idx++`。  
![插入操作][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNTc1NTA3_size_16_color_FFFFFF_t_70 1]

void add(int k, int x) { 
        e[idx] = x;
        ne[idx] = ne[k - 1];
        ne[k - 1] = idx;
        idx++;
    }

同样也可以将最后两步进行合并：

void add(int k, int x) { 
        e[idx] = x;
        ne[idx] = ne[k - 1];
        ne[k - 1] = idx++;
    }

# 删除节点 #

这里的删除节点并不是真正的删除节点，只要让当前节点的前一个节点的 `next` 指针指向当前节点后面节点的地址即可。比如删除第 k 个节点：

ne[k - 1] = ne[ne[k - 1]];

![删除操作][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNTc1NTA3_size_16_color_FFFFFF_t_70 2]

--------------------

# 说明 #

静态链表还有很多操作可以实现，只要单链表可以实现的操作这里提到的静态链表都可以实现。比如尾插法插入元素、查找元素、输出单链表的长度等等。这里就不一一介绍了，感兴趣的小伙伴可以按照已有的代码自己实现一下。

# 例题 #

**题目来源：** [AcWing 826. 单链表][AcWing 826.]

## 题目信息 ##

### 题目描述 ###

实现一个单链表，链表初始为空，支持三种操作：

(1) 向链表头插入一个数；

(2) 删除第 **k** 个插入的数后面的数；

(3) 在第 **k** 个插入的数后插入一个数；

现在要对该链表进行 **M** 次操作，进行完所有操作后，从头到尾输出整个链表。

**注意:** 题目中第 **k** 个插入的数并不是指当前链表的第 **k** 个数。例如操作过程中一共插入了 **n** 个数，则按照插入的时间顺序，这 **n** 个数依次为：第 **1** 个插入的数，第 **2** 个插入的数，…第 **n** 个插入的数。

### 输入格式 ###

第一行包含整数 **M**，表示操作次数。

接下来 **M** 行，每行包含一个操作命令，操作命令可能为以下几种：

(1) “H x”，表示向链表头插入一个数x。

(2) “D k”，表示删除第k个插入的数后面的数（当k为0时，表示删除头结点）。

(3) “I k x”，表示在第k个插入的数后面插入一个数x（此操作中k均大于0）。

### 输出格式 ###

共一行，将整个链表从头到尾输出。

### 数据范围 ###

**1 ≤ M ≤ 100000**  
所有操作保证合法。

### 输入样例 ###

> **10  
> H 9  
> I 1 1  
> D 1  
> D 0  
> H 6  
> I 3 6  
> I 4 5  
> I 4 5  
> I 3 4  
> D 6**

### 输出样例 ###

> **6 4 6 5**

## 解题代码 ##

#include<iostream>
    using namespace std;
    
    const int N = 1e5 + 10;
    int e[N], ne[N], head, idx;
    
    // 静态链表初始化
    void init() { 
        head = -1; // 初始条件下头指针指向尾结点
        idx = 0;   // idx 表示当前分配的内存空间
    }
    
    // 向链表头插入一个元素
    void addToHead(int x) { 
        e[idx] = x;
        ne[idx] = head;
        head = idx++;
    }
    
    void del(int k) { 
        if (!k) head = ne[head];
        ne[k - 1] = ne[ne[k - 1]];
    }
    
    void add(int k, int x) { 
        e[idx] = x;
        ne[idx] = ne[k - 1];
        ne[k - 1] = idx++;
    }
    
    int main() { 
        init();
        int n, x, k;
        char op;
        cin >> n;
        while (n--) { 
            cin >> op;
            if (op == 'H') { 
                cin >> x;
                addToHead(x);
            } else if (op == 'D') { 
                cin >> k;
                del(k);
            } else { 
                cin >> k >> x;
                add(k, x);
            }
        }
        for (int i = head; i != -1; i = ne[i]) cout << e[i] << " ";
        return 0;
    }

--------------------

> 未完待续，持续更新中……  
> ![20210217221853293.png][]

[Link 1]: https://ac-fun.blog.csdn.net/article/details/113819979
[https_ac-fun.blog.csdn.net]: https://ac-fun.blog.csdn.net/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNTc1NTA3_size_16_color_FFFFFF_t_70]: /images/20221024/79db9fbd0f774a9387c4c18a0e6a7d72.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNTc1NTA3_size_16_color_FFFFFF_t_70 1]: /images/20221024/2dd63725422e4197b1e235cab65797ca.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNTc1NTA3_size_16_color_FFFFFF_t_70 2]: /images/20221024/944b075eee424f74853b77b6242e6baa.png
[AcWing 826.]: https://www.acwing.com/problem/content/828/
[20210217221853293.png]: /images/20221024/09037650e538475588c6aa9dd1292379.png