不学网

 找回密码
 立即注册

只需一步,快速开始

手机号码,快捷登录

查看: 362|回复: 0

[c/c++] [C数据结构]顺序队列(复用顺序表)

[复制链接]
j2cat 发表于 2018-1-6 19:22:06 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能,让你轻松玩转社区。

您需要 登录 才可以下载或查看,没有帐号?立即注册

x
SeqQueue.h
  1. #ifndef _SEQQUEUE_H_
  2. #define _SEQQUEUE_H_

  3. typedef void SeqQueue;

  4. //创建队列
  5. SeqQueue* SeqQueue_Create(int capacity);

  6. //销毁队列
  7. void SeqQueue_Destroy(SeqQueue* queue);

  8. //清空队列
  9. void SeqQueue_Clear(SeqQueue* queue);

  10. //入队列
  11. int SeqQueue_Append(SeqQueue* queue, void* item);

  12. //出队列
  13. void* SeqQueue_Retrieve(SeqQueue* queue);

  14. //获取头成员
  15. void* SeqQueue_Header(SeqQueue* queue);

  16. //队列长度
  17. int SeqQueue_Length(SeqQueue* queue);

  18. //队列容量
  19. int SeqQueue_Capacity(SeqQueue* queue);

  20. #endif
复制代码
SeqQueue.c
  1. #include "SeqQueue.h"
  2. #include "seqlist.h"

  3. //创建队列
  4. SeqQueue* SeqQueue_Create(int capacity) {
  5.         return seqlist_create(capacity);
  6. }

  7. //销毁队列
  8. void SeqQueue_Destroy(SeqQueue* queue) {
  9.         seqlist_destroy((Seqlist*)queue);
  10. }

  11. //清空队列
  12. void SeqQueue_Clear(SeqQueue* queue) {
  13.         seqlist_clear((Seqlist*)queue);
  14. }

  15. //入队列
  16. int SeqQueue_Append(SeqQueue* queue, void* item) {
  17.         return seqlist_insert((Seqlist*)queue, (Seqlistnode*)item, seqlist_length((Seqlist*)queue));
  18. }

  19. //出队列
  20. void* SeqQueue_Retrieve(SeqQueue* queue) {
  21.         return seqlistnode_delete((Seqlist*)queue, 0);
  22. }

  23. //获取头成员
  24. void* SeqQueue_Header(SeqQueue* queue) {
  25.         return seqlistnode_get((Seqlist*)queue, 0);
  26. }

  27. //队列长度
  28. int SeqQueue_Length(SeqQueue* queue) {
  29.         return seqlist_length((Seqlist*)queue);
  30. }

  31. //队列容量
  32. int SeqQueue_Capacity(SeqQueue* queue) {
  33.         return seqlist_capacity((Seqlist*)queue);
  34. }
复制代码
SeqQueue.c (优化)
  1. /*
  2. *顺序队列实现
  3. *队列状态:
  4. *当空队列时 length == 0, front == 0, rear == 0; (清空队列时的状态也一样)
  5. *当满队列时 length == capacity, front == rear;
  6. *当队列未满时 length < capacity, front != rear;
  7. *入队时 rear指向新元素  (rear+1)%capacity;
  8. *出队时 front指向下一个元素 (front+1)%capacity;
  9. * 0(front) ----------------------- n(rear)
  10. *
  11. */
  12. #include <malloc.h>
  13. #include "SeqQueue.h"

  14. //封装 TSeqQueueNode 为void* 存储node元素地址
  15. typedef void* TSeqQueueNode;
  16. //定义顺序队列体
  17. typedef struct _tag_SeqQueue {
  18.         int capacity; //容量
  19.         int length;   //长度
  20.         int front;    //指向队列第一个元素
  21.         int rear;     //指向队列最后一个元素
  22.         TSeqQueueNode* node;  //元素指针
  23. }TSeqQueue;

  24. //创建顺序队列
  25. SeqQueue* SeqQueue_Create(int capacity) { //O(1)
  26.         TSeqQueue* sQueue = NULL;
  27.         if (capacity >= 0) {
  28.                 //sizeof(队列类型大小) + sizeof(元素) * capacity(个数)
  29.                 sQueue = (TSeqQueue*)malloc(sizeof(TSeqQueue) + sizeof(TSeqQueueNode) * capacity);
  30.                 if (NULL != sQueue) {
  31.                         sQueue->capacity = capacity;
  32.                         sQueue->length = 0;
  33.                         sQueue->front = 0;
  34.                         sQueue->rear = 0;
  35.                         sQueue->node = (TSeqQueueNode*)(sQueue + 1);
  36.                 }
  37.         }
  38.        
  39.         return sQueue;
  40. }

  41. void SeqQueue_Destroy(SeqQueue* queue) {//O(1)
  42.         free(queue);
  43. }

  44. void SeqQueue_Clear(SeqQueue* queue) {//O(1)
  45.         TSeqQueue* sQueue = (TSeqQueue*)queue;
  46.         if (NULL != sQueue) {
  47.                 sQueue->length = 0;
  48.                 sQueue->front = 0;
  49.                 sQueue->rear = 0;
  50.         }
  51. }

  52. int SeqQueue_Append(SeqQueue* queue, void* item) {//O(1)
  53.         TSeqQueue* sQueue = (TSeqQueue*)queue;
  54.         int ret = (NULL != sQueue) && (NULL != item); //判断队列和新元素是否合法,不为空
  55.         ret = ret && (sQueue->length + 1 <= sQueue->capacity); //判断队列是否未满

  56.         if (ret) {
  57.                 sQueue->node[sQueue->rear] = (TSeqQueueNode)item;//rear位存储新元素
  58.                 sQueue->rear = (sQueue->rear + 1) % sQueue->capacity; //rear自加, 指向队尾
  59.                 sQueue->length++;
  60.         }

  61.         return ret;
  62. }

  63. void* SeqQueue_Retrieve(SeqQueue* queue) { //O(1)
  64.         TSeqQueue* sQueue = (TSeqQueue*)queue;
  65.         void* ret = SeqQueue_Header(queue); //获取队列第一个元素

  66.         if (NULL != ret) {//队列不为空
  67.                 sQueue->front = (sQueue->front + 1) % sQueue->capacity; //第一个元素出队 front指向下一个元素
  68.                 sQueue->length--;
  69.         }

  70.         return ret;
  71. }

  72. void* SeqQueue_Header(SeqQueue* queue) {//O(1)
  73.         TSeqQueue* sQueue = (TSeqQueue*)queue;
  74.         void* ret = NULL;
  75.         if (NULL != sQueue && 0 < sQueue->length) { //合法性判断 队列不能为NULL,长度不能为空队列
  76.                 ret = (void*)sQueue->node[sQueue->front]; //获取第一个元素地址
  77.         }

  78.         return ret;
  79. }

  80. int SeqQueue_Capacity(SeqQueue* queue) {//O(1)
  81.         TSeqQueue* sQueue = (TSeqQueue*)queue;
  82.         int ret = -1;
  83.         if (NULL != sQueue) {
  84.                 ret = sQueue->capacity;
  85.         }
  86.         return ret;
  87. }

  88. int SeqQueue_Length(SeqQueue* queue) {//O(1)
  89.         TSeqQueue* sQueue = (TSeqQueue*)queue;
  90.         int ret = -1;
  91.         if (NULL != sQueue) {
  92.                 ret = sQueue->length;
  93.         }
  94.         return ret;
  95. }
复制代码


回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

QQ|手机版|小黑屋|不学网

GMT+8, 2018-9-19 04:58

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

快速回复 返回顶部 返回列表