使用鏈接列表而不使用重複鍵的順序搜索

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

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。