C语言程序设计群体类和群体数据的组织

会计学1C语言程序设计群体类和群体数据的组织2第一部分—模板函数模板类模板第1页/共79页3函数模板函数模板可以用来创建一个通用功能的函数，以支持多种不同形参，进一步简化重载函数的函数体设计。声明方法：template<typename标识符>函数声明

函数模板第2页/共79页4求绝对值函数的模板#include<iostream>usingnamespacestd;template<typenameT>Tabs(Tx){returnx<0?-x:x;}intmain(){intn=-5;doubled=-5.5;cout<<abs(n)<<endl;cout<<abs(d)<<endl;}

函数模板运行结果：55.5第3页/共79页5求绝对值函数的模板分析编译器从调用abs()时实参的类型，推导出函数模板的类型参数。例如，对于调用表达式abs(n)，由于实参n为int型，所以推导出模板中类型参数T为int。当类型参数的含义确定后，编译器将以函数模板为样板，生成一个函数：

intabs(intx)

{returnx<0?-x:x;}

函数模板第4页/共79页6类模板的作用使用类模板使用户可以为类声明一种模式，使得类中的某些数据成员、某些成员函数的参数、某些成员函数的返回值，能取任意类型（包括基本类型的和用户自定义类型）。类模板第5页/共79页7类模板的声明类模板：template<模板参数表>class类名{类成员声明}如果需要在类模板以外定义其成员函数，则要采用以下的形式：template<模板参数表>类型名类名<T>::函数名（参数表）类模板第6页/共79页8例9-2类模板应用举例#include<iostream>#include<cstdlib>usingnamespacestd;//结构体StudentstructStudent{intid;//学号

floatgpa;//平均分};类模板第7页/共79页template<classT>//类模板：实现对任意类型数据进行存取classStore{private:Titem;//用于存放任意类型的数据

inthaveValue;//用于标记item是否已被存入内容

public:Store(void);//默认形式（无形参）的构造函数

TGetElem(void);//提取数据函数

voidPutElem(Tx);//存入数据函数};//默认形式构造函数的实现template<classT>Store<T>::Store(void):haveValue(0){}9第8页/共79页template<classT>//提取数据函数的实现TStore<T>::GetElem(void){//如果试图提取未初始化的数据，则终止程序

if(haveValue==0){cout<<"Noitempresent!"<<endl;exit(1);}returnitem;//返回item中存放的数据}template<classT>//存入数据函数的实现voidStore<T>::PutElem(Tx){haveValue++;//将haveValue置为TRUE，表示item中已存入数值

item=x;//将x值存入item}10第9页/共79页intmain(){Studentg={1000,23}; Store<int>S1,S2;Store<Student>S3;Store<double>D;

S1.PutElem(3);S2.PutElem(-7);cout<<S1.GetElem()<<""<<S2.GetElem()<<endl;

S3.PutElem(g);cout<<"Thestudentidis"<<S3.GetElem().id<<endl;

cout<<"RetrievingobjectD"; cout<<D.GetElem()<<endl;//输出对象D的数据成员

//由于D未经初始化,在执行函数D.GetElement()时出错}11第10页/共79页12第二部分—群体数据线性群体线性群体的概念直接访问群体--数组类顺序访问群体--链表类栈类队列类第11页/共79页13群体的概念群体是指由多个数据元素组成的集合体。群体可以分为两个大类：线性群体和非线性群体。线性群体中的元素按位置排列有序，可以区分为第一个元素、第二个元素等。非线性群体不用位置顺序来标识元素。第12页/共79页14线性群体的概念线性群体中的元素次序与其位置关系是对应的。在线性群体中，又可按照访问元素的不同方法分为直接访问、顺序访问和索引访问。在本章我们只介绍直接访问和顺序访问。…第一个元素第二个元素第三个元素最后一个元素第13页/共79页15数组静态数组是具有固定元素个数的群体，其中的元素可以通过下标直接访问。缺点：大小在编译时就已经确定，在运行时无法修改。动态数组由一系列位置连续的，任意数量相同类型的元素组成。优点：其元素个数可在程序运行时改变。动态数组类模板：例9-3（9_3.h）直接访问的线性群体第14页/共79页#ifndefARRAY_CLASS#defineARRAY_CLASSusingnamespacestd;#include<iostream>#include<cstdlib>#ifndefNULLconstintNULL=0;#endif//NULLenumErrorType{invalidArraySize,memoryAllocationError,indexOutOfRange};char*errorMsg[]={"Invalidarraysize","Memoryallocationerror","Invalidindex:"};动态数组类模板程序16第15页/共79页template<classT>classArray{private:T*alist;intsize;voidError(ErrorTypeerror,intbadIndex=0)const;public:Array(intsz=50);Array(constArray<T>&A);~Array(void);Array<T>&operator=(constArray<T>&rhs);T&operator[](inti);operatorT*(void)const;intListSize(void)const;voidResize(intsz);};17第16页/共79页18数组类模板的构造函数//构造函数template<classT>Array<T>::Array(intsz){if(sz<=0)//sz为数组大小（元素个数），若小于0，则输出错误信息

