unit06模板與數(shù)據(jù)結(jié)構(gòu)

面向?qū)ο蟪绦蛟O(shè)計課程安排：40（上課）+16（實驗）考核方式（程序）：課程作業(yè)+4次上機(jī)實驗+一份綜合性的課程設(shè)計報告授課內(nèi)容課本：模板、繼承、多態(tài)、排序和查找算法以及異常處理課本外(自學(xué)為主)：WindowsAPI可視化編程+Openframework注意：所有關(guān)于課程相關(guān)的資料都放在課程主頁類、對象相關(guān)知識回顧1.類對象的概念（封裝和抽象）2.如何設(shè)計類3.編譯器提供的默認(rèn)成員函數(shù)4.函數(shù)重載（運(yùn)算符和成員函數(shù)）5.對象的生命周期6.引用7.類型的隱式轉(zhuǎn)換（新的知識點）類、對象相關(guān)知識回顧C(jī)ircle類設(shè)計：classCircle{數(shù)據(jù)成員(屬性或組件)：

圓心和半徑操作(基于數(shù)據(jù)成員)：

設(shè)置半徑，移動圓心位置，圓的大小比較，計算面積和周長以及判斷某點是否在圓內(nèi)等};Point類structPoint{數(shù)據(jù)成員：x,y坐標(biāo)};類、對象相關(guān)知識回顧公有私有程序源代碼第六章

模板與數(shù)據(jù)結(jié)構(gòu)面性對象程序設(shè)計（OOP）三個核心：1.抽象(abstraction):數(shù)據(jù)和方法用類的形式進(jìn)行封裝2.繼承(inheritance)：繼承一個類的所有方法和屬性3.

多態(tài)(polymophism)：編譯或者運(yùn)行時決定調(diào)用那個函數(shù)多態(tài)：編譯時(compiletme)多態(tài)和運(yùn)行時(runtime)多態(tài)(靜態(tài)綁定/動態(tài)綁定).泛型編程：獨(dú)立于任何特定類型的方式編寫代碼。簡化程序代碼的重要手段。模板是建立通用的與數(shù)據(jù)類型無關(guān)的算法的重要手段，是泛型編程的基礎(chǔ)函數(shù)重載inta,b;...if(0==compare(a,b))...strings1,s2;...if(1==compare(s1,s2))...

intcompare(stringa,stringb){ if(a>b)return1; elseif(b>a))return-1; elsereturn0;}intcompare(inta,intb){ if(a>b)return1; elseif(b>a)return-1; elsereturn0;}這兩個函數(shù)的區(qū)別？有沒有簡化代碼的方法？第三章遺留的問題

3.8.1函數(shù)重載【例3.16】

3+5=調(diào)用sum(3,5)函數(shù)sum(3,5)return82.2+5.6=調(diào)用sum(2.2,5.6)函數(shù)doublesum(2.2,5.6)return7.83.5+4+8=調(diào)用sum(3.5,4,8)函數(shù)floatsum(3.5,4.0,8.0)return15.5結(jié)束87.815.5【例3.16】

重載函數(shù)的應(yīng)用。intsum(inta,intb){

returna+b;}Doublesum(doublea,doubleb){

returna+b;}floatsum(floata,floatb,floatc){

returna+b+c;}intmain(){ cout<<"3+5="<<sum(3,5) <<endl; cout<<"2.2+5.6=“ <<sum(2.2,5.6)<<endl; cout<<"3.5+4+8=“ <<sum(3.5,4,8)<<endl;

return0;}思考：重載有沒有需要改進(jìn)的地方？第六章模板與數(shù)據(jù)結(jié)構(gòu)6.1模板

6.5

函數(shù)指針與指針識別（選讀）

6.4模板與類參數(shù)

6.3索引查找與指針數(shù)組

6.2

排序與查找

6.1模板

參數(shù)化程序設(shè)計：

通用的代碼就必須不受數(shù)據(jù)類型的限制，可以把數(shù)據(jù)類型改為一個設(shè)計參數(shù)。這種類型的程序設(shè)計稱為參數(shù)化(parameterize)程序設(shè)計。

這種設(shè)計由模板(template)

完成。包括函數(shù)模板(functiontemplate)和類模板(classtemplate)。6.1.2

類模板與線性表

6.1.1

函數(shù)模板及應(yīng)用

個人理解：模板是從代碼實現(xiàn)的角度為某一類問題提供通用的代碼解決方案。大大減輕了程序員的代碼開發(fā)代價6.1.1

函數(shù)模板及應(yīng)用

<模板參數(shù)表>（templateparameterlist）尖括號中一般（課本說法有誤）不能為空，參數(shù)可以有多個，用逗號分開。模板參數(shù)有兩種情況：模板類型參數(shù)（常用）或者模板非類型參數(shù)。模板類型參數(shù)(templatetypeparameter)代表一種類型，由關(guān)鍵字class或typename（建議用typename

）

后加一個標(biāo)識符構(gòu)成，在這里兩個關(guān)鍵字的意義相同，它們表示后面的參數(shù)名代表一個潛在的內(nèi)置或用戶定義的類型。函數(shù)模板用來創(chuàng)建一個通用函數(shù)，支持多種不同類型形參。函數(shù)模板定義：template<模板參數(shù)表>返回類型

函數(shù)名(形式參數(shù)表){……；}//函數(shù)體函數(shù)模板實例template<typenameT>//T:模板類型參數(shù)intcompare(Ta,Tb){ if(b<a)return1; elseif(a<b)return-1; elsereturn0;}inta,b;...if(0==compare(a,b))... strings1,s2;...if(1==compare(s1,s2))...

