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

【数据结构】 链队列的基本操作 （C语言版）

作者：prog456 | 2024-01-28 23:43:42

赞

踩

【数据结构】 链队列的基本操作 （C语言版）

目录

一、链队列

1、链栈的定义：

2、链栈的优缺点：

二、链队列的基本操作算法（C语言）    

1、宏定义

  2、创建结构体

3、链栈的初始化 

4、链队列的入队 

5、链队列的出队

6、取链队列的对头元素

7、链队列的销毁

8、链队列的清空

9、判断链队列是否为空

10、求队列长度

 11、遍历队列元素

三、链队列的基本操作完整代码（C语言）

  四、运行结果

一、链队列

1、链栈的定义：

链队列是一种线性数据结构，采用链表来实现队列的操作。链队列具有队头指针和队尾指针，用于指示队列元素所在的位置。链队列只允许在队尾插入元素，在队头删除元素，符合先进先出（First In First Out，FIFO）的原则。

2、链栈的优缺点：

链队列的优点：

  1. 动态分配空间：链队列使用链表实现，可动态分配和释放空间。因此，不需要预先分配大量存储空间，可以根据实际需求进行空间分配。
  2. 无需移动元素：相比普通队列，链队列在删除元素时无需移动大量元素，只需修改指针即可。这使得链队列在处理大规模数据时具有更高的效率。
  3. 适合处理用户排队等待的情况：链队列适用于处理用户排队等待的情况，例如银行排队、网络请求等。通过链队列，可以快速地插入新用户和删除已处理的用户。

链队列的缺点：

  1. 需要额外的存储空间：为了实现链表结构，链队列需要额外的存储空间来维护指针和节点。这会增加存储空间的消耗。
  2. 插入和删除操作可能引起内存分配和释放：在链队列中插入和删除元素时，可能需要动态分配和释放内存。这会增加操作的时间复杂度，并可能引起内存碎片化问题。
  3. 无法充分利用连续空间的优势：链表结构使得链队列无法像数组一样充分利用连续空间的优势，这会影响空间利用率和访问速度。

二、链队列的基本操作算法（C语言）    

1、宏定义
  1. #define OK 1
  2. #define ERROR 0
  3. #define OVERFLOW -1
  4.  
  5. #define MAXSIZE 100
  6.  
  7. typedef int QElemtype;
  8. typedef int Status;
  2、创建结构体
  1. //创建结构体
  2. typedef struct QNode {
  3.     QElemtype data;
  4.     struct QNode *next;
  5. } QNode, *QueuePtr;
  6.  
  7. typedef struct {
  8.     QueuePtr front;
  9.     QueuePtr rear;
  10. } LinkQueue;
3、链栈的初始化 
  1. //链队列的初始化
  2. Status InitQueue(LinkQueue &Q) {
  3.     Q.front = Q.rear = (QueuePtr) malloc(sizeof(QNode));
  4.     if (!Q.front) {
  5.         exit(OVERFLOW);
  6.     }
  7.     Q.front->next = NULL;
  8.     return OK;
  9. }
4、链队列的入队 
  1. //链队列的入队 
  2. Status EnQueue(LinkQueue &Q, QElemtype e) {
  3.     QueuePtr p = (QueuePtr) malloc(sizeof(QNode));
  4.     if (!p) {
  5.         exit(OVERFLOW);
  6.     }
  7.     p->data = e;
  8.     p->next = NULL;
  9.     Q.rear->next = p;
  10.     Q.rear = p;
  11.     return OK;
  12. }
5、链队列的出队
  1. //链队列的出队
  2. Status DeQueue(LinkQueue &Q, QElemtype &e) {
  3.     if (Q.front == Q.rear) {
  4.         return ERROR;
  5.     }
  6.     QueuePtr p = Q.front->next;
  7.     e = p->data;
  8.     Q.front->next = p->next;
  9.     if (Q.rear == p) {
  10.         Q.rear = Q.front;
  11.     }
  12.     delete p;
  13.     return OK;
  14.  
  15. }
