数据结构-队列-C++实现

...wd......wd......wd...目录2258一、题目内容及要求316140二、题目设计思路35084三、类设计与类关系47971四、主要功能函数流程图420382五、运行结果及分析514570六、总结6题目内容及要求1.队列是一种连续的存储构造，存入数据只能从一端〔称为尾部〕进入，取出数据则只能从另一端〔头部〕取出。根据下述描述实现一个自定义的队列类：template<typenameType>structLinkNode{Typedata;LinkNode<Type>*next;LinkNode():next(NULL){}LinkNode(constType&x,LinkNode<Type>*p=NULL):data(x),next(p){}};template<typenameType>classQueue{public: Queue();//构造函数~Queue();//析构函数inlineboolisEmpty()const;//队列是否为空inlinevoidmakeEmpty();//清空队列inlinevoidenqueue(constType&x);//插入一个元素inlinevoiddequeue(Type&x);//弹出一个元素inlinevoidgetFront(Type&x);//得到对头元素private:LinkNode<Type>*front;//指向头结点的指针,front->next->data是队头的第一个元素LinkNode<Type>*rear;//指向队尾〔最后添加的一个元素〕的指针inlinevoidhandleUnderflow();//控制队列下溢};题目设计思路queue.h文件在queue.h头文件中使用命名空间itlab在其中声明：模板构造体链表结点〔structLinkNode〕，其中包含的数据成员有：①模板参数类类型Type对应的data，存放模板实现类的具体数据，②LinkNode<Type>模板类型构造体指针next，用来指向下一个结点；成员函数包括：①LinkNode()无参构造函数，其中数据成员next默认为NULL，②LinkNode(constType&x,LinkNode<Type>*p=NULL)，采用参数初始化表对数据成员初始化，其中第一个参数为常量Type类型的引用x，初始化数据成员data，第二个参赛为构造体类型指针p默认值为NULL，用来初始化数据成员next。模板类队列〔classQueue〕，包含的公共成员函数有：①无参构造函数Queue()，在定义对象时，由系统调用，完成对象的初始化；②析构函数~Queue()，与构造函数相反，是在撤销对象占用内存前进展一些清理工作。可以被用来执行“用户希望在最后一次使用对象之后所执行的任何操作〞；③内联函数判断队列是否为空，返回值为布尔类型常量，inlineboolisEmpty()const;④内联函数清空队列，无返回值，inlinevoidmakeEmpty();⑤内联函数向队列中插入一个元素，inlinevoidenqueue(constType&x)，参数为Type类型常量，插入的新元素作为队列中的队尾结点；⑥内联函数从队列中弹出一个元素，inlinevoiddequeue(Type&x)，无返回值，但传入参数为Type类型的引用x，从对首取出结点元素的数据，将其赋值给x，实现函数值的返回；⑦内联函数得到对首元素结点的数据，inlinevoidgetFront(Type&x)，同样采用函数参数引用类型间接返回函数值；私有数据成员包括：①指向模板构造体类型变量的头指针，LinkNode<Type>*front②指向模板构造体类型变量的后继指针，LinkNode<Type>*rear③内联函数控制队列下溢，inlinevoidhandleUnderflow()。同时包含其实现文件queue-impl.h，#include"queue-impl.h"。queue-impl.h文件在queue-impl.h头文件，是实现queue.h头文件中声明的模板类Queue，实现其声明的函数，完成函数的定义，在预编译时，会将头文件queue-impl.h中的内容取代头文件queue.h中的#include"queue-impl.h"这一行。queue_test.cpp在queue_test.cpp文件中，包含主函数，声明构造体类型Student，是模板构造体链表〔LinkNode<Type>〕的实现类，将其作为插入队列和弹出队列的基本元素，测试队列类Queue的主要成员函数：判断队列是否为空〔isEmpty〕、向对列中插入一个元素〔enqueue〕、从队列中弹出一个元素〔dequeue〕、得到队首元素的数据〔getFront〕、私有成员函数控制队列下溢〔handleUnderflow〕。类设计与类关系类设计主要包含队列类Queue。其私有数据成元是指向构造体类型变量〔structStudent〕的头指针和指向构造体类型的后继指针。在main函数中声明了构造体类型Student，其主要包含整型的学号、字符串类型的学生姓名、字符串类型的系部名称，以及带默认参数的构造函数。类关系在main函数中，通过定义一个队列类类型的对象q〔Queue<Student>q〕，显示的将构造体类型〔Student为构造体类型〕传递给Queue<Type>对应的类参Type〔模板参数类型〕。主要功能函数流程图向对列中插入一个元素函数〔inlinevoidenqueue(constType&x)〕流程图从队列中弹出一个元素函数〔inlinevoiddequeue(Type&x)〕流程图运行结果及分析运行结果：结果分析：队列初始为空，依次将学生插入队列，并打印入队顺序；此时调用getFront(Type&x)函数取得对头的元素；出对时，按照先进先出原则，打印出队顺序。总结1.模板机制〔1〕模板的代码重用机制是基于C语言宏展开基础开展而来，宏展开的一套文本替换算法从预处理阶段搬移到编译阶段，结合函数重载中的一套类型匹配搜寻算法一起就诞生了模版的内在运作机制。〔2〕函数模板和类模板提供了类型参数化的通用机制。函数模板的类参在函数的调用点根据实参的类型反演出来，形成重载函数，同时实参的数值作为入口又进展函数调用。〔3〕类模板的类参一般由对象定义的方式显式给出，根据直接指定的类名或整型常数初始化模板类参形参表中的对应工程值，用这些具体的类名和常数替换模板中类参或形参，形成特定的类。这些工作是编译器自动宏替换复制完成的，但比预处理的宏替换执行了更多的类型安全检查，而根据模板生成的代码具有明显的相近性质。〔4〕需要注意形参与类参的区别，形参是运行时压入堆栈传递给函数的数据值，而类参是在函数调用点获得的实参的静态数据类型，数据类型是静态的，该数据类型在编译阶段确定。〔5〕函数模板产生的函数是一系列形参个数一样，形参数据类型不同的重载函数，类模板产生的类是类名不同，构造相近的类。〔6〕此外，类模板的不同实现是不同的类，此特定的类上的模板成员函数不同于彼模板类相应的成员函数版本。其间通过类域分辨符进展了清晰的分界，因此类模板提供一种类型安全的鉴别机制。2.队列数据构造〔1〕队列是一种采用先进先出〔firstin,firstoutFIFO〕策略的对元素操作的动态集合。〔2〕队列上的INSERT操作称为入队〔ENQUEUE〕，DELETE操作称为出队〔DEQUEUE〕。〔3〕队列的先进先出特性类似于收银台前排队等待结账的一排顾客。队列有对头〔head〕和对尾〔tail〕，当有一个元素入对时，它被放在队尾的位置，就像一个新到来的顾客排在队伍末端一样。而出队的元素则总是在对头的那个，就像排在队伍前面等待最久的那个顾客一样。源代码：/********************************************************queue.h**AsimplequeueimplementedbyC++templateclass.********************************************************/#ifndefQUEUE_H#defineQUEUE_H#include<iostream>#include<stdlib.h>#include<cstdlib>usingnamespacestd;namespaceitlab{/***QueueNode**///#defineQUEUE_INIT_SIZE100//队列初始化大小//#defineQUEUE_INCREMENT10//队列空间不够时一次申请大小template<typenameType>structLinkNode{Typedata;LinkNode<Type>*next;LinkNode():next(NULL){}LinkNode(constType&x,LinkNode<Type>*p=NULL):data(x),next(p){}};/***Queue**/template<typenameType>classQueue{public:Queue();//构造函数~Queue();//析构函数//Queue(constQueue<Type>&q); // Queue&operator=(constQueue<Type>&q);inlineboolisEmpty()const;//队列是否为空inlinevoidmakeEmpty();//清空队列//inlineboolisFull()const;//队列是否已满//intsize()const;//队列中元素的个数inlinevoidenqueue(constType&x);//插入一个元素inlinevoiddequeue(Type&x);//弹出一个元素inlinevoidgetFront(Type&x);//得到对头元素private:LinkNode<Type>*front;//指向头结点的指针,front->next->data是队头的第一个元素LinkNode<Type>*rear;//指向队尾〔最后添加的一个元素〕的指针inlinevoidhandleUnderflow();};#include"queue-impl.h"}//namespaceitlab#endif//QUEUE_H/////********************************************************queue-impl.h**ImplementationforQueueclass.********************************************************//***constructorsanddestructor**/template<typenameType>Queue<Type>::Queue():front(NULL),rear(NULL){}template<typenameType>Queue<Type>::~Queue(){makeEmpty();}/***Ifthequeueempty,returntrue.**/template<typenameType>inlineboolQueue<Type>::isEmpty()const{returnfront==NULL;}/***Makethequeueempty.**/template<typenameType>inlinevoidQueue<Type>::makeEmpty(){LinkNode<Type>*p;while(front!=NULL){p=front;front=front->next;deletep;}}/***Entertheelementintothequeue.**/template<typenameType>inlinevoidQueue<Type>::enqueue(constType&x){if(front==NULL){front=rear=newLinkNode<Type>(x);if(!front){cerr<<"Outofmemory!"<<endl;exit(1);}}else{rear->next=newLinkNode<Type>(x);if(!rear){cerr<<"Outofmemory!"<<endl;exit(1);}rear=rear->next;}}/***Popanelementfromthequeue.**/template<typenameType>inlinevoidQueue<Type>::dequeue(Type&x){if(!isEmpty()){LinkNode<Type>*p=front;x=front->data;front=front->next;deletep;}elsehandleUnderflow();}/***Getthefrontelementofthequeue.**/template<typenameType>inlinevoidQueue<Type>::getFront(Type&x){if(!isEmpty())x=front->data;elsehandleUnderflow();}/***Handletheerrorofgetelementfromamemptyqueue.**/template<typenameType>inlinevoidQueue<Type>::handleUnderflow(){cerr<<"Thequeueisempty!"<<endl<<endl;exit(1);}/////********************************************************queue_test.cpp**Queueclasstesting.********************************************************/#include<iostream>#include<string>#include"queue.h"#include<stdlib.h>usingnamespacestd;usingnamespaceitlab;structStudent{intstuNum;stringstuName;stringdepartment;Student(intnumber=0,conststring&name="Tom&Jerry",conststring&dpt="Information"):stuNum(number),stuName(name),department(dpt){}};intmain(intargc,char**argv){Studentstu;Queue<Student>q;Studentstudents[3