线性表(四)--循环链表 (C语言实现)

想不到把 还有四。。。。其实还有五六七八九。。。。。

通过前面对单链表的学习,我们知道单链表只能从当前结点出发向后操作。那么啥叫循环链表结构嘞。循环循环,也就是首尾相接的链表,是不是很好理解。(我不会告诉你就是单链表的尾结点指向头结点或是第一个结点,一般仍以头结点表示一个链表)。。。。。

这样我们就可以从任一结点开始遍历整个链表,而不是只能从头结点开始。

如何创建就不再细写了,可以参考之前文章中的头插法和尾插法。

那么我们就来看看带头结点的循环单链表的一般形式循环单链表的合并吧。

遍历两链表找表尾;将第一表尾链接第二表头,将第二表尾链接第一表头就可以了。

LinkList merge_ 1(LinkListLA,LinkList LB) 
{  /*此算法将两个采用头指针的循环单链表的首尾连接起来*/ 
    Node *p, *q; 
    p=LA; q=LB; 
    while (p->next!=LA) 
        p=p->next; /*找到表LA的表尾,用p指向它*/ 
    while (q->next!=LB) 
        q=q->next; /*找到表LB的表尾,用q指向它*/ 
    q->next=LA; /*修改表LB 的尾指针,使之指向表LA 的头结点*/ 
    p->next=LB->next; /*修改表LA的尾指针,使之指向表LB 中的第一个结点*/ 
    free(LB); 
    return(LA); 
} 


LinkList  merge_2(LinkList RA,LinkList RB) 
{  /*此算法将两个采用尾指针的循环链表首尾连接起来*/ 
    Node *p; 
    p=RA->next; /*保存链表RA的头结点地址*/ 
    RA->next=RB->next->next;/*链表RB的开始结点链到链表RA的终端结点之后*/  
    free(RB->next);/*释放链表RB的头结点*/ 
    RB->next=p;/*链表RA的头结点链到链表RB的终端结点之后*/ 
    return  RB;/*返回新循环链表的尾指针*/ 
} 

这里有些地方需要说明一下,那就是可能->next->next有些绕,其实这是将其连到了第一个指针而不是头指针,这是有区别的。其次关于free()函数,free()的调用方式是:void free(void *ptr)。是释放由ptr所指的内存,并将它返回给堆,以便这些内存成为再分配时的可用内存,而不是将其置为null。
其实作为循环链表,连接时为什么非要找到头尾结点,我想了想,大概是因为头结点的存在吧,毕竟头结点对于整个表的内容是无关的。(当然也可能不是。。也可能可以随便找个结点。。。仍待考证。。。。)

总的来说,循环链表与单链表最大的区别就是可以从当前结点遍历所有结点。