6、取链队列的对头元素
  1. //取链列的对头元素 
  2. Status GetQueueHead(LinkQueue &Q, QElemtype &e) {
  3.     if (Q.front == Q.rear) {
  4.         return ERROR;
  5.     }
  6.     e = Q.front->next->data;
  7.     return OK;
  8.  
  9. }
7、链队列的销毁
  1. //队列的销毁
  2. Status DestoryQueue(LinkQueue &Q) {
  3.     while (Q.front) {
  4.         Q.rear = Q.front->next;
  5.         delete (Q.front);
  6.         Q.front = Q.rear;
  7.     }
  8. //    printf("销毁成功！");
  9.     return OK;
  10. }
8、链队列的清空
  1. //清空
  2. Status ClearQueue(LinkQueue &Q) {
  3.     Q.rear = Q.front->next;
  4.     while (Q.front->next) {
  5.         Q.rear = Q.rear->next;
  6.         delete (Q.front->next);
  7.         Q.front->next = Q.rear;
  8.     }
  9.     Q.rear = Q.front;
  10. //    printf("清空成功！");
  11.     return OK;
  12. }
9、判断链队列是否为空
  1. //判断是否为空
  2. Status QueueEmpty(LinkQueue &Q) {
  3.     if (Q.front == Q.rear) {
  4. //        printf("队列为空！\n");
  5.         return true;
  6.     } else {
  7.         return false;
  8.     }
  9. //    printf("该队列不为空！");
  10. }
10、求队列长度
  1. //求队列长度
  2. Status QueueLength(LinkQueue Q) {
  3.     int i = 0;
  4.     while (Q.front != Q.rear) {
  5.         i++;
  6.         Q.front = Q.front->next;
  7.     }
  8. //    printf("该队列长度为：%d", i);
  9.     return i;
  10. }
 11、遍历队列元素
  1. //遍历队列
  2. Status QueueTraverse(LinkQueue Q) {
  3.     QNode *p;
  4.     if (Q.front == Q.rear) {
  5.         return ERROR;
  6.     }
  7.     p = Q.front->next;//存储头元素
  8.     printf("从队头依次读出该队列中的元素值为: ");
  9.     while (p != NULL) {
  10.         printf("%d ", p->data);
  11.         p = p->next;
  12.     }
  13.     printf("\n");
  14.     return OK;
  15. }

