c - 消除所有重复元素的出现

Question

我试图消除链表中所有重复元素的出现。 例如，如果我有:1-2-3-2-4-2-4，我想消除所有出现的2和4并得到:1-3

我使用一个名为eliminateRepeated的函数来迭代并计算出现次数；如果计数大于 1，则程序调用函数eliminateAllTheOc。但我得到了这个:1-3-2-4。最后出现的情况不会被消除。 例如，如果我使用值 4 单独调用函数 eliminateAllOc，它会正常工作并返回 1-2-3-2-2。

typedef struct{
    int num;
}t_dataL;

typedef struct s_nodeL{
    t_dataL dataL;
    struct s_nodeL *next;
}t_nodeL;

typedef t_nodeL *t_list;

int elimnateAllTheOc(t_list *l, t_dataL *d, int(*cmp)(const void*, const void*)){
    if(!*l) return 0;
    t_nodeL *aux;
    while(*l){
        if(cmp(&(*l)->dataL, d) == 0){
            aux = *l;
            *l = (*l)->next;
            free(aux);
        }
        else l = &(*l)->next;
    }
    return 1;
}

int eliminateRepeated(t_list *l, int(*cmp)(const void*, const void*)){
    t_list *plec, *ini = l;
    t_nodeL *aux;
    int n = 0;
    while (*l){
        plec = ini;
        while(*plec){
            if(cmp(&(*l)->dataL, &(*plec)->dataL) == 0) n++;
            plec = &(*plec)->next;
        }
        if(n > 1) eliminateAllTheOc(ini, &(*l)->dataL, cmp);
        else l = &(*l)->next;
        n = 0;
    }
    return 1;
}

如何消除重复元素的所有出现？

Answer 1

首先你必须修复错误的函数名称，即

int elimnateAllTheOc(...  ->  int eliminateAllTheOc(
                                      ^

那么您必须修复代码中的未定义行为。问题是您传递了一个指向比较值的指针，即 t_dataL *d。这是一个指向您要释放的列表元素内的数据的指针。因此，一旦释放该元素，取消引用 d 就是未定义的行为。

示例

考虑一个非常简单的列表:

1 -> 1

在这种情况下，您想要删除这两个元素。您可以使用指向第一个元素的指针来调用eliminateAllTheOc，并且为了比较值，您可以传递一个指向第一个元素中的dataL 的指针。

在第一个循环中，您释放了第一个元素。因此d不再指向有效的对象。因此，在下一个循环中，执行 *d 时，您会出现未定义的行为。

如果要传递一个指向比较值的指针，则必须确保该指针始终指向一个有效的对象。您可以通过复制来做到这一点:

    if(n > 1)
    {
        t_dataL tmp = (*l)->dataL;
        eliminateAllTheOc(ini, &tmp, cmp);
    }
    else l = &(*l)->next;

我怀疑这能解决代码的所有问题，但修复这个 UB 是重要的第一步。