队列的基本操作.doc

_ 精品资料 实验实验三三 队队列的操作及列的操作及应应用用 实验学时：2 实验类型：（设计型） 一、一、实验实验目的目的 1. 理解并掌握队列的逻辑结构和顺序存储结构，了解循环队列的特点； 2. 掌握循环队列中基本操作的相关算法； 3. 编程实现相关算法； 4. 学会利用循环队列解决实际问题。 二、二、实验实验条件条件 Visual C+。 三、三、实验实验原理及相关知原理及相关知识识 1. 循环队列存储结构描述 #define MAXSIZE 100/最大队列长度 typedef struct QElemType *base;/存储空间基址 int front;/头指针 int rear;/尾指针 SqQueue; 2. 基本操作的算法描述 设下标为 index，队列长度为 m，则下一个下标的累进循环计算公式为： index_next = ( index+1 ) % m。 实验中涉及的三个关键操作时循环队列中求队列长度、入队和出队操作。 _ 精品资料 (1) 求长度 所谓求队列长度，即技术队列中元素的个数。 算法思想：根据循环队列的结构特征，可以用公式（Q.rear-Q.front+ MAXSIZE）%MAXSIZE 直接计算出队列的长度。 算法描述 Status QueueLength(SqQueue Q) return ( ( Q.rear-Q.front+ MAXSIZE) %MAXSIZE); /QueueLength (2) 入队 入队运算实际上相当于顺序表中的插入运算，所不同的是这里只能在队尾 插入元素。 算法思想： 将元素 e 插入循环队列中队尾元素的下一个存储空间 修改队尾指针，根据循环累计公式计算出其新位置 算法描述 Status EnQueue(SqQueue /队列满 Q.baseQ.rear = e; Q.rear = ( Q.rear + 1 ) % MAXSIZE; return OK; / EnQueue (3) 出队 出队运算实际上相当于顺序表中的删除运算，所不同的是这里只能在队头 删除元素。 _ 精品资料 算法思想：修改队头指针，根据循环累计公式计算出其新位置 算法描述 Status DeQueue(SqQueue /队列为空 e = Q.baseQ.front; Q.front = ( Q.front + 1 ) % MAXSIZE; return OK; / DeQueue 四、四、实验实验步步骤骤 1. 使用 C 语言实现循环队列的初始化、计算长度、入队、出队和遍历算法 2. 用顺序存储方式构造一个循环队列 Q，并输出构造好的队列和该队列的长 度 3. 在第 1 步所构造的队列 Q 中将元素 e 入队，并将更新后的队列 Q 输出 4. 在第 2 步更新后所得到的队列 Q 中将队头元素出队，用变量 e 返回该元素， 并将更新后的队列 Q 输出 五、思考五、思考题题及其它及其它 1. 使用循环队列实现输出杨辉三角的前 N 行 2. 如何使用循环队列解决“猴子选大王“问题 【参考程序】 #include stdio.h #include malloc.h #define OK 1 #define ERROR 0 #define MAXQSIZE 10 /*最大队列长度+1*/ typedef int QElemType; _ 精品资料 typedef struct QElemType *base; int front; int rear; SqQueue; int InitQueue(SqQueue *Q) Q-base=(QElemType *)malloc(MAXQSIZE*sizeof(QElemType); if(!Q-base) return ERROR; Q-front = Q-rear = 0; return OK; int EnQueue(SqQueue *Q,QElemType e) if( (Q-rear+1)%MAXQSIZE = Q-front ) / 队列满 return ERROR; return OK; int DeQueue(SqQueue *Q, QElemType *e) if(Q-front = Q-rear) / 队列空 return ERROR; return OK; int QueueLength(SqQueue Q) return (Q.rear-Q.front+MAXQSIZE)%MAXQSIZE; void QueueTraverse(SqQueue Q) /*从队头到队尾依次打印队列 Q 中每个元素*/ void main() int n,e,i; SqQueue q; /初始化循环队列 _ 精品资料 printf(“该循环队列最多可存放%d 个元素n”,MAXQSIZE-1); printf(“请输入数据元素的个数 n n”); scanf(%d, printf(“n 请输入%d 个整数n”,n); /*创建队列*/ for(i=1;i=n;i+) scanf(%d, /入队 printf(“q=”); /输出循环队列 q 的内容 fflush(stdin);/刷新缓冲区 printf(“n 请输入入队元素 en”); scanf(%d, /入队 printf(“q=”); /输出循环队列 q 的内容 fflush(stdin);/刷新缓冲区 printf(n 执行出队操作n); /出队 pri