链接列表没有重复

我有下面的代码（正确为我的简单测试）的链接列表没有重复，但我认为它有点难看。链接列表没有重复

任何人都可以推荐一个更清洁的方式来处理重复的代码？问题目前的段子：

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

链接列表没有重复

回答

相关问题