你能检查为什么从链表中删除一个项目在这段代码中不起作用吗？

Question

朋友请我帮他做个练习，大致思路如下。

Car number = fr50000       Car owner = AlexNelson       Parking time = 3.5 hours.

他被告知不要使用像 string 或 getline 这样的东西，所以这是一个简单的应用程序，只是为了学习使用链表的想法。

所以我做了这个程序。当我第一次调用 remove() 函数时，它说列表在开头是空的（它应该如此）。但是第二次和第三次，都说车被移除了，但是当我调用display()函数时，车还在（它没有从列表中移除）

你能告诉我我的代码有什么问题吗？

#include <iostream>
using namespace std;

int length = 0;//variable of how many items in the list

struct node
{
    char carNumber[15];
    char carOwner[20];
    float parkingTime;
    node *link;
};
typedef struct node node;

node *head;//the begining of a list;

bool isempty()
{
    if (length == 0)
        return true;
    else
        return false;
}

void insert()
{
    if (isempty())
    {
        head = new node;
        cout << "Enter car number: ";
        cin >> head->carNumber;
        cout << "Enter Car owner: ";
        cin >> head->carOwner;
        cout << "Enter parking time: ";
        cin >> head->parkingTime;
        head->link = NULL;
        length++;
    }
    else
    {
        node *p = head;
        node *pnext = new node;
        while (true)
        {
            if (p->link == NULL)
            {
                p->link = pnext;
                break;
            }
            p = p->link;
        }
    
        cout << "Enter car number: ";
        cin >> pnext->carNumber;
        cout << "Enter Car owner: ";
        cin >> pnext->carOwner;
        cout << "Enter parking time: ";
        cin >> pnext->parkingTime;
        pnext->link = NULL;
        length++;
    }
}

void remove()
{
    if (isempty())
    {
        cout << "List is empty\n";
        return;
    }

    char carnumber[15];
    cout << "Enter car number to remove: ";
    cin >> carnumber;
    node *p;
    p = head;
    while (p != NULL)
    {
        if (strcmp(p->carNumber, carnumber) == 0)
        {
            p = p->link;
            cout << "Car removed\n";
            return;
        }
        p = p->link;
    }
    
    cout << "Car was not found, check the number\n";
}

void display()
{
    if (isempty())
    {
        cout << "List is empty\n";
        return;
    }

    cout << "Car Number\t\tCar Owner\t\tParking Time\n";
    node *p = head;
    while (p != NULL)
    {
        cout << p->carNumber << "\t\t" << p->carOwner << "\t\t" << p->parkingTime << " Hours\n";
        p = p->link;
    }
}

int main()
{
    string number;
    display();
    insert();
    insert();
    insert();
    display();
    remove();
    display();
    insert();
    remove();
    display();
}

Answer 1

p = p->link; 您正在修改局部变量 p 的值，而不是列表。需要修改前一个节点的link字段

Answer 2

您的 remove() 函数实际上并未从列表中删除（或销毁）节点。您需要更新列表中 previous 节点的 link 以指向列表中的 next 节点。如果删除列表中的第一个节点，您也需要更新 head。

试试这个：

void remove()
{
    if (isempty())
    {
        cout << "List is empty\n";
        return;
    }

    char carnumber[15];
    cout << "Enter car number to remove: ";
    cin >> carnumber;

    node *p = head;
    node *prev = NULL;

    while (p != NULL)
    {
        if (strcmp(p->carNumber, carnumber) == 0)
        {
            if (p == head)
                head = p->link;

            if (prev)
                prev->link = p->link;

            delete p;

            cout << "Car removed\n";
            return;
        }

        prev = p;
        p = p->link;
    }
    
    cout << "Car was not found, check the number\n";
}

或者：

void remove()
{
    if (isempty())
    {
        cout << "List is empty\n";
        return;
    }

    char carnumber[15];
    cout << "Enter car number to remove: ";
    cin >> carnumber;

    node **p = &head;

    while (*p != NULL)
    {
        if (strcmp((*p)->carNumber, carnumber) == 0)
        {
            node *n = *p;
            *p = (*p)->link;

            delete n;

            cout << "Car removed\n";
            return;
        }

        p = &(p->link);
    }
    
    cout << "Car was not found, check the number\n";
}

Answer 3

在remove 的循环中，你在做p = p->link，当p 指向你要删除的节点。但是您实际上需要更新指向 p.

的节点的 link 字段

这是一个简单的方法：

node **p = &head;
while(*p)
  if (strcmp((*p)->carNumber, carnumber) == 0)
     break;
  else p = &(*p)->link;

if (*p)
{  
    cout<<"Car removed\n";
    delete std::exchange(*p, (*p)->link);
}
else cout << "Car was not found, check the number\n";

如果您不能使用 std::exchange，那么您可以将其替换为：

auto h = *p;
*p = (*p)->link);
delete h;

你能检查为什么从链表中删除一个项目在这段代码中不起作用吗？

Can you check why removing an Item from a linked list is not working in this code?

c++

linked-list

data-structures

singly-linked-list