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++中有序鏈表類的插入函數問題

回答

相關問題