在雙鏈表中搜索和刪除

Question

我想在雙鏈表中搜索某些內容並將其刪除。

我的問題是我失去了以前和我想刪除的節點的節點。

這裏是我的代碼：

int delnode(string moviename) 
     { 
      node *temp,*del; 
      //check empty 
      if(!head) 
       { 
        cout<<"empty"; 
       } 
      else 
       { 
        temp=head; 
       while (temp->next!=NULL) 
        { 

         if (temp->title==moviename) 
          { 
           del=temp; 
           temp=temp->previous; 
           temp->next=del->next; 
           delete del; 
          } 
         temp=temp->next; 
        } 
       } 
     } 

例如，如果我有5部電影，MOVIE1，電影2，MOVIE3，movie4，movie5並希望刪除MOVIE3我的名單將是MOVIE1，movie4，movie5：S

Answer 1

你讓自己變得非常困難。您的代碼有很多的問題，包括：

• 未能正確連接以前的指針
• 未能佔最後節點刪除。
• 如果它是前景節點，則無法提前讀取指針。

考慮，我認爲這是你想要什麼，我強烈建議您仔細審視它，甚至通過它加強在調試器來看看它是如何工作的。

void delnode(const std::string& moviename) 
{ 
    // pp holds the address of the pointer that will 
    // eventually point to our node being deleted. 
    node **pp = &head; 

    // skip nodes until we find a match 
    while (*pp && (*pp)->title.compare(moviename)) 
     pp = &(*pp)->next; 

    if (*pp) 
    { 
     node *tmp = *pp; 
     if ((*pp = tmp->next)) // assignment-eval intentional 
      (*pp)->previous = tmp->previous; 
     delete tmp; 
    } 
} 

這解決了一些問題，其中包括

• 正確更新頭指針，如果它是符合字符串的節點。
• 正確接線next和previous所有正確的指針
• 正確刪除列表中的最後節點如果這是你的嫌疑犯節點。
• 如果頭指針爲空，則什麼也不做。

Answer 2

您並未更新temp->next末尾的previous鏈接。

由於您使用的是雙鏈表，因此您需要在delete del行之前添加temp->next->previous = temp。

Answer 3

你有幾個問題。

如果你的列表只有一個項目，你將永遠不會測試它，因爲

if (temp->next != NULL) 

如果你的產品在要刪除列表的頭，你不更新頭你的代碼會崩潰，因爲你不測試那個temp-> previous是有效的。

如果你刪除一個項目，你不會像@Leigh提到的那樣更新返回指針。

這是我上取消我的列表模板的項目代碼：

void untie_pointer(_Tp * aptr) 
{ 
    if (aptr) 
    { 
     if (aptr-> prior()) { aptr-> prev_-> next_= aptr-> next_ ; } 
      else { if (first_ == aptr) { first_= aptr-> next_ ; if (first_) { first_-> pr 
ev_= nullptr ; } } } 
     aptr -> prev_= nullptr ; 
     if (aptr-> next()) { aptr-> next_-> prev_= aptr-> prev_ ; } 
      else { if (last_ == aptr) { last_= aptr-> prev_ ; if (last_) { last_-> next 
_= nullptr ; } } } 
     aptr-> next_= nullptr ; 
    } 
} 

，因爲所有這些情況下，海灣合作委員會的STL的名單使用了定點對象的啓示。

Answer 4

這裏是我寫的檢查後，該節點

1.is在前面，沒有節點它的代碼。

2.is在前面，後面有節點。

3.節點是最後一個節點

4.A節點是在第n個位置

void deleteRear() 
{ 
if(n == NULL) 
{ 
cout <<"No People Found" << endl; 
} 
else 
{ 
node *temp1; 
if(n == NULL) 
{ 
cout<<"No People Found"<<endl; 
} 
else 
{ 
temp1 = start_ptr; 
if(temp1->prev == NULL && temp1->nxt == NULL) 
{ 
start_ptr = NULL; 
delete temp1; 
n = NULL; 
} 
else 
{ 
while (temp1->nxt != NULL) 
{ 
temp1 = temp1->nxt; 
end_ptr= temp1->prev; 
} 
end_ptr->nxt = NULL; 
delete temp1; 
cout<<end_ptr->name<<endl; 
} 
} 
} 
} 
void deleteAPerson() 
{ 
if(n == NULL) 
{ 
cout <<"No People Found" << endl; 
} 
else 
{ 
node *temp1; 
temp1 = start_ptr; 
while(temp1 != NULL) 
{ 
cout << "Name : " << temp1->name << endl; 

temp1 = temp1 ->nxt; 
} 
node *temp, *temp2, *temp3, *temp4; 
temp = start_ptr; 
string names; 
cout << "Please Enter Person's Name: >>"; 
cin >> names; 
while(temp->nxt != NULL && temp->name != names) 
{ 
temp = temp->nxt; 
} 
if (temp->name == names) 
{ 
if(temp->prev == NULL && temp->nxt == NULL) 
{ 
cout<<"Deleting Front"<<endl; 
cout<<"Only one person on the list"<<endl; 
temp = start_ptr; 
start_ptr = NULL; 
delete temp; 
n = NULL; 
} 
else if (temp->prev == NULL && temp->nxt != NULL) 
{ 
cout<<"Deleting Front"<<endl; 
cout<<"There are other people on the list"<<endl; 
temp2 = start_ptr; 
start_ptr = start_ptr->nxt; 
start_ptr->prev = NULL; 
delete temp2; 
} 
else if(temp->prev != NULL && temp->nxt == NULL) 
{ 
cout<<"Deleting End"<<endl; 
deleteRear(); 
} 
else 
{ 
current = temp; 
current->prev->nxt = current->nxt; 
current->nxt->prev = current->prev; 
delete current; 
} 
} 
else 
{ 
cout<<"No such person exists"<<endl; 
} 
} 
}