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

数据结构——队列_链队列判断只有一个元素

作者：小蓝xlanll | 2024-05-30 09:43:18

赞

踩

链队列判断只有一个元素

一、定义

队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出的特性。

队尾：进行插入操作的一端。

队头：进行删除操作的一端。

二、结构体定义

  1. // 链式结构：表示队列 
  2. typedef int QDataType;
  3. typedef struct QListNode
  4. {
  5. 	struct QListNode* next;
  6. 	QDataType data;
  7. }QNode;
  8.  
  9. // 队列的结构 
  10. typedef struct Queue
  11. {
  12. 	QNode* front;//队头
  13. 	QNode* rear;//队尾
  14. }Queue;

若采用顺序表的方式实现队列，随着出队入队的操作，队头指针和队尾指针的移动，队头前的空间就可能发生内存泄漏，或出现假溢出问题。对此有两种解决方法，一种是采用链表的方式实现队列，一种是采用循环队列，这里采用的是链表的方式实现队列，随后会发布循环队列的实现方法。

三、接口实现

  1. void Queue_Tese();//队列功能测试函数
  2. QNode* buyQNode(QDataType data);//带头结点的单链表
  3. void QueueInit(Queue* q);// 初始化队列 
  4. void QueuePush(Queue* q, QDataType data);// 队尾入队列 
  5. void QueuePop(Queue* q);// 队头出队列 
  6. QDataType QueueFront(Queue* q);// 获取队列头部元素 
  7. QDataType QueueBack(Queue* q);// 获取队列队尾元素 
  8. int QueueSize(Queue* q);// 获取队列中有效元素个数 
  9. int QueueEmpty(Queue* q);// 检测队列是否为空，为空返回1，非空返回0 
  10. void QueueDestroy(Queue* q);// 销毁队列

1.创建带头结点的单链表

  1. QNode* buyQNode(QDataType data) {//带头结点的单链表
  2. 	QNode* newNode = (QNode*)malloc(sizeof(QNode));
  3. 	if (newNode == NULL) {
  4. 		assert(0);
  5. 		return NULL;
  6. 	}
  7. 	newNode->data = data;
  8. 	newNode->next = NULL;
  9. 	return newNode;
  10. }

使用带头结点的单链表实现队列，可以简化实现过程的很多操作。

2.初始化队列

  1. void QueueInit(Queue* q) {// 初始化队列
  2. 	assert(q);
  3. 	q->front = buyQNode(0);
  4. 	q->rear = q->front;
  5. }

将队列头尾指针都指向头结点即可。

3.入队

  1. void QueuePush(Queue* q, QDataType data) {// 队尾入队列 
  2. 	assert(q);
  3. 	QNode* newNode = buyQNode(data);
  4. 	q->rear->next = newNode;
  5. 	q->rear = newNode;
  6. }

只能在队尾入队。

4.判空

  1. int QueueEmpty(Queue* q) {// 检测队列是否为空，为空返回1，非空返回0 
  2. 	assert(q);
  3. 	return q->front == q->rear;
  4. }

队头队尾指针都在初始位置指向头结点，即队列为空，若用顺序表实现则是队头队尾都在0号位置即队列为空。

5.出队

  1. void QueuePop(Queue* q){// 队头出队列 
  2. 	assert(q);
  3. 	if (QueueEmpty(q)) {//判空
  4. 		return;
  5. 	}
  6. 	QNode* delNode = q->front->next;
  7. 	q->front->next = delNode->next;
  8. 	if (delNode == q->rear) {//若队列只有一个元素，出队列后要将队尾放到头结点处
  9. 		q->rear = q->front;
  10. 	}
  11. 	free(delNode);
  12. }

出队列只能在队头出队。因为这里采用的是带头结点的单链表实现队列，所以在队列只有一个元素时出队列，需要把队尾指针放回到头节处。

6.获取队头

  1. QDataType QueueFront(Queue* q) {// 获取队列头部元素 
  2. 	assert(q);
  3. 	return q->front->next->data;
  4. }

7.获取队尾

  1. QDataType QueueBack(Queue* q) {// 获取队列队尾元素
  2. 	assert(q);
  3. 	return q->rear->data;
  4. }