typename可以被class替換注意：函數(shù)模板不是普通函數(shù)，是具有特定操作的一類函數(shù)的設(shè)計框架。編譯時模板參數(shù)T被實例化第三章遺留的問題

3.8.1函數(shù)重載【例3.16】

3+5=調(diào)用sum(3,5)函數(shù)sum(3,5)return82.2+5.6=調(diào)用sum(2.2,5.6)函數(shù)doublesum(2.2,5.6)return7.83.5+4+8=調(diào)用sum(3.5,4,8)函數(shù)floatsum(3.5,4.0,8.0)return15.5結(jié)束87.815.5【例3.16】

重載函數(shù)的應(yīng)用。intsum(inta,intb){

returna+b;}Doublesum(doublea,doubleb){

returna+b;}floatsum(floata,floatb,floatc){

returna+b+c;}intmain(){ cout<<"3+5="<<sum(3,5) <<endl; cout<<"2.2+5.6=“ <<sum(2.2,5.6)<<endl; cout<<"3.5+4+8=“ <<sum(3.5,4,8)<<endl;

return0;}思考：重載有沒有需要改進(jìn)的地方？答案template<typenameT>Tsum(Ta,Tb){returna+b;}6.1.1

函數(shù)模板及應(yīng)用【例6.1】用函數(shù)模板求數(shù)組元素中最大值template<typename

Groap>Groapmax(const

Groap*r_array,intsize){

inti;

Groapmax_val=r_array[0];for(i=1;i<size;++i)if(r_array[i]>max_val)max_val=r_array[i];

returnmax_val;}類型參數(shù)Groap在程序編譯時（非運(yùn)行時,課本錯誤）會被各種內(nèi)置（基本）類型或用戶定義類型所置換。模板參數(shù)表的使用與函數(shù)形式參數(shù)表的使用相同，都是位置對應(yīng)。類型和值的置換過程稱為模板實例化(templateinstantiation)。形參size表示r_array數(shù)組的長度。6.1.1

函數(shù)模板及應(yīng)用模板實參推演：函數(shù)模板根據(jù)一組實際類型或（和）值構(gòu)造出獨(dú)立的函數(shù)的過程通常是隱式發(fā)生的，稱為模板實參推演(templateargumentdeduction)。下面完成【例6.1】intia[5]={10,7,14,3,25};doubleda[6]={10.2,7.1,14.5,3.2,25.6,16.8};stringsa[5]={"上海","北京","沈陽","廣州","武漢"};intmain(){

inti=max(ia,5);cout<<"整數(shù)最大值為："<<i<<endl;

doubled=max(da,6);cout<<"實數(shù)最大值為："<<d<<endl;strings=max(sa,5);cout<<"字典排序最大為："<<s<<endl;

return0;}編譯器如何知道具體的參數(shù)類型？6.1.1

函數(shù)模板及應(yīng)用第一次調(diào)用時，Groap被int取代。第二次調(diào)用，Groap被double取代。第三次Groap被string取代。為了判斷用作模板實參的實際類型，編譯器需檢查函數(shù)調(diào)用中提供的函數(shù)實參的類型。ia的類型為int數(shù)組，da的類型為double數(shù)組。都被用來決定每個實例的模板參數(shù)。該過程稱為模板實參推演。

當(dāng)然也可以顯式指定（explicitlyspecify），如：i=max<int>(ia,5);d=max<double>(da,6);這樣可讀性更好。這里數(shù)組名是作為指向數(shù)組首元素的指針進(jìn)行傳遞，數(shù)組長度是由size參數(shù)進(jìn)行傳遞的。模板實參推演過程：非類型模板形參模板形參不必都是類型，可以為非類型形參（補(bǔ)充知識：數(shù)組作為函數(shù)形參）template<typenameT,intN>voidarr_init(T(&arr)[N]){ for(inti=0;i<N;i++)arr[i]=0;}inta[42];doubleb[10];arr_init(a);//顯示調(diào)用：arr_init<int,42>(a);arr_init(b);//顯示調(diào)用：arr_init<double,10>(b);表示什么？數(shù)組名作為函數(shù)參數(shù)傳遞的是數(shù)組的首地址，當(dāng)作普通指針來處理，以下三個聲明等價voidtest(int*arr);voidtest(intarr[]);voidtest(intarr[10]);數(shù)組訪問越界問題；也可以通過引用來傳遞數(shù)組，即傳遞數(shù)組本身（檢查邊界）voidtest(int(&arr)[10]);inti[2]={0,2};intk[10]={3};test(i);//errortest(k);//okint(&arr)[10]:arr指向具有10個int的數(shù)組int&arr[10];一個有10個引用類型(整形)的數(shù)組同理int*arr[10];：具有10個指針元素的數(shù)組；int(*arr)[10];指向具有10個數(shù)據(jù)元素的數(shù)組類型形參和實參的轉(zhuǎn)換1.多個類型形參的實參必須嚴(yán)格完全匹配template<typenameT>intcompare(Ta,Tb);shorts1,s2;intx1,x2;compare(s1,s2);//okcompare(x1,x2);//okcompare(s1,x1);//error不能實例化compare(short,int);2.兩種轉(zhuǎn)換：const轉(zhuǎn)換和數(shù)組或函數(shù)到指針的轉(zhuǎn)換const轉(zhuǎn)換：接受const引用或const指針的函數(shù)可以分別用非const對象或者非const指針來實例化。如果函數(shù)形參接受非引用類型，形參和實參都忽略const數(shù)組或函數(shù)到指針的轉(zhuǎn)換：形參為非引用類型，數(shù)組名當(dāng)作指向第一個元素的指針(了解)template<typenameT>Tfobj(To1,To2);template<typenameT>Tfref(constT&r1,constT&r2);strings1("avalue");conststrings2("anothervalue");fobj(s1,s2);//okconsts2isigoredfref(s1,s2);//ok,non-consts1iscovertedtoconstreferenceinta[10],b[40];fobj(a,b);//ok,T=int*;fref(a,b);//error編寫函數(shù)模板的原則1.模板參數(shù)用const引用.template<typenameT>intcompare(constT&a,constT&b)；可以用于不允許復(fù)制的類型：比如IO類型2.函數(shù)體中如果有比較測設(shè)，進(jìn)來用單一關(guān)系運(yùn)算符 if(a>b)return1; elseif(b>a)return-1; elsereturn0;if(a>b)return1;elseif(a<b)return-1;elsereturn0;設(shè)計模板時，T的類型是什么？ofstreamout1;ofstreamout2=out1;//error不允許兩個或以上的對象指向同一個輸入輸出流思考？template<typenameT>intcompare(constT&a,constT&b){ if(b<a)return1; elseif(a<b)return-1; elsereturn0;}inta,b;...if(0==compare(a,b))... strings1,s2;...if(compare(s1,s2))...char*p1="world",*p2="class";if(1==compare(p1,p2))...

