当前位置:   article > 正文

数据结构学习——链式队列的创建和使用_初始化并建立链队列,入链队列,出链队列,遍历链队列

初始化并建立链队列,入链队列,出链队列,遍历链队列

一、队列的介绍

        队列是一种常见的数据结构,它遵循先进先出(First-In-First-Out, FIFO)的原则,在队列的操作中入队从队列的尾部插入,出队的时候释放队列的头节点并且更新新的头节点。队列的存储方式主要有两种,分别是链式存储和顺序存储。每种存储方式都有其特点和适用场景。链式存储适合频繁进行插入和删除操作的队列,而顺序存储则适合频繁进行访问操作的队列。选择适当的存储方式要根据具体的应用需求和性能要求来决定。本篇主要介绍链式存储。

二、队列的创建以及初始化

        因为要用到链式存储的结构,因此需要定义结点结构体,以及队列的头尾指针。这里定义节点数据为int类型的data,结构体指针为next

  1. typedef struct Node{
  2. int data;
  3. struct Node* next;
  4. }Node; //结点结构体定义
  5. typedef struct{
  6. Node* front; //头指针
  7. Node* rear; //尾指针
  8. }Queue;

        队列的初始化即分配一个节点内存,并且将头尾指针都指向这个空节点。

  1. //链队列初始化
  2. void Init_Queue(Queue* queue){
  3. //创建头节点
  4. queue->front = queue->rear = (Node*)malloc(sizeof(Node));
  5. if( !queue->front ){
  6. printf("内存分配失败\n");
  7. return;
  8. }
  9. }

三、入队列

        入队列即在队尾插入一个新的节点,首先需要分配一块内存空间,将原来队尾指针指向新节点,并将新节点作为新的队尾。

  1. //入队列
  2. void Insert_Queue(Queue* queue,int value){
  3. Node* newCode;
  4. newCode = (Node*)malloc(sizeof(Node));
  5. if(newCode == NULL){
  6. printf("内存分配失败\n");
  7. return;
  8. }
  9. newCode->data = value;
  10. newCode->next = NULL;
  11. //判断是否是空队列
  12. if(queue->front == NULL){
  13. printf("该队列是空的\n");
  14. return;
  15. }
  16. //在尾部插入新节点
  17. queue->rear->next = newCode;
  18. //更新尾指针
  19. queue->rear = newCode;
  20. }

四、出队列

        出队列的操作需要从队列的头进行,遵循先进先出的原理,因此需要将原来的头节点取出并释放,将下一个节点作为新的头节点。

  1. void Delete_Queue(Queue* queue){
  2. if(queue->front == NULL){
  3. printf("该队列是空的\n");
  4. return;
  5. }
  6. /*queue->front为头指针,指向的头节点*/
  7. Node* pout = queue->front;
  8. //更新头指针
  9. queue->front = queue->front->next;
  10. //若队列中仅剩一个结点时,删除了该节点后
  11. //队列就为空,此时应该从新初始化
  12. if(queue->front == NULL)
  13. queue->rear = NULL;
  14. //释放删除结点的内存
  15. free(pout);
  16. }

五、销毁队列

        销毁一个队列就是在出队列的基础上进行一个循环,跳出循环的条件就是链队列的头指针为空,并且逐个节点进行释放,最后重置链队列的头尾节点。

  1. void Destroy_Queue(Queue* queue){
  2. Node* p = queue->front;
  3. while(p != NULL){
  4. Node* temp = p;
  5. p = p->next;
  6. free(temp);
  7. }
  8. printf("队列销毁成功!\n");
  9. //内存释放后指针重置,指向空
  10. queue->front = NULL;
  11. queue->rear = NULL;
  12. }

六、遍历队列

        这里链队列的头指针指向了节点的头地址,因此要遍历打印队列需要从头指针的下一个节点开始。由于遍历链队列不需要对其进行修改,函数参数就不需要引用指针。

  1. void Print_Queue(Queue queue){
  2. if(queue.front == NULL){
  3. printf("该队列是空的\n");
  4. return;
  5. }
  6. Node* temp = queue.front->next;
  7. printf("该队列的内容为:\n");
  8. while(temp != NULL){
  9. printf("%d ",temp->data);
  10. temp = temp->next;
  11. }
  12. printf("\n");
  13. }

