已有a、b两个链表,每个链表中的结点包括学号、成绩,要求把两个链表合并,按学号升序排列
时间: 2024-05-02 08:17:38 浏览: 76
可以采用归并排序的思想,将两个链表合并排序。具体实现步骤如下:
1. 定义一个新链表,表示合并后的链表,同时定义指针p指向它的头结点。
2. 分别定义指针p1和p2,分别指向链表a和b的头结点。
3. 依次比较p1和p2所指向的学号大小,将较小的结点加入到新链表中,并将指针向后移动一位。
4. 当p1或p2中的一个链表遍历完毕后,将另一个链表的剩余结点依次加入到新链表中。
5. 返回新链表的头结点。
下面是C++代码实现:
```c++
#include <iostream>
using namespace std;
struct node
{
int id; //学号
int score; //成绩
node *next; //指向下一个结点的指针
};
//合并两个有序链表
node* merge(node* a, node* b)
{
node *p1 = a->next;
node *p2 = b->next;
node *newList = new node;
newList->next = nullptr;
node *p = newList;
while (p1 && p2) {
if (p1->id < p2->id) {
p->next = p1;
p1 = p1->next;
}
else {
p->next = p2;
p2 = p2->next;
}
p = p->next;
}
if (p1) p->next = p1;
if (p2) p->next = p2;
return newList;
}
//输出链表
void print(node *list)
{
node *p = list->next;
while (p) {
cout << "id: " << p->id << ", score: " << p->score << endl;
p = p->next;
}
}
int main()
{
//创建链表a
node *a = new node;
a->next = nullptr;
node *p = a;
for (int i = 1; i <= 5; i++) {
node *temp = new node;
temp->id = i;
temp->score = i * 10;
temp->next = nullptr;
p->next = temp;
p = temp;
}
//创建链表b
node *b = new node;
b->next = nullptr;
p = b;
for (int i = 3; i <= 7; i++) {
node *temp = new node;
temp->id = i;
temp->score = i * 10;
temp->next = nullptr;
p->next = temp;
p = temp;
}
//合并链表a和b,并按学号升序排列
node *newList = merge(a, b);
//输出新链表
print(newList);
return 0;
}
```
阅读全文