用c语言将两个有序顺序表进行合并成一个有序的顺序表: /* 测试用例:输入: 1 3 5 2 4 6 8 10 输出:1 2 3 4 5 6 8 10
时间: 2024-09-28 12:09:27 浏览: 27
系统测试用例评审检查表.pdf
5星 · 资源好评率100%
在 C 语言中,合并两个有序顺序表(数组)可以采用双指针法。这里是一个简单的示例:
```c
#include <stdio.h>
// 定义节点结构体
typedef struct Node {
int data;
struct Node* next;
} Node;
// 合并两个有序链表函数
Node* mergeSortedLists(Node* list1, Node* list2) {
// 初始化临时头结点
Node* head = NULL;
if (list1 == NULL) {
return list2; // 如果 list1 为空,则直接返回 list2
}
if (list2 == NULL) {
return list1; // 如果 list2 为空,则直接返回 list1
}
// 比较两个列表的头部元素并决定新链表的头结点
if (list1->data <= list2->data) {
head = list1;
list1 = list1->next;
} else {
head = list2;
list2 = list2->next;
}
// 将较小元素添加到结果链表,并递归处理剩余部分
while (list1 != NULL && list2 != NULL) {
if (list1->data <= list2->data) {
head->next = list1;
list1 = list1->next;
} else {
head->next = list2;
list2 = list2->next;
}
head = head->next;
}
// 如果其中一个列表还有剩余元素,将其添加到结果链表
if (list1 != NULL) {
head->next = list1;
} else {
head->next = list2;
}
return head;
}
// 打印链表
void printList(Node* node) {
while (node != NULL) {
printf("%d ", node->data);
node = node->next;
}
printf("\n");
}
int main() {
// 创建第一个有序链表
Node* list1 = (Node*)malloc(sizeof(Node));
list1->data = 1;
list1->next = (Node*)malloc(sizeof(Node));
list1->next->data = 3;
list1->next->next = (Node*)malloc(sizeof(Node));
list1->next->next->data = 5;
list1->next->next->next = NULL;
// 创建第二个有序链表
Node* list2 = (Node*)malloc(sizeof(Node));
list2->data = 2;
list2->next = (Node*)malloc(sizeof(Node));
list2->next->data = 4;
list2->next->next = (Node*)malloc(sizeof(Node));
list2->next->next->data = 6;
list2->next->next->next = (Node*)malloc(sizeof(Node));
list2->next->next->next->data = 8;
list2->next->next->next->next = (Node*)malloc(sizeof(Node));
list2->next->next->next->next->data = 10;
list2->next->next->next->next->next = NULL;
// 合并两个链表
Node* mergedList = mergeSortedLists(list1, list2);
// 打印合并后的链表
printList(mergedList);
return 0;
}
```
在这个例子中,我们首先比较两个链表的头部元素,然后将较小的元素添加到新的链表中,并递归地处理剩余的部分,直到其中一个链表为空。最后,打印出合并后的链表。
阅读全文