根据一个单向链表,复制建立一个双向链表,然后输出双向链表
时间: 2024-10-16 22:13:46 浏览: 6
要根据一个单向链表(`Singly Linked List`)复制并创建一个新的双向链表(`Doubly Linked List`),你需要遍历原始链表,为每个节点添加一个对应的前后指针。以下是C++代码示例:
```cpp
#include <iostream>
// 定义单向链表节点结构体
struct Node {
int data;
Node* next;
};
// 定义双向链表节点结构体
struct DoublyNode {
int data;
DoublyNode* prev;
DoublyNode* next;
};
// 单向链表节点的复制函数
DoublyNode* copyToDoubly(Node* src) {
if (src == nullptr) return nullptr;
// 创建新的双向链表节点
DoublyNode* dst = new DoublyNode();
dst->data = src->data;
dst->prev = nullptr; // 新的节点没有前驱
// 将新节点添加到复制后的链表
if (src->next != nullptr) {
DoublyNode* current = dst;
while (src->next != nullptr) {
current->next = new DoublyNode();
current->next->data = src->next->data;
current->next->prev = current;
current = current->next;
src = src->next;
}
current->next = nullptr; // 处理最后一个节点
}
dst->next = nullptr; // 初始化尾部指针
return dst;
}
// 打印双向链表
void printList(DoublyNode* node) {
while (node != nullptr) {
std::cout << node->data << " ";
node = node->next;
}
std::cout << std::endl;
}
int main() {
// 假设你已经有了一个名为`sourceList`的单向链表实例
Node* sourceList = ...; // 实际上你需要提供一个已构建好的单向链表
// 使用`copyToDoubly`函数复制单向链表
DoublyNode* doubleLinkedList = copyToDoubly(sourceList);
// 打印新复制的双向链表
std::cout << "Copy of Doubly Linked List: ";
printList(doubleLinkedList);
// 清理内存
DoublyNode* temp = doubleLinkedList;
while (temp != nullptr) {
DoublyNode* nextTemp = temp->next;
delete temp;
temp = nextTemp;
}
return 0;
}
```
在这个例子中,我们首先定义了单向链表和双向链表的节点结构体。`copyToDoubly`函数接受单向链表的头节点,逐个复制节点并添加前后指针。`printList`函数用于打印双向链表的内容。
注意:这个代码假设你已经有一个完整的单向链表实例,并且知道如何处理其数据和连接。如果你还没有这样一个链表,你需要先构造或获取它。
阅读全文