三、链队列的基本操作完整代码（C语言）

  1. #include<stdio.h>
  2. #include<stdlib.h>
  3.  
  4. #define OK 1
  5. #define ERROR 0
  6. #define OVERFLOW -1
  7.  
  8. #define MAXSIZE 100
  9.  
  10. typedef int QElemtype;
  11. typedef int Status;
  12.  
  13. //创建结构体
  14. typedef struct QNode {
  15.     QElemtype data;
  16.     struct QNode *next;
  17. } QNode, *QueuePtr;
  18.  
  19. typedef struct {
  20.     QueuePtr front;
  21.     QueuePtr rear;
  22. } LinkQueue;
  23.  
  24. //链队列的初始化
  25. Status InitQueue(LinkQueue &Q) {
  26.     Q.front = Q.rear = (QueuePtr) malloc(sizeof(QNode));
  27.     if (!Q.front) {
  28.         exit(OVERFLOW);
  29.     }
  30.     Q.front->next = NULL;
  31.     return OK;
  32. }
  33.  
  34. //链队列的入队 
  35. Status EnQueue(LinkQueue &Q, QElemtype e) {
  36.     QueuePtr p = (QueuePtr) malloc(sizeof(QNode));
  37.     if (!p) {
  38.         exit(OVERFLOW);
  39.     }
  40.     p->data = e;
  41.     p->next = NULL;
  42.     Q.rear->next = p;
  43.     Q.rear = p;
  44.     return OK;
  45. }
  46.  
  47. //链队列的出队
  48. Status DeQueue(LinkQueue &Q, QElemtype &e) {
  49.     if (Q.front == Q.rear) {
  50.         return ERROR;
  51.     }
  52.     QueuePtr p = Q.front->next;
  53.     e = p->data;
  54.     Q.front->next = p->next;
  55.     if (Q.rear == p) {
  56.         Q.rear = Q.front;
  57.     }
  58.     delete p;
  59.     return OK;
  60.  
  61. }
  62.  
  63. //取链列的对头元素 
  64. Status GetQueueHead(LinkQueue &Q, QElemtype &e) {
  65.     if (Q.front == Q.rear) {
  66.         return ERROR;
  67.     }
  68.     e = Q.front->next->data;
  69.     return OK;
  70.  
  71. }
  72.  
  73.  
  74. //队列的销毁
  75. Status DestoryQueue(LinkQueue &Q) {
  76.     while (Q.front) {
  77.         Q.rear = Q.front->next;
  78.         delete (Q.front);
  79.         Q.front = Q.rear;
  80.     }
  81. //    printf("销毁成功！");
  82.     return OK;
  83. }
  84.  
  85. //清空
  86. Status ClearQueue(LinkQueue &Q) {
  87.     Q.rear = Q.front->next;
  88.     while (Q.front->next) {
  89.         Q.rear = Q.rear->next;
  90.         delete (Q.front->next);
  91.         Q.front->next = Q.rear;
  92.     }
  93.     Q.rear = Q.front;
  94. //    printf("清空成功！");
  95.     return OK;
  96. }
  97.  
  98.  
  99. //判断是否为空
  100. Status QueueEmpty(LinkQueue &Q) {
  101.     if (Q.front == Q.rear) {
  102. //        printf("队列为空！\n");
  103.         return true;
  104.     } else {
  105.         return false;
  106.     }
  107. //    printf("该队列不为空！");
  108. }
  109.  
  110. //求队列长度
  111. Status QueueLength(LinkQueue Q) {
  112.     int i = 0;
  113.     while (Q.front != Q.rear) {
  114.         i++;
  115.         Q.front = Q.front->next;
  116.     }
  117. //    printf("该队列长度为：%d", i);
  118.     return i;
  119. }
  120.  
  121.  
  122. //遍历队列
  123. Status QueueTraverse(LinkQueue Q) {
  124.     QNode *p;
  125.     if (Q.front == Q.rear) {
  126.         return ERROR;
  127.     }
  128.     p = Q.front->next;//存储头元素
  129.     printf("从队头依次读出该队列中的元素值为: ");
  130.     while (p != NULL) {
  131.         printf("%d ", p->data);
  132.         p = p->next;
  133.     }
  134.     printf("\n");
  135.     return OK;
  136. }
  137.  
  138.  
  139. //功能菜单列表
  140. void show_help() {
  141.     printf("******* 功能菜单列表 *******\n");
  142.     printf("1----入队------------------\n");
  143.     printf("2----求链队列长度----------\n");
  144.     printf("3----出队------------------\n");
  145.     printf("4----取队头元素-------------\n");
  146.     printf("5----清空循环队列-----------\n");
  147.     printf("6----销毁循环队列-----------\n");
  148.     printf("7----判断循环队列是否为空-----\n");
  149.     printf("8----批量插入元素------------\n");
  150.     printf("9----显示队列元素------------\n");
  151.     printf("10----退出------------------\n\n");
  152. }
  153.  
  154.  
  155. //主函数
  156. int main() {
  157.     LinkQueue LQ;
  158.     Status reIn = InitQueue(LQ);
  159.     if (reIn == OK) {
  160.         printf("链队列初始时成功  \n");
  161.     } else {
  162.         printf("链队列初始时失败 \n");
  163.     }
  164.  
  165.     while (1) {
  166.  
  167.         //功能菜单列表
  168.         show_help();
  169.  
  170.         int flag;
  171.         printf("请输入所需的功能编号：\n");
  172.         scanf("%d", &flag);
  173.  
  174.         switch (flag) {
  175.             case 1: {//入队
  176.                 Status EnQueueindex;
  177.                 printf("请输入插入元素(请在英文状态下输入例如:1): \n");
  178.                 scanf("%d", &EnQueueindex);
  179.                 Status rEnQueue = EnQueue(LQ, EnQueueindex);
  180.                 if (rEnQueue == OK) {
  181.                     printf("向链队列入队%d成功！\n", EnQueueindex);
  182.                 } else {
  183.                     printf("向链队列入队失败！\n");
  184.                 }
  185.             }
  186.                 break;
  187.             case 2: {//求链队列的长度
  188.                 int length = QueueLength(LQ);
  189.                 printf("链队列的长度为:%d。 \n\n", length);
  190.             }
  191.                 break;
  192.             case 3: {//出队
  193.                 QElemtype DeElem;
  194.                 Status DeEn = DeQueue(LQ, DeElem);
  195.                 if (DeEn == OK) {
  196.                     printf("从链队列中出队成功，出队的元素为 %d! \n", DeElem);
  197.                 } else {
  198.                     printf("从链队列中出队失败！\n");
  199.                 }
  200.             }
  201.                 break;
  202.             case 4: {//求队头元素
  203.                 QElemtype getEl;
  204.                 Status reGet = GetQueueHead(LQ, getEl);
  205.                 if (reGet == OK) {
  206.                     printf("从链队列中取对头元素成功，队头元素为:%d! \n", getEl);
  207.                 } else {
  208.                     printf("从链队列中取对头元素成功 \n");
  209.                 }
  210.             }
  211.                 break;
  212.             case 5: { //清空
  213.                 Status rClearStack = ClearQueue(LQ);
  214.                 if (rClearStack == OK) {
  215.                     printf("链队列清空成功！\n");
  216.                 } else {
  217.                     printf("链队列清空失败！\n");
  218.                 }
  219.             }
  220.                 break;
  221.             case 6: {//销毁
  222.                 Status rDestroyStack = DestoryQueue(LQ);
  223.                 if (rDestroyStack == OK) {
  224.                     printf("链队列销毁成功！\n");
  225.                 } else {
  226.                     printf("链队列销毁失败！\n");
  227.                 }
  228.             }
  229.                 break;
  230.             case 7: {///判空
  231.                 Status ClearStatus = QueueEmpty(LQ);
  232.                 if (ClearStatus == true) {
  233.                     printf("链队列为空！\n\n");
  234.                 } else {
  235.                     printf("链队列不为空！\n\n");
  236.                 }
  237.             }
  238.                 break;
  239.             case 8: {//批量插入
  240.                 int on;
  241.                 printf("请输入想要插入的元素个数：\n");
  242.                 scanf("%d", &on);
  243.                 QElemtype array[on];
  244.                 for (int i = 1; i <= on; i++) {
  245.                     printf("向链队列第%d个位置插入元素为:", i);
  246.                     scanf("%d", &array[i]);
  247.                 }
  248.  
  249.                 for (int i = 1; i <= on; i++) {
  250.                     Status InsertStatus = EnQueue(LQ, array[i]);
  251.                     if (InsertStatus == OK) {
  252.                         printf("向链队列第%d个位置插入元素%d成功！\n", i, array[i]);
  253.                     } else {
  254.                         printf("向链队列第%d个位置插入元素%d失败！\n", i, array[i]);
  255.                     }
  256.                 }
  257.             }
  258.                 break;
  259.             case 9: {//输出链表元素
  260.                 QueueTraverse(LQ);
  261. //                printf("\n");
  262.             }
  263.                 break;
  264.             case 10: {//退出程序
  265.                 return 0;
  266.             }
  267.                 break;
  268.             default: {
  269.                 printf("输入错误，无此功能，请检查输入:\n\n");
  270.             }
  271.         }
  272.     }
  273.  
  274.  
  275.     return 1;
  276. }

  四、运行结果

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

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

  

闽ICP备14008679号