疑似指针算术错误导致意外输出

Question

我正在尝试从头开始用 C++ 构建一个链表。考虑以下带注释的类声明。

/*
    Linked list goes from smallest to largest
*/
class List
{
public:
    List():head(0), tail(0), theCount(0) {}
    virtual ~List() {};
    void insert(int value);
    bool is_present(int value) const;
    bool is_empty() const { return head == 0; }
    void showAll();
    int count() const {return theCount;}
private:
    class ListCell
    {
    public:
        ListCell(int value, ListCell* cell = 0):val(value), next(cell) {}
        int val;
        ListCell* next;
    
    };
    ListCell* head;
    ListCell* tail;
    int theCount;
    
};

创建

List

实例后，我们将

Head

和

Tail

设置为空指针。为了向头部、尾部和中间元素添加值，我实现了

insert

方法。

插入：

void List::insert(int value) {
    theCount++;
    
    if (!head) {
        /*
            first insert sets the head and points to tail which is a nullPtr.
        */
        head = new ListCell(value, 0);
        //cout << "head is after initalization is " << head << endl;
        return;
    }
    if (!tail) {
            /*
                if tail is a nullptr, we set it to be the next node after head.
            */
            if (value > head->val) {
                /*
                    Value larger = therefore it should be the tail
                */

                tail = new ListCell(value, 0);
                head->next = tail;
                return;
            }
            else {
                /*
                    Value smaller, therefore, we swap.
                */
                tail = new ListCell(head->val, 0);
                head->next = tail;
                return;
            }
    }

            
    ListCell* previousNode = head;
    // the major problem, please advise me on the loop.
            for (ListCell* nodePtr = head; nodePtr->next; nodePtr++) {
                ListCell* next = nodePtr->next; // for convience
                if (next == tail) {
                    if (value > next->val) {
                        // if the value is the largest in the list.
                        int oldVal = tail->val;
                        tail->val = value;
                        next = new ListCell(oldVal, tail);
                        previousNode = nodePtr;
                        break;
                    }
                    else {
                        // if the value is just before the tail.
                        next = new ListCell(value, tail);
                        previousNode = nodePtr;
                        break;
                    }
                }
                if (value < nodePtr->val) {
                    /*
                        if value is less than the node's value, then we create a nodePtr
                    */
                    previousNode->next = new ListCell(value, nodePtr);
                    previousNode = nodePtr;
                    break;
                }
                previousNode = nodePtr;



                


            }
        


}

但是，当我尝试在主函数中显示全部时，我遇到了意外的行为。

int main() {
    List mainList;
    mainList.insert(10);
    mainList.insert(12);
    mainList.insert(15);
    mainList.insert(11);
    mainList.showAll(); // shows undefined values. probably indirecting empty pointers
    return 0;
}

我有一种感觉，是

nodePtr++

造成了问题，因为我不习惯指针算术。

Answer 1

有几个问题，包括以下几点：

• 在

  !tail

  情况下，在

  else

  块中，使用与头节点中已存在的值相同的值创建第二个节点，并且不使用给定的

  value

  。因此，您不会插入

  value

  ，而是复制了第一个节点。

• 在主循环中，

  nodePtr++

  是错误的。你需要

  nodePtr = nodePtr->next

  。

• 在某些情况下，您将新节点分配给

  next

  。但这不会更新前一个节点的

  next

  成员。为此，您确实需要分配给

  previousNode->next

  而不仅仅是

  next

  。您在一种情况（最后一种情况）中这样做是正确的，但在另外两种情况下则错误。

• 在

  else

  案例的

  value > next->val

  块中，仍然有两种可能性：

  value > nodePtr->val

  为真或不为真。但你不检查这个，并以相同的方式处理这两种情况。如果不是 true，则

  ListNode

  构造函数的第二个参数应该是

  nodePtr

  ，而不是

  tail

  。如果 is true，则应分配给

  nodePtr->next

  ，否则应分配给

  previousNode->next

  。

• 没问题，但在

  previousNode = nodePtr;

  之前做

  break

  是没有用的。

• 将第一个节点添加到列表中时，

  tail

  保留为

  nullptr

  ，这似乎是其余代码所期望的。但这很奇怪，因为根据 tail 的

  含义

  ，即使只有一个节点，它也应该引用列表的最后一个节点。

• 尽管修复上述几点会改善代码的行为，但事情过于复杂。您已经确定了六个位置来创建

  ListNode

  并将其以某种方式插入到列表中。这太多了。确实应该只有两三种情况需要分别处理。

当我们减少不同情况的数量并处理上面提到的其他点时，您的代码可能会是什么样子：

void List::insert(int value) {
    theCount++;
    if (!head || value <= head->val) {
        head = new ListCell(value, head);
        if (!tail) tail = head;
        return;
    }
    ListCell* previousNode = head;
    while (previousNode->next && value > previousNode->next->val) {
        previousNode = previousNode->next;
    }
    previousNode->next = new ListCell(value, previousNode->next);
    if (tail->next) tail = tail->next;
}