数据结构-实验队列的实现

1、贵州大学实验报告学院： 计信学院 专业： 网络工程 班级：091班姓名XXX学号XXXXXXXXX实验组5实验时间2011.12.02指导教师XXXXX成绩实验项目名称队列的实现 实验目的1掌握队列的思想及其存储实现。 2掌握队列的常见算法的程序实现。实验原理1. 根据实验内容编程，上机调试、得出正确的运行程序。2. 编译运行程序，观察运行情况和输出结果。3. 写出实验报告（包括源程序和运行结果）。实验内容1采用链式存储实现队列的初始化、入队、出队操作。 2采用顺序存储实现循环队列的初始化、入队、出队操作。 3在主函数中设计一个简单的菜单，分别测试上述算法。实验数据及其步骤链式存储队列：#in

2、clude#includeusing namespace std;typedef int ElemType;struct QueueElemType *queue;int front,rear,len;int Maxsize;void Initqueue(Queue &Q) cout队列初始化操作endl;Q.Maxsize=10;Q.queue=new ElemTypeQ.Maxsize;Q.front=Q.rear=0;void Enqueue(Queue &Q,ElemType item)if(Q.rear+1)%Q.Maxsize=Q.front)int k=sizeof(ElemTy

3、pe);Q.queue=(ElemType*)realloc(Q.queue,2*Q.Maxsize*k);if(Q.rear!=Q.Maxsize-1)for(int i=0;i=Q.rear;i+)Q.queuei+Q.Maxsize=Q.queuei;Q.rear+=Q.Maxsize;Q.Maxsize=2*Q.Maxsize;Q.rear=(Q.rear+1)%Q.Maxsize;Q.queueQ.rear=item;ElemType Outqueue(Queue &Q)if(Q.front=Q.rear)cout队列已空,无法删除!endl;exit(1);Q.front=(Q.f

4、ront+1)%Q.Maxsize;return Q.queueQ.front;struct LNodeElemType data;LNode *next;struct LinkQueueLNode *front;LNode *rear;void init(LinkQueue &HQ) cout链式队列初始化data=item;newptr-next=NULL;if(HQ.rear=NULL)HQ.front=HQ.rear=newptr;else HQ.rear=HQ.rear-next=newptr;ElemType outq(LinkQueue &HQ)if(HQ.front=NULL)

5、cout链队为空,无法删除data;LNode *p=HQ.front;HQ.front=p-next;if(HQ.front=NULL)HQ.rear=NULL;delete p;return temp;void main()ElemType x,y;int i;int a4=1,3,5,7;cout原始数组数据endl;for(i=0;i4;i+)coutai ;coutendl;Queue q1; cout操作一endl;Initqueue(q1);for(i=0;i4;i+)Enqueue(q1,ai);cout输入要进队列的元素:x; Enqueue(q1,x); cout出队操作e

6、ndl; for(i=0;i5;i+) coutOutqueue(q1) ; coutendl; LinkQueue q2; cout操作二endl; init(q2); for(i=0;i4;i+) enq(q2,ai); cout输入要进链队列的元素y; enq(q2,y); cout出链队操作endl; for(i=0;i5;i+) coutoutq(q2) ; coutendl;运行结果如下：顺序存储队列：#include#include#define OVERFLOW -1#define OK 1#define ERROR 0#define MAXSIZE 100typedef st

7、ructint *elem;/队列存储空间int front;int rear;SqQueue;/判断选择是否正确int menu_select()int sn;for(;)scanf(%d,&sn);if(sn6)printf(nt输入错误，请重新输入n);elsebreak;return sn;int InitQueue(SqQueue &Q)Q.elem=(int *)malloc(MAXSIZE*sizeof(int);if(!Q.elem)exit(OVERFLOW);Q.front=Q.rear=-1;for(int i=0;iMAXSIZE;i+)Q.elemi=-1;retur

8、n OK;int QueueLength(SqQueue Q)return (Q.rear-Q.front+MAXSIZE)%MAXSIZE;void Display(SqQueue Q)for(int i=0;i=QueueLength(Q);i+)if(Q.elemi!=-1)printf(%d ,Q.elemi);printf(n);int EnQueue(SqQueue &Q,int e)Q.rear=(Q.rear+1)%MAXSIZE;if(Q.rear=Q.front)return ERROR;Q.elemQ.rear=e;return OK;int DeQueue(SqQueu

9、e &Q,int &e)if(Q.front=Q.rear)return ERROR;e=Q.elemQ.front+1;Q.elemQ.front+1=-1;Q.front=(Q.front+1)%MAXSIZE;return OK;void main()SqQueue Q;InitQueue(Q);int elem,e;printf(请输入队列元素(以0结束):n);scanf(%d,&elem);while(elem!=0)EnQueue(Q,elem);scanf(%d,&elem);printf(队列为：n);Display(Q);printf(1.初始化一个队列;n2.入队;n3.

10、出队;n4.显示队列的所有元素;n5.队列长度:n6.结束;n);while(1)switch(menu_select()case 1:printf(请输入队列元素(以0结束):n);scanf(%d,&elem); while(elem!=0)EnQueue(Q,elem); scanf(%d,&elem);printf(队列为：n);Display(Q);fflush(stdin);break; case 2:scanf(%d,&elem);EnQueue(Q,elem);printf(队列为：n);Display(Q);fflush(stdin);break;case 3:DeQueue(Q,elem);printf(队列为：n);Display(Q);break;