链表，无重复 [英] linked list with no duplicates

问题描述

对于不重复的链表，我有以下代码(对于我的简单测试而言是正确的)，但我认为这有点难看.

I have the following code (correct for my simple tests) for a linked list for no duplicates, but I think it is a bit ugly.

有人可以推荐一种更干净的方式来处理重复代码吗?当前有问题的是:

Could anyone recommend a cleaner way to handle the duplicate code? The current piece in question is:

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

但是我认为使用比较运算符的不同用法可能会存在一个更好的解决方案(我没有看到).

But I think that a better solution might exist (that I don't see) using a different use of comparison operators.

另外，有人可以给我一个有用的"断言或在这里的建议.很难说出何时断言，特别是如果您有一个if语句为您做的话.

Also, can someone give me a suggestion for a "useful" assert or to inside here. It is hard to tell when to assert, especially if you have an if statement doing it for you.

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

推荐答案

我会这样写:

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

这篇关于链表，无重复的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！