数据结构队列c++实现教学提纲

1、此文档仅供收集于网络，如有侵权请联系网站删除目录一、 题目内容及要求2二、 题目设计思路2三、 类设计与类关系3四、 主要功能函数流程图3五、 运行结果及分析4六、 总结5只供学习与交流此文档仅供收集于网络，如有侵权请联系网站删除一、题目内容及要求1. 队列是一种连续的存储结构，存入数据只能从一端（称为尾部）进入，取出数据则只能从另一端（头部）取出。根据下述描述实现一个自定义的队列类：template <typename Type>struct LinkNodeType data;LinkNode<Type> *next;LinkNode() : next(NULL)

2、LinkNode( const Type &x,LinkNode<Type> *p=NULL ) : data(x),next(p) ;template <typename Type>class Queuepublic:Queue ();/构造函数Queue ();/ 析构函数inline bool isEmpty () const;/队列是否为空inline void makeEmpty();/ 清空队列inline void enqueue( const Type &x );/ 插入一个元素inline void dequeue( Type &

3、;x );/ 弹出一个元素inline void getFront( Type &x);/得到对头元素private:LinkNode<Type> *front; / 指向头结点的指针 ,front->next->data 是队头的第一个元素 LinkNode<Type> *rear; / 指向队尾（最后添加的一个元素）的指针inline void handleUnderflow();/控制队列下溢;二、题目设计思路文件在 queue.h 头文件中使用命名空间itlab 在其中声明：（ 1）模板结构体链表结点（ struct LinkNode ），其

4、中包含的数据成员有：模板参数类类型 Type 对应的 data，存放模板实现类的具体数据， LinkNode<Type>模板类型结构体指针next，用来指向下一个结点；成员函数包括： LinkNode() 无参构造函数，其中数据成员next 默认为 NULL ， LinkNode(const Type&x,LinkNode<Type> *p = NULL)，采用参数初始化表对数据成员初始化，其中第一个参数为常量 Type 类型的引用x，初始化数据成员data，第二个参赛为结构体类型指针p 默认值为只供学习与交流此文档仅供收集于网络，如有侵权请联系网站删除NULL

5、 ，用来初始化数据成员next。（ 2）模板类队列（ class Queue），包含的公共成员函数有：无参构造函数 Queue()，在定义对象时，由系统调用，完成对象的初始化；析构函数 Queue()，与构造函数相反，是在撤销对象占用内存前进行一些清理工作。可以被用来执行“用户希望在最后一次使用对象之后所执行的任何操作”；内联函数判断队列是否为空，返回值为布尔类型常量，inline bool isEmpty() const;内联函数清空队列，无返回值，inline void makeEmpty();内联函数向队列中插入一个元素，inline void enqueue(const Type &a

6、mp;x) ，参数为 Type 类型常量，插入的新元素作为队列中的队尾结点；内联函数从队列中弹出一个元素，inline void dequeue( Type &x ) ，无返回值， 但传入参数为 Type 类型的引用x，从对首取出结点元素的数据，将其赋值给x，实现函数值的返回；内联函数得到对首元素结点的数据，inline void getFront( Type &x)，同样采用函数参数引用类型间接返回函数值；私有数据成员包括：指向模板结构体类型变量的头指针，LinkNode<Type> *front指向模板结构体类型变量的后继指针，LinkNode<Type&

7、gt; *rear内联函数控制队列下溢，inline void handleUnderflow()。（ 3）同时包含其实现文件 queue-impl.h ，#include "queue-impl.h" 。2.queue-impl.h 文件在 queue-impl.h 头文件，是实现 queue.h 头文件中声明的模板类 Queue，实现其声明的函数，完成函数的定义， 在预编译时， 会将头文件 queue-impl.h 中的内容取代头文件 queue.h 中的 #include "queue-impl.h" 这一行。在 queue_test.cpp 文件

