动态链表详解：

动态链表详解：

什么是链表：

链表是一种常见的重要的数据结构，是动态的进行内存分配的一种结构，通过结构体去进行建立。

链表中有一个“头指针”变量，本文中用 head 表示，它存放一个地址，这个地址指向链表的第一个元素。就这样一直连接下去，知道最后一个元素，它不再指向其他元素，称作是“表尾”，存放一个空地址 NULL 表示链表结束。

链表中的每个元素又叫“结点”。

每个节点都必须包含两部分：

• 用户所需的实际数据
• 下一个结点的地址。

我们建立链表的目的还是为了存放数据，因此节点中必须要有实际的数据存放，通过下一个结点的地址再去访问下一个结点，读取下一个结点的内容。

可以看成链表中的各元素在内存中的地址可以是不连续的，要找到某一元素，必须要找到它的上一个元素，根据它提供的地址，才能定位到下一个元素。因此链表的首地址很重要，相当于是整个链表的入口地址，通过它才能去访问整个地址。

链表是如何建立起来的：

显而易见，链表这种数据结构，必须通过指针变量才能实现，每个节点中必须包含指针变量，用它来存放下一个结点的地址。

而结构体变量，用它去建立链表是最合适的，因为一个结构体变量可以包含若干和不同的数据成员，用结构体变量去充当结点，可以存放很多的数据：

struct link {
    int num;
    char ch;
    char *str;
    float x;
    double y;
    struct link *next;
};
1
2
3
4
5
6
7
8

建立链表的结构体中可以包含很多数据类型和数据，与普通的结构体不同的是，该结构体必须包含一项为指向该结构体类型的指针 struct link *next 用来存放下一个节点的地址。

**注意：**上面的代码只是定义了一个叫 link 的结构体，实际上并没有分配内存空间，只有定义了结构体变量之后才会分配

静态链表：

静态链表使用的不多，因为静态链表中所有的数据都是在程序内部填充好的，不是临时开辟的，使用完后也不会释放。

#include <stdio.h>

// 创建结构体：
struct link {
    int num;
    char *name;
    struct link * next;
};

int main(void)
{
    // 定义结构体变量：
    struct link x, y, z, *head, *p;
    // 为结构体变量填充数据：
    x.num = 100; x.name = "wang";
    y.num = 110; y.name = "zhang";
    z.num = 120; z.name = "li";
    // 将结构体变量连接起来：
    head = &x;
    x.next = &y;
    y.next = &z;
    z.next = NULL;

    // 开始遍历链表：
    p = head;
    while(p != NULL)
    {
        printf("num:%d name:%s\n", p->num, p->name);
        p = p->next;
    }
    return 0;
}
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

动态链表：

建立动态链表是指在程序执行过程中从无到有的建立起一个链表，即一个个的开辟结点和输入各节点的数据，并建立起前后相连的关系。

这里用一个简单的结构体举例：

// 建立动态链表所用的结构体：
struct link {
    int num;
    struct link *next;
};
1
2
3
4
5

写了六个函数：

• 开辟链表的函数
• 输出链表的函数
• 删除结点的函数
• 插入结点的函数
• 延长链表的函数
• 链表排序的函数

其中，链表的开辟是最重要的一步，只要理解了动态链表开辟的过程，就能理解动态链表的基本组成原理。

下面是动态链表的函数与详解：

# include "stdio.h"
# include "stdlib.h"

# define LEN sizeof(struct link)

// 建立动态链表所用的结构体：
struct link {
    int num;
    struct link *next;
};

// 静态内存区的全局变量：负责记录节点个数：
static int n;

// 开辟链表的函数：
struct link *creat(void);

// 输出链表的函数：
void print(struct link *const);

// 删除动态链表节点的函数：x 为待删除的数据值：
struct link *del(struct link *, int);

// 插入节点的函数：
struct link *insert(struct link *, struct link *, int);

// 延长链表的函数：
struct link *extend(struct link *);

// 给链表排序的函数：
void sort(struct link *);

