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

我有一个模板类OList，它是一个有序的链表（元素按升序排列）。它有一个名为void insert(const T & val)的功能，它将一个元素插入列表中的正确位置。例如，如果我有一个OList，其值为{ 1,3,5 }，并且被称为insert(4)，则4将插入3和5之间，从而使OList { 1,3,4,5 }。C++中有序链表类的插入函数问题

现在，我在将元素插入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的默认构造函数，运算符< <，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是一个“虚拟节点”，它不包含任何数据，仅用作列表的起始位置。

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

来源

2011-03-01 DormoTheNord

您正在将指针pre传递给findInsertPoint，所以它被复制，并且函数更改指针的副本，并且当函数返回时，它仍然是旧pre，而不是从函数内部pre 。

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

来源

2011-03-01 22:19:28 ajuc

嘎，我是个白痴！我将参数类型更改为'Node *＆pre'，并且工作得很完美。谢谢！ – DormoTheNord 2011-03-01 22:22:13

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

回答

相关问题