用c语言编写一个程序,有顺序表A和B,其元素均按从小到大的升序排列,编写一个算法,将它们合并成一个顺序表C,要求C的元素也按从小到大的升序排列。
时间: 2024-09-19 07:08:47 浏览: 32
你可以使用双指针法来解决这个问题,遍历两个有序列表A和B,每次取当前指针所指的较小元素放入结果列表C,并相应地移动对应指针。以下是C语言的一个简单实现:
```c
#include <stdio.h>
#include <stdlib.h> // 用于malloc动态分配内存
// 定义顺序表节点结构体
typedef struct Node {
int data;
struct Node* next;
} ListNode;
// 合并两个有序链表并返回新的头节点
ListNode* mergeSortedLists(ListNode* listA, ListNode* listB) {
ListNode* dummyHead = (ListNode*) malloc(sizeof(ListNode)); // 创建虚拟头节点
dummyHead->next = NULL;
ListNode* current = dummyHead; // 初始化合并后的链表头
while (listA != NULL && listB != NULL) {
if (listA->data < listB->data) {
current->next = listA;
listA = listA->next;
} else {
current->next = listB;
listB = listB->next;
}
current = current->next;
}
// 将剩余未遍历的部分连接到结果链表末尾
if (listA != NULL) {
current->next = listA;
} else {
current->next = listB;
}
return dummyHead->next; // 返回合并后的链表的真正头节点
}
// 打印链表
void printList(ListNode* head) {
ListNode* temp = head;
while (temp != NULL) {
printf("%d -> ", temp->data);
temp = temp->next;
}
printf("NULL\n");
}
int main() {
// 假设有两个顺序表A和B,创建它们并填充数据
// ...
ListNode* listA = ...;
ListNode* listB = ...;
ListNode* mergedList = mergeSortedLists(listA, listB);
printList(mergedList); // 打印合并后的顺序表C
return 0;
}
```
在这个程序中,`mergeSortedLists`函数实现了合并两个有序链表的功能。
阅读全文