删除链表中的节点函数

Question

我有一个程序，它应该询问用户他们希望删除哪个项目。然后，删除函数应成功删除该节点。我知道我需要从前一个节点获取地址，并使其指向我要删除的节点之后的节点，然后删除悬空节点。我很难理解语法来使其工作。这是我的代码。我省略了不必要的功能。

#include <iostream> 
#include <cstddef> 
#include <string> 
using namespace std;
struct Node 
{
    string item; 
    int count; 
    Node *link; 
};
typedef Node* NodePtr;
void insert(NodePtr after_me, string an_item, int a_number); 
void list_remove(NodePtr& head, string an_item);
void head_insert(NodePtr& head, string an_item, int a_number); 
void show_list(NodePtr& head); 
NodePtr search(NodePtr head, string target);

---

int main() 
{ 
    string new_item, target, remove_item; 
    int new_count; 
    NodePtr head = NULL; 
    head_insert(head, "Tea", 2); 
    head_insert(head, "Jam", 3); 
    head_insert(head, "Rolls", 10);
    cout << "List contains:" << endl; 
    show_list(head);
    NodePtr after_me = head; 
    after_me = after_me ->link;
    cout << "Enter the item you wish to remove (string) n"; 
    cin >> remove_item; 
    after_me = search(head, remove_item);
    if(after_me != NULL) 
    { 
        cout << "nWill remove " << remove_item  << endl << endl;       
        list_remove(head, remove_item);
        cout << "List now contains:" << endl; 
        show_list(head); 
    }
    else 
    { 
        cout << "I can't find " << remove_item 
             << " in the list, so I can't remove anything n"; 
    }
    system("PAUSE");
    return EXIT_SUCCESS; 
}

---

void list_remove(NodePtr& head, string remove_item)
{
    NodePtr remove_ptr; //pointer to the node that is being removed
    remove_ptr = search(head, remove_item); // finds the address for the item 
                                            // that is being removed and puts it
                                            // in remove_ptr

}

---

// Uses cstddef: 
void head_insert(NodePtr& head, string an_item, int a_number) 
{ 
    NodePtr temp_ptr; 
    temp_ptr = new Node;
    temp_ptr -> item = an_item; 
    temp_ptr -> count = a_number;
    temp_ptr->link = head; 
    head = temp_ptr; 
}

---

//Uses iostream and cstddef: 
void show_list(NodePtr& head) 
{ 
    NodePtr here = head;
    while (here != NULL) 
    { 
        cout << here-> item << "t"; 
        cout << here-> count << endl; 
        here = here->link; 
    } 
}

---

NodePtr search(NodePtr head, string target) 
{ 
    // Point to the head node
    NodePtr here = head;
    // If the list is empty nothing to search 
    if (here == NULL) 
    { 
         return NULL; 
    }
    // Search for the item 
    else 
    { 
         // while you have still items and you haven't found the target yet 
         while (here-> item != target && here->link != NULL) 
             here = here->link;
         // Found the target, return the pointer at that location 
         if (here-> item == target) 
             return here;
         // Search unsuccessful, return Null 
         else 
             return NULL; 
    } 
}

Answer 1

要删除，您还需要在要删除的节点之前使用节点。步骤如下：

// find the preceding_ptr
NodePtr preceding_ptr = head;
while(preceding_ptr != NULL && preceding_ptr->link != remove_ptr){
    preceding_ptr = preceding_ptr->link;
}
// now preceding_ptr is set, make it skip remove_ptr
preceding_ptr->link = remove_ptr->link;
// free up memory from remove_ptr

Answer 2

所以，由于你并没有真正展示你要尝试什么，我真的不知道哪个"语法"特别让你感到困惑。只是一个猜测...

如果我理解正确，归结为您想知道如何找到放置在要删除的物品之前的项目以根据需要对其进行操作，对吧？
然后，只需自己遍历列表，而不是使用 search() 方法：

void list_remove(NodePtr& head, string remove_item)
{
    NodePtr remove_ptr; //pointer to the node that is being removed
    remove_ptr = search(head, remove_item);
    if(remove_ptr != NULL) // indicates the item is part of the list and 
                           // we can remove it    
    {
         NodePtr predecessorNode = NULL;
         // Iterate the list to find the predecessor of remove_ptr
         for(NodePtr curNode = head; curNode != NULL; curNode = curNode->link)
         {
             if(curNode->link == remove_ptr) // Indicates that curNode is the
                                             // predecessor of remove_ptr
             {
                 predecessorNode = curNode;  // store it and ...
                 break;                      // ... exit the loop
             }
         }
         if(predecessorNode != NULL) // We have found a predecessor
         {
             // Now you have the predecessor for remove_ptr, 
             // manipulate it as necessary
         }
         else // indicates the item to remove is the head of the list
         {
             // You might need to manipulate head, depending on how your 
             // linked list is organized (set to remove_ptr->link most likely)
         }
    }
}