比較的是什么？模板特化模板特化形式關(guān)鍵字template后面接一對空的<>；然后接模板名和<>，<>中指定特化的模板形參；函數(shù)形參表函數(shù)體template<>intcompare<char*>(constchar*const&v1,constchar*const&v2){ returnstrcmp(v1,v2);}inta,b;...if(compare(a,b))... strings1,s2;...if(compare(s1,s2))...char*p1="world",*p2="class";if(compare(p1,p2))...

6.1.1

函數(shù)模板及應(yīng)用在main()函數(shù)中，由調(diào)用函數(shù)模板(functrontemplate)

而生成的函數(shù)，稱為模板函數(shù)(templatefunction)。這兩個概念須分清楚。函數(shù)模板與模板函數(shù)：【例6.2】矩陣運(yùn)算：矩陣轉(zhuǎn)置與矩陣相乘函數(shù)模板。下標(biāo)作為參數(shù)傳遞。解決例5.5程序的通用性問題。6.1.1

函數(shù)模板及應(yīng)用請注意：與函數(shù)聲明不同，函數(shù)模板的聲明必須含變量名。因為兩者編譯過程不一樣，函數(shù)模板必須先轉(zhuǎn)換為模板函數(shù)。template<typenameT1,typenameT2>voidinverse(T1*mat1,T2*mat2,int

a,intb);template<typenameT1,typenameT2>voidmulti(T1*mat1,T2*mat2,T2*result,int

a,

int

b,int

c);template<typenameT>voidoutput(T*mat,char*s,int

a,int

b);注意：mat2和result屬同一類型，均為由具有相同元素數(shù)量的一維數(shù)組所組成的二維數(shù)組。本例為mat[3][4]和result[6][4]。記住數(shù)組最高維是不檢查邊界的。函數(shù)模板的聲明：6.1.2類模板類模板定義：template<模板參數(shù)表>

class類名{……

//類定義體返回類型

成員函數(shù)名1(形參表)；//相當(dāng)于//返回類型

成員函數(shù)名1<模板參數(shù)名表>(形參表)；};

//再次指出分號不可少template<模板參數(shù)表>返回類型

