C++リンクリスト実装がクラッシュする

Question

データ構造クラスのリンクリストを実装しようとしていますが、アルゴリズムの検索部分に問題があります。

以下

Iテキストをアルゴリズム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-loopの本体にあるように見えます。ここで、ノードオブジェクトへのポインタは次のノードに割り当てられます。しかし、これはノードの頭を越えているので、本質的にメモリ内のいくつかのランダムな場所を指しています（これは理にかなっています）。

この場合、アルゴリズムは次のノードの代わりに前のノードに移動してはなりませんか？以下は擬似コードです：

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

また、私のリンクリストの実装のヘッダーファイルは次のとおりです。私は物事をシンプルに保つために、まだテンプレートの形でそれを実装しようとしていない：に、addNodeメソッドの

#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 

実装：

// 
// 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

を残念ながら、あなたのコードは、あなたが提供する擬似コードに似ていません。

擬似コードは、リンクされたリストを検索して、位置ではなくキーを探し出すためのものです。

として擬似コードを読み取ります。返された値が指定した位置でノードを検索しようとしている場合はKまたはnull

が含まれているノードへのポインタのいずれかである

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 

あなたのループは（これはあなたがリストにアクセスするためのゼロベースのインデックスを使用するつもりだと仮定されていることに注意）次のようになります。

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は、指定された位置またはnullのノードへのポインタのどちらかになります：あなたのコードは、後者に非常に近いことは、あなたがしようとしているものだ場合あなたは違いを見ることができますか？

編集私は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とは非常に異なります。ノードを返すのではなく、クライアントにリストの実装について知ってもらうために、リストを作成しているタイプを返して受け入れます。あなたが整数のリストを作っている。この場合

、あなたは両方の

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

実装は簡単ですしたいと思いますSOU。 Addは新しいノードを作成し、それをリンクします。その後

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 
}