LinkList C++刪除節點

Question

刪除中間節點時出現問題。如果我在中間放置一個位置，所有前面的節點都會消失，任何人都可以幫助我，謝謝！

它沒有任何問題，如果我刪除前面的一個，但在中間部分會有一些問題。

我現在被卡住了。

#include<iostream> 
#include<string> 
#include <limits> 
using namespace std; 
struct Student{ 
    string name; 
    int matricNo; 
    string course; 
    double cgpa; 
    Student* link; 
}; 

int main(){ 
    Student *head = NULL, *last, *newStudent, *target; 
    int menu = 0; 
    int select; 
    while(menu != 6){ 
    cout << "Student Database.\n"; 
    cout << "1.Add a student.\n"; 
    cout << "2.Delete a student.\n"; 
    cout << "3.View a student's information.\n"; 
    cout << "4.View all students' information.\n"; 
    cout << "5.View all students' information with CGPA of 3.0 or higher.\n"; 
    cout << "6.End program.\n"; 
    while(!(cin >> menu)){ 
     cin.clear(); 
     cin.ignore(numeric_limits<streamsize>::max(), '\n'); 
     cout << "Invalid input.\n"; 
    } 
    if(menu == 1){ 
    newStudent = new Student; 

    if(head == NULL) 
     head = newStudent; 

     cin.clear(); 
     cin.ignore(2000,'\n'); 
     cout << "Please enter the student's name : "; 
     getline(cin, newStudent -> name); 
     cin.clear(); 
     cout << "Please enter the Matric Number  : "; 
      while(!(cin >> newStudent -> matricNo)){ 
      cin.clear(); 
      cin.ignore(numeric_limits<streamsize>::max(), '\n'); 
      cout << "Invalid input. Please enter a number.\n"; 
     } 
     cin.clear(); 
     cin.ignore(2000,'\n'); 
     cout << "Please enter the Course : "; 
     getline(cin, newStudent -> course); 
     cin.clear(); 
     cout << "Please enter the student's CGPA : "; 
      while(!(cin >> newStudent -> cgpa) || newStudent -> cgpa > 4 || newStudent -> cgpa < 0){ 
      cin.clear(); 
      cin.ignore(numeric_limits<streamsize>::max(), '\n'); 
      cout << "Invalid input. Please enter a value between 0.00 and 4.00\n"; 
     } 
     newStudent -> link = NULL; 

    if(last != NULL) 
     last -> link = newStudent; 

    last = newStudent; 
    system("cls"); 
    } 

    if(menu == 2){ 
     if(head != NULL){ 
     cout << "Please enter the matric number of a student : "; 
     while(!(cin >> select)){ 
     cin.clear(); 
     cin.ignore(numeric_limits<streamsize>::max(), '\n'); 
     cout << "Invalid input.\n"; 
     } 
      for(Student* p = head; p != NULL; p = p -> link){ 
       if(p -> matricNo == select){ 
        target = p; 
        if(head != NULL) 
        head = p -> link; 
        target -> link = NULL; 
        delete target; 
       } 
      } 
     } 
     else if(head == last){ 
      head -> link=NULL; 
      last -> link=NULL; 
     } 
     else 
      cout << "No students in the database.\n"; 
    } 
    if(menu == 3){ 

     if(head != NULL){ 
     cout << "Please enter the matric number of a student : "; 
     while(!(cin >> select)){ 
     cin.clear(); 
     cin.ignore(numeric_limits<streamsize>::max(), '\n'); 
     cout << "Invalid input.\n"; 
     } 
      for(Student* p = head; p != NULL; p = p -> link){ 
       if(p -> matricNo == select){ 
       cout << "Student's Name : " << p -> name << endl; 
       cout << "Matric Number : " << p -> matricNo << endl; 
       cout << "Course   : " << p -> course << endl; 
       cout << "CGPA  : " << p -> cgpa << endl; 
       cout << "==================================\n"; 
       } 
      } 
     } 
     else 
      cout << "No students in the database.\n"; 
    } 
    if(menu == 4){ 
     if(head != NULL){ 
      for(Student* p = head; p != NULL; p = p -> link){ 
      cout << "Student's Name : " << p -> name << endl; 
      cout << "Matric Number : " << p -> matricNo << endl; 
      cout << "Course   : " << p -> course << endl; 
      cout << "CGPA  : " << p -> cgpa << endl; 
      cout << "==================================\n"; 
      } 
     } 
     else 
      cout << "No students in the database.\n"; 
    } 
    if(menu == 5){ 
     if(head != NULL){ 
      for(Student* p = head; p != NULL; p = p -> link){ 
       if(p -> cgpa >=3){ 
       cout << "Student's Name : " << p -> name << endl; 
       cout << "Matric Number : " << p -> matricNo << endl; 
       cout << "Course   : " << p -> course << endl; 
       cout << "CGPA  : " << p -> cgpa << endl; 
       cout << "==================================\n"; 
       } 
      } 
     } 
     else 
      cout << "No students in the database.\n";  
    } 
    if(menu == 6) 
     return 0; 
    } 
    system("PAUSE"); 
    return 0; 
} 

Answer 1

要刪除一個節點單鏈表的中間像你這樣，你首先需要之前找到節點要刪除的一個。這是因爲您需要將鏈接設置爲（要刪除的）節點鏈接。

有點圖形，可以說您的列表看起來是這樣的：

 
     +--------+  +--------+  +--------+ 
... --> | Node A | --> | Node B | --> | Node C | --> ... 
     +--------+  +--------+  +--------+ 

現在讓我們說你要刪除的「節點B」。要做到這一點，你必須做出的排行榜是這樣的：

 
        /---------------\ 
     +--------+ | +--------+ | +--------+ 
... --> | Node A | -/ | Node B | -+-> | Node C | --> ... 
     +--------+  +--------+  +--------+ 

現在「節點A」不鏈接到「節點B」，所以「節點B」是有效的不在列表中了。 「節點A」和「節點B」都鏈接到「節點C」並不重要，因爲你無法到達「節點B」，並且因爲下一步是刪除「節點B」的結構， 。

請注意，當您要刪除的節點是列表中的第一個時，會出現特殊情況。您還應該能夠處理列表中沒有找到節點的情況。

---

當然還有其他的解決方案（如通過UKMonkey說明），像使用標準std::list（或單聯std::forward_list）。所以我認爲這只是練習來學習鏈表如何工作的基礎。

您也可以有一個雙鏈表，其中每個節點不僅鏈接到列表中的下一個節點，而且還包含前一個鏈接。儘管上述原則是相同的。

Answer 2

當涉及遍歷一個單鏈表以查找和刪除列表中的某個現有節點時，一個簡單的範例轉換大大簡化了任務。

問題的範式轉換將使用指向列表中每個節點的指針，而不是指向列表中每個節點的指針。當你這樣做，if語句的典型尷尬林立即消失，並獲得由非常簡單，直接，算法代替：

for (Student **p=&head; *p; p=&(*p)->next) 
{ 
    if ((*p)->matricNo == select) 
    { 
     Student *node= *p; 
     *p=node->next; 
     delete node; 
     break; 
    } 
}