8.获取队列中有效元素个数

  1. int QueueSize(Queue* q) {// 获取队列中有效元素个数 
  2. 	assert(q);
  3. 	QNode* cur = q->front->next;
  4. 	int len = 0;
  5. 	while (cur) {
  6. 		len++;
  7. 		cur = cur->next;
  8. 	}
  9. 	return len;
  10. }

通过单链表的遍历计数实现。

9.队列销毁

  1. void QueueDestroy(Queue* q) {// 销毁队列
  2. 	assert(q);
  3. 	QNode* cur = q->front->next;
  4. 	while (cur) {
  5. 		q->front->next = cur->next;
  6. 		free(cur);
  7. 		cur = q->front->next;
  8. 	}
  9. 	free(q->front);
  10. 	q->front = q->rear = NULL;
  11. }

循环释放每个结点，最后置空头尾指针。

四、接口测试

1.测试用例

  1. void Queue_Tese() {//队列功能测试函数
  2. 	Queue q;
  3. 	QueueInit(&q);
  4. 	printf("size = %d\n", QueueSize(&q));
  5.  
  6. 	// 入队列
  7. 	QueuePush(&q, 1);
  8. 	QueuePush(&q, 2);
  9. 	QueuePush(&q, 3);
  10. 	QueuePush(&q, 4);
  11. 	QueuePush(&q, 5);
  12. 	QueuePush(&q, 6);
  13. 	QueuePush(&q, 7);
  14. 	printf("\nsize = %d\n", QueueSize(&q));
  15. 	printf("front = %d\n", QueueFront(&q));
  16. 	printf("back = %d\n", QueueBack(&q));
  17.  
  18. 	// 出队列
  19. 	QueuePop(&q);
  20. 	printf("\nsize = %d\n", QueueSize(&q));
  21. 	printf("front = %d\n", QueueFront(&q));
  22. 	printf("back = %d\n", QueueBack(&q));
  23.  
  24. 	QueuePop(&q);
  25. 	QueuePop(&q);
  26. 	QueuePop(&q);
  27. 	QueuePop(&q);
  28. 	QueuePop(&q);
  29. 	printf("\nsize = %d\n", QueueSize(&q));
  30. 	printf("front = %d\n", QueueFront(&q));
  31. 	printf("back = %d\n", QueueBack(&q));
  32.  
  33. 	QueuePop(&q);
  34. 	QueuePop(&q);
  35. 	printf("\nsize = %d\n", QueueSize(&q));
  36. 	QueueDestroy(&q);
  37. }

2.测试结果

