将俩个顺序表合并成一个新的顺序表,并返回顺序表c语言
时间: 2024-11-03 11:13:16 浏览: 8
c语言数据结构顺序表合并
在C语言中,将两个已排序的顺序表合并成一个新的有序顺序表,通常可以采用迭代或递归的方式来实现。这里提供一种简单的迭代方法:
```c
#include <stdio.h>
#include <stdlib.h>
// 定义链表节点结构体
typedef struct Node {
int data;
struct Node* next;
} Node;
// 合并两个有序链表
Node* mergeSortedLists(Node* list1, Node* list2) {
// 创建新链表头结点
Node* head = NULL;
Node* tail = NULL;
// 指针分别指向两个列表的头部
if (list1 != NULL && list2 != NULL) {
// 如果两个列表都不为空,选择较小的元素作为新链表的第一个
if (list1->data <= list2->data) {
head = list1;
tail = list1;
} else {
head = list2;
tail = list2;
}
// 遍历两个列表,每次添加较小的元素到新链表
while (list1 != NULL && list2 != NULL) {
if (list1->data <= list2->data) {
tail->next = list1;
tail = list1;
list1 = list1->next;
} else {
tail->next = list2;
tail = list2;
list2 = list2->next;
}
}
// 如果其中一个列表遍历完还没结束,则将其剩余部分加到新链表末尾
if (list1 != NULL)
tail->next = list1;
else if (list2 != NULL)
tail->next = list2;
}
return head; // 返回合并后的链表头指针
}
// 打印链表函数
void printList(Node* node) {
while (node != NULL) {
printf("%d -> ", node->data);
node = node->next;
}
printf("NULL\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 = NULL;
Node* list2 = (Node*)malloc(sizeof(Node));
list2->data = 2;
list2->next = (Node*)malloc(sizeof(Node));
list2->next->data = 4;
list2->next->next = NULL;
// 合并两个链表
Node* mergedList = mergeSortedLists(list1, list2);
// 打印结果
printf("Merged List: ");
printList(mergedList);
return 0;
}
```
在这个例子中,我们首先检查两个链表是否非空,然后比较每个节点的数据,选择较小的节点加入新链表。最后打印出合并后的有序链表。
阅读全文