devbox
天景科技苑
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

【数据结构】带头双向循环链表的实现及链表顺序表的区别

作者：天景科技苑 | 2024-06-27 14:35:59

赞

踩

【数据结构】带头双向循环链表的实现及链表顺序表的区别

目录

一、带头双向循环链表接口实现

连接关系：

创建哨兵位（表头）：

头插——头删：

尾插——尾删：

查找——打印：

指定位置pos前插入，删除pos位置：

链表销毁：

二、快速实现“链表”

三、链表和顺序表的区别：

四、整体代码：

一、带头双向循环链表接口实现

连接关系：

实现这个链表最重要的就是理清楚连接关系：这里我给出两个动图，模拟这个关系

插入：

删除：

创建哨兵位（表头）：

这里我们可以用两种方法，一种是采取二级指针的方法，另一种是直接创建一个表头，然后把表头地址返回去，这里我们采用第二种：

  1. //创建新节点
  2. ListNode* CreateNewNode(LTDataType x)
  3. {
  4. 	ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
  5. 	if (newnode == NULL)
  6. 	{
  7. 		perror("malloc fail");
  8. 		exit(-1);
  9. 	}
  10. 	newnode->_data = x;
  11. 	newnode->_next = NULL;
  12. 	newnode->_prev = NULL;
  13. 	return newnode;
  14. }
  15. // 创建返回链表的头结点.
  16. ListNode* ListCreate()
  17. {
  18. 	ListNode* head = CreateNewNode(-1);
  19. 	head->_prev = head;
  20. 	head->_next = head;
  21. 	return head;
  22. }

头插——头删：

头插:

头插的时候，我们保存好链表第一个有效节点的地址，然后插入，记得把连接关系连接清楚

头删:

头删的时候，记得保存好，第二个节点的地址，记得把表头与第二节点的连接关系连接清楚

  1. // 双向链表头插
  2. void ListPushFront(ListNode* pHead, LTDataType x)
  3. {
  4. 	assert(pHead);
  5. 	ListNode* newnode = CreateNewNode(x);
  6. 	ListNode* second = pHead->_next;
  7. 	pHead->_next = newnode;
  8. 	newnode->_prev = pHead;
  9. 	newnode->_next = second;
  10. 	second->_prev = newnode;
  11. }
  12. // 双向链表头删
  13. void ListPopFront(ListNode* pHead)
  14. {
  15. 	assert(pHead);
  16. 	assert(pHead->_next != pHead);
  17. 	ListNode* first = pHead->_next;
  18. 	ListNode* second = first->_next;
  19. 	pHead->_next = second;
  20. 	second->_prev = pHead;
  21. 	free(first);
  22. 	first = NULL;
  23. }

尾插——尾删：

尾插：

保存好当前尾节点的地址，注意搞清楚头节点，尾节点，新节点的连接关系

尾删:

保存好最后两个节点的位置，注意连接清楚头节点和倒数第二个节点

  1. // 双向链表尾插
  2. void ListPushBack(ListNode* pHead, LTDataType x)
  3. {
  4. 	assert(pHead);
  5. 	ListNode* newnode= CreateNewNode(x);
  6. 	ListNode* tail = pHead->_prev;
  7. 	newnode->_next = pHead;
  8. 	newnode->_prev = tail;
  9. 	tail->_next = newnode;
  10. 	pHead->_prev = newnode;
  11. }
  12. // 双向链表尾删
  13. void ListPopBack(ListNode* pHead)
  14. {
  15. 	assert(pHead);
  16. 	assert(pHead->_next != pHead);
  17. 	ListNode* tail = pHead->_prev;
  18. 	ListNode* tailPrev = tail->_prev;
  19. 	pHead->_prev = tailPrev;
  20. 	tailPrev->_next = pHead;
  21. 	free(tail);
  22. 	tail = NULL;
  23. }

查找——打印：

注意：

循环从哨兵位的下一个节点开始，直到等于哨兵位结束

  1. // 双向链表查找
  2. ListNode* ListFind(ListNode* pHead, LTDataType x)
  3. {
  4. 	assert(pHead);
  5. 	ListNode* cur = pHead->_next;
  6. 	while (cur != pHead)
  7. 	{
  8. 		if (cur->_data == x)
  9. 			return cur;
  10. 		cur = cur->_next;
  11. 	}
  12. 	return NULL;
  13. }
  14. // 双向链表打印
  15. void ListPrint(ListNode* pHead)
  16. {
  17. 	assert(pHead);
  18. 	ListNode* cur = pHead->_next;
  19. 	while (cur!=pHead)
  20. 	{
  21. 		printf("%d <-> ", cur->_data);
  22. 		cur = cur->_next;
  23. 	}
  24. 	printf("NULL\n");
  25. }

