小贝子编程

对单链表的混淆



所以我最近在学习链表。这些功能有点简单，但是当我检查输出时，它总是很混乱。

在测试文件中，从测试 1 到测试 3，我更改了 std：：cout 行的位置，在测试 1 中没有显示输出。我不知道一个简单的cout线或行的顺序如何影响链表的输出方式。这非常令人困惑(每个测试的输出中都提供了详细信息(

我的函数，特别是InsertHead，SearchList，InsertAfter，PreviousNode有时在特定输出中是正确的。

对于我的 InsertBefore 函数，我使用一个名为 PreviousNode 的函数来获取指向当前节点的上一个节点的指针，并使用 InsertAfter 在前一个节点之后插入一个节点。然而，结果是无限的。(我不允许使用双向链表(

文件节点.h

#include <iostream>
using namespace std;
template <typename T>
struct Node{
T _item;
Node<T>* _next;
Node() {
_item = T();
_next = NULL;
}
Node(T item){
_item = item;
_next = NULL;
}
// Print the value of a node
friend std::ostream& operator <<(std::ostream& outs, const Node<T> &printMe){
outs << "[" << printMe._item << "]";
}
};
// Print the entire linked list
template <typename T>
void PrintList(Node<T>* head){
Node<T>* walker = head;
while(walker != NULL){
cout << *walker;
cout << "->";
walker = walker->_next;
}
cout << "|||";
}
// Insert an item to the head
template <typename T>
Node<T>* InsertHead(Node<T>* &head, const T& item){
Node<T>* temp = new Node<T>(item);
temp->_next = head;
head = temp;
return head;
}
// Search an element in list, return the pointer to that node
template <typename T>
Node<T>* SearchList(Node<T>* head, const T& item){
Node<T>* temp = head;
// Iterate temp to find the match item
while (temp->_item != item && temp->_next != NULL)
temp = temp->_next;
if (temp->_item == item) // If found, return temp
return temp;
else
return NULL;
}
// find previous node
template <typename T>
Node<T>* PreviousNode(Node<T>* head, Node<T>* prevToThis) {
if (prevToThis == head)
return NULL;
else {
Node<T> *prev = head;
// Iterate it until it reaches the one before prevToThis
while(prev->_next != NULL && prev->_next != prevToThis)
prev = prev->_next;
return prev;
}
}    
template <typename T>
Node<T>* InsertAfter(Node<T>* afterThis, const T& insertThis){
// Create a temp node
Node<T>* temp;
temp->_item = insertThis;
if (afterThis->_next == NULL){
temp->_next = NULL;
afterThis->_next = temp;
}
else {
// Point temp to next node
temp->_next = afterThis->_next;
// Point mark node to temp
afterThis->_next = temp;
}
return temp;
}

// Insert an item before a node
template <typename T>
Node<T>* InsertBefore(Node<T>*& head, Node<T>* beforeThis, T insertThis){
Node<T> *prev = PreviousNode(head, beforeThis);
Node<T>* temp;
// If current node is head node
if (beforeThis == head){
temp->_item = insertThis;
temp->_next = head;
head = temp;
}
// Other nodes
else {
temp = InsertAfter(prev, insertThis);
}
return temp;
}

文件主.cpp，测试 1，运行 InsertAfter 函数：

int main(){
Node<int>* head = NULL;
for (int i = 0; i < 10; i++)
InsertHead(head, i * 10);
PrintList(head);
cout << endl;
Node<int> *pos_50 = SearchList(head, 50);
cout << "Insert 500 after 50: ";
cout << endl;
InsertAfter(pos_50, 500);
PrintList(head);
Node<int> *pos_0 = SearchList(head, 0);
cout << "Insert 600 after 0: ";
cout << endl;
InsertAfter(pos_0, 600);
PrintList(head);
}

输出，测试 1，其余代码不输出

[90]->[80]->[70]->[60]->[50]->[40]->[30]->[20]->[10]->[0]->|||
Insert 500 after 50:

文件 main.cpp，测试 2：运行 InsertAfter 函数，与测试 1类似，但更改 std：：cout 行的位置：

int main(){
Node<int>* head = NULL;
for (int i = 0; i < 10; i++)
InsertHead(head, i * 10);
PrintList(head);
cout << endl;
cout << "Insert 500 after 50: ";
cout << endl;
Node<int> *pos_50 = SearchList(head, 50);
InsertAfter(pos_50, 500);
PrintList(head);
cout << endl;
cout << "Insert 600 after 0: ";
cout << endl;
Node<int> *pos_0 = SearchList(head, 0);
InsertAfter(pos_0, 600);
PrintList(head);
}

输出测试2：改变std：：cout线的位置后，显示输出的其余

部分
[90]->[80]->[70]->[60]->[50]->[40]->[30]->[20]->[10]->[0]->|||
Insert 500 after 50: 
[90]->[80]->[70]->[60]->[50]->[500]->[40]->[30]->[20]->[10]->[0]->|||
Insert 600 after 0: 
[90]->[80]->[70]->[60]->[50]->[500]->[40]->[30]->[20]->[10]->[0]->[600]->|||

文件主.cpp测试 3，运行插入后与测试 1类似，但只运行一次：

int main() {
Node<int>* head = NULL;
for (int i = 0; i < 10; i++)
InsertHead(head, i * 10);
PrintList(head);
cout << endl;
Node<int> *pos_50 = SearchList(head, 50);
cout << "Insert 500 after 50: ";
cout << endl;
InsertAfter(pos_50, 500);
PrintList(head);
}

输出测试3，输出如图所示：

[90]->[80]->[70]->[60]->[50]->[40]->[30]->[20]->[10]->[0]->|||
Insert 500 after 50: 
[90]->[80]->[70]->[60]->[50]->[500]->[40]->[30]->[20]->[10]->[0]->|||

文件main.cpp测试4，运行测试4，把Insert放在类似测试3之后，然后检查上一页节点

int main() {
Node<int>* head = NULL;
for (int i = 0; i < 10; i++)
InsertHead(head, i * 10);
PrintList(head);
cout << endl;
cout << "Insert 500 after 50: ";
cout << endl;
Node<int> *pos_50 = SearchList(head, 50);
InsertAfter(pos_50, 500);
PrintList(head);

cout << "Previous node before 50: " << *PreviousNode(head, pos_50);
}

输出：上一个节点为0，不正确

[90]->[80]->[70]->[60]->[50]->[40]->[30]->[20]->[10]->[0]->|||
Insert 500 after 50: 
[90]->[80]->[70]->[60]->[50]->[500]->[40]->[30]->[20]->[10]->[0]->|||
Previous node before 50: [0]

File main.cpp测试 5，运行 InsertAfter 和 PreviousNode 与测试 4类似，但我先运行 PreviousNode。

int main(){
Node<int>* head = NULL;
for (int i = 0; i < 10; i++)
InsertHead(head, i * 10);
PrintList(head);
cout << endl;

Node<int> *pos_50 = SearchList(head, 50);
cout << "Previous node before 50: " << *PreviousNode(head, pos_50);
cout << endl;
cout << "Insert 500 after 50: ";
cout << endl;
InsertAfter(pos_50, 500);
PrintList(head);
}

输出测试 5，与测试 4 类似，但输出正确：

[90]->[80]->[70]->[60]->[50]->[40]->[30]->[20]->[10]->[0]->|||
Previous node before 50: [60]
Insert 500 after 50: 
[90]->[80]->[70]->[60]->[50]->[500]->[40]->[30]->[20]->[10]->[0]->|||

主.cpp测试 6，仅运行 插入之前

int main(){
Node<int>* head = NULL;
for (int i = 0; i < 10; i++)
InsertHead(head, i * 10);
PrintList(head);
cout << endl;

Node<int> *pos_50 = SearchList(head, 50);
cout << "Insert 700 before 50: " << endl;
InsertBefore(head, pos_50, 700);
PrintList(head);
}

输出测试 6：结果无限显示

[700]->[700]->[700]->[700]->[700]->
我

真诚地希望你能看看它并向我解释为什么测试 1 没有显示输出的其余部分，为什么 PreviousNode 在 4 中因为 cout 行的微小变化，以及为什么 InsertBefore 有一个循环，即使我只使用了前面的函数。多谢！

您必须在operator<<中返回outs流。目前您什么也没返回。它应该是：

friend std::ostream& operator <<(std::ostream& outs, const Node<T> &printMe){
outs << "[" << printMe._item << "]";
return outs; // added missing return
}

此外，InsertAfter有一个悬空的指针。只需观察gcc发出警告(在GCC和Clang上使用-Wall运行所有编译，在Visual Studio上使用/w4运行所有编译(：

prog.cc: In function 'Node<T>* InsertAfter(Node<T>*, const T&) [with T = int]':
prog.cc:83:5: warning: 'temp' is used uninitialized in this function [-Wuninitialized]
83 |     temp->_item = insertThis;
|     ^~~~

有问题的代码是：

template <typename T>
Node<T>* InsertAfter(Node<T>* afterThis, const T& insertThis){
// Create a temp node
Node<T>* temp;
temp->_item = insertThis;

temp变量是指针，而不是节点。最初，它不指向任何特定内容，访问它是未定义的行为。您必须创建一个新节点：

template <typename T>
Node<T>* InsertAfter(Node<T>* afterThis, const T& insertThis){
// Create a temp node
auto temp = new Node<T>;
temp->_item = insertThis;

对于InsertBefore，它更复杂，因为有时需要一个新对象，有时不需要：

template <typename T>
Node<T>* InsertBefore(Node<T>*& head, Node<T>* beforeThis, T insertThis){
Node<T> *prev = PreviousNode(head, beforeThis);
Node<T>* temp;

所以最安全的做法是稍微重新组织代码：

if (beforeThis != head){
return InsertAfter(prev, insertThis);
}
auto temp = new Node<T>;
temp->_item = insertThis;
temp->_next = head;
head = temp;

一般说明：最好使用std::unique_ptr和std::make_unique而不是原始指针和new。如果可能，请完全避免new。如果正确使用std::unique_ptr，则悬空指针和内存泄漏的机会将大大减少。

此外，我强烈建议使用C++最佳实践。例如，对类的用户隐藏实现详细信息，使用nullptr而不是NULL，在无法nullptr且不需要对指针进行操作时返回引用，尽可能使用return而不是通过引用参数进行修改，等等。

编辑

添加了在开发代码时查阅警告的建议。

相关内容

  • 没有找到相关文章

最新更新


热门标签：

javascript python java c# php android html jquery c++ css ios sql mysql arrays asp.net json python-3.x ruby-on-rails .net sql-server django objective-c excel regex ruby linux ajax iphone xml vba spring asp.net-mvc database wordpress string postgresql wpf windows xcode bash git oracle list vb.net multithreading eclipse algorithm macos powershell visual-studio image forms numpy scala function api selenium