如何删除链表中的特定节点

Question

我遇到了一个问题，我似乎无法找到一个特定的节点，然后从链表中删除该节点。我试图创建最后显示的 while 循环，将 head 的内存分配循环两次，其中包含节点，然后将其删除，但如果我将 deleteNode 设置为 2，它似乎会删除两个节点。

void delete_list(Book *&head, Book *&last){
    if (head == NULL)
    {
        cout << "Database is already empty! \n";
    }
    else if (head == last){
        delete head;
        head = NULL;
        last = NULL;
    }
    else
    {
        cout << "Please enter the number of the node you would like to delete \n";
        cin >> deleteNode;

        Book* new_book = head;

        while(deleteNode>0) {
            head = head -> next;
            deleteNode--;
        }
        delete new_book;
    }
}


#include <iostream>
#include <string>
using namespace std;



struct Book{

    string title;
    string author;
    string publisher;
    int publishYear;
    int isbn;
    Book* next;
};

void add_node(Book*&, Book*&);
void print_list(Book*);
void delete_list(Book*& , Book*& );
int deleteNode;


int main()
{

    Book* head = NULL;
    Book* last = NULL;

  char option;
    do{

        cout << "Press required option: \n" "To Add Book detail   [A]\n"
                "To Print Book details   [P]\n" "To Delete Book details   [D]\n"
                "Quit  [Q]\n";
                cin >> option;

      switch(option){
          case 'A':
          add_node(head, last);
          break;

          case 'P':
          print_list(head);
          break;

          case 'D':
          delete_list(head, last);

          case 'Q':
          break;

          default:
          cout << "Invalid Input" << endl;

      }
    } while (option != 'Q');

    return 0;
}


void add_node(Book *&head, Book *&last){
    //Cheaks the empty link list
    if (head == NULL){

    Book* new_book = new Book();

    cout <<"Enter Book name \n";
    cin >> new_book -> title;

    cout << "Enter author name \n";
    cin >> new_book -> author;


    cout << "Enter publisher name \n";
    cin >> new_book -> publisher;

    cout << "Enter publish year \n";
    cin >> new_book -> publishYear;

    cout << "Enter ISBN number \n";
    cin >> new_book -> isbn;


    new_book -> next = NULL;
    head = new_book;
    last = new_book;

    }

    else
    {
        Book* new_book1 = new Book;

    cout <<"Enter Book name \n";
    cin >> new_book1 -> title;

    cout << "Enter author name \n";
    cin >> new_book1 -> author;


    cout << "Enter publisher name \n";
    cin >> new_book1 -> publisher;

    cout << "Enter publish year \n";
    cin >> new_book1 -> publishYear;

    cout << "Enter ISBN number \n";
    cin >> new_book1 -> isbn;


        last -> next = new_book1;
        last =  new_book1;
    }

}


void print_list(Book* in_root){

    Book* next_ptr;
    next_ptr = in_root;
    if(next_ptr == NULL)
    {
        cout << "No information found! \n";

    }

    else
    {
        while (next_ptr != NULL){
            cout << "Book Name: "<<next_ptr -> title << endl;
            cout << "Author Name: "<<next_ptr -> author << endl;
            cout << "Publisher: "<<next_ptr -> publisher << endl;
            cout << "Publishing Year: "<<next_ptr -> publishYear << endl;
            cout << "ISBN Number: "<<next_ptr -> isbn << endl;
            cout << " \n";
            next_ptr = next_ptr -> next;
        }
    }
}


void delete_list(Book *&head, Book *&last){


    if (head == NULL)
    {
        cout << "Database is already empty! \n";
    }

    else if (head == last){
        delete head;
        head = NULL;
        last = NULL;
    }

    else
    {
        cout << "Please enter the number of the node you would like to delete \n";
        cin >> deleteNode;

        Book* new_book = head;

      while(deleteNode>0){

        head = head -> next;
        deleteNode--;
      }
      delete new_book;
    }
}

Answer 1

你很接近。你在这里有几个问题。首先，当您执行 head = head->next 遍历列表时，您正在主动重新分配头指针，因此会从列表中丢失节点。您应该创建一个临时节点，通常称为 curr 作为当前节点。然后设置 curr = head 并在 while 循环中执行 curr = curr->next

另一个问题是，您删除了列表中间的一个节点，这有效地将您的列表分成两部分，但没有将这两部分重新组合在一起。您需要创建另一个临时变量以指向要删除的节点，Book* deleteMe = curr->next。设置 curr->next = curr->next->next 然后 delete deleteMe

