用C语言编写一个算法,将两个循环链表a=(a1,a2...an-1,an)和b= (b1,b2...bm-1,bm)合并为一个循环链表c,
时间: 2024-03-16 12:46:43 浏览: 114
以下是C语言实现的算法,将两个循环链表合并为一个循环链表:
```c
#include <stdio.h>
#include <stdlib.h>
typedef struct node{
int data;
struct node *next;
}Node, *LinkList;
void CreateList(LinkList *L, int n)//创建循环链表
{
int i;
Node *p, *tail;
*L = (LinkList)malloc(sizeof(Node));
(*L)->next = NULL;
tail = *L;
for (i = 0; i < n; i++)
{
p = (Node*)malloc(sizeof(Node));
scanf("%d", &p->data);
tail->next = p;
tail = p;
}
tail->next = *L;//将链表尾结点指向头结点,形成循环链表
}
void MergeList(LinkList *La, LinkList *Lb, LinkList *Lc)//合并两个循环链表
{
Node *pa, *pb, *pc, *tail;
pa = (*La)->next;
pb = (*Lb)->next;
*Lc = pc = *La;//将Lc指向La的头结点,用于存储合并后的循环链表
tail = (*Lc)->next;//tail指向Lc的头结点的下一个结点
while (pa != *La && pb != *Lb)
{
if (pa->data <= pb->data)
{
tail->next = pa;
tail = pa;
pa = pa->next;
}
else
{
tail->next = pb;
tail = pb;
pb = pb->next;
}
}
tail->next = pa == *La ? pb : pa;
free(*Lb);//释放Lb的头结点
}
void PrintList(LinkList L)//输出循环链表
{
Node *p = L->next;
while (p != L)
{
printf("%d ", p->data);
p = p->next;
}
printf("\n");
}
int main()
{
int n, m;
LinkList La, Lb, Lc;
printf("请输入La的元素个数:");
scanf("%d", &n);
CreateList(&La, n);
printf("请输入Lb的元素个数:");
scanf("%d", &m);
CreateList(&Lb, m);
MergeList(&La, &Lb, &Lc);
printf("合并后的循环链表Lc为:");
PrintList(Lc);
return 0;
}
```
该算法首先遍历两个循环链表,将它们按照递增的顺序合并到一个新的循环链表Lc中。在遍历过程中,使用tail指针指向Lc的头结点的下一个结点,用于记录Lc的最后一个结点,方便后面插入新的结点。最后释放Lb的头结点,输出合并后的循环链表Lc。
阅读全文