算法模板之单链表图文讲解

2023-12-16 23:28:53

在这里插入图片描述
🌈个人主页:聆风吟
🔥系列专栏:算法模板数据结构
🔖少年有梦不应止于心动,更要付诸行动。


📋前言

????💬 hello! 各位铁子们大家好哇,今天作者给大家带来的是使用使用数组模拟单链表,让我们一起加油进步。
????📚 系列专栏:本期文章收录在《算法模板》,大家有兴趣可以浏览和关注,后面将会有更多精彩内容!
????🎉 欢迎大家关注🔍点赞👍收藏??留言📝



一. ??使用数组模拟单链表讲解

1.1 🔔为什么我们要使用数组去模拟单链表?

????假如你学过数据结构,那么你对链表的第一反应可能就是:由一系列结点组成,每个结点包含两个域,其中一个域用于存储数据元素,另一个域用于存储下一个结点的地址。节点的表示形式如下:

class Node{
public:
    int val;
    Node* next;
};

这种构造形式是我们常见的,使用该方法,在创建 一个值为 x 的新结点的时候,语法如下:

Node* node = new Node();
node->val = x

代码分析:Node* node = new Node();,中间有一个 new 关键字来为新对象分配空间。new 的底层涉及内存分配,调用构造函数,指针转换等多种复杂且费时的操作。由于一秒大概只能 new 一万次左右。在平时的工程代码中,不会涉及上万次的new操作,所以这种使用这种结构创建单链表是一种 见代码知意 的好结构。
????但是在算法比赛中,经常碰到在10w级别以上的链表操作,如果使用结构体这种方式创建链表,是无法在算法规定时间完成的。因此,在算法比赛这种有严格的时间要求的环境中,不能频繁使用new操作。所以在这里我们采用数组去模拟单链表


1.2 🔔用数组模拟实现单链表

1.2.1 👻整体框架说明

初始状态:将头指针head指向空结点。
在这里插入图片描述


插入结点状态:

  • 创建数组valne分别存储某个结点的值和指向下个结点的next指针;
  • 使用数组下表进行关联,通过数组ne将整个链表链接起来;
  • 空结点的下表用 - 1 来表示;

在这里插入图片描述


### 1.2.2 👻单链表查找和修改 因为是使用数组模拟出来的链表,所以对于查找和修改直接通过数组下标进行遍历查找即可,这里就不多叙述。

1.2.3 👻单链表插入结点

1. 头插:将 x 插入到头结点
在这里插入图片描述

代码展示(建议结合图示看注释):

//将x插到头结点
//idx 存储当前已经用到了哪个点,即记录当前下标位置
void add_to_head(int x)
{
    val[idx] = x;//记录要插入结点的数据
    ne[idx] = head;//将待插结点指向头结点
    head = idx;//断开头指针head指向的头结点的箭头,改为指向待插入结点
    idx++;//下标向后移一位,为下一次插入元素做准备。
}

2. 任意位置插入:将 x 插入到下标是k的结点后面
在这里插入图片描述

代码展示(建议结合图示看注释):

//将x插到下标是k的结点后面
//idx 存储当前已经用到了哪个点,即记录当前下标位置
void add(int k, int x)
{
    val[idx] = x;//记录要插入结点的数据
    ne[idx] = ne[k];//将待插结点指向下标为k结点的下个结点
    ne[k] = idx;//断开下标为k到k+1结点的箭头,将下标为k的结点改为指向待插入结点
    idx++;//下标向后移一位,为下一次插入元素做准备。
}

1.2.4 👻单链表删除结点

将下标为 k 的结点 后面的结点删掉
在这里插入图片描述

代码展示(建议结合图示看注释):

//将下标是k的点后面的点删掉
void remove(int k)
{
    ne[k] = ne[ne[k]];//让k指向的改为指向下下个结点,那中间的那个结点就被挤掉了。
}

1.3 🌟模板提取(重点)🌟

模板代码

// head 表示头结点的下标
// val[i] 表示结点i的值
// ne[i] 表示结点i的next指针是多少
// idx 存储当前已经用到了哪个点,即记录当前下标位置
int head, val[N], ne[N], idx;

//初始化
void init()
{
    head = -1;//将头指针head指向空结点。
    idx = 0;//下标置为0
}

//将 x 插入到头结点
void add_to_head(int x)
{
    val[idx] = x; 
    ne[idx] = head;
    head = idx;
    idx++;
}

//将 x 插入到下标是k的结点后面
void add(int k, int x)
{
    val[idx] = x;
    ne[idx] = ne[k];
    ne[k] = idx;
    idx++;
}

//将下标是k的点后面的点删掉
void remove(int k)
{
    ne[k] = ne[ne[k]];
}


二. ??题目练习

? 在线OJ链接,可以转至此处自行练习 ?

2.1 题目

在这里插入图片描述

2.2 输入样例

3
H ?9
I ??1 ?1
D??1

2.3 输出样例

9

2.4 c++代码

#include <iostream>

using namespace std;

const int N = 100010;
// head 表示头结点的下标
// val[i] 表示结点i的值
// ne[i] 表示结点i的next指针是多少
// idx 存储当前已经用到了哪个点,即记录当前下标位置
int head, val[N], ne[N], idx;

//初始化
void init()
{
    head = -1;
    idx = 0;
}

//将 x 插入到头结点
void add_to_head(int x)
{
    val[idx] = x; 
    ne[idx] = head;
    head = idx;
    idx++;
}

//将 x 插入到下标是k的结点后面
void add(int k, int x)
{
    val[idx] = x;
    ne[idx] = ne[k];
    ne[k] = idx;
    idx++;
}

//将下标是k的点后面的点删掉
void remove(int k)
{
    ne[k] = ne[ne[k]];
}


int main()
{
    int m;
    cin >> m;
    
    init();//切记:初始化
    
    while(m--)
    {
        int k, x;
        char op;
        
        cin >> op;
        //判断执行哪种操作
        if(op == 'H')
        {
            //执行头插操作
            cin >> x;
            add_to_head(x);
        }
        else if(op == 'D')
        {
            //执行删除操作
            cin >> k;
            if(k == 0) head = ne[head];//删除头节点
            remove(k - 1);//注意删除第k个输入后面的数,那函数里放的是下标,k要减去1
        }
        else
        {
            //执行指定位置插入操作
            cin >> k >> x;
            add(k - 1, x);
        }
    }
    
    for(int i = head; i != -1; i = ne[i]) cout << val[i] << " ";
    cout << endl;
    
    return 0;
}



📝结语

???? 今天的干货分享到这里就结束啦!如果觉得文章还可以的话,希望能给个三连支持一下,聆风吟的主页还有很多有趣的文章,欢迎小伙伴们前去点评,您的支持就是作者前进的最大动力!
在这里插入图片描述

文章来源:https://blog.csdn.net/2301_80026901/article/details/135038266
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。