我在学习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->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
中,你需要在你做任何事情之前保存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) );
}