九、单链表、双向链表、循环链表

https://zhuanlan.zhihu.com/p/29627391

======知识点======

单链表

单链表删除结点

单链表添加结点

双向链表

双向链表删除结点

双向链表添加结点

循环链表

https://zhuanlan.zhihu.com/p/360567636
一个结点

循环链表头插法

循环链表在指定位置插入结点

循环链表删除结点

======代码实现=======

单链表 邻接表

https://www.acwing.com/problem/content/828/

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int m;
int hh, e[N], ne[N], idx;
void add_to_head(int x){
    e[idx] = x, ne[idx] = hh, hh = idx++;
}
void add_to_node(int k, int x){
    e[idx] = x, ne[idx] = ne[k], ne[k] = idx++;
}
void remove(int k){
    ne[k] = ne[ne[k]];
}
int main(){
    hh = -1;
    cin >> m;
    while (m--){
        string op;
        cin >> op;
        if (op[0] == 'H'){
            int x;
            cin >> x;
            add_to_head(x);
        }
        else if (op[0] == 'D'){
            int k;
            cin >> k;
            if (k == 0) hh = ne[hh];  //如何删除的是头结点
            else remove(k - 1);
        }
        else{
            int k, x;
            cin >> k >> x;
            add_to_node(k - 1, x);
        }
    }
    for (int i = hh; i != -1; i = ne[i]) printf("%d ", e[i]);
    puts("");
    return 0;
}

头插法演示

单链表 结构体 TLE

// new Node(); 非常慢，链表大小1e4 1e5就会超时
// 这部分代码，希望大家能看懂C语言的指针，不推荐这种写法
#include <bits/stdc++.h>
#include <stddef.h>  
// How to fix C error ‘NULL undeclared’
// https://techoverflow.net/2019/06/20/how-to-fix-c-error-null-undeclared/
using namespace std;
const int N = 1e5 + 10;
struct Node{
    int data, id;
    Node *next;
};
int m, idx;
Node *head;
void add_to_head(int x){
    Node *t = new Node();
    t->data = x;
    t->next = head;
    t->id = idx++;
    head = t;
}
void add_to_node(int k, int x){
    Node *t = head;
    while (t->next != NULL){
        if (t->id == k) break;
        t = t->next;
    }
    Node *nw = new Node();
    nw->data = x;
    nw->id = idx++;
    nw->next = t->next;
    t->next = nw;
}
void remove(int k){
    Node *t = head;
    while (t->next != NULL){
        if (t->id == k) break;
        t = t->next;
    }
    Node *p = t->next;
    t->next = p->next;
    delete p;
}
int main(){
    head = new Node;
    head->next = NULL;
    cin >> m;
    while (m--){
        string op;
        cin >> op;
        if (op[0] == 'H'){
            int x;
            cin >> x;
            add_to_head(x);
        }
        else if (op[0] == 'D'){
            int k;
            cin >> k;
            if (k == 0) head = head->next;  //如何删除的是头结点
            else remove(k - 1);
        }
        else{
            int k, x;
            cin >> k >> x;
            add_to_node(k - 1, x);
        }
    }
    while (head->next != NULL){
        printf("%d ", head->data);
        head = head->next;
    }
    puts("");
    return 0;
}

双链表 邻接表

https://www.acwing.com/problem/content/829/

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int m;
int e[N], L[N], R[N], idx;
// k -> idx -> R[k]
void insert(int k, int x){
    e[idx] = x;
    R[idx] = R[k];   // 先把idx挂好
    L[idx] = k;
    L[R[k]] = idx;   // 然后弄原来的结点
    R[k] = idx++;
}
void remove(int k){
    L[R[k]] = L[k];
    R[L[k]] = R[k];
}
int main(){
    // r[0] 指向第一个点，0 1两个点作为两端，r[0] = 1, l[1] = 0 模拟成环
    // 用0, 1表示左端点、右端点，第一个数从idx = 2开始
    R[0] = 1, L[1] = 0, idx = 2;
    cin >> m;
    while (m--){
        string op;
        cin >> op;
        if (op == "L"){
            int x;
            cin >> x;
            insert(0, x);
        }
        if (op == "R"){
            int x;
            cin >> x;
            insert(L[1], x);
        }
        if (op == "D"){
            int k;
            cin >> k;
            remove(k+1);
        }
        if (op == "IL"){
            int k, x;
            cin >> k >> x;
            insert(L[k+1], x);  // 2-index
        }
        if (op == "IR"){
            int k, x;
            cin >> k >> x;
            insert(k+1, x);
        }
    }
    for (int i = R[0]; i != 1; i = R[i]) printf("%d ", e[i]);
    puts("");
    return 0;
}

循环链表 结构体

// 约瑟夫环问题
// 1~n个人，从第1个人开始报数，数到m的人出列
// 如此循环，直到最后一个人出列为止
// 输出出列的顺序
#include <bits/stdc++.h>
using namespace std;
struct node{
    int id;
    node *next;
};
node *head, *r;
int n, m;
int main(){
    cin >> n >> m;
    head = new node();
    head->id = 1;
    head->next = NULL;
    r = head;
    for (int i = 2; i <= n; i++){
        node *p = new node();
        p->id = i;
        p->next = NULL;
        r->next = p;
        r = p;
    }
    r->next = head;
    r = head;
    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= m - 2; j++) r = r->next;   //r走到了m-1的位置上
        cout << r->next->id << ' ';                     //m-1的下一个是m
        r->next = r->next->next;                        //删除结点
        r = r->next;                                    //挪到下一个从1开始数
    }
    puts("");
    return 0;
}