c++ - 链表 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 )。所以我认为这只是为了学习链表工作原理的基础练习。

你也可以有一个双链表，其中每个节点不仅有指向列表中下一个节点的链接，也有指向前一个节点的链接。上面概述的原则是相同的。