devbox
从前慢现在也慢
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

带头循环双向链表详解_带头双向链表

作者：从前慢现在也慢 | 2024-04-09 16:15:39

赞

踩

带头双向链表

目录

一、什么是带头循环双向链表？

1.特点：

2.优点：

二、实现接口

1.前置准备

1.1需要的三个文件

1.2结构体的创建和头文件的引用

2.接口实现

2.1函数创建新节点

2.2打印链表内容

 2.3尾插新节点

2.4头插新节点

 2.5头删节点

2.6尾删节点

 2.7查找节点

2.8在指定位置前插入节点

2.9删除指定位置节点.

2.10摧毁链表

 三、全部代码

1.接口头文件

2.接口实现

3.测试文件

一、什么是带头循环双向链表？

1.特点：

1.带头：有哨兵位节点，它不用存储数据。对链表进行插入删除操作时也不会影响改节点。

2.双向：组成链表的结构体中的结构体成员有数据，上一个节点的地址和下一个节点的地址

3.循环：链表的头结点存储了尾结点的地址，链表的尾结点存储了头节点的地址。

2.优点：

相比单向链表，双向循环链表的优点在于它的尾插找尾巴非常的快    因为它的头节点同时存储了上一个节点的地址，头的上一个即尾。相比无头链表，带头链表的好处在于当没有节点的时候，可以直接通过访问结构体成员的方式来增加相应的指针，而无头的话需要直接对地址进行修改，传变量的时候还需要传递二级指针   不仅不好理解，还易在实现的时候出错。

二、实现接口

1.前置准备

1.1需要的三个文件

先创建两个.c文件，再创建一个头文件，分别命名为test.c，list.c，list.h

test.c用来测试写好的接口                                   list.c存放实现接口的代码

list.h则存放对应函数，头文件，结构体的声明，这样在想使用链表的接口时，直接引用list.h即可，不需要引用别的头文件。 

创建好的环境如图

1.2结构体的创建和头文件的引用

这些内容放在list.h的文件中，到时引用就可以一条龙带走，不需要再引用别的内容

  1. #pragma once//防止头文件二次引用
  2. #include<stdio.h>
  3. #include<assert.h>
  4. #include<stdlib.h>
  5. typedef int LTDateType;
  6. //这样创建结构体数据类型，不仅是为了和int做区分
  7. //也是为了到时更好的替换，想换直接把int改了就行
  8. typedef struct listnode
  9. {
  10. 	struct listnode* prev;//存放上一个节点的地址
  11. 	struct listnode* next;//存放下一个节点的地址
  12. 	LTDateType data;//该节点存放的数据
  13. }listnode;

2.接口实现

2.1函数创建新节点

创建节点，虽然简单，但我们在很多操作中都会用到，因此把它单独分装成一个接口

  1. listnode* buy_listnode(LTDateType x)
  2. {
  3. 	listnode*newnode=(listnode*)malloc(sizeof(listnode));
  4. 	if (newnode == NULL)
  5. 	{
  6. 		perror("buy_listnode");//错误提示
  7. 		exit(-1);//节点都没创建出来，直接退出程序
  8. 	}
  9. 	newnode->data = x;//将新节点的数据初始化成我们需要的
  10. 	newnode->next = NULL;//不清楚插入的方式，先初始化成空
  11. 	newnode->prev = NULL;
  12. }

2.2打印链表内容

非常经典的操作，遍历一遍链表即可，唯一需要注意的便是，哨兵节点不是链表中真正的成员，它只能算是实现链表的辅助，因此跳过哨兵节点进行打印

  1. void print_list(listnode* phead)
  2. {
  3. 	assert(phead);//哨兵节点地址不可能为空
  4. 	listnode* head = phead->next;
  5. 	//哨兵位节点不存储有效数据，因此phead->next才是头节点
  6. 	printf("head<=>");//纯属美观
  7. 	while (head != phead)//当head和phead相等意味着已经遍历完一遍链表
  8. 	{
  9. 		printf("%d<=>", head->data);
  10. 		head = head->next;
  11. 	}
  12. 	printf("\n");
  13. }

 2.3尾插新节点

  1. void list_pushback(listnode*phead,LTDateType x)
  2. //尾插一个新节点，此节点存储x
  3. {
  4. 	listnode* newnode = buy_listnode(x);
  5. 	//创建一个我们需要的新节点
  6. 	listnode* tail = phead->prev;
  7. 	//先找尾，尾很显然是哨兵位节点的上一个节点
  8. 	tail->next = newnode;
  9. 	newnode->prev = tail;
  10. 	newnode->next = phead;
  11. 	phead->prev = newnode;
  12. }

