抱歉，您的浏览器无法访问本站

本页面需要浏览器支持（启用）JavaScript


了解详情 >

链表

秃头王
基础数据结构

发布于：2022年1月15日
次浏览

单向链表

结点组成部分

数据域 - data

指针域 - next / 后继

image-20220115112228264

插入 - 结点

  1. 把待插入数据创建成一个结点
  2. 把待插入结点指向新建结点的next
  3. 把待插入结点前一个结点的next指向新建结点

image-20220115113310080

代码演示 - 单向链表

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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
/*************************************************************************
        > File Name: 链表.c
        > Author: 秃头王
        > Mail: 1658339000@qq.com
        > Created Time: 2022年01月15日 星期六 11时09分25秒
 ************************************************************************/

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define COLOR_HL(a, b) "\033[1;" #b "m" a "\033[0m"
#define GREEN_HL(a) COLOR_HL(a, 32)

typedef struct ListNode {
    int data;
    struct ListNode *next;
} ListNode;

typedef struct List {
    // 虚拟头
    ListNode head;
    int length;
} List;

ListNode *getNewNode(int);
List *getLinkList();
void clear_node(ListNode *);
void clear(List *);
int insert(List*, int, int);
int erase(List *, int);
void reverse(List *);

ListNode* getNewNode(int val) {
    // sizeof ListNode 可以不加括号 可能是在c语言中不行
    ListNode *p = (ListNode *) malloc(sizeof (ListNode));
    p->data = val;
    p->next = NULL;
    return p;
}

List *getLinkList() {
    List *l = (List *)malloc(sizeof(List));
    l->head.next = NULL;
    l->length = 0;
    return l;
}

void clear_node(ListNode *node) {
    if(node == NULL) return ;
    free(node);
    return ;
}

void clear(List * l) {
    if(l == NULL) return ;
    ListNode *p = l->head.next;
    ListNode *t = NULL;
    if(p != NULL) {
        t = p->next;
        clear_node(p);
        p = t;
    }
    free(l);
    return ;
}

int insert(List *l, int ind, int val) {
    if(l == NULL) return 0;
    if(ind < 0 || ind > l->length) return 0;
    ListNode *p = getNewNode(val);
    ListNode *h = &(l->head);
    while(ind--) h = h->next;
    p->next = h->next;
    h->next = p;
    l->length++;
    return 1;
}

int erase(List *l, int ind) {
    if(l == NULL) return 0;
    if(ind < 0 || ind >= l->length) return 0;
    ListNode *h = &(l->head);
    // 这里说明一下为什么不 直接 h->next = h->next->next;
    // 1. 这个操作是合法的 但是要这样操作的就会发生内存泄漏
    // 2. 所有我们这里需要一个临时变量  t 来存储待删除结点 之后好free掉
    ListNode *t = NULL;
    while(ind--) h = h->next;
    t = h->next;
    h->next = t->next;
    l->length--;
    clear_node(t);
    return 1;
}

void output(List *l) {
    if(l == NULL) return ;
    printf("List(%d) : ", l->length);
    ListNode *h = l->head.next;
    while(h != NULL) {
        printf("%d->", h->data);
        h = h->next;
    }
    printf("NULL\n\n");
}

void reverse(List *l) {
    if(l == NULL) return ;
    ListNode *h = l->head.next;
    l->head.next = NULL;
    ListNode *t = NULL;
    while(h != NULL) {
        t = h->next;
        t = l->head.next;
        l->head.next = h;
        h = t;
    }
    return ;
}

int main() {
    srand(time(0));
    // 20 次测试
    #define MAX_OP 20
    List *l = getLinkList();
    for(int i = 0; i < MAX_OP; i++) {
        int val = rand() % 100;
        int ind = rand() % (l->length + 3) - 1;
        // 想变大插入概率 可以把 2 变成 4
        // case 0 1 2 3
        int op = rand() % 3;
        switch(op) {
            case 0: {
                printf("erase a iterm at %d from List = %d \n", ind, erase(l, ind));
                break;
            }
            case 1: {
                printf("insert %d at %d to List = %d \n", val, ind, insert(l, ind, val));
                break;
            }
            case 2: {
                printf(GREEN_HL("reverse the list ! \n"));
                reverse(l);
                break;
            }
        }
        output(l);
    }
    #undef MAX_OP
    clear(l);
    return 0;
}

