C语言编写:已有a,b两个链表,每个链表中的结点包括学号、姓名。要求把两个链表合并,按学号升序排列
时间: 2023-07-11 13:17:07 浏览: 48
可以按照以下步骤实现:
1. 定义一个新的链表,作为合并后的链表。
2. 定义两个指针,分别指向 a 和 b 链表的开头。
3. 遍历 a 和 b 链表,比较当前两个指针所指向的结点的学号大小,将学号较小的结点加入新链表中,并将指针向后移动。
4. 如果其中一个链表已经遍历完了,将另一个链表剩余的结点全部加入新链表中。
5. 返回新链表的头结点即可。
下面是 C 语言代码的实现:
```c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
struct student {
int id; // 学号
char name[20]; // 姓名
struct student *next; // 指向下一个结点的指针
};
// 比较两个学生的学号大小
int cmp(struct student *s1, struct student *s2) {
return s1->id < s2->id;
}
// 合并两个链表
struct student* merge(struct student *a, struct student *b) {
struct student *head = NULL; // 新链表的头结点
struct student *p = NULL; // 新链表的尾结点
while (a != NULL && b != NULL) {
// 比较当前两个结点的学号大小
if (cmp(a, b)) {
// 将 a 的结点加入新链表中
if (head == NULL) {
head = p = a;
} else {
p->next = a;
p = a;
}
a = a->next;
} else {
// 将 b 的结点加入新链表中
if (head == NULL) {
head = p = b;
} else {
p->next = b;
p = b;
}
b = b->next;
}
}
// 如果其中一个链表已经遍历完了,将另一个链表剩余的结点全部加入新链表中
if (a != NULL) {
p->next = a;
} else if (b != NULL) {
p->next = b;
}
return head;
}
int main() {
// 创建链表 a
struct student *a = (struct student*)malloc(sizeof(struct student));
a->id = 2;
strcpy(a->name, "Tom");
a->next = (struct student*)malloc(sizeof(struct student));
a->next->id = 5;
strcpy(a->next->name, "Jack");
a->next->next = NULL;
// 创建链表 b
struct student *b = (struct student*)malloc(sizeof(struct student));
b->id = 1;
strcpy(b->name, "Bob");
b->next = (struct student*)malloc(sizeof(struct student));
b->next->id = 3;
strcpy(b->next->name, "Alice");
b->next->next = (struct student*)malloc(sizeof(struct student));
b->next->next->id = 4;
strcpy(b->next->next->name, "Lucy");
b->next->next->next = NULL;
// 合并链表 a 和 b,并按学号升序排列
struct student *head = merge(a, b);
// 打印新链表中的结点
struct student *p = head;
while (p != NULL) {
printf("%d %s\n", p->id, p->name);
p = p->next;
}
return 0;
}
```
输出结果为:
```
1 Bob
2 Tom
3 Alice
4 Lucy
5 Jack
```