指定位置pos前插入，删除pos位置：

pos前插入： 

保存好pos前一个位置的地址，连接清楚就行了

删除pos位置：

保存好pos前后的位置，连接清楚就行了

  1. // 双向链表在pos的前面进行插入
  2. void ListInsert(ListNode* pos, LTDataType x)
  3. {
  4. 	assert(pos);
  5. 	ListNode* newnode = CreateNewNode(x);
  6. 	ListNode* prev = pos->_prev;
  7. 	prev->_next = newnode;
  8. 	newnode->_prev = prev;
  9. 	newnode->_next = pos;
  10. 	pos->_prev = newnode;
  11. }
  12. // 双向链表删除pos位置的节点
  13. void ListErase(ListNode* pos)
  14. {
  15. 	assert(pos);
  16. 	ListNode* prev = pos->_prev;
  17. 	ListNode* next = pos->_next;
  18. 	prev->_next = next;
  19. 	next->_prev = prev;
  20. 	free(pos);
  21. 	pos = NULL;
  22. }

链表销毁：

这一个要从哨兵位的下一个节点开始，循环直到不等于哨兵位结束：

  1. // 双向链表销毁
  2. void ListDestory(ListNode* pHead)
  3. {
  4. 	assert(pHead);
  5. 	ListNode* cur = pHead->_next;
  6. 	while (cur != pHead)
  7. 	{
  8. 		ListNode* next = cur->_next;
  9. 		free(cur);
  10. 		cur = next;
  11. 	}
  12. 	free(pHead);
  13. }

二、快速实现“链表”

学了带头双向循环链表之后，我们可以快速实现一个简单链表：

大多数接口其实都是不变的，但是有4个接口可以简化，那就是头插——头删——尾插——尾删；

这两个接口可以复用insert接口和erase接口：这四个接口连接关系是比较麻烦的，省去了这几个麻烦的，其他的接口就会很快写出来，大大节省了时间：

  1. // 双向链表尾插
  2. void ListPushBack(ListNode* pHead, LTDataType x)
  3. {
  4. 	assert(pHead);
  5. 	//ListNode* newnode= CreateNewNode(x);
  6. 	//ListNode* tail = pHead->_prev;
  7. 	//newnode->_next = pHead;
  8. 	//newnode->_prev = tail;
  9. 	//tail->_next = newnode;
  10. 	//pHead->_prev = newnode;
  11.  
  12. 	ListInsert(pHead,x);
  13. }
  14. // 双向链表尾删
  15. void ListPopBack(ListNode* pHead)
  16. {
  17. 	assert(pHead);
  18. 	//assert(pHead->_next != pHead);
  19. 	//ListNode* tail = pHead->_prev;
  20. 	//ListNode* tailPrev = tail->_prev;
  21. 	//pHead->_prev = tailPrev;
  22. 	//tailPrev->_next = pHead;
  23. 	//free(tail);
  24. 	//tail = NULL;
  25.  
  26. 	ListErase(pHead->_prev);
  27. }
  28. // 双向链表头插
  29. void ListPushFront(ListNode* pHead, LTDataType x)
  30. {
  31. 	assert(pHead);
  32. 	//ListNode* newnode = CreateNewNode(x);
  33. 	//ListNode* second = pHead->_next;
  34. 	//pHead->_next = newnode;
  35. 	//newnode->_prev = pHead;
  36. 	//newnode->_next = second;
  37. 	//second->_prev = newnode;
  38.  
  39. 	ListInsert(pHead->_next, x);
  40. }
  41. // 双向链表头删
  42. void ListPopFront(ListNode* pHead)
  43. {
  44. 	assert(pHead);
  45. 	//assert(pHead->_next != pHead);
  46. 	//ListNode* first = pHead->_next;
  47. 	//ListNode* second = first->_next;
  48. 	//pHead->_next = second;
  49. 	//second->_prev = pHead;
  50. 	//free(first);
  51. 	//first = NULL;
  52.  
  53. 	ListErase(pHead->_next);
  54. }

