c++ - 重複キーのないリンクリストを使用した順次検索

Question

seq 検索を実行しようとしています。重複キーがないかどうかを確認します。存在する場合は、値を更新するだけです。しかし、リンクされたリストを使用して実行しようとすると、メモリの問題が発生します。

重複キー (コード内でコメントアウト) をチェックせずに値を配置する通常のコードは正常に機能します。

class seqSearch
{
public:
    int N;

    //helper class node
    class node
    {
    public:
        char key;
        int val;
        node *next;

        node(){ key = NULL; val = NULL; next = NULL;}
        node(char k,int v, node *nxt)
        {
            this->key = k;
            this->val = v;
            this->next = nxt;
        }

    };

    node *first;
    seqSearch(){N=0;}
    bool isEmpty(){return first == NULL;}
    int size(){return N;}
    void put(char,int);
    int get(char);
};

void seqSearch::put(char k, int v)
{
    /*
    node *oldfirst = first;
    //first = new node(k,v,oldfirst);
    first = new node;
    first->key = k;
    first->val = v;
    first->next = oldfirst;
    N++;
    */

    for (node *x = first; x!= NULL; x=x->next)
    {
        //node *oldfirst = first;
        //first = new node(k, v, oldfirst);
        if(x->key == k)
        {
            x->val = v; 
            return;
        }
    }
    first = new node(k, v, first); N++;

}

Answer 1

いくつか問題があります。

1. first新しいノードを作成すると、常にリセットされます。
2. firstノードをそれ自体に等しく設定nextし、リストをたどることができないことを保証します。

このようなことをもっと試してください：

void seqSearch::put(char k, int v)
{
    node* last = NULL;
    node* current = NULL;

    for (node *x = first; x!= NULL; x=x->next)
    {
        if(x->key == k)
        {
            x->val = v; 
            return;
        }
        last = x;
    }
    current = new node(k, v, NULL); N++;
    if( last == NULL )
        first = current;
    else
        last->next = current;
}

これ：

1. 新しく作成されたノードを現在のものとして追跡します。
2. トラバースされた最後のノードを追跡するため、そのnextセットを新しく作成されたノードに設定できます。
3. first最後のノードがなかった場合 (つまり、どのノードもトラバースしなかった場合)、現在のノードに設定します。

Answer 2

firstNULLコンストラクタで初期化する必要があります