2017-02-24 13 views
0

開始:これは宿題の問題の一部なので、答えをヒントするか、直接答えなくても正しい方向に向けるようにしてください。C++単一リンクリストで一致するノードに前ノードを取得

私はC++で単一のリンクリストを作成しています。必要な関数の1つはvoid remove(const T& key)です。値が関数に渡されたキーの値と一致する場合は、特定のノードが削除されます。

私の現在の考え方は、最初に削除するノードを見つけて、削除するノードの前にあるノードを見つけて、削除するノードの後に​​ノードを見つけることです。そこから私は削除が必要なノードを削除し、削除されたノードの後に​​来るノードに向けて前のノードを設定することができます。ここで

関連する関数です:

LinkedList.h

//Returns the node with passed in value key 
ListNode<T>* find(const T& key) { 
    ListNode<T>* currentNode = _head; 
    while(currentNode != NULL && currentNode->data() != key){ 
     currentNode = currentNode->next(); 
    } 
    return currentNode; 
} 

//Returns the node before the key 
ListNode<T>* findPreviousNode(const T& key){ 
    ListNode<T>* previousNode; 
    ListNode<T>* currentNode = _head; 

    while(currentNode != NULL && currentNode->data() != key){ 
     previousNode = currentNode; 
     currentNode = currentNode->next(); 
    } 
    return previousNode; 
} 

// Removes and deletes the first node in the linked list that has data 
// equal to the key 
void remove(const T& key) { 
    ListNode<T>* nodeToDelete = find(key); 
    ListNode<T>* previousNode = findPreviousNode(key); 
    ListNode<T>* nextNode = nodeToDelete->next(); 
    delete nodeToDelete; 
    previousNode->setNext(nextNode); 

} 

私は広範囲に私のfind(const T& key)機能をテストして、それはので、私は、私は、コードを歩くしかしとき、問題は私のfindPreviousNode機能であると信じて動作しますそれは正常に動作するようです。

私は、previousNodeは常に最後にチェックされた要素を持ち、一致するものが見つかった場合、更新されていないpreviousNodeを返すので、まだ一致するノードの直前にノードが含まれていますが、正しいと私はなぜわからない。

LinkedList.h http://pastebin.com/b4miZBzA

:私は、コードを実行すると、私は

セグメンテーションフォールト(コアダンプ)

エラーメッセージここで

を取得することは、全体のコードといくつかのpastebinsです

main.cpp(テスト関数を呼び出すメソッド)http://pastebin.com/0QGtUhjC

+0

参考になることがあります:http://stackoverflow.com/questions/12914917/using-pointers-to-remove-item-from-singly-linked-list – user4581301

答えて

1

あなたには明らかに多くのエッジケースがありません。

find()関数は、キーが見つからない場合は処理しません。その場合、nullを返します。findPreviousNode()は、previousNodeのガベージ値を返します。

と仮定すると、find()はヘッドへのポインタを返します。その後、再びfindPreviousNode()は、初期化されていない前のノードポインタを返します。

コードでEdge caseを処理するようにしてください。

あなたのremove()機能は、それらが処理されるとうまくいくはずです。

実際にfind()関数を呼び出す必要はありません。findPreviousNode()から適切な値を返すだけで、実際にランタイムを改善することができます。不要な2つのループを実行しているため、実行時に保存できます。

+0

'find()'の指示は、値が見つからない場合はNULLを返しますが、findPreviousNode()の次のノードを取得しようとすると、ヌル値。私はそれを試して混乱させ、それが何かを修正するかどうかを見ます。 – kalenpw

+0

私の答えの最後の行を読んで、コード非効率性問題のためにそれを使って作業してみてください。 – Phoenix

+0

なぜfind()関数を実行する必要はありませんか?それは対応するノードを削除するために必要です。 – kalenpw

1

質問にここに投稿したコードから、正しい考えがあるようです。

つのヒント:

  1. 守備プログラミング。 nodeToDeleteとpreviousNodeがNULLでないことを確認してください。現在、キーが見つからない場合は、セグメンテーションフォルトの原因となるNULLポインタの逆参照が終了します。

  2. 効率。なぜそれを一度トラバースして両方の値を取得すればよいのか、リストを2回トラバースするのはなぜですか( 'find'では1回、 'findPrevious'では1回)?私。 find()とfindPrevious()関数を組み合わせて、プログラムの作業量を減らします。

+0

1のために私はそれが私が働いている問題だと思いますに。私はそれが効率的ではないと感じたことを明確にコーディングしていましたが、時には前ノードとノードを必要とするので、メソッドパラメータにブール値を含めるように変更できないか、以前のものか現在のものかを返すことを指定します。 – kalenpw

関連する問題