七、获取链队列的头

  1. int GetHead_Queue(Queue queue){
  2. if(queue.front == NULL){
  3. printf("该队列是空的\n");
  4. return -1;
  5. }
  6. return queue.front->next->data;
  7. }

八、主函数及全部代码

        主函数:

  1. void main(){
  2. //创建队列
  3. Queue queue;
  4. //队列初始化
  5. Init_Queue(&queue);
  6. //插入结点
  7. Insert_Queue(&queue,1);
  8. Insert_Queue(&queue,2);
  9. Insert_Queue(&queue,3);
  10. Print_Queue(queue);
  11. printf("该队列的头节点值为: %d \n",GetHead_Queue(queue));
  12. //删除结点
  13. Delete_Queue(&queue);
  14. Print_Queue(queue);
  15. //销毁队列
  16. Destroy_Queue(&queue);
  17. Print_Queue(queue);
  18. }

全部代码:

  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <malloc.h>
  4. typedef struct Node{
  5. int data;
  6. struct Node* next;
  7. }Node; //结点结构体定义
  8. typedef struct{
  9. Node* front; //头指针
  10. Node* rear; //尾指针
  11. }Queue;
  12. //链队列初始化
  13. void Init_Queue(Queue* queue){
  14. //创建头节点
  15. queue->front = queue->rear = (Node*)malloc(sizeof(Node));
  16. if( !queue->front ){
  17. printf("内存分配失败\n");
  18. return;
  19. }
  20. }
  21. //入队列
  22. void Insert_Queue(Queue* queue,int value){
  23. Node* newCode;
  24. newCode = (Node*)malloc(sizeof(Node));
  25. if(newCode == NULL){
  26. printf("内存分配失败\n");
  27. return;
  28. }
  29. newCode->data = value;
  30. newCode->next = NULL;
  31. //判断是否是空队列
  32. if(queue->front == NULL){
  33. printf("该队列是空的\n");
  34. return;
  35. }
  36. //在尾部插入新节点
  37. queue->rear->next = newCode;
  38. //更新尾指针
  39. queue->rear = newCode;
  40. }
  41. void Delete_Queue(Queue* queue){
  42. if(queue->front == NULL){
  43. printf("该队列是空的\n");
  44. return;
  45. }
  46. /*queue->front为头指针,指向的头节点*/
  47. Node* pout = queue->front;
  48. //更新头指针
  49. queue->front = queue->front->next;
  50. //若队列中仅剩一个结点时,删除了该节点后
  51. //队列就为空,此时应该从新初始化
  52. if(queue->front == NULL)
  53. queue->rear = NULL;
  54. //释放删除结点的内存
  55. free(pout);
  56. }
  57. void Print_Queue(Queue queue){
  58. if(queue.front == NULL){
  59. printf("该队列是空的\n");
  60. return;
  61. }
  62. Node* temp = queue.front->next;
  63. printf("该队列的内容为:\n");
  64. while(temp != NULL){
  65. printf("%d ",temp->data);
  66. temp = temp->next;
  67. }
  68. printf("\n");
  69. }
  70. void Destroy_Queue(Queue* queue){
  71. Node* p = queue->front;
  72. while(p != NULL){
  73. Node* temp = p;
  74. p = p->next;
  75. free(temp);
  76. }
  77. printf("队列销毁成功!\n");
  78. //内存释放后指针重置,指向空
  79. queue->front = NULL;
  80. queue->rear = NULL;
  81. }
  82. int GetHead_Queue(Queue queue){
  83. if(queue.front == NULL){
  84. printf("该队列是空的\n");
  85. return -1;
  86. }
  87. return queue.front->next->data;
  88. }
  89. void main(){
  90. //创建队列
  91. Queue queue;
  92. //队列初始化
  93. Init_Queue(&queue);
  94. //插入结点
  95. Insert_Queue(&queue,1);
  96. Insert_Queue(&queue,2);
  97. Insert_Queue(&queue,3);
  98. Print_Queue(queue);
  99. printf("该队列的头节点值为: %d \n",GetHead_Queue(queue));
  100. //删除结点
  101. Delete_Queue(&queue);
  102. Print_Queue(queue);
  103. //销毁队列
  104. Destroy_Queue(&queue);
  105. Print_Queue(queue);
  106. }

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

闽ICP备14008679号