文章目录
一、链表
1. 顺序表简介
1.1 静态顺序表
1.2 动态顺序表
2. 链表简介
3. 链表的构成
4. 数组与链表的区别
5. 链表分类
5.1 单链表
5.2 双链表
二、链表基础操作
1. 链表的创建
2. 链表的遍历
3. 链表的释放
4. 链表节点的查找
5. 链表节点的删除
6. 链表中插入一个节点
7. 链表的排序
8. 双向链表的创建和遍历
9. 双向链表插入节点
三、链表例题——单链表
题目描述
输入格式
输出格式
数据范围
输入样例
输出样例
具体实现
实现思路
实现代码
四、链表例题——双链表
题目描述
输入格式
输出格式
数据范围
输入样例
输出样例
具体实现
实现思路
实现代码
————————————————
一、链表
1. 顺序表简介
- 顺序表 是用一段物理地址连续的存储单元依次存储数据元素的线性结构（连续存储数据，不能跳跃）。
- 一般我们用数组存储顺序表，在数组上完成数据的增删查改。
1.1 静态顺序表
#define N 7 typedef int SLDateType; typedef struct SeqList { SLDateType array[N]; //定长数组 size_t size; //有效数据长度，size_t是无符号整形 }SeqList;
1.2 动态顺序表
typedef int SLDateType; typedef struct SeqList { SLDateType* array; //指向动态开辟的数组 size_t size; //数据中存储的数据 size_t capacity; //数组的容量 }SeqList;
2. 链表简介
链表和顺序表都是线性表的一种，但是链表的每个数据的存储是不连续的，要知道每个元素是怎么连接的那就要知道，在基本单位结构体中的分为两种数据分别是数据域和指针域，它是由每个基本单位结构体的指针域指向下一个位置的地址，从而将它们连接起来。
- 链表在内存空间中数据存储的位置的特点是分布离散的、随机的。它们像串珠子一样一个接一个的线性结构。
- 链表可以用 指针 + 结构体 的方式实现。
3. 链表的构成
- 头指针 ：头指针是指向链表第一个结点的的指针，如果有头结点那么头指针就是头结点的指针。
- 头结点 ：头结点是为了操作统一和方便而设立的，即放在第一个元素的结点之前，数据域一般没有意义(也可以放链表长度)。
- 数据域 ：存放各种实际的数据，如：num、score等。
- 指针域 ：存放下一节点的首地址，如：next等。
- 链表由一个个节点构成，每个节点一般采用结构体的形式组织。（每次 new 一个新的节点，会导致操作非常慢，在数据量较大时会导致超时问题）
typedef struct student ｛ int num； char name[20]； struct student *next； }STU;
因此，我们选择使用拿 数组模拟 链表。
4. 数组与链表的区别
- 链表是通过节点把离散的数据链接成一个表，通过对节点的插入和删除操作从而实现对数据的存取。
- 数组是通过开辟一段连续的内存来存储数据。
- 数组的每个成员对应链表的节点，成员和节点的数据类型可以是标准的 C 类型或者是用户自定义的结构体。
- 数组有起始地址和结束地址，而链表是一个圈，没有头和尾之分， 但是为了方便节点的插入和删除操作会人为的规定一个根节点。
5. 链表分类
5.1 单链表
- 单链表：由各个内存结构通过一个 next 指针链接在一起组成，每一个内存结构都存在后继内存结构（链尾除外），内存结构由数据域和 next 指针域组成。
- 单链表多为 邻接表 ，常用来存储树和图。
数据 + 指针，组成一个单链表的内存结构；第一个内存结构称为链头，最后一个内存结构称为链尾；链尾的 next 指针设置为 NULL [指向空]；单链表的遍历方向单一（只能从链头一直遍历到链尾）。
在数组当中，这里使用 e[N] 表示某个点值是多少，ne[N] 表示某个点的 next 指针是多少。e[N] 和 ne[N] 通过下标关联起来，具体可见下图（空节点用 -1 表示）
5.2 双链表
- 双链表常用来优化某些问题。
- 双向链表与单向链表的区别就是节点中有两个节点指针，分别指向前后两个节点。
- 在数组当中，可以使用 l[N] 作为节点左边的是什么，r[N] 作为节点右边的是什么。
- 双链表的插入和删除操作，只需写其中一边的，另一边可以通过调整函数调用参数进行转化操作。
二、链表基础操作
- 本文介绍基础操作不展示代码，因为可以实现该操作的代码有很多，只要掌握其主要操作步骤和思想即可，具体操作会在后面的例题当中展示。
1. 链表的创建
- 第一步：创建一个节点。
- 第二步：创建第二个节点，将其放在第一个节点的后面（第一的节点的指针域保存第二个节点的地址）。
第三步：再次创建节点，找到原本链表中的最后一个节点，接着讲最后一个节点的指针域保存新节点的地址，依此类推。
2. 链表的遍历
- 第一步：输出第一个节点的数据域，输出完毕后，让指针保存后一个节点的地址。
- 第二步：输出移动地址对应的节点的数据域，输出完毕后，指针继续后移 。
- 第三步：依此类推，直到节点的指针域为 NULL 。
3. 链表的释放
- 定义一个新指针，保存原指向节点的地址，然后原指针后移保存下一个节点的地址，然后释放新指针对应的节点，依此类推，直到原指针为 NULL 为止。
4. 链表节点的查找
- 先对比第一个节点的数据域是否是想要的数据，如果是就直接返回，如果不是则继续查找下一个节点，如果到达最后一个节点的时候都没有匹配的数据，说明要查找数据不存在。
5. 链表节点的删除
- 如果链表为空，则不需要删除。
- 如果删除的是第一个节点，则需要将保存链表首地址的指针保存第一个节点的下一个节点的地址。
- 如果删除的是中间节点，则找到中间节点的前一个节点，让前一个节点的指针域保存这个节点的后一个节点的地址即可
6. 链表中插入一个节点
链表中插入一个节点，按照原本链表的顺序插入，找到合适的位置。
情况（按照从小到大）：
（1） 如果链表没有节点，则新插入的就是第一个节点。
（2） 如果新插入的节点的数值最小，则作为头节点。
（3） 如果新插入的节点的数值在中间位置，则找到前一个，然后插入到他们中间。
（4） 如果新插入的节点的数值最大，则插入到最后。
7. 链表的排序
- 如果链表为空或者只有一个节点，则不需要排序。
- 先将第一个节点与后面所有的节点依次对比数据域，只要有比第一个节点数据域小的，则交换位置。
- 交换之后，拿新的第一个节点的数据域与下一个节点再次对比，如果比他小，再次交换，依此类推。
- 第一个节点确定完毕之后，接下来再将第二个节点与后面所有的节点对比，直到最后一个节点也对比完毕为止。
8. 双向链表的创建和遍历
- 第一步：创建一个节点作为头节点，将两个指针域都保存 NULL 。
- 第二步：先找到链表中的最后一个节点，然后让最后一个节点的指针域保存新插入节点的地址，新插入节点的两个指针域，一个保存上一个节点的地址，一个保存 NULL 。
9. 双向链表插入节点
- 只需编写一边插入代码，另一边可以通过调整自定义函数的参数进行插入。
三、链表例题——单链表
题目描述
实现一个单链表，链表初始为空，支持三种操作：
- 向链表头插入一个数；
- 删除第 k 个插入的数后面的数；
- 在第 k 个插入的数后插入一个数。
现在要对该链表进行 M 次操作，进行完所有操作后，从头到尾输出整个链表。
注意:题目中第 k 个插入的数并不是指当前链表的第 k 个数。例如操作过程中一共插入了 n 个数，则按照插入的时间顺序，这 n 个数依次为：第 1 个插入的数，第 2 个插入的数，…第 n 个插入的数。
输入格式
第一行包含整数 M，表示操作次数。
接下来 M 行，每行包含一个操作命令，操作命令可能为以下几种：
- H x，表示向链表头插入一个数 x。
- D k，表示删除第 k 个插入的数后面的数（当 k 为 0 时，表示删除头结点）。
- I k x，表示在第 k 个插入的数后面插入一个数 x（此操作中 k 均大于 0）
输出格式
共一行，将整个链表从头到尾输出。
数据范围
1 ≤ M ≤ 100000
所有操作保证合法。
输入样例
10
H 9
I 1 1
D 1
D 0
H 6
I 3 6
I 4 5
I 4 5
I 3 4
D 6
输出样例
6 4 6 5
具体实现
实现思路
- （1） 链表初始化，头节点指向空集，即为 -1 ，idx 当前存储点为 0 。
- head 最开始的时候，链表的头节点要指向 -1 ，为的就是在后面进行不断操作后仍然可以知道链表是在什么时候结束。
head 最开始的时候，负责指向空结点，在链表里有元素的时候，它变成了一个指向第一个元素的指针，当它在初始化的时候指向-1，来表示链表离没有内容。
idx 在链表进行各种插入，删除等操作的时候，作为一个临时的辅助性的所要操作的元素的下标来帮助操作，并且是在每一次插入操作的时候，给插入元素一个下标。
void init() // 链表的初始化 { head=-1; idx=0; }
- 2） 实现操作 H x：x 插到头节点 。
- 将 idx 位置的 e[] 数组存储元素为 x 。
- 将元素 x 的指针指向 head 原本指向的。
- head 选择表示指向第一个元素。
- idx 指针向后移动一位，为下一次插入元素做准备
void add_to_head(int x) // 将x插到头节点 { e[idx] = x; ne[idx] = head; head = idx; idx++; }
- （3） 实现操作 D k：将下标是 k 的点后面的点删掉。
- 让 k 的指针指向，k下一个元素的下一个元素，那么中间的元素就被去掉了。
void remove(int k) // 将下标是k的点后面的点删掉 { ne[k] = ne[ne[k]]; }
- （4） 实现操作 I k x：将 x 插到下标是 k 的点后面。
- 将 idx 位置的 e[] 数组存储元素为 x 。
- 将元素 x 的指针，指向他要占位的元素原本指向的位置。
- 让被占位元素的指针指向元素 x 的位置。
- idx 指针向后移动一位，为下一次插入元素做准备。
void add(int k, int x) // 将x插到下标是k的点后面 { e[idx]=x; ne[idx]=ne[k]; ne[k]=idx; idx++; }
实现代码
#include#include <bits/stdc++.h> using namespace std; const int N=100010; int head,idx,e[N],ne[N]; // head 表示头节点的下标 // e[N] 表示节点 i 的位置 // ne[N] 表示节点 i 的 next 指针是多少 // idx 存储当前已经用到了哪个点 void init() // 链表的初始化 { head=-1; idx=0; } void add_to_head(int x) // 将x插到头节点 { e[idx] = x; ne[idx] = head; head = idx; idx++; } void add(int k, int x) // 将x插到下标是k的点后面 { e[idx]=x; ne[idx]=ne[k]; ne[k]=idx; idx++; } void remove(int k) // 将下标是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) { head = ne[head]; } else { 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; system("pause"); return 0; }
