C++ 中有序链表类的插入函数出现问题

Question

我有一个模板类 OList，它是一个有序链接列表（元素按升序排列）。它有一个名为 void insert(const T & val) 的函数，用于将元素插入列表中的正确位置。例如，如果我有一个值为 { 1,3,5 } 的整数 OList 并调用 insert(4)，则 4 将插入到 3 和5，使 OList { 1,3,4,5 }。

现在，当我将元素插入 EMPTY Olists 时，我所拥有的工作正常。但是，当我使用以下代码时：

OList<char> list;
for (int i = 0; i < 3; i++) {
    list.insert('C'); 
    list.insert('A');
}
printInfo(list);

printList(list) 应该输出：

List = { A,A,A,C,C,C }  Size = 6        Range = A...C

相反，它输出：

List = { A,C,C,C, 

后跟运行时错误。

我已经搞砸了大约 5 个小时，但我似乎没有取得任何进展（除了得到不同的错误输出和错误）。

共有三段相关的代码：OList 的默认构造函数、operator<<、printInfo()、insert() 以及用于插入的辅助函数（用于查找要插入元素的节点）。我认为没有任何理由提供运营商<<也不是 printInfo() 因为这些在其他地方似乎工作得很好。

// default constructor
OList() {
    size = 0;
    headNode = new Node<T>;
    lastNode = new Node<T>;
    headNode->next = lastNode;
    lastNode->next = NULL;
}


void insert(const T & val) {
    if ( isEmpty() ) {
        lastNode->data = val;
    }
    else {
        Node<T> * pre = headNode;
        Node<T> * insertPoint = findInsertPoint(pre, val);
        Node<T> * insertNode = new Node<T>;
        insertNode->data = val;
        insertNode->next = insertPoint;
        pre->next = insertNode;

        // why is pre equal to headNode? 
        // I thought I changed that when using it
        // with findInsertPoint()
        cout << (pre == headNode) << endl;
    }

    size++;
}

// returns the node AFTER the insertion point
// pre is the node BEFORE the insertion point
Node<T> * findInsertPoint(Node<T> * pre, const T & val) {
    Node<T> * current = pre->next;

    for (int i = 0; (i < getSize()) && (val > current->data); i++) {
        pre = current;
        current = current->next;
    }

    return current;
}

lastNode 只是列表中的最后一个节点。 headNode 是一个“虚拟节点”，不包含任何数据，仅用作列表的起始位置。

提前致谢。我真的很尴尬在互联网上寻求家庭作业帮助，特别是因为我确信主要问题是我对指针缺乏透彻的理解。

Answer 1

您将指向 pre 的指针按值传递到 findInsertPoint 中，因此它被复制，并且该函数更改了指针的副本，并且当函数返回时，它仍然是旧的 pre，而不是函数内部的 pre。

如果要更改指针，则必须将指针传递给函数的指针（或对指针的引用）。