面向對象程序設計（C++）：第九章 數組類與群體數據的組織

第九章群體類和群體數據的組織本章主要內容模板群體類群體數據的組織第一部分—模板函數模板類模板9.1函數模板1、函數模板可以用來創(chuàng)建一個通用功能的函數，以支持多種不同形參，進一步簡化重載函數的函數體設計。2、聲明方法：template<typename

標識符>函數聲明案例：求絕對值函數的模板#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案例：求絕對值函數的模板分析（1）編譯器從調用abs()時實參的類型，推導出函數模板的參數類型。例如，對于調用表達式abs(n)，由于實參n為int型，所以推導出模板中類型參數T為int。（2）當類型參數的含義確定后，編譯器將以函數模板為樣板，生成一個函數：

intabs(intx)

{returnx<0?-x:x;}1、類模板的作用使用類模板使用戶可以為類聲明一種模式，使得類中的某些數據成員、某些成員函數的形式參數、某些成員函數的返回值，能取任意類型（包括基本類型的和用戶自定義類型）。9.2類模板2、類模板的聲明類模板語法格式：template<classT>class類名{類成員聲明}

9.2類模板2、類模板的聲明如果需要在類模板以外定義其成員函數，則要采用以下的形式：template<class

模板參數表>類型名類名<T>::函數名（參數表）{}9.2類模板例9-2類模板應用舉例#include<iostream>#include<cstdlib>usingnamespacestd;//結構體StudentstructStudent{intid;//學號

floatgpa;//平均分};template<classT>//類模板：實現對任意類型數據進行存取classStore{private:Titem;//成員變量類型待定

inthaveValue;//用于標記item是否已被存入內容

public:Store(void);//默認形式（無形參）的構造函數

TGetElem(void);//提取數據函數,返回值類型待定

voidPutElem(Tx);//存入數據函數，形參類型待定};//默認形式構造函數的實現template<classT>Store<T>::Store(void):haveValue(0){}11例9-2類模板應用舉例template<classT>//提取數據函數的實現TStore<T>::GetElem(void){//如果試圖提取未初始化的數據，則終止程序

if(haveValue==0){cout<<"Noitempresent!"<<endl;exit(1);}returnitem;//返回item中存放的數據}12例9-2類模板應用舉例template<classT>//存入數據函數的實現voidStore<T>::PutElem(Tx){haveValue++;//將haveValue置為TRUE，表示item中已存入數值

item=x;//將x值存入item}13例9-2類模板應用舉例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未經初始化,在執(zhí)行函數D.GetElement()時出錯}14例9-2類模板應用舉例模版的本質(1)函數模版從功能上來說，和函數重載的功能相似(2)與函數重載區(qū)別

函數重載在代碼編寫階段需要寫出多個同名的函數，而模版是在程序編譯階段才將模版轉化成函數重載的形式。從而使得程序員不要編寫多個重名函數，減少了程序員的代碼編寫量。

第二部分—群體數據9.3群體1、群體概念群體是指由多個數據元素組成的集合體。群體可以分為兩個大類：線性群體和非線性群體。線性群體中的元素按位置排列有序，可以區(qū)分為第一個元素、第二個元素等。非線性群體不用位置順序來標識元素。1、線性群體的概念2、直接訪問群體--數組類3、順序訪問群體--鏈表類4、棧類5、隊列類9.3.1線性群體9.3.1線性群體1、線性群體的概念線性群體中的元素次序與其位置關系是對應的。在線性群體中，又可按照訪問元素的不同方法分為直接訪問、順序訪問和索引訪問。在本章我們只介紹直接訪問和順序訪問?！谝粋€元素第二個元素第三個元素最后一個元素2、數組（1）靜態(tài)數組是具有固定元素個數的群體，其中的元素可以通過下標直接訪問。（2）動態(tài)數組由一系列位置連續(xù)的，任意數量相同類型的元素組成。

