插入在双向链表元素

我或多或少落后单链表的基本理念，但与在双向链表插入元素的麻烦。基本上我无法链接prev指针和下一个指针到适当的节点。在此先感谢您的帮助。这是我的代码的样子。插入在双向链表元素

LinkedList.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; 
    }  
}

LinkedListNode.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; 
}

来源

2012-10-06 intsymmetry

首先，在带箭头的纸上做指针。其次，当你有['std :: list']（http://en.cppreference.com/w/cpp/container/list）时不要创建你自己的列表。 –

@JoachimPileborg小点：创建自己的列表非常棒。你不应该使用它（除了测试它）。 – delnan

在你最新的'insert'代码中，当已经有一个成员变量'head'时，你声明一个局部变量'head'。后来，当你说'head'时，编译器无法猜出你的意思（或者说，它猜错了）。 – Beta

你是variable shadowing的受害者。

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

//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-06 16:49:14 Zeta

太好了，谢谢你的详细反馈。 – intsymmetry

插入在双向链表元素

回答

相关问题