单线循环链表

image-20220115163522464

头- -> 尾

双向链表

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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
/*************************************************************************
        > File Name: 双向链表.c
        > Author: 秃头王
        > Mail: 1658339000@qq.com
        > Created Time: 2022年01月18日 星期二 17时05分55 秒
 ************************************************************************/

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

typedef struct Node {
    int data;
    struct Node *next, *pre;
} Node;

typedef struct Dlist {
    Node head;
    int length;
} Dlist;

Node *getNewNode(int val) {
    Node *p = (Node *)malloc(sizeof(Node));
    p->data = val;
    p->next = p->pre = NULL;
    return p;
}

Dlist *init_list() {
    Dlist *l = (Dlist *)malloc(sizeof(Dlist));
    l->head.next = NULL;
    l->length = 0;
    return l;
}

int insert(Dlist *l, int ind, int val) {
    if(l == NULL) return 0;
    if(ind < 0 || ind > l->length) return 0;
    Node *p = &(l->head), *node = getNewNode(val);
    while(ind--) p = p->next;
    node->next = p->next;
    p->next = node;
    node->pre = p;
    if(node->next != NULL) node->next->pre = node;
    l->length ++;
    return 1;
}

void clear_node(Node *node) {
    if(node == NULL) return ;
    free(node);
    return ;
}

void clear(Dlist *l) {
    if(l == NULL) return ;
    Node *p = l->head.next, *t;
    while(p) {
        t = p->next;
        clear_node(p);
        p = t;
    }
    free(l);
    return ;
}

int erase(Dlist *l, int ind) {
    if(l == NULL ) return 0;
    if(ind < 0 || ind >= l->length) return 0;
    Node *p= &(l->head), *t;
    while(ind--) p = p->next;
    t = p->next;
    p->next = t->next;
    if(t->next != NULL) t->next->pre = p;
    clear_node(t);
    l->length--;
    return 1;
}


void l_output(Dlist *l) {
    if(l == NULL) return ;
    printf("L-Dlist(%d) : ", l->length);
    for(Node *p = l->head.next; p; p = p->next) {
        printf("%d->", p->data);
    }
    printf("NULL\n");
    return ;
}

void r_output(Dlist *l) {
    if(l == NULL) return ;
    printf("L-Dlist(%d) : ", l->length);
    int ind = 0;
    Node *p = &(l->head);
    while(ind++ != l->length) p = p->next;
    for(; p != &(l->head); p = p->pre) {
        printf("%d->", p->data);
    }
    printf("head\n");
    return ;
}

int main() {
    #define MAX_OP 20
    Dlist *l = init_list();
    for(int i = 0; i < MAX_OP; i++) {
        int val = rand() % 100;
        int ind = rand() % (l->length + 3) - 1;
        int op = rand() % 2;
        switch(op) {
            case 0 : {
                printf("erase a iterm at %d form lis = %d", ind, erase(l, ind));
            } break;
            case 1 : {
                printf("insert %d at %d to Lis = %d\n", val, ind, insert(l, ind, val));
            } break;
        }
        l_output(l);
        r_output(l), printf("\n");
    }
    #undef MAX_OP
    clear(l);
    return 0;
}

链表翻转

image-20220203122707544

image-20220203122714585

力扣206

image-20220203130222576

博客内容遵循 署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0) 协议

本文永久链接是：https://tutouwang.vercel.app/2022/01/15/%E5%9F%BA%E7%A1%80%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/%E9%93%BE%E8%A1%A8/

更新于：2022年5月22日

链表

评论