操作链表的函数出现逻辑错误

Question

我需要帮助确定我的逻辑错误在哪里。我正在C++编写一个函数，该函数将单向链表作为输入，旨在删除奇数整数节点，同时复制偶数整数节点：

例子：

initial: 0  5  2  2  7  3  7  9  0  2
 ought2b: 0  0  2  2  2  2  0  0  2  2  
outcome: 0  0  2  2  2  2  0  0  2  2  
initial: 0
 ought2b: 0  0
initial: 1
 ought2b: (empty)

我

遇到的问题是我的结果是正确的（如上所示），但是在第二个链表之后，整个程序退出，当我只能假设是分段错误时，我得到一个退出代码 11。我已经重写了整个函数 6+ 次，并且在心理上找不到我在哪里犯了逻辑错误，因为我的代码通常每次迭代看起来都相似。任何帮助将不胜感激！函数的代码如下所示。

void RemOddDupEven(Node*& headPtr){
    // Define two cursors to iterate through referenced list.
    Node *precursor = 0,
            *cursor = headPtr;
    // Error Checking | Check for reference to empty list.
    if(headPtr == 0){
        cerr << "RemOddDupEven() attempted on empty list" << endl;
        return;
    }
    while(cursor->link != 0){
        if(cursor->data%2 != 0){
            /// Odd node found in referenced list. Remove it.
            if(precursor == 0){
                // No previous. Removing first node.
                precursor = cursor;
                cursor = cursor->link;
                headPtr = cursor;
                delete precursor;
                precursor = 0;
            } else {
                Node* tempNodePtr = cursor;
                cursor = cursor->link;
                precursor->link = cursor;
                delete tempNodePtr;
            }
        } else {
            /// Even node found in referenced list. Duplicate it.
            if(precursor == 0){
                // No previous. Duplicate and insert before current node.
                Node* newNodePtr = new Node;
                newNodePtr->data = cursor->data;
                newNodePtr->link = cursor;
                headPtr = newNodePtr;
                precursor = cursor;
                cursor = cursor->link;
            } else {
                // There is a previous. Duplicate and insert before current.
                Node* newNodePtr = new Node;
                newNodePtr->data = cursor->data;
                precursor->link = newNodePtr;
                newNodePtr->link = cursor;
                precursor = cursor;
                cursor = cursor->link;
            }
        }
    }
    /// We are at last item in the list.
    if(cursor->data%2 != 0){
        /// Odd node found at end of referenced list. Remove it.
        precursor->link = 0;
        delete cursor;
        cursor = 0;
    } else {
        /// Even node found at the end of referenced list. Duplicte it.
        Node* newNodePtr = new Node;
        newNodePtr->data = cursor->data;
        precursor->link = newNodePtr;
        newNodePtr->link = cursor;
    }
}

Answer 1

你的函数太复杂了，很难研究它，因为函数中有许多特殊条件。

但乍一看，很明显，例如这个代码片段

/// We are at last item in the list.
if(cursor->data%2 != 0){
    /// Odd node found at end of referenced list. Remove it.
    precursor->link = 0;
    delete cursor;
    cursor = 0;
} else {

是错误的。

让我们考虑一个列表，该列表只有一个节点是头节点。

在这种情况下，循环

while(cursor->link != 0){
    //...
}

不会执行，因为headPtr->link等于 nullptr 。这也意味着precursor等于 0（在循环之前最初设置为 0）。所以表达式语句

precursor->link = 0;

导致函数的行为未定义。

同时此声明

    cursor = 0;

不会更改headPtr的值，因为cursor和headPtr是两个不同的对象，更改一个对象的值不会影响另一个对象的值。

函数实现看起来可以本质上更简单。

这是一个演示程序

#include <iostream>
struct Node
{
    int data;
    Node *link;
};
void initialize(Node * &head, const int a[], size_t n)
{
    Node **current = &head;
    while (*current) current = &(*current)->link;
    for (size_t i = 0; i < n; i++)
    {
        *current = new Node{ a[i], nullptr };
        current = &(*current)->link;
    }
}
void RemOddDupEven(Node * &head)
{
    Node **current = &head;
    while (*current)
    {
        if ((*current)->data % 2 == 0)
        {
            (*current)->link = new Node{ (*current)->data, (*current)->link };
            current = &(*current)->link->link;
        }
        else
        {
            Node *tmp = *current;
            *current = (*current)->link;
            delete tmp;
        }
    }
}
std::ostream & show(Node * &head, std::ostream &os = std::cout)
{
    for (Node *current = head; current; current = current->link)
    {
        os << current->data << ' ';
    }
    return os;
}
int main()
{
    Node *head = nullptr;
    int a[] = { 0, 5, 2, 2, 7, 3, 7, 9, 0, 2 };
    initialize(head, a, sizeof(a) / sizeof(*a));
    show(head) << std::endl;
    RemOddDupEven(head);
    show(head) << std::endl;
    return 0;
}

它的输出是

0 5 2 2 7 3 7 9 0 2
0 0 2 2 2 2 0 0 2 2