類名<模板參數(shù)名表>::成員函數(shù)名1(形參表){……；//成員函數(shù)1定義體}模板參數(shù)有兩種：模板類型參數(shù)和模板非類型參數(shù)。注意：和函數(shù)模板一樣，類模板的聲明和定義最好放在同一個文件，避免產(chǎn)生編譯錯誤。

6.1.2類模板與線性表

模板非類型參數(shù)由一個普通的參數(shù)聲明構(gòu)成。表示該參數(shù)名代表了一個潛在的常量，企圖修改這種參數(shù)的值是一個錯誤。如數(shù)組類模板，可以有一個數(shù)組長度的非類型參數(shù)：template<typenameT,inti>classarray{ T

vector[i]; intsize;public: array():size(i){}//等效array(){size=i;}見4.4.3節(jié)（不等價） intfind(constT&x)const; ......};

template<typenameT,inti>intarray<T,i>::find(constT&x)const{...}模板非類型參數(shù)：類外必須聲明為函數(shù)模板類模板參數(shù)必須指明無類型聲明

6.1.2類模板與線性表從通用的類模板定義中生成一個具體的類的過程稱為類模板實例化（templateinstantiation），其格式為：類名<類模板實參表>通常與定義對象同時完成：類名<類模板實參數(shù)表>對象名；類模板實例化：例如：字符串類string是basic_string模板類的一個實例

typedefbasic_string<char>string;標(biāo)準(zhǔn)串類模板basic_string實例化為上一章討論的字符串類string。因為字符串中的字符可以是ASCII碼，也可以是中文漢字編碼，還可以是unicode編碼，所以使用類模板是合理的。上例array模板類實例化：array<int,10>arri;//實例化為一個處理int類型array對象arriarray<string,14>arrs;//實例化為一個處理string類型對象

類模板中的友元和成員模板1.非模板類或非模板函數(shù)可以是類模板的友元template<typenameT>classX{friendclassY;friendvoidfun();};類Y的成員可以訪問類模板任意實例的私有和受保護(hù)的成員。2.函數(shù)模板或類模板也可以聲明為類模板的友元template<typenameT>classX{template<classT>friendclassY;template<classT>friendvoidfun();};類模板中的友元和成員模板3.類模板成員函數(shù)可以為模板函數(shù)template<classT>classX{template<classIT>voidfun(ITi);//聲明};類外定義template<classT>template<classIT>voidX<T>::fun(ITi){......}6.1.2類模板與線性表

線性表是數(shù)據(jù)結(jié)構(gòu)中的概念。數(shù)組中除第一個元素外，其他元素有且僅有一個直接前驅(qū)，第一個元素沒有前驅(qū)；除最后一個元素外，其他元素有且僅有一個直接后繼，最后一個元素?zé)o后繼。這樣的特性稱為線性關(guān)系。所議稱數(shù)組元素在一個線性表中。線性表實際包括順序表（數(shù)組）和鏈表（后面章節(jié)）。線性表：273134109658724162189711511181214x013線性表圖例下標(biāo)以存儲整形數(shù)據(jù)為例：類模板與線性表

對順序表的典型操作包括：計算表長度，尋找變量或?qū)ο髕（其類型與表元素相同）在表中的位置（下標(biāo)值），判斷x是否在表中，刪除x，將x插入列表中第i個位置，尋找x的后繼，尋找x的前驅(qū)，判斷表是否空，判斷表是否滿（表滿不能再插入數(shù)據(jù)，否則會溢出，產(chǎn)生不可預(yù)知的錯誤），取第i個元素的值。

這些操作與數(shù)組封裝在一起可以定義一個類，考慮到數(shù)組元素的類型可以各不相同，所以定義為類模板。

273134109658724162189711511181214x013圖b下標(biāo)6.1.2類模板與線性表

由編譯器編譯時分配內(nèi)存的數(shù)組稱為靜態(tài)數(shù)組，數(shù)組的長度是不可改變的。

如果定義了30個元素的數(shù)組，后來需要40個元素，是不可能續(xù)上10個的，必然產(chǎn)生溢出。因系統(tǒng)不檢查數(shù)組邊界，進(jìn)而產(chǎn)生不可預(yù)知的運(yùn)行時錯誤，所以一般采用“大開小用”的方法，即數(shù)組定義的較大，而實用較小。

為防止不可避免的溢出，應(yīng)在添加新數(shù)據(jù)時判斷表是否滿。靜態(tài)數(shù)組：使用靜態(tài)數(shù)組有什么缺點？（程序的通用性角度考慮）6.1.2類模板與線性表1431341096587241621892771185112110131234i圖a下標(biāo)1431341096587241621897118511211013圖b下標(biāo)圖6.1從表中刪除一個數(shù)據(jù)當(dāng)需要在順序表中刪除一個元素時，必須把它后面的元素的數(shù)據(jù)全部順序前移一個位置，否則表中前驅(qū)后繼關(guān)系被破壞。圖6.1表中有11個數(shù)據(jù)。刪去第i個元素的數(shù)據(jù)，就是把第i+1個元素拷入第i個元素，把第i+2個元素拷入第i+1個元素,依此類推，直到最后一個元素（下標(biāo)為10），現(xiàn)在表長度為10。刪除順序表元素：6.1.2類模板與線性表1431341096587241621892771185112110135432i圖a下標(biāo)1273134109658724162189711511181214x013圖b下標(biāo)圖6.2向表中插入一個數(shù)據(jù)當(dāng)需要在順序表的指定位置i插入一個數(shù)據(jù)x時，必須為它騰出這個位置，把從該位置開始向后的所有元素數(shù)據(jù)，后移一個位置，最后才插入。后移時從最后一個元素開始，參見圖6.2?，F(xiàn)在長度為12，這樣的移動也是不可少的，否則新插入的數(shù)據(jù)x會沖掉原來的數(shù)據(jù)，或先移的數(shù)據(jù)沖掉未移的數(shù)據(jù)。添加順序表元素：【例6.3】順序表類模板template<typenameT,intsize>classseqlist{Tslist[size];//存放順序表的數(shù)組

intMaxsize;//最大可容納項數(shù)

intlast;//已存表項的最后位置public:seqlist():Maxsize(size),last(-1){}//初始化為空表

intLength()const{returnlast+1;}//計算表長度

intFind(constT&x)const;//尋找x在表中位置（下標(biāo)）

boolIsIn(constT&x)const;//判斷x是否在表中

boolInsert(constT&x,inti);//x插入到列表中第i個位置處（下標(biāo)）

boolRemove(constT&x);//刪除x

intNext(constT&x);//尋找x的后繼位置

intPrior(constT&x);//尋找x的前驅(qū)位置

boolIsEmpty(){returnlast==-1;}//判斷表是否空

boolIsFull(){returnlast==Maxsize-1;}//判斷表是否滿

constT&Get(inti)const{returni<0||i>last?NULL:slist[i];}//取第i個元素T&operator[](inti);//重載下標(biāo)運(yùn)算符[]()只考慮非const對象};

檢驗主程序６.2排序與查找

6.2.2常用的排序法6.2.1常用查找方法

排序（sorting）：

是最重要的計算應(yīng)用之一。例如查字典，字典中的詞條是按序存放的，我們才能按字母順序找到要查的字。又如圖書館的藏書也是按書的編號有序排列的。在計算機(jī)上數(shù)據(jù)庫里的資料也是有序排列的。查找（search）：

當(dāng)然也是最常見的運(yùn)算，就是在數(shù)據(jù)集合中尋找滿足條件的數(shù)據(jù)對象，找到后進(jìn)一步給出對象的具體信息，在數(shù)據(jù)庫技術(shù)中稱為檢索（retrieval）。6.2.1常用查找方法

順序查找：從第一個元素開始，順序查找直到找到或查到最后一個元素為止。

查找是按關(guān)鍵字（keyword）進(jìn)行?？梢晕ㄒ坏匕奄Y料區(qū)分出來的數(shù)據(jù)被稱為主關(guān)鍵字。如學(xué)生的資料(結(jié)構(gòu)體變量):structstudent{intid;//學(xué)號charname[20];//姓名charsex;//性別intage;//年齡charaddress[60];//家庭地址floateng,phy,math,electron;//英語,物理,數(shù)學(xué)和電子學(xué)成績};學(xué)號可作為主關(guān)鍵字。

如果關(guān)鍵字小的排在前面，我們稱為升序排列，反之為降序排列。這時可以采用對半查找（binarysearch）。

6.2.1常用查找方法lowmidhigh首先安排兩個指針low和high指向首尾兩元素，取mid=(low+high)/2，如mid指向元素是所查找的，則結(jié)束。如果該元素關(guān)鍵字大了，則取low=mid+1，high不變，繼續(xù)查找；如果該元素關(guān)鍵字小了，則取high=mid-1，low不變，繼續(xù)查找。如果查到low>high仍未找到，則失敗，停止。對半查找:low8917131120719212331262925373923查找lowmidhigh2021292623313739midhighlow202123midhigh23成功圖6.3查找成功例16806.2.1常用查找方法—對半查找25781113179192023212629313710查找low39midhigh25781113179lowmidhigh1113179lowmidhigh9lowmidhigh圖6.4查找失敗例注意：low=mid+1和high=mid-1非常重要.0836.2.1常用查找方法【例6.4】對半查找遞歸算法，作為有序表模板類成員函數(shù)。遞歸方法易讀易懂，但效率低。注意遞歸的隱式循環(huán)代碼編寫?！纠?.5】對半查找迭代算法。該例中迭代算法的可讀性也不差，效率要高于遞歸。注意迭代的顯式循環(huán)代碼編寫

的關(guān)鍵點。*本例中出現(xiàn)的成員函數(shù)Binarysearch(T&x)const

，稱為const成員函數(shù)，該函數(shù)保證只讀。相應(yīng)節(jié)點對象重載的比較運(yùn)算符也必須是const?！纠?.4】對半查找遞歸算法，作為有序表模板類成員函數(shù)。遞歸方法易讀易懂，但效率低。注意遞歸的隱式循環(huán)代碼編寫。6.2.1常用查找方法例6.5節(jié)點對象重載的比較運(yùn)算符：template<typenameT>classElement{

Tkey; //其他域省略public:booloperator<(Elementele)const{ returnkey<ele.key;//如果T為用戶自定義類類型，需要重載該運(yùn)算符}voidputkey(constT&k){ key=k;}};//注意這里加了const&const

6.2.1常用查找方法const成員函數(shù)和const對象：const成員函數(shù)：返回類型函數(shù)名(形參表)const;該函數(shù)的this指針?biāo)笇ο鬄槌Ａ?，即它不能修改對象的?shù)據(jù)成員，而且在函數(shù)體內(nèi)只能調(diào)用const成員函數(shù)（它們不會修改對象的數(shù)據(jù)成員），不能調(diào)用其他成員函數(shù)。如果編程時不慎修改對象的數(shù)據(jù)成員，編譯器會報錯。const對象：const類名對象名；表示該對象的數(shù)據(jù)成員均為常量，并僅可訪問const成員函數(shù)（很少用）。6.2.1常用查找方法散列查找（略）：

散列（hash）查找是最快的查找方法。前文介紹的兩種查找方法都是將需查找的關(guān)鍵字值與表中的數(shù)據(jù)元素的關(guān)鍵字值進(jìn)行比較而達(dá)到查找的目的。如果能找到一個函數(shù)f(key)，將關(guān)鍵字經(jīng)過函數(shù)的運(yùn)算轉(zhuǎn)換為數(shù)據(jù)表中的位置，直接將數(shù)據(jù)元素插入在該位置上。在查找中可直接取用該位置的數(shù)據(jù)元素。這樣的組織稱為散列，利用散列技術(shù)查找的方法稱為散列查找，散列查找是一種直接查找。亦用音譯稱哈希查找。課下了解：baidu,google搜索引擎是怎樣實現(xiàn)查找功能的呢？6.6.2常用的排序法排序的概念：排序（sorting）是將數(shù)據(jù)元素的無序序列調(diào)整為一個有序序列。

數(shù)據(jù)元素中一般有多個數(shù)據(jù)項，排序可選擇其中一個可排序的數(shù)據(jù)項（可進(jìn)行比較運(yùn)算）作為依據(jù)，稱為排序關(guān)鍵字。

對高考考生的統(tǒng)計表進(jìn)行排序，可根據(jù)考生的準(zhǔn)考證號，這樣的關(guān)鍵字可以保證排序結(jié)果的唯一性，稱主關(guān)鍵字。

為了便于錄取，也可以按高考總分排序，只可稱關(guān)鍵字,這樣同一分?jǐn)?shù)的人很多，這些人的排名可再取一個次關(guān)鍵字如數(shù)學(xué)或語文分來排序，以減少重復(fù)排名的隨意性。從小到大排序稱升序，反之為降序。

