我的循环链表的代码有什么问题？

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 %g\n", 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 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你需要你做任何事情，那么你需要插入你的链接到现有的人之前先保存的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)); 
}