C语言之链表

C语言之链表

定义：
链表是一种物理存储上非连续，数据元素的逻辑顺序通过链表中的指针链接次序，实现的一种线性存储结构。
特点：
链表由一系列节点（链表中每一个元素称为节点）组成，节点在运行时动态生成（malloc），每个节点包括两个部分：
一个是存储数据元素的数据域
另一个是存储下一个节点地址的指针域

//链表的构成
typedef struct student
{
    //数据域
    int num;
    char name [20];
    //指针域
    struct student *next;
}STU;
1
2
3
4
5
6
7
8
9

数据域：存放各种实际的数据，如：num、name等。
指针域：存放下一节点的首地址，如：next等。

链表的操作:

创建
增、删、改、查

链表的创建

#include 
#include 

//链表的构成
typedef struct student
{
    //数据域
    int num;//学号
    int score;//分数
    char name [20];//姓名
    //指针域
    struct student *next;//结构体指针
}STU;

//函数功能:创建列表
//输入参数:STU **p_head表示新的链表指针的二级结构体指针，用于存放当前链表中结构体指针的地址
//STU *p_new表示新链表的指针，用于存放新链表的地址
void link_creat_head(STU **p_head,STU *p_new)
{
    STU *p_mov = *p_head;
    //如果当前链表的结构体指针指向为空
    if(*p_head == NULL)
    {
        //当第一次加入链表为空时，head执行p_new
        *p_head = p_new;
        p_new->next = NULL;
    }
    else//如果当前链表的结构体指针指向不为空
    {
        //第二次及以后加入链表
        while(p_mov->next != NULL)//链表指针域指针指向不为空
        {
            //找到原有链表的最后一个节点
            p_mov = p_mov->next;
        }
        //将新申请的节点加入链表
        p_mov->next = p_new;
        p_new->next = NULL;
    }
}