最常見的是插入排序、選擇排序和交換排序。classstudent{stringname,Id;intmath,english;};6.2.2常用的排序法1．插入排序(InsertSorting)(1)直接插入排序的思想是:(以升序為例)當(dāng)插入第i(i>=1)個元素sl[i]時,前面的元素sl[0],sl[1],…,sl[i-1]已經(jīng)排好序,我們將sl[i]的關(guān)鍵字與sl[i-1],sl[i-2],…,的關(guān)鍵碼順序進(jìn)行比較,找到第一個比它小的,則sl[i]插到該元素之后。i0123456temp初始序列[8]67945261[68]7945272[678]945293[6789]45244[46789]5255[456789]226[2456789]直接插入排序算法中用了一個臨時變量temp，要插入的元素放到temp中，這樣插入前各元素后移時允許將該元素沖掉。6.6.2常用的排序法【例6.6】升序直接插入排序算法(算法演示)*(2)對半插入排序（BinaryInsertSort）是用對半查找的思想取代順序查找。對半插入排序要快于插入排序。（略）【例6.7】升序?qū)Π氩迦肱判蛩惴ㄋ惴ㄓ袥]有改進(jìn)的地方？從執(zhí)行效率角度結(jié)合查找算法分析。6.2.2常用的排序法2．交換排序（算法演示）交換排序的基本思想是按關(guān)鍵字兩兩排序?qū)ο?，如果發(fā)生逆序則交換之，直到所有的對象都排好序為止。冒泡排序基本思想?yún)⒁妶D6.6。最左列為最初的情況，最右列為完成后的情況。首先我們從一列數(shù)據(jù)底部開始，相鄰的兩數(shù)據(jù)進(jìn)行比較，小的數(shù)放上面，一趟比較下來，最小的數(shù)據(jù)冒到了最上面。再縮小區(qū)域，按同樣方法繼續(xù)下一趟交換，如果有一趟比較中沒有發(fā)生交換，則已排好序。圖6.6中，第5列就已排好序，若再繼續(xù)下一趟就不會發(fā)生交換。49494949491338383838134965656513383897971365656576139797979713767676767627272727272749’49’49’49’49’49’冒泡排序示例491313131313131338492727272727276538493838383838976538494949494976976549’49’49’49’49’1376976565656565272776977676767649’49’49’7697979797圖6.6從下往上掃描的冒泡程序

