单向循环链表
循环链表的最后一个结点的指针是指向该循环链表的第一个结点或者表头结点,从而构成一个环形的链。单链表的最后一个结点的指针是置为NULL。
单向循环链表的遍历:判断该结点链域的值是否是表头结点,当链域值等于表头指针时,说明已到表尾。而非循环单链表判断链域值是否为NULL。
单向循环链表的4种不同的形式:
//循环链表的创建:
node *create_list_loop()
{
node *h=NULL;
while(1)
{
node *p=(node *)malloc(sizeof(node));
if(p==NULL)
{
return h;
}
memset(p,0,sizeof(node));
printf("Please input a data\n");
scanf_s("%d",&p->value);
p->next=NULL;
if(h==NULL) //如果头结点指针为空,表明这是创建的第一个结点
{
h=p;
p->next=h;
}
else
{
node *q=h;
while(q->next!=h)//q->next如果等于h,那么q就是最后一个结点
{
q=q->next;
}
q->next = p;
p->next =h;//将p的next指针指向h,构成一个循环
}
if(p->value==0)
{
break;
}
}
return h;
}
//循环链表的遍历方法,注意循环条件的判断:
void traverse_loop_list(node *h)
{
node *p=h;
do
{
printf("%d ",p->value);
p=p->next;
}while(p!=h);
printf("\n");
}
//循环链表的销毁方法
void destroy_loop_list(node *h)
{
node *p=h;
do
{
node *q=p;
p=p->next;
free(q);
} while (p!=h);
}
//步长法判断链表是否含有循环
//思路是:定义2个指针遍历该链表,1个指针跑一步,1个指针跑两步;
//那么如果两个指针相遇,则表示有循环,否则无循环。
bool is_a_loop_list(node *h)
{
node *p=h;
node *q=h->next;
while(p&&q&&q!=p&&q->next)
{
p=p->next;
q=q->next->next;
}
if(p==q)//循环退出,p和q相等了,表示链表中存在循环
{
return true;
}
return false;
}