c语言 - 我的循环链表代码有什么问题？

Question

我正在学习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 %gn", q->Sentinel->next->value);
        q->Sentinel->next = q->Sentinel->next->next;
    }
}

Answer 1

在这段代码中，malloc没有初始化q->Sentinel，您也没有初始化q->Sentinel->prev，因此q->Sentinel->next和q->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 memoryn" );
         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中，你需要在做任何事情之前保留lnk的当前next属性，然后你需要将你的链接插入到现有的链接中…

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