動態(tài)數組類模板：例9-3（9_3.h）（3）動態(tài)數組類模板程序212、數組淺拷貝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;}深拷貝alistsizeAA的數組元素占用的內存拷貝前alistsizeAA的數組元素占用的內存拷貝后alistsizeBB的數組元素占用的內存為什么有的函數返回引用（1）如果一個函數的返回值是一個對象的值，它就被認為是一個常量，不能成為左值。（2）如果返回值為引用，由于引用是對象的別名，所以通過引用當然可以改變對象的值。指針轉換運算符的作用#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,intn);read(a,10);}//調用指針類型強制轉換voidread(int*p,intn){for(inti=0;i<n;i++)cin>>p[i];}Array類的應用例9-4求范圍2~N中的質數，N在程序運行時由鍵盤輸入。3、鏈表（1）鏈表是一種動態(tài)數據結構，可以用來表示順序訪問的線性群體。（2）每一個結點包括數據域和指向鏈表中下一個結點的指針（即下一個結點的地址）。單鏈表data1data2data3datanNULL…h(huán)eadrear3、鏈表單鏈表的結點類模板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;};在結點之后插入一個結點data1data2…pdata…template<classT>voidNode<T>::InsertAfter(Node<T>*p){//p節(jié)點指針域指向當前節(jié)點的后繼節(jié)點

p->next=next->next;next->next=p;//當前節(jié)點的指針域指向p}next

刪除結點之后的結點data1data2data3……Node<T>*Node<T>::DeleteAfter(void){Node<T>*tempPtr=next;if(next==NULL)returnNULL;next=tempPtr->next;returntempPtr;}tempPtr（3）基本操作生成結點插入結點查找結點刪除結點遍歷鏈表清空鏈表3、鏈表（4）鏈表類模板(例9-6)3、鏈表（4）鏈表類應用舉例(例9-7)3、鏈表4、特殊的線性群體——棧棧是只能從一端訪問的線性群體，可以訪問的這一端稱棧頂，另一端稱棧底。an┆a2a1入棧出棧棧頂棧底（1）棧的基本操作初始化入棧出棧清空棧訪問棧頂元素檢測棧的狀態(tài)（滿、空）4、特殊的線性群體——棧棧的應用例9.9一個簡單的整數計算器實現一個簡單的整數計算器，能夠進行加、減、乘、除和乘方運算。使用時算式采用后綴輸入法，每個操作數、操作符之間都以空白符分隔。4、特殊的線性群體——棧5、特殊的線性群體——隊列隊列是只能向一端添加元素，從另一端刪除元素的線性群體a1a2an-1an……隊頭隊尾入隊出隊a0循環(huán)隊列在想象中將數組彎曲成環(huán)形，元素出隊時，后繼元素不移動，每當隊尾達到數組最后一個元素時，便再回到數組開頭。1234……m-1m-2m-30amam+1am+2a3隊頭隊尾a4am-2am-3am-1隊滿狀態(tài)元素個數=m1234……m-1m-2m-30隊尾隊頭隊空狀態(tài)元素個數=0隊尾1234……m-1m-2m-30a0a1a2a3隊頭一般狀態(tài)41循環(huán)隊列例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;};//成員函數的實現略第三部分—群體數據的組織插入排序選擇排序交換排序順序查找折半查找9.4.1排序（sorting）1、排序是將一個數據元素的任意序列，重新排列成一個按關鍵字有序的序列。2、排序需要完成兩種基本操作：（1）比較兩個數的大?。?）調整元素在序列中的位置9.4.2內部排序方法1、插入排序2、選擇排序3、交換排序1、插入排序（1）思想：

每一步將一個待排序元素按其關鍵字值的大小插入到已排序序列的適當位置上，直到待排序元素插入完為止。（2）直接插入排序例9-11直接插入排序函數模板（9_11.h）1、插入排序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]=