C/C++数据结构-完整代码（三）队列【Queue】（顺序存储，链式存储）增删改查

转x33g5p2x  于2021-09-19 转载在 C/C++  
字(8.8k)|赞(0)|评价(0)|浏览(741)

队列

1、队列的基本概念

队列是一种特殊的线性表，

特殊之处在于它只允许在表的前端（front）进行删除操作，

而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。

进行插入操作的端称为队尾，进行删除操作的端称为队头。

队列中没有元素时，称为空队列。
队列的数据元素又称为队列元素。

在队列中插入一个队列元素称为入队，从队列中删除一个队列元素称为出队。

因为队列只允许在一端插入，在另一端删除，

所以只有最早进入队列的元素才能最先从队列中删除，

故队列又称为先进先出（FIFO—first in first out）线性表。

2、队列的顺序存储

基本概念

队列是在之前的动态数组的基础上实现的

先向项目当中导入以下两个文件

  • dynamaicArray.c
  1. #include "dynamaicArray.h"
  3. //初始化数组
  4. struct dynamicAray * init_DynamicArray(int  capacity){
  5.     //开辟到堆区
  6.     if(capacity <= 0){
  7.         return NULL;
  8.     }
  9.     struct dynamicAray * array = malloc(sizeof(struct dynamicAray ));
  10.     //判断内存是否申请成功
  11.     if(array == NULL){
  12.         return NULL;
  13.     }
  14.     //设置容量
  15.     array -> m_capacity = capacity;
  16.     //设置大小
  17.     array -> m_size = 0;
  18.     //维护在堆区数组的指针
  19.     array ->pAddr = malloc(sizeof(void*) * array-> m_capacity);
  20.     return array;
  21. }
  22. //插入功能
  23. void insert_dynamicArray(struct dynamicAray * array,int pos,void *data){
  24.     if(array == NULL){
  25.         return;
  26.     }
  27.     if(data == NULL){
  28.         return;
  29.     }
  30.     if(pos < 0 || pos > array->m_size){
  31.         //无效的位置 进行尾插
  32.         pos = array-> m_size;//插入到当前数组的最后一个位置
  33.     }
  34.     //先判断是否已经满载，如果满载的就动态的开辟
  35.     if(array -> m_size >=array -> m_capacity){
  36.         //1、申请一个更大的内存空间
  37.         int newCapacity = array->m_capacity * 2;
  38.         //2、创建新的空间
  39.         void ** newSpace =  malloc(sizeof(void *) * newCapacity);
  40.         //3、将原有的数据 拷贝到新空间下
  41.         memcpy(newSpace,array->pAddr,sizeof(void  * ) * array->m_capacity);
  42.         //4、释放原有的空间
  43.         free(array->pAddr);
  44.         //5、更改指针的指向
  45.         array -> pAddr = newSpace;
  46.         //6、更新新容量的大小
  47.         array -> m_capacity = newCapacity;
  48.     }
  49.     //插入新的数据的元素
  50.     //从最后一个位置开始依次往后移动数据 后移
  51.     int i;
  52.     for(i = array -> m_size -1 ;i >= pos;i--){
  53.         array->pAddr[i+1] = array->pAddr[i];
  54.     }
  55.     //将新元素插入到指定的位置
  56.     array -> pAddr[pos] = data;
  58.     //更新一下大小
  59.     array ->m_size++;
  60. }
  61. //遍历数组
  62. void foreach_DynamicArray(struct dynamicAray * array,void(*myForeach)(void *)){
  64.     if(array == NULL){
  65.         return;
  66.     }
  67.     if(myForeach == NULL){
  68.         return;
  69.     }
  70.     int i;
  71.     for(i = 0; i < array ->m_size; i++)
  72.     {
  73.         myForeach(array->pAddr[i]);
  74.     }
  76. }
  77. //删除素质当中的元素
  78. void removeByPos_DynamicArray(struct dynamicAray * array, int pos){
  80.     if(array == NULL)
  81.     {
  82.         return ;
  83.     }
  84.     if(pos < 0 || pos > array->m_size-1){
  85.         //无效的位置 直接return
  86.         return;
  87.     }
  88.     //从pos位置开始 到数组的尾，数据进行前移动
  89.     int i;
  90.     for(i = pos; i < array->m_size -1; i++){
  91.         array->pAddr[i] = array->pAddr[i+1];
  92.     }
  93.     array->m_size--;
  95. }
  96. void myPrintPerson(void * data){
  97.     struct Person * p = data;
  98.     printf("姓名：%s,年龄%d\n",p->name,p->age);
  99. }
  100. //销毁数据
  101. void destroy_DynamicArray(struct dynamicAray * arr){
  102.     if(arr == NULL)
  103.     {
  104.         return;
  105.     }
  106.     if(arr->pAddr != NULL)
  107.     {
  108.         free(arr->pAddr);
  109.         arr->pAddr = NULL;
  110.     }
  111.     free(arr);
  112.     arr = NULL;
  113. }
  115. void test01(){
  116.     //创建 动态数组
  117.     struct dynamicAray * arr = init_DynamicArray(5);
  118.     //准备出5个person 数据
  119.     struct Person p1 = {"亚瑟",28 };
  120.     struct Person p2 = {"王昭君",18 };
  121.     struct Person p3 = {"赵云",38 };
  122.     struct Person p4 = {"张飞",38 };
  123.     struct Person p5 = {"关羽",28 };
  124.     struct Person p6 = {"宫本",88 };
  125.     printf("当前的容量为：%d\n",arr->m_capacity);
  126.     //将数据插入到动态数组当中
  127.     insert_dynamicArray(arr,0,&p1);
  128.     insert_dynamicArray(arr,0,&p2);
  129.     insert_dynamicArray(arr,0,&p3);
  130.     insert_dynamicArray(arr,2,&p4);
  131.     insert_dynamicArray(arr,10,&p5);
  132.     insert_dynamicArray(arr,1,&p6);
  133.     printf("插入数据后的容量为：%d\n",arr->m_capacity);
  134.     //赵云 宫本 王昭君 张飞 亚瑟 关羽
  135.     //遍历动态数组
  136.     printf("删除前\n");
  137.     foreach_DynamicArray(arr,myPrintPerson);
  138.     //删除数组当中的元素
  139.     removeByPos_DynamicArray(arr,1);
  140.     printf("删除后\n");
  141.     foreach_DynamicArray(arr,myPrintPerson);
  142. }
  • dynamaicArray.h
  1. #include "stdio.h"
  2. #include "string.h"
  3. #include "stdlib.h"
  4. //动态数组的结构
  5. struct dynamicAray{
  6.     void ** pAddr;//维护在堆区真实的数组指针
  7.     int m_capacity;//数组的容量
  8.     int m_size;//数组的大小
  9. };
  10. //初始化数组
  11. struct dynamicAray * init_DynamicArray(int  capacity);
  12. //插入功能
  13. void insert_dynamicArray(struct dynamicAray * array,int pos,void *data);
  14. //遍历数组
  15. void foreach_DynamicArray(struct dynamicAray * array,void(*myForeach)(void *));
  16. //删除素质当中的元素
  17. void removeByPos_DynamicArray(struct dynamicAray * array, int pos);
  19. void destroy_DynamicArray(struct dynamicAray * arr);
  21. struct Person{
  22.     char name[64];
  23.     int age;
  24. };
  26. void myPrintPerson(void * data);
  28. void test01();
  • 创建seqQueue.h

  1. #pragma once
  2. #include "stdio.h"
  3. #include "string.h"
  4. #include "stdlib.h"
  5. #include "dynamaicArray.h"
  6. #define MAX 1024
  7. typedef void * seqQueue;
  9. //初始化队列
  10. seqQueue init_SeqQueue();
  11. //入队
  12. void push_SeqQueue(seqQueue queue, void * data);
  13. //出队
  14. void pop_SeqQueue(seqQueue queue);
  15. //返回队头元素
  16. void * front_SeqQueue(seqQueue queue);
  17. //返回队尾元素
  18. void * back_SeqQueue(seqQueue queue);
  19. //返回队尾大小
  20. int size_seqQueue(seqQueue queue);
  21. //销毁
  22. void destroy_SeqQueue(seqQueue queue);
  • seqQueue.c
  1. #include "seqQueue.h"
  2. //初始化队列
  3. seqQueue init_SeqQueue()
  4. {
  5.     struct dynamicAray * arr = init_DynamicArray (MAX);
  6.     return arr;
  7. }
  8. //入队
  9. void push_SeqQueue(seqQueue queue, void * data){
  10.     if(queue == NULL){
  11.         return;
  12.     }
  13.     if(data == NULL){
  14.         return;
  15.     }
  16.     struct dynamicAray * myQueue = queue;//将当前插入数据转换为原本的数据
  17.     if(myQueue->m_size >= MAX){
  18.         return;
  19.     }
  20.     //入队 === 尾插
  21.     insert_dynamicArray (myQueue,myQueue->m_size,data);
  22. }
  23. //出队
  24. void pop_SeqQueue(seqQueue queue){
  25.     if(queue == NULL){
  26.         return;
  27.     }
  28.     struct dynamicAray * myQueue = queue;
  29.     if(myQueue ->m_size <= 0){
  30.         return;
  31.     }
  32.     removeByPos_DynamicArray (myQueue,0);
  33. }
  34. //返回队头元素
  35. void * front_SeqQueue(seqQueue queue){
  36.     if(queue == NULL){
  37.         return NULL;
  38.     }
  39.     struct dynamicAray * myQueue = queue;
  40.     return myQueue->pAddr[0];
  41. }
  42. //返回队尾元素
  43. void * back_SeqQueue(seqQueue queue){
  44.     if(queue == NULL){
  45.         return NULL;
  46.     }
  47.     struct dynamicAray * myQueue = queue;
  48.     return myQueue->pAddr[myQueue->m_size-1];
  49. }
  50. //返回队尾大小
  51. int size_seqQueue(seqQueue queue){
  52.     if(queue == NULL){
  53.         return -1;
  54.     }
  55.     struct dynamicAray * myQueue = queue;
  56.     return myQueue->m_size;
  57. }
  58. //销毁
  59. void destroy_SeqQueue(seqQueue queue){
  60.     if(queue == NULL){
  61.         return;
  62.     }
  63.     destroy_DynamicArray (queue);
  65. }
  • 在main.c当中
  1. #include <stdio.h>
  2. #include "seqQueue.h"
  4. void test02(){
  5.     //初始化队列
  6.     seqQueue  queue = init_SeqQueue();
  7.     
  9.     while (size_seqQueue (queue) > 0 ){
  10.         //获取对头元素
  11.         struct Person * pFont =  front_SeqQueue (queue);
  12.         //打印队尾元素
  13.         printf ("Front element\tName:%s\t\tAge:%d\n",pFont->name ,pFont->age);
  14.         //获取队尾元素
  15.         struct Person * pBack =  back_SeqQueue(queue);
  16.         //打印队尾元素
  17.         printf ("Back element \tName:%s\t\tAge:%d\n",pBack->name ,pBack->age);
  18.         //出队
  19.         pop_SeqQueue (queue);
  20.     }
  21.     printf ("Queue\t size:%d\n", size_seqQueue (queue));
  22.     //销毁
  23.     destroy_SeqQueue (queue);
  24. }
  26. int main () {
  27.     printf ("Hello, World!\n");
  28.     test02();
  29.     return 0;
  30. }

