1

好的，所以我正在执行一项任务，您必须在 C 中构建一个循环双端队列。我已经实现了所有功能，并且正在测试它们。在“反向”功能之前，一切都很好。

我认为这很容易，您创建一个新链接，将其连接到 Sentinel 的位置。杀死旧哨兵，然后将双端队列的哨兵设置为新链接。

但是，当我运行它时，我得到一个 malloc 错误，并且由于我是 C 新手，我不确定如何调试。

- - - - 错误 - - - -

prog(10346) malloc: *对象 0x7faf13c03920 的错误：未分配被释放的指针 在 malloc_error_break 中设置断点以进行调试

代码

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <float.h>
#include "cirListDeque.h"

/* Double Link Struture */
struct DLink {
    TYPE value;/* value of the link */
    struct DLink *next;/* pointer to the next link */
    struct DLink *prev;/* pointer to the previous link */
};

# define TYPE_SENTINEL_VALUE DBL_MAX 


/* ************************************************************************
 Deque ADT based on Circularly-Doubly-Linked List WITH Sentinel
 ************************************************************************ */

struct cirListDeque {
    int size;/* number of links in the deque */
    struct DLink *Sentinel; /* pointer to the sentinel */
};
/* internal functions prototypes */
struct DLink* _createLink (TYPE val);
void _addLinkAfter(struct cirListDeque *q, struct DLink *lnk, struct DLink *newLnk);
void _removeLink(struct cirListDeque *q, struct DLink *lnk);



/* ************************************************************************
    Deque Functions
************************************************************************ */

/* Initialize deque.

    param:  q       pointer to the deque
    pre:    q is not null
    post:   q->backSentinel is allocated and q->size equals zero
*/
void _initCirListDeque (struct cirListDeque *q) 
{
    struct DLink* lnk = (struct DLink*)malloc(sizeof(struct DLink));
    assert(lnk != 0);   //sentinel made
    q->Sentinel = lnk;
    q->Sentinel->next = q->Sentinel->prev = q->Sentinel;
    q->size = 0;
}

/*
 create a new circular list deque
 */
struct cirListDeque *createCirListDeque()
{
    struct cirListDeque* newCL = malloc(sizeof(struct cirListDeque));
    _initCirListDeque(newCL);
    return(newCL);
}


/* Create a link for a value.

    param:  val     the value to create a link for
    pre:    none
    post:   a link to store the value
*/
struct DLink * _createLink (TYPE val)
{
    struct DLink* lnk = (struct DLink*) malloc(sizeof(struct DLink));
    lnk->value = val;
    return(lnk);

}

/* Adds a link after another link

    param:  q       pointer to the deque
    param:  lnk     pointer to the existing link in the deque
    param:  newLnk  pointer to the new link to add after the existing link
    pre:    q is not null
    pre:    lnk and newLnk are not null
    post:   the new link is added into the deque after the existing link
*/
void _addLinkAfter(struct cirListDeque *q, struct DLink *lnk, struct DLink *newLnk)
{
    lnk->next->prev = newLnk;       //right connects to new
    newLnk->next = lnk->next;       //new connect to right
    newLnk->prev = lnk;             //new connect to left
    lnk->next = newLnk;             //left connect to new
    q->size++;
}

/* Adds a link to the back of the deque

    param:  q       pointer to the deque
    param:  val     value for the link to be added
    pre:    q is not null
    post:   a link storing val is added to the back of the deque
*/
void addBackCirListDeque (struct cirListDeque *q, TYPE val) 
{
    struct DLink* lnk = _createLink(val);
    _addLinkAfter(q, q->Sentinel->prev, lnk);
}

/* Adds a link to the front of the deque

    param:  q       pointer to the deque
    param:  val     value for the link to be added
    pre:    q is not null
    post:   a link storing val is added to the front of the deque
*/
void addFrontCirListDeque(struct cirListDeque *q, TYPE val)
{
    struct DLink* lnk = _createLink(val);
    _addLinkAfter(q, q->Sentinel, lnk);
}

/* Get the value of the front of the deque

    param:  q       pointer to the deque
    pre:    q is not null and q is not empty
    post:   none
    ret:    value of the front of the deque
*/
TYPE frontCirListDeque(struct cirListDeque *q) 
{
    return q->Sentinel->next->value;
}

/* Get the value of the back of the deque

    param:  q       pointer to the deque
    pre:    q is not null and q is not empty
    post:   none
    ret:    value of the back of the deque
*/
TYPE backCirListDeque(struct cirListDeque *q)
{
    return q->Sentinel->prev->value;
}

