广西工学院计算机学院《数据结构》课程实验报告书实验四队列的基本操作及其应用学生姓名：李四学号：2012班级：计Y124指导老师：王日凤专业：计算机学院软件学院提交日期：2013年6月20日1．实验目的1）通过对队列特点的分析，掌握队列的存储结构及其基本操作，学会定义队列的顺序存储结构和链式存储结构，在实际问题中灵活运用。
2）掌握队列先进先出的特点，掌握队列的基本操作，如出队列、入队列、判队列空、判队列满等，熟悉各种操作的实现方法。
3）通过具体的应用实例，进一步熟悉和掌握队列的实际应用。
2.实验内容（1）建立一个含n个数据的队列，实现队列的基本操作。
包括：▪//1. 初始化,构造一个空队列void initQueue(Queue &Q)▪//2. 判断队列空, 空则返回truebool QueueEmpty(seqQueue &Q)▪//3. 判断队列满, 满则返回truebool QueueFull(seqQueue &Q)▪//4. 取队头元素, 用x返回队头元素，返回true；空队列则返回falseBool QueueHead(seqQueue &Q, elementType &x)▪//5. 入队列，在队尾插入新元素x （流程图）bool pushQueue (seqQueue &Q, elementType x)▪//6. 出队列，用x带回队头元素，并在队头删除，返回true，队列空则返回false（流程图）bool popQueue (seqQueue &Q, elementType &x)▪//7. 输出队列,从队头到队尾依次输出void printQueue(seqQueue Q)（2）队列应用：利用队列操作打印杨辉三角形的前n行（如n=7）。
3．实验要求（1）上机前交实验源程序（纸质版），由学习委员统一收好交老师（附上不交同学名单）。
（2）用一切你能想到的办法解决遇到的问题，培养解决问题的能力。
（3）实验课上进行答辩。
（4）实验报告当场交。
报告内容包括：实验目的、实验内容、实验代码、实验输入输出结果以及实验体会供五部分。
3．主要算法3.1 顺序存储结构（1）结构定义：#include<stdio.h>#include<stdlib.h>#include<malloc.h>#include<conio.h>//各个头文件#define OK 1#define ERROR 0#define OVERFLOW -2//定义宏参#define MAXQSIZE 100//最大队列长度typedef int QElemType;//引用整型数据类型别名//顺序表的储存结构typedef struct{QElemType *base;//初始化的动态分配内存空间int front;//头指针int rear;//尾指针}SqQueue;int N;//======================函数声明=========================// int InitQueue(SqQueue &Q);//初始化void creatQueue(SqQueue &Q,int n);//创建int QueueLength(SqQueue &Q);//求长度void EnQueue(SqQueue &Q,QElemType e);//入队int DeQueue(SqQueue &Q);//出队int QueueTraverse(SqQueue &Q);//显示队列int GetHead(SqQueue Q);//取头元素int DestroyQueue(SqQueue &Q);//销毁顺序表int ClearQueue(SqQueue &Q);//清空顺序表int yanghui(int n);//杨辉三角int ElemptyQueue(SqQueue &Q);//判空//======================函数声明=========================////构造空队列int InitQueue(SqQueue &Q){//操作结果：构造一个空队列Qprintf("输入分配空间大小: ");scanf(" %d",&N);Q.base=(QElemType *)malloc(N*sizeof(QElemType));//动态分配内存空间，以下同样if(!Q.base||N<0||N>MAXQSIZE){ //若n值不合理，则返回ERROR，以下同样printf("构造失败!");printf("\n\t\t按任意键返回主菜单!");getch();return ERROR;}Q.front=Q.rear=0;//队列设置为空，以下同样printf("构造成功!");printf("\n\t\t按任意键返回主菜单!");getch();return OK;}//初始化队列int InitQue(SqQueue &Q,int n){ //操作结果:初始化一个空队列Q.base=(QElemType *)malloc(n*sizeof(QElemType));if(!Q.base||n<0||n>MAXQSIZE)return ERROR;Q.front=Q.rear=0;return OK;}//创建队列void creatQueue(SqQueue &Q,int n){ //初始条件：Q已经存在//操作结果：向队列输入n个元素int m;if(!Q.base||n<0||n>N){printf("初始化未完成或超出队列长度，无法创建!");printf("\n\t\t按任意键返回主菜单!");getch();return;}printf("请输入入队元素!\n");for(int i=0;i<n;i++)//将元素逐个从队列尾部插入{printf("请输入第%d个数据：",i+1);scanf(" %d",&m);Q.rear=i;Q.base[Q.rear]=m;}Q.rear=(Q.rear+1)%N;//尾指针后移一位printf("创建成功!\n");QueueTraverse(Q);//调用显示函数printf("\n\t\t按任意键返回主菜单!");getch();return;}//求队列的长度int QueueLength(SqQueue &Q){ //初始条件：Q已经存在//操作结果：返回队列的长度QueueTraverse(Q);//调用显示函数printf("\nThe Queue length is: %d",(Q.rear-Q.front+N)%N);//打印表长printf("\n\n");printf("\n\t\t按任意键返回主菜单!");getch();return OK;}//入队列void EnQueue(SqQueue &Q,QElemType e){ //初始条件：Q已经存在//操作结果：插入元素e为Q的新的队尾元素if((Q.rear+1) % N==Q.front) //队列为满的情况{printf("队列已满,无法插入!");printf("\n\t\t按任意键返回主菜单!");getch();return;}Q.base[Q.rear]=e;Q.rear=(Q.rear+1) % N; //尾指针后移一位printf("入队成功!\n");QueueTraverse(Q);//调用显示函数printf("\n\t\t按任意键返回主菜单!");getch();return;}//入队列void EnQueu(SqQueue &Q,QElemType e){ //初始条件：Q已经存在//操作结果：插入元素e为Q的新的队尾元素if((Q.rear+1)%MAXQSIZE==Q.front)return;Q.base[Q.rear]=e;Q.rear=(Q.rear+1) % MAXQSIZE;}//出队列int DeQueue(SqQueue &Q){ //初始条件：Q已经存在//操作结果：若队列不空，删除Q的队头元素，//用e返回其值，并返回，否则返回int e;if(Q.front==Q.rear) //队列为空的情况{printf("队列为空，无法出队!");printf("\n\t\t按任意键返回主菜单!");getch();return ERROR;}e=Q.base[Q.front];Q.front=(Q.front+1) % N;//头指针后移一位printf("队头元素出队成功!\n");printf("这队头元素是：%d",e);printf("\n\t\t按任意键返回主菜单!");getch();return OK;}//出队列int DeQueu(SqQueue &Q){ //初始条件：Q已经存在//操作结果：若队列不空，删除Q的队头元素，//用e返回其值，并返回，否则返回int e;if(Q.front==Q.rear) //队列为空的情况return ERROR;e=Q.base[Q.front]; //将头元素赋给eQ.front=(Q.front+1) % MAXQSIZE;//头指针后移一位return e;}//显示int QueueTraverse(SqQueue &Q){ //初始条件：Q已经存在//操作结果：把队列中的元素输出到显示屏int i;i=Q.front;if(Q.front==Q.rear) //队列为空的情况{printf("The Queue is Empty!");printf("\n\t\t按任意键返回主菜单!");getch();return ERROR;}else{printf("The Queue is:");while(i!=Q.rear) //当队列不为空时{printf("%3d",Q.base[i]);i=(i+1)%N;}}printf("\n");printf("显示成功!");return OK;}//取队头元素int GetHead(SqQueue Q){ //初始条件：Q已经存在//操作结果：若队列不空，返回其值，否则返回int e;if(Q.front==Q.rear) //队列为空的情况{printf("The Queue is Empty!");printf("\n\t\t按任意键返回主菜单!");getch();return ERROR;}e=*(Q.base+Q.front);//将头元素赋给ereturn e;}//判断顺序表是否为空int ElemptyQueue(SqQueue &Q){ //初始条件：Q已经存在//操作结果：若队列为空返回，否则返回if(Q.front==Q.rear)//队列为空的情况return OK;elsereturn ERROR;}//销毁链表int DestroyQueue(SqQueue &Q){//初始条件:顺序表已存在//操作结果:销毁顺序表Q.front=Q.rear=0;return OK;}//清空队列int ClearQueue(SqQueue &Q){//初始条件:顺序表已存在//操作结果:清空顺序表Q.front=Q.rear=0;return OK;}//杨辉三角int yanghui(int n){ //打印输出杨辉三角的前n( n>0 )行if(n<0||n>MAXQSIZE){printf("行数不合理，无法显示!");printf("\n\t\t按任意键返回主菜单!");getch();return ERROR;}SqQueue Q;//定义新的循环队列int k,e,p;for(int i=1;i<=n;i++)printf(" ");printf("1\n");//在中心位置输出杨辉三角最顶端的"1"InitQue(Q,n+2);//设置最大容量为n+2 的空队列EnQueu(Q,0);//添加行界值EnQueu(Q,1);EnQueu(Q,1);//第一行的值入队列k=1;while(k<n){ //通过循环队列输出前n-1 行的值for(int i=1;i<=n-k;i++)printf(" ");//输出n-k个空格以保持三角型EnQueu(Q,0);//行界值"0"入队列do//输出第k 行，计算第k+1 行{p=DeQueu(Q);e=GetHead(Q);if(e)printf("%d ",e);//若e为非行界值，则打印输出e elseprintf("\n");//否则回车换行，为下一行输出做准备EnQueu(Q,p+e);}while(e!=0);k++;}e=DeQueu(Q);//行界值"0"出队列while(!ElemptyQueue(Q)){//单独处理第n 行的值的输出e=DeQueu(Q);printf("%d ",e);}printf("\n\t\t显示成功!");printf("\n\t\t按任意键返回主菜单!");getch();return OK;}//主函数void main(){SqQueue Q;//定义队列变量int b,c,f;//定义整型数据变量int j,k;//设置选项变量while(1){system("cls");//清屏printf("\n\t***************************************************"); printf("\n\t* 队列的基本操作及其应用 *");printf("\n\t***************************************************\n");printf("\t * 1.初始化队列 2.创建队列 *\n");printf("\t * 3.队列长度 4.入队队列 * \n");printf("\t * 5.取头元素 6.显示队列 * \n");printf("\t * 7.杨辉三角 8.销毁队列 * \n");printf("\t * 9.清空队列 0.退出 *\n");printf("\t****************************************************\n");printf("请选择选项<1-9>: ");//打印选项功能提示scanf(" %d",&k);if(k<0||k>9){printf("输入有误，请重新输入!");printf("\n");printf("\n\t\t\t按任意键进行重新操作!");getch();continue;}switch(k)//分支结构来调用各功能子函数{case 1:printf("创建空的循环队列\n");InitQueue(Q);//调用初始化函数printf("\n");break;//退出并重新进入主菜单case 2:printf("创建新的循环队列\n");printf("输入长度:");scanf("%d",&f);creatQueue(Q,f);//调用创建函数break;case 3:printf("求表长!\n");QueueLength(Q);//调用求表长函数break;case 4:printf("入队!\n");printf("输入入队元素: ");scanf("%d",&b);EnQueue(Q,b);//调用入队函数QueueTraverse(Q);//调用显示函数break;case 5:printf("出队!\n");DeQueue(Q);//调用出队函数break;case 6:printf("显示顺序表!\n");QueueTraverse(Q);//调用显示函数getch();break;case 7:system("cls");//清屏printf("杨辉三角!\n");printf("输入其行数: ");scanf(" %d",&c);//输入行数+1printf("杨辉三角显示为:\n");yanghui(c-1);//调用杨辉三角函数break;case 8:printf("你真确定要销毁队列! 1.YES 2.NO\n");printf("请选择项<1-2>: ");scanf("%d",&j);if(j==1)DestroyQueue(Q);printf("队列销毁成功呦!\n");if(j==2)printf("\n");printf("\n\t\t\t按任意键进行重新操作!");getch();break;case 9:printf("你真确定要清空队列! 1.YES 2.NO\n");printf("请选择项<1-2>: ");scanf("%d",&j);if(j==1){ClearQueue(Q);printf("队列清空成功呦!\n");}elseprintf("\n");printf("\n\t\t\t按任意键进行重新操作!");getch();break;case 0:printf("你真确定要退出! 1.YES 2.NO\n");printf("请选择项<1-2>: ");scanf("%d",&j);if(j==1){printf("\n\t\t\t再见，欢迎再次使用!\n\n\t\t\t");exit(OVERFLOW);}elseprintf("\n");printf("\n\t\t\t按任意键进行重新操作!");getch();break;}}}3.流程图如下1.队尾插入元素Q.front->Q.rear->1. 队尾插入元素2.删除队头元素4．程序运行结果（1）实验内容（1）运行结果如下：运行结果如下：运行结果如下：5.心得体会。