后面的4行代码是核心，单独在文章中解释，创建了一个新节点，要把它放到链表的末端，尾节点我们已经找到了，接下来就是链接即可

首先明确，新的尾巴是创建出来的新节点，但还没进行链接之前，尾巴还是之前的尾巴

原始链表

第一步： 

第二步： 

 

第三步：

 第四步：

测试代码：

  1. #include"list.h"
  2. void test1()
  3. {
  4. 	listnode* plist=NULL;
  5. 	plist=init_listnode(plist);
  6. 	list_pushback(plist,1);
  7. 	list_pushback(plist,2);
  8. 	list_pushback(plist,3);
  9. 	list_pushback(plist,4);
  10. 	print_list(plist);
  11. }
  12. int main()
  13. {
  14. 	test1();
  15. }

 测试效果：

2.4头插新节点

这里我就不再画图了，自己画一遍比看别人画一万遍都来的快 

  1. void list_pushfront(listnode* phead, LTDateType x)
  2. {
  3. 	listnode* head = phead->next;//找到头节点
  4. 	listnode* newnode = buy_listnode(x);//创建新节点
  5. 	head->prev = newnode;
  6. 	newnode->next = head;
  7. 	phead->next = newnode;
  8. 	newnode->prev = phead;
  9. }

测试代码：

  1. void test2()
  2. {
  3. 	listnode* plist = NULL;
  4. 	plist = init_listnode(plist);
  5. 	list_pushfront(plist, 1);
  6. 	list_pushfront(plist, 2);
  7. 	print_list(plist);
  8. 	list_pushfront(plist, 10086);
  9. 	print_list(plist);
  10. }
  11. int main()
  12. {
  13. 	test2();
  14. }

测试效果： 

 2.5头删节点

需要注意的一点便是，我们删的节点不是哨兵节点，哨兵节点是不存放有效数据的，我们删除的是头节点

  1. void list_popfront(listnode*phead)
  2. {
  3. 	assert(phead);
  4. 	if (phead->next == phead)
  5. 	{
  6. 		printf("链表为空，操作失败\n");//为空就别删了
  7. 		return;
  8. 	}
  9. 	listnode* head = phead->next;//找到头节点
  10. 	phead->next = head->next;
  11. 	head->next->prev = phead;
  12. 	free(head);//链接完成，彻底删除
  13. }

测试代码：

  1. void test3()
  2. {
  3. 	listnode* plist = NULL;
  4. 	plist = init_listnode(plist);
  5. 	list_pushfront(plist, 1);
  6. 	list_pushfront(plist, 2);
  7. 	print_list(plist);
  8. 	list_pushfront(plist, 10086);
  9. 	print_list(plist);
  10. 	list_popfront(plist);
  11. 	print_list(plist);
  12. 	list_popfront(plist);
  13. 	print_list(plist);
  14. 	list_popfront(plist);
  15. 	print_list(plist);
  16. 	list_popfront(plist);
  17. 	print_list(plist);
  18. }
  19. int main()
  20. {
  21. 	test3();
  22. }

测试效果：

 

2.6尾删节点

没什么好说的，和之前的一样关键点在链接上，自己画了图什么都知道

  1. void list_popback(listnode*phead)
  2. {
  3. 	assert(phead);
  4. 	if (phead->next == phead)
  5. 	{
  6. 		printf("链表为空，操作失败\n");//为空就别删了
  7. 		return;
  8. 	}
  9. 	listnode* tail = phead->prev;//找到尾节点
  10. 	phead->prev = tail->prev;
  11. 	tail->prev->next = phead;
  12. 	free(tail);
  13. }

