1

我或多或少地了解了单链表背后的基本思想，但是在将元素插入双链表时遇到了麻烦。基本上我无法将 prev 和 next 指针链接到适当的节点。提前感谢您的帮助。这是我的代码的样子。

链表.h

template <class T>
class LinkedList{
      protected:
        LinkedListNode<T>* head;
      public:
        LinkedList():head(NULL){}
        ~LinkedList();
        void insert(const T& x);
};


//inserting
template <class T>
void LinkedList<T>::insert(const T& x) {
 LinkedListNode<T>* head = new LinkedListNode<T>(head->prev, x, head->next);
 if(head != NULL){
         head->prev = head->next;
         head->next = head;
  }       
}

链表节点.h

class LinkedListNode{
      protected:
        LinkedListNode<T>* prev;
        T value;
        LinkedListNode<T>* next;
        LinkedListNode(LinkedListNode<T>* p, const T& x, LinkedListNode<T>* n):prev(p), value(x), next(n) {}
        ~doublyLinkedListNode();
        template <class S> friend class doublyLinkedList;
};

我尝试如下修改插入函数，但它给出了分段错误。我的实施有什么问题？

template <class T>
void LinkedList<T>::insert(const T& x) {
 LinkedListNode<T>* head;
 if(head == NULL){
        head->value = x;
        head->prev = NULL;
        head->next = head;

 }
else{   LinkedListNode<T>* newnode;
        newnode->value = x;
        newnode->prev = head->next;
        newnode->next = newnode;
        head = newnode;
 }
4

1 回答 1

1

你是可变阴影的受害者。

让我们看看你的原始版本：

//inserting
template <class T> void LinkedList<T>::insert(const T& x) {
   LinkedListNode<T>* head = new LinkedListNode<T>(head->prev, x, head->next);
   // ...

我们将剖析您的函数的第一条指令：

   LinkedListNode<T>* head; // not initialized value
   new LinkedListNode<T>(head->prev, x, head->next); // oh oh....

head是一个新变量，您的原始变量this->head被遮蔽。但即使你解决了这个问题，初始this->head状态仍然存在NULL，因此this->head->prev会导致分段错误。您在第二个版本中修复了后者，但仍然有问题：

模板

void LinkedList<T>::insert(const T& x) {
 LinkedListNode<T>* head; // #1
 if(head == NULL){
        // #2
        head->value = x;
        head->prev = NULL;
        head->next = head;

 }
else{   LinkedListNode<T>* newnode;
        newnode->value = x;
        newnode->prev = head->next; // #3
        newnode->next = newnode;    // #3
        head = newnode;
 }

第一个错误 ( #1) 同样是变量阴影。#2再次是分段错误，因为您没有为头部分配内存。

#3是逻辑错误。前一个节点应该是头本身，而节点后面的节点不应该是节点本身。

于 2012-10-06T16:49:14.997 回答