链表之循环链表

发表于 | 分类于 | | 阅读次数:

上期文章介绍了单链表的一些基本功能函数，本次主要介绍循环链表的一些基本功能函数。循环链表其实就是将单链表的最后一个结点指向单链表的头结点，从而构成一个循环结构。本次函数功能主要包括链表创建函数（头插法和尾插法）、链表打印函数和两种链表是否有环的判定函数，以及最后的一个链表清除函数。
函数运行如下图所示：

cLinkList

功能函数

链表创建函数（头插法）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//定义循环链表生成函数（头插法）
void cListCreatHead(cLinkList *L, int n)
{
    int i;
    cLinkList *p, *r;
    p = L;
    p->data = rand() % 100 + 1;
    for(i = 1; i < n; ++i)
    {
        r = (cLinkList *)malloc(sizeof(cLinkList));
        r->data = rand() % 100 + 1;
        r->next = p;
        p = r;
    }
    L->next = p;
}

这里使用了头插法对链表进行生成操作，L作为cLinkList的一个指针，指向链表的最后一个结点，这里注意最后要将L指向p构建循环。

链表创建函数（尾插法）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//定义循环链表生成函数（尾插法）
void cListCreatTail(cLinkList *L, int n)
{
    int i;
    cLinkList *head, *p;
    head = L;
    L->data = rand() % 100 + 1;
    for(i = 1; i < n; i++)
    {
        p = (cLinkList *)malloc(sizeof(cLinkList));
        p->data = rand() % 100 + 1;
        L->next = p;
        L = p;
    }
    L->next = head;
}

这里使用了尾插法对链表进行生成操作，L作为cLinkList的一个指针，在创建过程中不断向后移动，最后指向链表的最后一个结点，这里注意最后要将L指向头结点指针head构建循环。

链表打印函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void cListPrint(cLinkList *L)
{
    cLinkList *head, *p;
    head = L;
    p = L;
    int count = 1;
    while(p->next != head)
    {
        printf("%d\t", p->data);
        p = p->next;
        count++;
    }
    printf("%d\n", p->data);
    printf("The length of this LinkList is: %d\n", count);
}

通过判定p->next ！= head为条件对链表进行遍历打印，在遍历过程中计算链表的长度并打印输出。

检测是否有环（方法一）

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
//检查是否有环（方法一）
int cListCheckLoop1(cLinkList *L)
{
    cLinkList *head, *p, *q;
    head = p = q = L;
    int countp, countq;
    countp = 1;
    while(1)
    {
        p=p->next;
        countp++;
        countq = 1;
        q = head;
        while(q != p)
        {
            q = q->next;
            countq++;
        }
        if(++countq != countp)
        {
            printf("YES!\nThere is a loop in the LinkList!\n");
            return 1;
        }
        if(p->next == NULL)
        {
            printf("NO!\nThere is no loop in the LinkLis!\n");
            return 0;
        }
    }
}

设置指针变量p对链表进行遍历，同时使用q对p之前的结点进行遍历，如果发现到达p所在结点的更短路径，则判定链表存在环。比如，p走了6步到达结点A，而q只需要3步即可到达结点A，则此时链表中必定存在环，换言之，此前p已经经过结点A了。

检测是否有环（方法二）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//检测链表是否有环（方法二）
int cListCheckLoop2(cLinkList *L)
{
    cLinkList *p, *q;
    p = q = L;
    while(p->next != NULL && p->next->next != NULL)
    {
        p = p->next->next;
        q = q->next;
        if(p == q)
        {
            printf("YES!\nThere is a loop in this LinkList\n");
            return 1;
        }
    }
    printf("NO!\nThere is no loop in the LinkList\n");
    return 0;
}

设置p的步长为2，q的步长为1，同时对链表进行遍历，如果在某个时刻p == q，则就可以断定链表中存在环。

链表清除

1
2
3
4
5
6
7
8
9
10
11
12
//链表清除函数
void cListClear(cLinkList *L)
{
    cLinkList *p, *temp;
    p = L->next;
    while(p != L)
    {
       temp = p;
       p = p->next;
       free(temp);
    }
}

