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

1、1目录一、题目内容及要求.2二、题目设计思路.2三、类设计与类关系.3四、主要功能函数流程图.3五、运行结果及分析.4六、总结.52题目内容及要求1.队列是一种连续的存储结构， 存入数据只能从一端(称为尾部)进入， 取出数据则只能 从另一端(头部)取出。根据下述描述实现一个自定义的队列类：template type name Typestruct Lin kNode Type data;Lin kNode *n ext;Lin kNode() : next(NULL) Lin kNode( con st Type &x,L in kNode *p=NULL ) : data(x), next(

2、p) ;template classQueuepublic:Queue ();Queue ();in li ne bool isEmpty () con st;in li ne void makeEmpty();in li ne void enq ueue( const Type &x );in li ne void dequeue( Type &x );in li ne void getFr ont( Type &x);private:LinkNode *front;/指向头结点的指针，front-next-data是队头的第一个元素LinkNode *rear; /指向队尾(最后添加的一个

3、元素)的指针in li ne void han dleU nderflow();/控制队列下溢;题目设计思路1.queue.h文件在queue.h头文件中使用命名空间itlab在其中声明：(1)模板结构体链表结点(struct LinkNode)，其中包含的数据成员有：模板参数类类型Type对应的data，存放模板实现类的具体数据，LinkNode模板类型结构体指针n ext，用来指向下一个结点；成员函数包括：LinkNode()无参构造函数，其中数据成员next默认为NULL，LinkNode(const Type构造函数/析构函数/队列是否为空清空队列/插入一个元素/弹出一个元素 得到对头

4、元素3&x,LinkNode *p = NULL)，采用参数初始化表对数据成员初始化，其中第一个参数为常量Type类型的引用x,初始化数据成员data，第二个参赛为结构体类型指针p默认值为4NULL，用来初始化数据成员next。(2)模板类队列(class Queue),包含的公共成员函数有：1无参构造函数Queue()，在定义对象时，由系统调用，完成对象的初始化；2析构函数Queue()，与构造函数相反，是在撤销对象占用内存前进行一些清理工作。可以被用来执行“用户希望在最后一次使用对象之后所执行的任何操作”；3内联函数判断队列是否为空，返回值为布尔类型常量，in li ne bool isE

5、mpty() const;4内联函数清空队列，无返回值，inline void makeEmpty();5内联函数向队列中插入一个元素，inline void enqueue(const Type &x)，参数为Type类型常量，插入的新元素作为队列中的队尾结点；内联函数从队列中弹出一个元素，inline void dequeue( Type &x )，无返回值，但传入参数为Type类型的引用x,从对首取出结点元素的数据，将其赋值给x，实现函数值的返回；3内联函数控制队列下溢，in li ne void han dleU nderflow()。(3)同时包含其实现文件queue-impl.h，

6、#include queue-impl.h。2.queue-impl.h文件在queue-impl.h头文件，是实现queue.h头文件中声明的模板类Queue，实现其声明的函数，完成函数的定义，在预编译时，会将头文件queue-impl.h中的内容取代头文件queue.h中的#include queue-impl.h这一行。3.queue_test.cpp在queue_test.cpp文件中，包含主函数，声明结构体类型Student，是模板结构体链表(LinkNode)的实现类，将其作为插入队列和弹出队列的基本元素，测试队列类Queue的主要成员函数：判断队列是否为空(isEmpty)、向对

7、列中插入一个元素(enqueue)、从队列中弹出一个元素(dequeue)、得到队首元素的数据(getFront)、私有成员函数控制队列下 溢(handleUnderflow)。三、类设计与类关系1.类设计主要包含队列类Queue。 其私有数据成元是指向结构体类型变量(struct Student)的头 指针和指向结构体类型的后继指针。在main函数中声明了结构体类型Student，其主要包含整型的学号、字符串类型的学生姓名、字符串类型的系部名称，以及带默认参数的构造函数。2.类关系在main函数中，通过定义一个队列类类型的对象q(Queue q)，显示的将结内联函数得到对首元素结点的数据，数