6.2.2常用的排序法3．選擇排序（SelectionSort，略）基本思想是：每一趟從待排序的記錄中選出關(guān)鍵字最小的元素，順序放在已排好序的子序列的后面，直到全部記錄排序完成。直接選擇排序（StraightSelectionSort）是最簡單的。此方法的最大優(yōu)點是易讀。缺點是做過的工作和序列的部分有序性利用不上，效率低。選擇排序中也有可能利用到以前的工作的方法，如堆排列（HeapSort）

[49 38 65 97 76 13 27 49’]

13 [38 65 97 76 49 27 49’]

13 27 [65 97 76 49 38 49’]

13 27 38 [97 76 49 65 49’]

13 27 38 49 [76 97 65 49’]

13 27 38 49 49’ [97

65 76]

13 27 38 49 49’ 65 [97

76]

13 27 38 49 49’ 65 76 97

圖6.7直接選擇排序的過程6.3索引查找與指針數(shù)組

指針數(shù)組：

數(shù)據(jù)元素為指針的數(shù)組稱指針數(shù)組。類型*數(shù)組名[size/常量];int*arr[10];arr：包含10個指針元素的數(shù)組注意和指向數(shù)組的指針區(qū)別類型(*數(shù)組名)[size];int(*arr)[10];arr:指向含有10個整形數(shù)據(jù)的一維數(shù)組索引查找（略）：

6.3索引查找與指針數(shù)組字符型指針數(shù)組可以實現(xiàn)字符串?dāng)?shù)組的功能。這些字符串的長度可以不等；所以用指針數(shù)組更方便。如存儲每周7天的英文名稱，可定義一個char*name[7]的一維字符指針數(shù)組，如圖6.9。name[5]name[2]name[0]name[1]name[3]name[4]name[6]“Wednesday”“Friday”“Monday”“Sunday”“Tuesday”“Thursday”“Saturday”圖6.9字符指針數(shù)組指針數(shù)組與字符串：6.4模板與類參數(shù)

模板的通用性：在前文所討論的排序與查找中，模板的通用性得到了很好的體現(xiàn)。關(guān)鍵技術(shù)是數(shù)組的數(shù)據(jù)元素說明為類，并重載小于運(yùn)算符，該運(yùn)算符實際是將元素類對象的比較轉(zhuǎn)化為類對象關(guān)鍵字的比較。因使用標(biāo)準(zhǔn)字符串類string看不見其內(nèi)部構(gòu)成，下面用自定義字符串類來進(jìn)一步闡述這個問題?！纠?.10】冒泡排序算法，關(guān)鍵字為自定義字符串。

【例6.6】中同樣可以用mystring代替標(biāo)準(zhǔn)字符串類string，不過那兒有兩個層次：元素類和字符串類。運(yùn)算符的重載可以由對象成員的重載的運(yùn)算符（或成員）函數(shù)一級一級調(diào)用生成。在類定義中運(yùn)算符和函數(shù)的重載是面向?qū)ο蟪绦蛟O(shè)計實現(xiàn)通用性的非常得力的工具。6.4模板與類參數(shù)

以類對象作為函數(shù)的實參，實現(xiàn)被積函數(shù)(類對象的成員函數(shù))的傳遞：

【例6.12】設(shè)計梯形法求積分的函數(shù)模板。以模板參數(shù)T來引入被積函數(shù)類，由該參數(shù)調(diào)用欲求定積分的函數(shù)【例6.11】設(shè)計梯形法求積分的類模板。求積分的函數(shù)為獨(dú)立的非成員函數(shù)。該方法更簡潔。

