用C++写一个定义单向循环链表节点类型。 尾插法创建单向循环链表并返回头指针。 定义打印输出单向循环链表节点。 4.在main 函数中编写测试 分别创建循环链表La 和 Lb 编写合并算法,存储到Lc 编写输出Lc验证合并结果 源代码要有详细注释
时间: 2024-09-24 19:09:48 浏览: 43
首先,我们定义一个名为`Node`的结构体,用于表示单向循环链表的节点。这里包含一个整数值`data`,一个指向下一个节点的指针`next`,以及一个标志`isCycle`表示是否是循环链表:
```cpp
#include <iostream>
// 定义单向循环链表节点
struct Node {
int data;
Node* next; // 指向下一个节点
bool isCycle; // 是否形成循环
Node(int val = 0, Node* cycleStart = nullptr) : data(val), next(nullptr), isCycle(cycleStart != nullptr) {}
};
```
接下来,我们实现尾插法来创建单向循环链表,并返回头指针。这个函数会接收一个已经存在的非空链表`head`,一个新的值`val`,以及是否形成循环的标识。
```cpp
// 尾插法创建单向循环链表并返回头指针
Node* createCycleList(Node* head, int val, bool makeCycle = false) {
if (!head || !head->next) { // 如果链表为空或只有一个节点,将新节点直接设为头
head = new Node(val);
head->isCycle = makeCycle;
} else {
// 否则,插入新节点
Node* newNode = new Node(val);
newNode->next = head->next;
head->next->prev = newNode; // 更新前一个节点的next指向前一个节点,形成循环
if (makeCycle) {
newNode->isCycle = true;
head->next->next = head; // 关闭循环,使得next指针再次回到原头
}
head->next = newNode;
}
return head;
}
```
定义一个函数来打印输出单向循环链表节点。由于循环链表的特点,我们需要处理好循环的情况。
```cpp
void printCycleList(Node* current, std::string prefix = "") {
while (current != nullptr) {
std::cout << prefix << current->data << " ";
if (current == current->next && current->isCycle) {
std::cout << "(cycle)";
}
current = current->next;
if (current == head && current->isCycle) {
break; // 避免无限循环
}
}
std::cout << std::endl;
}
```
在`main`函数中,我们可以分别创建两个循环链表`La`和`Lb`,然后合并它们。为了简化,这里假设我们有现成的`headLa`和`headLb`作为链表头指针:
```cpp
int main() {
// 创建链表 La 和 Lb
Node* headLa = ...; // 初始化 La 的头指针
Node* headLb = ...; // 初始化 Lb 的头指针
// 合并操作
Node* headLc = createCycleList(headLa, 0); // 先复制 La
headLc = createCycleList(headLc, 1, true); // 添加一个循环节点到 Lc
headLc = createCycleList(headLc, 2, false); // 添加另一个节点到 Lc
// 现在 headLc 是合并后的链表 Lc 的头
// 打印和验证合并结果
printCycleList(headLc, "[La] ");
printCycleList(headLb, "[Lb] ");
// 合并 Lb 到 Lc
headLc = createCycleList(headLc, 3, true); // 在 Lc 中添加 Lb 的首节点
headLc = createCycleList(headLc, 4, false);
printCycleList(headLc, "[Lc]"); // 输出合并后的链表 Lc
return 0;
}
```
阅读全文