队列类模板.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.应用类模板可以使类中的数据成员、成员函数的参数及成员函数的返回值 能根据模板参数匹配情况取任意数据类型。这种类型既可以是 C+预定义的数 据类型，也可以是用户自定义的数据类型。 2.队列在程序设计中也经常出现。一个最典型的例子就是操作系统中的作业 排队。在允许多道程序运行的计算机系统中，同时有几个作业运行。如果运行的 结果都需要通过通道输出，那就要按请求输出的先后次序排队。每当通道传输完 毕可以接受新的输出任务时，队头的作业先从队列中退出作输出操作。凡是申请 输出的作业都从队尾进入队列。 2. 算法基本原理算法基本原理 1.初始化一个循环队列。和顺序栈相类似，在队列的顺序存储结构中，除了 用一组地址连续的存储单元依次存放从队列头到队列尾的元素之外，尚需附设 两个指针 front 和 rear 分别指示队列头元素及队列尾元素的位置。 2.实现清空队列操作。直接让类 Queue 中的 private 成员全部清零。从而实现 队列的清空。 3.实现判断队列是否为空的操作。如果该队列中成员 count 为零的话。便直 接输出该队列为空。 4.实现求队列长度的操作。直接输出当前情况下的成员 count 的值。 5. 实现返回队首元素的操作。由于存在 front 直接指向着对首。所以直接输 出该队首元素即 qfront。 6.实现入队操作。在 count+的情况下。让输入的值赋于 qrear+。即实现了 在队尾插入的功能。 7.实现出队操作。在 count-的情况下。让 qfront=qfront+1。即实现了在队 首删除的功能。 8.实现队列的遍历操作。输出队列的每个元素。利用 for 循环直接输出 q数 组中所有的元素。 _ 精品资料 3. 类设计类设计 1.对于基类 Queue 来讲。内部有私有成员和公有成员。私有成员包括了描 述一个队列必须的对首（front）、队尾（rear）、即队总数（count）。另外还有用于存 放队列数据的一个数组 qlistMaxQSize。公有成员则包括了各个函数。 Queue(void)为构造函数。QDelete()为实现队列的删除的函数。QInsert()为实现队 列的插入的函数。ClearQueue()为实现队列的清空的函数。QLength()为计算求出 队列的长度的函数。QFront()为找到队列的队首元素的函数。QEmpty()为判断队 列是否为空的函数。PrintQueue()输出队列的函数。 2.对于模板类来讲。即 template。由于要求的是可以执行 int、char、float 三种类型的数据。所以我们在主函数中定义了三个成员 Queue s、Queue z、 Queue y。用于分别调用这三种类型进行操作处理。 4.基于控制台的基于控制台的应应用程序用程序 整个程序分为三个大部分。第一个部分即为对类 Queue 的定义。第二个部分 则是对类 Queue 中的各个成员函数进行定义。第三个部分即为主函数，主函数中 分别定义了 int 型、float 型、char 型的队列类型用于程序的选择及处理。 4.1 类类的初始定的初始定义义 #include #include using namespace std; const int MaxQSize = 20; template /模板声明 class Queue /类 Queue 的声明 private: int count; int front; int rear; /类 Queue 私有成员声明 T qlistMaxQSize; public: Queue(void); /构造函数 void QDelete(); /实现队列的删除 void QInsert(); /实现队列的插入 void ClearQueue(); /实现队列的清空 void QLength(); /计算求出队列的长度 void QFront(); /找到队列的队首元素 void QEmpty(); /判断队列是否为空 void PrintQueue(); /输出这个队列 _ 精品资料 ; 4.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 = qlistfront; count-; front = (front+1) % MaxQSize; template void Queue :QInsert() /插入 char a; T item; if (count = MaxQSize) cout 这是个满的队列! endl; exit(1); while(1) couta; if(a=Y|a=y) cout输入队列的数据:item; count+; qlistrear = item; rear = (rear+1) % MaxQSize; else break; template _ 精品资料 void Queue :QLength() /长度 cout该队列长度为:countendl; template void Queue :QFront() / 队首 cout该队列队首元素为:qlistfrontendl; 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;icount;i+) coutqlisti ; coutendl; int IfContinue() /判断是否继续执行函数的函数 char i; cout继续执行函数请输入 Y/y:i; if(i=Y|i=y) return 0; else exit(1); 4.3 主函数的主函数的设计设计 _ 精品资料 #include #include using namespace std; const int MaxQSize = 20; void main() int c,d; Queue s; Queue z; Queue y; cout这是个队列类模板的设计与实现的程序endl; cout请选择要处理的队列的数据类型: 型 2.char 型 3.float 型c; switch(c) case 1: while(1) cout1.初始化 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) cout1.初始化 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; case 7:z.PrintQueue();IfContinue();break; default: break; break; _ 精品资料 case 3: while(1) cout1.初始化 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.4 基于控制台的基于控制台的应应用程序用程序测试测试 对 int 型数据进行程序运行结果如图 1 所示。 图 1 int 型数据运行结果 对 char 型数据进行程序运行结果如图 2 所示。 _ 精品资料 图 2 char 型数据运行结果 对 float 型数据进行程序运行结果如图 3 所示。 图 3 float 型数据运行结果 5.1 基于基于 MFC 的的应应用程序用程序设计设计 _ 精品资料 5.1.1 MFC 程序界面程序界面设计设计 首先在 VC 中建立 MFC AppWizard（exe）工程，名称为队列，并在向导的 Step1 中选择 Dialog based，即建立基于对话框的应用程序，如下图 45 所示。 图 4 建立 MFC AppWizard（exe）工程 图 5 建立基于对话框的应用程序 将对话框资源中的默认对话框利用工具箱改造成如下界面，如图 6 所示。 _ 精品资料 图 6 方程组求解程序界面设计 图 6 所示的界面中包含了个 Static Text 控件，个 Button 控件，和个 Edit Box 控件，控件的基本信息列表如下表 1 所示。 表 1 控件基本信息 控件类别控件 ID控件 Caption说明 该队列为：Static TextIDC_STATIC 输入插入的数据： IDC_BUTTON_Read读入数据 IDC_BUTTON_Del删除数据 IDC_BUTTON_Empt y 清空数据 Button IDC_BUTTON_Insert进行插入 IDC_EDIT_A00 IDC_EDIT_A10 队列的 10 个元 素 Edit Box IDC_EDIT_b0 用于插入的元素 5.1.2 MFC 程序代程序代码设计码设计 为了能够将对话框界面上的控件能够与代码联系起来，需要为 11 个 Edit Box 控件建立 Member Variables，按 Ctrl+w 键进入 MFC ClassWizard 界面，选择 Member Variables 选项卡，可显示成员变量设置界面。 通过该界面设置与 11 个 Edit Box 控件对应的成员变量，具体如表 2 所示。 表 2 控件基本信息 控件 ID成员变量类型成员变量名称 IDC_EDIT_A00IDC_EDIT_A 10 intdl_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); 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.3 基于基于 MFC 的的应应用程序用程序测试测试 运行程序后，首先出现的界面如图 8 所示。 图 8 程序初始运行界面 单击读入数据按钮后，可将队列的数据在界面上显示出来，如图 9 所示。 _ 精品资料 图 9 读入数