网站建设与网页设计的区别,ppth5怎么制作,做网站用的服务器,商城app开发多少钱#x1f308;个人主页#xff1a;聆风吟 #x1f525;系列专栏#xff1a;算法模板、数据结构 #x1f516;少年有梦不应止于心动#xff0c;更要付诸行动。 文章目录 #x1f4cb;前言一. ⛳️使用数组模拟单链表讲解1.1 #x1f514;为什么我们要使用数组去模拟单链表… 个人主页聆风吟 系列专栏算法模板、数据结构 少年有梦不应止于心动更要付诸行动。 文章目录 前言一. ⛳️使用数组模拟单链表讲解1.1 为什么我们要使用数组去模拟单链表1.2 用数组模拟实现单链表1.2.1 整体框架说明1.2.3 单链表插入结点1.2.4 单链表删除结点 1.3 模板提取(重点) 二. ⛳️题目练习2.1 题目2.2 输入样例2.3 输出样例2.4 c代码 结语 前言 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指向空结点。 插入结点状态
创建数组val和ne分别存储某个结点的值和指向下个结点的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到k1结点的箭头将下标为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 iostreamusing 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;
} 结语 今天的干货分享到这里就结束啦如果觉得文章还可以的话希望能给个三连支持一下聆风吟的主页还有很多有趣的文章欢迎小伙伴们前去点评您的支持就是作者前进的最大动力
