首页  /  数据结构教程  /  循环链表一  /  

循环链表一

点击打开在线编译器,边学边练

1.        循环链表概念

对于单链表以及双向链表,其就像一个小巷,无论怎么样最终都能从一端走到另一端,然而循环链表则像一个有传送门的小巷,因为循环链表当你以为你走到结尾的时候,其实你又回到了开头。

循环链表和非循环链表其实创建的过程以及思路几乎完全一样,唯一不同的是,非循环链表的尾结点指向空(NULL),而循环链表的尾指针指向的是链表的开头。通过将单链表的尾结点指向头结点的链表称之为循环单链表(Circular linkedlist)

如图,为一个完整的循环单链表

111.png

2.  循环链表结点设计(以单循环链表为例)

对于循环单链表的结点,可以完全参照于单链表的结点设计,如图:

222.png

data表示数据,其可以是简单的类型(如int,double等等),也可以是复杂的结构体(struct类型)

next表示指针,它永远指向自身的下一个结点,对于只有一个结点的存在,这个next指针则永远指向自身,对于一个链表的尾部结点,next永远指向开头。

其代码可以表示为:

typedef struct list{
    int data;
    struct list *next;
}list;
//data为存储的数据,next指针为指向下一个结点

3. 循环单链表初始化

如同单链表的创建,我们需要先创建一个头结点并且给其开辟内存空间,但与单链表不同的是,我们需要在开辟内存空间成功之后将头结点的next指向head自身,我们可以创建一个init函数来完成这件事情,为了以后的重复创建和插入,我们可以考虑在init重创建的结点next指向空,而在主函数调用创建之后手动讲head头结点的next指针指向自身。

这样的操作方式可以方便过后的创建单链表,直接利用多次调用的插入函数即可完成整体创建。

其代码可以表示为:

//初始结点
list *initlist(){
    list *head=(list*)malloc(sizeof(list));
    if(head==NULL){
        printf("创建失败,退出程序");
        exit(0);
    }else{
        head->next=NULL;
        return head;
    }
}

在主函数重调用可以是这样

在主函数重调用可以是这样
    //////////初始化头结点//////////////
    list *head=initlist();
    head->next=head;

4. 循环链表的创建操作

如图所示:

333.png

我们可以通过逐步的插入操作,创建一个新的节点,将原有链表尾结点的next指针修改指向到新的结点,新的结点的next指针再重新指向头部结点,然后逐步进行这样的插入操作,最终完成整个单项循环链表的创建。

 

其代码可以表示为:

//创建——插入数据
int insert_list(list *head){
    int data;   //插入的数据类型
    printf("请输入要插入的元素:");
    scanf("%d",&data);
 
    list *node=initlist();
    node->data=data;
    //初始化一个新的结点,准备进行链接
 
    if(head!=NULL){
        list *p=head;
        //找到最后一个数据
        while(p->next!=head){
            p=p->next;
        }
        p->next=node;
        node->next=head;
        return 1;
    }else{
        printf("头结点已无元素\n");
        return 0;
    }
 
}


上一课:双向链表二 下一课:循环链表二
第一章 数据结构入门
第二章 链表
第三章 栈
第四章 队列
第五章 从C语言到C++
第六章 串,数组,矩阵,广义表
第七章 树
第八章 图
第九章 算法—查找
第十章 算法—排序
第十一章 算法&竞赛,思维培养
第十二章 后记