int main(void) {
    struct link *head;
    head = creat();
    print(head);
    int ch = '#';
    char *sentence = "请选择您的操作：\n0.退出程序  1.打印链表的值  2.删除链表节点  3.插入链表节点  4.延长链表  5.给链表排序:";
    while (1) {
        printf("%s", sentence);
        scanf("%d", &ch);
        if (ch == 0) {
            printf("程序退出！");
            break;
        }
        if (ch == 1) {
            print(head);
        }
        if (ch == 2) {
            if (head == NULL) {
                printf("链表为空！请先输入数值！\n");
            } else {
                int x;
                printf("请输入要删除的数值：");
                scanf("%d", &x);
                head = del(head, x);
                print(head);
            }
        }
        if (ch == 3) {
            int pos;
            struct link *plus = (struct link *) malloc(LEN);
            plus->next = NULL;
            if (head == NULL || n == 0) {
                printf("链表为空！请先添加数据！");
            } else {
                printf("请输入要插入的数值：");
                scanf("%d", &plus->num);
                printf("请输入要插入的位置：");
                scanf("%d", &pos);
                head = insert(head, plus, pos);
                print(head);
            }
        }
        if (ch == 4) {
            head = extend(head);
            printf("添加数据成功！\n");
            print(head);
        }
        if (ch == 5) {
            sort(head);
            printf("链表排序成功！\n");
            print(head);
        }
    }
}

// 开辟链表的函数：
struct link *creat() {
    // 定义三个结构体指针变量，其中head指向链表首地址：
    struct link *head = NULL, *p, *q;
    n = 0;
    // 使用 malloc 开辟第一个节点，然后使 p,q 指向那片空间：
    // malloc带回的是不指向任何类型的指针数据 void 类型
    // 需要通过(struct link *)强制类型转换
    p = q = (struct link *) malloc(LEN);
    // 输入数据，当输入0的时候停止建立：
    // 因为 p 指向这片空间，通过 p 把数据写入那片内存空间
    printf("请输入数据开始建立链表：输入0时停止：");
    scanf("%d", &p->num);
    while (p->num != 0) {
        // 让节点数目 +1；
        n++;
        if (n == 1) {
            // 当第一次建立节点时让 head 指向第一个节点：
            head = p;
        } else {
            // 将新开辟的节点的地址赋值给上一个节点的 next 成员
            // 因为 q 指向这一个节点，对 q 进行的操作就是对节点的操作
            // 通过这一步把新开辟的节点和上一个节点连接起来
            q->next = p;
        }
        // 第一次循环的时候没有作用，此时 p 和 q 都是指向第一个节点
        // 之后的循环使 q 也指向刚建立的那个节点：
        q = p;
        // 第一次循环的时候开辟第二个节点
        // 之后的循环也是开辟新的节点并让 p 指向那片空间
        p = (struct link *) malloc(LEN);
        // 通过 p1 再次把数据写入新的内存空间中：
        scanf("%d", &p->num);
    }
    // 最后让 q 指向空，使链表最后一个结点的 next 指向 NULL
    // 将 NULL 设置为填表结尾的标志：
    q->next = NULL;
    // 此时 p 正指向输入数据为0的地址空间，将其释放掉：
    free(p);
    printf("建立链表成功！\n");
    // 把指向表头的指针返回出去：
    return head;
}

// 输出链表的函数：
void print(struct link *const head) {
    // 这里将 head 指针类型传入为 const 保护 head 的地址不被改变
    struct link *p = head;
    // 确保链表不为空：
    if (head != NULL) {
        printf("链表中的数据为：\n");
        // 开始循环打印链表的数据，当到 NULL 时停止：
        do {
            printf("%d ", p->num);
            p = p->next;
        } while (p != NULL);
        printf("\n");
    } else {
        printf("链表为空！\n");
    }
}

// 删除动态链表节点的函数：有重复数据时默认删除第一个：
struct link *del(struct link *head, int x) {
    // 删除一个节点是把它从链表中分离出来，只要撤销原来的链接关系即可
    // 这里指定 x 的数据的值作为删除节点的标志
    struct link *p, *q;
    // 检测链表为空：
    if (head == NULL) {
        printf("链表为空！\n");
        return head;
    }
    p = head;
    // 通过循环条件寻找待删除的数据：
    while (x != p->num && p->next != NULL) {
        // 让 q 是始终是 p 前面的那个节点：
        // 通过循环让 p 定位到待删除的节点位置：
        // 这样可以将待删除节点前的节点(q位置)与待删除节点后的节点(p->next)位置连接起来
        q = p;
        p = p->next;
    }
    // 再次确认条件：开始删除节点，这里分为两种情况：
    if (x == p->num) {
        // 如果待删除的节点是第一个节点，就要将 head 后移一个位置：
        // 如果不是第一个节点，就断开原有的连接，重新建立连接：
        // 将待删除节点前的节点(q位置)与待删除节点后的节点(p->next)位置连接起来
        if (p == head) {
            head = p->next;
        } else {
            q->next = p->next;
        }
        printf("数值为%d的节点已删除！\n", x);
        // 将删除的那个节点的空间释放掉：
        free(p);
        // 节点数目减一；
        n--;
    } else {
        printf("未找到数值为%d的节点！\n", x);
    }
    // 返回新的头指针：
    return head;
}

