使用C语言,完成下列题目。 设ha=(a1,a2,…,an)和 hb=(b1,b2,…,bm)是两个带头结点的循环单链表,ha和hb是尾指针,分别指向ha和hb两个循环单链表中的最后一个结点,设计一个算法将这两个表合并为带头结点的循环单链表hc,hc是尾指针。完整的代码
时间: 2024-11-09 10:26:59 浏览: 16
c语言吃逗游戏源码===C语言小游戏源码
在C语言中,合并两个循环单链表可以按照以下步骤实现:
```c
#include <stdio.h>
#include <stdlib.h>
// 定义链表节点结构体
typedef struct Node {
int data;
struct Node* next;
} Node;
// 创建新节点并初始化
Node* createNode(int val) {
Node* newNode = (Node*)malloc(sizeof(Node));
if (!newNode) {
printf("Memory allocation failed.\n");
return NULL;
}
newNode->data = val;
newNode->next = newNode; // 循环链表的特性,头尾相连
return newNode;
}
// 合并两个循环链表
Node* mergeCircularLists(Node* ha, Node* hb) {
if (!ha || !hb || ha->next == ha) { // 如果其中一个链表为空或者只有一个元素
return ha ? ha : hb;
}
// 找到两个链表的公共前驱节点
Node* preCommon = NULL;
Node* pa = ha;
Node* pb = hb;
while (pa != pb) {
pa = pa->next;
if (pa == ha) {
preCommon = pb;
} else {
pb = pb->next;
}
}
// 将hb的链表接到ha之后
Node* tail = ha;
for (; tail != preCommon; tail = tail->next) {
}
tail->next = hb;
ha->next = hb->next;
return ha; // 返回新的链表头节点
}
// 打印循环链表
void printList(Node* head) {
Node* temp = head;
do {
printf("%d ", temp->data);
temp = temp->next;
} while (temp != head);
printf("\n");
}
int main() {
// 测试示例
Node* ha = createNode(1);
ha->next = createNode(2);
ha->next->next = createNode(3);
ha->next->next->next = ha;
Node* hb = createNode(4);
hb->next = createNode(5);
hb->next->next = createNode(6);
hb->next->next->next = hb;
Node* hc = mergeCircularLists(ha, hb);
printf("Merged list: ");
printList(hc);
return 0;
}
```
这段代码首先创建了两个循环单链表`ha`和`hb`作为示例,并合并它们为一个新的循环链表`hc`。注意,实际应用中你需要处理链表为空的情况,并根据实际情况输入或构造链表。
阅读全文