链表的特点是用一组位于任意位置的存储单元存线性表的数据元素，这组存储单元可以是连续的，也可以不连续。链表是容易理解和操作的基本数据结构，它的操作有初始化、添加、遍历、插入、删除、查找、排序、释放等。有单向链表和双向链表，如图 1 所示，上面是单向链表，下面是双向链表。
■ 图 1 单向链表和双向链表
链表的各结点首尾相接，最后的 next 指针指向第一个 data，第一个的 pre 指针指向最后的 data。单向链表只有一个遍历方向，双向链表有两个方向，比单向链表的访问方便一点，也快一点。在需要频繁访问前后几个结点的场合，可以使用双向链表。
使用链表时，可以直接用 STL list，也可以自己写链表。如果自己写代码实现链表，有两种编码实现方法：动态链表、静态链表。在算法竞赛中为加快编码速度，一般用静态链表或者 STL list。
下面以“例 1. 洛谷 P1996”为例题，在后面 3 个小节中分别给出动态链表、静态链表、STL 链表等 3 种方案、5 种代码。这 5 种代码的逻辑和流程完全一样，只有链表的实现不一样，方便大家学习，把关注点放在链表的实现上。● 例 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
01、动态链表
动态链表需要临时分配链表结点、使用完毕后释放链表结点。优点是能及时释放空间，不使用多余内存；缺点是需要管理空间，容易出错。动态链表是“教科书式”的标准做法。
下面的代码用动态单向链表实现了例 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;}
复制代码
02、静态链表
提示/
动态链表虽然“标准”，但是竞赛中一般不用。算法竞赛对内存管理要求不严格，为加快编码速度，一般就在题目允许的存储空间内静态分配，省去了动态分配和释放的麻烦。静态链表使用预先分配的一段连续空间存储链表。从物理存储的意义上讲，“连续空间”并不符合链表的本义，因为链表的优点就是能克服连续存储的弊端。但是，用连续空间实现的链表，在逻辑上是成立的。具体有两种做法：
①定义链表结构体数组，和动态链表的结构差不多；
②使用一维数组，直接在数组上进行链表操作。
本节给出 3 段代码：用结构体数组实现单向静态链表、用结构体数组实现双向静态链表、用一维数组实现单向静态链表。
用结构体数组实现单向静态链表
用结构体数组实现单向静态链表，注意静态分配应该定义在全局，不能定义在函数内部。
#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; }
复制代码
用结构体数组实现双向静态链表
#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; }
复制代码
用一维数组实现单向静态链表
这是最简单的实现方法。定义一个一维数组 nodes［］，nodes［i］的 i 就是节点的值，而 nodes［i］的值是下一个节点。它的使用环境很有限，因为它的节点只能存一个数据，就是 i。
#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;}
复制代码
03、STL list
在算法竞赛或工程项目中常常使用 C++ STL list。list 是双向链表，由标准模板库(Standard Template Library,STL)管理，通过指针访问节点数据，高效率地删除和插入。请大家熟悉 list 的初始化、插入、删除、遍历、查找、释放。下面是用 list 实现例 1 的代码。
#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; }
复制代码
评论