C语言数据结构005 | 您所在的位置:网站首页 › 顺序循环队列解决了空间溢出的问题对吗 › C语言数据结构005 |
一、队列的基本概念
(1)定义:只能在表的一端进行插入操作,在表的另一端进行删除操作的线性表。 (2)特点:先进先出 示意图如下: 有6个存储空间的顺序队列动态示意图 ①假溢出 顺序队列因多次入队列和出队列操作后出现的虽有存储空间但不能进行入队列操作的情况。 ②如何解决顺序队列的假溢出问题? 可采取四种方法: 1 )采用循环队列; 2 )按最大可能的进队操作次数设置顺序队列的最大元素个数; 3 )修改出队算法,使每次出队列后都把队列中剩余数据元素向队头方向移动一个位置; 4)修改入队算法,增加判断条件,当假溢出时,把队列中的数据元素向对头移动,然后方完成入队操作。 新问题:在循环队列中,空队特征是front=rear;队满时也会有front=rear;判决条件将出现二义性! 解决方案有三: ①使用一个计数器记录队列中元素个数(即队列长度); 判队满:count>0 && rearfront; countMaxQueueSize 判队空:count0 ②加设标志位,出队时置0,入队时置1,则可识别当前front=rear属于何种情况 判队满:tag1 && rearfront 判队空:tag0 && rearfront ③ 少用一个存储单元 队满: front==(rear+1)%MaxQueueSize 判队空: rearfront 3.3、顺序循环队列的实现 //顺序循环队列的结构体定义如下: typedef struct { DataType queue[MaxQueueSize]; int rear; //队尾指针 int front; //队头指针 int count; //计数器 } SeqCQueue; //(1)初始化QueueInitiate(Q) void QueueInitiate(SeqCQueue *Q) { Q->rear = 0; Q->front = 0; Q->count = 0; } //(2)非空否QueueNotEmpty(Q) //判断循环队列Q非空否,非空则返回1,否则返回0 int QueueNotEmpty(SeqCQueue Q) { if(Q.count != 0) return 1; else return 0; } //(3)入队列QueueAppend(Q, x) //把数据元素值x插入顺序循环队列Q的队尾,成功返回1,失败返回0 int QueueAppend(SeqCQueue *Q, DataType x) { if(Q->count > 0 && Q->rear == Q->front) { printf("队列已满无法插入! \n"); return 0; } else { Q->queue[Q->rear] = x; Q->rear = (Q->rear + 1) % MaxQueueSize; Q->count++; return 1; } } //(4)出队列 QueueDelete(Q, d) //删除顺序循环队列Q的队头元素并赋值给d,成功则返回1,失败返回0 int QueueDelete(SeqCQueue *Q, DataType *d) { if(Q->count == 0) { printf("队列已空无数据元素出队列! \n"); return 0; } else { *d = Q->queue[Q->front]; Q->front = (Q->front + 1) % MaxQueueSize; Q->count--; return 1; } } //(5)取队头数据元素 QueueGet(Q, d) int QueueGet(SeqCQueue Q, DataType *d) { if(Q.count == 0) { printf("队列已空无数据元素可取! \n"); return 0; } else { *d = Q.queue[Q.front]; return 1; } } 四、链式存储结构的队列链式队列的存储结构 链式队列的队头指针指向队列的当前队头结点;队尾指针指在队列的当前队尾结点. 不带头结点的链式队列的结构如下: 优先级队列的出队列操作不是把队头元素出队列,而是把队列中优先级最高的元素出队列。 struct DataType { ElemType elem; //数据元素 int priority; //优先级 }; /*出队列操作 (把优先级最高的元素出队列并由函数返回,优先级相同时按先进先出的原则出队列。取顺序优先队列中优先级最高的元素算法类同)*/ int QueueDelete(SeqPQueue *Q, DataType *d) //删除优先级队列Q中优先级最高的元素 { DataType min; int minIndex, i; if(Q->size min = Q->queue[0]; minIndex = 0; for(i = 1; i size; i++){ if(Q->queue[i].priority Q->queue[i-1] = Q->queue[i]; } Q->size--; return 1; } } //取优先级最高的元素 int QueueGet(SeqPQueue *Q, DataType *d) { DataType min; int minIndex i; if(Q->size min=Q->queue[0]; minIndex =0; for(i=1;isize;i++) if(Q->queue[i].priority |
CopyRight 2018-2019 实验室设备网 版权所有 |