8、中，包含主函数，声明结构体类型Student，是模板结构体链表（LinkNode<Type> ）的实现类，将其作为插入队列和弹出队列的基本元素，测试队列类Queue的主要成员函数：判断队列是否为空（isEmpty ）、向对列中插入一个元素（enqueue）、从队列中弹出一个元素（ dequeue）、得到队首元素的数据（ getFront）、私有成员函数控制队列下溢（ handleUnderflow ）。三、类设计与类关系1.类设计主要包含队列类 Queue。其私有数据成元是指向结构体类型变量（ struct Student）的头指针和指向结构体类型的后继指针。在 main 函数中声

9、明了结构体类型 Student，其主要包含整型的学号、字符串类型的学生姓名、字符串类型的系部名称，以及带默认参数的构造函数。2.类关系在 main 函数中，通过定义一个队列类类型的对象q（ Queue<Student> q），显示的将结构体类型（ Student 为结构体类型）传递给Queue<Type>对应的类参Type（模板参数类型） 。四、主要功能函数流程图1.向对列中插入一个元素函数（inline void enqueue(const Type &x)）流程图只供学习与交流此文档仅供收集于网络，如有侵权请联系网站删除2.从队列中弹出一个元素函数（inli

10、ne void dequeue( Type &x )）流程图五、运行结果及分析1.运行结果：只供学习与交流此文档仅供收集于网络，如有侵权请联系网站删除2.结果分析：（ 1）队列初始为空，依次将学生插入队列，并打印入队顺序；（ 2）此时调用 getFront(Type &x) 函数取得对头的元素；（ 3）出对时，按照先进先出原则，打印出队顺序。六、总结1.模板机制（ 1）模板的代码重用机制是基于 C 语言宏展开基础发展而来，宏展开的一套文本替换算法从预处理阶段搬移到编译阶段， 结合函数重载中的一套类型匹配搜寻算法一起就诞生了模版的内在运作机制。（ 2）函数模板和类模板提供了类型参

11、数化的通用机制。函数模板的类参在函数的调用点根据实参的类型反演出来，形成重载函数，同时实参的数值作为入口又进行函数调用。（ 3）类模板的类参一般由对象定义的方式显式给出，根据直接指定的类名或整型常数初始化模板类参形参表中的对应项目值，用这些具体的类名和常数替换模板中类参或形参，形成特定的类。这些工作是编译器自动宏替换复制完成的， 但比预处理的宏替换执行了更多的类型安全检查，而根据模板生成的代码具有明显的相近性质。（ 4）需要注意形参与类参的区别，形参是运行时压入堆栈传递给函数的数据值，而类参是在函数调用点获得的实参的静态数据类型， 数据类型是静态的， 该数据类型在编译阶段确定。（ 5）函数模板

12、产生的函数是一系列形参个数相同，形参数据类型不同的重载函数，类模板产生的类是类名不同，结构相近的类。（ 6）此外，类模板的不同实现是不同的类，此特定的类上的模板成员函数不同于彼模板类相应的成员函数版本。 其间通过类域分辨符进行了清晰的分界， 因此类模板提供一种类型安全的鉴别机制。2.队列数据结构（ 1）队列是一种采用先进先出（first in,first out FIFO ）策略的对元素操作的动态集合。（2）队列上的INSERT操作称为入队（ENQUEUE ），DELETE操作称为出队（DEQUEUE ）。（ 3）队列的先进先出特性类似于收银台前排队等待结账的一排顾客。队列有对头（ head）

13、和对尾（ tail ），当有一个元素入对时，它被放在队尾的位置，就像一个新到来的顾客排在队伍末端一样。 而出队的元素则总是在对头的那个，就像排在队伍前面等待最久的那个顾客一样。源代码：/*queue.h* A simple queue implemented by C+ template class.*/只供学习与交流此文档仅供收集于网络，如有侵权请联系网站删除#ifndef QUEUE_H#define QUEUE_H#include <iostream>#include<stdlib.h>#include<cstdlib>using namespace

