链接列表中的后退遍历问题

Question

下面是C++编写的带有Node类和主函数的链表。列表正在使用"；next(("；函数，但是当使用"返回"遍历时产生执行时间误差；back(("；。

#include <iostream>
using namespace std;
class Node {
public:
int object;
Node *nextNode;
Node *prevNode;

public:

int get(){
return object;
}

void set(int object){
this->object = object;
}

Node* getNext(){
return nextNode;
}

void setNext(Node *nextNode){
this->nextNode = nextNode;
}

Node* getPrev(){
return prevNode;
}

void setPrev(Node *prevNode){
this->prevNode = prevNode;
}


};

class List {
public:
Node* headNode;
Node* currentNode;
int size;

public:

List(){
headNode = new Node();
headNode->setNext(NULL);
headNode->setPrev(NULL);
currentNode = NULL;
int size = 0;   
}

void add(int addObject){
Node* newNode = new Node();
newNode->set(addObject);

if(currentNode != NULL){
newNode->setNext(currentNode->getNext());
newNode->setPrev(currentNode);
currentNode->setNext(newNode);
currentNode = newNode;

}
else {
newNode->setNext(NULL);
newNode->setPrev(headNode);
headNode->setNext(newNode);
currentNode = newNode;
}

size++;

}

int get(){
if(currentNode != NULL) {
return currentNode->get();
}
} 

bool next(){
if(currentNode == NULL) return false;

currentNode = currentNode->getNext();

if(currentNode == NULL) return false;
else                    return true;

}

bool back(){
if(currentNode == NULL) return false;
currentNode = currentNode->getPrev();

if(currentNode == NULL) return false;
else return true;
}

void start(){
currentNode = headNode;
}

void remove() {
if (currentNode != NULL && currentNode != headNode){
delete currentNode;
size--;
}
}

int length() {
return size;
}

};

int main(){

List list;

list.add(5);
list.add(13); 
list.add(4);
list.add(8);
list.add(48);
list.add(12); 

list.start(); 

while(list.next()){
cout<<endl<<"Element: " << list.get() << endl;
}

cout<<endl<<"BACK"<<endl;
while(list.back()){
cout<<endl<<"Element: " << list.get() << endl;
} 
}

Back((函数应该以相反的方向(从末尾到开头(遍历列表。。相反的方式。有时这段代码会挂起CPU，有时它只运行next((函数，而对于back((函数则保持静默而不执行任何操作。

Answer 1

首先，让我们修复代码：

bool next(){
if(currentNode == nullptr)  return false; 
// if next is null we are at the end, don't go futher
if (  currentNode->getNext() == nullptr ) return false;
currentNode = currentNode->getNext();
return true;
}

bool back(){
if(currentNode == nullptr) return false;

// if prev is head, we are at the start, stop here 
if ( currentNode->getPrev() == headNode) return false;
currentNode = currentNode->getPrev();

return true;
}

---

逻辑：

// we are at the last element, so we have to print BEFORE going back
do{
cout<<endl<<"Element: " << list.get() << endl;
} while (list.back());

演示实时

---

警告：

警告：未使用的变量"大小">

在这种情况下，有这个警告是可以的，如果你想消除它，你可以使用方法length()。

在成员函数'int List:：get(('中：警告：控制达到非无效功能的末尾[-转弯类型]

在您的get方法if(currentNode == nullptr )中，您不返回任何内容，它将导致错误。解决此问题的一种方法是将throw作为异常。

int get(){
if(currentNode == nullptr ) {
throw std::logic_error("CurrentNode is null");
}
return currentNode->get();
} 

我个人认为最好的解决方案是：对List的所有成员函数进行编码，使currentNode不能为null。

---

内存管理

您使用new创建节点，但从未使用delete，因此内存泄漏。查看valgrind(网站或这篇不错的帖子(，它非常有用。

valgrind ./leaky --leak-check=full
....
==3225== HEAP SUMMARY:
==3225==     in use at exit: 168 bytes in 7 blocks
==3225==   total heap usage: 9 allocs, 2 frees, 73,896 bytes allocated
==3225== 
==3225== LEAK SUMMARY:
==3225==    definitely lost: 24 bytes in 1 blocks 
==3225==    indirectly lost: 144 bytes in 6 blocks
==3225==      possibly lost: 0 bytes in 0 blocks
==3225==    still reachable: 0 bytes in 0 blocks
==3225==         suppressed: 0 bytes in 0 blocks

是的，valgrind发现了泄漏。

你需要添加一个析构函数。

~List(){
// first be sure that we are at one end
while (next()) {}

while (back())
{
std::cout << "delete the node we just left : " << currentNode->getNext()->get() << std::endl;
delete currentNode->getNext();
}
// don't forget this one (without valgrind I will have miss it!)
delete currentNode;
std::cout << "finaly we clear the head" << std::endl;
delete headNode;
}

但现在如果我们写：

List list2 = list;

我们得到了：

double free or corruption (fasttop)

因为我们有两个对象试图删除相同的内存。

我们可以禁止复制：

List(const List&) = delete;
List& operator=(const List&) = delete;

通常大多数内存管理都是通过智能指针完成的。

---

能见度：

对属性使用private：

private :
int object;
Node *nextNode;
Node *prevNode;

和

private:
Node* headNode;
Node* currentNode;
size_t size = 0;

最终版本：演示

使用valgrind检查：

==3532== HEAP SUMMARY:
==3532==     in use at exit: 0 bytes in 0 blocks
==3532==   total heap usage: 9 allocs, 9 frees, 73,896 bytes allocated
==3532== 
==3532== All heap blocks were freed -- no leaks are possible

无泄漏，一切正常；(

希望它能有所帮助！