链表与邻接表

【一般实现方式：指针+结构体——动态链表（工程中常用）】

1
2
3
4
5
6
7

struct Node
{
	int val;
    Node *next;
}

new Node(); // 非常慢，若要使用可以初始化n个节点

这里介绍用数组模拟【静态链表】该数据结构的方式——速度快！

单链表

单链表中用的最多的是邻接表——n个单链表：将每个点（共有n个点）的所有邻边存下来

邻接表应用：存储图和树（e.g. 最短路问题、最小生成树问题、……）

单链表基本结构：从头指针开始依次指向若干个节点，每个节点存储一个数值val和一个next指针，沿着next指针不断访问后续数据，直到指向空指针

数组模拟链表存储需要定义（均为整数型数组）：

• e[N]：存储各点数值val
• ne[N]：存储各点next指针——空节点下标用-1表示

二者通过下标关联 ：

事实上，同一下标i对应的e[i]与ne[i]表示一个节点的数值val及其next指针，将其看作一个结构体会更好理解，但在代码实现过程中，为使得代码尽量简洁，选择直接对数组下标进行操作

1
2
3
4
5
6
7
8
9
10
11
12

// 结构体写法
struct Node
{
    int e, ne;
}nodes[N];

// 以删除为例：删除下标是k的节点“后面”的一个节点
void remove(int k)
{
    // 直接让k节点指向的节点变成其后的节点指向的节点
    nodes[k].ne = nodes[nodes[k].ne].ne;   
}

需要注意：一个下标代表一个节点，各节点之间的指向关系仅由next指针（即ne[i]的值）决定

单链表的性质：顺序（单向）访问——可以在O(1)的时间复杂度内找到指定节点的后一个节点（包括完成插入等操作），但如果要找到指定节点之前的节点，则只能从头指针head开始遍历

例题：826. 单链表 - AcWing题库

实现一个单链表，链表初始为空，支持三种操作：

1. 向链表头插入一个数；
2. 删除第 k 个插入的数后面的一个数；
3. 在第 k 个插入的数后插入一个数。

现在要对该链表进行 M 次操作，进行完所有操作后，从头到尾输出整个链表。

注意:题目中第 k 个插入的数并不是指当前链表的第 k 个数。例如操作过程中一共插入了 n 个数，则按照插入的时间顺序，这 n 个数依次为：第 1 个插入的数，第 2 个插入的数，…第 n 个插入的数。

输入格式

第一行包含整数 M，表示操作次数。

接下来 M 行，每行包含一个操作命令，操作命令可能为以下几种：

排序

快速排序

主要思想：分治

时间复杂度：O(n*log{2}{n})【平均时间复杂度，最快可以达到n^2】

e.g. 对数组q的序号l至r区域进行排序

1. 确定分界点x（数值）：常用——左边界q[l]、**中心点处值q[(l+r)/2]**、右边界q[r]、随机
2. 调整区间：使所有小于（等于）x的值均位于x左侧，所有大于（等于）x的值都位于x右侧（区间内不要求有序）
   • 暴力做法（时间复杂度仍为O(n)，但会额外耗费空间）：
     1. 新开两个数组a[]，b[]
     2. 对数组q的序号l至r区间进行扫描：
        • 若q[i]≤x，将q[i]放入a[]
        • 若q[i]≥x，将q[i]放入b[]
     3. 将a[]、b[]依次放回q[]中
   • 推荐做法（使用指针）：
     1. 从左边界q[l]处开始，使用指针i向右侧移动，若指针指向的数值大于等于x，停下
     2. 从右边界q[r]处开始，使用指针j向左侧移动，若指针指向的数值小于等于x，停下
     3. 交换指针i、j处的数值
     4. 重复1、2、3步骤（在移动后的指针i、j位置基础上继续向右/左侧移动），直到两个指针相遇
3. 递归处理左右两段

例题：785. 快速排序 - AcWing题库

给定一个长度为 n 的整数数列。

请你使用快速排序对这个数列按照从小到大进行排序。

并将排好序的数列按顺序输出。

输入格式

输入共两行，第一行包含整数 n。

第二行包含 n 个整数（所有整数均在 1∼10^9范围内），表示整个数列。

输出格式

输出共一行，包含 n 个整数，表示排好序的数列。

数据范围

1≤n≤100000

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

#include <iostream>

using namespace std;

const int N = 100010; // 保险，防止边界问题

int n;
int q[N];

void quick_sort(int q[], int l, int r)
{
    //判定边界：区间内只有一个数或没有数时不需要排序
    if (l >= r)
        return;
    
    int x = q[(l + r) / 2], i = l - 1, j = r + 1; //取分界值
    //注意：由于每次完成交换（包括初始状态）都自动向中间移动一格，初始时要将两侧指针取在区间外侧1个单位
    while (i < j) //迭代：移动+交换
    {
        do
            i ++ ;
        while (q[i] < x);
        do
            j -- ;
        while (q[j] > x);
        if (i < j)
        {
            //交换两数:swap(q[i], q[j]);
            int t = q[i];
            q[i] = q[j];
            q[j] = t;
        }
    }
    
    quick_sort(q, l, j);
    quick_sort(q, j + 1, r);
}

int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; i ++ )
        scanf("%d", &q[i]);
    
    quick_sort(q, 0, n-1);
    
    for (int i = 0; i < n; i ++ )
        printf("%d ", q[i]);
    
    return 0;
}

归并排序

主要思想：分治

时间复杂度：O(n*log{2}{n})

• 时间复杂度计算：每次递归将当前序列分为2份（原序列->2份->4份->8份->……），直到每一份的长度为1时停止；显然这样的递归需要进行log{2}{n}轮，而对于每一轮而言又需要进行时间复杂度为O(n)的归并，因此整体排序算法的时间复杂度为两者相乘，即O(n*log{2}{n})

e.g. 对数组q的序号l至r区域进行排序

1. 确定分界点：以数组中心点mid = (l+r)/2为分界点，将数组q分成Left、Right两部分
2. 对两部分进行递归排序，使其各自成为有序序列
3. 归并：将两个有序数组合并成一个有序数组
   • 双指针算法（时间复杂度为O(n)）：
     1. 对于两个有序数组Left、Right而言，分别在其左端点处放置一个指针
     2. 比较两个数组指针处数值的大小，将更小的那一个放入输出的目标数组（初始为空）
        • 注意：若两个数组指针处数值大小相等，则优先将数组Left中的数值放入输出目标数组，则可保证排序算法的稳定
        • 排序算法的稳定：排序完成后，原数组中值相同的数之间的相对位置不变（归并排序稳定，快速排序不稳定；若想使快速排序稳定，需要在对数值排序的基础上对各元素在原数组中的位置序号进行排序）
     3. 对于更小的数值所在的数组而言，将指针向后移一位，重复步骤2（依次排入输出目标数组中）
     4. 重复步骤3，直到某个数组中所有的数全部被放入输出目标数组，则跳出循环，将另一个数组的所有剩余数值依次排入输出目标数组中，归并完成