int main()
{
    STU *head = NULL,*p_new = NULL;
    int num,i;
    printf("请输入链表初始个数:\n");
    scanf("%d",&num);

    for(i = 0;i < num;i++)
    {
        //申请一个新节点空间
        p_new = (STU*)malloc(sizeof(STU));
        //给新节点赋值
        printf("请输入学号、分数、名字:\n");
        scanf("%d %d %s",&p_new->num,&p_new->score,p_new->name);

        //将新节点加入链表
        link_creat_head(&head,p_new);
    }
    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
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

链表的遍历

//链表的遍历
void link_print(STU *head)
{
    STU *p_mov;
    //定义新的指针保存链表的首地址，防止使用head改变原本链表
    p_mov = head;
    //当指针保存最后一个结点的指针域为NULL时，循环结束
    while(p_mov != NULL)
    {
        //先打印当前指针保存结点的指针域
        printf("num=%d score=%d name:%s\n",p_mov->num,\
               p_mov->score,p_mov->name);
        //指针后移，保存下一个结点的地址
        p_mov = p_mov->next;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

链表的释放

//链表的释放
void link_free(STU **p_head)
{
    //定义一个指针变量保存头结点的地址
    STU *pb = *p_head;

    while (*p_head != NULL) {
        //先保存p_head指向的结点的地址
        pb = *p_head;
        //p_head保存下一个结点地址
        *p_head = (*p_head)->next;
        //释放结点并防止野指针
        free(pb);
        pb = NULL;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

链表节点的查找

先对比第一个结点的数据域是否是想要的数据，如果是就直接返回，如果不是则继续查找下一个结点，如果到达最后一个结点的时候都没有匹配的数据，说明要查找数据不存在。

//链表的查找：按照学号查找
STU *link_search_num(STU *head,int num)
{
    STU *p_mov;
    //定义的指针变量保存第一个结点的地址
    p_mov = head;
    //当没有到达最后一个结点的指针域时循环继续
    while (p_mov != NULL) {
        //如果找到是当前结点的数据，则返回当前结点的地址
        if(p_mov->num == num)//找到了
        {
            return p_mov;
        }
        p_mov = p_mov->next;
    }
    //当循环结束的时候还没有找到，说明要查找的数据不存在，返回NULL进行标识
    return NULL;//没有找到
}

//链表的查找：按照姓名查找
STU *link_search_name(STU *head,char* name)
{
    STU *p_mov;
    //定义的指针变量保存第一个结点的地址
    p_mov = head;
    //当没有到达最后一个结点的指针域时循环继续
    while (p_mov != NULL) {
        //如果找到是当前结点的数据，则返回当前结点的地址
        if(strcmp(p_mov->name,name)==0)//找到了
        {
            return p_mov;
        }
        p_mov = p_mov->next;
    }
    //当循环结束的时候还没有找到，说明要查找的数据不存在，返回NULL进行标识
    return NULL;//没有找到
}
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

链表节点的删除

如果链表为空，不需要删除
如果删除的是第一个结点，则需要将保存链表首地址的指针保存第一个结点的下一个结点的地址
如果删除的是中间结点，则找到中间结点的前一个结点，让前一个结点的指针域保存这个结点的后一个结点的地址即可

//链表的释放
void link_free(STU **p_head)
{
    //定义一个指针变量保存头结点的地址
    STU *pb = *p_head;

    while (*p_head != NULL) {
        //先保存p_head指向的结点的地址
        pb = *p_head;
        //p_head保存下一个结点地址
        *p_head = (*p_head)->next;
        //释放结点并防止野指针
        free(pb);
        pb = NULL;
    }
}

//链表的查找：按照学号查找
STU *link_search_num(STU *head,int num)
{
    STU *p_mov;
    //定义的指针变量保存第一个结点的地址
    p_mov = head;
    //当没有到达最后一个结点的指针域时循环继续
    while (p_mov != NULL) {
        //如果找到是当前结点的数据，则返回当前结点的地址
        if(p_mov->num == num)//找到了
        {
            return p_mov;
        }
        p_mov = p_mov->next;
    }
    //当循环结束的时候还没有找到，说明要查找的数据不存在，返回NULL进行标识
    return NULL;//没有找到
}

//链表的查找：按照姓名查找
STU *link_search_name(STU *head,char* name)
{
    STU *p_mov;
    //定义的指针变量保存第一个结点的地址
    p_mov = head;
    //当没有到达最后一个结点的指针域时循环继续
    while (p_mov != NULL) {
        //如果找到是当前结点的数据，则返回当前结点的地址
        if(strcmp(p_mov->name,name)==0)//找到了
        {
            return p_mov;
        }
        p_mov = p_mov->next;
    }
    //当循环结束的时候还没有找到，说明要查找的数据不存在，返回NULL进行标识
    return NULL;//没有找到
}

//链表节点的删除
void link_delete_num(STU **p_head,int num)
{
    STU *pb,*pf;
    pb=pf=*p_head;
    if(*p_head == NULL)//链表为空，不用删
    {
        printf("链表为空，没有您要删的节点");
        return ;
    }
    
    while(pb‐>num != num && pb‐>next !=NULL)//循环找，要删除的节点
    {
        pf=pb;
        pb=pb‐>next;
    }
    
    if(pb‐>num == num)//找到了一个节点的num和num相同
    {
        if(pb == *p_head)//要删除的节点是头节点
        {
            //让保存头结点的指针保存后一个结点的地址
            *p_head = pb‐>next;
        }
        else
        {
            //前一个结点的指针域保存要删除的后一个结点的地址
            pf‐>next = pb‐>next;
        }
        //释放空间
        free(pb);
        pb = NULL;
    }
    else//没有找到
    {
        printf("没有您要删除的节点\n");
    }
}
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

链表中插入一个节点

//链表的插入：按照学号的顺序插入
void link_insert_num(STU **p_head,STU *p_new)
{
    STU *pb,*pf;
    pb=pf=*p_head;
    if(*p_head ==NULL)// 链表为空链表
    {
        *p_head = p_new;
        p_new->next=NULL;
        return ;
    }
    while((p_new->num >= pb->num) && (pb->next !=NULL) )
    {
        pf=pb;
        pb=pb->next;
    }

    if(p_new->num < pb->num)//找到一个节点的num比新来的节点num大，插在pb的前面
    {
        if(pb== *p_head)//找到的节点是头节点，插在最前面
        {
            p_new->next= *p_head;
            *p_head =p_new;
        }
        else
        {
            pf->next=p_new;
            p_new->next = pb;
        }
    }
    else//没有找到pb的num比p_new‐>num大的节点，插在最后
    {
        pb->next =p_new;
        p_new->next =NULL;
    }
}

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

链表排序

如果链表为空，不需要排序
如果链表只有一个结点，不需要排序
先将第一个结点与后面所有的结点依次对比数据域，只要有比第一个结点数据域小的，则交换位置，
交换之后，拿新的第一个结点的数据域与下一个结点再次对比，如果比他小，再次交换，依次类推
第一个结点确定完毕之后，接下来再将第二个结点与后面所有的结点对比，直到最后一个结点也对比完毕为止

//链表的排序
void link_order(STU *head)
{
    STU *pb,*pf,temp;
    pf=head;

    if(head==NULL)
    {
        printf("链表为空,不用排序\n");
        return ;
    }

    if(head->next ==NULL)
    {
        printf("只有一个节点，不用排序\n");
        return ;
    }

    while(pf->next !=NULL)//以pf指向的节点为基准节点
    {
        pb=pf->next;//pb从基准元素的下个元素开始
        while(pb!=NULL)
        {
            if(pf->num > pb->num)
            {
                temp=*pb;
                *pb=*pf;
                *pf=temp;

                temp.next=pb->next;
                pb->next=pf->next;
                pf->next=temp.next;
            }
            pb=pb->next;
        }
        pf=pf->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

链表逆序

//链表的逆序
STU *link_reverse(STU *head)
{
    STU *pf,*pb,*r;
    pf=head;
    pb=pf->next;

    while(pb!=NULL)
    {
        r=pb->next;
        pb->next=pf;
        pf=pb;
        pb=r;
    }

    head->next=NULL;
    head=pf;
    return head;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

总结

#include 
#include 

//链表的构成
typedef struct student
{
    //数据域
    int num;//学号
    int score;//分数
    char name [20];//姓名
    //指针域
    struct student *next;//结构体指针
}STU;

//函数功能:创建列表
//输入参数:STU **p_head表示新的链表指针的二级结构体指针，用于存放当前链表中结构体指针的地址
//STU *p_new表示新链表的指针，用于存放新链表的地址
void link_creat_head(STU **p_head,STU *p_new)
{
    STU *p_mov = *p_head;
    //如果当前链表的结构体指针指向为空
    if(*p_head == NULL)
    {
        //当第一次加入链表为空时，head执行p_new
        *p_head = p_new;
        p_new->next = NULL;
    }
    else//如果当前链表的结构体指针指向不为空
    {
        //第二次及以后加入链表
        while(p_mov->next != NULL)//链表指针域指针指向不为空
        {
            //找到原有链表的最后一个节点
            p_mov = p_mov->next;
        }
        //将新申请的节点加入链表
        p_mov->next = p_new;
        p_new->next = NULL;
    }
}

//链表的遍历
void link_print(STU *head)
{
    STU *p_mov;
    //定义新的指针保存链表的首地址，防止使用head改变原本链表
    p_mov = head;
    //当指针保存最后一个结点的指针域为NULL时，循环结束
    while(p_mov != NULL)
    {
        //先打印当前指针保存结点的指针域
        printf("num=%d score=%d name:%s\n",p_mov->num,\
               p_mov->score,p_mov->name);
        //指针后移，保存下一个结点的地址
        p_mov = p_mov->next;
    }
}

//链表的释放
void link_free(STU **p_head)
{
    //定义一个指针变量保存头结点的地址
    STU *pb = *p_head;

    while (*p_head != NULL) {
        //先保存p_head指向的结点的地址
        pb = *p_head;
        //p_head保存下一个结点地址
        *p_head = (*p_head)->next;
        //释放结点并防止野指针
        free(pb);
        pb = NULL;
    }
}

//链表的查找：按照学号查找
STU *link_search_num(STU *head,int num)
{
    STU *p_mov;
    //定义的指针变量保存第一个结点的地址
    p_mov = head;
    //当没有到达最后一个结点的指针域时循环继续
    while (p_mov != NULL) {
        //如果找到是当前结点的数据，则返回当前结点的地址
        if(p_mov->num == num)//找到了
        {
            return p_mov;
        }
        p_mov = p_mov->next;
    }
    //当循环结束的时候还没有找到，说明要查找的数据不存在，返回NULL进行标识
    return NULL;//没有找到
}

//链表的查找：按照姓名查找
STU *link_search_name(STU *head,char* name)
{
    STU *p_mov;
    //定义的指针变量保存第一个结点的地址
    p_mov = head;
    //当没有到达最后一个结点的指针域时循环继续
    while (p_mov != NULL) {
        //如果找到是当前结点的数据，则返回当前结点的地址
        if(strcmp(p_mov->name,name)==0)//找到了
        {
            return p_mov;
        }
        p_mov = p_mov->next;
    }
    //当循环结束的时候还没有找到，说明要查找的数据不存在，返回NULL进行标识
    return NULL;//没有找到
}

//链表节点的删除
void link_delete_num(STU **p_head,int num)
{
    STU *pb,*pf;
    pb=pf=*p_head;
    if(*p_head == NULL)//链表为空，不用删
    {
        printf("链表为空，没有您要删的节点");
        return ;
    }

    while(pb->num != num && pb->next !=NULL)//循环找，要删除的节点
    {
        pf=pb;
        pb=pb->next;
    }

    if(pb->num == num)//找到了一个节点的num和num相同
    {
        if(pb == *p_head)//要删除的节点是头节点
        {
            //让保存头结点的指针保存后一个结点的地址
            *p_head = pb->next;
        }
        else
        {
            //前一个结点的指针域保存要删除的后一个结点的地址
            pf->next = pb->next;
        }
        //释放空间
        free(pb);
        pb = NULL;
    }
    else//没有找到
    {
        printf("没有您要删除的节点\n");
    }
}

//链表的插入：按照学号的顺序插入
void link_insert_num(STU **p_head,STU *p_new)
{
    STU *pb,*pf;
    pb=pf=*p_head;
    if(*p_head ==NULL)// 链表为空链表
    {
        *p_head = p_new;
        p_new->next=NULL;
        return ;
    }
    while((p_new->num >= pb->num) && (pb->next !=NULL) )
    {
        pf=pb;
        pb=pb->next;
    }

    if(p_new->num < pb->num)//找到一个节点的num比新来的节点num大，插在pb的前面
    {
        if(pb== *p_head)//找到的节点是头节点，插在最前面
        {
            p_new->next= *p_head;
            *p_head =p_new;
        }
        else
        {
            pf->next=p_new;
            p_new->next = pb;
        }
    }
    else//没有找到pb的num比p_new‐>num大的节点，插在最后
    {
        pb->next =p_new;
        p_new->next =NULL;
    }
}

//链表的排序
void link_order(STU *head)
{
    STU *pb,*pf,temp;
    pf=head;

    if(head==NULL)
    {
        printf("链表为空,不用排序\n");
        return ;
    }

    if(head->next ==NULL)
    {
        printf("只有一个节点，不用排序\n");
        return ;
    }

    while(pf->next !=NULL)//以pf指向的节点为基准节点
    {
        pb=pf->next;//pb从基准元素的下个元素开始
        while(pb!=NULL)
        {
            if(pf->num > pb->num)
            {
                temp=*pb;
                *pb=*pf;
                *pf=temp;

                temp.next=pb->next;
                pb->next=pf->next;
                pf->next=temp.next;
            }
            pb=pb->next;
        }
        pf=pf->next;
    }
}

//链表的逆序
STU *link_reverse(STU *head)
{
    STU *pf,*pb,*r;
    pf=head;
    pb=pf->next;

    while(pb!=NULL)
    {
        r=pb->next;
        pb->next=pf;
        pf=pb;
        pb=r;
    }

    head->next=NULL;
    head=pf;
    return head;
}
int main()
{
    STU *head = NULL,*p_new = NULL;
    int num,i;
    printf("请输入链表初始个数:\n");
    scanf("%d",&num);

    for(i = 0;i < num;i++)
    {
        //申请一个新节点空间
        p_new = (STU*)malloc(sizeof(STU));
        //给新节点赋值
        printf("请输入学号、分数、名字:\n");
        scanf("%d %d %s",&p_new->num,&p_new->score,p_new->name);

        //将新节点加入链表
        link_creat_head(&head,p_new);
    }
    //打印链表
    link_print(head);

    //查找链表：按学号查找
#if 0
    STU *pb;
    while (1) {
        printf("请输入你要查找学生的学号\n");
        scanf("%d",&num);
        pb = link_search_num(head,num);
        if(pb != NULL)//找到了
        {
            printf("找到了 num=%d score=%d name:%s\n",pb->num,\
                   pb->score,pb->name);
        }
        else
        {
            printf("没有找到您要查找的节点\n");
        }
    }
#endif

    //查找链表：按名字查找
#if 0
    char name[32] = "";
    while (1) {
        printf("请输入你要查找学生的姓名\n");
        scanf("%s",&name);
        pb = link_search_name(head,name);
        if(pb != NULL)//找到了
        {
            printf("找到了 num=%d score=%d name:%s\n",pb->num,\
                   pb->score,pb->name);
        }
        else
        {
            printf("没有找到您要查找的节点\n");
        }
    }
#endif
//插入链表
#if 0
    while(1)
    {
        printf("请输入您要插入的节点的 num score name\n");
        p_new=(STU*)malloc(sizeof(STU));//申请一个新节点
        scanf("%d %d %s",&p_new->num,&p_new->score,p_new->name);
        link_insert_num(&head,p_new);
        link_print(head);
    }
#endif

    printf("***************************\n");
    //link_order(head);
    //逆序
    head = link_reverse(head);
    link_print(head);
    //删除链表
    link_free(&head);
    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
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
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327