使用free()函数对我们生成的链表空间进行遍历删除。

总体代码

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
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
#include <stdio.h>
#include <stdlib.h>
//定义循环链表结构
typedef struct node
{
    int data;
    struct node *next;
}cLinkList;

//定义循环链表生成函数（头插法）
void cListCreatHead(cLinkList *L, int n)
{
    int i;
    cLinkList *p, *r;
    p = L;
    p->data = rand() % 100 + 1;
    for(i = 1; i < n; ++i)
    {
        r = (cLinkList *)malloc(sizeof(cLinkList));
        r->data = rand() % 100 + 1;
        r->next = p;
        p = r;
    }
    L->next = p;
}

//定义循环链表生成函数（尾插法）
void cListCreatTail(cLinkList *L, int n)
{
    int i;
    cLinkList *head, *p;
    head = L;
    L->data = rand() % 100 + 1;
    for(i = 1; i < n; i++)
    {
        p = (cLinkList *)malloc(sizeof(cLinkList));
        p->data = rand() % 100 + 1;
        L->next = p;
        L = p;
    }
    L->next = head;
}

//打印链表
void cListPrint(cLinkList *L)
{
    cLinkList *head, *p;
    head = L;
    p = L;
    int count = 1;
    while(p->next != head)
    {
        printf("%d\t", p->data);
        p = p->next;
        count++;
    }
    printf("%d\n", p->data);
    printf("The length of this LinkList is: %d\n", count);
}

//检查是否有环（方法一）
int cListCheckLoop1(cLinkList *L)
{
    cLinkList *head, *p, *q;
    head = p = q = L;
    int countp, countq;
    countp = 1;
    while(1)
    {
        p=p->next;
        countp++;
        countq = 1;
        q = head;
        while(q != p)
        {
            q = q->next;
            countq++;
        }
        if(++countq != countp)
        {
            printf("YES!\nThere is a loop in the LinkList!\n");
            return 1;
        }
        if(p->next == NULL)
        {
            printf("NO!\nThere is no loop in the LinkLis!\n");
            return 0;
        }
    }
}

//检测链表是否有环（方法二）
int cListCheckLoop2(cLinkList *L)
{
    cLinkList *p, *q;
    p = q = L;
    while(p->next != NULL && p->next->next != NULL)
    {
        p = p->next->next;
        q = q->next;
        if(p == q)
        {
            printf("YES!\nThere is a loop in this LinkList\n");
            return 1;
        }
    }
    printf("NO!\nThere is no loop in the LinkList\n");
    return 0;
}

//清除链表
void cListClear(cLinkList *L)
{
    cLinkList *p, *temp;
    p = L->next;
    while(p != L)
    {
       temp = p;
       p = p->next;
       free(temp);
    }
}

//主函数
int main()
{
    int length = 10;
    cLinkList *L;
    L = (cLinkList *)malloc(sizeof(cLinkList));
    char operator;
    printf("1.生成链表（头插法）\n");
    printf("2.生成链表（尾插法）\n");
    printf("3.打印链表\n");
    printf("4.判断链表是否有环（方法一）\n");
    printf("5.判断链表是否有环（方法二）\n");
    printf("6.清除链表\n");
    printf("0.退出\n");
    while(1)
    {
        scanf("%c", &operator);
        switch(operator)
        {
            case '1':
                cListCreatHead(L, length);
                printf("**********生成链表（头）！**********\n");
                break;
            case '2':
                cListCreatTail(L, length);
                printf("**********生成链表（尾）！**********\n");
                break;
            case '3':
                printf("*************打印链表！*************\n");
                cListPrint(L);
                break;
            case '4':
                printf("***********是否有环（一）***********\n");
                cListCheckLoop1(L);
                break;
            case '5':
                printf("***********是否有环（二）***********\n");
                cListCheckLoop2(L);
                break;
            case '6':
                printf("*************清除链表！*************\n");
                cListClear(L);
                break;
            case '0':
                printf("***************退出*****************\n");
                free(L);
                return 0;
        }
    }
    return 0;
}
-------------本文结束感谢您的阅读-------------
0%