使用无重复键的链表进行顺序搜索

Question

我试图做一个序列搜索，检查重复键，如果存在，我只需要更新值。但是当我尝试使用链表时，就会出现内存问题。

放入值而不必检查重复键(在代码中注释掉)的正常代码工作得很好。

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

first应在构造函数中初始化NULL

Answer 2

你有几个问题。

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为当前节点，如果没有最后一个节点(即，我们没有遍历任何节点)。