6.4模板與類參數(shù)函數(shù)模板常用方式：(1)函數(shù)模板作為類模板的成員函數(shù)，在本類中重載函數(shù)和運(yùn)算符，直接訪問私有數(shù)據(jù)成員，實現(xiàn)通用算法。這是標(biāo)準(zhǔn)的面向?qū)ο蟮姆椒ā?2)獨(dú)立的（非成員函數(shù)）函數(shù)模板處理模板類（或普通類，或普通數(shù)據(jù)），以類模板（或類對象，或普通數(shù)據(jù)）為參數(shù)，借助模板類中重載的函數(shù)或運(yùn)算符，實現(xiàn)通用算法。但間接訪問私有數(shù)據(jù)成員。這也是常見的。6.5函數(shù)指針與指針識別指針內(nèi)置類型intx;int*p=&x;類類型classx;class*p;p=&x;數(shù)組intx[10];int*p=x;函數(shù)intfun();6.5函數(shù)指針與指針識別指向函數(shù)而非指向?qū)ο蟮闹羔槪瘮?shù)指針的類型由其返回類型和形參表來確定，與函數(shù)名無關(guān)。定義方式如下： 返回類型(*指針變量名)(參數(shù)表)例：bool(*pf)(conststring&,conststring&);指針pf指向返回值為bool類型且?guī)в袃蓚€為conststring&形參的函數(shù)。注意：與下面聲明的區(qū)別()優(yōu)先級高于* bool*pf(conststring&,conststring&);

函數(shù)指針：6.5函數(shù)指針與指針識別typedef簡化函數(shù)指針的定義,格式如下typedefbool(*pFun)(conststring&,conststring&);pFun:指向函數(shù)的指針類型名定義和初始化如下：boolcompare(conststring&,conststring&);pFunpf1=0;pFunpf2=compare;//隱式pf1=pf2;pf2=&compare;//顯式注意：函數(shù)指針可以初始化為0，且指向不同類型的函數(shù)指針不能相互轉(zhuǎn)化。6.5函數(shù)指針與指針識別函數(shù)指針的使用：【例6.13】梯形法求積分的函數(shù)integer()作為通用函數(shù)，可求任一函數(shù)的定積分。(課堂演示)compare("ab","cd");//直接調(diào)用(*pf1)("ab","cd");//ok,顯式調(diào)用pf1("ab","cd");//ok,隱式調(diào)用typedefbool(*pFun)(conststring&,conststring&);boolcompare1(conststring&,conststring&);intcompare2(conststring&,conststring&);pFunpf1=compare1;//okpFunpf1=compare2;//error6.5.2指向類成員的指針（選讀）

在類對象中有隱含的this指針，用以正確訪問成員函數(shù)。所以指向類成員函數(shù)的指針有其特殊性。

指向類成員函數(shù)的指針：

成員函數(shù)有一個非成員函數(shù)沒有的屬性：它所屬的類（class）。所以指向成員函數(shù)的指針需要三個方面的匹配：參數(shù)的類型和個數(shù)，返回類型和所屬的類類型。6.5.2指向類成員的指針（選讀）定義指向類成員函數(shù)的指針的說明及初始化：必須在三個方面嚴(yán)格匹配(1)函數(shù)形參類型和數(shù)目，包括函數(shù)是否為const(2)函數(shù)返回類型(3)所屬類的類型以指向商品類GetPrice()函數(shù)的指針為例：float

(CGoods::*pf)()const=&CGoods::GetPrice;不能寫成float

(CGoods::*pf)()const=CGoods::GetPrice;//錯誤上述定義可簡化為typedeffloat

(CGoods::*pFun)()const;pFunpf=&CGoods::GetPrice;

classCGoods{floatGetPrice()const;};6.5.2指向類成員的指針（選讀）成員函數(shù)指針的用法(綁定)：CGoodscar,*p=&car;(car.*pf)();//注意不能寫成這樣car.*pf();編譯錯誤()不能省略//將指針pf與對象car綁定，最終等效調(diào)用car.GetPrice();(p->*pf)();//指針方式調(diào)用上式表示指針pf與對象car綁定，指向了car.GetPrice()。所以指向成員函數(shù)的指針存儲的不是成員函數(shù)的地址，綁定后才獲得地址。課本錯誤：也可以用對象代替類進(jìn)行初始化，效果一樣：CGoodscar,motor;float(CGoods::*pf)()=motor.GetPrice;typedeffloat

(CGoods::*pFun)()const;pFunpf=&CGoods::GetPrice;//&不可省error:ISOC++forbidstakingtheaddressofaboundmemberfunctiontoformapointertomemberfunction.6.5.2指向類成員的指針（選讀）普通函數(shù)指針int(*p)(double);成員函數(shù)指針int(className::*p)(double);

普通函數(shù)指針存儲函數(shù)的地址，可以直接用來調(diào)用指定函數(shù)。成員函數(shù)指針必須首先被綁定在一個對象或指針上，才能獲得被調(diào)用對象的this指針，然后才能調(diào)用指針?biāo)赶虻某蓡T函數(shù)。6.5.3指針的識別方法（選讀）

