贵州大学实验报告学院：计信学院专业：网络工程班级：091班姓名XXX 学号XXXXXXXXX 实验组 5 实验时间2011.12.02 指导教师XXXXX 成绩实验项目名称队列的实现实验目的1．掌握队列的思想及其存储实现。

2．掌握队列的常见算法的程序实现。

实验原理1.根据实验内容编程，上机调试、得出正确的运行程序。

2. 编译运行程序，观察运行情况和输出结果。

3. 写出实验报告（包括源程序和运行结果）。

实验内容1．采用链式存储实现队列的初始化、入队、出队操作。

2．采用顺序存储实现循环队列的初始化、入队、出队操作。

3．在主函数中设计一个简单的菜单，分别测试上述算法。

实验数据及其步骤链式存储队列：#include<stdio.h>#include<iostream>using namespace std;typedef int ElemType;struct Queue{ElemType *queue;int front,rear,len;int Maxsize;};void Initqueue(Queue &Q){cout<<"队列初始化操作"<<endl;Q.Maxsize=10;Q.queue=new ElemType[Q.Maxsize];Q.front=Q.rear=0;}void Enqueue(Queue &Q,ElemType item){if((Q.rear+1)%Q.Maxsize==Q.front){int k=sizeof(ElemType);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.queue[i+Q.Maxsize]=Q.queue[i];Q.rear+=Q.Maxsize;}Q.Maxsize=2*Q.Maxsize;}Q.rear=(Q.rear+1)%Q.Maxsize;Q.queue[Q.rear]=item;}ElemType Outqueue(Queue &Q){if(Q.front==Q.rear){cout<<"队列已空,无法删除!"<<endl;exit(1);}Q.front=(Q.front+1)%Q.Maxsize;return Q.queue[Q.front];}struct LNode{ElemType data;LNode *next;};struct LinkQueue{LNode *front;LNode *rear;};void init(LinkQueue &HQ){cout<<"链式队列初始化"<<endl;HQ.front=HQ.rear=NULL;}void enq(LinkQueue &HQ,ElemType item) {LNode *newptr=new LNode;newptr->data=item;newptr->next=NULL;if(HQ.rear==NULL)HQ.front=HQ.rear=newptr;elseHQ.rear=HQ.rear->next=newptr;}ElemType outq(LinkQueue &HQ){if(HQ.front==NULL){cout<<"链队为空,无法删除"<<endl;exit(1);}ElemType temp=HQ.front->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 a[4]={1,3,5,7};cout<<"原始数组数据"<<endl;for(i=0;i<4;i++)cout<<a[i]<<" ";cout<<endl;Queue q1;cout<<"操作一"<<endl;Initqueue(q1);for(i=0;i<4;i++)Enqueue(q1,a[i]);cout<<"输入要进队列的元素:"<<endl;cin>>x;Enqueue(q1,x);cout<<"出队操作"<<endl;for(i=0;i<5;i++)cout<<Outqueue(q1)<<" ";cout<<endl;LinkQueue q2;cout<<"操作二"<<endl;init(q2);for(i=0;i<4;i++)enq(q2,a[i]);cout<<"输入要进链队列的元素"<<endl;cin>>y;enq(q2,y);cout<<"出链队操作"<<endl;for(i=0;i<5;i++)cout<<outq(q2)<<" ";cout<<endl;}运行结果如下：顺序存储队列：#include<stdlib.h>#include<stdio.h>#define OVERFLOW -1#define OK 1#define ERROR 0#define MAXSIZE 100typedef struct{int *elem;//队列存储空间int front;int rear;}SqQueue;//判断选择是否正确int menu_select(){int sn;for(;;){scanf("%d",&sn);if(sn<1||sn>6)printf("\n\t输入错误，请重新输入\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;i<MAXSIZE;i++)Q.elem[i]=-1;return 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.elem[i]!=-1)printf("%d ",Q.elem[i]);printf("\n");}int EnQueue(SqQueue &Q,int e){Q.rear=(Q.rear+1)%MAXSIZE;if(Q.rear==Q.front)return ERROR;Q.elem[Q.rear]=e;return OK;}int DeQueue(SqQueue &Q,int &e){if(Q.front==Q.rear)return ERROR;e=Q.elem[Q.front+1];Q.elem[Q.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.出队;\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;case 4:printf("\n队列的所有元素:\n");Display(Q);break;case 5:printf("%d\n",QueueLength(Q));break;case 6:return;}}}实验总结1．了解了链式存储实现队列的初始化、入队、出队操作。

2．加深了关于顺序存储实现循环队列的初始化、入队、出队操作指导教师意见。