五、完整代码

  1. #include<stdio.h>
  2. #include<assert.h>
  3. #include<malloc.h>
  4.  
  5. // 链式结构：表示队列 
  6. typedef int QDataType;
  7. typedef struct QListNode
  8. {
  9. 	struct QListNode* next;
  10. 	QDataType data;
  11. }QNode;
  12.  
  13. // 队列的结构 
  14. typedef struct Queue
  15. {
  16. 	QNode* front;//队头
  17. 	QNode* rear;//队尾
  18. }Queue;
  19. void Queue_Tese();//队列功能测试函数
  20. QNode* buyQNode(QDataType data);//带头结点的单链表
  21. void QueueInit(Queue* q);// 初始化队列 
  22. void QueuePush(Queue* q, QDataType data);// 队尾入队列 
  23. void QueuePop(Queue* q);// 队头出队列 
  24. QDataType QueueFront(Queue* q);// 获取队列头部元素 
  25. QDataType QueueBack(Queue* q);// 获取队列队尾元素 
  26. int QueueSize(Queue* q);// 获取队列中有效元素个数 
  27. int QueueEmpty(Queue* q);// 检测队列是否为空，为空返回1，非空返回0 
  28. void QueueDestroy(Queue* q);// 销毁队列 
  29.  
  30. int main() {
  31. 	Queue_Tese();
  32. 	return 0;
  33. }
  34.  
  35. QNode* buyQNode(QDataType data) {//带头结点的单链表
  36. 	QNode* newNode = (QNode*)malloc(sizeof(QNode));
  37. 	if (newNode == NULL) {
  38. 		assert(0);
  39. 		return NULL;
  40. 	}
  41. 	newNode->data = data;
  42. 	newNode->next = NULL;
  43. 	return newNode;
  44. }
  45.  
  46. void QueueInit(Queue* q) {// 初始化队列
  47. 	assert(q);
  48. 	q->front = buyQNode(0);
  49. 	q->rear = q->front;
  50. }
  51.  
  52. void QueuePush(Queue* q, QDataType data) {// 队尾入队列 
  53. 	assert(q);
  54. 	QNode* newNode = buyQNode(data);
  55. 	q->rear->next = newNode;
  56. 	q->rear = newNode;
  57. }
  58.  
  59. int QueueEmpty(Queue* q) {// 检测队列是否为空，为空返回1，非空返回0 
  60. 	assert(q);
  61. 	return q->front == q->rear;
  62. }
  63.  
  64. void QueuePop(Queue* q){// 队头出队列 
  65. 	assert(q);
  66. 	if (QueueEmpty(q)) {//判空
  67. 		return;
  68. 	}
  69. 	QNode* delNode = q->front->next;
  70. 	q->front->next = delNode->next;
  71. 	if (delNode == q->rear) {//若队列只有一个元素，出队列后要将队尾放到头结点处
  72. 		q->rear = q->front;
  73. 	}
  74. 	free(delNode);
  75. }
  76.  
  77. QDataType QueueFront(Queue* q) {// 获取队列头部元素 
  78. 	assert(q);
  79. 	return q->front->next->data;
  80. }
  81.  
  82. QDataType QueueBack(Queue* q) {// 获取队列队尾元素
  83. 	assert(q);
  84. 	return q->rear->data;
  85. }
  86.  
  87. int QueueSize(Queue* q) {// 获取队列中有效元素个数 
  88. 	assert(q);
  89. 	QNode* cur = q->front->next;
  90. 	int len = 0;
  91. 	while (cur) {
  92. 		len++;
  93. 		cur = cur->next;
  94. 	}
  95. 	return len;
  96. }
  97.  
  98. void QueueDestroy(Queue* q) {// 销毁队列
  99. 	assert(q);
  100. 	QNode* cur = q->front->next;
  101. 	while (cur) {
  102. 		q->front->next = cur->next;
  103. 		free(cur);
  104. 		cur = q->front->next;
  105. 	}
  106. 	free(q->front);
  107. 	q->front = q->rear = NULL;
  108. }
  109.  
  110. void Queue_Tese() {//队列功能测试函数
  111. 	Queue q;
  112. 	QueueInit(&q);
  113. 	printf("size = %d\n", QueueSize(&q));
  114.  
  115. 	// 入队列
  116. 	QueuePush(&q, 1);
  117. 	QueuePush(&q, 2);
  118. 	QueuePush(&q, 3);
  119. 	QueuePush(&q, 4);
  120. 	QueuePush(&q, 5);
  121. 	QueuePush(&q, 6);
  122. 	QueuePush(&q, 7);
  123. 	printf("\nsize = %d\n", QueueSize(&q));
  124. 	printf("front = %d\n", QueueFront(&q));
  125. 	printf("back = %d\n", QueueBack(&q));
  126.  
  127. 	// 出队列
  128. 	QueuePop(&q);
  129. 	printf("\nsize = %d\n", QueueSize(&q));
  130. 	printf("front = %d\n", QueueFront(&q));
  131. 	printf("back = %d\n", QueueBack(&q));
  132.  
  133. 	QueuePop(&q);
  134. 	QueuePop(&q);
  135. 	QueuePop(&q);
  136. 	QueuePop(&q);
  137. 	QueuePop(&q);
  138. 	printf("\nsize = %d\n", QueueSize(&q));
  139. 	printf("front = %d\n", QueueFront(&q));
  140. 	printf("back = %d\n", QueueBack(&q));
  141.  
  142. 	QueuePop(&q);
  143. 	QueuePop(&q);
  144. 	printf("\nsize = %d\n", QueueSize(&q));
  145. 	QueueDestroy(&q);
  146. }

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

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

  

闽ICP备14008679号