队列的基本操作.doc

1 实验三实验三 队列的操作及应用队列的操作及应用 实验学时 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 2 return Q rear Q front MAXSIZE MAXSIZE QueueLength 2 入队 入队运算实际上相当于顺序表中的插入运算 所不同的是这里只能在队尾 插入元素 算法思想 将元素 e 插入循环队列中队尾元素的下一个存储空间 修改队尾指针 根据循环累计公式计算出其新位置 算法描述 Status EnQueue SqQueue 队列满 Q base Q rear e Q rear Q rear 1 MAXSIZE return OK EnQueue 3 出队 出队运算实际上相当于顺序表中的删除运算 所不同的是这里只能在队头 删除元素 算法思想 修改队头指针 根据循环累计公式计算出其新位置 算法描述 Status DeQueue SqQueue 队列为空 e Q base Q front Q front Q front 1 MAXSIZE return OK DeQueue 3 四 实验步骤四 实验步骤 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 4 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 请输入入队元素 e n scanf d 入队 printf q 输出循环队列 q 的内容 fflush stdin 刷新缓冲区 5 printf n 执行出队操作 n 出队 printf 出队元素是 d