【C 数据结构】循环链表

【 1. 基本原理 】

• 对于单链表以及双向链表，其就像一个小巷，无论怎么样最终都能从一端走到另一端，然而循环链表则像一个有传送门的小巷，因为循环链表当你以为你走到结尾的时候，其实你又回到了开头。
• 循环链表和非循环链表其实创建的过程以及思路几乎完全一样，唯一不同的是，非循环链表的尾结点指向空（NULL），而 循环链表的尾指针指向的是链表的开头。通过将单链表的尾结点指向头结点的链表称之为 循环单链表（Circular linkedlist）。如下图所示：
  

【 2. 循环链表的创建 】

2.1 循环链表结点设计

• 以单循环链表为例，对于循环单链表的结点，可以完全参照于单链表的结点设计，如图：
  • data表示数据，其可以是简单的类型（如int,double等等），也可以是复杂的结构体（struct类型）
  • next表示指针，它永远指向自身的下一个结点， 对于 只有一个结点的存在，这个next指针则永远指向自身，对于一个 循环链表的尾部结点，next永远指向开头。
    
• 其代码可以表示为：

typedef struct list
{
    int data;
    struct list *next;
}list;
//data为存储的数据，next指针为指向下一个结点
1
2
3
4
5
6

2.2 循环单链表初始化

• 如同单链表的创建，我们需要先创建一个头结点并且给其开辟内存空间，但与单链表不同的是，我们需要在开辟内存空间成功之后将头结点的next指向head自身。我们可以创建一个init函数来完成这件事情，为了以后的重复创建和插入，我们可以考虑 在init重创建的结点next指向空，而在主函数调用创建之后手动 将head头结点的next指针指向自身。这样的操作方式可以方便过后的创建单链表，直接利用多次调用的插入函数即可完成整体创建。
• C语言实现可以表示为：

