用c语言将两个有序单循环链表La和Lb合并为一个新的有序链表,并输出一次。
时间: 2024-04-29 21:24:25 浏览: 105
C++版本将两个有序链表合并为一个新的有序链表并返回原理及代码实现
以下是使用C语言将两个有序单循环链表La和Lb合并为一个新的有序链表的代码:
```c
#include <stdio.h>
#include <stdlib.h>
typedef struct node {
int data;
struct node *next;
} Node;
Node *createList(int arr[], int n) {
Node *head, *p, *q;
head = (Node *)malloc(sizeof(Node));
head->data = arr[0];
head->next = NULL;
p = head;
for (int i = 1; i < n; i++) {
q = (Node *)malloc(sizeof(Node));
q->data = arr[i];
q->next = NULL;
p->next = q;
p = q;
}
p->next = head;
return head;
}
void printList(Node *head) {
Node *p = head;
do {
printf("%d ", p->data);
p = p->next;
} while (p != head);
printf("\n");
}
Node *mergeList(Node *La, Node *Lb) {
Node *p = La->next, *q = Lb->next, *r, *head;
r = head = (Node *)malloc(sizeof(Node));
head->next = head;
while (p != La && q != Lb) {
if (p->data <= q->data) {
r->next = p;
r = p;
p = p->next;
} else {
r->next = q;
r = q;
q = q->next;
}
}
if (p == La) {
r->next = q;
} else {
r->next = p;
}
return head;
}
int main() {
int arr1[] = {1, 3, 5, 7, 9};
int arr2[] = {2, 4, 6, 8, 10};
int n1 = sizeof(arr1) / sizeof(int);
int n2 = sizeof(arr2) / sizeof(int);
Node *La = createList(arr1, n1);
Node *Lb = createList(arr2, n2);
printf("La: ");
printList(La);
printf("Lb: ");
printList(Lb);
Node *Lc = mergeList(La, Lb);
printf("Lc: ");
printList(Lc->next);
return 0;
}
```
这个程序首先定义了一个结构体Node来表示链表中的节点。然后,它定义了一个createList函数来创建一个由给定数组构成的循环链表,并返回头节点。它还定义了一个printList函数来打印循环链表中的所有节点的数据。
程序的主要函数是mergeList,它将两个有序单循环链表La和Lb合并为一个新的有序链表Lc,并返回头节点。这个函数从La和Lb的第一个节点开始遍历,比较它们的数据,然后将它们中较小的一个加入到Lc中。当其中一个链表被遍历完时,它将把另一个链表中的剩余节点加入到Lc中。
在主函数中,程序创建了两个有序单循环链表La和Lb,并打印它们的内容。然后,它调用mergeList函数将它们合并为一个新的有序链表Lc,并打印它的内容。
当程序运行时,它将输出以下结果:
```
La: 1 3 5 7 9
Lb: 2 4 6 8 10
Lc: 1 2 3 4 5 6 7 8 9 10
```
阅读全文