我在学习C和数据结构。我正在尝试创建一个带有一个哨兵的循环链表并打印6个数字。但我很难完成这项任务。我已经做了几个小时了。我卡住了。我希望有人能帮我看看我的代码,并给我一些提示,什么是问题。提前谢谢你的时间!
我试着在前面加上3个数字,在后面加上3个数字,然后打印出前面和后面的数字,就行了。但当我试图打印整个列表时,我只能得到3个数字或遇到错误。

    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


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);

/* 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)
{
    assert(q != 0);

    //allocate the sentinel
    q->Sentinel = malloc(sizeof(struct DLink));
    assert(q->Sentinel != 0);

    //the start point and end point are equal to each other
    //q->Sentinel->next = q->Sentinel;
    q->Sentinel->next = q->Sentinel->prev;

    //set the size of the deque
    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.
struct DLink * _createLink (TYPE val)
{
    /* FIXME: you must write this */
    /*temporary return value..you may need to change it*/
    //Create a new link to store the value
    struct DLink *new_lnk = malloc(sizeof(struct DLink));
    assert(new_lnk != 0);
    new_lnk->value = val;

    return new_lnk;
}

//Adds a link after another link
void _addLinkAfter(struct cirListDeque *q, struct DLink *lnk, struct DLink *newLnk)
{
    assert(q != 0);
    assert(lnk != 0);
    assert(newLnk != 0);

    //The existing link is before the new link
    lnk->next = newLnk;
    newLnk->prev = lnk;

    //The link that was originally after the existing link is after the new link
    newLnk->next = q->Sentinel->next;

    //The new link is the last link
    //q->Sentinel->prev = newLnk;

    //update the size field
    q->size++;
}

// Adds a link to the back of the deque
void addBackCirListDeque (struct cirListDeque *q, TYPE val)
{
    /* FIXME: you must write this */
    assert(q != 0);

    //Create the new back link
    struct DLink *new_backLnk = _createLink(val);
    struct DLink *tmp = q->Sentinel->prev;

    q->Sentinel->prev = new_backLnk;
    new_backLnk->prev = tmp;
    new_backLnk->next = q->Sentinel->next;

}

// Adds a link to the front of the deque
void addFrontCirListDeque(struct cirListDeque *q, TYPE val)
{
    /* FIXME: you must write this */
    assert(q != 0);

    //create a temp link for the link that is originally after the sentinel
    struct DLink *tmp = q->Sentinel->next;

    //allocate the new front link
    struct DLink *new_frontLnk = _createLink(val);

    //add the new front link after the Sentinel
    _addLinkAfter(q, q->Sentinel, new_frontLnk);

    //Put the old front link after the new front link
    new_frontLnk->next = tmp;

    //new_frontLnk->prev = q->Sentinel->prev;

}

// Get the value of the front of the deque
TYPE frontCirListDeque(struct cirListDeque *q)
{
    /* FIXME: you must write this */
    /*temporary return value..you may need to change it*/
    assert(q != 0);
    assert(q->size > 0);

    return q->Sentinel->next->value;
}

// Get the value of the back of the deque
TYPE backCirListDeque(struct cirListDeque *q)
{
    /* FIXME: you must write this */
    /*temporary return value..you may need to change it*/
    assert(q != 0);
    assert(q->size > 0);

    return q->Sentinel->prev->value;

}


// Check whether the deque is empty
int isEmptyCirListDeque(struct cirListDeque *q) {
    /* FIXME: you must write this */
    /*temporary return value..you may need to change it*/
    assert(q != 0);

    if (q->size == 0)
        return 1;

    return 0;
}

// Print the links in the deque from front to back
void printCirListDeque(struct cirListDeque *q)
{
    assert(q != 0);
    assert(!isEmptyCirListDeque(q));

    for (int i = 0; i < q->size; i++)
    {
        printf("The value is %g\n", q->Sentinel->next->value);
        q->Sentinel->next = q->Sentinel->next->next;
    }

}

最佳答案

在这段代码中,malloc不会初始化q->Sentinel并且您也不会初始化q->Sentinel->prev,因此q->Sentinel->nextq->Sentinel->prev的值是未定义的。所以,应该取消q->Sentinel->prev = q->Sentinel;行的注释。

void _initCirListDeque (struct cirListDeque *q)
{
    assert(q != 0);

    //allocate the sentinel
    q->Sentinel = malloc(sizeof(struct DLink));

    if( !q->Sentinel )
    {
         printf( "out of memory\n" );
         exit( -1 );
    }

    //the start point and end point are equal to each other
    q->Sentinel->prev = q->Sentinel->next = q->Sentinel;

    //set the size of the deque
    q->size = 0;
}

_addLinkAfter中,你需要在你做任何事情之前保存next的当前lnk属性,然后你需要把你的链接插入到现有的一个…
void _addLinkAfter(struct cirListDeque *q, struct DLink *lnk, struct DLink *newLnk)
{
    // preserve current linkage

    newLnk->prev = lnk;
    newLnk->next = lnk->next;

    // link in new record

    lnk->next = newLnk;
    newLnk->next->prev = newLnk;

    q->size++;
}

你可以优化你的addBackCirListDeque使用现有的_addLinkAfter
void addBackCirListDeque(struct cirListDeque *q, TYPE val)
{
    _addLinkAfter( q, q->Sentinel->prev, _createLink(val) );
}

对于addFrontCirListDeque
void addFrontCirListDeque(struct cirListDeque *q, TYPE val)
{
    _addLinkAfter( q, q->Sentinel, _createLink(val) );
}

10-08 12:29