/* Remove a link from the deque

    param:  q       pointer to the deque
    param:  lnk     pointer to the link to be removed
    pre:    q is not null and q is not empty
    post:   the link is removed from the deque
*/
void _removeLink(struct cirListDeque *q, struct DLink *lnk)
{
    //assert(!isEmptyList(lst));
    lnk->next->prev = lnk->prev;    //connect right link to left link
    lnk->prev->next = lnk->next;    //connect left link to right link
    q->size--;
    free(lnk);
}

/* Remove the front of the deque

    param:  q       pointer to the deque
    pre:    q is not null and q is not empty
    post:   the front is removed from the deque
*/
void removeFrontCirListDeque (struct cirListDeque *q) {
    _removeLink(q, q->Sentinel->next);
}


/* Remove the back of the deque

    param:  q       pointer to the deque
    pre:    q is not null and q is not empty
    post:   the back is removed from the deque
*/
void removeBackCirListDeque(struct cirListDeque *q)
{
    _removeLink(q, q->Sentinel->prev);
}

/* De-allocate all links of the deque

    param:  q       pointer to the deque
    pre:    none
    post:   All links (including backSentinel) are de-allocated
*/
void freeCirListDeque(struct cirListDeque *q)
{
    while (q->size > 0){
        removeFrontCirListDeque(q);
    }
    free(q->Sentinel);
}

/* Check whether the deque is empty

    param:  q       pointer to the deque
    pre:    q is not null
    ret:    1 if the deque is empty. Otherwise, 0.
*/
int isEmptyCirListDeque(struct cirListDeque *q) {
    return q->size == 0;
}

/* Print the links in the deque from front to back

    param:  q       pointer to the deque
    pre:    q is not null and q is not empty
    post:   the links in the deque are printed from front to back
*/
void printCirListDeque(struct cirListDeque *q)
{
    struct DLink *current;
    int x = 0;
    assert(!isEmptyCirListDeque(q));

    current = q->Sentinel->next;
    while(current != q->Sentinel){
        printf("value: %f\t", current->value);
        current = current->next;
        x++;
        if (x >= 6){
            printf("\n");
            x = 0;
        }
    }
}

/* Reverse the deque

    param:  q       pointer to the deque
    pre:    q is not null and q is not empty
    post:   the deque is reversed
*/
void reverseCirListDeque(struct cirListDeque *q)
{
    //struct DLink *temp = _createNewLink(0); //try this allocat then assign then move
    struct DLink *newSent = (struct DLink*) malloc(sizeof(struct DLink));
        newSent->next = q->Sentinel->prev;
        newSent->prev = q->Sentinel->next;
        q->Sentinel->next->prev = newSent;
        q->Sentinel->prev->next = newSent;
        free(q->Sentinel);
        q->Sentinel = newSent;

/* A different approach that didn't work.
        temp->next = q->Sentinel->prev;
            q->Sentinel->prev = q->Sentinel->next;
            q->Sentinel->next = temp->next;
            free(temp);*/
}
4

3 回答 3

1

对于调试 C 程序，gdb是最好的。学习如何使用它会对你有很多好处。该文档位于http://sourceware.org/gdb/current/onlinedocs/gdb/

如果您真的想要一个 GUI 前端（并且“gdb -tui”是不可接受的），请尝试ddd或insight。

调试器将帮助您在程序运行时继续前进，并使您能够在每一步检查您的数据结构，以便您可以在第一次损坏时找到我们的数据结构。

于 2012-10-19T20:23:56.030 回答
0

我的调试方法是添加 printfs。例如，在 malloc 调用后_initCirListDeque添加：

fprintf(stderr, "dbg malloc sentinel %p\n", (void *)lnk);

在 malloc in 之后添加类似的行reverseCirListDeque。

然后在调用 free in 和 之前添加类似的_removeLinkprintffreeCirListDeque行reverseCirListDeque。

当您运行代码时，您应该在标准错误中看到指针地址被 malloc 和释放。您应该能够查看未能释放的值是否已被释放（我的猜测是这就是正在发生的事情）。

这个词的目的dbg是使搜索这些调试 printfs 并在找到错误后将其删除变得容易。

于 2012-10-19T20:38:29.957 回答
0

我在这里回答我自己的问题，但感谢海报，调试技巧使这个答案成为可能。

我的逻辑有缺陷。

我认为如果你颠倒哨兵的方向，你可以颠倒循环列表的顺序。但是，即使您将所有四个链接更改为前哨，周围的链接 prev 和 next 字段也会指向错误的方向。

为了解决这个问题，我使用以下代码创建了一个新的双端队列：

    void reverseCirListDeque(struct cirListDeque *q)
{
    struct cirListDeque* newQ = createCirListDeque();
    while(!isEmptyCirListDeque(q)){
        addBackCirListDeque(newQ, backCirListDeque(q));
        removeBackCirListDeque(q);
    }
    q->Sentinel = newQ->Sentinel;
    q->size = newQ->size;
    free(newQ);
}
于 2012-10-19T22:04:55.190 回答