// 插入节点的函数：
struct link *insert(struct link *head, struct link *data, int pos) {
    // 函数接受的参数是头指针、要插入的结构体指针和要插入的位置：
    struct link *t = data, *p = head, *q = p->next;
    int i;
    // 判断当链表为空时，将插入的数据作为第一个节点：
    // 当链表不为空时，将有三种情况：
    if (head == NULL || n == 0) {
        head = t;
        t->next = NULL;
    } else {
        // 当要插入的位置为链表的头部时，将插入节点的地址位置给 head
        // 然后再与后面的链表连接起来：
        if (pos == 1 || pos == 0) {
            head = t;
            t->next = p;
        } else if (pos > n) {
            // 当要插入位置位于链表的末尾时；先通过循环定位到链表的尾端
            // 将插入的节点与尾端相连，最后将新的尾端地址改为 NULL
            while (p->next != NULL) {
                p = p->next;
            }
            p->next = t;
            // 修改新的尾端：
            t->next = NULL;
        } else {
            // 当插入节点位于中间时，通过 p,q两个指针同时定位到插入位置前一个节点和后一个节点
            for (i = 2; i < pos && p->next != NULL; i++) {
                // 通过循环进行定位：
                p = p->next;
                q = q->next;
            }
            // 找到对应位置后插入节点：
            p->next = t;
            t->next = q;
        }
    }
    // 插入节点后让节点数目+1：
    n++;
    return head;
}

// 延长链表的函数：
struct link *extend(struct link *head) {
    // 延长链表指的是在链表的尾部继续添加数据：
    struct link *till = head, *p, *q;
    // 此时分为两种情况：
    // 第一种情况时当链表为空的时候，就要重新去开辟链表：
    // 第二种情况时当链表不为空的时候，就在链表的尾部添加数据：
    if (till == NULL) {
        printf("链表为空，请输入数据建立链表：输入0时停止:");
        p = q = (struct link *) malloc(LEN);
        // 链表为空时，要将新建立的空间的指针赋值给头指针 till
        till = p;
    } else {
        // 链表不为空时，先定位到链表的尾端：
        q = till;
        while (q->next != 0) {
            q = q->next;
        }
        printf("请输入您要添加的数据：输入0时停止:");
        // p 指针负责去开辟新的空间：
        p = (struct link *) malloc(LEN);
    }
    // 输入数据：
    scanf("%d", &p->num);
    // 通过循环去添加数据：
    // 此时不管之前链表是否为空，同样都是将数据添加到链表的尾部：
    while (p->num != 0) {
        // 只要有数据添加：节点数+1
        n++;
        // 将节点与后一个节点连接起来：
        q->next = p;
        // 跳转到末尾的那个节点上：
        q = p;
        p = (struct link *) malloc(LEN);
        scanf("%d", &p->num);
    }
    // 让最后一个节点指向空地址：
    q->next = NULL;
    // 释放 p 所占用的空间：
    free(p);
    return till;
}

// 给链表数据排序的函数：
void sort(struct link *head) {
    // 对链表进行排序其实并不是一件简单的事情，因为链表的各个数据并不是紧密连接的
    // 这里先用结构体数组来读取链表的数据，转化为对数组的排序：
    // 排序过后再将数据重新写入链表中，可以保持原链表的结构不发生改变：
    struct link a[n], *p = head, t;
    int i, j, swap;
    // 将链表中的数据写入结构体数组中数组中：
    for (i = 0; i < n; i++) {
        a[i] = *p;
        p = p->next;
    }
    // 通过冒泡排序对数组进行排序：
    for (i = 0; i < n; i++) {
        swap = 0;
        for (j = 0; j < n - i - 1; j++) {
            if (a[j].num > a[j + 1].num) {
                t = a[j];
                a[j] = a[j + 1];
                a[j + 1] = t;
                swap = 1;
            }
        }
        if (swap == 0) {
            break;
        }
    }
    // 将数据重新写入链表中：
    p = head;
    for (i = 0; i < n; i++) {
        p->num = a[i].num;
        p = p->next;
    }
    // 这种方法的特点是能保持原链表的结构不发生改变
    // 改变的只是链表中各个节点的数据：
}

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
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312