Answer 2

您没有更新包围被删除节点的节点。从列表的前面或后面删除节点时，您不会更新 head 或 last 指针。您正在更新调用者的 head 指针，同时简单地迭代列表，有效地破坏了调用者的列表。

试试这个：

void delete_list(Book* &head, Book* &last)
{
    if (!head)
    {
        cout << "Database is already empty! \n";
    }
    else
    {
        cout << "Please enter the number of the node you would like to delete \n";
        int deleteNode = -1;
        cin >> deleteNode;

        if (deleteNode < 1)
        {
            cout << "Invalid node number \n";
            return;
        }

        Book* book = head, *previous = NULL;

        while ((book) && (--deleteNode > 0))
        {
            previous = book;
            book = book->next;
        }

        if (!book)
        {
            cout << "Invalid node number \n";
            return;
        }

        if (previous)
            previous->next = book->next;

        if (head == book)
            head = book->next;

        if (last == book)
            last = previous;

        delete book;
    }
}

也就是说，您的代码还有一些其他问题。试试像这样的东西：

#include <iostream>
#include <string>
#include <limits>
using namespace std;

struct Book
{
    string title;
    string author;
    string publisher;
    int publishYear;
    int isbn;

    Book* next;
};

void add_node(Book*&, Book*&);
void print_list(Book*);
void delete_list(Book*&, Book*&);

int main()
{
    Book* head = NULL;
    Book* last = NULL;

    char option;

    do
    {
        cout << "Press required option: \n"
                "To Add Book detail   [A]\n"
                "To Print Book details   [P]\n"
                "To Delete Book details   [D]\n"
                "Quit  [Q]\n";

        if (!(cin >> option))
        {
            option = '[=11=]';
            cin.clear();
            cin.ignore(numeric_limits<streamsize>::max(), '\n');
            continue;
        }

        switch (option)
        {
            case 'A':
                add_node(head, last);
                break;

            case 'P':
                print_list(head);
                break;

            case 'D':
                delete_list(head, last);
                break;

            case 'Q':
                break;

            default:
                cout << "Invalid Input" << endl;
                cin.ignore(numeric_limits<streamsize>::max(), '\n');
                break;
        }
    }
    while (option != 'Q');

    return 0;
}

void add_node(Book *&head, Book *&last)
{
    Book* new_book = new Book;

    cout << "Enter Book name \n";
    getline(cin, new_book->title);

    cout << "Enter author name \n";
    getline(cin, new_book->author);

    cout << "Enter publisher name \n";
    getline(cin, new_book->publisher);

    cout << "Enter publish year \n";
    cin >> new_book->publishYear;
    cin.ignore(numeric_limits<streamsize>::max(), '\n');

    cout << "Enter ISBN number \n";
    cin >> new_book->isbn;
    cin.ignore(numeric_limits<streamsize>::max(), '\n');

    new_book->next = NULL;

    //Checks the empty link list
    if (!head) {
        head = last = new_book;
    }
    else
    {
        last->next = new_book;
        last = new_book;
    }
}

void print_list(Book* root)
{
    if (!root)
    {
        cout << "No information found! \n";
        return;
    }

    Book* book = root;
    do
    {
        cout << "Book Name: " << book->title << endl;
        cout << "Author Name: " << book->author << endl;
        cout << "Publisher: " << book->publisher << endl;
        cout << "Publishing Year: " << book->publishYear << endl;
        cout << "ISBN Number: " << book->isbn << endl;
        cout << " \n";
        book = book->next;
    }
    while (book);
}

void delete_list(Book* &head, Book* &last)
{
    if (!head)
    {
        cout << "Database is already empty! \n";
    }
    else
    {
        cout << "Please enter the number of the node you would like to delete \n";

        int deleteNode;
        if (!(cin >> deleteNode))
        {
            cin.clear();
            cin.ignore(numeric_limits<streamsize>::max(), '\n');
            cout << "Invalid Input" << endl;
            return;
        }

        if (deleteNode < 1)
        {
            cout << "Invalid node number \n";
            return;
        }

        Book* book = head, *previous = NULL;

        while ((book) && (--deleteNode > 0))
        {
            previous = book;
            book = book->next;
        }

        if (!book)
        {
            cout << "Invalid node number \n";
            return;
        }

        if (previous)
            previous->next = book->next;

        if (head == book)
            head = book->next;

        if (last == book)
            last = previous;

        delete book;
    }
}

如何删除链表中的特定节点

How do I delete a specific node in a linked list

c++

pointers

structure

linked-list

dynamic