Visual Studio 中双向链表中的 C++ 读取访问冲突

Question

我能够使用 g++ 在 Linux 机器上编译我的代码并运行驱动程序。在我的 Windows 机器上编译和运行驱动程序时，我在 size() 方法中遇到了 ptr->next 语句的读取访问冲突错误。 (假设只有一个节点)在调试时，我可以按预期单步执行 while 语句，在第二遍中它继续通过 ptr != nullptr，即使没有节点也是如此。

添加节点和列表 size == 1 时会发生此错误。

我一直在查看所有陈述，但似乎无法找到我哪里出错了。任何关于此的信息都将不胜感激!

标题

#ifndef DEQUE_H
#define DEQUE_H
#include <iostream>

using namespace std;

template <class Object>
class Deque {
 public:
  Deque( );                                   // the constructor
  Deque( const Deque &rhs );                  // the copy constructor
  ~Deque( );                                  // the destructor

  bool isEmpty( ) const;                      // checks if a deque is empty.
  int size( ) const;                          // retrieves # deque nodes
  const Object &getFront( ) const;            // retrieve the front node
  const Object &getBack( ) const;             // retrieve the tail node

  void clear( );                              // clean up all deque entries.
  void addFront( const Object &obj );         // add a new node to the front
  void addBack( const Object &obj );          // add a new node to the tail
  Object removeFront( );                      // remove the front node
  Object removeBack( );                       // remove the tail node

  const Deque &operator=( const Deque &rhs ); // assignment

 private:
  struct DequeNode {                          // a deque node
    Object item;
    DequeNode *next;
    DequeNode *prev;
  };
  DequeNode *front;
  DequeNode *back;
};

#include "deque.cpp.h"
#endif

CPP

template <class Object>
Deque<Object>::Deque( ) {                          // the constructor
  front = back = NULL;
}

template <class Object>
Deque<Object>::Deque( const Deque &rhs ) {         // the copy constructor
  front = back = NULL;
  *this = rhs;
}

template <class Object>
Deque<Object>::~Deque( ) {                         // the destructor
  clear( );
}

template <class Object>
bool Deque<Object>::isEmpty( ) const {             // check if a deque is empty
  return front == NULL;
}

template <class Object>
int Deque<Object>::size( ) const {                 // retrieves # deque nodes
    int length = 0;
    DequeNode* ptr = front;

    while (ptr != nullptr) {
        length++;
        ptr = ptr->next;
    }
    return length;
}

template <class Object>
const Object &Deque<Object>::getFront( ) const {   // retrieve the front node
  if ( isEmpty( ) )
    throw "empty queue";
  return front->item;
}

template <class Object>
const Object &Deque<Object>::getBack( ) const {    // retrieve the tail node
  if ( isEmpty( ) )
    throw "empty queue";
  return back->item;
}

template <class Object>
void Deque<Object>::clear( ) {          // clean up all entries.
  while ( !isEmpty( ) )                 // dequeue till the queue gets empty.
    removeFront( );
}

template <class Object>
void Deque<Object>::addFront( const Object &obj ) {// add a new node to  front
  // Implement the function body.
  DequeNode* newNode = new DequeNode;
  newNode->item = obj;

  // if no nodes, new node is front and back
  if (isEmpty()){
    front = back = newNode;
  }

  // if one node, new front and back are established

  else if (size() == 1){
    back->prev = newNode;
    front = newNode;
    front->next = back;
  }

  // add to front and shift right
  else {
    DequeNode* oldFront = front;
    front->prev = newNode;
    front = newNode;
    front->next = oldFront;
    }
}

template <class Object>
void Deque<Object>::addBack( const Object &obj ) { // add a new node to tail
  // Implement the function body.
  DequeNode* newNode = new DequeNode;
  newNode->item = obj;

  // if no nodes, new node is front and back
  if (isEmpty()){
    front = back = newNode;
  }

  // if one node, new front and back are established
  else if (size() == 1){
    front->next = newNode;
    back = newNode;
    back->prev = front;
  }

  // add to back and shift left
  else {
    DequeNode* oldBack = back;
    back->next = newNode;
    back = newNode;
    back->prev = oldBack;
  }
}

template <class Object>
Object Deque<Object>::removeFront( ) {  // remove the front node
  // Implement the function body.

  if (isEmpty())
    throw "empty queue"; 

  // if only one node, return item, Deque is now NULL.
  else if (size() == 1){
    DequeNode* remove = front;
    Object result = remove->item; 
    front = back = NULL;

    delete remove;
    remove = NULL;

    return result;
    }

  // remove front node, shift right
  else {
    Object result = front->item;
    DequeNode* remove = front;
    front = front->next;
    front->prev = NULL;

    delete remove;
    remove = NULL;

    return result;
    }
}

template <class Object>
Object Deque<Object>::removeBack( ) {   // remove the tail node
  // Implement the function body.

  if (isEmpty())
     throw "empty queue";

  // if only one node, return item, Deque is now NULL.
  else if (size() == 1){
      DequeNode* remove = back;
      Object result = remove->item;
      front = back = NULL;

      delete remove;
      remove = NULL;

      return result;
    }

  // remove back node, shift left
  else {
    Object result = back->item; 
    DequeNode* remove = back;
    back = back->prev;
    back->next = NULL;

    delete remove;
    remove = NULL;

    return result;
    }
}

template <class Object>
const Deque<Object> &Deque<Object>::operator=( const Deque &rhs ) { // assign
  if ( this != &rhs ) { // avoid self assignment
    clear( );
    for ( DequeNode *rptr = rhs.front; rptr != NULL; rptr = rptr->next )
      addBack( rptr->item );
  }
  return *this;
}

司机

#include <iostream>
#include "deque.h"

using namespace std;

int main( ) {
  Deque<int> deque1;
  int item;

  for ( int j = 0; j < 5; j++ )
    deque1.addBack( j );
  for ( int j = 5; j < 10; j++ )
    deque1.addFront( j );

  Deque<int> deque2 = deque1;
  deque2.addBack( 10 );

  cout << "deque1: " << endl;
  while ( !deque1.isEmpty( ) )
    cout << deque1.removeFront( ) << endl;

  cout << "deque2: " << endl;
  while ( !deque2.isEmpty( ) )
    cout << deque2.removeBack( ) << endl;
}

Answer 1

确保在插入元素时正确设置了 prev 和 next 指针。

template <class Object>
void Deque<Object>::addFront( const Object &obj ) {// add a new node to  front
  // Implement the function body.
  DequeNode* newNode = new DequeNode;
  newNode->item = obj;

  //Set these pointers to proper values depending on the state of the queue.
  newNode->next = nullptr;
  newNode->prev = nullptr;

例如，当你的队列是空的，而你正在向其中插入一个项目时，

 // if no nodes, new node is front and back
 if (isEmpty()){
   front = back = newNode;
 }

不会初始化next 或prev 指针。因此，当您在迭代中到达此节点时，这些指针将不等于 nullptr，您将尝试访问无效内存。