数据结构系列－队列的基本操作 |
您所在的位置：网站首页 › cad中的基本操作有哪些种类的 › 数据结构系列－队列的基本操作 |
|
队列(Queue)是只允许在一端进行插入操作，而在另一端进行删除操作的线性表。允许插入的端是队尾，允许删除的端是队头。 所以说队列是一个先进先出的线性表，相应的也有顺序存储和链式存储两种方式。 顺序存储就是用数组实现，比如有一个ｎ个元素的队列，数组下标0的一端是队头，入队操作就是通过数组下标一个个顺序追加，不需要移动元素，但是如果删除队头元素，后面的元素就要往前移动，对应的时间复杂度就是O(n)，性能自然不高。 为了提高出队的性能，就有了循环队列，什么是循环队列呢？就是有两个指针，front指向队头，rear指向对尾元素的下一个位置，元素出队时front往后移动，如果到了对尾则转到头部，同理入队时rear后移，如果到了对尾则转到头部，这样通过下标front出队时，就不需要移动元素了。 同时规定，当队列为空时，front和rear相等，那么队列什么时候判断为满呢？按照循环操作rear依次后移，然后再从头开始，也是出现rear和front相等时，队列满。这样跟队列空的情况就相同了，为了区分这种情况，规定数组还有一个空闲单元时，就表示队列已满，因为rear 可能在front后面，也可能循环到front前面，所以队列满的条件就变成了(rear+1)%maxsize = front ,同时队列元素个数的计算就是(rear -front+maxsize)%maxsize。 如下是循环队列的数据结构及基本操作实现： #include "stdio.h" #include "stdlib.h" #include "io.h" #include "math.h" #include "time.h" #define OK 1 #define ERROR 0 #define TRUE 1 #define FALSE 0 #define MAXSIZE 11 //初始容量 typedef int Status; typedef int QElemType;//定义数据类型 //循环队列的顺序存储结构 typedef struct{ QElemType data[MAXSIZE]; int front; //头指针 int rear;//尾指针，队列非空时，指向队尾元素的下一个位置 }SqQueue; Status visit(QElemType item){ printf("%d",item); return OK; } //初始化空队列 Status InitQueue(SqQueue *sQ){ sQ->front =0; sQ->rear =0; return OK; } //将队列清空 Status ClearQueue(SqQueue *Q){ Q->front = Q->rear =0; return OK; } //判断队列是否为null Status QueueEmpty(SqQueue Q){ if(Q.front == Q.rear) return TRUE; else return FALSE; } //返回队列中的元素个数 int QueueLength(SqQueue Q){ return (Q.rear-Q.front+MAXSIZE)%MAXSIZE; } //返回队头元素 Status GetHead(SqQueue Q, QElemType *e){ if(Q.front == Q.rear)//是否为空队列 return ERROR; *e = Q.data[Q.front]; return OK; } //在队尾插入元素 Status EnQueue(SqQueue *Q, QElemType e){ if((Q->rear+1)%MAXSIZE == Q->front)//队列已满 return ERROR; Q->data[Q->rear] =e;//插入队尾 Q->rear = (Q->rear +1)%MAXSIZE;//尾部指针后移，如果到最后则转到头部 return OK; } //元素出队 Status DeQueue(SqQueue *Q, QElemType *e){ if(Q->front == Q->rear)//队列空 return ERROR; *e = Q->data[Q->front];//返回队头元素 Q->front = (Q->front+1)%MAXSIZE;//队头指针后移，如到最后转到头部 return OK; } //遍历队列元素 Status QueueTraverse(SqQueue Q){ int i = Q.front; while((i+Q.front) != Q.rear){ visit(Q.data[i]); i=(i+1)%MAXSIZE; } printf("\n"); return OK; } int main(){ Status j; int i=0,l; QElemType d; SqQueue Q; InitQueue(&Q); //入队１０个元素 for(int i =0;i< MAXSIZE-1; i++){ EnQueue(&Q,i); } QueueTraverse(Q); printf("依次出队:"); for(l=1;lfront = Q->rear = (QueuePtr)malloc(sizeof(QNode)); if(!Q->front) exit(OVERFLOW); Q->front->next =NULL; return OK; } //销毁队列 Status DestroyQueue(LinkQueue *Q){ while(Q->front){ Q->rear=Q->front->next;//从队头开始销毁 free(Q->front); Q->front = Q->rear; } return OK; } //清空队列，队头指针还在 Status ClearQueue(LinkQueue *Q){ QueuePtr p,q; Q->rear =Q->front;//跟初始状态相同，Q->rear指向头结点 p=Q->front->next;//开始销毁队头元素，队头，对尾依然保留 Q->front->next =NULL; while(p){ q=p; p=p->next; free(q); } return OK; } //队列是否空 Status QueueEmpty(LinkQueue Q){ if(Q.front == Q.rear) return TRUE; else return FALSE; } //取队列长度 int QueueLength(LinkQueue Q){ int i=0; QueuePtr p = Q.front; while(Q.rear != p){ i++; p = p->next; } return i; } //获取队头元素 Status GetHead(LinkQueue Q,QElemType *e){ QueuePtr p; if(Q.front == Q.rear)//队空 return ERROR; p=Q.front->next; *e = p->data; return OK; } //对尾插入元素 Status EnQueue(LinkQueue *Q,QElemType e){ QueuePtr s = (QueuePtr)malloc(sizeof(QNode)); if(!s) exit(OVERFLOW); s->data = e; s->next =NULL; Q->rear->next =s;//原来对尾的next指向新的元素 Q->rear =s;//将新元素变为对尾 return OK; } //队头元素出队 Status DeQueue(LinkQueue *Q,QElemType *e){ QueuePtr p; if(Q->front == Q->rear) return ERROR; p=Q->front->next;//ｐ指向队头元素 *e = p->data; Q->front->next = p->next;//头结点的后继指向队头的下一个元素 if(Q->rear == p){//队头等于对尾了 Q->rear = Q->front;//对尾指向头结点 } free(p); return OK; } //遍历元素 Status QueueTraverse(LinkQueue Q){ QueuePtr p; p=Q.front->next; while(p){ visit(p->data); p=p->next; } printf("\n"); return OK; } int main(){ int i; QElemType d; LinkQueue q; i=InitQueue(&q); //入队１０个元素 for(int index=0;index |
今日新闻 |
点击排行 |
|
推荐新闻 |
图片新闻 |
|
专题文章 |
| CopyRight 2018-2019 实验室设备网 版权所有 win10的实时保护怎么永久关闭 |