第21讲模板应用举例 教学目的与要求: 了解各类模板的特征。 掌握栈、队列、链表的应用 教学内容提要: 、栈类模板; 2、队列类模板; 2、链表类模板; 教学重点:链表类的声明和使用 教学难点:链表类的声明和使用。 教学进度:P228~P238 教学过程:
第 21 讲 模板应用举例 •教学目的与要求： 了解各类模板的特征。 掌握栈、队列、链表的应用。 •教学内容提要： 1、栈类模板； 2、队列类模板； 2、链表类模板； •教学重点： 链表类的声明和使用。 •教学难点：链表类的声明和使用。 •教学进度：P228～P238 •教学过程：
211栈类模板 入栈 出栈 入栈出栈 数组下标 数组下标 max max n a 栈顶 a 0 栈顶 0 a 0 初始状态(栈空) 般状态 入栈 出栈 数组下标 max ax+栈顶 a 相满状杰
栈顶 ┆ an ┆ a1 a0 入栈 出栈 数组下标 max n 1 0 一般状态 栈顶 入栈 出栈 数组下标 初始状态（栈空） max n 1 0 amax 栈顶 ┆ an ┆ a1 a0 入栈 出栈 数组下标 max n 1 0 栈满状态 21.1 栈类模板
例21.1使用栈类模板的使用。 #includeiostream. h> const int size=10 templateclass Type> //声明一个类模板 class stack[ public: void inito tos=0; void push( Type ch);//参数取Type类型 Type popo //返回类型取Type类型 private Type stck[size];//数组的类型为类型参数Type, 即可取任意类型 int tos template class Type> void stack:: push ( Type ob) if (tos==size) cout<< stack is full", return:I stckltos]=ob; tos++
例21.1 使用栈类模板的使用。 #include const int size=10; template //声明一个类模板 class stack{ public: void init(){ tos=0; } void push(Type ch); //参数取Type类型 Type pop(); //返回类型取Type类型 private: Type stck[size]; //数组的类型为类型参数Type， 即可取任意类型 int tos; }; template void stack::push(Type ob) { if (tos==size){ cout<<"stack is full"; return ; } stck[tos]=ob; tos++; }
template class Type> Type stack :: pop o if (tos==o) couts1,s2;//创建两个模板参数 为char型的对象 int s1 inito; s2. inito
template Type stack ::pop() { if (tos==0) { cout s1,s2; //创建两个模板参数 为char型的对象 int i; s1.init(); s2.init();
s1.push(a’);s2.push(x’); s1. push(b); s2. push(y') sl push(c); s2. push(z') for(i=0; 1is1,is2;//创建两个模板参数为int型的对象 isl inito; is2 inito isl. push (1); is2. push (2) is1. push (3); is2 push (4) isl. push (5); is2. push (6) for(i=0;i<3;i++) cout< pop is1: <<isl. pop(<endl for(i=0;i<3;i++ cout< pop is2: <<is2 pop(<<endl return 0
s1.push('a'); s2.push('x'); s1.push('b'); s2.push('y'); s1.push('c'); s2.push('z'); for(i=0;i is1,is2; //创建两个模板参数为int型的对象 is1.init(); is2.init(); is1.push(1); is2.push(2); is1.push(3); is2.push(4); is1.push(5); is2.push(6); for (i=0;i<3;i++) cout<<"pop is1: "<<is1.pop()<<endl; for (i=0;i<3;i++) cout<<"pop is2: "<<is2.pop()<<endl; return 0; }
21.2队列类模板 队列与栈不同,对数据采用“先进先出”--FIFO的管理 方式(而栈则使用“先进后出”-FILO方式)。 出队 ao a2 入队 队尾 队列数据放于作为类成员的动态数组 queue之中,在构造 函数中,将通过new来生成该动态数组,动态数组 queue的 大小由类的私有数据成员 Maxsize之值来确定。但注意,此 示例并没有循环使用上述的动态数组 queue空间。即是说 队列中至多可以存放 Maxsize个数据项,即使取走若干项后 有了空闲空间后也不可重新进行使用。若稍加改造,使存取 数据时首先通过对下标进行模 Maxsize的运算,则可实现循 环使用动态数组 queue空间的功能
21.2队列类模板 队列与栈不同，对数据采用“先进先出”--FIFO的管理 方式（而栈则使用“先进后出”--FILO方式）。 队列数据放于作为类成员的动态数组queue之中，在构造 函数中，将通过new来生成该动态数组，动态数组queue的 大小由类的私有数据成员Maxsize之值来确定。但注意，此 示例并没有循环使用上述的动态数组queue空间。即是说， 队列中至多可以存放Maxsize个数据项，即使取走若干项后 有了空闲空间后也不可重新进行使用。若稍加改造，使存取 数据时首先通过对下标进行模Maxsize的运算，则可实现循 环使用动态数组queue空间的功能。 a1 a2 …… an-1 an 队头 队尾 出队 a0 入队
#include #include template class Queue i int maxsize: /队列的大小 int front rear 元素放在 queue front1图到 queuerearl之中 keytype * queue;/动态数组 queue,用来存放队列数据 public: Queue( Gint size){/构造函数,生成动态数组来存放队列数据 Maxsize=size; queue=new keytype maxsize]; front=rear=-41;/意味着队列为空
#include #include template class Queue { int Maxsize; //队列的大小 int front,rear; //元素放在queue[front+1]到queue[rear]之中 keytype *queue; //动态数组queue，用来存放队列数据 public: Queue (int size) { //构造函数，生成动态数组来存放队列数据 Maxsize=size; queue=new keytype[Maxsize]; front=rear=-1; //意味着队列为空 };
int IsFull o i if (rear==Maxsize-1) return 1 else return o int IsEmpty o i if (front==rear) return 1 else return 0 void Add(const keytype &) keytype Delete(void)
int IsFull () { if (rear==Maxsize-1) return 1; else return 0; }; int IsEmpty () { if (front==rear) return 1; else return 0; }; void Add(const keytype &); keytype Delete(void); };
Delete在类体外定义,函数名前要加类限定符“ Queue:” template keytype Queue:: Delete(void) if (sEmptyOi cout void Queue: Add(const keytype item) i if (FuLlo) cout <<the queue is full"<<endl; else queue++rearl=item;
//Delete在类体外定义，函数名前要加类限定符“Queue::” template keytype Queue::Delete(void){ if (IsEmpty()){ cout void Queue::Add(const keytype & item){ if (IsFull()) cout << "the queue is full"<<endl; else queue[++rear]=item; };
void minot int i=0; Queue Qi(10); Queue Qfl(10), Qf2(10 while( Qi IsFull!O){∥Qi中只能盛10个数 Qi.Add(2*i++);∥Qi中:0,2,4,6,8,10,12,14,16,18 Q1.Ad(3.0*i);∥Q中:3,6,9,12,15,18,21,24,27,30 for(i=0;i<4;i++){ /四次循环,每次总 ∥先往Qn的队列尾部加入两个数,而后又从首部删取一个数并输出 Qf2.Add(4.5 Qi. Delete( 从Q首删取一元素,乘以45,而后将其加入到Q尾部 /四次循环往QD队列尾加入:0*45,2*4.5,4*4.5,6*45 程序执行后的显示结果如下 1.5 9 3
void main() { int i=0; Queue Qi(10); Queue Qf1(10),Qf2(10); while (!Qi.IsFull()) { //Qi中只能盛10个数 Qi.Add(2*i++); //Qi中: 0,2,4,6,8,10,12,14,16,18 Qf1.Add(3.0*i); //Qf1中: 3,6,9,12,15,18,21,24,27,30 } for (i=0; i<4; i++){ //四次循环，每次总 //先往Qf2的队列尾部加入两个数，而后又从首部删取一个数并输出 Qf2.Add(4.5*Qi.Delete()); //从Qi首删取一元素，乘以4.5，而后将其加入到Qf2尾部 //四次循环往Qf2队列尾加入：0*4.5，2*4.5，4*4.5，6*4.5 ... } } 程序执行后的显示结果如下： 0 1.5 9 3