三、链表和顺序表的区别：

顺序表空间连续支持下标访问使得我们在排序，访问等很多场景下都是很高效的

链表的合理利用空间使我们对空间的管理更合理

四、整体代码：

SList.h

  1. #pragma once
  2. #include<stdio.h>
  3. #include<stdlib.h>
  4. #include<assert.h>
  5.  
  6. // 带头+双向+循环链表增删查改实现
  7. typedef int LTDataType;
  8. typedef struct ListNode
  9. {
  10. 	LTDataType _data;
  11. 	struct ListNode* _next;
  12. 	struct ListNode* _prev;
  13. }ListNode;
  14.  
  15. // 创建返回链表的头结点.
  16. ListNode* ListCreate();
  17. // 双向链表销毁
  18. void ListDestory(ListNode* pHead);
  19. // 双向链表打印
  20. void ListPrint(ListNode* pHead);
  21. // 双向链表尾插
  22. void ListPushBack(ListNode* pHead, LTDataType x);
  23. // 双向链表尾删
  24. void ListPopBack(ListNode* pHead);
  25. // 双向链表头插
  26. void ListPushFront(ListNode* pHead, LTDataType x);
  27. // 双向链表头删
  28. void ListPopFront(ListNode* pHead);
  29. // 双向链表查找
  30. ListNode* ListFind(ListNode* pHead, LTDataType x);
  31. // 双向链表在pos的前面进行插入
  32. void ListInsert(ListNode* pos, LTDataType x);
  33. // 双向链表删除pos位置的节点
  34. void ListErase(ListNode* pos);
  35.

SList.c

  1. #define _CRT_SECURE_NO_WARNINGS 1
  2. #include"List.h"
  3.  
  4. //创建新节点
  5. ListNode* CreateNewNode(LTDataType x)
  6. {
  7. 	ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
  8. 	if (newnode == NULL)
  9. 	{
  10. 		perror("malloc fail");
  11. 		exit(-1);
  12. 	}
  13. 	newnode->_data = x;
  14. 	newnode->_next = NULL;
  15. 	newnode->_prev = NULL;
  16. 	return newnode;
  17. }
  18. // 创建返回链表的头结点.
  19. ListNode* ListCreate()
  20. {
  21. 	ListNode* head = CreateNewNode(-1);
  22. 	head->_prev = head;
  23. 	head->_next = head;
  24. 	return head;
  25. }
  26. // 双向链表销毁
  27. void ListDestory(ListNode* pHead)
  28. {
  29. 	assert(pHead);
  30. 	ListNode* cur = pHead->_next;
  31. 	while (cur != pHead)
  32. 	{
  33. 		ListNode* next = cur->_next;
  34. 		free(cur);
  35. 		cur = next;
  36. 	}
  37. 	free(pHead);
  38. }
  39. // 双向链表打印
  40. void ListPrint(ListNode* pHead)
  41. {
  42. 	assert(pHead);
  43. 	ListNode* cur = pHead->_next;
  44. 	while (cur!=pHead)
  45. 	{
  46. 		printf("%d <-> ", cur->_data);
  47. 		cur = cur->_next;
  48. 	}
  49. 	printf("NULL\n");
  50. }
  51. // 双向链表尾插
  52. void ListPushBack(ListNode* pHead, LTDataType x)
  53. {
  54. 	assert(pHead);
  55. 	//ListNode* newnode= CreateNewNode(x);
  56. 	//ListNode* tail = pHead->_prev;
  57. 	//newnode->_next = pHead;
  58. 	//newnode->_prev = tail;
  59. 	//tail->_next = newnode;
  60. 	//pHead->_prev = newnode;
  61.  
  62. 	ListInsert(pHead,x);
  63. }
  64. // 双向链表尾删
  65. void ListPopBack(ListNode* pHead)
  66. {
  67. 	assert(pHead);
  68. 	//assert(pHead->_next != pHead);
  69. 	//ListNode* tail = pHead->_prev;
  70. 	//ListNode* tailPrev = tail->_prev;
  71. 	//pHead->_prev = tailPrev;
  72. 	//tailPrev->_next = pHead;
  73. 	//free(tail);
  74. 	//tail = NULL;
  75.  
  76. 	ListErase(pHead->_prev);
  77. }
  78. // 双向链表头插
  79. void ListPushFront(ListNode* pHead, LTDataType x)
  80. {
  81. 	assert(pHead);
  82. 	//ListNode* newnode = CreateNewNode(x);
  83. 	//ListNode* second = pHead->_next;
  84. 	//pHead->_next = newnode;
  85. 	//newnode->_prev = pHead;
  86. 	//newnode->_next = second;
  87. 	//second->_prev = newnode;
  88.  
  89. 	ListInsert(pHead->_next, x);
  90. }
  91. // 双向链表头删
  92. void ListPopFront(ListNode* pHead)
  93. {
  94. 	assert(pHead);
  95. 	//assert(pHead->_next != pHead);
  96. 	//ListNode* first = pHead->_next;
  97. 	//ListNode* second = first->_next;
  98. 	//pHead->_next = second;
  99. 	//second->_prev = pHead;
  100. 	//free(first);
  101. 	//first = NULL;
  102.  
  103. 	ListErase(pHead->_next);
  104. }
  105. // 双向链表查找
  106. ListNode* ListFind(ListNode* pHead, LTDataType x)
  107. {
  108. 	assert(pHead);
  109. 	ListNode* cur = pHead->_next;
  110. 	while (cur != pHead)
  111. 	{
  112. 		if (cur->_data == x)
  113. 			return cur;
  114. 		cur = cur->_next;
  115. 	}
  116. 	return NULL;
  117. }
  118. // 双向链表在pos的前面进行插入
  119. void ListInsert(ListNode* pos, LTDataType x)
  120. {
  121. 	assert(pos);
  122. 	ListNode* newnode = CreateNewNode(x);
  123. 	ListNode* prev = pos->_prev;
  124. 	prev->_next = newnode;
  125. 	newnode->_prev = prev;
  126. 	newnode->_next = pos;
  127. 	pos->_prev = newnode;
  128. }
  129. // 双向链表删除pos位置的节点
  130. void ListErase(ListNode* pos)
  131. {
  132. 	assert(pos);
  133. 	ListNode* prev = pos->_prev;
  134. 	ListNode* next = pos->_next;
  135. 	prev->_next = next;
  136. 	next->_prev = prev;
  137. 	free(pos);
  138. 	pos = NULL;
  139. }