测试代码：

  1. void test4()
  2. {
  3. 	listnode* plist = NULL;
  4. 	plist = init_listnode(plist);
  5. 	list_pushfront(plist, 1);
  6. 	list_pushfront(plist, 2);
  7. 	list_pushfront(plist, 10086);
  8. 	print_list(plist);
  9. 	list_popback(plist);
  10. 	print_list(plist);
  11. 	list_popback(plist);
  12. 	print_list(plist);
  13. 	list_popback(plist);
  14. 	print_list(plist);
  15. 	list_popback(plist);
  16. 	print_list(plist);
  17. }
  18. int main()
  19. {
  20. 	test4();
  21. }

测试效果： 

 2.7查找节点

遍历一遍，找不到就返回NULL即可

  1. listnode* list_find(listnode* phead, LTDateType x)
  2. //哨兵节点和目标
  3. {
  4. 	assert(phead);
  5. 	listnode* head = phead->next;//找到头节点
  6. 	while (head!=phead)//相等意味着已经遍历完了
  7. 	{
  8. 		if (head->data == x)
  9. 		//找到目标，直接返回
  10. 		{
  11. 			return head;
  12. 		}
  13. 		head = head->next;
  14. 	}
  15. 	return NULL;//遍历完还找不到，返回空指针
  16. }

2.8在指定位置前插入节点

根据目标进行链接即可

  1. void list_insert(listnode*pos,LTDateType x)
  2. //目标位置，和在其前面插入数据为x的节点
  3. {
  4. 	if (pos == NULL)//传空意味着没找到目标
  5. 	{
  6. 		printf("目标不存在，操作失败\n");
  7. 		return;
  8. 	}
  9. 	listnode*newnode=buy_listnode(x);//创建新节点
  10. 	newnode->next = pos;
  11. 	newnode->prev= pos->prev;
  12. 	pos->prev->next = newnode;
  13. 	pos->prev = newnode;
  14. }

测试代码：

  1. void test5()
  2. {
  3. 	listnode* plist = NULL;
  4. 	plist = init_listnode(plist);
  5. 	list_pushfront(plist, 1);
  6. 	list_pushfront(plist, 2);
  7. 	list_pushfront(plist, 10086);
  8. 	print_list(plist);
  9. 	listnode*pos=list_find(plist,2);
  10. 	list_insert(pos, 888);//在2之前插入888
  11. 	print_list(plist);
  12. 	list_insert(plist->next, 666);
  13. 	//在头节点前插入666，与头插效用一致
  14. 	//可以在头插中复用这个函数
  15. 	print_list(plist);
  16. 	list_insert(plist, 520);
  17. 	//在哨兵节点前插入520，与尾插效用一致
  18. 	//可以在尾插中复用这个函数
  19. 	print_list(plist);
  20.  
  21.  
  22. }
  23. int main()
  24. {
  25. 	test5();
  26. }

测试效果：

2.9删除指定位置节点.

  1. void list_erase(listnode* pos)
  2. {
  3. 	assert(pos && pos->next != pos);
  4.     //pos为空意味着不存在，pos->next==pos意味着为哨兵节点
  5. 	pos->next->prev = pos->prev;
  6. 	pos->prev->next = pos->next;
  7. 	free(pos);
  8. }

测试代码：

  1. void test6()
  2. {
  3. 	listnode* plist = NULL;
  4. 	plist = init_listnode(plist);
  5. 	//list_erase(plist->prev);//尾删,测试报错
  6. 	list_pushfront(plist, 1);
  7. 	list_pushfront(plist, 2);
  8. 	list_pushfront(plist, 3);
  9. 	list_pushfront(plist, 4);
  10. 	list_pushfront(plist, 5);
  11. 	print_list(plist);
  12. 	listnode* pos = list_find(plist, 2);
  13. 	list_erase(pos);//把2删除
  14. 	print_list(plist);
  15. 	list_erase(plist->next);//头删
  16. 	print_list(plist);
  17. 	list_erase(plist->prev);//尾删
  18. 	print_list(plist);
  19. }
  20. int main()
  21. {
  22. 	test6();
  23. }