//初始结点
list *initlist()
{
    list *head=(list*)malloc(sizeof(list));
    if(head==NULL)
    {
        printf("创建失败，退出程序");
        exit(0);
    }
    else
    {
        head->next=NULL;
        return head;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

• 在主函数重调用：

//初始化头结点
list *head=initlist();
head->next=head;
1
2
3

【 3. 循环链表的 插入 】

• 对于插入数据的操作，基本与单链表的插入操作相同，我们可以创建一个独立的结点，通过将需要插入的结点的上一个结点的next指针指向该节点，再由需要插入的结点的next指针指向下一个结点的方式完成插入操作。
  
• C 代码可以表示为：

//插入元素
//三个参数分别是链表，位置，参数
list *insert_list(list *head,int pos,int data)
{
    list *node=initlist();  //新建结点
    list *p=head;       //p表示新的链表
    list *t;
    t=p;
    node->data=data;
    if(head!=NULL)
    {
        for(int i=1;i<pos;i++)
        {
            t=t->next;  //走到需要插入的位置处
        }
        node->next=t->next;
        t->next=node;
        return p;
    }
    return p;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

【 4. 循环单链表的 删除操作 】

• 如图所示，循环单链表的删除操作可以参考单链表的删除操作，其都是 找到需要删除的结点，将其前一个结点的next指针直接指向删除结点的下一个结点 即可，但需要注意的是尾节点和头结点的特判，尤其是尾结点，因为删除尾节点后，尾节点前一个结点就成了新的尾节点，这个新的尾节点需要指向的是头结点而不是空，其重点可以记录为【删除节点的前一节点.next=删除结点.next】这样的操作可以省去头尾结点的特判：
  
• C 代码：

//删除元素
int delete_list(list *head) 
{
    if(head == NULL) 
    {
        printf("链表为空！\n");
        return 0;
    }
    //建立临时结点存储头结点信息（目的为了找到退出点）
    //如果不这么建立的化需要使用一个数据进行计数标记，计数达到链表长度时自动退出
    //循环链表当找到最后一个元素的时候会自动指向头元素，这是我们不想让他发生的
    list *temp = head; //作为遍历的前一个节点         
    list *ptr = head->next;//作为遍历的当前节点

    int del;
    printf("请输入你要删除的元素：");
    scanf("%d",&del);

    while(ptr != head) 
    {
        if(ptr->data == del) 
        {
            if(ptr->next == head) //如果是最后一个尾节点
            {
                temp->next = head;
                free(ptr);
                return 1;
            }
            temp->next = ptr->next;    //核心删除操作代码
            free(ptr);
            //printf("元素删除成功！\n");
            return 1;
        }
        temp = temp->next;
        ptr = ptr->next;
    }
    printf("没有找到要删除的元素\n");
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

【 5. 循环单链表的遍历 】

• 与普通的单链表和双向链表的遍历不同，循环链表需要进行结点的判断，找到尾节点的位置，由于尾节点的next指针是指向头结点的，所以不能使用链表本身是否为空（NULL）的方法进行简单的循环判断，我们需要通过判断结点的next指针是否等于头结点的方式进行是否完成循环的判断。
• 此外还有一种计数的方法，即建立一个计数器count=0，每一次next指针指向下一个结点时计数器加一，当count数字与链表的节点数相同的时候即完成循环，这样做有一个 问题就是获取到链表的节点数同时也需要完成一次遍历才可以达成目标。
• C代码：

//遍历元素
int display(list *head) 
{
    if(head != NULL) 
    {
        list *p  = head;
        //遍历头节点到，最后一个数据
        while(p->next != head ) 
        {
            printf("%d   ",p->next->data);
            p = p->next;
        }
        printf("\n");   //习惯性换行
        //把最后一个节点赋新的节点过去
        return 1;
    }
    else
    {
        printf("头结点为空!\n");
        return 0;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

【 6. 实例 - 循环链表的 增删查改 】

 #include<stdio.h>
#include<stdlib.h>
typedef struct list{
    int data;
    struct list *next;
}list;
//data为存储的数据，next指针为指向下一个结点
 
//初始结点
list *initlist(){
    list *head=(list*)malloc(sizeof(list));
    if(head==NULL){
        printf("创建失败，退出程序");
        exit(0);
    }else{
        head->next=NULL;
        return head;
    }
}
 
//创建--插入数据
int create_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;
    }
 
}
 
//插入元素
list *insert_list(list *head,int pos,int data){
    //三个参数分别是链表，位置，参数
    list *node=initlist();  //新建结点
    list *p=head;       //p表示新的链表
    list *t;
    t=p;
    node->data=data;
    if(head!=NULL){
        for(int i=1;i<=pos;i++){
            t=t->next;
        }
        node->next=t->next;
        t->next=node;
        return p;
    }
    return p;
}
 
//删除元素
int delete_list(list *head) {
    if(head == NULL) {
        printf("链表为空！\n");
        return 0;
    }
    //建立零时结点存储头结点信息（目的为了找到退出点）
    //如果不这么建立的化需要使用一个数据进行计数标记，计数达到链表长度时自动退出
    //循环链表当找到最后一个元素的时候会自动指向头元素，这是我们不想让他发生的
    list *temp = head;          
    list *ptr = head->next;
 
    int del;
    printf("请输入你要删除的元素：");
    scanf("%d",&del);
 
    while(ptr != head) {
        if(ptr->data == del) {
            if(ptr->next == head) { //循环结束的条件换成ptr->next == head
                temp->next = head;
                free(ptr);
                return 1;
            }
            temp->next = ptr->next;
            free(ptr);
            //printf("元素删除成功！\n");
            return 1;
        }
        temp = temp->next;
        ptr = ptr->next;
    }
    printf("没有找到要删除的元素\n");
    return 0;
}
 
 
//遍历元素
int display(list *head) {
    if(head != NULL) {
        list *p  = head;
        //遍历头节点到，最后一个数据
        while(p->next != head ) {
            printf("%d   ",p->next->data);
            p = p->next;
        }
        printf("\n");   //习惯性换行 ( o=^•ェ•)o　┏━┓
        //把最后一个节点赋新的节点过去
        return 1;
    } else {
        printf("头结点为空!\n");
        return 0;
    }
}
 
int main(){
    //初始化头结点//
    list *head=initlist();
    head->next=head;
    通过插入元素完善链表/
    for(int i=0;i<5;i++){   //只是演示使用，不具体提供输入
        create_list(head);
    }
    display(head);
    插入元素
    head=insert_list(head,1,10);
    display(head);
    删除元素
    delete_list(head);
    display(head);
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136

【 7. 双向循环链表 】

• 循环链表还有一个进阶的概念练习，同双向链表与单链表的关系一样，循环单链表也有一个孪生兄弟——双向循环链表，其设计思路与单链表和双向链表的设计思路一样，就是 在原有的双向链表的基础上，将尾部结点和头部结点进行互相连接。