用c语言将两个有序单循环链表La和Lb合并为一个新的有序链表,并输出一次。
时间: 2024-04-29 21:24:25 浏览: 107
以下是使用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
```
阅读全文