队列类模板.doc

封封 皮皮 按学校要求手工填写 按学校要求手工填写 成成 绩绩 评评 定定 表表 学生姓名崔丁昴班级学号1203060115 专 业通信工程课程设计题目 队列类模板的设计与 实现 评 语 组长签字 成绩 日期 20 年 月 日 课程设计任务书课程设计任务书 学 院信息科学与工程专 业通信工程 学生姓名崔丁昴班级学号 1203060115 课程设计题目队列类模板的设计与实现 实践教学要求与任务实践教学要求与任务 进行队列类模板的设计并实现 队列采用循环队列实现 数据元素可以是 char int float 等多种数据类型 包括以下功能 1 实现初始化队列操作 建立一个空队列 2 实现清空队列操作 3 实现判断队列是否为空的操作 4 实现求队列长度的操作 5 实现返回队首元素的操作 6 实现入队操作 7 实现出队操作 8 实现队列的遍历操作 输出队列的每个元素 9 将上述功能作为类的成员函数实现 编写主函数测试上述功能 工作计划与进度安排工作计划与进度安排 第 17 周 分析题目 查阅课题相关资料 进行类设计 算法设计 第 18 周 程序的设计 调试与实现 第 19 周 程序测试与分析 撰写课程设计报告 进行答辩验收 指导教师 201 年 月 日 专业负责人 201 年 月 日 学院教学副院长 201 年 月 日 摘 要 很多自然科学和工程技术中的问题的解决最终都归结到队列问题的处理 模板是 处理问题很经典的方法 由它改进 变形得到的类模板 是一种效率很高 较为常用 的方法 本文采用 C 语言实现了对队列的各个操作 设计了队列类 采用 Visual C 6 0 的控制台工程和 MFC 工程分别实现了对队列的处理 关键词 队列 类模板 控制台工程 MFC 工程 目 录 1 需求分析 1 2 算法基本原理 1 3 类设计 2 4 基于控制台的应用程序 2 4 1 类的初始定义 2 4 2 类的实现 3 4 3 主函数设计 5 4 4 基于控制台的应用程序测试 6 5 基于 MFC 的应用程序 8 5 1 基于 MFC 的应用程序设计 8 5 1 1 MFC 程序界面设计 8 5 1 2 MFC 程序代码设计 9 5 2 基于 MFC 的应用程序测试 11 结 论 14 参考文献 15 1 1 1 需求分析需求分析 1 应用类模板可以使类中的数据成员 成员函数的参数及成员函数的返回 值能根据模板参数匹配情况取任意数据类型 这种类型既可以是 C 预定义的 数据类型 也可以是用户自定义的数据类型 2 队列在程序设计中也经常出现 一个最典型的例子就是操作系统中的作 业排队 在允许多道程序运行的计算机系统中 同时有几个作业运行 如果运 行的结果都需要通过通道输出 那就要按请求输出的先后次序排队 每当通道 传输完毕可以接受新的输出任务时 队头的作业先从队列中退出作输出操作 凡是申请输出的作业都从队尾进入队列 2 2 算法基本原理算法基本原理 1 初始化一个循环队列 和顺序栈相类似 在队列的顺序存储结构中 除 了用一组地址连续的存储单元依次存放从队列头到队列尾的元素之外 尚需附 设两个指针 front 和 rear 分别指示队列头元素及队列尾元素的位置 2 实现清空队列操作 直接让类 Queue 中的 private 成员全部清零 从而 实现队列的清空 3 实现判断队列是否为空的操作 如果该队列中成员 count 为零的话 便 直接输出该队列为空 4 实现求队列长度的操作 直接输出当前情况下的成员 count 的值 5 实现返回队首元素的操作 由于存在 front 直接指向着对首 所以直接 输出该队首元素即 q front 6 实现入队操作 在 count 的情况下 让输入的值赋于 q rear 即实 现了在队尾插入的功能 7 实现出队操作 在 count 的情况下 让 q front q front 1 即实现 了在队首删除的功能 8 实现队列的遍历操作 输出队列的每个元素 利用 for 循环直接输出 q 数 组中所有的元素 2 3 3 类设计类设计 1 对于基类 Queue 来讲 内部有私有成员和公有成员 私有成员包括了 描述一个队列必须的对首 front 队尾 rear 即队总数 count 另外还 有用于存放队列数据的一个数组 qlist MaxQSize 公有成员则包括了各个函 数 Queue void 为构造函数 QDelete 为实现队列的删除的函数 QInsert 为实现队列的插入的函数 ClearQueue 为实现队列的清空的函数 QLength 为计算求出队列的长度的函数 QFront 为找到队列的队首元素的函数 QEmpty 为判断队列是否为空的函数 PrintQueue 输出队列的函数 2 对于模板类来讲 即 template 由于要求的是可以执行 int char float 三种类型的数据 所以我们在主函数中定义了三个成员 Queue s Queue z Queue y 用于分别调用这三种类型 进行操作处理 4 4 基于控制台的应用程序基于控制台的应用程序 整个程序分为三个大部分 第一个部分即为对类 Queue 的定义 第二个部 分则是对类 Queue 中的各个成员函数进行定义 第三个部分即为主函数 主函 数中分别定义了 int 型 float 型 char 型的队列类型用于程序的选择及处理 4 14 1 类的初始定义类的初始定义 include include using namespace std const int MaxQSize 20 template 模板声明 class Queue 类 Queue 的声明 private int count int front int rear 类 Queue 私有成员声明 T qlist MaxQSize public Queue void 构造函数 void QDelete 实现队列的删除 void QInsert 实现队列的插入 void ClearQueue 实现队列的清空 void QLength 计算求出队列的长度 void QFront 找到队列的队首元素 3 void QEmpty 判断队列是否为空 void PrintQueue 输出这个队列 4 24 2 类的实现类的实现 template Queue Queue void front 0 rear 0 count 0 初 始化 template void Queue QDelete 删除 T temp if count 0 cout 这是个空的队列 endl exit 1 temp qlist front count front front 1 MaxQSize template void Queue QInsert 插入 char a T item if count MaxQSize cout 这是个满的队列 endl exit 1 while 1 cout a if a Y a y cout 输入队列的数据 item count qlist rear item rear rear 1 MaxQSize else break 4 template void Queue QLength 长度 cout 该队列长度为 count endl template void Queue QFront 队首 cout 该队列队首元素为 qlist front endl template void Queue ClearQueue 清空 count 0 front 0 rear 0 template void Queue QEmpty 判断 if count 0 cout 该队列为空 endl else cout 该队列不为空 endl template void Queue PrintQueue 输出 int i for i 0 i count i cout qlist i cout endl int IfContinue 判断是否继续执行函数的函 数 char i cout 继续执行函数请输入 Y y i 5 if i Y i y return 0 else exit 1 4 34 3 主函数的设计主函数的设计 include include using namespace std const int MaxQSize 20 void main int c d Queue s Queue z Queue y cout 这是个队列类模板的设计与实现的程序 endl cout 请选择要处理的队列的数据类型 endl 1 int 型 2 char 型 3 float 型 c switch c case 1 while 1 cout 1 初始化 2 删除 3 长度 4 队首元素 5 清空 6 判断 7 输出 d switch d case 1 s QInsert IfContinue break case 2 s QDelete IfContinue break case 3 s QLength IfContinue break case 4 s QFront IfContinue break case 5 s ClearQueue IfContinue break case 6 s QEmpty IfContinue break case 7 s PrintQueue IfContinue break default break break case 2 while 1 cout 1 初始化 2 删除 3 长度 4 队首元素 5 清空 6 判断 7 输出 d switch d case 1 z QInsert IfContinue break case 2 z QDelete IfContinue break case 3 z QLength IfContinue break case 4 z QFront IfContinue break case 5 z ClearQueue IfContinue break case 6 z QEmpty IfContinue break 6 case 7 z PrintQueue IfContinue break default break break case 3 while 1 cout 1 初始化 2 删除 3 长度 4 队首元素 5 清空 6 判断 7 输出 d switch d case 1 y QInsert IfContinue break case 2 y QDelete IfContinue break case 3 y QLength IfContinue break case 4 y QFront IfContinue break case 5 y ClearQueue IfContinue break case 6 y QEmpty IfContinue break case 7 y PrintQueue IfContinue break default break break default break 4 44 4 基于控制台的应用程序测试基于控制台的应用程序测试 对 int 型数据进行程序运行结果如图 1 所示 7 图 1 int 型数据运行结果 对 char 型数据进行程序运行结果如图 2 所示 图 2 char 型数据运行结果 8 对 float 型数据进行程序运行结果如图 3 所示 图 3 float 型数据运行结果 5 15 1 基于基于 MFCMFC 的应用程序设计的应用程序设计 5 1 15 1 1 MFCMFC 程序界面设计程序界面设计 首先在 VC 中建立 MFC AppWizard exe 工程 名称为队列 并在向导的 Step1 中选择 Dialog based 即建立基于对话框的应用程序 如下图 4 5 所示 图 4 建立 MFC AppWizard exe 工程 9 图 5 建立基于对话框的应用程序 将对话框资源中的默认对话框利用工具箱改造成如下界面 如图 6 所示 图 6 方程组求解程序界面设计 图 6 所示的界面中包含了 个 Static Text 控件 个 Button 控件 和 个 Edit Box 控件 控件的基本信息列表如下表 1 所示 表 1 控件基本信息 控件类别控件 ID控件 Caption说明 该队列为 Static TextIDC STATIC 输入插入的数据 IDC BUTTON Read 读入数据 ButtonIDC BUTTON Del删除数据 10 IDC BUTTON Empty 清空数据 IDC BUTTON Insert 进行插入 IDC EDIT A00 IDC EDIT A10 队列的 10 个元素 Edit Box IDC EDIT b0 用于插入的元素 5 1 25 1 2 MFCMFC 程序代码设计程序代码设计 为了能够将对话框界面上的控件能够与代码联系起来 需要为 11 个 Edit Box 控件建立 Member Variables 按 Ctrl w 键进入 MFC ClassWizard 界 面 选择 Member Variables 选项卡 可显示成员变量设置界面 通过该界面设置与 11 个 Edit Box 控件对应的成员变量 具体如表 2 所 示 表 2 控件基本信息 控件 ID成员变量类型成员变量名称 IDC EDIT A00 IDC EDIT A10intdl 1 dl 10 IDC EDIT b0intcr 1 下面是编写代码的重要阶段 可以借鉴在设计基于 DOS 界面的控制台应 用程序的代码 并将其作必要的改写 具体改写的步骤与内容如下 1 编写读入数据按钮的消息处理函数 实现将队列的数据刷新到界面上 具体代码如下 void CMyDlg OnInputNum TODO Add your control notification handler code here UpdateData true dl 1 7 dl 2 11 dl 3 12 dl 4 15 dl 5 22 dl 6 29 dl 7 35 dl 8 42 UpdateData false 2 编写删除数据的消息处理函数 实现数据删除 具体代码如下 void CMyDlg OnDeleteNum TODO Add your control notification handler code here UpdateData true if dl 1 0 dl 1 0 else if dl 2 0 dl 2 0 else if dl 3 0 dl 3 0 else if dl 4 0 dl 4 0 else if dl 5 0 dl 5 0 else if dl 6 0 dl 6 0 UpdateData false 11 3 编写插入数据的消息处理函数 实现数据插入 具体代码如下 void CMyDlg OnInsertNum TODO Add your control notification handler code here UpdateData true if dl 5 0 dl 5 cr 1 else if dl 6 0 dl 6 cr 1 else if dl 7 0 dl 7 cr 1 else if dl 8 0 dl 8 cr 1 else if dl 9 0 dl 9 cr 1 else if dl 10 0 dl 10 cr 1 UpdateData false 4 编写清空数据的消息处理函数 实现数据清空 具体代码如下 void CMyDlg OnEmptyNum TODO Add your control notification handler code here UpdateData true dl 1 0 dl 10 0 cr 1 0 dl 2 0 dl 3 0 dl 4 0 dl 5 0 dl 6 0 dl 7 0 dl 8 0 dl 9 0 UpdateData false 5 1 35 1 3 基于基于 MFCMFC 的应用程序测试的应用程序测试 运行程序后 首先出现的界面如图 8 所示 图 8 程序初始运行界面 单击读入数据按钮后 可将队列的数据