链表

链表的特点是用一组位于任意位置的存储单元存储线性表的数据元素，这组存储单元可以是连续的，也可以不连续。链表分为单向链表和双向链表

使用链表时，可以使用STL list ,也可以自己手搓。先以下列问题为例，给出动态链表，静态链表，STL链表3种方案

约瑟夫问题

问题描述：

动态链表

动态链表需要临时分配节点，使用完毕后释放链表节点。动态链表的优点，能及时释放空间，不使用多余内存；缺点是需要管理空间，容易出错

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
#include<bits/stdc++.h>
struct node {
	int data;
	node* next;
};

void process() {
	int n, m; // n为节点个数，m为约瑟夫环的报数最高数
	cin >> n >> m;
	node* head, * now , *p;
	head = new node;
	now = head;
	for (int i = 2; i <= n; i++) {
		p = new node;
		p->data = i;
		p->next = nullptr;
		now->next = p;
		now = p;
	}
	now->next = head;
// 以上是建立链表的过程，下面是解决约瑟夫问题的流程
	now = head; // 从头开始数
	int count = 1;
	node* prev;//记录删除节点的前一个节点
	while ((n--) > 1) {
		for (int i = 1; i < m; i++) {
			prev = now;
			now = now->next;
		}
		printf("%d", now->data);
		prev->next = now->next;
		delete now;
		now = prev->next;
	}
	printf("%d", now->data);
	delete now;
}

静态链表

静态链表使用预先分配的一段连续空间存储链表。虽然这不符合链表的本义（即克服连续存储的弊端），但是在逻辑上是成立的

下面给出三段代码，分别用结构体数组实现单向静态链表、双向静态链表、用一维数组实现单向静态链表

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

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
#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 = n;
    while((n--) >1)
    {
    	for(int i = 1; i<=n ;i++){
            prev= now; 
            now = now + 1;
        }
        printf("%d",nodes[now]);
        nodes[prev].nextid = nodes[now].nextid;
        now = nodes[prev].nextid;
    }
    printf("%d",nodes[now]);
	return 0;
}

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

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
#include<bits/stdc++.h>

int N = 105;
struct node{
    int nextid;
    int id;
    int previd;
    // int data;
}nodes[N];

int main(){
    int n,m;
    nodes[0].nextid = 1;
    for(int i = 1; i < n; i++){
        nodes[i].id = i;
        nodes[i].previd = i-1;
        nodes[i].nextid = i+1;
    }
    nodes[n].nextid = 1;
    nodes[0].previd = n;
    
    int now = 1;
    while((n--)>1){
    	for(int i = 1; i < m; i++){
            now = nodes[now].nextid;
        }
        printf("%d",nodes[now].id);
        int prev = nodes[now].previd;
        int next = nodes[now].nextid;
        nodes[prev].nextid = next;
        nodes[next].previd = prev; 
        now = next;
    }
    printf("%d",nodes[now].id);
    return 0;
}

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

一维数组nodes[]，nodes[i]的i就是节点的值，nodes[i]的值是下一个节点的值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include<bits/stdc++.h>
int main()
{
    int nodes[105];
    int n,m;
    scanf("%d %d",&n,&m);
    for(int i = 1; i <= n-1; i++)
    {
        nodes[i] = i+1;
    }
    nodes[n] = 1;
    while((n--)>1){
        int now = 1,prev = n;
        for(int i = 1; i< m; i++){
            prev = now;
            now = nodes[prev];
        }
        printf("%d",now);
        nodes[prev] = nodes[now];
        now = nodes[prev];
    }
    printf("%d",now);
    return 0;
}

STL List

在算法竞赛中，常常使用C++ STL List。list是双向链表，下面介绍一些基本使用方法，如初始化，删除，插入，遍历，查找，释放

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
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n,m;
    scanf("%d %d",&n,&m);
    list<int> nodes;
    for(int i=1 ; i<=n; i++){
        nodes.push_back(i);
    }
    list<int>::iterator it = nodes.begin();
    
    while((n--)>1)
    {
        for(int i = 1; i < m; i++){
            it ++;
            if(it == nodes.end()){
                it = nodes.begin();
            }
        }
        cout<< *it<<endl;
        list<int>::iterator next = ++it;
        if(next == nodes.end()){
            next = nodes.begin();
        }
        node.erase(--it);
        it = next;
    }
    cout<< *it<<endl;
    return 0;
}