Linux C语言 17-链表_linux c 链表

Linux C语言 17-链表

本节关键字：Linux、C语言、链表、信息管理系统
相关C库函数：malloc、free、memset、memcpy、sizeof、strcmp、printf

什么是链表？

大白话，就是多块地址连续或不连续的内存首尾相连组成的一个集体，可以实现节点的增删改查。链表的本质是一种“数据结构”，实现了数据的链式存储方式。

链表的特点

开辟的空间不连续、有需求再开辟空间，见缝插针式存储。

链表的结构

• 节点：一个数据块，可以分为数据域和指针域（用结构体实现数据域和指针域的存储）；
• 数据域：存放有效数据；
• 指针域：存放下一个节点的地址；
• 头节点：第一个节点，头节点的数据域一般不存放数据，因为要删除的内容在链表头内，就需要删除链表头，很不方便；
• 尾节点：最后一个节点，尾节点的指针域一般为NULL；
• 遍历：从头到尾查找的过程。

链表的分类

• 单向链表：每个节点由数据域和指针域组成，并且每个节点的指针域存储的是下一个节点的地址；

• 单向循环链表：每个节点由数据域和指针域组成，并且尾节点的指针域存储的是头节点的地址；

• 双向链表：每个节点由数据域和两个指针域组成，一个指针域存储前一个节点的地址，另一个指针域存储后一个节点的地址；

• 双向循环链表：每个节点由数据域和两个指针域组成，并且头节点的前一个节点是尾节点，尾节点的后一个节点是头节点，实质上就是两个单向循环链表。

链表的存储方式

• 头插法：在头节点和第一个节点之间插入一个新的节点；
• 尾插法：在尾节点之后插入一个新的节点。

链表的判断

判断两个单向链表是否相交

• 拿第一个链表的元素和第二个链表的元素逐个比较，一旦出现相同的地址，就认为相交；
• 两个链表一旦相交，可能有相同的尾节点，判断尾节点是否相同；
• 截取和较短链表长度一致的子链表，将子链表和较短的链表逐个比较；
• …

判断单链表是否为有环链表

• 从给定链表的头节点开始遍历，没遍历一个节点，都将其和遍历过的节点相比较，若有相同，即为有环链表；
• 定义两个遍历指针p1和p2，遍历过程中p1每次移动一个节点，p2每次移动两个节点，若p1和p2相遇，则说明有环；
• …

链表的使用

链表的使用很广泛，这里我们就利用本节举例将之前所学的知识点进行复习。题目就是比较火爆的“简易版学生信息管理系统”。

/**
 * 程序：简易版学生信息管理系统
 * 作者：Tianwx_
 * 时间：2020.04.11
 */

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

// 定义学生信息
typedef struct info_t
{
    char name[64];        // 姓名
    char sex[16];        // 性别
    int  age;            // 年龄
    char major[128];    // 专业
    int  score;            // 成绩
    int  no;            // 学号
} info_t;

// 定义节点
typedef struct node_t
{
    struct node_t    *pLast;
    info_t            info;
    struct node_t      *pNext;
} node_t;

// 定义系统信息
typedef struct sys_info_t
{
    node_t    *pHead;        // 头节点
    node_t    *pTail;        // 尾节点
    int        sCount;        // 学生数量
} sys_info_t;

typedef node_t* pnode_t;
typedef node_t* phead_t;

enum user_cmd
{
    CMD_EXIT, CMD_ADD, CMD_DELETE, CMD_UPDATE, CMD_FIND, CMD_FILTER, CMD_PRINT,
};


pnode_t createLinkNode();                           // 创建链表节点
phead_t createLinkHead();                           // 创建链表头节点
pnode_t addLinkNode(phead_t head, info_t info);        // 增加一个链表节点
pnode_t deleteLinkNode(phead_t head, info_t info);    // 删除一个链表节点
pnode_t updateLinkNode(phead_t head, info_t info);    // 更新指定学生信息
void findLinkNode(phead_t head, info_t info);       // 筛选指定学生信息
void printLinkNode(phead_t head);                   // 罗列所有学生信息
int  compare(info_t *info1, info_t *info2);         // 比较学生信息
int  update(info_t *info1, info_t *info2);          // 更新学生信息
int  filter(info_t *info1, info_t *info2);          // 过滤学生信息
void print(info_t *info);                           // 打印学生信息
int  menu();                                        // 打印菜单
void readUserInfo(phead_t head, int cmd);           // 读取用户输入

void studentInfoTest();                             // 测试接口

sys_info_t g_SystermInformation;


