在 C++ 中实现循环链接列表的数据结构
本文将讲解如何用 C++ 实现一个循环链表数据结构。
在 C++ 中用成员函数实现循环单链表，在末端添加新元素并打印元素
循环链表可以表征为一个链表，其中最后一个节点指向链表的头部。本质上，列表中的节点形成一个圆圈，并且没有 nullptr 来划分列表的末尾。你可以利用循环链表来构建队列样式的数据结构。循环特征可以添加到双向链表和单链表中。
在这种情况下，我们将实现后一个。请记住，我们需要定义一个节点结构，其中包含一个指向下一个节点的指针和一个数据元素来构造一个单向链表。struct ListNode 对象代表我们实现的单个节点，并存储名为 data 的单个 string 对象，该对象将用作本示例的元素数据。请注意，可以在节点中存储任何自定义对象，如果对象相对较大，最好将其包含为指针。
一旦我们有了单个节点的结构，我们就可以定义一个 CircularList 类，它只有两个用于初学者的成员函数。通常，循环链表应该跟踪链表的头部或尾部；然而，实现者通常可以根据他们的需要自由地做出类设计决策。此外，CircularList 类存储两个单独的指针来表示列表的头部和结尾。
存储列表头/尾的指针可以是一个虚拟节点，也可以是一个带有数据的实际节点。在这个例子中，我们选择将 CircularList 类设计为没有虚拟指针。我们定义了一个构造函数来接受一个 string 参数来初始化循环列表中的第一个节点。请注意，类定义期间的设计选择通常会影响不同的变量，应根据潜在问题进行考虑。因此，下面的实现只是为了解释循环链表的概念的简单实现。
一旦使用构造函数初始化 CircularList 对象，我们就可以使用 insertNodeEnd 成员函数添加新元素。后者接受 string 参数并在列表末尾构造一个新元素。insertNodeEnd 函数使用 new 运算符分配新元素并相应地修改指针以在列表末尾插入节点。它还更新 end 数据成员以指向新分配的节点。
下一个示例中定义的另一个成员函数是 printNodes，它遍历列表以打印其内容，并且不接受任何参数。现在，为了更好地演示这个结构的用法，我们需要在 main 函数中添加一些驱动程序代码。我们选择初始化任意字符串的 vector，然后使用 for 循环将其插入到 CircularList 对象中。最后，我们调用 printNodes 函数将列表内容显示到终端。
#include <iostream>
#include <string>
#include <vector>
using std::cout; using std::cin;
using std::endl; using std::string;
using std::vector;
struct ListNode {
struct ListNode *next = nullptr;
string data;
} typedef ListNode;
class CircularList {
public:
explicit CircularList(string data) {
head = new ListNode;
head->next = head;
head->data = std::move(data);
end = head;
};
ListNode *insertNodeEnd(string data);
void printNodes();
private:
ListNode *head = nullptr;
ListNode *end = nullptr;
};
ListNode *CircularList::insertNodeEnd(string data) {
auto new_node = new ListNode;
new_node->next = end->next;
new_node->data = std::move(data);
end->next = new_node;
end = end->next;
return new_node;
}
void CircularList::printNodes() {
auto count = 0;
auto tmp = head;
while (tmp != end){
cout << "node " << count << " - data: " << tmp->data << endl;
tmp = tmp->next;
count++;
}
cout << "node " << count << " - data: " << tmp->data << endl;
}
int main() {
vector<string> data_set = { "Precise", "Quantal",
"Saucy", "Raring"};
CircularList clist("Xenial");
for (const auto &item : data_set) {
clist.insertNodeEnd(item);
}
clist.printNodes();
return EXIT_SUCCESS;
}
输出：
node 0 - data: Xenial
node 1 - data: Precise
node 2 - data: Quantal
node 3 - data: Saucy
node 4 - data: Raring
C++ 中实现在 List 开头插入新元素的析构函数和成员函数
请注意，前面的代码片段有一个巨大的问题，即没有定义析构函数；这意味着使用 CircularList 类的程序将泄漏内存，因为在程序退出之前不会释放在动态内存上创建的节点。
这个问题的解决方案是实现一个析构函数，该析构函数将遍历整个列表并使用 delete 运算符解除分配所有节点。因此，我们无需担心手动释放列表内存。一旦 CircularList 对象到达作用域末尾，它将被自动释放。
另一个要实现的有用函数是在列表的头部插入一个新元素； insertNodeHead 命令就是为了做到这一点而设计的。它只需要存储一个 string 参数并返回指向新分配节点的指针。请注意，insertNodeEnd 和 insertNodeHead 函数的返回值是另一种设计选择，其实现方式因程序员的决定而异。以下代码片段在 main 函数中包含类似的驱动程序代码，以测试和展示 CircularList 类的用法。
#include <iostream>
#include <string>
#include <vector>
using std::cout; using std::cin;
using std::endl; using std::string;
using std::vector;
struct ListNode {
struct ListNode *next = nullptr;
string data;
} typedef ListNode;
class CircularList {
public:
explicit CircularList(string data) {
head = new ListNode;
head->next = head;
head->data = std::move(data);
end = head;
};
ListNode *insertNodeEnd(string data);
ListNode *insertNodeHead(string data);
void printNodes();
~CircularList();
private:
ListNode *head = nullptr;
ListNode *end = nullptr;
};
ListNode *CircularList::insertNodeEnd(string data) {
auto new_node = new ListNode;
new_node->next = end->next;
new_node->data = std::move(data);
end->next = new_node;
end = end->next;
return new_node;
}
ListNode *CircularList::insertNodeHead(string data) {
auto new_node = new ListNode;
new_node->next = end->next;
new_node->data = std::move(data);
end->next = new_node;
head = end->next;
return new_node;
}
CircularList::~CircularList() {
while (head != end) {
auto tmp = head;
head = head->next;
delete tmp;
}
delete head;
}
void CircularList::printNodes() {
auto count = 0;
auto tmp = head;
while (tmp != end){
cout << "node " << count << " - data: " << tmp->data << endl;
tmp = tmp->next;
count++;
}
cout << "node " << count << " - data: " << tmp->data << endl;
}
int main() {
vector<string> data_set = { "Precise", "Quantal",
"Saucy", "Raring"};
CircularList clist("Xenial");
for (const auto &item : data_set) {
clist.insertNodeEnd(item);
}
clist.printNodes();
cout << " ----------------------------------- " << endl;
clist.insertNodeHead("Bionic");
clist.insertNodeEnd("Zeisty");
clist.printNodes();
return EXIT_SUCCESS;
}
输出：
node 0 - data: Xenial
node 1 - data: Precise
node 2 - data: Quantal
node 3 - data: Saucy
node 4 - data: Raring
-----------------------------------
node 0 - data: Bionic
node 1 - data: Xenial
node 2 - data: Precise
node 3 - data: Quantal
node 4 - data: Saucy
node 5 - data: Raring
node 6 - data: Zeisty
Founder of DelftStack.com. Jinku has worked in the robotics and automotive industries for over 8 years. He sharpened his coding skills when he needed to do the automatic testing, data collection from remote servers and report creation from the endurance test. He is from an electrical/electronics engineering background but has expanded his interest to embedded electronics, embedded programming and front-/back-end programming.
LinkedIn