2022年数据结构C语言版循环队列 3.pdf
/* 数据结构 C 语言版循环队列P64 编译环境： Dev-C+ 4.9.9.2 日期：2011 年 2 月 12 日*/ #include #include typedef int QElemType; / 队列的顺序存储结构(可用于循环队列和非循环队列) #define MAXQSIZE 5 / 最大队列长度(对于循环队列，最大队列长度要减1) typedef struct QElemType *base; / 初始化的动态分配存储空间，相当于一个数组头/ 头指针 ,若队列不空 ,指向队列头元素，相当于一个下标int front; / 尾指针 ,若队列不空 ,指向队列尾元素的下一个位置，相当于一个下标int rear; SqQueue;/ 空队列的标志是队头队尾指针都相同/ 构造一个空队列Q int InitQueue(SqQueue *Q) /给队头队尾指针分配空间，并置空(*Q).base=(QElemType *)malloc(MAXQSIZE*sizeof(QElemType); /这里的 Q.base相当于一个数组头if(!(*Q).base) / 存储分配失败exit(0); (*Q).front=(*Q).rear=0; /下标初始化为0 return 1; / 销毁队列Q,Q 不再存在int DestroyQueue(SqQueue *Q) if(*Q).base) free(*Q).base); (*Q).base=NULL; (*Q).front=(*Q).rear=0; /空队列的标志是队头队尾指针都相同，且为0 return 1; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 5 页 - - - - - - - - - / 将 Q 清为空队列int ClearQueue(SqQueue *Q) (*Q).front=(*Q).rear=0; /空队列的标志是队头队尾指针都相同，且为0 return 1; / 若队列 Q 为空队列 ,则返回 1,否则返回0 int QueueEmpty(SqQueue Q) if(Q.front=Q.rear) / 队列空的标志return 1; else return 0; / 返回 Q 的元素个数 ,即队列的长度int QueueLength(SqQueue Q) return(Q.rear-Q.front+MAXQSIZE)%MAXQSIZE; / 若队列不空 ,则用 e 返回 Q 的队头元素 ,并返回 1,否则返回0 int GetHead(SqQueue Q,QElemType *e) if(Q.front=Q.rear) / 队列空return 0; / *(Q.base+Q.front) 相当于 Q.baseQ.front, 即 Q.base是数/ 组头，表示第Q.front 个元素*e=*(Q.base+Q.front); return 1; / 插入元素e 为 Q 的新的队尾元素int EnQueue(SqQueue *Q,QElemType e) if(*Q).rear+1)%MAXQSIZE=(*Q).front) / 队列满return 0; (*Q).base(*Q).rear=e; (*Q).rear=(*Q).rear+1)%MAXQSIZE; return 1; / 若队列不空 ,则删除 Q 的队头元素 ,用 e 返回其值 ,并返回 1;否则返回0 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 5 页 - - - - - - - - - int DeQueue(SqQueue *Q,QElemType *e) if(*Q).front=(*Q).rear) / 队列空return 0; *e=(*Q).base(*Q).front; (*Q).front=(*Q).front+1)%MAXQSIZE; return 1; / 从队头到队尾依次对队列Q 中每个元素调用函数vi() int QueueTraverse(SqQueue Q,void(*vi)(QElemType) int i; i=Q.front; while(i != Q.rear) vi(*(Q.base+i); i=(i+1) % MAXQSIZE; printf(n); return 1; void visit(QElemType i) printf(%d ,i); int main() int j; int i=0,l; QElemType d; SqQueue Q; InitQueue(&Q); printf( 初始化队列后，队列空否？%u(1:空 0:否)n,QueueEmpty(Q); printf( 请输入整型队列元素(不超过 %d 个),-1 为提前结束符: ,MAXQSIZE-1); do scanf(%d,&d); if(d=-1) break; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 5 页 - - - - - - - - - i+; EnQueue(&Q,d); while(iMAXQSIZE-1); printf( 队列长度为 : %dn,QueueLength(Q); printf( 现在队列空否？%u(1:空 0:否)n,QueueEmpty(Q); printf( 连续 %d 次由队头删除元素,队尾插入元素 :n,MAXQSIZE); for(l=1;l0) printf( 现在由队头删除%d 个元素 :n,l-2); while(QueueLength(Q)2) DeQueue(&Q,&d); printf( 删除的元素值为%dn,d); j=GetHead(Q,&d); if(j) printf( 现在队头元素为: %dn,d); ClearQueue(&Q); printf( 清空队列后 , 队列空否？ %u(1:空 0:否)n,QueueEmpty(Q); DestroyQueue(&Q); system(pause); return 0; /* 输出效果：初始化队列后，队列空否？1(1:空 0:否) 请输入整型队列元素(不超过 4 个),-1 为提前结束符 : 1 2 3 -1 队列长度为 : 3 现在队列空否？0(1:空 0:否) 连续 5 次由队头删除元素,队尾插入元素 : 删除的元素是1,请输入待插入的元素: 4 删除的元素是2,请输入待插入的元素: 5 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 5 页 - - - - - - - - - 删除的元素是3,请输入待插入的元素: 6 删除的元素是4,请输入待插入的元素: 7 删除的元素是5,请输入待插入的元素: 8 现在队列中的元素为: 6 7 8 共向队尾插入了8 个元素现在由队头删除1 个元素 : 删除的元素值为6 现在队头元素为: 7 清空队列后 , 队列空否？ 1(1:空 0:否) 请按任意键继续. . . */ 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 5 页 - - - - - - - - -
