在C语言中删除双重链表中的重复项

Question

我正试图与200-800之间的SAT成绩的双重链接列表工作。我需要从列表中删除所有重复项，即通过删除所有重复项来确保每个等级只出现一次。

#define HIGHEST_GRADE 800
typedef struct dListNode{
    int* dataPtr;
    struct dListNode* next;
    struct dListNode* prev;
}DListNode;
typedef struct dList
{
    DListNode* head;
    DListNode* tail;
}DList;
void removeDuplicates(DList* lst)
{
    int i;
    int gradesBucket [numOfGrades];
    DListNode* temp;
    temp = lst->head;
    for(i=200 ; i<HIGHEST_GRADE ; i++) /*creating 600 buckets - each bucket for a grade*/
        gradesBucket[i] = FALSE;
    while (temp)
    {
        if ((gradesBucket [*temp->dataPtr]) == TRUE) /*if current grade has already  */
                                                     /* appeared earlier on the list */
        {
            deleteFromList (temp);  /*delete that grade's cell*/
        }
        else
            gradesBucket[*temp->dataPtr] = TRUE; /* mark grade bucket as true, meaning */
                                                 /* the grade already appeared*/
        temp = temp->next; /*moving on to next grade*/
    }
}
void deleteFromList(DListNode*  toRemove)
{
    toRemove->prev->next = toRemove->next;
    toRemove->next->prev = toRemove->prev;
    deAllocateListCell (toRemove);    
}
void deAllocateListCell (DListNode* cell)
{
    free (cell->dataPtr);
    free (cell);
}

请告诉我是怎么回事。

---

是修复后的代码，但仍然不能正常工作。现在它编译了，但是屏幕上没有显示任何东西。顺便说一下，我不需要处理删除头部的问题，因为第一个数字永远不能是重复的……但我照顾它的情况下，头部是NULL;
我还将我想要删除的前一个单元格发送给deleteFromList函数。还是不行。什么好主意吗?谢谢!

    void deleteFromList(DList* lst, DListNode*  p)
{
DListNode* del_cell = p->next;   /* cell to delete*/
if (p->next->next == NULL) /*if cell to remove is the tail*/
{
    deAllocateListCell (p->next); /* freeing current tail */
    lst->tail = p;  /* p is the new tail */
    p->next = NULL; /* tail points to NULL */
}
else /* if cell to remove is not the tail (note: can't be head beacuse no duplicates can be found in the first grade) */
{
    p->next = del_cell->next;
    del_cell->next->prev = p;
    deAllocateListCell (del_cell);
    }
}

Answer 1

函数deleteFromList()的代码不考虑(文字)边缘情况:删除列表的第一个或最后一个节点。

另外，你的代码解引用了一个指向已释放节点的指针;指针可能完全无效，或者free()函数可以覆盖其内容(正如Microsoft Debug C RunTime所知道的那样)。

Answer 2

1. 尽量具体-是什么不起作用?你的代码可以编译吗?运行时是否出现错误?在一个场景中，你没有得到预期的结果?

2. 你的deleteFromList函数应该照顾去除头部或尾部(即当toRemove->prev或toRemove->next为空(分别)。

3. temp = lst->head;，当lst为空时会发生什么?你会得到一个运行时错误

4. 您没有更新head或tail，以防它们被删除

这就是我第一眼看到的。

Answer 3

你应该写while(temp->next)来纠正这个....也可以使用free命令释放节点。为了消除悬空指针问题，你应该在释放该节点后将其设置为NULL