Error(invalidArraySize);

size=sz;//将元素个数赋值给变量sizealist=newT[size];//动态分配size个T类型的元素空间

if(alist==NULL)//如果分配内存不成功，输出错误信息

Error(memoryAllocationError);}直接访问的线性群体第17页/共79页19数组类的拷贝构造函数template<classT>Array<T>::Array(constArray<T>&X){intn=X.size;size=n;alist=newT[n];if(alist==NULL)Error(memoryAllocationError);T*srcptr=X.alist;//X.alist是对象X的数组首地址

T*destptr=alist;//alist是本对象中的数组首地址

while(n--)//逐个复制数组元素*destptr++=*srcptr++;}直接访问的线性群体第18页/共79页20浅拷贝alistsizeAA的数组元素占用的内存拷贝前alistsizeAA的数组元素占用的内存拷贝后alistsizeBintmain(){Array<int>A(10);......Array<int>B(A);......}template<classT>Array<T>::Array(constArray<T>&X){size=X.size;alist=X.alist;}第19页/共79页21深拷贝alistsizeAA的数组元素占用的内存拷贝前alistsizeAA的数组元素占用的内存拷贝后alistsizeBB的数组元素占用的内存第20页/共79页22数组类的重载"="运算符函数template<classT>Array<T>&Array<T>::operator=(constArray<T>&rhs){intn=rhs.size;if(size!=n){delete[]alist;alist=newT[n];if(alist==NULL)Error(memoryAllocationError);size=n;}T*destptr=alist;T*srcptr=rhs.alist;while(n--)*destptr++=*srcptr++;return*this;}直接访问的线性群体第21页/共79页23数组类的重载下标操作符函数template<classT>T&Array<T>::operator[](intn){//检查下标是否越界

if(n<0||n>size-1)Error(indexOutOfRange,n);//返回下标为n的数组元素

returnalist[n];}直接访问的线性群体第22页/共79页24为什么有的函数返回引用如果一个函数的返回值是一个对象的值，它就被认为是一个常量，不能成为左值。如果返回值为引用。由于引用是对象的别名，所以通过引用当然可以改变对象的值。直接访问的线性群体第23页/共79页25重载指针转换操作符template<classT>Array<T>::operatorT*(void)const{//返回当前对象中私有数组的首地址

returnalist;}直接访问的线性群体第24页/共79页26指针转换运算符的作用#include<iostream>usingnamespacestd;intmain(){

inta[10];voidread(int*p,intn);read(a,10);}voidread(int*p,intn){for(inti=0;i<n;i++)cin>>p[i];}intmain(){

Array<int>a(10);voidread(int*p,n);read(a,10);}voidread(int*p,intn){for(inti=0;i<n;i++)cin>>p[i];}直接访问的线性群体第25页/共79页27Array类的应用例9-4求范围2~N中的质数，N在程序运行时由键盘输入。直接访问的线性群体第26页/共79页#include<iostream>#include<iomanip>#include"9_3.h"usingnamespacestd;intmain(){Array<int>A(10);intn;intprimecount=0,i,j;cout<<"Enteravalue>=2asupperlimitforprimenumbers:";cin>>n;A[primecount++]=2;//2是一个质数

