• 【面试官让我十分钟实现一个链表？一个双向带头循环链表甩给面试官】

    我们在面试中面试官一般都会让我们现场写代码，如果你面试的时候面试官让你十分钟写一个链表，你是不是懵逼了？十分钟写一个链表，怎么可能？事实上是有可能的，十分钟写出的链表也能震惊面试官。

    我们学习单链表其实是为了后面学习更高级的数据结构，因为单链表一般不会用来存储数据，只是用来作为更高级数据结构的子结构，如哈希桶、图的邻接表等。单链表看似简单，其实一点也不简单，在进行增删改查操作的时候需要注意很多问题。

    在实际中，我们一般使用双向带头循环链表存储数据，因为在链表结构中，双向带头循环链表可以说是链表当中最优的结构了。双向带头循环链表，名字听起来很高大上，看起来很难的样子，其实不是的，它就是一个纸老虎，看起来难，其实它的实现很容易。

     双向带头循环链表有一个数据域和两个指针域，第一个指针域指向直接后继，第二个指针域指向直接前驱。表中最后一个节点的第二个指针域指向头节点，头节点的第一个指针域指向最后一个节点，整个链表形成一个环。

    双向带头循环链表的结构

    1. typedef int DListDataType;
    2. typedef struct DListNode
    3. {
    4. 	DListDataType* data;
    5. 	struct DListNode* prev;
    6. 	struct DListNode* next;
    7. }DListNode;

    链表节点的创建

    1. DListNode* BuyListNode(DListDataType x)
    2. {
    3. 	DListNode* node = (DListNode*)malloc(sizeof(DListNode));
    4. 	if (node == NULL)
    5. 	{
    6. 		perror("malloc fail");
    7. 		exit(-1);
    8. 	}
    9. 	node->data = x;
    10. 	node->prev = NULL;
    11. 	node->next = NULL;
    12. 	return node;
    13. }

    链表的初始化

     创建一个头节点，让头节点的两个指针域都分别指向自己。

    1. DListNode* LTInit()
    2. {
    3. 	DListNode* phead = BuyListNode(-1);//头节点的data可以为任意值
    4. 	phead->next = phead;
    5. 	phead->prev = phead;
    6. 	return phead;
    7. }

    链表的打印

    1. void LTPrint(DListNode* phead)
    2. {
    3. 	assert(phead);
    4.  
    5. 	DListNode* cur = phead->next;
    6. 	while (cur != phead)
    7. 	{
    8. 		printf("%d ", cur->data);
    9. 		cur = cur->next;
    10. 	}
    11. 	printf("\n");
    12. }

     链表的尾插

     

    1. void LTPushBack(DListNode* phead, DListDataType x)
    2. {
    3. 	assert(phead);
    4. 	DListNode* newnode = BuyListNode(x);
    5. 	DListNode* tail = phead->prev;//保存尾节点（头节点的prev）
    6.  
    7. 	tail->next = newnode;
    8. 	newnode->prev = tail;
    9.  
    10. 	newnode->prev = phead;
    11. 	phead->prev = newnode;
    12. 	
    13. }

     链表的尾删

    1. void LTPopBack(DListNode* phead)
    2. {
    3. 	assert(phead);
    4. 	assert(phead->next != phead);  // 判断是否为空
    5.  
    6. 	DListNode* tail = phead->prev;
    7.  
    8. 	tail->prev->next = phead;
    9. 	phead->prev = tail;
    10. 	free(tail);
    11. }

     链表的头插

    1. void LTPushFront(DListNode* phead, DListDataType x)
    2. {
    3. 	assert(phead);
    4. 	DListNode* newnode = BuyListNode(x);
    5. 	newnode->next = phead->next;
    6. 	phead->next->prev = newnode;
    7.  
    8. 	phead->next = newnode;
    9. 	newnode->prev = phead;
    10. 	
    11. }

    链表的头删

    1. void LTPopFront(DListNode* phead)
    2. {
    3. 	assert(phead);
    4. 	assert(phead->next != phead);  // 判断是否为空
    5.  
    6. 	DListNode* pheadnext = phead->next;
    7.  
    8. 	phead->next = pheadnext->next;
    9. 	pheadnext->next->prev = phead;
    10. 	free(pheadnext);
    11. }

    在链表中插入节点

     

    1. // pos位置之前插入
    2. void LTInsert(DListNode* pos, DListDataType x)
    3. {
    4. 	assert(pos);
    5. 	DListNode* prevpos = pos->prev;
    6. 	DListNode* newnode = BuyListNode(x);
    7. 	// prev newnode pos
    8. 	prevpos->next = newnode;
    9. 	newnode->prev = prevpos;
    10. 	newnode->next = pos;
    11. 	pos->prev = newnode;
    12. }

    删除链表中的节点

    1. // 删除pos位置
    2. void LTErase(DListNode* pos)
    3. {
    4. 	assert(pos);
    5. 	DListNode* prevpos = pos->prev;
    6. 	DListNode* nextpos = pos->next;
    7.  
    8. 	free(pos);
    9. 	prevpos->next = nextpos;
    10. 	nextpos->prev = prevpos;
    11.  
    12. }

     判断链表是否为空

    1. bool LTEmpty(DListNode* phead)
    2. {
    3. 	assert(phead);
    4.  
    5. 	/*if (phead->next == phead)
    6. 	{
    7. 		return true;
    8. 	}
    9. 	else
    10. 	{
    11. 		return false;
    12. 	}*/
    13.  
    14. 	return phead->next == phead;
    15. }

    计算链表的节点

    1. size_t LTSize(DListNode* phead)
    2. {
    3. 	assert(phead);
    4.  
    5. 	size_t size = 0;
    6. 	DListNode* cur = phead->next;
    7. 	while (cur != phead)
    8. 	{
    9. 		++size;
    10. 		cur = cur->next;
    11. 	}
    12.  
    13. 	return size;
    14. }

     销毁链表

    1. void LTDestroy(DListNode* phead)
    2. {
    3. 	assert(phead);
    4.  
    5. 	DListNode* cur = phead->next;
    6. 	while (cur != phead)
    7. 	{
    8. 		DListNode* next = cur->next;
    9. 		free(cur);
    10.  
    11. 		cur = next;
    12. 	}
    13. 	free(phead);
    14. }

    以上就是带头双向链表的基本操作，如果想在十分钟之内写出这个链表，只需要在头插，尾插复用

     LTInsert（），头删，尾删复用 LTErase（），这样你只需要写出LTInsert（）和 LTErase（）就等于将头插，尾插、头删，尾删写出来了。

    完整代码：

    DList.h  接口函数

    1. #include 
    2. #include 
    3.  
    4. typedef int DListDataType;
    5. typedef struct DListNode
    6. {
    7. 	DListDataType* data;
    8. 	struct DListNode* prev;
    9. 	struct DListNode* next;
    10. }DListNode;
    11.  
    12. DListNode* BuyListNode(DListDataType x);
    13. void LTPrint(DListNode* phead);
    14. DListNode* LTInit();
    15. void LTPushBack(DListNode* phead, DListDataType x);
    16. void LTPopBack(DListNode* phead);
    17.  
    18. void LTPushFront(DListNode* phead, DListDataType x);
    19. void LTPopFront(DListNode* phead);
    20. DListNode* LTFind(DListNode* phead, DListDataType x);
    21.  
    22. // pos位置之前插入
    23. void LTInsert(DListNode* pos, DListDataType x);
    24. // pos位置之后插入
    25. void LTErase(DListNode* pos);
    26.  
    27. bool LTEmpty(DListNode* phead);
    28. size_t LTSize(DListNode* phead);
    29. void LTDestroy(DListNode* phead);

    DList.c  函数的实现

    1. #include "DList.h"
    2.  
    3. DListNode* BuyListNode(DListDataType x)
    4. {
    5. 	DListNode* node = (DListNode*)malloc(sizeof(DListNode));
    6. 	if (node == NULL)
    7. 	{
    8. 		perror("malloc fail");
    9. 		exit(-1);
    10. 	}
    11. 	node->data = x;
    12. 	node->prev = NULL;
    13. 	node->next = NULL;
    14. 	return node;
    15. }
    16. DListNode* LTInit()
    17. {
    18. 	DListNode* phead = BuyListNode(-1);//头节点的data可以为任意值
    19. 	phead->next = phead;
    20. 	phead->prev = phead;
    21. 	return phead;
    22. }
    23. void LTPrint(DListNode* phead)
    24. {
    25. 	assert(phead);
    26.  
    27. 	DListNode* cur = phead->next;
    28. 	while (cur != phead)
    29. 	{
    30. 		printf("%d ", cur->data);
    31. 		cur = cur->next;
    32. 	}
    33. 	printf("\n");
    34. }
    35. void LTPushBack(DListNode* phead, DListDataType x)
    36. {
    37. 	assert(phead);
    38. 	//DListNode* newnode = BuyListNode(x);
    39. 	//DListNode* tail = phead->prev;//保存尾节点（头节点的prev）
    40.  
    41. 	//tail->next = newnode;
    42. 	//newnode->prev = tail;
    43.  
    44. 	//newnode->prev = phead;
    45. 	//phead->prev = newnode;
    46.  
    47. 	LTInsert(phead, x);
    48. 	
    49. }
    50. void LTPopBack(DListNode* phead)
    51. {
    52. 	assert(phead);
    53. 	//assert(phead->next != phead);  // 判断是否为空
    54.  
    55. 	//DListNode* tail = phead->prev;
    56.  
    57. 	//tail->prev->next = phead;
    58. 	//phead->prev = tail;
    59. 	//free(tail);
    60.  
    61. 	LTErase(phead->prev);
    62. }
    63.  
    64. void LTPushFront(DListNode* phead, DListDataType x)
    65. {
    66. 	assert(phead);
    67. 	/*DListNode* newnode = BuyListNode(x);
    68. 	newnode->next = phead->next;
    69. 	phead->next->prev = newnode;
    71. 	phead->next = newnode;
    72. 	newnode->prev = phead;*/
    73. 	
    74. 	LTInsert(phead->next, x);
    75.  
    76. }
    77. void LTPopFront(DListNode* phead)
    78. {
    79. 	assert(phead);
    80. 	//assert(phead->next != phead);  // 判断是否为空
    81.  
    82. 	//DListNode* pheadnext = phead->next;
    83.  
    84. 	//phead->next = pheadnext->next;
    85. 	//pheadnext->next->prev = phead;
    86. 	//free(pheadnext);
    87. 	LTErase(phead->next);
    88. }
    89. DListNode* LTFind(DListNode* phead, DListDataType x)
    90. {
    91. 	assert(phead);
    92. 	DListNode* cur = phead->next;
    93. 	while (cur != phead)
    94. 	{
    95. 		if (cur->data == x)
    96. 		{
    97. 			return cur;
    98. 		}
    99. 		cur = cur->next;
    100. 	}
    101. 	return NULL;
    102. }
    103.  
    104. // pos位置之前插入
    105. void LTInsert(DListNode* pos, DListDataType x)
    106. {
    107. 	assert(pos);
    108. 	DListNode* prevpos = pos->prev;
    109. 	DListNode* newnode = BuyListNode(x);
    110. 	// prev newnode pos
    111. 	prevpos->next = newnode;
    112. 	newnode->prev = prevpos;
    113. 	newnode->next = pos;
    114. 	pos->prev = newnode;
    115. }
    116. // 删除pos位置
    117. void LTErase(DListNode* pos)
    118. {
    119. 	assert(pos);
    120. 	DListNode* prevpos = pos->prev;
    121. 	DListNode* nextpos = pos->next;
    122.  
    123. 	free(pos);
    124. 	prevpos->next = nextpos;
    125. 	nextpos->prev = prevpos;
    126.  
    127. }
    128.  
    129. bool LTEmpty(DListNode* phead)
    130. {
    131. 	assert(phead);
    132.  
    133. 	/*if (phead->next == phead)
    134. 	{
    135. 		return true;
    136. 	}
    137. 	else
    138. 	{
    139. 		return false;
    140. 	}*/
    141.  
    142. 	return phead->next == phead;
    143. }
    144. size_t LTSize(DListNode* phead)
    145. {
    146. 	assert(phead);
    147.  
    148. 	size_t size = 0;
    149. 	DListNode* cur = phead->next;
    150. 	while (cur != phead)
    151. 	{
    152. 		++size;
    153. 		cur = cur->next;
    154. 	}
    155.  
    156. 	return size;
    157. }
    158. void LTDestroy(DListNode* phead)
    159. {
    160. 	assert(phead);
    161.  
    162. 	DListNode* cur = phead->next;
    163. 	while (cur != phead)
    164. 	{
    165. 		DListNode* next = cur->next;
    166. 		free(cur);
    167.  
    168. 		cur = next;
    169. 	}
    170. 	free(phead);
    171. }

    Test.c   测试函数

    1. #include "DList.h"
    2.  
    3. void TestList1()
    4. {
    5. 	DListNode* phead = LTInit();
    6. 	LTPushBack(phead, 1);
    7. 	LTPushBack(phead, 2);
    8. 	LTPushBack(phead, 3);
    9. 	LTPushBack(phead, 4);
    10. 	LTPushBack(phead, 5);
    11. 	LTPrint(phead);
    12.  
    13. 	LTPopBack(phead);
    14. 	LTPrint(phead);
    15. 	LTPopBack(phead);
    16. 	LTPrint(phead);
    17. 	LTPopBack(phead);
    18. 	LTPrint(phead);
    19. 	LTPopBack(phead);
    20. 	LTPrint(phead);
    21. 	LTPopBack(phead);
    22. 	LTPrint(phead);
    23.  
    24. 	//LTPopBack(phead);
    25. }
    26.  
    27. void TestList2()
    28. {
    29. 	DListNode* phead = LTInit();
    30. 	LTPushFront(phead, 1);
    31. 	LTPushFront(phead, 2);
    32. 	LTPushFront(phead, 3);
    33. 	LTPushFront(phead, 4);
    34. 	LTPushFront(phead, 5);
    35. 	LTPrint(phead);
    36.  
    37. 	LTPopFront(phead);
    38. 	LTPrint(phead);
    39. 	LTPopFront(phead);
    40. 	LTPrint(phead);
    41. 	LTPopFront(phead);
    42. 	LTPrint(phead);
    43. 	LTPopFront(phead);
    44. 	LTPrint(phead);
    45. 	LTPopFront(phead);
    46. 	LTPrint(phead);
    47. }
    48.  
    49. void TestList3()
    50. {
    51. 	DListNode* phead = LTInit();
    52. 	LTPushFront(phead, 1);
    53. 	LTPushFront(phead, 2);
    54. 	LTPushFront(phead, 3);
    55. 	LTPushFront(phead, 4);
    56. 	LTPushFront(phead, 5);
    57. 	LTPrint(phead);
    58.  
    59. 	DListNode* pos = LTFind(phead, 3);
    60. 	LTPrint(phead);
    61.  
    62. 	LTDestroy(phead);
    63. 	phead = NULL;
    64. }
    65.  
    66. int main()
    67. {
    68. 	
    69. 	TestList1();
    70. 	//TestList2();
    71. 	//TestList3();
    72. 	return 0;
    73. }

     

     

  • 相关阅读:
    5个基于.Net Core值得推荐的CMS开源项目
    Activiti兼容达梦数据库
    Spring学习笔记4 Bean的作用域
    Angualr-Library笔记
    Qt扫盲-QFontInfo理论
    {“Code“:“InvalidParameterValue.TemplateParameterFormatError“
    Java学习----前端4
    C++编程语言的深度解析: 从零开始的学习路线
    UE4 设计模式：单例模式(Singleton Pattern)
    服务器——SSL/TLS协议信息泄露漏洞(CVE-2016-2183)修复办法
  • 原文地址：https://blog.csdn.net/m0_55752775/article/details/127797691