C++鏈接列表實現崩潰

Question

我想實現一個數據結構類的鏈表，我在搜索部分的算法有一些困難。

下面是有問題的代碼，我試圖實現以下僞代碼在MIT算法導論文字：

// 
// Method searches and retrieves a specified node from the list 
// 
Node* List::getNode(unsigned position) 
{ 
    Node* current = m_listHead; 

    for(unsigned i = m_listSize-1; (current != 0) && (i != position); --i) 
      current = current->next; 

    return current; 
} 

在程序中的該點的頭部是4節點，包含int 5的值。問題出現在for循環的主體中，其中指向節點對象的指針被分配給下一個節點。但是這超出了節點的頭部，所以它基本上指向了內存中的某個隨機位置（這是有道理的）。

在這種情況下算法不應該移動到前一個節點而不是下一個節點？下面是僞代碼：

LIST-SEARCH(L, k) 
    x <- head 
    while x != NIL and key != k 
     do x <- next[x] 
    return x 

另外，這裏是我的鏈接列表實現的頭文件。我還沒有嘗試實現它的模板形式還只是爲了讓事情變得簡單：

#ifndef linkList_H 
#define linkList_h 


// 
// Create an object to represent a Node in the linked list object 
// (For now, the objects to be put in the list will be integers) 
// 
struct Node 
{ 
    // nodes of list will be integers 
    int number; 
    // pointer to the next node in the linked list 
    Node* next; 
}; 


// 
// Create an object to keep track of all parts in the list 
// 
class List 
{ 
public: 

    // Contstructor intializes all member data 
    List() : m_listSize(0), m_listHead(0) {} 

    // methods to return size of list and list head 
    Node* getListHead() const { return m_listHead; } 
    unsigned getListSize() const { return m_listSize; } 

    // method for adding a new node to the linked list, 
    // retrieving and deleting a specified node in the list 
    void addNode(Node* newNode); 
    Node* getNode(unsigned position); 

private: 

    // member data consists of an unsigned integer representing 
    // the list size and a pointer to a Node object representing head 
    Node* m_listHead; 
    unsigned m_listSize; 
}; 

#endif 

ADDNODE方法的實現：

// 
// Method adds a new node to the linked list 
// 
void List::addNode(Node* newNode) 
{ 
    Node* theNode = new Node; 

    theNode = newNode; 
    theNode->next; 
    m_listHead = theNode; 

    ++m_listSize; 
} 

Answer 1

試試這個構建列表：

void List::addNode(int number) 
{ 
    newNode = new Node; 
    newNode -> number = number; 
    newNode -> next = m_listHead ; 
    m_listHead = newNode; 
    ++m_listSize; 
} 

將節點添加到頭部。也許你可能希望將指針存儲到尾部，並在那裏插入節點。

Answer 2

不幸的是你的代碼並不像您所提供的僞代碼。

僞代碼用於搜索鏈接列表中的鍵而不是位置。

的僞代碼讀作：

Assign head to (node) x. 
while x isn't null and the key inside the current node (x) doesn't match k 
    assign x->next to x 
return x 

返回的值是一個指向包含k或空節點

如果你試圖找到節點在給定位置你的循環將是（注意，這是假設你要使用一個從零開始的索引來訪問列表）：

Assign head to (node) x 
assign 0 to (int) pos 
while x isn't null and pos not equal to given position 
    assign x->next to x 
    increment pos 
return x 

將R esult要麼是指向給定位置或空節點（如果你打的列表的末尾第一）

編輯：你的代碼是非常接近後者，如果這就是你想要什麼做...你能看出差異嗎？

編輯，因爲我喜歡的功課，其中OP問正確的問題:)

Node* List::getNodeContaining(int searchValue) 
{ 
    Node* current = m_listHead; 

    while (current != 0 && current->number != searchValue) 
    { 
     current = current->next; 
    } 
    return current; 
} 

Node* List::getNodeAtPos(int position) 
{ 
    Node* current = m_listHead; 
    int pos = 0; 

    while (current != 0 && pos != position) 
    { 
     current = current->next; 
     pos++; 
    } 

    return current; 
} 

Answer 3

您的列表與ADT的正常列表非常不同。不是返回節點，而是要求客戶端知道列表實現的情況，而是返回並接受你正在列表的類型。

在這種情況下，你正在做一個整數列表，SOU你想要

public: 
    void add(int num); //prepends an Item to the list 
    int get(int pos); 

兩者的實現很簡單。添加一個新節點，並將其鏈接到;

void List::add(int num) 
{ 
    Node *newNode = new Node; 
    newNode->number = num; 
    newNode->next = m_listHead; 
    m_listHead = newNode; 
    m_listSize++; 
} 

然後得到的是一件容易的事：

int List::get(int pos) 
{ 
    if(pos>m_listSize) 
     ;//throw an error somehow 
    Node *tmp = m_listHead; 
    while(pos-->0) 
     tmp=tmp->next; 
    return m->number 
}