Как удалить определенный узел в связанном списке

Question

Я столкнулся с проблемой, когда я не могу найти определенный узел и затем удалить этот узел из связанного списка. Я попытался создать цикл while, показанный в самом конце, чтобы два раза зациклить выделение памяти головке, содержащей узлы, а затем удалить ее, но, кажется, удаляются оба узла, если я установил 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 или 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 = '\0';
            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;
    }
}

Answer 2

Вы рядом. У вас есть пара вопросов здесь. Во-первых, когда вы делаете head = head->next, чтобы пройти по списку, вы активно переназначаете указатель головы и, следовательно, теряете узлы из своего списка. Вы должны создать временный узел, условно называемый curr для текущего. Затем установите curr = head и в цикле while выполните curr = curr->next

Другая проблема заключается в том, что вы удаляете узел в середине списка, который эффективно разрезает ваш список на две части, но не помещает двекусочки обратно вместе. Вам нужно будет создать другую временную переменную для указания на узел, который вы хотите удалить, Book* deleteMe = curr->next. Установите curr->next = curr->next->next, затем delete deleteMe