title: 数据结构与算法（四）循环链表date: 2021-06-25 20:44:55.983

updated: 2021-06-26 00:14:36.877
url: /?p=261
categories: 数据结构与算法
tags: 数据结构与算法

循环列表

链表的两头连接，使其成为了一个环状链表，通常称为循环链表。

需要注意的是，虽然循环链表成环状，但本质上还是链表，因此在循环链表中，依然能够找到头指针和首元节点等。循环链表和普通链表相比，唯一的不同就是循环链表首尾相连，其他都完全一样。

循环链表实现约瑟夫环

约瑟夫环问题，是一个经典的循环链表问题，题意是：已知 n 个人（分别用编号 1，2，3，…，n 表示）围坐在一张圆桌周围，从编号为 k 的人开始顺时针报数，数到 m 的那个人出列；他的下一个人又从 1 开始，还是顺时针开始报数，数到 m 的那个人又出列；依次重复下去，直到圆桌上剩余一个人。

如图 2 所示，假设此时圆周周围有 5 个人，要求从编号为 3 的人开始顺时针数数，数到 2 的那个人出列：

出列顺序依次为：

  1. 编号为 3 的人开始数 1，然后 4 数 2，所以 4 先出列；
  2. 4 出列后，从 5 开始数 1，1 数 2，所以 1 出列；
  3. 1 出列后，从 2 开始数 1，3 数 2，所以 3 出列；
  4. 3 出列后，从 5 开始数 1，2 数 2，所以 2 出列；
  5. 最后只剩下 5 自己，所以 5 胜出。

约瑟夫环问题有多种变形，比如顺时针转改为逆时针等，虽然问题的细节有多种变数，但解决问题的中心思想是一样的，即使用循环链表。

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
#include <stdio.h>
#include <stdlib.h>

typedef struct Node
{
    int data;
    struct Node *next;
} person;

person *initLinkAndData(int number);
void displayLink(person *p);
void findAndKill(person *ptr, int k, int m);

int main()
{
    person *p = initLinkAndData(5);
    displayLink(p);
    findAndKill(p, 3, 2);
    return 0;
}

person *initLinkAndData(int number)
{
    person *ptr = (person *)malloc(sizeof(person));
    ptr->data = 0;
    ptr->next = NULL;
    //
    person *temp = ptr;
    for (size_t i = 1; i <= number; i++)
    {
        person *temp1 = (person *)malloc(sizeof(person));
        temp1->data = i;
        temp1->next = NULL;
        //
        temp->next = temp1;
        temp = temp->next;
    }

    temp->next = ptr->next;

    return ptr;
}

void displayLink(person *p)
{
    printf("输出双向列表：");
    person *temp = p;
    do
    {
        temp = temp->next;
        printf("%d --> ", temp->data);
    } while (p->next != temp->next);

    printf("%d \n", p->next->data);
}

void findAndKill(person *ptr, int k, int m)
{
    person *temp = ptr;
    //起始节点
    person *currentNode = temp->next;
    //找到编号为K的人
    while (temp->data != k)
    {
        temp = temp->next;
        currentNode = temp;
    }

    //从编号K开始计数。
    while (currentNode->next != currentNode)
    {
        for (size_t i = 1; i < m; i++)
        {
            temp = currentNode;
            currentNode = currentNode->next;
        }
        temp->next = currentNode->next;
        printf("出列人的编号为:%d\n", currentNode->data);
        free(currentNode);
        currentNode = temp->next;
    }
    printf("优胜者的编号为:%d\n", currentNode->data);
    free(currentNode);
}
1
2
3
4
5
6
7
请输入人数：5
输出双向列表：1 --> 2 --> 3 --> 4 --> 5 --> 1 
出列人的编号为:4
出列人的编号为:1
出列人的编号为:3
出列人的编号为:2
优胜者的编号为:5
1
2
3
4
5
6
7
8
9
10
11
12
请输入人数：10
输出双向列表：1 --> 2 --> 3 --> 4 --> 5 --> 6 --> 7 --> 8 --> 9 --> 10 --> 1 
出列人的编号为:4
出列人的编号为:6
出列人的编号为:8
出列人的编号为:10
出列人的编号为:2
出列人的编号为:5
出列人的编号为:9
出列人的编号为:3
出列人的编号为:1
优胜者的编号为:7

双向循环链表

单链表通过首尾连接可以构成单向循环链表。

双向链表也可以进行首尾连接，构成双向循环链表。

当问题中涉及到需要 “循环往复” 地遍历表中数据时，就需要使用双向循环链表。例如，前面章节我们对约瑟夫环问题进行了研究，其实约瑟夫环问题有多种玩法，每次顺时针报数后，下一轮可以逆时针报数，然后再顺时针……一直到剩下最后一个人。解决这个问题就需要使用双向循环链表结构。

双向循环链表的创建

创建双向循环链表，只需在创建完成双向链表的基础上，将其首尾节点进行双向连接即可。

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
#include <stdio.h>
#include <stdlib.h>

typedef struct Node
{
    struct Node *prior;
    int data;
    struct Node *next;
} node;

node *initLink();
void initData(node *, int);
void displayLink(node *);

int main()
{
    int num = 0;
    scanf("%d", &num);
    node *myLink = initLink();
    initData(myLink, num);
    displayLink(myLink);
    return -1;
}

node *initLink()
{
    node *head = (node *)malloc(sizeof(node));
    head->data = 0;
    head->next = NULL;
    head->prior = NULL;
    return head;
}

void initData(node *head, int num)
{
    node *temp = head;
    for (size_t i = 0; i < num; i++)
    {
        node *newNode = (node *)malloc(sizeof(node));
        newNode->data = i * 10;
        newNode->next = NULL;
        newNode->prior = NULL;
        //
        temp->next = newNode;
        newNode->prior = temp;
        temp = temp->next;
    }
    //连接首尾，实现闭环，完成双向循环链表
    temp->next = head->next;
    head->next->prior = temp;
}

void displayLink(node *head)
{
    node *temp = head;
    do
    {
        temp = temp->next;
        printf("%d --> ", temp->data);
    } while (temp->next != head->next);

    printf("%d", head->next->data);
    printf("\n");
}
1
2
10
0 --> 10 --> 20 --> 30 --> 40 --> 50 --> 60 --> 70 --> 80 --> 90 --> 0

练习

  1. c编程网