算法竞赛系列 | 链表

清华计算机学堂 2023-03-13

347

本文适合初级和中级学习：刚学过编程语言，正在学数据结构的编程新手；学过基础数据结构，但是对代码的掌握还不够熟练的读者。

PS: 与普通计算机教材相比，本书代码的写法很不一样，似乎不太正式，而是非常简洁。这是因为本书的主要读者是算法竞赛选手，他们在竞赛时需要简化代码、加快编码速度、把注意力放在算法实现上。例如使用一个大数组，普通教材的常见做法是动态分配一个空间，使用完后释放。而本书的代码省略了分配和释放，直接定义一个全局的静态大数组，例如int a[1000000]。

链表的特点是用一组位于任意位置的存储单元存线性表的数据元素，这组存储单元可以是连续的，也可以不连续。链表是容易理解和操作的基本数据结构，它的操作有初始化、添加、遍历、插入、删除、查找、排序、释放等。有单向链表和双向链表，如图1.1所示，上面是单向链表，下面是双向链表。

■ 图1.1 单向链表和双向链表

链表的各结点首尾相接，最后的next指针指向第一个data，第一个的pre指针指向最后的data。单向链表只有一个遍历方向，双向链表有两个方向，比单向链表的访问方便一点，也快一点。在需要频繁访问前后几个结点的场合，可以使用双向链表。

使用链表时，可以直接用STL list，也可以自己写链表。如果自己写代码实现链表，有两种编码实现方法：动态链表、静态链表。在算法竞赛中为加快编码速度，一般用静态链表或者STL list。

下面以“例1-1. 洛谷P1996”为例题，在后面3个小节中分别给出动态链表、静态链表、STL链表等3种方案、5种代码。经过作者的精心整理，这5种代码的逻辑和流程完全一样，只有链表的实现不一样，方便读者学习，把关注点放在链表的实现上。

● 例1-1. 约瑟夫问题洛谷P1996

题目描述：n个人，编号为1~n，按顺序围成一圈，从第一个人开始报数，数到 m 的人出列，再由下一个人重新从 1 开始报数，数到 m 的人再出圈，依次类推，直到所有的人都出圈，请依次输出出圈人的编号。

输入：一行，2个整数n、m。

输出：一行n个整数，按顺序输出每个出圈人的编号。1 ≤ m, n ≤ 100。

输入样例：

10 3

输出样例：

3 6 9 2 7 1 8 5 10 4

动态链表

动态链表需要临时分配链表结点、使用完毕后释放链表结点。优点是能及时释放空间，不使用多余内存；缺点是需要管理空间，容易出错。动态链表是“教科书式”的标准做法。

下面的代码用动态单向链表实现了例1.1。

#include <bits/stdc++.h>
struct node{                            //定义链表结点
    int data;                           //结点的值
    node *next;                         //单向链表，只有一个next指针
};
int main(){
    int n,m;   scanf("%d %d",&n,&m);
    node *head,*p,*now,*prev;           //定义变量
    head = new node; head->data = 1; head->next=NULL; //分配第一个结点，数据置为1        
    now = head;                         //当前指针是头
    for(int i=2;i<=n;i++){
        p = new node;  p->data = i; p->next = NULL;  //p是新结点
        now->next = p;                  //把申请的新结点连到前面的链表上
        now = p;                        //尾指针后移一个
    }    
    now->next = head;                   //尾指针指向头：循环链表建立完成
//以上是建立链表，下面是本题的逻辑和流程。后面4种代码，逻辑流程完全一致。
    now = head, prev = head;            //从第1个开始数
    while((n--) >1 ){ 
        for(int i=1;i<m;i++){           //数到m，停下
            prev = now;                 //记录上一个位置，用于下面跳过第m个结点
            now = now->next; 
        }
        printf("%d ", now->data);       //输出第m结点，带空格
        prev->next = now->next;         //跳过这个结点
        delete now;                     //释放结点
        now = prev->next;               //新的一轮        
    }
    printf("%d", now->data);            //打印最后一个，后面不带空格
    delete now;                         //释放最后一个结点
    return 0;
}

静态链表

提示/

动态链表虽然“标准”，但是竞赛中一般不用。算法竞赛对内存管理要求不严格，为加快编码速度，一般就在题目允许的存储空间内静态分配，省去了动态分配和释放的麻烦。

静态链表使用预先分配的一段连续空间存储链表。从物理存储的意义上讲，“连续空间”并不符合链表的本义，因为链表的优点就是能克服连续存储的弊端。但是，用连续空间实现的链表，在逻辑上是成立的。具体有两种做法：

①定义链表结构体数组，和动态链表的结构差不多；

②使用一维数组，直接在数组上进行链表操作。

本节给出3段代码：用结构体数组实现单向静态链表、用结构体数组实现双向静态链表、用一维数组实现单向静态链表。

