C++数据结构算法篇Ⅰ

📟作者主页：慢热的陕西人

🌴专栏链接：C++算法

📣欢迎各位大佬👍点赞🔥关注🚓收藏，🍉留言

主要内容讲解数据结构中的链表结构

文章目录

C++数据结构算法篇Ⅰ
- Ⅰ. 链表
- - Ⅰ . Ⅰ 单链表
  - Ⅰ. Ⅱ 双链表

Ⅰ. 链表

Ⅰ . Ⅰ 单链表

在C++中我们用list来代替动态的链表，但是new()申请动态内存是非常缓慢的。所以我们在竞赛中一般采用数组的方式模拟实现一种静态的链表；

首先我们需要涉及到四个变量:

//e[idx]  --- 用来存储第idx个节点的值
//ne[idx] --- 用来存储第idx个节点的next指针
//idx     --- 用来表示当前指向的是第idx个节点
//head    --- 用来指向第一个节点

所以如下我们实现一个例题：

外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

代码：

#include<iostream>using namespace std;#define N 100010int e[N];
int ne[N];
int x;
int idx;
int head;
char op;
int k;void init()
{//我们规定最后一个空节点的地址为-1head = -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为tailr[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);
}