14、std;namespace itlab/* Queue Node*/#define QUEUE_INIT_SIZE 100/队列初始化大小/#define QUEUE_INCREMENT 10/ 队列空间不够时一次申请大小template <typename Type>struct LinkNodeType data;LinkNode<Type> *next;LinkNode() : next(NULL) LinkNode( const Type &x,LinkNode<Type> *p=NULL ) : data(x),next(p) ;/* Qu

15、eue*/template <typename Type>class Queuepublic:Queue ();/构造函数Queue ();/析构函数/ Queue(const Queue<Type> &q);/ Queue & operator=(const Queue<Type> &q);inline bool isEmpty () const;/ 队列是否为空inline void makeEmpty();/清空队列只供学习与交流此文档仅供收集于网络，如有侵权请联系网站删除/inline bool isFull() const;

16、/ 队列是否已满/int size () const;/队列中元素的个数inline void enqueue( const Type &x );/ 插入一个元素inline void dequeue( Type &x );/弹出一个元素inline void getFront( Type &x);/得到对头元素private:LinkNode<Type>*front;/ 指向头结点的指针,front->next->data是队头的第一个元素LinkNode<Type> *rear; / 指向队尾（最后添加的一个元素）的指针inlin

17、e void handleUnderflow();#include "queue-impl.h"/namespace itlab#endif/ QUEUE_H/-/-/*queue-impl.h* Implementation for Queue class.*/* constructors and destructor */template <typename Type> Queue<Type>:Queue():front(NULL), rear(NULL)template <typename Type>Queue<Type>

18、;:Queue()只供学习与交流此文档仅供收集于网络，如有侵权请联系网站删除makeEmpty();/* If the queue empty, return true. */template <typename Type>inline bool Queue<Type>:isEmpty() constreturn front = NULL;/* Make the queue empty. */template <typename Type>inline void Queue<Type>:makeEmpty()LinkNode<Type>

19、; *p;while( front != NULL)p = front;front = front->next;delete p;/* Enter the element into the queue. */template <typename Type>inline void Queue<Type>:enqueue( const Type &x )if(front = NULL)front = rear = new LinkNode<Type>( x );if( !front )cerr << "Out of memor

20、y!" << endl;exit(1);else只供学习与交流此文档仅供收集于网络，如有侵权请联系网站删除rear->next = new LinkNode<Type>( x );if( !rear )cerr << "Out of memory!" << endl;exit(1);rear = rear->next;/* Pop an element from the queue.*/template <typename Type>inline void Queue<Type>:

21、dequeue( Type &x )if( !isEmpty() )LinkNode<Type> *p = front;x = front->data;front = front->next;delete p;elsehandleUnderflow();/* Get the front element of the queue. */template <typename Type>inline void Queue<Type>:getFront( Type &x )if( !isEmpty() )x = front->dat

22、a;elsehandleUnderflow();/* Handle the error of get element from am empty queue. */template <typename Type>只供学习与交流此文档仅供收集于网络，如有侵权请联系网站删除inline void Queue<Type>:handleUnderflow()cerr << "The queue is empty!" << endl << endl;exit(1);/-/-/*queue_test.cpp* Queue cl

23、ass testing.*/#include <iostream>#include <string>#include "queue.h"#include <stdlib.h>using namespace std;using namespace itlab;struct Student只供学习与交流此文档仅供收集于网络，如有侵权请联系网站删除intstuNum;string stuName;string department;Student ( int number = 0, const string &name = "

24、Tom&Jerry",const string &dpt = "Information" ): stuNum(number), stuName(name), department(dpt) ;int main(int argc, char* argv) Student stu;Queue<Student> q;Student students 3 = Student(11, "ZhangMing", "Information"),Student(12, "HuZhaoJun"),Student(13, "ZhangYuYang", "AutoControl");cout << " 入队列顺序为:" << endl << endl;for(int i=0; i<3; i+)cout << "" <<studentsi.stuNum << "t" << studentsi.stuName << "t"<&