测试效果：

2.10摧毁链表

  1. void destory_list(listnode* phead)
  2. {
  3. 	listnode* tail = phead->prev;
  4. 	while (tail != phead)
  5. 	{
  6. 		listnode* tmp = tail;//存储尾
  7. 		tail = tail->prev;//从后往前遍历
  8. 		free(tmp);
  9. 		//不需要管什么链接了，直接摧毁就行
  10.  
  11. 	}
  12. 	free(phead);//单独摧毁
  13. }

 测试代码：
 

  1. void test7()
  2. {
  3. 	listnode* plist = NULL;
  4. 	plist = init_listnode(plist);
  5. 	//list_erase(plist->prev);//尾删,测试报错
  6. 	list_pushfront(plist, 1);
  7. 	list_pushfront(plist, 2);
  8. 	list_pushfront(plist, 3);
  9. 	list_pushfront(plist, 4);
  10. 	list_pushfront(plist, 5);
  11. 	destory_list(plist);
  12. }
  13. int main()
  14. {
  15. 	test7();
  16. }

测试效果：

从监视来看，确实全部释放

 三、全部代码

1.接口头文件

  1. #pragma once//防止头文件二次引用
  2. #include<stdio.h>
  3. #include<assert.h>
  4. #include<stdlib.h>
  5. typedef int LTDateType;
  6. //这样创建结构体数据类型，不仅是为了和int做区分
  7. //也是为了到时更好的替换，想换直接把int改了就行
  8. typedef struct listnode
  9. {
  10. 	struct listnode* prev;//存放上一个节点的地址
  11. 	struct listnode* next;//存放下一个节点的地址
  12. 	LTDateType data;//该节点存放的数据
  13. }listnode;
  14. listnode* buy_listnode(LTDateType x);
  15. listnode* init_listnode(listnode* phead);
  16. void print_list(listnode* phead);
  17. void list_pushback(listnode* phead, LTDateType x);
  18. void list_pushfront(listnode* phead, LTDateType x);
  19. void list_popfront(listnode* phead);
  20. void list_popback(listnode* phead);
  21. listnode* list_find(listnode* phead, LTDateType x);
  22. void list_insert(listnode* pos, LTDateType x);
  23. void list_erase(listnode* pos);
  24. void destory_list(listnode* phead);

