插入链表

Question

我在LinkedListinsertAfter功能不工作的权利内。

我真的很感激，如果有人能指出什么是错我的代码。

谢谢:)

下面的列表结构：

struct ListItem 
{ 
    T value; 
    ListItem<T> *next; 
    ListItem<T> *prev; 

    ListItem(T theVal) 
    { 
     this->value = theVal; 
     this->next = NULL; 
     this->prev = NULL; 
    } 
}; 

，这里是我的功能列表中插入：

template <class T> 
void LinkedList<T>::insertAfter(T toInsert, T afterWhat) 
{ 
if(head!=NULL)  
{ 
    ListItem<T>*p; 
    p=head; 
    while(p->next!=NULL) 
    { 
    if(p->value==afterWhat) 
    { 
    ListItem<T>*k; 
    k=new ListItem<T>(toInsert); 
    k->next=p->next; 
    p->next=k; 
    k->prev=p; 
    k->next->prev=k; 
    } 
    else 
    p=p->next; 
    } 
} 
else 
{ 
    head= new ListItem<T>(toInsert); 
} 
//p=NULL; 
} 

Answer 1

首先，不应该插入如果进行，找不到afterWhat。

所以，也就没有插入当任：列表为空，或者afterWhat并不在列表中存在。

其次，while(p->next!=NULL)循环将永远不会检查列表的最后一个元素afterWhat，因为它在最后一个之前结束其迭代。

所以，如果afterWhat是列表的最后一个元素，它会检测不出来。

第三，循环应尽快插入完成破。稍后，p的值也可以确定是否找到afterWhat，并且如果需要可以显示适当的结果。

第四，因为现在的afterWhat的情况下进行的最后一个元素也被处理，我们还需要做出任何更改之前检查p->next!=NULL，因为它p可能是最后一个元素，在这种情况下，没有什么需要完成p->next。

需要注意的是，你不能插入使用insertAfter功能head位置的元素，因为没有什么是head之前，可在这种情况下，作为afterWhat。

的insertAfter功能，应该是这样的：

template <class T> 
void LinkedList<T>::insertAfter(T toInsert, T afterWhat) 
{ 
if(head != NULL) 
{ 
    ListItem<T>*p; 
    p=head; 
    while(p != NULL) 
    { 
    if(p->value==afterWhat) 
    { 
    ListItem<T>*k; 
    k = new ListItem<T>(toInsert); 
    k->next = p->next; 
    p->next = k; 
    k->prev=p; 
    if(k->next != NULL) 
    k->next->prev = k; 
    break; 
    } 
    else 
    p = p->next; 
    } 

    if(p == NULL) 
    cout<<"afterWhat, not found, hence no insertion made\n"); 
    else 
    cout<<"Inserted!\n"; 
} 
else 
{ 
    cout<<"List is empty, hence afterWhat, not found\n"); 
} 
}