合并两个 线性表的代码
时间: 2024-09-12 11:11:42 浏览: 20
合并两个线性表(通常是单链表)可以使用迭代或递归的方式实现。这里我给你提供一个基本的迭代方法,它创建了一个新的链表来存储合并后的元素。
```c
#include <stdio.h>
#include <stdlib.h>
// 定义链表节点结构
typedef struct Node {
int data;
struct Node* next;
} Node;
// 创建新节点
Node* createNode(int value) {
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->data = value;
newNode->next = NULL;
return newNode;
}
// 合并两个已排序链表
Node* mergeSortedLists(Node* list1, Node* list2) {
Node* result = NULL; // 结果链表的头指针,初始化为NULL
if (list1 == NULL) return list2; // 如果list1为空,直接返回list2
if (list2 == NULL) return list1; // 如果list2为空,直接返回list1
// 比较两个列表的当前节点
if (list1->data <= list2->data) {
result = list1; // 将较小的节点添加到结果链表
list1 = list1->next; // 移动到下一个节点
} else {
result = list2; // 否则,较大的节点添加到结果链表
list2 = list2->next;
}
// 重复上述过程,直到其中一个链表为空
while (list1 && list2) {
if (list1->data <= list2->data) {
result->next = list1;
list1 = list1->next;
} else {
result->next = list2;
list2 = list2->next;
}
result = result->next; // 移动到下一个结果节点
}
// 添加剩余的一个链表(如果还有)
if (list1) result->next = list1;
else result->next = list2;
return result;
}
// 打印链表
void printList(Node* node) {
while (node != NULL) {
printf("%d -> ", node->data);
node = node->next;
}
printf("NULL\n");
}
int main() {
Node* list1 = createNode(1);
list1->next = createNode(3);
list1->next->next = createNode(5);
Node* list2 = createNode(2);
list2->next = createNode(4);
list2->next->next = createNode(6);
Node* mergedList = mergeSortedLists(list1, list2);
printList(mergedList); // 输出: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> NULL
return 0;
}
```
在这个例子中,我们首先定义了链表节点结构,然后创建一个`mergeSortedLists`函数,它接受两个链表的头部指针,比较它们的当前节点并合并。最后,我们在`main`函数中创建两个链表并打印合并后的新链表。
如果你有其他疑问,比如如何处理未排序的链表、数组或其他数据结构,或是对这个代码有特定需求,请告诉我。