链式有序表的合并C语言
时间: 2023-05-25 08:03:54 浏览: 92
假设有两个有序链表L1和L2,它们都是链式结构,现在需要将这两个链表合并成一个有序链表,如下所示是一个C语言的实现示例:
```
#include <stdio.h>
#include <stdlib.h>
typedef struct node {
int data;
struct node *next;
}Node, *LinkedList;
// 链表的初始化,传入一个头指针
void initList(LinkedList *L) {
*L = (LinkedList)malloc(sizeof(Node));
(*L)->next = NULL;
}
// 在链表头插入一个元素,即使链表仍然有序
void insertHead(LinkedList L, int value) {
Node *temp = (Node*)malloc(sizeof(Node));
temp->data = value;
temp->next = L->next;
L->next = temp;
}
// 合并两个有序链表
LinkedList mergeList(LinkedList L1, LinkedList L2) {
LinkedList L3 = (LinkedList)malloc(sizeof(Node));
Node *tail = L3; // L3的尾指针
while (L1 && L2) {
if (L1->data <= L2->data) {
tail->next = L1;
tail = L1;
L1 = L1->next;
}
else {
tail->next = L2;
tail = L2;
L2 = L2->next;
}
}
if (L1)
tail->next = L1;
if (L2)
tail->next = L2;
return L3->next; // L3的头指针
}
// 遍历链表并输出每一个元素的值
void printList(LinkedList L) {
Node *p = L->next;
while (p) {
printf("%d ", p->data);
p = p->next;
}
}
int main() {
LinkedList L1, L2;
initList(&L1);
initList(&L2);
insertHead(L1, 6);
insertHead(L1, 4);
insertHead(L1, 2);
insertHead(L2, 5);
insertHead(L2, 3);
insertHead(L2, 1);
LinkedList L3 = mergeList(L1, L2);
printList(L3);
return 0;
}
```
通过以上代码可以实现两个有序链表的合并,并将结果输出。当然,在实践中,还需要考虑其他的因素,比如链表是否空等等。