队列作业

一、队列的顺序表示和实现要求：编写一个程序实现顺序队列的各种基本运算，并在此基础上设计一个主程序，完成如下功能：（1）初始化队列（2）建立顺序队列（3）入队（4）出队（5）判断队列是否为空（6）取队头元素（7）遍历队列分析:队列的顺序存储结构称为顺序队列，顺序队列实际上是运算受限的顺序表。入队时，将新元素插入rear所指的位置，然后将rear加1。出队时，删去front所指的元素，然后将front加1并返回被删元素。顺序队列中的溢出现象：（1）下溢现象。当队列为空时，做出队运算产生的溢出现象。“下溢”是正常现象，常用作程序控制转移的条件。（2）真上溢现象。当队列满时，做进栈运算产生空间溢出的现象。“真上溢”是一种出错状态，应设法避免。（3）假上溢现象。由于入队和出队操作中，头尾指针只增加不减小，致使被删元素的空间永远无法重新利用。当队列中实际的元素个数远远小于向量空间的规模时，也可能由于尾指针已超越向量空间的上界而不能做入队操作。该现象称为假上溢现象。注意：（1）当头尾指针相等时，队列为空。（2）在非空队列里，队头指针始终指向队头元素，尾指针始终指向队尾元素的下一位置。二、队列的链式表示和实现要求:编写一个程序实现链队列的各种基本运算，并在此基础上设计一个主程序，完成如下功能：（1）初始化并建立链队列（2）入链队列（3）出链队列（4）遍历链队列分析:队列的链式存储结构简称为链队列。它是限制仅在表头删除和表尾插入的单链表。注意：（1）和链栈类似，无须考虑判队满的运算及上溢。（2）在出队算法中，一般只需修改队头指针。但当原队中只有一个结点时，该结点既是队头也是队尾，故删去此结点时亦需修改尾指针，且删去此结点后队列变空。（3）和单链表类似，为了简化边界条件的处理，在队头结点前可附加一个头结点。#includestdio.h#includemalloc.h#defineMAXNUM100#defineElemtypeint#defineTRUE1#defineFALSE0typedefstruct{Elemtypequeue[MAXNUM];intfront;intrear;}sqqueue;/*队列初始化*/intinitQueue(sqqueue*q){if(!q)returnFALSE;；returnTRUE;}/*入队*/intappend(sqqueue*q,Elemtypex){if(q-rear=MAXNUM-1)returnFALSE;；returnTRUE;}/*出队*/ElemtypeDelete(sqqueue*q){Elemtypex;；returnx;}/*判断队列是否为空*/intEmpty(sqqueue*q){；}/*取队头元素*/intgethead(sqqueue*q){；}/*遍历队列*/voiddisplay(sqqueue*q){ints;s=q-front;if(q-front==q-rear)printf(队列空!\n);else{printf(\n顺序队列依次为：);while(sq-rear){s=s+1;printf(%d-,q-queue[s]);}printf(\n);printf(顺序队列的队尾元素所在位置:rear=%d\n,q-rear);printf(顺序队列的队头元素所在位置:front=%d\n,q-front);}}/*建立顺序队列*/voidSetsqqueue(sqqueue*q){intn,i,m;printf(\n请输入将要入顺序队列的长度:);scanf(%d,&n);printf(\n请依次输入入顺序队列的元素值:\n);for(i=0;in;i++){；}}main(){sqqueue*head;intx,y,z,select;head=(sqqueue*)malloc(sizeof(sqqueue));do{printf(\n第一次使用请初始化！\n);printf(\n请选择操作(1--7):\n);printf(===================================\n);printf(1初始化\n);printf(2建立顺序队列\n);printf(3入队\n);printf(4出队\n);printf(5判断队列是否为空\n);printf(6取队头元素\n);printf(7遍历队列\n);printf(===================================\n);scanf(%d,&select);switch(select){case1:{initQueue(head);printf(已经初始化顺序队列！\n);break;}case2:{Setsqqueue(head);printf(\n已经建立队列！\n);display(head);break;}case3:{printf(请输入队的值:\n);scanf(%d,&x);append(head,x);display(head);break;}case4:{z=Delete(head);printf(\n队头元素%d已经出队！\n,z);display(head);break;}case5:{if(Empty(head))printf(队列空\n);elseprintf(队列非空\n);break;}case6:{y=gethead(head);printf(队头元素为:%d\n,y);break;}case7:{display(head);break;}}}while(select=7);}#includestdio.h#includestdlib.h#defineElemTypeinttypedefstructQnode{ElemTypedata;structQnode*next;}Qnodetype;typedefstruct{Qnodetype*front;Qnodetype*rear;}Lqueue;/*初始化并建立链队列*/voidcreat(Lqueue*q){Qnodetype*h;inti,n,x;printf(输入将建立链队列元素的个数：n=);；；for(i=1;i=n;i++){printf(链队列第%d个元素的值为：,i);scanf(%d,&x);Lappend(q,x);}}/*入链队列*/voidLappend(Lqueue*q,intx){Qnodetype*s;；}/*出链队列*/ElemTypeLdelete(Lqueue*q){Qnodetype*p;ElemTypex;if(q-front==q-rear){printf(队列为空!\n);x=0;}else{；}return(x);}/*遍历链队列*/voiddisplay(Lqueue*q){Qnodetype*p;p=q-front-next;/*指向第一个数据元素节点*/printf(\n链队列元素依次为：);while(p!=NULL){；}printf(\n\n遍历链队列结束！\n);}main(){Lqueue*p;intx,cord;printf(\n*****第一次操作请选择初始化并建立链队列！*****\n);do{printf(\n链队列的基本操作\n);printf(=========================================\n);printf(主菜单\n);printf(=========================================\n);printf(1初始化并建立链队列\n);printf(2入链队列\n);printf(3出链队列\n);printf(4遍历链队列\n);printf(5结束程序运行\n);printf(==========================================\n);scanf(%d,&cord);switch(cord){case1:{p=(Lqueue*)malloc(sizeof(Lqueue));creat(p);display(p);}break;case2:{printf(请输入队列元素的值：x=);scanf(%d,&x);Lappend(p,x);display(p);}break;case3:{printf(出链队列元素：x=%d\n,Ldelete(p));display(p);}break;case4:{display(p);}break;case5:{exit(0);}}}while(cord=5);}