1第一部分(bfen)模板函数(hnsh)模板类模板第1页/共79页第一页，共80页。2函数(hnsh)模板函数模板(mbn)可以用来创建一个通用功能的函数，以支持多种不同形参，进一步简化重载函数的函数体设计。声明方法：template函数声明 函 数 模 板第2页/共79页第二页，共80页。3求绝对值函数(hnsh)的模板#includeusing namespace std;templateT abs(T x) return x0?-x:x; int main() int n=-5; double d=-5.5; coutabs(n)endl; coutabs(d)endl; 函 数 模 板运行(ynxng)结果：55.5第3页/共79页第三页，共80页。4求绝对值函数(hnsh)的模板分析编译器从调用(dioyng)abs()时实参的类型，推导出函数模板的类型参数。例如，对于调用(dioyng)表达式abs(n)，由于实参n为int型，所以推导出模板中类型参数T为int。当类型参数的含义确定后，编译器将以函数模板为样板，生成一个函数：intabs(intx)returnx0?-x:x; 函 数 模 板第4页/共79页第四页，共80页。5类模板(mbn)的作用使用类模板使用户可以为类声明一种模式，使得类中的某些数据成员、某些成员函数的参数、某些成员函数的返回值，能取任意类型（包括(boku)基本类型的和用户自定义类型）。类 模 板第5页/共79页第五页，共80页。6类模板(mbn)的声明类模板：templateclass类名类成员声明如果需要在类模板以外(ywi)定义其成员函数，则要采用以下的形式：template类型名类名:函数名（参数表）类 模 板第6页/共79页第六页，共80页。7例9-2类模板应用(yngyng)举例#include#includeusingnamespacestd;/结构(jigu)体StudentstructStudentintid;/学号floatgpa;/平均分;类 模 板第7页/共79页第七页，共80页。template/类模板：实现对任意类型数据进行存取classStoreprivate:Titem;/用于存放任意类型的数据inthaveValue;/用于标记item是否已被存入(cnr)内容public:Store(void);/默认形式（无形参）的构造函数TGetElem(void);/提取数据函数voidPutElem(Tx);/存入(cnr)数据函数;/默认形式构造函数的实现templateStore:Store(void):haveValue(0)8第8页/共79页第八页，共80页。template/提取数据函数的实现(shxin)TStore:GetElem(void)/如果试图提取未初始化的数据，则终止程序if(haveValue=0)coutNoitempresent!endl;exit(1);returnitem;/返回item中存放的数据template/存入数据函数的实现(shxin)voidStore:PutElem(Tx)haveValue+;/将haveValue置为TRUE，表示item中已存入数值item=x;/将x值存入item9第9页/共79页第九页，共80页。intmain()Studentg=1000,23;StoreS1,S2;StoreS3;StoreD;S1.PutElem(3);S2.PutElem(-7);coutS1.GetElem()S2.GetElem()endl;S3.PutElem(g);coutThestudentidisS3.GetElem().idendl;coutRetrievingobjectD;coutD.GetElem()endl;/输出对象D的数据成员/由于(yuy)D未经初始化,在执行函数D.GetElement()时出错10第10页/共79页第十页，共80页。11第二部分(bfen)群体数据线性群体线性群体的概念直接访问(fngwn)群体-数组类顺序访问(fngwn)群体-链表类栈类队列类第11页/共79页第十一页，共80页。12群体(qnt)的概念群体是指由多个数据元素组成的集合体。群体可以分为两个(lin)大类：线性群体和非线性群体。线性群体中的元素按位置排列有序，可以区分为第一个元素、第二个元素等。非线性群体不用位置顺序来标识元素。第12页/共79页第十二页，共80页。13线性群体(qnt)的概念线性群体中的元素次序与其位置关系是对应的。在线性群体中，又可按照访问元素的不同方法分为直接访问、顺序访问和索引(suyn)访问。在本章我们只介绍直接访问和顺序访问。第一个元素第二个元素第三个元素最后一个元素第13页/共79页第十三页，共80页。14数组静态数组是具有固定元素个数的群体，其中的元素可以(ky)通过下标直接访问。缺点：大小在编译时就已经确定，在运行时无法修改。动态数组由一系列位置连续的，任意数量相同类型的元素组成。优点：其元素个数可在程序运行时改变。动态数组类模板：例9-3（9_3.h）直接(zhji)访问的线性群体第14页/共79页第十四页，共80页。#ifndefARRAY_CLASS#defineARRAY_CLASSusingnamespacestd;#include#include#ifndefNULLconstintNULL=0;#endif/NULLenumErrorTypeinvalidArraySize,memoryAllocationError,indexOutOfRange;char*errorMsg=Invalidarraysize,Memoryallocationerror,Invalidindex:;动态数组类模板(mbn)程序15第15页/共79页第十五页，共80页。templateclassArrayprivate:T*alist;intsize;voidError(ErrorTypeerror,intbadIndex=0)const;public:Array(intsz=50);Array(constArray&A);Array(void);Array&operator=(constArray&rhs);T&operator(inti);operatorT*(void)const;intListSize(void)const;voidResize(intsz);16第16页/共79页第十六页，共80页。17数组类模板(mbn)的构造函数/构造函数templateArray:Array(intsz)if(sz=0)/sz为数组大小(dxio)（元素个数），若小于0，则输出错误信息Error(invalidArraySize);size=sz;/将元素个数赋值给变量sizealist=newTsize;/动态分配size个T类型的元素空间if(alist=NULL)/如果分配内存不成功，输出错误信息Error(memoryAllocationError);直接(zhji)访问的线性群体第17页/共79页第十七页，共80页。18数组类的拷贝(kobi)构造函数templateArray:Array(constArray&X)intn=X.size;size=n;alist=newTn;if(alist=NULL)Error(memoryAllocationError);T*srcptr=X.alist;/X.alist是对象X的数组首地址T*destptr=alist;/alist是本对象中的数组首地址while(n-)/逐个复制(fzh)数组元素*destptr+=*srcptr+;直接(zhji)访问的线性群体第18页/共79页第十八页，共80页。19浅拷贝(kobi) alist sizeAA的数组元素占用的内存拷贝前 alist sizeAA的数组元素占用的内存拷贝后 alist sizeBint main() Array A(10); . Array B(A); .template Array:Array( const Array& X) size = X.size; alist= X.alist;第19页/共79页第十九页，共80页。20深拷贝(kobi) alist sizeAA的数组元素占用的内存拷贝前 alist sizeAA的数组元素占用的内存拷贝后 alist sizeBB的数组元素占用的内存第20页/共79页第二十页，共80页。21数组类的重载(zhnzi)=运算符函数templateArray&Array:operator=(constArray&rhs)intn=rhs.size;if(size!=n)deletealist;alist=newTn;if(alist=NULL)Error(memoryAllocationError);size=n;T*destptr=alist;T*srcptr=rhs.alist;while(n-)*destptr+=*srcptr+;return*this;直接访问(fngwn)的线性群体第21页/共79页第二十一页，共80页。22数组类的重载下标(xibio)操作符函数templateT&Array:operator(intn)/检查(jinch)下标是否越界if(nsize-1)Error(indexOutOfRange,n);/返回下标为n的数组元素returnalistn;直接访问(fngwn)的线性群体第22页/共79页第二十二页，共80页。23为什么有的函数返回(fnhu)引用如果(rgu)一个函数的返回值是一个对象的值，它就被认为是一个常量，不能成为左值。如果(rgu)返回值为引用。由于引用是对象的别名，所以通过引用当然可以改变对象的值。直接访问(fngwn)的线性群体第23页/共79页第二十三页，共80页。24重载(zhnzi)指针转换操作符templateArray:operatorT*(void)const/返回(fnhu)当前对象中私有数组的首地址returnalist;直接访问(fngwn)的线性群体第24页/共79页第二十四页，共80页。25指针转换(zhunhun)运算符的作用#includeusingnamespacestd;intmain()inta10;voidread(int*p,intn);read(a,10);voidread(int*p,intn)for(inti=0;ipi;intmain()Arraya(10);voidread(int*p,n);read(a,10);voidread(int*p,intn)for(inti=0;ipi;直接(zhji)访问的线性群体第25页/共79页第二十五页，共80页。26Array类的应用(yngyng)例9-4求范围(fnwi)2N中的质数，N在程序运行时由键盘输入。直接(zhji)访问的线性群体第26页/共79页第二十六页，共80页。#include#include#include9_3.husingnamespacestd;intmain()ArrayA(10);intn;intprimecount=0,i,j;cout=2asupperlimitforprimenumbers:;cinn;Aprimecount+=2;/2是一个(y)质数for(i=3;in;i+)if(primecount=A.ListSize()A.Resize(primecount+10);if(i%2=0)continue;j=3;while( ji/2)Aprimecount+=i;for(i=0;iprimecount;i+)coutsetw(5)Ai;if(i+1)%10=0)coutendl;coutendl;27第27页/共79页第二十七页，共80页。28链表链表是一种动态数据结构，可以用来表示(biosh)顺序访问的线性群体。链表是由系列结点组成的，结点可以在运行时动态生成。每一个结点包括数据域和指向链表中下一个结点的指针（即下一个结点的地址）。如果链表每个结点中只有一个指向后继结点的指针，则该链表称为单链表。顺序访问(fngwn)的线性群体第28页/共79页第二十八页，共80页。29单链表 data1 data2 data3 datan NULLheadrear顺序(shnx)访问的线性群体第29页/共79页第二十九页，共80页。30单链表的结点(jidin)类模板templateclassNodeprivate:Node*next;public:Tdata;Node(constT&item,Node*ptrnext=NULL);voidInsertAfter(Node*p);Node*DeleteAfter(void);Node*NextNode(void)const;顺序访问(fngwn)的线性群体第30页/共79页第三十页，共80页。31在结点之后插入(chr)一个结点 data1 data2 p datatemplate void Node:InsertAfter(Node *p) /p节点指针域指向当前(dngqin)节点的后继节点 p-next = next; next = p; /当前(dngqin)节点的指针域指向p 顺序访问(fngwn)的线性群体第31页/共79页第三十一页，共80页。32删除(shnch)结点之后的结点顺序访问(fngwn)的线性群体 data1 data2 data3Node *Node:DeleteAfter(void) Node *tempPtr = next; if (next = NULL) return NULL; next = tempPtr-next; return tempPtr; tempPtr第32页/共79页第三十二页，共80页。33链表的基本操作生成(shnchn)结点插入结点查找结点删除结点遍历链表清空链表顺序访问(fngwn)的线性群体第33页/共79页第三十三页，共80页。34链表类模板(mbn)(例9-6)/9_6.h#ifndefLINKEDLIST_CLASS#defineLINKEDLIST_CLASS#include#includeusingnamespacestd;#ifndefNULLconstintNULL=0;#endif/NULL#include9_5.h顺序(shnx)访问的线性群体第34页/共79页第三十四页，共80页。templateclassLinkedListprivate:Node*front,*rear;Node*prevPtr,*currPtr;intsize;intposition;Node*GetNode(constT&item,Node*ptrNext=NULL);voidFreeNode(Node*p);voidCopyList(constLinkedList&L);35第35页/共79页第三十五页，共80页。public:LinkedList(void);LinkedList(constLinkedList&L);LinkedList(void);LinkedList&operator=(constLinkedList&L);intListSize(void)const;intListEmpty(void)const;voidReset(intpos=0);voidNext(void);intEndOfList(void)const;intCurrentPosition(void)const;36第36页/共79页第三十六页，共80页。voidInsertFront(constT&item);voidInsertRear(constT&item);voidInsertAt(constT&item);voidInsertAfter(constT&item);TDeleteFront(void);voidDeleteAt(void);T&Data(void);voidClearList(void);#endif/LINKEDLIST_CLASS37第37页/共79页第三十七页，共80页。38链表类应用(yngyng)举例(例9-7)#includeusingnamespacestd;#include9_6.h#include9_6.cppintmain()LinkedListLink;inti,key,item;for(i=0;iitem;Link.InsertFront(item);顺序(shnx)访问的线性群体第38页/共79页第三十八页，共80页。coutList:;Link.Reset();while(!Link.EndOfList()coutLink.Data();Link.Next();coutendl;coutkey;Link.Reset();39第39页/共79页第三十九页，共80页。while(!Link.EndOfList()if(Link.Data()=key)Link.DeleteAt();Link.Next();coutList:;Link.Reset();while(!Link.EndOfList()coutLink.Data();Link.Next();coutendl;40第40页/共79页第四十页，共80页。41特殊(tsh)的线性群体栈栈是只能(zhnn)从一端访问的线性群体，可以访问的这一端称栈顶，另一端称栈底。ana2a1入栈出栈栈顶栈底特殊(tsh)的线性群体栈第41页/共79页第四十一页，共80页。42栈的应用(yngyng)举例函数调用特殊(tsh)的线性群体栈main调fun(参数)结束fun(参数)返回参数当前现场返回地址入栈当前现场返回地址出栈参数出栈当前现场 返 回 地址第42页/共79页第四十二页，共80页。43栈的应用(yngyng)举例表达式处理ba/a/b+c*d(a)t1+a/b+c*dt1=a/b(b)dct1*+a/b+c*d(c)t3a/b+c*dt3=t1+t2(e)t2t1+a/b+c*dt2=c*d(d)特殊(tsh)的线性群体栈第43页/共79页第四十三页，共80页。44栈的基本(jbn)状态栈空栈中没有(miyu)元素栈满栈中元素个数达到上限一般状态栈中有元素，但未达到栈满状态特殊(tsh)的线性群体栈第44页/共79页第四十四页，共80页。栈顶ana1a0入栈出栈数组下标maxn10一般状态栈顶入栈出栈数组下标初始状态（栈空）maxn10栈顶amaxana1a0入栈出栈数组下标maxn10栈满状态45第45页/共79页第四十五页，共80页。46栈的基本操作初始化入栈出栈清空栈访问栈顶元素(yuns)检测栈的状态（满、空）特殊(tsh)的线性群体栈第46页/共79页第四十六页，共80页。47栈类模板(mbn)(例9-8)特殊(tsh)的线性群体栈/9-8.h#ifndefSTACK_CLASS#defineSTACK_CLASS#include#includeusingnamespacestd;constintMaxStackSize=50;templateclassStackprivate:TstacklistMaxStackSize;inttop;public: Stack (void); void Push (const T& item); T Pop (void); void ClearStack(void); T Peek (void) const; int StackEmpty(void) const; int StackFull(void) const;/类的实现(shxin)略第47页/共79页第四十七页，共80页。48栈的应用(yngyng)例9.9一个简单的整数计算器实现一个简单的整数计算器，能够进行加、减、乘、除和乘方运算。使用 (shyng)时算式采用后缀输入法，每个操作数、操作符之间都以空白符分隔。例如，若要计算3+5则输入35+。乘方运算符用表示。每次运算在前次结果基础上进行，若要将前次运算结果清除，可键入 c。当键入q时程序结束。9-9.h9-9.cpp特殊(tsh)的线性群体栈第48页/共79页第四十八页，共80页。/9_9.h#include#include#include#includeusingnamespacestd;enumBooleanFalse,True;#include9_8.hclassCalculatorprivate:StackS;voidEnter(intnum);BooleanGetTwoOperands(int&opnd1,int&opnd2);voidCompute(charop);public:voidRun(void);voidClear(void);49第49页/共79页第四十九页，共80页。voidCalculator:Enter(intnum)S.Push(num);BooleanCalculator:GetTwoOperands(int&opnd1,int&opnd2)if(S.StackEmpty()cerrMissingoperand!endl;returnFalse;opnd1=S.Pop();if(S.StackEmpty()cerrMissingoperand!endl;returnFalse;opnd2=S.Pop();returnTrue;50第50页/共79页第五十页，共80页。voidCalculator:Compute(charop)Booleanresult;intoperand1,operand2;result=GetTwoOperands(operand1,operand2);if(result)switch(op)case+:S.Push(operand2+operand1);break;case-:S.Push(operand2-operand1);break;case*:S.Push(operand2*operand1);break;case/:if(operand1=0)cerrDivideby0!endl;S.ClearStack();elseS.Push(operand2/operand1);break;case:S.Push(pow(operand2,operand1);break;cout=S.Peek()c,*c!=q)switch(*c)casec:S.ClearStack();break;case-:if(strlen(c)1)Enter(atoi(c);elseCompute(*c);break;case+:case*:case/:case:Compute(*c);break;default:Enter(atoi(c);break;52第52页/共79页第五十二页，共80页。voidCalculator:Clear(void)S.ClearStack();/9_9.cpp#include9-9.hintmain()CalculatorCALC;CALC.Run();53第53页/共79页第五十三页，共80页。54特殊的线性群体(qnt)队列队列是只能向一端添加元素，从另一端删除(shnch)元素的线性群体a1 a2an-1 an队头队尾入队出队a0第54页/共79页第五十四页，共80页。55队列(duli)的基本状态队空队列中没有元素队满队列中元素个数达到(ddo)上限一般状态队列中有元素，但未达到(ddo)队满状态特殊的线性群体(qnt)队列第55页/共79页第五十五页，共80页。a0 a1an-1 an队头队尾入队出队数组下标 0 1 n-1 n max(一般状态)队头队尾入队出队数组下标 0 1 n-1 n max(队空状态) a0 a1 an-1 an amax队头队尾入队出队数组下标 0 1 n-1 n max(队满状态)元素移动(ydng)方向元素(yun s)移动方向56第56页/共79页第五十六页，共80页。57循环(xnhun)队列在想象中将数组弯曲成环形，元素出队时，后继元素不移动，每当队尾达到数组最后一个 (y)元素时，便再回到数组开头。特殊(tsh)的线性群体队列第57页/共79页第五十七页，共80页。1234m-1m-2m-30amam+1am+2a3队头队尾a4am-2am-3am-1队满状态 元素个数=m1234m-1m-2m-30队尾队头队空状态 元素个数=0队尾1234m-1m-2m-30a0a1a2a3队头一般状态58第58页/共79页第五十八页，共80页。59例9-10队列(duli)类模板特殊(tsh)的线性群体队列#ifndefQUEUE_CLASS#defineQUEUE_CLASS#include#includeusingnamespacestd;constintMaxQSize=50;templateclassQueueprivate:intfront,rear,count;TqlistMaxQSize;public: Queue (void); void QInsert(const T& item); T QDelete(void); void ClearQueue(void); T QFront(void) const; int QLength(void) const; int QEmpty(void) const; int QFull(void) const; ;/成员函数(hnsh)的实现略第59页/共79页第五十九页，共80页。60第三部分(bfen)群体数据的组织插入排序选择排序交换排序顺序(shnx)查找折半查找第60页/共79页第六十页，共80页。61排序(pix)（sorting）排序是计算机程序设计中的一种重要操作，它的功能是将一个数据元素的任意序列，重新排列成一个按关键字有序的序列。数据元素：数据的基本单位。在计算机中通常作为一个整体进行考虑。一个数据元素可由若干(rugn)数据项组成。关键字：数据元素中某个数据项的值，用它可以标识（识别）一个数据元素。在排序过程中需要完成两种基本操作：比较两个数的大小调整元素在序列中的位置群体数据(shj)的组织第61页/共79页第六十一页，共80页。62内部排序(pix)与外部排序(pix)内部排序：待排序的数据元素(yuns)存放在计算机内存中进行的排序过程。外部排序：待排序的数据元素(yuns)数量很大，以致内存存中一次不能容纳全部数据，在排序过程中尚需对外存进行访问的排序过程。群体数据(shj)的组织第62页/共79页第六十二页，共80页。63内部(nib)排序方法插入排序选择(xunz)排序交换排序群体(qnt)数据的组织第63页/共79页第六十三页，共80页。64插入排序的基本(jbn)思想每一步将一个待排序(pix)元素按其关键字值的大小插入到已排序(pix)序列的适当位置上，直到待排序(pix)元素插入完为止。初始状态： 5 4 10 20 12 3插入操作：1 4 4 5 10 20 12 32 10 4 5 10 20 12 33 20 4 5 10 20 12 34 12 4 5 10 12 20 35 3 3 4 5 10 12 20第64页/共79页第六十四页，共80页。65直接(zhji)插入排序在插入(chr)排序过程中，由于寻找插入(chr)位置的方法不同又可以分为不同的插入(chr)排序算法，这里我们只介绍最简单的直接插入(chr)排序算法。例9-11直接插入(chr)排序函数模板（9_11.h）群体数据(shj)的组织第65页/共79页第六十五页，共80页。templatevoidInsertionSort(TA,intn)inti,j;Ttemp;for(i=1;i0&tempAj-1)Aj=Aj-1;j-;Aj=temp;直接插入排序函数(hnsh)模板（9_11.h）66第66页/共79页第六十六页，共80页。67选择排序的基本(jbn)思想每次从待排序序列中选择一个关键字最小的元素，（当需要按关键字升序排列(pili)时），顺序排在已排序序列的最后，直至全部排完。5 4 10 20 12 3初始状态：3 4 10 20 12 53 4 10 20 12 5第 i 次选择后，将选出的那个(n ge)记录与第 i 个记录做交换。3 4 5 20 12 10. .第67页/共79页第六十七页，共80页。68直接选择(xunz)排序在选择类排序方法中，从待排序序列中选择元素的方法不同，又分为不同的选择排序方法，其中(qzhng)最简单的是通过顺序比较找出待排序序列中的最小元素，称为直接选择排序。例9-12直接选择排序函数模板（9-12.h）群体(qnt)数据的组织第68页/共79页第六十八页，共80页。templatevoidSwap(T&x,T&y)Ttemp;temp=x;x=y;y=temp;templatevoidSelectionSort(TA,intn)intsmallIndex;inti,j;for(i=0;in-1;i+)smallIndex=i;for(j=i+1;jn;j+)if(A jAsmallIndex)smallIndex=j;Swap(Ai,AsmallIndex);直接(zhji)选择排序函数模板（9-12.h）69第69页/共79页第六十九页，共80页。70交换排序(pix)的基本思想两两比较待排序序列中的元素，并交换不满足(mnz)顺序要求的各对元素，直到全部满足(mnz)顺序要求为止。群体(qnt)数据的组织第70页/共79页第七十页，共80页。71最简单(jindn)的交换排序方法起泡排序对具有n个元素(yuns)的序列按升序进行起泡排序的步骤：首先将第一个元素(yuns)与第二个元素(yuns)进行比较，若为逆序，则将两元素(yuns)交换。然后比较第二、第三个元素(yuns)，依次类推，直到第n-1和第n个元素(yuns)进行了比较和交换。此过程称为第一趟起泡排序。经过第一趟，最大的元素(yuns)便被交换到第n个位置。对前n-1个元素(yuns)进行第二趟起泡排序，将其中最大元素(yuns)交换到第n-1个位置。如此继续，直到某一趟排序未发生任何交换时，排序完毕。对n个元素(yuns)的序列，起泡排序最多需要进行n-1趟。群体(qnt)数据的组织第71页/共79页第七十一页，共80页。72起泡(q po)(q po)排序举例对整数序列(xli)85243按升序排序8524352438243582345823458初始状态第一趟结果(ji gu)第二趟结果第三趟结果第四趟结果小的逐渐上升每趟沉下一个最大的群体数据的组织第72页/共79页第七十二页，共80页。73例9-13起泡排序函数(hnsh)模板templatevoidSwap(T&x,T&y)Ttemp;temp=x;x=y;y=temp;template void BubbleSort(T A, int n) int i,j; int lastExchangeIndex; i = n-1; while (i 0) lastExchangeIndex = 0; for (j = 0; j i; j+) if (Aj+1 Aj) Swap(Aj,Aj+1); lastExchangeIndex = j; i = lastExchangeIndex; 群体(qnt)数据的组织第73页/共79页第七十三页，共80页。74顺序(shnx)查找其基本思想从序列的首元素开始，逐个元素与待查找的关键字进行比较，直到找到相等的。若整个序列中没有与待查找关键字相等的元素，就是(jish)查找不成功。顺序查找函数模板例9-14群体(qnt)数据的组织第74页/共79页第七十四页，共80页。templateintSeqSearch(Tlist,intn,Tkey)for(inti=0;in;i+)if(listi=key)returni;return-1;顺序查找(ch zho)函数模板75第75页/共79页第七十五页，共80页。76折半(zhbn)查找的基本思想对于已按关键字排序(pi x)的序列，经过一次比较，可将序列分割成两部分，然后只在有可能包含待查元素的一部分中继续查找，并根据试探结果继续分割，逐步缩小查找范围，直至找到或找不到为止。群体数据(shj)的组织第76页/共79页第七十六页，共80页。77折半查找(chzho)举例用折半查找法，在下列(xili)序列中查找值为21的元素：L=1513192137566475808892H=11M =INT(L+H)/2)=6513192137L=1H=M-1=5M=INT(L+H)/2)=3M2137HL=M+1=4LM=INT(L+H)/2)=4M第77页/共79页第七十七页，共80页。78例10-5折半(zhbn)查找函数模板templateintBinSearch(Tlist,intn,Tkey)intmid,low,high;Tmidvalue;low=0;high=n-1;while(low=high)mid=(low+high)/2;midvalue=listmid;if(key=midvalue)returnmid;elseif(keymidvalue)high=mid-1;elselow=mid+1;return-1;群体(qnt)数据的组织第78页/共79页第七十八页，共80页。79感谢您的欣赏(xnshng)！第79页/共79页第七十九页，共80页。内容(nirng)总结1。-x:x。类型名 类名(li mn):函数名（参数表）。栈的应用举例函数调用。栈的应用举例表达式处理。= q)。case -:。case +:。case *:。case /:。case :。特殊的线性群体队列。感谢您的欣赏第八十页，共80页。