运行结果

3、队列的链式存储

对外接口
初始化
入队
出队
返回对头
返回队尾大小

分文件编写
目录结构

（1）linkQueue.h

  1. #pragma once
  2. #include "stdio.h"
  3. #include "string.h"
  4. #include "stdlib.h"
  6. //声明链表的节点
  7. struct QueueNode{
  8.     struct QueueNode * next;//只维护指针域
  9. };
  10. //队列的结构体
  11. struct LQueue{
  12.     //头节点
  13.     struct QueueNode pHeader;
  14.     //队列的大小
  15.     int m_Size;
  16.     //维护尾节点的指针
  17.     struct QueueNode * pTail;
  18. };
  19. typedef void * LinkQueue;
  20. //初始化队列
  21. LinkQueue init_LinkQueue();
  22. //入队
  23. void  push_LinkQueue(LinkQueue queue,void * data);
  24. //出队
  25. void pop_LinkQueue(LinkQueue queue);
  26. //返回对头
  27. void * front_LinkQueue(LinkQueue queue);
  28. //返回队尾
  29. void * back_LinkQueue(LinkQueue queue);
  30. //返回队的大小
  31. int size_LinkQueue(LinkQueue queue);
  32. //销毁
  33. void destory_LinkQueue(LinkQueue queue);
