《算法竞赛》第一章 基础数据结构 1.1链表

链表是什么

链表一般用于存储一组存在链性关系的数据，如下图是一幅单向循环链表的示意图：
其中粉色框内的是元素编号，data表示当前位置的数据内容，next指向当前位置的下一个数据。

相信看了这张图就已经理解很多内容了，链表确实是一个很容易理解和操作的基本数据结构。

使用链表

链表的分类：

静态/动态、手写/STL、双向/单向、循环/不循环链表，一般都是用前者，更方便编码，所以下文中一般只给出最方便编码的手写静态链表代码。

链表的操作：

链表一般有初始化、插入、添加、删除、查找、释放等操作，分为单向链表和双向链表，绝大部分是循环链表，即首尾相连。

下面以例1.1为例，给出手写静态双向循环链表的示例代码以理解。

例1.1 约瑟夫问题（洛谷P1996）
有n个人，按顺序编号为1~n并围成一圈，从第一个人开始报数，数到m的人出列，然后下一个人又从1开始报数，以此类推，依次输出出列人的编号。
输入：两个整数n和m，含义如题所示，$1<=m,n<=100$。
输出：n个整数，按顺序输出每个出列人编号。
输入样例：10 3
输出样例：3 6 9 2 7 1 8 5 10 4

这道题很明显是一道双向循环链表模板题，从题目中很容易看出每个点只和上一个点和下一个点有关系，并且是一个环，首尾相连。

例1.1 AC代码

#include<cstdio>

using namespace std;

const int maxn = 105;

struct Node {
    int prev, next;                        //前驱, 后驱
} node[maxn];

int n, m;
void input() {
    scanf("%d %d", &n, &m);
}

void init() {                            //初始化链表
    for (int i = 1; i <= n; ++i) {        //每个点链接下一个点和上一个点
        node[i].next = i + 1;
        node[i].prev = i - 1;
    }
    node[0].next = 1;                    //从一个虚拟的点（不在环中）进入环，因为根据题意最开始数第一个点也算一个点
    node[1].prev = n;                    //特殊处理第一个点的上一个点
    node[n].next = 1;                    //特殊处理最后一个点的下一个点
}

void del_Node(int num) {                //删除点 num
    node[node[num].next].prev = node[num].prev;
    node[node[num].prev].next = node[num].next;
}

int p;                                    //维护当前数到的位置
void sol() {
    while (n--) {                        //一共要让 n 个人出列
        for (int i = 1; i <= m; ++i) {  //数 m 次
            p = node[p].next;           //p 指向下一个人
        }
        printf("%d ", p);               //输出要出列的 p
        del_Node(p);                    //让 p 出列
    }
}

int main() {
    input();
    init();
    sol();
    return 0;
}

这道题能大致熟悉链表的基本使用方式————删除 & 插入，下面给出图解。

删除

将与要删除的点相邻的两个点next和prev跳过要删除的点直接指向后一个点，让要删除的点无法通过其它点走到，这样就实现了删除点的目的。

插入

• 先将删除的操作步骤倒过来，将与它相邻的两个点的next和prev指向它就实现了从前后都能访问到这个点的目的。
• 然后再将这个点的next和prev指向相邻的两个点，实现从这个点访问到相邻的两个点。