2.接口实现

  1. #define _CRT_SECURE_NO_WARNINGS 1
  2. #include"list.h"
  3. listnode* buy_listnode(LTDateType x)
  4. {
  5. 	listnode*newnode=(listnode*)malloc(sizeof(listnode));
  6. 	if (newnode == NULL)
  7. 	{
  8. 		perror("buy_listnode");//错误提示
  9. 		exit(-1);//节点都没创建出来，直接退出程序
  10. 	}
  11. 	newnode->data = x;//将新节点的数据初始化成我们需要的
  12. 	newnode->next = NULL;//不清楚插入的方式，先初始化成空
  13. 	newnode->prev = NULL;
  14. }
  15. listnode* init_listnode(listnode* phead)
  16. {
  17. 	phead = buy_listnode(-1);	//-1是随便给的，初始化哨兵节点中的数据为-1,代表着没意义的数据
  18. 	phead->next = phead;//初始化哨兵节点，自己指向自己
  19. 	phead->prev = phead;
  20. 	return phead;
  21. }
  22. void print_list(listnode* phead)
  23. {
  24. 	assert(phead);//哨兵节点地址不可能为空
  25. 	listnode* head = phead->next;
  26. 	//哨兵位节点不存储有效数据，因此phead->next才是头节点
  27. 	printf("head<=>");//纯属美观
  28. 	while (head != phead)//当head和phead相等意味着已经遍历完一遍链表
  29. 	{
  30. 		printf("%d<=>", head->data);
  31. 		head = head->next;
  32. 	}
  33. 	printf("\n");
  34. }
  35. void list_pushback(listnode*phead,LTDateType x)
  36. //尾插一个新节点，此节点存储x
  37. {
  38. 	listnode* newnode = buy_listnode(x);
  39. 	//创建一个我们需要的新节点
  40. 	listnode* tail = phead->prev;
  41. 	//先找尾，尾很显然是哨兵位节点的上一个节点
  42. 	tail->next = newnode;
  43. 	newnode->prev = tail;
  44. 	newnode->next = phead;
  45. 	phead->prev = newnode;
  46. }
  47. void list_pushfront(listnode* phead, LTDateType x)
  48. {
  49. 	listnode* head = phead->next;//找到头节点
  50. 	listnode* newnode = buy_listnode(x);//创建新节点
  51. 	head->prev = newnode;
  52. 	newnode->next = head;
  53. 	phead->next = newnode;
  54. 	newnode->prev = phead;
  55. }
  56. void list_popfront(listnode*phead)
  57. {
  58. 	assert(phead);
  59. 	if (phead->next == phead)
  60. 	{
  61. 		printf("链表为空，操作失败\n");//为空就别删了
  62. 		return;
  63. 	}
  64. 	listnode* head = phead->next;//找到头节点
  65. 	phead->next = head->next;
  66. 	head->next->prev = phead;
  67. 	free(head);//链接完成，彻底删除
  68. }
  69. void list_popback(listnode*phead)
  70. {
  71. 	assert(phead);
  72. 	if (phead->next == phead)
  73. 	{
  74. 		printf("链表为空，操作失败\n");//为空就别删了
  75. 		return;
  76. 	}
  77. 	listnode* tail = phead->prev;//找到尾节点
  78. 	phead->prev = tail->prev;
  79. 	tail->prev->next = phead;
  80. 	free(tail);
  81. }
  82. listnode* list_find(listnode* phead, LTDateType x)
  83. //哨兵节点和目标
  84. {
  85. 	assert(phead);
  86. 	listnode* head = phead->next;//找到头节点
  87. 	while (head!=phead)//相等意味着已经遍历完了
  88. 	{
  89. 		if (head->data == x)
  90. 		//找到目标，直接返回
  91. 		{
  92. 			return head;
  93. 		}
  94. 		head = head->next;
  95. 	}
  96. 	return NULL;//遍历完还找不到，返回空指针
  97. }
  98. void list_insert(listnode*pos,LTDateType x)
  99. //目标位置，和在其前面插入数据为x的节点
  100. {
  101. 	if (pos == NULL)//传空意味着没找到目标
  102. 	{
  103. 		printf("目标不存在，操作失败\n");
  104. 		return;
  105. 	}
  106. 	listnode*newnode=buy_listnode(x);//创建新节点
  107. 	newnode->next = pos;
  108. 	newnode->prev= pos->prev;
  109. 	pos->prev->next = newnode;
  110. 	pos->prev = newnode;
  111. }
  112. void list_erase(listnode* pos)
  113. {
  114. 	assert(pos && pos->next != pos);
  115. 	pos->next->prev = pos->prev;
  116. 	pos->prev->next = pos->next;
  117. 	free(pos);
  118. }
  119. void destory_list(listnode* phead)
  120. {
  121. 	listnode* tail = phead->prev;
  122. 	while (tail != phead)
  123. 	{
  124. 		listnode* tmp = tail;//存储尾
  125. 		tail = tail->prev;//从后往前遍历
  126. 		free(tmp);
  127. 		//不需要管什么链接了，直接摧毁就行
  128.  
  129. 	}
  130. 	free(phead);//单独摧毁
  131. }

