插入鏈表

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"); 
} 
}