-1

我正在尝试使用 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);
}

请帮助我了解问题所在。

这是固定代码，但仍然无法正常工作。现在它编译但屏幕上没有显示任何内容。顺便说一句，我不需要删除头部，因为第一个数字永远不能重复......但我会处理它以防头部为空；
我还将我要删除的单元格的前一个单元格发送到函数 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);
    }
}
4

3 回答 3

2

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

另外，您的代码取消引用指向已释放节点的指针；指针可能会变得完全无效，或者free()函数可能会覆盖其内容（正如 Microsoft Debug C RunTime 已知的那样）。

于 2013-04-17T12:12:18.927 回答
1

  1. 试着具体一点 - 什么是行不通的？你的代码编译了吗？运行时是否出错？您在某个场景中没有得到预期的结果？

  2. 您的deleteFromList函数应该注意移除头部或尾部（即何时toRemove->prev或toRemove->next为空（分别）。

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

  4. 您没有更新head或tail万一它们被删除

这就是我第一眼发现的。

于 2013-04-17T12:23:48.293 回答
0

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

于 2013-04-17T12:21:43.030 回答