int main(int argc, char *argv[])
{
    studentInfoTest();
    
    return 0;
}

pnode_t createLinkNode()
{
    pnode_t pnode = (pnode_t)malloc(sizeof(node_t));
    if (!pnode)
        return NULL;

    memset(pnode, 0, sizeof(node_t));
    return pnode;
}

phead_t createLinkHead()
{
    static phead_t pLinkHead = NULL;

    if (pLinkHead)
        return pLinkHead;

    pLinkHead = (phead_t)malloc(sizeof(node_t));
    if (!pLinkHead)
        return NULL;

    memset(pLinkHead, 0, sizeof(node_t));
    return pLinkHead;
}

pnode_t addLinkNode(phead_t head, info_t info)
{
    if (!head)
        return NULL;

    pnode_t ptail = head;
    while (ptail->pNext)
        ptail = ptail->pNext;

    pnode_t pnode = createLinkNode();
    if (!pnode)
        return NULL;

    memcpy(&pnode->info, &info, sizeof(info));
    ptail->pNext = pnode;
    pnode->pLast = ptail;

    g_SystermInformation.sCount += 1;
    g_SystermInformation.pTail = pnode;

    printf("\033[32m添加成功！\n\n\n\033[0m");
    
    return pnode;
}

pnode_t deleteLinkNode(phead_t head, info_t info)
{
    if (!head)
        return NULL;

    pnode_t plast = NULL;
    pnode_t pnext = NULL;
    pnode_t ptail = head->pNext;
    while (ptail)
    {
        if (compare(&ptail->info, &info) != 0)
        {
            ptail = ptail->pNext;
            continue;
        }

        plast = ptail->pLast;
        pnext = ptail->pNext;
        plast->pNext = pnext;
        pnext->pLast = plast;

        g_SystermInformation.sCount -= 1;
        if (ptail->pNext == NULL)
            g_SystermInformation.pTail = ptail->pLast;

        free(ptail);
        break;
    }

    return pnext;
}

pnode_t updateLinkNode(phead_t head, info_t info)
{
    if (!head)
        return NULL;

    pnode_t ptail = head->pNext;
    while (ptail)
    {
        if (ptail->info.no != info.no)
        {
            ptail = ptail->pNext;
            continue;
        }

        if (update(&ptail->info, &info) != 0)
            ptail = NULL;

        break;
    }

    return ptail;
}

void findLinkNode(phead_t head, info_t info)
{
    if (!head)
        return;

    printf("学号\t姓名\t性别\t年龄\t专业\t成绩\n");
    
    pnode_t ptail = head->pNext;
    while (ptail)
    {
        filter(&ptail->info, &info);
        ptail = ptail->pNext;
    }
}

void printLinkNode(phead_t head)
{
    if (!head)
        return;

    printf("@输出学生信息开始（共计学生 %d 名）\n", g_SystermInformation.sCount);
    printf("学号\t姓名\t性别\t年龄\t专业\t成绩\n");

    pnode_t ptail = head->pNext;
    while (ptail)
    {
        print(&ptail->info);
        ptail = ptail->pNext;
    }
    
    printf("@输出学生信息结束（共计学生 %d 名）\n\n\n", g_SystermInformation.sCount);
}

/**
 * @brief compare
 * @param info1
 * @param info2
 * @return 相同返回0, 不同返回非零
 */
int compare(info_t *info1, info_t *info2)
{
    if (!info1 && !info2)
        return 0;

    if (!info1 && info2)
        return 1;

    if (info1 && !info2)
        return 2;

    if (info1->no != info2->no)
        return 3;

    if (strcmp(info1->name, info2->name) != 0)
        return 4;

    if (strcmp(info1->sex, info2->sex) != 0)
        return 5;

    if (info1->age != info2->age)
        return 6;

    if (strcmp(info1->major, info2->major) != 0)
        return 7;

    if (info1->score != info2->score)
        return 8;

    return 0;
}

int update(info_t *info1, info_t *info2)
{
    if (!info1)
        return 1;

    if (!info2)
        return 2;

    if (info1->no != info2->no)
        return 3;

    if (strcmp(info1->name, info2->name) != 0)
    {
        memset(info1->name, 0, sizeof(info1->name));
        strcpy(info1->name, info2->name);
    }

    if (strcmp(info1->sex, info2->sex) != 0)
    {
        memset(info1->sex, 0, sizeof(info1->sex));
        strcpy(info1->sex, info2->sex);
    }

    if (info1->age != info2->age)
        info1->age = info2->age;

    if (strcmp(info1->major, info2->major) != 0)
    {
        memset(info1->major, 0, sizeof(info1->major));
        strcpy(info1->major, info2->major);
    }

    if (info1->score != info2->score)
        info1->score = info2->score;

    return 0;
}