Test.c

  1. #define _CRT_SECURE_NO_WARNINGS 1
  2. #include"List.h"
  3. void test()
  4. {
  5. 	ListNode* plist = ListCreate();
  6.  
  7. 	ListPushBack(plist,1);
  8. 	ListPushBack(plist,2);
  9. 	ListPushBack(plist,3);
  10. 	ListPushBack(plist,4);
  11. 	ListPushBack(plist,5);
  12.  
  13. 	ListPrint(plist);
  14.  
  15. 	ListPopBack(plist);
  16. 	ListPopBack(plist);
  17. 	ListPopBack(plist);
  18.  
  19. 	ListPrint(plist);
  20.  
  21. 	ListPushFront(plist,6);
  22. 	ListPushFront(plist,7);
  23. 	ListPushFront(plist,8);
  24. 	ListPushFront(plist,9);
  25. 	ListPushFront(plist,10);
  26.  
  27. 	ListPrint(plist);
  28.  
  29. 	ListPopFront(plist);
  30. 	ListPopFront(plist);
  31. 	ListPopFront(plist);
  32.  
  33. 	ListPrint(plist);
  34.  
  35. 	printf("%d\n", ListFind(plist, 6)->_data);
  36.  
  37. 	ListPrint(plist);
  38.  
  39. 	ListInsert(ListFind(plist,6), 99);
  40. 	ListInsert(ListFind(plist,7), 88);
  41.  
  42. 	ListPrint(plist);
  43.  
  44. 	ListErase(ListFind(plist, 99));
  45. 	ListErase(ListFind(plist, 88));
  46.  
  47. 	ListPrint(plist);
  48.  
  49.  
  50. 	ListDestory(plist);
  51. 	plist = NULL;
  52. }
  53. int main()
  54. {
  55. 	test();
  56.  
  57. 	return 0;
  58. }

本文内容由网友自发贡献，转载请注明出处：https://www.wpsshop.cn/w/天景科技苑/article/detail/762818
推荐阅读
相关标签

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

  

闽ICP备14008679号