c++ - C++ 删除和删除节点

Question

我第一次使用指针，并试图编写一个删除节点的函数和一个删除节点的函数。我的代码在我插入键和数据时识别（例如：键 = 123，数据 = 123）。但是，当我尝试删除密钥 123 时，它无法识别它的存在。这是我的 LList.cpp，如果需要，我可以包含其他代码：

#include <iostream>
#include "LList.h"

//----------------------------------------------------
//             constructor & destructor
//----------------------------------------------------
LList::LList() {
    head = NULL;
} // constructor (default)
LList::~LList() {
    if (head) delete head;
} // destructor


//----------------------------------------------------
//                  print
//----------------------------------------------------
// prints each node in the list, or EMPTY when there
// are no nodes to print
//----------------------------------------------------
void LList::print() {
    if (head == NULL)
        cout << "EMPTY\n\n";
    else {
        node* p;
        p = head;
        while (p != NULL) {
            p->print();
            p = p->next;
        }
        cout << endl;
    }
} // print()

//----------------------------------------------------
//                       search
//----------------------------------------------------
// Given: key to search for
// Returns: pointer to a node in the list found to have
//          the given search key, or NULL for not found
//----------------------------------------------------
node* LList::search(int srchKey) {
    if (head == NULL)
        return NULL;
    node* itr = head;
    while (itr != NULL) {
        if (itr->key == srchKey)
            itr = itr->next;
    }
    return itr;
} // search()

//----------------------------------------------------
//                 findNode
//----------------------------------------------------
// Given: a key to search for
// Searches for a node with the given key, and if 
// found, invokes the print() method in the found node.
// Otherwise, prints "not found"
//----------------------------------------------------
void LList::findNode(int srchkey) {
    if (head == NULL) {
        cout << "not found\n";
    }
    node* itr = head;
    while (itr != NULL) {
        if (itr->key == srchkey) {
            print();
        }
        itr = itr->next;
    }
    cout << "not found\n";
} // findNode()

//----------------------------------------------------
//                  getb4
//----------------------------------------------------
// Given: a pointer to a node in the list
// Returns: a pointer to the node in the list BEFORE
//               the one pointed to by r, OR
//          NULL when r is the head or not found in
//               the list
//----------------------------------------------------
node* LList::getb4(node* r) {
    node* tmp = head;
    while (tmp->next != NULL) {
        if (tmp->next == r)
            return tmp;
        tmp = tmp->next;
    }
    return NULL;
} // getb4()

//----------------------------------------------------
//                     insert
//----------------------------------------------------
// Given: key and data for a new node
// Allocates/populates a new node
// When a node with the same key already exists:
//     the current/old node is replaced by the new one
//     and the old one is placed on the new one's 
//     duplicate list.
// Otherwise, the new node is prepended to the head
//     of the list.
//----------------------------------------------------
void LList::insert(int k, string d) {
    node* newNode = new node();
    node* currentNode, *prevNode;
    newNode->key = k;
    newNode->data = d;
    if (head == NULL) {
        head = newNode;
    }
    else {
        currentNode = search(k);
        if (currentNode == NULL) {
            newNode->next = head;
            head = newNode;
        }
        if (currentNode == head) {
            newNode->next = head->next;
            head->next = NULL;
            newNode->dup = head;
            head = newNode;
        }
        prevNode = getb4(currentNode);
        if (prevNode == NULL)
            return;
        prevNode->next = newNode;
        //newNode->next = currentNode->next;
        currentNode->next = NULL;
        newNode->dup = currentNode;
    }
} // insert()

//----------------------------------------------------
//                     remove
//----------------------------------------------------
// Given: a pointer to a node in the list to be removed
//        BUT NOT DELETED/DESTROYED
// Returns: TRUE - when the node was successfully removed
//          FALSE - when the given node is NULL or the node
//                  is not actually in the list.
// Simply removes the node from the linked list.
// (including setting the NEXT pointer in the node to NULL)
//----------------------------------------------------
bool LList::remove(node* r) {
    if (r == NULL || search(r->key) == NULL) {
        return false;
    }
    if (r == head) {
        head = head->next;
    }
    else {
        node* prev = getb4(r);
        prev->next = r->next;
    }
    r->next = NULL;
    return true;
} // remove()

//----------------------------------------------------
//                     drop
//----------------------------------------------------
// Given: key of a node to drop
// Returns: TRUE when a node was found and deleted
//          FALSE when a node with the given key not found,
//                or the remove() fails.
// Searches for a node in the list with the given key:
// When found, removes and deletes the node
//----------------------------------------------------
bool LList::drop(int k) {
    node* currentNode = search(k);
    if (currentNode == NULL || !remove(currentNode))
        return false;
    node* tmp = currentNode;
    while (tmp != NULL) {
        currentNode = currentNode->dup;
        remove(tmp);
        tmp = currentNode;
    }
    return true;
} // drop()

//----------------------------------------------------
//                      max
//----------------------------------------------------
// Returns: a pointer to the node with the highest key
//          or NULL when there list is empty.
node* LList::max() {
    if (head == NULL)
        return NULL;
    node* max = head;
    node* tmp = head->next;
    while (tmp != NULL) {
        if ((tmp->key) > (max->key)) {
            max = tmp;
        }
        tmp = tmp->next;
    }
    return max;
} // max()

标签： c++pointersbinary-search-treenodes

Answer 1

这个循环：

 while (itr != NULL) {
        if (itr->key == srchKey)
            itr = itr->next;
    }
 return itr;

是不正确的。如果找到密钥，您要么进行迭代，要么根本不进行迭代。您需要遍历列表，并在执行此操作时搜索键：

 while (itr != NULL) {
        if (itr->key == srchKey)
            break;
        itr = itr->next;
    }
 return itr;

此外，您的析构函数不正确；您只删除第一个节点，并泄漏其余节点。您需要通过遍历链表来删除所有节点：

LList::~LList() {
    while (head) 
        delete std::exchange(head, head->next);
}

此外，更喜欢使用nullptr, 而不是NULL.