C++数据结构算法篇Ⅰ
📟作者主页：慢热的陕西人
🌴专栏链接：C++算法
📣欢迎各位大佬👍点赞🔥关注🚓收藏，🍉留言
主要内容讲解数据结构中的链表结构
Ⅰ. 链表
Ⅰ . Ⅰ 单链表
在C++中我们用
list来代替动态的链表，但是new()申请动态内存是非常缓慢的。所以我们在竞赛中一般采用数组的方式模拟实现一种静态的链表；首先我们需要涉及到四个变量:
//e[idx] --- 用来存储第idx个节点的值 //ne[idx] --- 用来存储第idx个节点的next指针 //idx --- 用来表示当前指向的是第idx个节点 //head --- 用来指向第一个节点
所以如下我们实现一个例题：
代码：
#include<iostream> using namespace std; #define N 100010 int e[N]; int ne[N]; int x; int idx; int head; char op; int k; void init() { //我们规定最后一个空节点的地址为-1 head = -1; idx = 0; } void add_to_head(int x) { e[idx] = x; ne[idx] = head; head = idx++; } void add(int k, int x) { e[idx] = x; ne[idx] = ne[k]; ne[k] = idx++; } void remove(int k) { ne[k] = ne[ne[k]]; } int main() { int m; cin >> m; init(); while (m--) { cin >> op; if (op == 'H') { cin >> x; add_to_head(x); } else if (op == 'D') { cin >> k; if (!k) head = ne[head]; remove(k - 1); } else { cin >> k >> x; add(k - 1, x); } } for (int i = head; i != -1; i = ne[i]) cout << e[i] << " "; cout << endl; return 0; }
Ⅰ. Ⅱ 双链表
双链表的实现方式类似，不过变量的参数有所变化
//l[idx] ---表示的是第idx个节点的左节点的地址 //r[idx] ---表示的是第idx个节点的有节点的地址 //e[idx] ---存储的是第idx个节点的值 //head ---存储的是头节点的地址 //tial ---存储的是尾节点的地址
int idx, e[N], l[N], r[N]; int m, tail, head; void init() { //起始规定0为head,1为tail r[0] = 1, l[1] = 0; idx = 2; head = 0, tail = 1; } //在下标为k的右边插入x void addr(int k, int x) { e[idx] = x; r[idx] = r[k]; l[idx] = k; r[k] = idx; l[r[k]] = idx; if (k == tail) tail = idx; idx++; } //在下标为k的左边插入x void addl(int k, int x) { addr(l[k], x); if (k == head) head = idx; } //删除第k个点 void remove(int k) { r[l[k]] = r[k]; l[r[k]] = l[k]; } //最右侧插入一个数 void addt(int x) { addr(tail, x); } //最左侧插入一个数 void addh(int x) { addl(head, x); }
到这本篇博客的内容就到此结束了。
如果觉得本篇博客内容对你有所帮助的话，可以点赞，收藏，顺便关注一下！
如果文章内容有错误，欢迎在评论区指正
