重複していないリンクリスト

Question

重複していないリンクリストの場合、次のコード（私の簡単なテストでは正しい）を持っていますが、少し醜いと思います。

重複したコードをよりきれいに処理する方法をお勧めしますか？

if((val == cur->val) || (cur->next && (val == cur->next->val))) 

しかし、私はよりよい解決策は、比較演算子の異なる使用を使用して（私は見ていないこと）が存在するかもしれないと思う：問題の 現在の作品です。

また、誰かが私に「有用な」アサーションまたは内部の提案をしてもらえますか？アサートするタイミングを特定するのは難しいです。特にifステートメントがある場合は特にそうです。

struct Node 
{ 
    Node(int v):val(v),next(NULL){} 
    int val; 
    Node * next; 
}; 

void insert(Node ** ppHead, const int val) 
{ 
    if(ppHead == NULL) 
     return; 
    if(*ppHead == NULL || val < (*ppHead)->val) 
    { 
     Node * tmp = new Node(val); // new throws 
     tmp->next = *ppHead; 
     *ppHead = tmp; 
    } 
    else 
    { 
     Node * cur = *ppHead; 
     while(cur->next && (val > cur->next->val)) 
      cur = cur->next; 

     if((val == cur->val) || (cur->next && (val == cur->next->val))) 
      return; 

     Node * tmp = new Node(val); // new throws 
     tmp->next = cur->next; 
     cur->next = tmp; 
    } 
    return; 
} 


int _tmain(int argc, _TCHAR* argv[]) 
{ 
    Node * list = NULL; 
    int x[] = { 5, 4, 6, 7, 1, 8, 1, 8, 7, 2, 3, 0, 1, 0, 4, 9, 9 }; 
    int size = sizeof(x)/sizeof(x[0]); 
    for(int i = 0; i < size; i++) 
     insert(&list, x[i]); 
    Node * cur = list; 
    while(cur) { 
     printf (" %d", cur->val); 
     cur = cur->next; 
    } 
    printf("\n"); 
    return 0; 
} 

Answer 1

私はこれをもっと書くように書く：

void insert(Node ** ppHead, const int val) 
{ 
    if (ppHead == NULL) 
     return; 
    while (*ppHead && (*ppHead)->val < val) 
     ppHead = &(*ppHead)->next; 
    if (*ppHead && (*ppHead)->val == val) 
     return; 
    Node * tmp = new Node(val); // new throws 
    tmp->next = *ppHead; 
    *ppHead = tmp; 
} 

Answer 2

私は、検索操作（*未テストコード）を実行するノードにメソッドを追加します。次に

Node* Find(int value) 
{ 
    if(this.val == value) return this; 
    if(this.next == null) return null; 
    return next.Find(value); 
} 

あなたが存在するかどうかを確認したい挿入する前に：

if(null == _head || null == _head.Find(value)) 
    ... add value ... 

Answer 3

これは効くだろうか？

// Note the change from > to >= 
while(cur->next && (val >= cur->next->val)) 
{ cur = cur->next; 
} 

if (val == cur->val) 
{ return; 
} 

Answer 4

本番コードのためにこれを使用している場合にはオプションだ場合まあ、まず、あなたはおそらくstd::を使用する必要があります。

あなたのコードについて考えると、私はあなたが2つのポインタを保持しているべきだと思います。基本的に現在のものはNodeで、前のものはNodeです。 cur == NULLの場合は、prevの後に挿入してください。 cur->value == valの場合は、次に、cur->value < valかどうかを確認し、そうであれば両方のノードを進めることができます。

現在、*ppHead == NULLを処理する特別なコードがあります。ただし、prevをNode** curPtrとしている場合、これは必要ありません。だからcurPtr=ppHeadとcur=*curPtrから始めてください。そして、上記のアルゴリズムはすべてのために動作するはずです。

あなたのためにコードされた投稿者は、curPtr変数としてppHeadを使用し、curとして（* ppHead）を使用することができます。より読みやすいものがわからない