· 拓展单向循环链表

—————————————本文旨在讨论计算机知识欢迎指正——————————————— 书接上回：我们已经了解了链表如何编写与前置节点和头指针两种表示方式，下面，我们来了解进阶写法———如何实现单向循环链表。下面，我们来梳理一下循环链表的实现方式：这是朴素的链表实现形式：这是我们理想中的循环链表实现形式：这就是我们大体的思路，然后，我们将要实现它：

首先，我们第一个难点就是———如何来构造链表的结构体；因为我们需要循环，那么我们必须要知道尾巴在哪里，所以结构体里必须有tail这一容器，然后我们还要考虑如果每次我们都用一个迭代器去迭代遍历找尾巴tail的话，效率会非常低，我们需要一个更好的表示形式

1
// 定义节点结构
2
typedef int Element;
3
typedef struct _loop_node {
4
Element val;//数据域
5
struct _loop_node *next;//地址域，指向下一个
6
} LoopNode;
7

8
// 定义单向循环链表的头结构
9
typedef struct {
10
LoopNode header;//头结点
11
LoopNode *tail;//尾巴的容器，相当于一个移动指针迭代器；
12
int num;//计数器，用来遏制循环次数，防止无限循环
13
} LinkLoopList;

于是，笔者想到了两种结构，分别是头插法和尾插法： 1、头插法：

1
int insertLinkLoopHeader(LinkLoopList* link_loop, Element value) {
2
// 1. 先有新节点
3
LoopNode *node = malloc(sizeof(LoopNode));
4
if (node == NULL) {
5
return -1;
6
}
7
node->val = value;//新节点赋值
8
node->next = link_loop->header.next;//插到头结点的下一个元素的前面；
9
link_loop->header.next = node;//更新头结点在新节点的前面
10

11
// 2. 判断尾指针是否需要更新
12
if (link_loop->tail== &link_loop->header) {
13
link_loop->tail = node;
14
}
15
++link_loop->num;
16
return 0;
17
}

2、尾插法：

1
int insertLinkLoopTail(LinkLoopList* link_loop, Element value) {
2
// 1. 先有新节点
3
LoopNode *node = malloc(sizeof(LoopNode));
4
if (node == NULL) {
5
return -1;
6
}
7
node->val = value;
8
node->next = link_loop->tail->next;//尾部插入
9
link_loop->tail->next = node;//与原尾部节点衔接
10
link_loop->tail = node;//更新尾部
11

12
++link_loop->num;//更新数量
13

14
return 0;
15
}

然后我们从头考虑初始化和声明结构体：

1
// 定义节点结构
2
typedef int Element;
3
typedef struct _loop_node {
4
Element val;
5
struct _loop_node *next;
6
} LoopNode;
7

8
// 定义单向循环链表的头结构
9
typedef struct {
10
LoopNode header;
11
LoopNode *rear;
12
int num;
13
} LinkLoopList;

这是初始化：

1
void initLinkLoopList(LinkLoopList* link_loop) {
2
link_loop->header.next = link_loop->tail = &link_loop->header;//头指针和尾指针同时指向头结点
3
link_loop->num = 0;
4
}

删除：

1
int deleteLinkLoopList(LinkLoopList* link_loop, Element value) {
2
LoopNode *node = &link_loop->header;
3

4
while (node->next != &link_loop->header && node->next->val != value) {
5
node = node->next;
6
}
7
if (node->next->val == value) {
8
LoopNode *tmp = node->next;
9
node->next = tmp->next;
10
free(tmp);//释放空间，删除操作
11
--link_loop->num;
12
} else {
13
printf("No %d element!\n", value);
14
}
15
return 0;
16
}

呈现操作：

1
void showLinkLoopList(const LinkLoopList* link_loop) {
2
LoopNode *node = link_loop->header.next;
3
while (node != &link_loop->header) {
4
printf("\t%d", node->val);
5
node = node->next;
6
}
7
printf("\n");
8
}

销毁函数：

1
void destroyLinkLoopList(LinkLoopList* link_loop) {
2
LoopNode *node = link_loop->header.next;
3
while (node != &link_loop->header) {
4
LoopNode *tmp = node;
5
node = node->next;
6
free(tmp);
7
--link_loop->num;
8
}
9
printf("Table %d element!\n", link_loop->num);
10
}

最后，是测试函数：

1
void test01() {
2
LinkLoopList table;
3
initLinkLoopList(&table);
4

5
for (int i = 0; i < 10; ++i) {
6
insertLinkLoopRear(&table, i + 100);
7
}
8
showLinkLoopList(&table);
9
printf("======================\n");
10
deleteLinkLoopList(&table, 106);
11
showLinkLoopList(&table);
12

13
destroyLinkLoopList(&table);
14
}
15

16
/* 以下是几组约瑟夫环的测试答案，包括每个被杀者的顺序编号和最后的幸存者:
17
* 当n=5，k=2时，被杀者的顺序编号为2, 4, 1, 5，最后的幸存者是3。
18
* 当n=10，k=3时，被杀者的顺序编号为3, 6, 9, 2, 7, 1, 8, 5, 10，最后的幸存者是4。
19
* 当n=7，k=2时，被杀者的顺序编号为2, 4, 6, 1, 5, 3，最后的幸存者是7。
20
* 当n=10，k=17时，最后的幸存者是3
21
*/
22
void test_Joseph() {
23

24
}
25

26
int main() {
27
test01();
28

29
return 0;
30
}

————————完结撒花！！！——————希望对你有所帮助！

音乐

文章分享

评论区

音乐

音乐

文章目录