模拟单链表


一、前言

在很久之前的博客sheepice已经有过对于链表的相关介绍,而当时那篇文章的访问量也比较大,说明还是对大家有一定的帮助,那么这篇文章将继续对链表进行一个介绍,而本次所记录的是单链表的数组模拟,其实就是采用了一个虚表头的做法。

为什么要用数组进行模拟呢,主要有以下几点:

  • 我们能够更好的理解单链表的存储方式。
  • 能够巩固之前对于一般利用结构体构建链表的理解。
  • 由于数组模拟的单链表能够实现用结构体模拟的链表的一切操作,但是在一些算法题上用数组进行模拟能够更快的跑出程序。
  • 也可以为之后即将总结一些图论的邻接表的构建打下一定的基础。

二、基本操作

①初始化操作

初始化的操作主要进行下面几点:

  • 头结点指向空(我们用-1代表空节点)
  • 当前节点idx为0(代表我们没有用一个节点进行操作)
  • 定义一些数组,存储当前节点和下一个节点的信息

代码如下:

const int N = 100050 //根据题目给的数据去定义一个N
int e[N];   //这个数组代表某个节点所存下的值
int ne[N];  //这个数组代表某个节点的下一个节点位置,相当于next指针

void init() {
    head = -1, idx = 0;
}

②向头节点插入一个元素

大家可以看一下上面的图,如果要在整个链表最左边插入一个值,我们只需要四步走

  • 存下当前节点值val
  • 存下当前节点的下一个节点值,也就是头指针指向的值
  • 让头指针指向新进来的值
  • idx++ 代表我们已经处理完了一个点,下一个节点的坐标需要比这个点多1。刚开始学的时候这个地方不太清楚,其实主要知道,每个节点都是独一无二的,idx无非只是控制这个节点的下标为多少。

代码如下:

void add_to_head(int x)
{
    e[idx] = x;
    ne[idx] = head;
    head = idx;
    idx ++ ;
}

③删除第k个节点后面的一个数

这个操作其实比较的简单,我们只需要让第k个节点的next指针指向它下一个节点的下一个节点。

代码如下:

//删除下标为k的后面一个数(D k)
void remove(int k)
{
    ne[k] = ne[ne[k]];
}

④在一个节点后面新加上一个值

这个操作和基本链表一样,也是四步走

  • 构建新节点记下存下的值
  • 新节点的next指针指向某节点指向的值
  • 某节点指向新的节点
  • idx++ 代表要处理后续的节点

代码如下:

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

⑤输出链表

上面的四个步骤已经包含了绝大部分链表的操作了,那最后就是如何把我们的链表进行输出呢?其实就是我们先让一个指针指向head头指针指向的地方,依次利用ne数组,去探索后续的节点,知道指针指向空节点(也就是值等于我们最初初始化的-1)

可能用文字描述不太能理解,我们可以看下面的图解,大家也可以跟着图慢慢的走,一定能够发现其中的逻辑。

上面的这个图便是模拟了插入两次头节点,然后在中间插入后,最终我们的一个红色线路就是我们的输出线路,而完成这个链表的输出。其实就是下面图中的代码!

代码如下:

for(int i = head; i != -1; i = ne[i]) cout << e[i] << " ";
    return 0;

三、题目分享

上述的所有操作就可以完成一个基本模拟单链表的题目,题目如下:

完整AC代码如下:

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 100010;

//idx表示节点
//head表示头结点
//e表示当前下标点的值
//ne表示当前下标点的下一个下标的位置
int idx = 0, head = -1;
int e[N], ne[N];

//将值为x插入到头节点的位置(H x)
void add_to_head(int x)
{
    e[idx] = x;
    ne[idx] = head;
    head = idx;
    idx ++ ;
}

//删除下标为k的后面一个数(D k)
void remove(int k)
{
    ne[k] = ne[ne[k]];
}

//在下标为k的数的后面插入一个数x(I k x)
void add(int k, int x)
{
    e[idx] = x;
    ne[idx] = ne[k];
    ne[k] = idx;
    idx ++ ;
}

int main()
{
    int n;
    cin >> n;
    while (n -- ) 
    {
        char op;
        cin >> op;
        if(op == 'H')
        {
            int x;
            cin >> x;
            add_to_head(x);
        }
        else if(op == 'D')
        {
            int k;
            cin >> k;
            if(k == 0) head = ne[head];
            remove(k - 1);
        }
        else
        {
            int x, k;
            cin >> k >> x;
            add(k - 1, x);
        }
    }
    for(int i = head; i != -1; i = ne[i]) cout << e[i] << " ";
    return 0;
}


作者:sheepice
链接:https://www.acwing.com/activity/content/code/content/3676581/
来源:AcWing
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

文章作者: sheepice
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 sheepice !
  目录