8、引用类型间接返回函数值；私有数据成员包括：1指向模板结构体类型变量的头指针，2指向模板结构体类型变量的后继指针,in li ne void getFro nt( Type &x)，同样采用函数参Lin kNode *frontLin kNode *rear5构体类型(Student为结构体类型)传递给Queue对应的类参Type(模板参数类型).四、主要功能函数流程图1.向对列中插入一个元素函数(in li ne void en queue(co nst Type &x)流程图6开始一/对头指针否-是否対空当前限尾的后继指针描向新结点结束2.从队列中弹出一个元素函数(in li ne void

9、 dequeue( Type &x )流程图开始 3/ 对列否Xjfts为空队首结点赋值给结点类型指针口将对百结由的数攥通过引用间接锁怕给释放箱针P指向的内存空间结束五、运行结果及分析1.运行结果:入肚列顺序为：11Zhangllinsf12HluZhaoJun13ZhanglfuVang对苜元素対：1 nf ar-mat lainInformat tanRuitoGantrci 111ZhangHing1 nf口rmat ion对头二对首 H 新结点对尾指针是否为 0 指针值打印内存空间不足退出程俘否设宣需结点为队尾结点对头栢针是否为 0 指针值打EI】内存空间不足退出程俘调甫捋制队列下満函

10、数打 ED 队列酣空退出程序7岀队列顺序为：11ZhanMin12HluZltaoduiitZltanVuVanianInformat ianAutDCantFO 1The queue 1母empti/f2结果分析：（1）队列初始为空，依次将学生插入队列，并打印入队顺序；（2）此时调用getFront（Type &x）函数取得对头的元素；（3）出对时，按照先进先出原则，打印出队顺序。六、总结1模板机制（1）模板的代码重用机制是基于C语言宏展开基础发展而来，宏展开的一套文本替换 算法从预处理阶段搬移到编译阶段，结合函数重载中的一套类型匹配搜寻算法一起就诞生了 模版的内在运作机制。（2）函数模板和

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

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

13、d）和对尾（tail），当有一个元素入对时，它被放在队尾的位置，就像一个新到来的顾客排在队 伍末端一样。而出队的元素则总是在对头的那个，就像排在队伍前面等待最久的那个顾客一样。源代码：/*queue.h*A simple queue impleme nted by C+ template class.8*/9#ifndef QUEUE_H #defi ne QUEUE_H#inelude #in clude#in clude using n amespace std;n amespace itlab* Queue Node*/template struct Lin kNodeType data

14、;Lin kNode *n ext;Li nkNode() : next(NULL) Lin kNode( co nst Type &x,Li nkNode *p=NULL ) : data(x), next(p) ；/* Queue*/template class Queuepublic:Queue ();Queue ();/ Queue(c onst Queue &q);/ Queue & operator=(c onst Queue&q);/#defi ne QUEUE_INIT_SIZE 100/#defi ne QUEUE_INCREMENT 10队列初始化大小/队列空间不够时一次申

15、请大小/构造函数析构函数/队列是否为空/清空队列10in li ne bool isEmpty () con st;in li ne void makeEmpty();11/in li ne bool isFull() con st;/队列是否已满int size () con st;/队列中元素的个数in li ne void enq ueue( const Type &x );/插入一个元素in li ne void dequeue( Type &x );/弹出一个元素in li ne void getFro nt( Type &x);得到对头元素private:LinkNode *fro

16、nt;/指向头结点的指针，front-next-data是队头的第一个元素LinkNode *rear; /指向队尾(最后添加的一个元素)的指针inline void han dle Un derflow();#in clude queue-impl.hn amespace itlab#en dif/ QUEUE_H/-/-*queue-impl.h* Impleme ntati on for Queue class.*/* con structors and destructor*/template Queue:Queue():fro nt(NULL), rear(NULL)*12templ

17、ate Queue:Queue()makeEmpty();/* If the queue empty, retur n true.*/template in li ne bool Queue:isEmpty() const retur n front = NULL;/* Make the queue empty.*/template in li ne void Queue:makeEmpty() Lin kNode *p;while( front != NULL)p = front;front = front-n ext;delete p;/* En ter the eleme nt into

18、 the queue.*/template in li ne void Queue:e nq ueue( const Type &x ) if(front = NULL)front = rear = new Lin kNode( x );if( !front )cerr Out of memory! n ext = new Lin kNode( x ); if( !rear )cerr Out of memory! n ext;/* Pop an eleme nt from the queue.*/template in li ne void Queue:dequeue( Type &x )

19、if( !isEmpty()Lin kNode *p = front;x = fron t-data;front = front-n ext;delete p;elsehan dle Un derflow();/* Get the front eleme nt of the queue.*/template in li ne void Queue:getFr ont( Type &x ) if( !isEmpty()x = fron t-data;elsehan dle Un derflow();/* Han dle the error of get eleme nt from am empt

20、y queue.14*/template in li ne void Queue:ha ndle Un derflow()cerr The queue is empty! endl en dl; exit(1);/-/-/*queue_test.cpp* Queue class testi ng.*/#in clude #in clude #in clude queue.h#i nclude 15using n amespace std;using n amespace itlab;struct Stude ntint stuNum;stri ng stuName;stri ng departme nt;Stude nt ( int nu mber = 0, const stri ng &n ame = To m&Jerry, const stri ng &dpt = I nformati on):stuN um(nu mber), stuName( name)