說明中包括多種說明符容易造成閱讀和理解的困難。一種理解和構(gòu)造對象說明的方法是：先撇開標(biāo)識符，按從右到左的順序逐個解釋每個說明符，如果有括號則改變解釋的先后，先解釋括號內(nèi)再解釋擴(kuò)號外。例如：int*arrp[5];---->int*[5];按下列順序理解：五個元素的數(shù)組、每個元素是一個指針、指針指向整型，所以arrp是一個有五個整型指針作為數(shù)組元素的數(shù)組。int(*parr)[5];---->int(*)[5];是一個指針，指針指向一個包含五個元素的數(shù)組，每個元素是一個整型，所以parr是一個指向五個整型數(shù)的數(shù)組的指針。復(fù)雜說明閱讀和理解的方法：6.5.3指針的識別方法（選讀）答案：inti;是一個整型的變量；int*ip;是一個指向整型變量的指針，即ip中存儲的是另一個整型變量的地址；intf();是一個返回整型值的函數(shù)；int*fp();是一個返回整型指針的函數(shù)，即fp返回的是一個指向整型變量的指針；int(*pf)();是一個指向返回整型值的函數(shù)的指針；復(fù)雜說明的實例：inti,*ip,f(),*fp(),(*pf)();6.5.3指針的識別方法（選讀）答案：pfp是一個指向函數(shù)的指針，該函數(shù)返回一個整型指針；a是一個有五個整型元素的數(shù)組；ap是一個指針數(shù)組，每個元素是一個指向整型的指針；pa是一個指向整型數(shù)組的指針，該數(shù)組有五個整型元素；fap是一個指針數(shù)組，每個指針指向一個返回int的無參函數(shù)fpa是一個指向數(shù)組的指針，該數(shù)組的每個元素都是一個指向函數(shù)的指針，而所指的函數(shù)的返回值是整型。復(fù)雜說明的實例：int*(*pfp)(),a[5],*ap[5],(*pa)[5],(*fap[5])(),(*(*fpa)[5])();int(*(*fap)[])();1.(*fap)是個指針;2(*fap)[]:指向一個數(shù)組;3int(*(*fap)[])();數(shù)組的元素是指向返回類型為int的無參函數(shù)指針6.5.3指針的識別方法（選讀）intf1(){return1;}intf2(){return2;}intf3(){return3;}int(*(*pf)[3])();int(*arr[3])()={f1,f2,f3};//arr[0]=f1;arr[1]=f2;arr[2]=f3;pf=&arr; //一維數(shù)組arr的引用cout<<(*pf)[2]()<<endl;//callsf3();cout<<(arr[2])()<<endl;//等價調(diào)用6.5.3指針的識別方法（選讀）返回指向函數(shù)的指針int(*pf(int))(int*,int);閱讀技巧：從名字開始，從里向外理解pf(int)pf為一個函數(shù)，帶一個int形參，返回值為：int(*)(int*,int);指向函數(shù)的指針，函數(shù)返回int并帶int*和int形參利用typedef簡化函數(shù)指針的定義typedefint(FF*)(int*,int);FFpf(int);//pf返回一個指向函數(shù)的指針第六章

模板與數(shù)據(jù)結(jié)構(gòu)作業(yè)：將學(xué)生成績管理系統(tǒng)中的成績管理類設(shè)計成類模板classStudent{private:stringm_id,m_name;intm_math,m_eng,m_phy;};template<typenameT>classManagement{friendclassStudent;//可以訪問Student類私有數(shù)據(jù)private:vector<T>mv_stu;//vector<Student>stu;//存儲所有學(xué)生的信息};【例6.2】矩陣運(yùn)算template<typenameT1,typenameT2>voidinverse(T1*mat1,T2*mat2,inta,intb){

inti,j;

for(i=0;i<b;i++)for(j=0;j<a;j++)

mat2[j][i]=mat1[i][j];

return;}template<typenameT1,typenameT2>voidmulti(T1*mat1,T2*mat2,T2*result,inta,intb,

intc){

inti,j,k;

for(i=0;i<a;i++)for(j=0;j<c;j++){result[i][j]=0;

for(k=0;k<b;k++)

result[i][j]+=mat1[i][k]*mat2[k][j];}

return;}【例6.2】矩陣運(yùn)算template<typenameT>voidoutput(T*mat,char*s,

inta,intb){

inti,j;cout<<s<<endl;

for(i=0;i<a;i++){

for(j=0;j<b;j++)cout<<setw(4)<<mat[i][j]<<"";cout<<endl;}

return;}【例6.2】矩陣運(yùn)算intmain(){

intmiddle[6][3],result[6][4];

intmatrix1[3][6]={8,10,12,23,1,3,5,7,9,2,4,6,34,45,56,2,4,6};

intmatrix2[3][4]={3,2,1,0,-1,-2,9,8,7,6,5,4};

char*s1="result";

char*s2="middle";inverse(matrix1,middle,6,3);//顯式：inverse<int[6],int[3]>(matrix1,middle,6,3);multi(middle,matrix2,result,6,3,4);//顯式：multi<int[3],int[4]>(middle,matrix2,result,6,3,4);output(matrix1,"matrix1",3,6);output(middle,s2,6,3);output(matrix2,"matrix2",3,4);output(result,s1,6,4);return0;}【例6.3】順序表類模板template<typenameT,intsize>intseqlist<T,size>::Find(T&x)const{//const表示該函數(shù)的this指針為const，即被訪問對象的數(shù)//據(jù)不能被修改。如被修改編譯器會警告，防止編程時失誤。

inti=0;

while(i<=last&&slist[i]!=x)++i;//順序查找是否有x

if(i>last)return-1;//未找到，返回-1elsereturni;//找到，返回下標(biāo)}【例6.3】順序表類模板template<typenameT,intsize>boolseqlist<T,size>::IsIn(T&x){

int

i=-1;

boolfound=0;

while(i<=last&&!found){//換了一種方法來查找

if(slist[++i]==x)found=1;//找到}returnfound;}template<typenameT,intsize>T&seqlist<T,size>::operator[](inti){

if(i>last||i<0){

//(i>last+1||i<0||i>=Maxsize)last永遠(yuǎn)小于Maxsizecout<<"下標(biāo)出界！"<<endl;

exit(1);//程序運(yùn)行結(jié)束，不合理，動態(tài)內(nèi)存無法釋放}

returnslist[i];}【例6.3】順序表類模板template<typenameT,intsize>

boolseqlist<T,size>::Insert(T&x,inti){

intj;if(i<0||i>last+1||last==Maxsize-1)return

false;

//插入位置不合理，不能插入（健壯性）

else{last++;

for(j=last;j>i;j--)slist[j]=slist[j-1];

//從表最后位置向前依次后移，空出指定位置來slist[i]=x;

returntrue;}}【例6.3】順序表類模板template<typenameT,intsize>

boolseqlist<T,size>::Remove(T&x){

inti=Find(x)