1、定义一个结构体变量（包含年、月、日）。计算该日在本年中是第几天，注意闰年问题。

解题思路：虽然本题只为巩固结构体知识而显得有点突兀，这种直接可以不使用结构体完成的问题复杂化了。

  1. 定义结构体变量，成员有年（year）、月（month）、日（day）
  2. 计算公式：判断闰年（四年一润，百年不润，四百年再润）即可决定 2 月是 28 天还是 29 天，因此从 课后习题 - 图2累加，最后再加上第 month 月的天数 day 即可。 ```c

    include

struct Date { int year; int month; int day; };

int main() { struct Date d; printf(“Year Month Day:”); scanf(“%d%d%d”, &d.year, &d.month, &d.day); // calculate day of year int result = 0; int days[12] = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31}; if ((d.year % 4 == 0 && d.year % 100 !=0) || d.year % 400 == 0) { days[1] = 29; // leap year } for(int i = 0; i < date.month - 1; i++) { result = result + days[i]; } result = result + d.day; printf(“%d %d %d is the %d day of this year\n”, d.year, d.month, d.day, result); return 0; }

  1. 运行如下，程序尚未对其进行合法性检验，具体可待完善。
  2. :::success
  3. b12@PC:~/chapter9$ gcc -Wall ./src/dayOfYear.c -o ./bin/dayOfYear<br />b12@PC:~/chapter9$ ./bin/dayOfYear<br />Year Month Day:2020 7 20<br />2020 7 20 is the 202 day of this year
  5. b12@PC:~/chapter9$ date "+%j"  # Linux自带date函数 %j 格式化表示 day of year (001..366)<br />202
  7. b12@PC:~/chapter9$ ./bin/dayOfYear<br />Year Month Day:2020 1 0<br />2020 1 0 is the 0 day of this year
  8. :::
  10. <a name="Bjg9k"></a>
  11. # 2、写一个函数 `days`，实现第一题的计算。由主函数将年、月、日传递给 `days` 函数，计算后将日子数传回主函数输出。
  12. **解题思路**：代码同上面一模一样，只是简单的函数传参而已，考点就是结构体形参的使用可以免去传三个参数 `int days(int year, int month, int day)` 而直接传入 `int dayOfYear(struct Date d)` 即可。
  13. ```c
  14. #include <stdio.h>
  16. struct Date {
  17.     int year;
  18.     int month;
  19.     int day;
  20. };
  22. int dayOfYear(struct Date d){
  23.     int result = 0;
  24.     int days[12] = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
  25.     if ((d.year % 4 == 0 && d.year % 100 !=0) || d.year % 400 == 0) {
  26.         days[1] = 29;  // leap year
  27.     }
  28.     for(int i = 0; i < date.month - 1; i++) {
  29.         result = result + days[i];
  30.     }
  31.     result = result + d.day;
  32.     return result;
  33. }
  35. int main() {
  36.     struct Date d;
  37.     printf("Year Month Day:");
  38.     scanf("%d%d%d", &d.year, &d.month, &d.day);
  39.     printf("%d %d %d is the %d day of this year\n",
  40.           d.year, d.month, d.day, dayOfYear(d);
  41.     return 0;
  42. }

3、编写一个函数 print ，打印一个学生的成绩数组，该数组中有 5 个学生的数据记录，每个记录包括 课后习题 - 图3，用主函数输入这些记录，用 print 函数输出这些记录。

解题思路：

  1. 构造结构体数组，成员共有三个如题所给
  2. 执行 void print(struct Student stu) 函数输出结果。 ```c

    include

    define MAXSIZE 5

struct Student { int num; char name[8]; float score[3]; // notice };

void print(struct Student stu[], int stuSize) { printf(“Student’id\tname\tscore1\tscore2\tscore3\n”); for (int i = 0; i < MAXSIZE; i++) { printf(“%d\t%10s\t”, stu[i].num, stu[i].name); for (int j = 0; j < 3; j++) { printf(“%.1f\t”, stu[i].score[j]); } printf(“\n”); } }

int main() { struct Student stu[MAXSIZE]; for (int i = 0; i < MAXSIZE; i++) { printf(“Please input student %d’s id and name:”, i + 1); scanf(“%d %s”, &stu[i].num, stu[i].name); for (int j = 0; j < 3; j++) { printf(“%s’s score%d:”, stu[i].name, j + 1); scanf(“%f”, stu[i].score + j); } } print(stu, MAXSIZE); return 0; }

  1. 编译运行：
  2. :::success
  3. b12@PC:~/chapter9$ gcc -Wall ./src/studentInfo.c -o ./bin/studentInfo<br />b12@PC:~/chapter9$ ./bin/studentInfo<br />Please input student 1's id and name:101 Li<br />Li's score1:90<br />Li's score2:79<br />Li's score3:89<br />Please input student 2's id and name:102 Ma<br />Ma's score1:97<br />Ma's score2:90<br />Ma's score3:68<br />Please input student 3's id and name:103 Wang<br />Wang's score1:77<br />Wang's score2:70<br />Wang's score3:78<br />Please input student 4's id and name:104 Fun<br />Fun's score1:67<br />Fun's score2:89<br />Fun's score3:56<br />Please input student 5's id and name:105 Xue<br />Xue's score1:87<br />Xue's score2:65<br />Xue's score3:69<br />Student'id      name    score1  score2  score3<br />101             Li      90.0    79.0    89.0<br />102             Ma      97.0    90.0    68.0<br />103           Wang      77.0    70.0    78.0<br />104            Fun      67.0    89.0    56.0<br />105            Xue      87.0    65.0    69.0
  4. :::
  5. <a name="odaLF"></a>
  6. # 4、在第 `3` 题的计算出上，编写一个函数 `input` ，用来输入 `5` 个学生的数据记录。
  7. 解题思路：直接把上面 `main` 函数的输入部分放到函数内即可。注意传参和数组大小。
  8. ```c
  9. #include <stdio.h>
  10. #define MAXSIZE 5
  12. struct Student {
  13.     int num;
  14.     char name[8];
  15.     float score[3];  // notice
  16. };
  18. void input(struct Student stu[], int stuSize) {
  19.     for (int i = 0; i < MAXSIZE; i++) {
  20.         printf("Please input student %d's id and name:", i + 1);
  21.         scanf("%d %s", &stu[i].num, stu[i].name);
  22.         for (int j = 0; j < 3; j++) {
  23.             printf("%s's score%d:", stu[i].name, j + 1);
  24.             scanf("%f", stu[i].score + j);
  25.         }
  26.     }
  27. }
  29. void print(struct Student stu[], int stuSize) {
  30.     printf("Student'id\tname\tscore1\tscore2\tscore3\n");
  31.     for (int i = 0; i < MAXSIZE; i++) {
  32.         printf("%d\t%10s\t", stu[i].num, stu[i].name);
  33.         for (int j = 0; j < 3; j++) {
  34.             printf("%.1f\t", stu[i].score[j]);
  35.         }
  36.         printf("\n");
  37.     }
  38. }
  40. int main() {
  41.     struct Student stu[MAXSIZE];
  42.     input(stu, MAXSIZE);
  43.     print(stu, MAXSIZE);
  44.     return 0;
  45. }

5、在 10 个学生，每个学生的数据包括学号、姓名、3 门课程的成绩，从键盘输入 10 个学生数据，要求输出 3 门课程总平均成绩，以及最高分的学生的数据（包括学号、姓名、3 门课程成绩、平均分数）。

解题思路：考察还是结构体的构建和输入输出。其他的操作基本上和上一章类似。书中N-S流程图非常清晰。剩下的工作就是搬砖了。
image.png

  1. #include <stdio.h>
  2. #define N 5
  4. struct Student {
  5.     int num;
  6.     char name[8];
  7.     float score[3];  // notice
  8.     float aver;
  9. };
  11. void input(struct Student stu[], int stuSize) {
  12.     for (int i = 0; i < stuSize; i++) {
  13.         printf("Please input student %d's id and name:", i + 1);
  14.         scanf("%d %s", &stu[i].num, stu[i].name);
  15.         for (int j = 0; j < 3; j++) {
  16.             printf("%s's score%d:", stu[i].name, j + 1);
  17.             scanf("%f", stu[i].score + j);
  18.         }
  19.     }
  20. }
  22. void print(struct Student stu[], int stuSize) {
  23.     printf("Student'id\tname\tscore1\tscore2\tscore3\taverage\n");
  24.     for (int i = 0; i < stuSize; i++) {
  25.         printf("%d\t%10s\t", stu[i].num, stu[i].name);
  26.         for (int j = 0; j < 3; j++) {
  27.             printf("%.1f\t", stu[i].score[j]);
  28.         }
  29.         printf("%.1f\n", stu[i].aver);
  30.     }
  31. }
  33. int main() {
  34.     struct Student stu[N];
  35.     input(stu, N);
  36.     // 2. 计算平均分
  37.     float average = 0;
  38.     int maxSum = 0, maxStu = 0;
  39.     for (int i = 0; i < N; i++) {
  40.         float sum = 0;
  41.         for (int j = 0; j < 3; j++) {
  42.             sum += stu[i].score[j];
  43.         }
  44.         stu[i].aver = sum / 3.0;
  45.         if (sum > maxSum) {
  46.             maxSum = sum;
  47.             maxStu = i;  // 记录最大成绩学生的下标
  48.         }
  49.         average += stu[i].aver;  // 注意这里直接加某个学生成绩平均分
  50.     }
  51.     average /= N;
  52.     print(stu, N);
  53.     // 3.输出所有课程平均分+最高分的学生信息
  54.     printf("average=%.2f\n", average);
  55.     printf("The highest score is: student %d, %s\n",
  56.         stu[maxStu].num, stu[maxStu].name);
  57.     printf("scores: %6.2f, %6.2f, %6.2f, average: %6.2f\n",
  58.         stu[maxStu].score[0], stu[maxStu].score[1], stu[maxStu].score[2], stu[maxStu].aver);
  59.     return 0;
  60. }

编译运行：（注：本例只使用 5 人数据，搬砖输入太痛苦） :::success b12@PC:~/chapter9$ gcc -Wall ./src/studentInfo.c -o ./bin/studentInfo
b12@PC:~/chapter9$ ./bin/studentInfo
Please input student 1’s id and name:101 Wang
Wang’s score1:93
Wang’s score2:89
Wang’s score3:87
Please input student 2’s id and name:102 Li
Li’s score1:85
Li’s score2:80
Li’s score3:78
Please input student 3’s id and name:103 Zhao
Zhao’s score1:65
Zhao’s score2:70
Zhao’s score3:59
Please input student 4’s id and name:104 Ma
Ma’s score1:77
Ma’s score2:70
Ma’s score3:83
Please input student 5’s id and name:105 Han
Han’s score1:70
Han’s score2:67
Han’s score3:60
Student’id name score1 score2 score3 average
101 Wang 93.0 89.0 87.0 89.7
102 Li 85.0 80.0 78.0 81.0
103 Zhao 65.0 70.0 59.0 64.7
104 Ma 77.0 70.0 83.0 76.7
105 Han 70.0 67.0 60.0 65.7
average=75.53
The highest score is: student 101, Wang
scores: 93.00, 89.00, 87.00, average: 89.67 :::

6、13个人围成一圈，从第 1 个人开始顺序报数 1, 2, 3。凡报到 3 者退出圈子。找出最后留在圈子中的人原来的序号。要求用链表实现。

解题思路：书本上任然使用的是数组来模拟链表，即对于每个数组结构体元素，结构体成员中的 .next 是存储下一个结点的位置。本质上就是循环链表的实现。将链表中最后一个连接到头部如此串成一个环。
约瑟夫环 :::tips 几乎大部分单向链表问题，只要找到某个节点的前驱，所有问题都可以迎刃而解。本章所有链表题目都用虚拟头节点操作，因为非常方便！！无需考虑头结点删除问题。
主要问题：如何创建单链表，单链表的增删查改操作。分别将在下面例题中展开分析。 :::

  1. 单向链表的特点：只有头结点只有一个后继和尾节点只有一个前继，除此之外的节点都有一个前驱和后继。每个结点只有数据域和指向下个结点的指针域。
  2. 单向链表的创建：就如同串珠一样，我们要拿到“线”（第一个节点的指针）的开头，然后拿到“珠子”穿上去。接着第二个等操作。因此这个过程是可以用递归或者循环解决的。 ```c

    include

    include

// Definition for singly-linked list. struct ListNode { int val; struct ListNode *next; };

struct ListNode buildList() { int n; printf(“Please input the length of LinkList:”); scanf(“%d”, &n); printf(“Please input %d numbers:”, n); struct ListNode head = NULL, curr = NULL, prev = NULL; for (int i = 0; i < n; i++) { curr = (struct ListNode *)malloc(sizeof(struct ListNode)); scanf(“%d”, &curr->val); curr->next = NULL; if (!head) head = curr; // (1)头结点创建 else prev->next = curr; // (3)前驱连接curr prev = curr; // (2)更新前驱 } return head; }

void pirntList(struct ListNode *head) { printf(“LinkList data:”); while (head) { printf(“%d “, head->val); head = head->next; } printf(“\n”); }

int main() { struct ListNode *head = buildList(); pirntList(head); return 0; }

  1. **编译运行**：
  2. :::success
  3. b12@PC:~/chapter9$ ./bin/buildLinkList<br />Please input the length of LinkList:5<br />Please input 5 numbers:5 4 3 2 1<br />ListList data:5 4 3 2 1
  4. :::
  5. 至于递归也容易实现，方式就判断递归条件，如果是根据用户输入 `-1` 这种结束创建链表的话更好，因为递归条件可以设置为判断输入是否满足。其框架大概如下：
  6. ```c
  7. struct ListNode *buildList() {
  8.     int n;
  9.     printf("Please input number(-1 to quit):");
  10.     scanf("%d", &n);
  11.     if (-1 == n) return NULL;  // 递归结束
  12.     struct ListNode *curr = (struct ListNode *)malloc(sizeof(struct ListNode));
  13.     curr->val = n;
  14.     curr->next = buildList();  // 递归创建后继
  15.     return curr;  // 向前驱返回子孙
  16. }

编译运行： :::success b12@PC:~/chapter9$ gcc -Wall ./src/buildLinkList.c -o ./bin/buildLinkList
b12@PC:~/chapter9$ ./bin/buildLinkList
Please input number(-1 to quit):9
Please input number(-1 to quit):5
Please input number(-1 to quit):4
Please input number(-1 to quit):3
Please input number(-1 to quit):0
Please input number(-1 to quit):-1
LinkList data:9 5 4 3 0 ::: 就通用性来讲，前者更好，能够处理数据中含有 -1 这种特殊判断结束例子。因此下面的创建也使用该方法。书本上根本很少用动态链表，都是用数组模拟，有数组为什么还有链表操作？？

7、在第 9 章例 9.9 和例 9.10 的基础上，写一个函数 del 用来删除动态链表中指定的结点

下面链接里面有所有删除链表节点的题目。 单向链表删除节点，找到删除节点前驱即可
删除节点

12、建立一个链表，每个结点包括：学号、姓名、性别、年龄。输入一个年龄，如果链表中的结点所包含的年龄等于此年龄，则将此结点删去。

解题思路：本题正好是上面给定一个值，要求删除链表中所有重复的节点。

  1. 创建链表：使用 for 循环创建
  2. IO 交互：继续删除或者退出。 while 循环实现。（这里年龄没有负数，所以以 -1 作为用户结束删除条件） ```c

    include

    include

// Definition for singly-linked list. struct ListNode { int id; char name[10]; char sex; // F/M int age; struct ListNode *next; };

struct ListNode buildList() { int n; printf(“Please input the length of LinkList:”); scanf(“%d”, &n); struct ListNode head = NULL, curr = NULL, prev = NULL; for (int i = 0; i < n; i++) { printf(“Please input %d info(id name sex age):”, i + 1); curr = (struct ListNode *)malloc(sizeof(struct ListNode)); scanf(“%d %s %c %d”, &curr->id, curr->name, &curr->sex, &curr->age); curr->next = NULL; if (!head) head = curr; // (1)头结点创建 else prev->next = curr; // (3)前驱连接curr prev = curr; // (2)更新前驱 } return head; }

void pirntList(struct ListNode *head) { printf(“LinkList data:\n”); while (head) { printf(“%d %10s %c %d\n”, head->id, head->name, head->sex, head->age); head = head->next; } printf(“\n”); }

struct ListNode removeElements(struct ListNode head, int val){ // sentinel哨兵，curr前进，prev前驱 struct ListNode sentinel = {-1, “”, ‘N’, -1, head}, curr = head, prev = &sentinel; while (curr) { if (curr->age == val) { // 删除时,prev任然是下个节点的前驱，因此不动 prev->next = curr->next; printf(“Remove %d from LinkList\n”, curr->id); free(curr); // 释放当前节点 curr = prev->next; // curr 换到下一个去 } else { prev = curr; // 更新前驱 curr = curr->next; } } return sentinel.next; }

int main() { struct ListNode *head = buildList(); pirntList(head); int input; printf(“Please age to remove or -1 to quit:”); scanf(“%d”, &input); while (-1 != input) { head = removeElements(head, input); pirntList(head); printf(“Please age to remove or -1 to quit:”); scanf(“%d”, &input); } return 0; }

  1. **编译运行：**
  2. :::success
  3. b12@PC:~/chapter9$ gcc -Wall ./src/removeElements.c -o ./bin/removeElements<br />b12@PC:~/chapter9$ ./bin/removeElements<br />Please input the length of LinkList:6<br />Please input 1 info(id name sex age):101 Ma m 20<br />Please input 2 info(id name sex age):109 Ekon f 20<br />Please input 3 info(id name sex age):107 EQA m 20<br />Please input 4 info(id name sex age):102 Li f 23<br />Please input 5 info(id name sex age):103 Zhang m 19<br />Please input 6 info(id name sex age):104 Wang m 19<br />LinkList data:<br />101         Ma m 20<br />109       Ekon f 20<br />107        EQA m 20<br />102         Li f 23<br />103      Zhang m 19<br />104       Wang m 19
  5. Please age to remove or -1 to quit:21<br />LinkList data:<br />101         Ma m 20<br />109       Ekon f 20<br />107        EQA m 20<br />102         Li f 23<br />103      Zhang m 19<br />104       Wang m 19
  7. Please age to remove or -1 to quit:20<br />Remove 101 from LinkList<br />Remove 109 from LinkList<br />Remove 107 from LinkList<br />LinkList data:<br />102         Li f 23<br />103      Zhang m 19<br />104       Wang m 19
  9. Please age to remove or -1 to quit:19<br />Remove 103 from LinkList<br />Remove 104 from LinkList<br />LinkList data:<br />102         Li f 23
  11. Please age to remove or -1 to quit:23<br />Remove 102 from LinkList<br />LinkList data:
  13. Please age to remove or -1 to quit:1<br />LinkList data:
  15. Please age to remove or -1 to quit:-1
  16. :::
  17. <a name="vgzTs"></a>
  18. # 11、有两个链表 `a` 和 `b`，设结点中包含学号、姓名。从 `a` 链表中删去与 `b` 链表中有相同学号的那些结点。
  19. **解题思路**：本题要求的数据域将会发生改变，链表节点也需要重新设计，然后对创建好的两个链表分别进行“双指针”暴力循环去重。
  21. - 枚举链表 `a` 中的节点，记此时节点为 `curr1` ，前驱为 `prev` 
  22.    - 枚举链表 `b` 中的节点，若此时节点 `curr2->val = curr1->val` ，那么就需要把 `a` 中的 `curr1` 删除。（删除操作见上面一题，本例使用哨兵节点进行处理）
  24. [链表差集.pptx](https://www.yuque.com/attachments/yuque/0/2020/pptx/1438957/1603954960087-8aa02a89-8eca-4113-b2b5-5af766f24dbb.pptx)<br />编码时候需要注意很多细节问题：都在代码中体现：凡是链表 `node->next` 都要思考此时是否 `node` 存在问题。尤其注意当 `l1` 最后一个节点在 `l2` 中时，此时 `curr1` 更新为 `NULL` 就证明结束！否则继续实现其后继的查找 `curr1 = curr1->next` 。注意这两条件！
  25. ```c
  26. #include <stdio.h>
  27. #include <stdlib.h>
  28. #include <string.h>
  29. // Definition for singly-linked list.
  30. struct ListNode {
  31.     int id;
  32.     char name[10];
  33.     struct ListNode *next;
  34. };
  36. struct ListNode *buildList() {
  37.     int n;
  38.     printf("Please input the length of LinkList:");
  39.     scanf("%d", &n);
  40.     struct ListNode *head = NULL, *curr = NULL, *prev = NULL;
  41.     for (int i = 0; i < n; i++) {
  42.         printf("Please input %d info(id && name):", i + 1);
  43.         curr = (struct ListNode *)malloc(sizeof(struct ListNode));
  44.         scanf("%d %s", &curr->id, curr->name);
  45.         curr->next = NULL;
  46.         if (!head) head = curr;  // (1)头结点创建
  47.         else prev->next = curr;  // (3)前驱连接curr
  48.         prev = curr;  // (2)更新前驱
  49.     }
  50.     return head;
  51. }
  53. void pirntList(struct ListNode *head) {
  54.     printf("LinkList data:\n");
  55.     while (head) {
  56.         printf("%d %s\n", head->id, head->name);
  57.         head = head->next;
  58.     }
  59.     printf("\n");
  60. }
  62. struct ListNode* difference(struct ListNode* l1, struct ListNode* l2){
  63.     struct ListNode dummy = {-1, "dummy", l1};
  64.     struct ListNode *prev = &dummy, *curr1 = l1;
  65.     while (curr1) {
  66.         for (struct ListNode *curr2 = l2; curr2 != NULL; curr2 = curr2->next) {
  67.             if (0 == strcmp(curr2->name, curr1->name)) {
  68.                 prev->next = curr1->next;  // (1)连curr1后继，剥离curr1
  69.                 free(curr1);  // (2)释放curr1
  70.                 curr1 = prev->next;  // (3)继续枚举l1后继
  71.                 break;  // 一定要break，否则出现l2前面可能与新的curr1重复
  72.             }
  73.         }
  74.         prev = curr1;  // 更新前驱
  75.         if (curr1) {  // 会出现l1最后一个节点在l2中，经过上面循环curr1=NULL
  76.             curr1 = curr1->next;  // 正常未删除情况下更新
  77.         }
  78.     }
  79.     return dummy.next;
  80. }
  82. int main() {
  83.     struct ListNode *l1 = buildList(), *l2 = buildList();
  84.     l1 = difference(l1, l2);
  85.     pirntList(l1);
  86.     return 0;
  87. }

编译运行： :::success b12@PC:~/chapter9$ gcc -Wall ./src/difference.c -o ./bin/difference
b12@PC:~/chapter9$ ./bin/difference
Please input the length of LinkList:4
Please input 1 info(id && name):101 Wang
Please input 2 info(id && name):102 Li
Please input 3 info(id && name):105 Zhang
Please input 4 info(id && name):106 Wei
Please input the length of LinkList:5
Please input 1 info(id && name):103 Zhang
Please input 2 info(id && name):104 Ma
Please input 3 info(id && name):105 Chen
Please input 4 info(id && name):106 Guo
Please input 5 info(id && name):108 Liu
LinkList data:
101 Wang
102 Li
106 Wei :::

8、写一个函数 insert ，用来向一个动态链表插入节点。

解题思路：链表插入问题一定要找到插入位置的前驱。但是对于头结点前怎么插入呢？这是需要单独考虑的问题，如下 ppt 示意图。
无哨兵伪头插入.pptx
但是如果存在一个虚拟头结点，所有的链表节点都有前驱，因此可以统一起来处理，非常方便。
有哨兵伪头插入.pptx

9、综合本章例 9.9（建立链表的函数 creat ）、例9.10（输出链表的函数 print ）和本章习题第 7 题（删除链表中的结点的函数 del ）、第 8 题（插入结点的函数 insert ），再编写一个主函数，先后调用这些函数。用以上 5 个函数组成一个程序，实现链表的建立、输出、删除和插入，在主函数中指定需要删除和插入的结点的数据。

链表：

10、已有 a, b 两个链表，每个链表中的节点包括学号、成绩。要求把两个链表合并，按学号升序排列。

解题思路：本题没有给定说明两个链表是否有序，因此需要按照最通用的方式进行。

  1. 将两个链表合成一个链表，然后对整个链表进行排序。
  2. 分别对两个链表进行排序，然后使用双指针合并两个有序链表。

由此可以看出，不管最终如何实现，都必须要实现排序，而链表的排序方式中的「归并排序」又涉及到基础的「合并两个有序链表」问题，因此先从这个基础问题开始了解。假设两个链表是有序的，详见下方卡片内容。
21. 合并两个有序链表
在明白上面道理后，我们需要开始对无序链表进行排序操作。见下方卡片的三种排序方式的实现
链表排序
最终我们使用上面的「归并排序」来实现解决本问题的两种方式。

  1. 先合并成大表然后再对新表排序。 ```c

    include

    include

// Definition for singly-linked list. struct ListNode { int id; float score; struct ListNode *next; };

struct ListNode splitInterval(struct ListNode head, int interval) { / 以 head 为开始切割出 <=interval 个节点，然后返回第interval作为后面链表的前驱 / for (int i = 1; i < interval && head->next; i++, head = head->next); struct ListNode *nxt = head->next; head->next = NULL; // 切断后继 return nxt; // 返回下个链表的起始位置 }

struct ListNode sortList(struct ListNode head){ // 1.条件判断特例 if (!head || !head->next) return head; // 2.统计链表长度，作为interval划分循环次数 struct ListNode dummy = {-1, 0, head}; int length = 0, interval = 1; for (struct ListNode curr = head; curr; length++, curr = curr->next); // 3.进行 interval < length 轮排序，一轮执行 length / (interval 2) 合并有序链表操作 while (interval < length) { struct ListNode l1 = dummy.next, prev = &dummy; while (l1) { // (1) 切割得到第一块 struct ListNode l2 = splitInterval(l1, interval); if (!l2) break; // 第二段没有，跳过开始下轮 // (2) 切割得到第二块 struct ListNode nxt = splitInterval(l2, interval); // (3) 合并两个有序链表 while (l1 || l2) { // 最长遍历 if (l1 && (!l2 || l1->score <= l2->score)) { prev->next = l1; l1 = l1->next; } else { prev->next = l2; l2 = l2->next; } prev = prev->next; // 更新前驱 } l1 = prev->next = nxt; // prev是下段的前驱，l1作为下段开始 } interval *= 2; } return dummy.next; // 返回排序链表 }

struct ListNode buildList() { int n; printf(“Please input the length of LinkList:”); scanf(“%d”, &n); struct ListNode head = NULL, curr = NULL, prev = NULL; for (int i = 0; i < n; i++) { printf(“Please input %d id, score:”, i + 1); curr = (struct ListNode *)malloc(sizeof(struct ListNode)); scanf(“%d %f”, &curr->id, &curr->score); curr->next = NULL; if (!head) head = curr; // (1)头结点创建 else prev->next = curr; // (3)前驱连接curr prev = curr; // (2)更新前驱 } return head; }

void pirntList(struct ListNode *head) { printf(“LinkList data:\n”); while (head) { printf(“%d %.1f\n”, head->id, head->score); head = head->next; } }

struct ListNode mergeList(struct ListNode l1, struct ListNode l2) { // 将 l2 合并到 l1 去 if (!l1) return l2; // 特判 struct ListNode head = l1; // 先存 l1 表头 while (l1->next) { l1 = l1->next; } l1->next = l2; // l1 最后一个节点连上后继 l2 return head; }

int main() { struct ListNode l1 = buildList(); struct ListNode l2 = buildList(); struct ListNode *head = mergeList(l1, l2); pirntList(head); head = sortList(head); pirntList(head); return 0; }

  1. **编译运行**：代码中是按成绩从小到大排序的。
  2. :::success
  3. b12@PC:~/chapter9$ gcc -Wall ./src/mergeSort.c -o ./bin/mergeSort<br />b12@PC:~/chapter9$ ./bin/mergeSort<br />Please input the length of LinkList:4<br />Please input 1 id, score:101 89<br />Please input 2 id, score:103 67<br />Please input 3 id, score:105 97<br />Please input 4 id, score:107 88<br />Please input the length of LinkList:3<br />Please input 1 id, score:100 100<br />Please input 2 id, score:102 65<br />Please input 3 id, score:106 60<br />LinkList data:<br />101 89.0<br />103 67.0<br />105 97.0<br />107 88.0<br />100 100.0<br />102 65.0<br />106 60.0<br />LinkList data:<br />106 60.0<br />102 65.0<br />103 67.0<br />107 88.0<br />101 89.0<br />105 97.0<br />100 100.0
  4. :::
  6. 2. 分别对两个链表进行快速排序后，再合并**两个有序链表**的操作。
  7. ```c
  8. #include <stdio.h>
  9. #include <stdlib.h>
  11. // Definition for singly-linked list.
  12. struct ListNode {
  13.     int id;
  14.     float score;
  15.     struct ListNode *next;
  16. };
  18. struct ListNode* helper(struct ListNode* head, struct ListNode** tail){
  19.     // 1.条件判断特例
  20.     if (!head || !head->next) {
  21.         *tail = head;
  22.         return head;
  23.     }
  24.     // 2.以 head 节点为 pivot
  25.     int pivot = head->id;
  26.     struct ListNode dummy1 = {-1, -1, NULL}, *gt = &dummy1;
  27.     struct ListNode dummy2 = {-1, -1, NULL}, *lt = &dummy2;
  28.     struct ListNode dummy3 = {-1, -1, NULL}, *eq = &dummy3;
  29.     while (head) {
  30.         if (head->id == pivot) {
  31.             eq->next = head;
  32.             eq = head;
  33.         } else if (head->id > pivot) {
  34.             gt->next = head;
  35.             gt = head;
  36.         } else {
  37.             lt->next = head;
  38.             lt = head;
  39.         }
  40.         head = head->next;
  41.     }
  42.     // 3.断掉 3 个链表末尾，对小于 pivot 和 大于 pivot 继续进行拆分
  43.     struct ListNode *tail1, *tail2;  // 拿到排序链表末尾节点
  44.     eq->next = gt->next = lt->next = NULL;
  45.     dummy2.next = helper(dummy2.next, &tail1);  // 小于继续
  46.     eq->next = helper(dummy1.next, &tail2);  // 大于继续
  47.     // 4.将排好序的 lt 的末尾节点连上 eq
  48.     // 四种情况：|eq| |eq|gt lt|eq| lt|eq|gt
  49.     *tail = tail2 ? tail2 : eq;  // 向上传入尾巴
  50.     if (!tail1) {  // 没有 lt 段
  51.         return dummy3.next;
  52.     }
  53.     tail1->next = dummy3.next;  // 将 lt 尾巴连上 eq 链表
  54.     return dummy2.next;  // 返回排序链表
  55. }
  57. struct ListNode* sortList(struct ListNode* head){
  58.     struct ListNode *tail;  // 虚拟设置
  59.     return helper(head, &tail);
  60. }
  62. struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2){
  63.     struct ListNode dummy = {-1, -1, NULL}, *prev = &dummy;
  64.     while (l1 && l2) {
  65.         if (l1->id <= l2->id) {
  66.             prev->next = l1;
  67.             l1 = l1->next;
  68.         } else {
  69.             prev->next = l2;
  70.             l2 = l2->next;
  71.         }
  72.         prev = prev->next;  // 继续前行
  73.     }
  74.     /* 连接较长的，就算相等也没事 */
  75.     prev->next = l1 ? l1 : l2;
  76.     return dummy.next;
  77. }
  79. struct ListNode *buildList() {
  80.     int n;
  81.     printf("Please input the length of LinkList:");
  82.     scanf("%d", &n);
  83.     struct ListNode *head = NULL, *curr = NULL, *prev = NULL;
  84.     for (int i = 0; i < n; i++) {
  85.         printf("Please input %d id, score:", i + 1);
  86.         curr = (struct ListNode *)malloc(sizeof(struct ListNode));
  87.         scanf("%d %f", &curr->id, &curr->score);
  88.         curr->next = NULL;
  89.         if (!head) head = curr;  // (1)头结点创建
  90.         else prev->next = curr;  // (3)前驱连接curr
  91.         prev = curr;  // (2)更新前驱
  92.     }
  93.     return head;
  94. }
  96. void pirntList(struct ListNode *head) {
  97.     printf("LinkList data:\n");
  98.     while (head) {
  99.         printf("%d %.1f\n", head->id, head->score);
  100.         head = head->next;
  101.     }
  102.     printf("\n");
  103. }
  105. int main() {
  106.     struct ListNode *l1 = sortList(buildList());
  107.     pirntList(l1);
  108.     struct ListNode *l2 = sortList(buildList());
  109.     pirntList(l2);
  110.     struct ListNode *head = mergeTwoLists(l1, l2);
  111.     pirntList(head);
  112.     return 0;
  113. }

编译运行：代码中以学号 id 进行排序 :::success b12@PC:~/chapter9$ gcc -Wall ./src/quickSort.c -o ./bin/quickSort
b12@PC:~/chapter9$ ./bin/quickSort
Please input the length of LinkList:5
Please input 1 id, score:105 97
Please input 2 id, score:78 78
Please input 3 id, score:101 89
Please input 4 id, score:105 78
Please input 5 id, score:103 67
LinkList data:
78 78.0
101 89.0
103 67.0
105 97.0
105 78.0

Please input the length of LinkList:3
Please input 1 id, score:102 65
Please input 2 id, score:45 98
Please input 3 id, score:106 60
LinkList data:
45 98.0
102 65.0
106 60.0

LinkList data:
45 98.0
78 78.0
101 89.0
102 65.0
103 67.0
105 97.0
105 78.0
106 60.0

:::

:::tips 总结：这部分涉及到数据结构，较难理解，因此使用较多时间制作 ppt 帮大家理解链表这个数据结构究竟是什么玩意。只要记住单向链表，无论干任何事情都要找到它前驱。
线性表：链表+顺序表。两者都可以使用数组模拟。 :::