鏈接列表沒有重複

我有下面的代碼（正確爲我的簡單測試）的鏈接列表沒有重複，但我認爲它有點難看。鏈接列表沒有重複

任何人都可以推薦一個更清潔的方式來處理重複的代碼？問題目前的段子：

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; 
}

來源

2009-09-01 teleball

也許你正在使用錯誤的數據結構作業。例如，您是否需要按特定順序存儲節點？如果不是，那麼使用哈希表或平衡二叉樹可以很容易地重寫代碼。 – Juliet 2009-09-01 19:27:47

感謝朱麗葉，但它是一個編碼威力的問題。 ;-)我不是一個真正的問題。 – teleball 2009-09-01 19:57:08

我會寫更像這樣的：

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; 
}

來源

2009-09-01 19:40:28

不錯的工作。我已經特別把頭埋了太久了！這是一個更清潔的方法。有點哈哈是我想要的！ – teleball 2009-09-01 19:59:01

-1

我想補充的方法，以節點執行查找操作（*未經測試的代碼）：

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 ...

來源

2009-09-01 19:26:05

因爲他試圖做一個排序列表，所以搜索完全匹配可能不會有幫助。 – clahey 2009-09-01 19:35:31

我必須錯過指定列表排序的部分。 – 2009-09-01 19:54:58

會這樣嗎？

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

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

來源

2009-09-01 19:42:50

這是正確的。我以前試過，其他東西一定是壞的。無論如何，在19K時，我認爲克里斯應該得到提升。但你是對的。 – teleball 2009-09-01 20:01:22

嗯，首先，如果你使用這種生產代碼，你或許應該使用std::如果這是一個選項。

我越想你的代碼，我越覺得你應該保留兩個指針。基本上一個到目前的Node和一個到以前的Node。如果cur == NULL，請在prev之後插入。如果cur->value == val，則返回。然後你可以檢查是否cur->value < val，如果是的話，推進兩個節點。

您目前有特殊的密碼來處理*ppHead == NULL。但是，如果您將prev改爲Node** curPtr，則這不是必需的。所以從curPtr=ppHead和cur=*curPtr開始。那麼上面的算法應該適用於整個事情。或者作爲剛發佈的人爲你編碼，你可以使用ppHead作爲curPtr變量本身和（* ppHead）作爲cur。不確定哪個更具可讀性。

來源

2009-09-01 19:43:35 clahey

鏈接列表沒有重複

回答

相關問題