队列的基本操作及其应用

1、广西工学院计算机学院数据结构课程实验报告书实验四 队列的基本操作及其应用 学生姓名：李四 学 号：2012 班级：计Y124 指导老师：王日凤 专 业：计算机学院软件学院提交日期：2013年6月20日1 实验目的1）通过对队列特点的分析，掌握队列的存储结构及其基本操作，学会定义队列的顺序存储结构和链式存储结构，在实际问题中灵活运用。2）掌握队列先进先出的特点，掌握队列的基本操作，如出队列、入队列、判队列空、判队列满等，熟悉各种操作的实现方法。3）通过具体的应用实例，进一步熟悉和掌握队列的实际应用。2.实验内容（1）建立一个含n个数据的队列，实现队列的基本操作。包括： /1. 初始化,构造一个空

2、队列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带回队头元素，并在队头删除，返回tru

3、e，队列空则返回false（流程图）bool popQueue (seqQueue &Q, elementType &x) /7. 输出队列,从队头到队尾依次输出void printQueue(seqQueue Q)（2）队列应用：利用队列操作打印杨辉三角形的 前n行（如n=7）。3实验要求（1） 上机前交实验源程序（纸质版），由学习委员统一收好交老师（附上不交同学名单）。（2） 用一切你能想到的办法解决遇到的问题，培养解决问题的能力。（3） 实验课上进行答辩。（4） 实验报告当场交。报告内容包括 ：实验目的、实验内容、实验代码、实验输入输出结果以及实验体会供五部分。3主要算法3.1 顺序存储

4、结构（1） 结构定义：#include#include #include#include /各个头文件#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);/初始化vo

5、id 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 Elempty

6、Queue(SqQueue &Q);/判空 /=函数声明=/构造空队列int InitQueue(SqQueue &Q)/操作结果：构造一个空队列Q printf(输入分配空间大小: ); scanf( %d,&N); Q.base=(QElemType *)malloc(N*sizeof(QElemType);/动态分配内存空间，以下同样if(!Q.base|NMAXQSIZE) /若n值不合理，则返回ERROR，以下同样 printf(构造失败!); printf(ntt按任意键返回主菜单!); getch(); return ERROR; Q.front=Q.rear=0;/队列设置为空

7、，以下同样printf(构造成功!); printf(ntt按任意键返回主菜单!); getch(); return OK; /初始化队列int InitQue(SqQueue &Q,int n) /操作结果:初始化一个空队列Q.base=(QElemType *)malloc(n*sizeof(QElemType); if(!Q.base|nMAXQSIZE) return ERROR; Q.front=Q.rear=0; return OK; /创建队列void creatQueue(SqQueue &Q,int n) /初始条件：Q已经存在/操作结果：向队列输入n个元素int m; if

8、(!Q.base|nN) printf(初始化未完成或超出队列长度，无法创建!); printf(ntt按任意键返回主菜单!); getch(); return; printf(请输入入队元素!n); for(int i=0;i0 )行if(nMAXQSIZE) printf(行数不合理，无法显示!); printf(ntt按任意键返回主菜单!); getch(); return ERROR; SqQueue Q;/定义新的循环队列 int k,e,p; for(int i=1;i=n;i+) printf( ); printf(1n);/在中心位置输出杨辉三角最顶端的1 InitQue(Q,

9、n+2);/设置最大容量为n+2 的空队列 EnQueu(Q,0);/添加行界值EnQueu(Q,1); EnQueu(Q,1);/第一行的值入队列 k=1; while(kn) /通过循环队列输出前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 else printf(n);/否则回车换行，为下一行输出做准备 EnQueu(

10、Q,p+e); while(e!=0); k+; e=DeQueu(Q);/行界值0出队列 while(!ElemptyQueue(Q) /单独处理第n 行的值的输出 e=DeQueu(Q); printf(%d ,e); printf(ntt显示成功!); printf(ntt按任意键返回主菜单!); getch(); return OK; /主函数void main() SqQueue Q;/定义队列变量int b,c,f;/定义整型数据变量int j,k;/设置选项变量while(1) system(cls);/清屏 printf(nt*); printf(nt* 队列的基本操作及其应用

11、 *); printf(nt*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(请选择选项: );/打印选项功能提示 scanf( %d,&k); if(k9) printf(输入有误，请重新输入!);printf(n);printf(nttt按任意键进行重新操作!); getch(); cont

12、inue; 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);

13、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);/输入行数+1 printf(杨辉三角显示为:n); yanghui(c-1);/调用杨辉三角函数 break; case 8: pr

14、intf(你真确定要销毁队列! 1.YES 2.NOn);printf(请选择项: );scanf(%d,&j);if(j=1) DestroyQueue(Q); printf(队列销毁成功呦!n);if(j=2) printf(n); printf(nttt按任意键进行重新操作!); getch(); break; case 9: printf(你真确定要清空队列! 1.YES 2.NOn);printf(请选择项: );scanf(%d,&j);if(j=1) ClearQueue(Q); printf(队列清空成功呦!n); else printf(n); printf(nttt按任意键进行重新操作!); getch(); break;case 0: printf(你真确定要退出! 1.YES 2.NOn); printf(请选择项: );scanf(%d,&j);if(j=1) printf(nttt再见，欢迎再次使用!nnttt); exit(OVERFLOW); else printf(n);