int filter(info_t *info1, info_t *info2)
{
    char cFlag = 0;

    if (!info1)
        return 1;

    if (!info2)
        return 2;

    if (info1->no != 0)
        if (info1->no != info2->no)
            return 3;
    cFlag |= 1;

    if (strlen(info2->name) > 0)
        if (strcmp(info1->name, info2->name) != 0)
            return 4;
    cFlag |= 1<<1;

    if (strlen(info2->sex) > 0)
        if (strcmp(info1->sex, info2->sex) != 0)
            return 5;
    cFlag |= 1<<2;

    if (info1->age != 0)
        if (info1->age != info2->age)
            return 6;
    cFlag |= 1<<3;

    if (strlen(info2->major) > 0)
        if (strcmp(info1->major, info2->major) != 0)
            return 7;
    cFlag |= 1<<4;

    if (info1->score != 0)
        if (info1->score != info2->score)
            return 8;
    cFlag |= 1<<5;

    if (cFlag>>0 & 1) printf("\033[31m%d\t", info1->no);
    if (cFlag>>1 & 1) printf("%s\t", info1->name);
    if (cFlag>>2 & 1) printf("%s\t", info1->sex);
    if (cFlag>>3 & 1) printf("%d\t", info1->age);
    if (cFlag>>4 & 1) printf("%s\t", info1->major);
    if (cFlag>>5 & 1) printf("%d\n\033[0m", info1->score);

    return 0;
}

void print(info_t *info)
{
    printf("%d\t%s\t%s\t%d\t%s\t%d\n",
           info->no, info->name, info->sex, info->age, info->major, info->score);
}

int menu()
{
    int chioce;
    printf("**************************************\n");
    printf("*    1 - 增加学生信息\n");
    printf("*    2 - 删除学生信息\n");
    printf("*    3 - 更新学生信息\n");
    printf("*    4 - 查找学生信息\n");
    printf("*    5 - 过滤学生信息\n");
    printf("*    6 - 打印所有学生信息\n");
    printf("*    0 - 退出\n");
    printf("**************************************\n");
    printf("请输入您的选择： ");
    scanf("%d", &chioce);

    return chioce;
}

void readUserInfo(phead_t head, int cmd)
{
    info_t info;
    memset(&info, 0, sizeof(info));
    
    if (cmd == CMD_PRINT)
    {
        printLinkNode(head);
        return;
    }

    if (cmd == CMD_ADD)
    {
        printf("请输入学号： ");
        scanf("%d", &info.no);

        printf("请输入姓名： ");
        scanf("%s", info.name);

        printf("请输入性别： ");
        scanf("%s", info.sex);

        printf("请输入年龄： ");
        scanf("%d", &info.age);

        printf("请输入专业： ");
        scanf("%s", info.major);

        printf("请输入成绩： ");
        scanf("%d", &info.score);
    }
    else
    {
        printf("请输入学号（跳过请输入 -1）： ");
        scanf("%d", &info.no);

        printf("请输入姓名（跳过请输入 \\0）： ");
        scanf("%s", info.name);

        printf("请输入性别（跳过请输入 \\0）： ");
        scanf("%s", info.sex);

        printf("请输入年龄（跳过请输入 -1）： ");
        scanf("%d", &info.age);

        printf("请输入专业（跳过请输入 \\0）： ");
        scanf("%s", info.major);

        printf("请输入成绩（跳过请输入 -1）： ");
        scanf("%d", &info.score);
    }

    switch (cmd)
    {
    case CMD_EXIT:      exit(0);                    break;
    case CMD_ADD:       addLinkNode(head, info);    break;
    case CMD_DELETE:    deleteLinkNode(head, info); break;
    case CMD_UPDATE:    updateLinkNode(head, info); break;
    case CMD_FIND:      findLinkNode(head, info);   break;
    case CMD_FILTER:    findLinkNode(head, info);   break;
    case CMD_PRINT:     printLinkNode(head);        break;
    default: break;
    }
}

void studentInfoTest()
{
    g_SystermInformation.pHead = createLinkHead();
    if (g_SystermInformation.pHead == NULL)
    {
        printf("程序初始化失败，退出！\n");
        exit(0);
    }

    while (1)
    {
        readUserInfo(g_SystermInformation.pHead, menu());
    }
}

/** 运行结果：步骤较多请自行验证
*/
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
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442

该版本为最基础版本，需要更加完善的版本请点赞关注后私信获取！！！