用c语言编写一个算法,将两个有序线性表合并成一个有序线性表,要求简洁
时间: 2024-09-21 16:11:48 浏览: 61
数据结构 两个有序线性表的归并算法 西南交通大学
在C语言中,合并两个有序线性表可以使用双指针法。以下是合并过程的一个简单实现:
```c
#include <stdio.h>
#include <stdlib.h>
// 定义链表节点结构体
typedef struct Node {
int data;
struct Node* next;
} Node;
// 创建一个新的节点
Node* newNode(int value) {
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->data = value;
newNode->next = NULL;
return newNode;
}
// 合并两个有序链表
Node* mergeSortedLists(Node* list1, Node* list2) {
if (list1 == NULL) return list2; // 如果list1为空,直接返回list2
if (list2 == NULL) return list1; // 如果list2为空,直接返回list1
// 比较两个链表的头部节点,选择较小的那个
if (list1->data <= list2->data) {
list1->next = mergeSortedLists(list1->next, list2);
return list1;
} else {
list2->next = mergeSortedLists(list1, list2->next);
return list2;
}
}
// 打印链表
void printList(Node* head) {
while (head != NULL) {
printf("%d -> ", head->data);
head = head->next;
}
printf("NULL\n");
}
int main() {
// 初始化两个有序链表...
Node* list1 = createFirstList(); // 假设createFirstList()是一个创建第一个有序链表的函数
Node* list2 = createSecondList(); // 假设createSecondList()是一个创建第二个有序链表的函数
// 合并链表
Node* mergedList = mergeSortedLists(list1, list2);
// 打印合并后的链表
printList(mergedList);
return 0;
}
阅读全文