for(i=3;i<n;i++){if(primecount==A.ListSize())A.Resize(primecount+10);if(i%2==0)continue;j=3;while(j<=i/2&&i%j!=0)j+=2;if(j>i/2)A[primecount++]=i;}for(i=0;i<primecount;i++){cout<<setw(5)<<A[i];if((i+1)%10==0)cout<<endl;}cout<<endl;}28第27页/共79页29链表链表是一种动态数据结构，可以用来表示顺序访问的线性群体。链表是由系列结点组成的，结点可以在运行时动态生成。每一个结点包括数据域和指向链表中下一个结点的指针（即下一个结点的地址）。如果链表每个结点中只有一个指向后继结点的指针，则该链表称为单链表。顺序访问的线性群体第28页/共79页30单链表data1data2data3datanNULL…headrear顺序访问的线性群体第29页/共79页31单链表的结点类模板template<classT>classNode{private:Node<T>*next;public:Tdata;Node(constT&item,Node<T>*ptrnext=NULL);voidInsertAfter(Node<T>*p);Node<T>*DeleteAfter(void);Node<T>*NextNode(void)const;};顺序访问的线性群体第30页/共79页32在结点之后插入一个结点data1data2…pdata…template<classT>voidNode<T>::InsertAfter(Node<T>*p){//p节点指针域指向当前节点的后继节点

p->next=next;next=p;//当前节点的指针域指向p}顺序访问的线性群体第31页/共79页33

删除结点之后的结点顺序访问的线性群体data1data2data3……Node<T>*Node<T>::DeleteAfter(void){Node<T>*tempPtr=next;if(next==NULL)returnNULL;next=tempPtr->next;returntempPtr;}tempPtr第32页/共79页34链表的基本操作生成结点插入结点查找结点删除结点遍历链表清空链表顺序访问的线性群体第33页/共79页35链表类模板(例9-6)//9_6.h#ifndefLINKEDLIST_CLASS#defineLINKEDLIST_CLASS#include<iostream>#include<cstdlib>usingnamespacestd;#ifndefNULLconstintNULL=0;#endif//NULL#include"9_5.h"顺序访问的线性群体第34页/共79页template<classT>classLinkedList{private:Node<T>*front,*rear;Node<T>*prevPtr,*currPtr;intsize;intposition;Node<T>*GetNode(constT&item,Node<T>*ptrNext=NULL);voidFreeNode(Node<T>*p);voidCopyList(constLinkedList<T>&L);36第35页/共79页public:LinkedList(void);LinkedList(constLinkedList<T>&L);~LinkedList(void);LinkedList<T>&operator=(constLinkedList<T>&L);intListSize(void)const;intListEmpty(void)const;voidReset(intpos=0);voidNext(void);intEndOfList(void)const;intCurrentPosition(void)const;37第36页/共79页voidInsertFront(constT&item);voidInsertRear(constT&item);voidInsertAt(constT&item);voidInsertAfter(constT&item);TDeleteFront(void);voidDeleteAt(void);T&Data(void);voidClearList(void);};#endif//LINKEDLIST_CLASS38第37页/共79页39链表类应用举例(例9-7)#include<iostream>usingnamespacestd;#include"9_6.h"#include"9_6.cpp"intmain(){LinkedList<int>Link;inti,key,item;for(i=0;i<10;i++){cin>>item;Link.InsertFront(item); }顺序访问的线性群体第38页/共79页cout<<"List:";Link.Reset();while(!Link.EndOfList()){cout<<Link.Data()<<"";Link.Next();}cout<<endl;cout<<"请输入一个需要删除的整数:";cin>>key;Link.Reset();40第39页/共79页while(!Link.EndOfList()){if(Link.Data()==key)Link.DeleteAt(); Link.Next(); }cout<<"List:";Link.Reset();while(!Link.EndOfList()){cout<<Link.Data()<<"";Link.Next();}cout<<endl;}41第40页/共79页42特殊的线性群体——栈栈是只能从一端访问的线性群体，可以访问的这一端称栈顶，另一端称栈底。an┆a2a1入栈出栈栈顶栈底特殊的线性群体——栈第41页/共79页43栈的应用举例——函数调用特殊的线性群体——栈main{}调fun(参数)结束fun(参数)返回①②⑤⑦⑧参数当前现场返回地址③⑥入栈当前现场返回地址出栈参数④出栈当前现场返回地址第42页/共79页44栈的应用举例——表达式处理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)特殊的线性群体——栈第43页/共79页45栈的基本状态栈空栈中没有元素栈满栈中元素个数达到上限一般状态栈中有元素，但未达到栈满状态特殊的线性群体——栈第44页/共79页栈顶┆an┆a1a0入栈出栈数组下标maxn10一般状态栈顶入栈出栈数组下标初始状态（栈空）maxn10栈顶amax┆an┆a1a0入栈出栈数组下标maxn10栈满状态46第45页/共79页47栈的基本操作初始化入栈出栈清空栈访问栈顶元素检测栈的状态（满、空）特殊的线性群体——栈第46页/共79页48栈类模板(例9-8)特殊的线性群体——栈//9-8.h#ifndefSTACK_CLASS#defineSTACK_CLASS#include<iostream>#include<cstdlib>usingnamespacestd;constintMaxStackSize=50;

template<classT>classStack{private:Tstacklist[MaxStackSize];inttop;public:Stack(void);voidPush(constT&item);TPop(void);voidClearStack(void);TPeek(void)const;intStackEmpty(void)const;intStackFull(void)const;};//类的实现略第47页/共79页49栈的应用例9.9一个简单的整数计算器实现一个简单的整数计算器，能够进行加、减、乘、除和乘方运算。使用时算式采用后缀输入法，每个操作数、操作符之间都以空白符分隔。例如，若要计算"3+5"则输入"35+"。乘方运算符用"^"表示。每次运算在前次结果基础上进行，若要将前次运算结果清除，可键入"c"。当键入"q"时程序结束。9-9.h9-9.cpp特殊的线性群体——栈第48页/共79页//9_9.h#include<iostream>#include<cmath>#include<cstdlib>#include<cstring>usingnamespacestd;enumBoolean{False,True};#include"9_8.h"classCalculator{private:Stack<int>S;voidEnter(intnum);BooleanGetTwoOperands(int&opnd1,int&opnd2);voidCompute(charop);public:voidRun(void);voidClear(void);};50第49页/共79页voidCalculator::Enter(intnum){S.Push(num);}BooleanCalculator::GetTwoOperands(int&opnd1,int&opnd2){if(S.StackEmpty()){cerr<<"Missingoperand!"<<endl;returnFalse;}opnd1=S.Pop();if(S.StackEmpty()){cerr<<"Missingoperand!"<<endl;returnFalse;}opnd2=S.Pop();returnTrue;}51第50页/共79页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){cerr<<"Divideby0!"<<endl;S.ClearStack();}elseS.Push(operand2/operand1);break;case'^':S.Push(pow(operand2,operand1));break; }cout<<'='<<S.Peek()<<''; }elseS.ClearStack();}52第51页/共79页voidCalculator::Run(void){charc[20];while(cin>>c,*c!='q')switch(*c){case'c':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;}}53第52页/共79页voidCalculator::Clear(void){S.ClearStack();}//9_9.cpp#include"9-9.h"intmain(){CalculatorCALC;CALC.Run();}54第53页/共79页55特殊的线性群体——队列队列是只能向一端添加元素，从另一端删除元素的线性群体a1a2an-1an……队头队尾入队出队a0第54页/共79页56队列的基本状态队空队列中没有元素队满队列中元素个数达到上限一般状态队列中有元素，但未达到队满状态特殊的线性群体——队列第55页/共79页a0a1an-1an……队头队尾入队出队数组下标01n-1nmax(一般状态)……队头队尾入队出队数组下标01n-1nmax(队空状态)a0a1an-1anamax……队头队尾入队出队数组下标01n-1nmax(队满状态)元素移动方向元素移动方向57第56页/共79页58循环队列在想象中将数组弯曲成环形，元素出队时，后继元素不移动，每当队尾达到数组最后一个元素时，便再回到数组开头。特殊的线性群体——队列第57页/共79页1234……m-1m-2m-30amam+1am+2a3队头队尾a4am-2am-3am-1队满状态元素个数=m1234……m-1m-2m-30队尾队头队空状态元素个数=0队尾1234……m-1m-2m-30a0a1a2a3队头一般状态59第58页/共79页60例9-10队列类模板特殊的线性群体——队列#ifndefQUEUE_CLASS#defineQUEUE_CLASS#include<iostream>#include<cstdlib>usingnamespacestd;constintMaxQSize=50;template<classT>classQueue{private:intfront,rear,count;Tqlist[MaxQSize];public:Queue(void);voidQInsert(constT&item);TQDelete(void);voidClearQueue(void);TQFront(void)const;intQLength(void)const;intQEmpty(void)const;intQFull(void)const;};//成员函数的实现略第59页/共79页61第三部分—群体数据的组织插入排序选择排序交换排序顺序查找折半查找第60页/共79页62排序（sorting）排序是计算机程序设计中的一种重要操作，它的功能是将一个数据元素的任意序列，重新排列成一个按关键字有序的序列。数据元素：数据的基本单位。在计算机中通常作为一个整体进行考虑。一个数据元素可由若干数据项组成。关键字：数据元素中某个数据项的值，用它可以标识（识别）一个数据元素。在排序过程中需要完成两种基本操作：比较两个数的大小调整元素在序列中的位置群体数据的组织第61页/共79页63内部排序与外部排序内部排序：待排序的数据元素存放在计算机内存中进行的排序过程。外部排序：待排序的数据元素数量很大，以致内存存中一次不能容纳全部数据，在排序过程中尚需对外存进行访问的排序过程。群体数据的组织第62页/共79页64内部排序方法插入排序选择排序交换排序群体数据的组织第63页/共79页65插入排序的基本思想每一步将一个待排序元素按其关键字值的大小插入到已排序序列的适当位置上，直到待排序元素插入完为止。初始状态：[5]41020123插入操作：1[4][45]10201232[10][4510]201233[20][451020]1234[12][45101220]35[3][345101220]第64页/共79页66直接插入排序在插入排序过程中，由于寻找插入位置的方法不同又可以分为不同的插入排序算法，这里我们只介绍最简单的直接插入排序算法。例9-11

直接插入排序函数模板（9_11.h）群体数据的组织第65页/共79页template<classT>voidInsertionSort(TA[],intn){inti,j;Ttemp;for(i=1;i<n;i++){j=i;temp=A[i];while(j>0&&temp<A[j-1]){A[j]=A[j-1];j--;}A[j]=temp;}}直接插入排序函数模板（9_11.h）67第66页/共79页68选择排序的基本思想每次从待排序序列中选择一个关键字最小的元素，（当需要按关键字升序排列时），顺序排在已排序序列的最后，直至全部排完。[541020123]初始状态：3[41020125]34[1020125]第i次选择后，将选出的那个记录与第i个记录做交换。345[201210]......第67页/共79页69直接选择排序在选择类排序方法中，从待排序序列中选择元素的方法不同，又分为不同的选择排序方法，其中最简单的是通过顺序比较找出待排序序列中的最小元素，称为直接选择排序。例9-12

直接选择排序函数模板（9-12.h）群体数据的组织第68页/共79页template<classT>voidSwap(T&x,T&y){Ttemp;temp=x;x=y;y=temp;}template<classT>voidSelectionSort(TA[],intn){intsmallIndex;inti,j;for(i=0;i<n-1;i++){smallIndex=i;for(j=i+1;j<n;j++)if(A[j]<A[smallIndex])smallIndex=j;Swap(A[i],A[smallIndex]);}}直接选择排序函数模板（9-12.h）70第69页/共79页71交换排序的基本思想两两比较待排序序列中的元素，并交换不满足顺序要求的各对元素，直到全部满足顺序要求为止。群体数据的组织第70页/共79页72最简单的交换排序方法