（2）linkQueue.c

  1. #include "linkQueue.h"
  3. //初始化队列
  4. LinkQueue init_LinkQueue(){
  5.     struct  LQueue * myQueue = malloc (sizeof(struct LQueue));
  7.     if(myQueue == NULL){
  8.         return NULL;
  9.     }
  10.     myQueue->pHeader.next = NULL;
  11.     myQueue->m_Size = 0;
  12.     myQueue->pTail = &(myQueue->pHeader);//尾结点的初始化，就是在头结点
  13.     return myQueue;
  14. }
  15. //入队
  16. void  push_LinkQueue(LinkQueue queue,void * data){
  17.     if(queue == NULL){
  18.         return;
  19.     }
  20.     if(data == NULL){
  21.         return;
  22.     }
  23.     //还原真实的队列的结构体
  24.     struct LQueue * myQueue = queue;
  25.     //取出用户数据的前四个字节
  26.     struct  QueueNode * myNode = data;
  27.     //插入新I节点-尾插，将队列的为节点的指针指向新节点（也就是尾结点的指针保存新节点的地址）
  28.     myQueue->pTail->next = myNode;
  29.     //将新节点的指针域置空
  30.     myNode->next = NULL;
  32.     myQueue->pTail = myNode;//移动尾节点的指针到新节点的位置
  34.     //更新队列的长度
  35.     myQueue->m_Size++;
  36. }
  37. //出队
  38. void pop_LinkQueue(LinkQueue queue){
  39.     if(queue == NULL){
  40.         return;
  41.     }
  42.     struct LQueue * myQueue = queue;
  44.     if(myQueue->m_Size <= 0){
  45.         return;
  46.     }
  47.     //获取链表当中第一个有数据的节点
  48.     struct QueueNode * pFirst = myQueue->pHeader.next;
  49.     //更新指针的指向
  50.     myQueue->pHeader.next = pFirst->next;
  52.     //更新队列的长度
  53.     myQueue->m_Size--;
  55. }
  56. //返回对头
  57. void * front_LinkQueue(LinkQueue queue){
  58.     if(queue == NULL){
  59.         return NULL;
  60.     }
  61.     struct LQueue * myQueue = queue;
  63.     return myQueue->pHeader.next;
  64. }
  65. //返回队尾
  66. void * back_LinkQueue(LinkQueue queue){
  67.     if(queue == NULL){
  68.         return NULL;
  69.     }
  70.     struct LQueue * myQueue = queue;
  72.     return myQueue->pTail;
  73. }
  74. //返回队的大小
  75. int size_LinkQueue(LinkQueue queue){
  76.     if(queue == NULL){
  77.         return -1;
  78.     }
  79.     struct LQueue * myQueue = queue;
  81.     return myQueue->m_Size;
  82. }
  83. //销毁
  84. void destory_LinkQueue(LinkQueue queue){
  86.     if(queue == NULL){
  87.         return;
  88.     }
  89.     free (queue);
  90.     queue == NULL;
  92. }
