面向?qū)ο蟪绦蛟O(shè)計(jì)（C++）：第九章 數(shù)組類與群體數(shù)據(jù)的組織

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

標(biāo)識(shí)符>函數(shù)聲明案例：求絕對值函數(shù)的模板#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;}運(yùn)行結(jié)果：55.5案例：求絕對值函數(shù)的模板分析（1）編譯器從調(diào)用abs()時(shí)實(shí)參的類型，推導(dǎo)出函數(shù)模板的參數(shù)類型。例如，對于調(diào)用表達(dá)式abs(n)，由于實(shí)參n為int型，所以推導(dǎo)出模板中類型參數(shù)T為int。（2）當(dāng)類型參數(shù)的含義確定后，編譯器將以函數(shù)模板為樣板，生成一個(gè)函數(shù)：

intabs(intx)

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

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

模板參數(shù)表>類型名類名<T>::函數(shù)名（參數(shù)表）{}9.2類模板例9-2類模板應(yīng)用舉例#include<iostream>#include<cstdlib>usingnamespacestd;//結(jié)構(gòu)體StudentstructStudent{intid;//學(xué)號(hào)

floatgpa;//平均分};template<classT>//類模板：實(shí)現(xiàn)對任意類型數(shù)據(jù)進(jìn)行存取classStore{private:Titem;//成員變量類型待定

inthaveValue;//用于標(biāo)記item是否已被存入內(nèi)容

public:Store(void);//默認(rèn)形式（無形參）的構(gòu)造函數(shù)

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

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

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

item=x;//將x值存入item}13例9-2類模板應(yīng)用舉例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的數(shù)據(jù)成員

//由于D未經(jīng)初始化,在執(zhí)行函數(shù)D.GetElement()時(shí)出錯(cuò)}14例9-2類模板應(yīng)用舉例模版的本質(zhì)(1)函數(shù)模版從功能上來說，和函數(shù)重載的功能相似(2)與函數(shù)重載區(qū)別

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

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

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

public:Tdata;Node(constT&item,Node<T>*ptrnext=NULL);voidInsertAfter(Node<T>*p);Node<T>*DeleteAfter(void);Node<T>*NextNode(void)const;};在結(jié)點(diǎn)之后插入一個(gè)結(jié)點(diǎn)data1data2…pdata…template<classT>voidNode<T>::InsertAfter(Node<T>*p){//p節(jié)點(diǎn)指針域指向當(dāng)前節(jié)點(diǎn)的后繼節(jié)點(diǎn)

p->next=next->next;next->next=p;//當(dāng)前節(jié)點(diǎn)的指針域指向p}next

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

每一步將一個(gè)待排序元素按其關(guān)鍵字值的大小插入到已排序序列的適當(dāng)位置上，直到待排序元素插入完為止。（2）直接插入排序例9-11直接插入排序函數(shù)模板（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]=