Algorithm11.1 数据结构 链表
[TOC]
数据结构 线性表 - 链表
1、STL库中的list，直接可以使用的链表
补：手写链表的基本结构以及名词区分：
基本结构就是指向第一个元素的指针（包含有第一个元素地址的变量）+后面一串的包含后序节点地址的节点
区分头指针、头节点、首元素节点
- 头指针就是存放第一个节点的地址的变量，无论第一个节点是头节点（用来填补回圈的）还是首元素节点，都是第一个节点的地址（也就是指向第一个节点）
- 头节点：一个存首元素节点地址的一个节点，这个节点的数据域没有实际意义，为了拼凑地址而存在
- 首元素节点：第一个存实际数值的节点
2、手写链表
- 单向链表
- 两个部分「数据域+指针域」+一个指针{记录链表第一个节点的地址}
- 单向链表双指针【主要用于用链接表模拟队列】
- 两个部分「数据域+指针域」+两个指针{记录链表第一个节点的地址front 和 记录链表最后一个节点的地址rear}
- 双向链表
- 三个部分「数据域+两个指针域」+两个指针{记录正方向链表的第一个节点的地址 和 记录反方向链表的第一个节点的地址}
- 循环链表
- 两个部分「数据域+指针域」+一个指针{记录链表第一个节点头节点的地址}+用于初始化回圈的头节点
- 注意：
- 需要用一个头节点组成回圈。
- 此时头指针初始化的位置是在循环链表的尾部，原因就是如果把它首尾相接的话，那么最后尾节点按理就是存放的首节点的地址，头指针就是指第一个节点的地址，所以头指针就相当于在尾节点的位置。
- 双向循环链表
- 三个部分「数据域+两个指针域」+两个指针{记录正方向链表的第一个节点的地址 和 记录反方向链表的第一个节点的地址}
队列排队问题 - 利用STL库中的链表进行实现
https://www.luogu.com.cn/problem/P1160
题目大意：在特定位置添加、插入成员，从而建立一个队列；然后通过调整相关的前后顺序位置，得到最后的队列
1、特定位置插入、前后顺序（相邻位置）调整 => 链表 // 双向链表
#include <iostream>
using namespace std;
#define maxn 100010
int n, m, idx, tp;
#include <list>
list<int> l;
using Iterator = list<int>::iterator;
Iterator pos[maxn]; // 用于存储索引关系
bool erased[maxn];
int main() {
// init
l.push_front(1);
pos[1] = l.begin();
scanf("%d", &n);
for (int i = 2; i <= n; ++i){
scanf("%d%d", &idx, &tp);
if (!tp) pos[i] = l.insert(pos[idx], i);
else {
auto ntiter = next(pos[idx]);
pos[i] = l.insert(ntiter, i);
}
}
scanf("%d", &m);
for (int i = 0; i < m; ++i) {
scanf("%d", &idx);
if (!erased[idx]) l.erase(pos[idx]);
erased[idx] = 1;
}
for (int x: l)
printf("%d ", x);
return 0;
}
队列问题 - 利用手写链表进行实现
手写链表之基本的链表操作 & 将链表封装成新的数据结构
1、链表单元：
struct node {
int num;
node *next;
}
2、链表的遍历：将bgnode给传入即可
node *nw = bgnode;
while(nw) {
/* 进行一定的操作或者记录 */
nw = nw->next;
}
3、链表基本操作之插入：
node *newnode = new node;
newnode->next = nw->next;
nw->next = newnode;
4、链表基本操作之删除 => 直接把它的下一个给隔过去就好。
nw->next = nw->next->next;
手写链表实现 树形结构之孩子兄弟表示法
1、链表单元：
struct node {
char a[maxn];
node *child, *bro;
}
2、几种树形结构的表示方式【双亲表示法】【孩子表示法】【孩子兄弟表示法】