（2）main.c

  1. #include "stdio.h"
  2. #include "linkQueue.h"
  4. struct Person{
  5.     void * node;
  6.     char name[64];
  7.     int age;
  8. };
  9. void test01(){
  11.     LinkQueue  queue =  init_LinkQueue();
  13.     //准备数据
  14.     struct Person p1 = {NULL,"aa",10};
  15.     struct Person p2 = {NULL,"bb",20};
  16.     struct Person p3 = {NULL,"cc",30};
  17.     struct Person p4 = {NULL,"dd",40};
  18.     struct Person p5 = {NULL,"ee",50};
  19.     //入队
  21.     push_LinkQueue (queue,&p1);
  22.     push_LinkQueue (queue,&p2);
  23.     push_LinkQueue (queue,&p3);
  24.     push_LinkQueue (queue,&p4);
  25.     push_LinkQueue (queue,&p5);
  26.     printf ("LinkQueue size : %d \n", size_LinkQueue (queue));
  27.     while (size_LinkQueue (queue) > 0){
  28.         struct  Person * pFront = front_LinkQueue (queue);
  29.         printf ("front_LinkQueue Name = %s\tAge = %d\n",pFront->name,pFront->age);
  31.         struct  Person * pBack = back_LinkQueue(queue);
  32.         printf ("back_LinkQueue Name = %s\tAge = %d\n",pBack->name,pBack->age);
  33.         pop_LinkQueue(queue);
  34.     }
  36.     printf ("LinkQueue size : %d \n", size_LinkQueue (queue));
  38.     destory_LinkQueue (queue);
  40. }
  42. int main () {
  43.     test01();
  44.     printf ("Hello, World!\n");
  45.     return 0;
  46. }

运行结果

版权说明 : 本文为转载文章, 版权归原作者所有 版权申明

原文链接 : https://blog.csdn.net/qq_44757034/article/details/120165289

内容来源于网络，如有侵权，请联系作者删除！

数据结构c++c/c++语言(数据结构)

相关文章

    查看更多

    热门标签

    更多
    JavaquerypythonNode开发语言requestUtil数据库Table后端算法LoggerMessageElementParser

    最新文章

    更多
    • 蜀ICP备13028337号-1 大数据知识库 https://www.saoniuhuo.com © All rights reserved
    • 本站内容来源互联网,如果侵犯您的权益请联系我们删除, 联系方式：448109455@qq.com