双向链表中删除重复项的解决方案不起作用

Question

我已经编写了用于删除双向链接循环列表中重复元素的函数。但是，当删除后遍历列表时，我没有得到所需的输出。

我用

typedef

来包围

#define MAX 10

typedef struct node {
    int data;
    struct node *next, *prev;
} NODE;

NODE *rem(NODE *head) {
    NODE *node = head;
    int hash[MAX] = { 0 };
    while (node != NULL) {
        hash[node->data]++;
        node = node->next;
    }
    node = head;
    NODE *node2 = head->next;
    while (node2 != NULL) {
        if (hash[node2->data] != 1) {
            NODE *r = node2;
            node->next = node2->next;
            node2->next->prev = node;
            free(r);
            hash[node->data]--;
        }
        node = node2;
        node2 = node2->next;
    }
    return head;
}

使用调试器显示分段错误：

hash[node->data]++;

我创建了一个哈希数组来记录重复元素的计数并不断删除元素，直到每个元素的计数为 1。 但是在函数之后遍历列表不会给出任何输出。

Answer 1

您的代码中存在多个问题：

• 所有节点的

  data

  成员中的值必须在

  0

  到

  MAX-1

  范围内。您至少应该验证这一点以避免在数组之外写入

  hash

  。名称

  MAX

  表明数组的长度应为

  MAX + 1

  ，但测试实际值是一个有用的预防措施。
• 如果列表是循环的，则测试空

  next

  成员是不正确的：您应该测试当前节点是否已循环回列表的

  head

  。

这是修改后的版本：

typedef struct node {
    int data;
    struct node *next, *prev;
} NODE;

// remove duplicates in the doubly linked circular list.
NODE *rem(NODE *head) {
    if (head != NULL) {
        NODE *node = head;
        for (;;) {
            NODE *next = node->next;
            while (next != head) {
                if (next->data == node->data) {
                    // next is a duplicate of node: detach and free it
                    NODE *r = next;
                    next->next->prev = next->prev;
                    next = next->prev->next = next->next;
                    free(r);
                } else {
                    next = next->next;
                }
            }
            node = node->next;
            if (node == head)
                break;
        }
    }
    return head;
}