3.测试文件

  1. #define _CRT_SECURE_NO_WARNINGS 1
  2. #include"list.h"
  3. void test1()
  4. {
  5. 	listnode* plist=NULL;
  6. 	plist=init_listnode(plist);
  7. 	list_pushback(plist,1);
  8. 	list_pushback(plist,2);
  9. 	list_pushback(plist,3);
  10. 	list_pushback(plist,4);
  11. 	print_list(plist);
  12. }
  13. void test2()
  14. {
  15. 	listnode* plist = NULL;
  16. 	plist = init_listnode(plist);
  17. 	list_pushfront(plist, 1);
  18. 	list_pushfront(plist, 2);
  19. 	print_list(plist);
  20. 	list_pushfront(plist, 10086);
  21. 	print_list(plist);
  22. }
  23. void test3()
  24. {
  25. 	listnode* plist = NULL;
  26. 	plist = init_listnode(plist);
  27. 	list_pushfront(plist, 1);
  28. 	list_pushfront(plist, 2);
  29. 	print_list(plist);
  30. 	list_pushfront(plist, 10086);
  31. 	print_list(plist);
  32. 	list_popfront(plist);
  33. 	print_list(plist);
  34. 	list_popfront(plist);
  35. 	print_list(plist);
  36. 	list_popfront(plist);
  37. 	print_list(plist);
  38. 	list_popfront(plist);
  39. 	print_list(plist);
  40. }
  41. void test4()
  42. {
  43. 	listnode* plist = NULL;
  44. 	plist = init_listnode(plist);
  45. 	list_pushfront(plist, 1);
  46. 	list_pushfront(plist, 2);
  47. 	list_pushfront(plist, 10086);
  48. 	print_list(plist);
  49. 	list_popback(plist);
  50. 	print_list(plist);
  51. 	list_popback(plist);
  52. 	print_list(plist);
  53. 	list_popback(plist);
  54. 	print_list(plist);
  55. 	list_popback(plist);
  56. 	print_list(plist);
  57. }
  58. void test5()
  59. {
  60. 	listnode* plist = NULL;
  61. 	plist = init_listnode(plist);
  62. 	list_pushfront(plist, 1);
  63. 	list_pushfront(plist, 2);
  64. 	list_pushfront(plist, 10086);
  65. 	print_list(plist);
  66. 	listnode*pos=list_find(plist,2);
  67. 	list_insert(pos, 888);//在2之前插入888
  68. 	print_list(plist);
  69. 	list_insert(plist->next, 666);
  70. 	//在头节点前插入666，与头插效用一致
  71. 	//可以在头插中复用这个函数
  72. 	print_list(plist);
  73. 	list_insert(plist, 520);
  74. 	//在哨兵节点前插入520，与尾插效用一致
  75. 	//可以在尾插中复用这个函数
  76. 	print_list(plist);
  77. }
  78. void test6()
  79. {
  80. 	listnode* plist = NULL;
  81. 	plist = init_listnode(plist);
  82. 	//list_erase(plist->prev);//尾删,测试报错
  83. 	list_pushfront(plist, 1);
  84. 	list_pushfront(plist, 2);
  85. 	list_pushfront(plist, 3);
  86. 	list_pushfront(plist, 4);
  87. 	list_pushfront(plist, 5);
  88. 	print_list(plist);
  89. 	listnode* pos = list_find(plist, 2);
  90. 	list_erase(pos);//把2删除
  91. 	print_list(plist);
  92. 	list_erase(plist->next);//头删
  93. 	print_list(plist);
  94. 	list_erase(plist->prev);//尾删
  95. 	print_list(plist);
  96. }
  97. void test7()
  98. {
  99. 	listnode* plist = NULL;
  100. 	plist = init_listnode(plist);
  101. 	//list_erase(plist->prev);//尾删,测试报错
  102. 	list_pushfront(plist, 1);
  103. 	list_pushfront(plist, 2);
  104. 	list_pushfront(plist, 3);
  105. 	list_pushfront(plist, 4);
  106. 	list_pushfront(plist, 5);
  107. 	destory_list(plist);
  108. }
  109. int main()
  110. {
  111. 	test7();
  112. }

好了，今天的分享到这里就结束了，感谢各位友友来访，祝各位友友前程似锦O(∩_∩)O

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/从前慢现在也慢/article/detail/393884
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号