1. 用结构体数组实现单向静态链表

用结构体数组实现单向静态链表，注意静态分配应该定义在全局，不能定义在函数内部。

//洛谷P1996，结构体数组实现单向静态链表
#include <bits/stdc++.h>                 
const int N = 105;                       //定义静态链表的空间大小
struct node{                             //单向链表
    int id, nextid;                      //单向指针
  //int data;                            如有必要，定义一个有意义的数据    
}nodes[N];                               //定义在全局的静态分配
int main(){
    int n, m;       scanf("%d%d", &n, &m);
    nodes[0].nextid = 1;
    for(int i=1;i<=n;i++){ nodes[i].id=i; nodes[i].nextid=i+1;}
    nodes[n].nextid = 1;                 //循环链表：尾指向头
    int now = 1, prev = 1;               //从第1个开始
    while((n--) >1){
        for(int i=1;i<m;i++){ prev = now; now = nodes[now].nextid;} //数到m停下            
        printf("%d ", nodes[now].id);    //带空格打印
        nodes[prev].nextid = nodes[now].nextid;    //跳过结点now，即删除now
        now = nodes[prev].nextid;        //新的now
    }    
    printf("%d", nodes[now].nextid);     //打印最后一个，后面不带空格
    return 0; 
}

2. 用结构体数组实现双向静态链表

//洛谷P1996，结构体数组实现双向静态链表
#include <bits/stdc++.h>
const int N = 105;
struct node{                          //双向链表
    int id;                           //结点编号
  //int data;                         如有必要，定义一个有意义的数据
    int preid, nextid;                //前一个结点，后一个结点
}nodes[N];
int main(){
    int n, m;    scanf("%d%d", &n, &m);
    nodes[0].nextid = 1;
    for(int i = 1; i <= n; i++){       //建立链表
        nodes[i].id = i;
        nodes[i].preid = i-1;          //前结点
        nodes[i].nextid = i+1;         //后结点
    }
    nodes[n].nextid = 1;               //循环链表：尾指向头
    nodes[1].preid = n;                //循环链表：头指向尾
    int now = 1;                       //从第1个开始
    while((n--) >1){
        for(int i=1;i<m;i++)  now = nodes[now].nextid;    //数到m，停下            
        printf("%d ", nodes[now].id);  //打印，后面带空格
        int prev = nodes[now].preid,  next = nodes[now].nextid;
        nodes[prev].nextid = nodes[now].nextid;  //删除now
        nodes[next].preid = nodes[now].preid;   
        now = next;                    //新的开始
    }    
    printf("%d", nodes[now].nextid);   //打印最后一个，后面不带空格
    return 0; 
}

3. 用一维数组实现单向静态链表

这是最简单的实现方法。定义一个一维数组nodes［］，nodes［i］的i就是节点的值，而nodes［i］的值是下一个节点。它的使用环境很有限，因为它的节点只能存一个数据，就是i。

//洛谷P1996，一维数组实现单向静态链表
#include<bits/stdc++.h>
int nodes[150];
int main(){   
    int n, m;    scanf("%d%d", &n, &m); 
    for(int i=1;i<=n-1;i++)  nodes[i]=i+1; //nodes[i]的值就是下一个结点        
    nodes[n] = 1;                          //循环链表：尾指向头
    int now = 1, prev = 1;                 //从第1个开始
    while((n--) >1){
        for(int i = 1; i < m; i++){   //数到m，停下
            prev = now;   now = nodes[now];    //下一个
        }
        printf("%d ", now);           //带空格
        nodes[prev] = nodes[now];     //跳过结点now，即删除now
        now = nodes[prev];            //新的now
    }    
    printf("%d", now);                //打印最后一个，不带空格
    return 0;
}

STL list

在算法竞赛或工程项目中常常使用C++ STL list。list 是双向链表，由标准模板库(Standard Template Library,STL)管理，通过指针访问节点数据，高效率地删除和插入。请读者自己熟悉list的初始化、插入、删除、遍历、查找、释放。下面是用list实现例1.1的代码。

//洛谷P1996，STL list
#include <bits/stdc++.h>
using namespace std;
int main(){
    int n, m;    cin>>n>>m;
    list<int>node;
    for(int i=1;i<=n;i++) node.push_back(i);   //建立链表             
    list<int>::iterator it = node.begin();
    while(node.size()>1){                      //list的大小由STL自己管理
        for(int i=1;i<m;i++){                  //数到m
             it++;
             if(it == node.end()) it = node.begin();  //循环：到末尾了再回头                                                              
        }
        cout << *it <<" ";
        list<int>::iterator next = ++it;
        if(next==node.end())  next=node.begin();  //循环链表
        node.erase(--it);                         //删除这个结点，node.size()自动减1
        it = next;
    }
    cout << *it;
    return 0;
 }