1、第六章 模板與數(shù)據(jù)結(jié)構(gòu),模板是建立通用的與數(shù)據(jù)類(lèi)型無(wú)關(guān)的算法的重要手段，在學(xué)習(xí)與數(shù)據(jù)結(jié)構(gòu)相關(guān)的表、排序與查找的知識(shí)和算法時(shí)，要逐步熟悉函數(shù)模板和類(lèi)模板的編程方法。,第六章模板與數(shù)據(jù)結(jié)構(gòu),6.1 模板,6.5 函數(shù)指針與指針識(shí)別（選讀）,6.4 模板與類(lèi)參數(shù),用UML類(lèi)圖表示模板,6.2 排序與查找,6.3 索引查找與指針數(shù)組,6.1 模板,參數(shù)化程序設(shè)計(jì)： 通用的代碼就必須不受數(shù)據(jù)類(lèi)型的限制，可以把數(shù)據(jù)類(lèi)型改為一個(gè)設(shè)計(jì)參數(shù)。這種類(lèi)型的程序設(shè)計(jì)稱為參數(shù)化(parameterize) 程序設(shè)計(jì)。 這種設(shè)計(jì)由模板(template) 完成。包括函數(shù)模板(function template)和類(lèi)模板(

2、class template)。,6.1.2 類(lèi)模板與線性表,6.1.1 函數(shù)模板及應(yīng)用,6.1.1 函數(shù)模板及應(yīng)用,（template parameter list）尖括號(hào)中不能為空，參數(shù)可以有多個(gè)，用逗號(hào)分開(kāi)。模板參數(shù)主要是模板類(lèi)型參數(shù)。,模板類(lèi)型參數(shù)(template type parameter)代表一種類(lèi)型，由關(guān)鍵字 class 或 typename（建議用typename ） 后加一個(gè)標(biāo)識(shí)符構(gòu)成，在這里兩個(gè)關(guān)鍵字的意義相同，它們表示后面的參數(shù)名代表一個(gè)潛在的內(nèi)置或用戶定義的類(lèi)型。,函數(shù)模板用來(lái)創(chuàng)建一個(gè)通用函數(shù)，支持多種不同類(lèi)型形參。 函數(shù)模板定義： template返回類(lèi)型 函數(shù)名

3、(形式參數(shù)表) ； /函數(shù)體,6.1.1 函數(shù)模板及應(yīng)用,【例6.1】用函數(shù)模板求數(shù)組元素中最大值 template Groap max(const Groap *r_array,int size) int i; Groap max_val=r_array0; for (i=1;imax_val) max_val=r_arrayi; return max_val; 類(lèi)型參數(shù)Groap在程序運(yùn)行中會(huì)被各種內(nèi)置（基本）類(lèi)型或用戶定義類(lèi)型所置換。 模板參數(shù)表的使用與函數(shù)形式參數(shù)表的使用相同，都是位置對(duì)應(yīng)。類(lèi)型和值的置換過(guò)程稱為模板實(shí)例化 (template instantiation)。 形參siz

4、e 表示 r_array 數(shù)組的長(zhǎng)度。,6.1.1 函數(shù)模板及應(yīng)用,模板實(shí)參推演： 函數(shù)模板根據(jù)一組實(shí)際類(lèi)型或（和）值構(gòu)造出獨(dú)立的函數(shù)的過(guò)程通常是隱式發(fā)生的，稱為模板實(shí)參推演(template argument deduction)。 下面完成【例6.1】 int ia5=10,7,14,3,25; double da6=10.2,7.1,14.5,3.2,25.6,16.8; string sa5=上海,北京,沈陽(yáng),廣州,武漢; int main() int i=max(ia,5);cout 整數(shù)最大值為：iendl; double d=max(da,6);cout 實(shí)數(shù)最大值為：dendl

5、; string s=max(sa,5);cout 字典排序最大為：sendl; return 0; ,6.1.1 函數(shù)模板及應(yīng)用,第一次調(diào)用時(shí)，Groap被int取代。第二次調(diào)用，Groap 被double取代。第三次Groap 被string取代。為了判斷用作模板實(shí)參的實(shí)際類(lèi)型，編譯器需檢查函數(shù)調(diào)用中提供的函數(shù)實(shí)參的類(lèi)型。ia 的類(lèi)型為int 數(shù)組，da為double 數(shù)組，sa為string數(shù)組。都被用來(lái)決定每個(gè)實(shí)例的模板參數(shù)。該過(guò)程稱為模板實(shí)參推演。,當(dāng)然也可以顯式指定（explicitly specify），如： i=max(ia,5); d=max(da,6); s=max(sa,

6、5); 這樣可讀性更好。這里數(shù)組名是作為指向數(shù)組首元素的指針進(jìn)行傳遞，數(shù)組長(zhǎng)度是由size參數(shù)進(jìn)行傳遞的。,模板實(shí)參推演過(guò)程：,6.1.1 函數(shù)模板及應(yīng)用,在main()函數(shù)中，由調(diào)用函數(shù)模板(function template) 而生成的函數(shù)，稱為模板函數(shù)(template function)。這兩個(gè)概念須分清楚。,函數(shù)模板與模板函數(shù)：,【例6.2】矩陣運(yùn)算：矩陣轉(zhuǎn)置與矩陣相乘函數(shù)模板。下標(biāo)作為參數(shù)傳遞。解決例5.5程序的通用性問(wèn)題。,6.1.1 函數(shù)模板及應(yīng)用,請(qǐng)注意：與函數(shù)聲明不同，函數(shù)模板的聲明必須含變量名。因?yàn)閮烧呔幾g過(guò)程不一樣，函數(shù)模板必須先轉(zhuǎn)換為模板函數(shù)。 template vo

7、id inverse(T1 *mat1, T2 *mat2,int a,int b); template void multi(T1 *mat1,T2 *mat2,T2 *result,int a, int b,int c); template void output(T *mat,char*s,int a,int b); 注意：mat2和result屬同一類(lèi)型，均為由具有相同元素?cái)?shù)量的一維數(shù)組所組成的二維數(shù)組。本例為mat34和result64。記住數(shù)組最高維是不檢查邊界的。,函數(shù)模板的聲明：,6.1.2 類(lèi)模板與線性表,類(lèi)模板定義： template class 類(lèi)名 /類(lèi)定義體 ; /再

8、次指出分號(hào)不可少 template 返回類(lèi)型 類(lèi)名:成員函數(shù)名1(形參表) ；/成員函數(shù)定義體 template 返回類(lèi)型 類(lèi)名:成員函數(shù)名n(形參表) ；/成員函數(shù)n定義體 模板參數(shù)有兩種：模板類(lèi)型參數(shù)和模板非類(lèi)型參數(shù)。,6.1.2 類(lèi)模板與線性表,模板非類(lèi)型參數(shù)由一個(gè)普通的參數(shù)聲明構(gòu)成。表示該參數(shù)名代表了一個(gè)潛在的常量，企圖修改這種參數(shù)的值是一個(gè)錯(cuò)誤。如數(shù)組類(lèi)模板，可以有一個(gè)數(shù)組長(zhǎng)度的非類(lèi)型參數(shù)： templateclass array T vectori; int size; public: array():size(i) /等效array()size=i;參見(jiàn)4.4.3節(jié) . . ;,

9、模板非類(lèi)型參數(shù)：,6.1.2 類(lèi)模板與線性表,注意： 在類(lèi)外定義的類(lèi)模板中的成員函數(shù)必須是函數(shù)模板。這樣的成員函數(shù)只有在被調(diào)用（或取地址）時(shí)才被實(shí)例化。成員函數(shù)模板定義中，指定成員函數(shù)所在類(lèi)域的類(lèi)型名后跟的中成員，與類(lèi)模板的中的類(lèi)型參數(shù)名相同，但不加 typename 或class。,與包含對(duì)象成員的構(gòu)造函數(shù)類(lèi)似，實(shí)際是一個(gè)模板實(shí)例化的類(lèi)型實(shí)參表，所以不加 typename 或class。,6.1.2 類(lèi)模板與線性表,從通用的類(lèi)模板定義中生成類(lèi)的過(guò)程稱為模板實(shí)例化（template instantiation），其格式為： typedef 類(lèi)名 類(lèi)實(shí)例名； 也可以與定義對(duì)象同時(shí)完成： 類(lèi)名 對(duì)

10、象名；,模板實(shí)例化：,例如：標(biāo)準(zhǔn)串類(lèi)模板basic_string，它提供了復(fù)制、查找等典型串操作。它包含在頭文件中。文件中包括有： typedef basic_string string; 標(biāo)準(zhǔn)串類(lèi)模板basic_string實(shí)例化為上一章討論的字符串類(lèi)string。因?yàn)樽址械淖址梢允茿SCII碼，也可以是中文漢字編碼，還可以是unicode編碼，所以使用類(lèi)模板是合理的。,6.1.2 類(lèi)模板與線性表,線性表是數(shù)據(jù)結(jié)構(gòu)中的概念。數(shù)組中除第一個(gè)元素外，其他元素有且僅有一個(gè)直接前驅(qū)，第一個(gè)元素沒(méi)有前驅(qū)；除最后一個(gè)元素外，其他元素有且僅有一個(gè)直接后繼，最后一個(gè)元素?zé)o后繼。這樣的特性稱為線性關(guān)系。

11、所以稱數(shù)組元素在一個(gè)線性表中。線性表實(shí)際包括順序表（數(shù)組）和鏈表。,對(duì)順序表的典型操作包括：計(jì)算表長(zhǎng)度，尋找變量或?qū)ο髕（其類(lèi)型與表元素相同）在表中的位置（下標(biāo)值），判斷x是否在表中，刪除x，將x插入列表中第i個(gè)位置，尋找x的后繼，尋找x的前驅(qū)，判斷表是否空，判斷表是否滿（表滿不能再插入數(shù)據(jù)，否則會(huì)溢出，產(chǎn)生不可預(yù)知的錯(cuò)誤），取第i個(gè)元素的值。,這些操作與數(shù)組封裝在一起可以定義一個(gè)類(lèi)，考慮到數(shù)組元素的類(lèi)型可以各不相同，所以定義為類(lèi)模板。,線性表：,6.1.2 類(lèi)模板與線性表,由編譯器編譯時(shí)分配內(nèi)存的數(shù)組稱為靜態(tài)數(shù)組，數(shù)組的長(zhǎng)度是不可改變的。 如果定義了30個(gè)元素的數(shù)組，后來(lái)需要40個(gè)元素，是不

12、可能續(xù)上10個(gè)的，必然產(chǎn)生溢出。因系統(tǒng)不檢查數(shù)組邊界，進(jìn)而產(chǎn)生不可預(yù)知的運(yùn)行時(shí)錯(cuò)誤，所以一般采用“大開(kāi)小用”的方法，即數(shù)組定義的較大，而實(shí)用較小。 為防止不可避免的溢出，應(yīng)在添加新數(shù)據(jù)時(shí)判斷表是否滿。在順序表類(lèi)模板中，添加了兩個(gè)數(shù)據(jù)成員專門(mén)用來(lái)完成這項(xiàng)任務(wù)：最大可容納項(xiàng)數(shù)和已用表項(xiàng)的最后位置。,靜態(tài)數(shù)組：,6.1.2 類(lèi)模板與線性表,當(dāng)需要在順序表中刪除一個(gè)元素時(shí)，必須把它后面的元素的數(shù)據(jù)全部順序前移一個(gè)位置，否則表中前驅(qū)后繼關(guān)系被破壞。圖6.1表中有11個(gè)數(shù)據(jù)。刪去第i個(gè)元素的數(shù)據(jù)，就是把第i+1個(gè)元素拷入第i個(gè)元素，把第i+2個(gè)元素拷入第i+1個(gè)元素,依此類(lèi)推，直到最后一個(gè)元素（下標(biāo)為10

13、），現(xiàn)在表長(zhǎng)度為10。,刪除順序表元素：,6.1.2 類(lèi)模板與線性表,圖6.2 向表中插入一個(gè)數(shù)據(jù),當(dāng)需要在順序表的指定位置i 插入一個(gè)數(shù)據(jù)x時(shí)，必須為它騰出這個(gè)位置，把從該位置開(kāi)始向后的所有元素?cái)?shù)據(jù)，后移一個(gè)位置，最后才插入。后移時(shí)從最后一個(gè)元素開(kāi)始，參見(jiàn)圖6.2?，F(xiàn)在長(zhǎng)度為12，這樣的移動(dòng)也是不可少的，否則新插入的數(shù)據(jù)x會(huì)沖掉原來(lái)的數(shù)據(jù)，或先移的數(shù)據(jù)沖掉未移的數(shù)據(jù)。,添加順序表元素：,【例6.3】順序表類(lèi)模板,template class seqlist T slistsize; /存放順序表的數(shù)組 int Maxsize; /最大可容納項(xiàng)數(shù) int last; /已存表項(xiàng)的最后位置 pu

14、blic: seqlist()last=-1;Maxsize=size; /初始化為空表 int Length() constreturn last+1; /計(jì)算表長(zhǎng)度 int Find(T /重載下標(biāo)運(yùn)算符,檢驗(yàn)主程序,用UML類(lèi)圖表示模板,模板參數(shù)化元素（parameterized element） 在UML中，模板是對(duì)一個(gè)帶有一個(gè)或多個(gè)未綁定的形式參數(shù)的元素的描述符。因此它定義了一系列的潛在元素，其中每個(gè)元素都通過(guò)把參數(shù)綁定到實(shí)際值來(lái)說(shuō)明。 模板類(lèi)是最常用的參數(shù)化元素，與C+的類(lèi)模板對(duì)應(yīng)得十分完美，參數(shù)有類(lèi)型參數(shù)和非類(lèi)型參數(shù)（代表潛在的常量）。模板類(lèi)的圖示方法是在類(lèi)圖的右上角加一個(gè)虛線框

15、，參數(shù)填在框內(nèi)。指定形式參數(shù)后由UML模板類(lèi)產(chǎn)生相關(guān)類(lèi)，稱為綁定（bind），即C+的模板實(shí)例化。相關(guān)類(lèi)與模板類(lèi)存在綁定依賴關(guān)系，用相關(guān)類(lèi)指向模板類(lèi)的虛箭頭表示，虛線邊加標(biāo)bind和圓括號(hào)中的實(shí)在參數(shù)。綁定可以是顯式的，相關(guān)類(lèi)有自己的名字；也可以是隱式的，無(wú)名的類(lèi)。,用UML類(lèi)圖表示模板,下圖是線性表類(lèi)模板的UML圖，同時(shí)給出綁定產(chǎn)生的新類(lèi)64元素的整型線性表。對(duì)應(yīng)C+的模板實(shí)例化。,.2 排序與查找,6.2.2 常用的排序法,6.2.1 常用查找方法,排序（sorting）： 是最重要的計(jì)算應(yīng)用之一。例如查字典，字典中的詞條是按序存放的，我們才能按字母順序找到要查的字。又如圖書(shū)館的藏書(shū)也是按

16、書(shū)的編號(hào)有序排列的。在計(jì)算機(jī)上數(shù)據(jù)庫(kù)里的資料也是有序排列的。 查找（search）： 當(dāng)然也是最常見(jiàn)的運(yùn)算，就是在數(shù)據(jù)集合中尋找滿足條件的數(shù)據(jù)對(duì)象，找到后進(jìn)一步給出對(duì)象的具體信息，在數(shù)據(jù)庫(kù)技術(shù)中稱為檢索（retrieval）。,6.2.1 常用查找方法,順序查找： 從第一個(gè)元素開(kāi)始，順序查找直到找到或查到最后一個(gè)元素為止。 查找是按關(guān)鍵字（key word）進(jìn)行。可以唯一地把資料區(qū)分出來(lái)的數(shù)據(jù)被稱為主關(guān)鍵字。如學(xué)生的資料(結(jié)構(gòu)體變量): struct student int id ; /學(xué)號(hào) char name20; / 姓名 char sex; / 性別 int age; / 年齡 char

17、 address60; /家庭地址 float eng, phy,math , electron;/英語(yǔ),物理,數(shù)學(xué)和電子學(xué)成績(jī) ; 學(xué)號(hào)可作為主關(guān)鍵字。 如果關(guān)鍵字小的排在前面，我們稱為升序排列，反之為降序排列。這時(shí)可以采用對(duì)半查找（binary search）。,6.2.1 常用查找方法,首先安排兩個(gè)指針low和high指向首尾兩元素，取mid= (low+ high)/2，如mid指向元素是所查找的，則結(jié)束。如果該元素關(guān)鍵字大了，則取low=mid +1， high不變，繼續(xù)查找；如果該元素關(guān)鍵字小了，則取 high=mid-1，low不變，繼續(xù)查找。如果查到lowhigh仍未找到，則失

18、敗，停止。,對(duì)半查找:,6.2.1 常用查找方法對(duì)半查找,注意：low=mid+1和high=mid-1非常重要，沒(méi)有加和減時(shí)，可能數(shù)據(jù)存在而找不到。如在圖6.3中，如果找到了僅剩20、21、23這一步，這時(shí)取low=mid，則剩下21、23，mid = (low + high)/2,得mid = low ,下一步low = mid ,還是剩下21、23，mid 永遠(yuǎn)不能指向23，永遠(yuǎn)找不到23了。,6.2.1 常用查找方法,【例6.4】對(duì)半查找遞歸算法，作為有序表模板類(lèi)成員函數(shù)。 遞歸方法易讀易懂，但效率低。注意遞歸的隱式循環(huán)代碼編寫(xiě)。,【例6.5】對(duì)半查找迭代算法。 該例中迭代算法的可讀性

19、也不差，效率要高于遞歸。注意迭代的顯式循環(huán)代碼編寫(xiě) 的關(guān)鍵點(diǎn)。 *本例中出現(xiàn)的成員函數(shù)Binarysearch(T / 其他域省略 public: bool operator(Element ele)const return keyele.key; void putkey(int k) key=k; ; /注意這里加了const,6.2.1 常用查找方法,const成員函數(shù)和const對(duì)象： const成員函數(shù)： 返回類(lèi)型 函數(shù)名(形參表) const; 該函數(shù)的this指針?biāo)笇?duì)象為常量，即它不能修改對(duì)象的數(shù)據(jù)成員，而且在函數(shù)體內(nèi)只能調(diào)用const成員函數(shù)（它們不會(huì)修改對(duì)象的數(shù)據(jù)成員），不能

20、調(diào)用其他成員函數(shù)。如果編程時(shí)不慎修改對(duì)象的數(shù)據(jù)成員，編譯器會(huì)報(bào)錯(cuò)。 const對(duì)象： const 類(lèi)名 對(duì)象名； 表示該對(duì)象的數(shù)據(jù)成員均為常量，并僅可訪問(wèn)const成員函數(shù)。,6.2.1 常用查找方法,散列查找： 散列（hash）查找是最快的查找方法。前文介紹的兩種查找方法都是將需查找的關(guān)鍵字值與表中的數(shù)據(jù)元素的關(guān)鍵字值進(jìn)行比較而達(dá)到查找的目的。如果能找到一個(gè)函數(shù) f(key)，將關(guān)鍵字經(jīng)過(guò)函數(shù)的運(yùn)算轉(zhuǎn)換為數(shù)據(jù)表中的位置，直接將數(shù)據(jù)元素插入在該位置上。在查找中可直接取用該位置的數(shù)據(jù)元素。這樣的組織稱為散列，利用散列技術(shù)查找的方法稱為散列查找，散列查找是一種直接查找。亦用音譯稱哈希查找。,6.6

21、.2 常用的排序法,排序的概念： 排序（sorting）是數(shù)據(jù)處理中經(jīng)常使用的一種重要運(yùn)算。其功能是將數(shù)據(jù)元素的無(wú)序序列調(diào)整為一個(gè)有序序列。 數(shù)據(jù)元素中一般有多個(gè)數(shù)據(jù)項(xiàng)，排序可選擇其中一個(gè)可排序的數(shù)據(jù)項(xiàng)（可進(jìn)行比較運(yùn)算）作為依據(jù)，稱為排序關(guān)鍵字。 對(duì)高考考生的統(tǒng)計(jì)表進(jìn)行排序，可根據(jù)考生的準(zhǔn)考證號(hào)，這樣的關(guān)鍵字可以保證排序結(jié)果的唯一性，稱主關(guān)鍵字。 為了便于錄取，也可以按高考總分排序，只可稱關(guān)鍵字,這樣同一分?jǐn)?shù)的人很多，這些人的排名可再取一個(gè)次關(guān)鍵字如數(shù)學(xué)或語(yǔ)文分來(lái)排序，以減少重復(fù)排名的隨意性。從小到大排序稱升序，反之為降序。 最常見(jiàn)的是插入排序、選擇排序和交換排序。,6.2.2 常用的排序法,

22、1插入排序(Insert Sorting) (1)直接插入排序的思想是:(以升序?yàn)槔?當(dāng)插入第i(i=1)個(gè)元素sli時(shí),前面的元素sl0,sl1,sli-1已經(jīng)排好序,我們將sli的關(guān)鍵字與sli-1, sli-2,的關(guān)鍵碼順序進(jìn)行比較,找到第一個(gè)比它小的,則sli插到該元素之后。,直接插入排序算法中用了一個(gè)臨時(shí)變量temp，要插入的元素放到temp中，這樣插入前各元素后移時(shí)允許將該元素沖掉。,6.6.2 常用的排序法,【例6.6】升序直接插入排序算法,*(2)對(duì)半插入排序（Binary Insert Sort）是用對(duì)半查找的思想取代順序查找。對(duì)半插入排序要快于插入排序。,【例6.7】升序?qū)?/p>

23、半插入排序算法,6.2.2 常用的排序法,圖6.6從下往上掃描的冒泡程序,2交換排序 交換排序的基本思想是按關(guān)鍵字兩兩排序?qū)ο?，如果發(fā)生逆序則交換之，直到所有的對(duì)象都排好序?yàn)橹埂?冒泡排序基本思想?yún)⒁?jiàn)圖6.6。最左列為最初的情況，最右列為完成后的情況。首先我們從一列數(shù)據(jù)底部開(kāi)始，相鄰的兩數(shù)據(jù)進(jìn)行比較，小的數(shù)放上面，一趟比較下來(lái)，最小的數(shù)據(jù)冒到了最上面。再縮小區(qū)域，按同樣方法繼續(xù)下一趟交換，如果有一趟比較中沒(méi)有發(fā)生交換，則已排好序。圖6.6中，第5列就已排好序，若再繼續(xù)下一趟就不會(huì)發(fā)生交換。,6.2.2 常用的排序法,3選擇排序（Selection Sort） 基本思想是：每一趟從待排序的記錄中

24、選出關(guān)鍵字最小的元素，順序放在已排好序的子序列的后面，直到全部記錄排序完成。直接選擇排序（Straight Selection Sort）是最簡(jiǎn)單的。此方法的最大優(yōu)點(diǎn)是易讀。缺點(diǎn)是做過(guò)的工作和序列的部分有序性利用不上，效率低。選擇排序中也有可能利用到以前的工作的方法，如堆排列（Heap Sort）,4938659776132749 1338659776492749 1327659776493849 1327389776496549 1327384976976549 1327384949976576 1327384949659776 1327384949657697 圖6.7直接選擇排序的過(guò)程,

25、6.3 索引查找與指針數(shù)組,指針數(shù)組： 數(shù)據(jù)元素為指針的數(shù)組稱指針數(shù)組 。 索引查找： 索引，就象一本書(shū)的目錄，找到標(biāo)題，再看一下頁(yè)號(hào)，立即可以翻到。如果每一個(gè)查找對(duì)象的數(shù)據(jù)元素很大，比如一個(gè)學(xué)生的簡(jiǎn)歷，要排序也挺麻煩，去查找也不方便。如果每位同學(xué)的簡(jiǎn)歷對(duì)應(yīng)一個(gè)指針，構(gòu)成一個(gè)數(shù)組，而把學(xué)生學(xué)號(hào)作為數(shù)組元素的下標(biāo)，這樣就形成了一個(gè)指針數(shù)組，找到學(xué)號(hào)對(duì)應(yīng)元素，其所保存的指針值，即簡(jiǎn)歷的地址，查找起來(lái)要方便多了，稱索引查找（Index Search）。參見(jiàn)圖6.8。,圖6.8用指針數(shù)組進(jìn)行索引查找,6.3索引查找與指針數(shù)組,6.3索引查找與指針數(shù)組,字符型指針數(shù)組可以實(shí)現(xiàn)字符串?dāng)?shù)組的功能。這些字符串

26、的長(zhǎng)度可以不等；所以用指針數(shù)組更方便。如存儲(chǔ)每周7天的英文名稱，可定義一個(gè)char*name7的一維字符指針數(shù)組，如圖6.9。,指針數(shù)組與字符串：,6.4 模板與類(lèi)參數(shù),模板的通用性： 在前文所討論的排序與查找中，模板的通用性得到了很好的體現(xiàn)。關(guān)鍵技術(shù)是數(shù)組的數(shù)據(jù)元素說(shuō)明為類(lèi)，并重載小于運(yùn)算符，該運(yùn)算符實(shí)際是將元素類(lèi)對(duì)象的比較轉(zhuǎn)化為類(lèi)對(duì)象關(guān)鍵字的比較。因使用標(biāo)準(zhǔn)字符串類(lèi)string看不見(jiàn)其內(nèi)部構(gòu)成，下面用自定義字符串類(lèi)來(lái)進(jìn)一步闡述這個(gè)問(wèn)題。,【例6.10】冒泡排序算法，關(guān)鍵字為自定義字符串。,【例6.6】中同樣可以用mystring代替標(biāo)準(zhǔn)字符串類(lèi)string，不過(guò)那兒有兩個(gè)層次：元素類(lèi)和字符

27、串類(lèi)。運(yùn)算符的重載可以由對(duì)象成員的重載的運(yùn)算符（或成員）函數(shù)一級(jí)一級(jí)調(diào)用生成。在類(lèi)定義中運(yùn)算符和函數(shù)的重載是面向?qū)ο蟪绦蛟O(shè)計(jì)實(shí)現(xiàn)通用性的非常得力的工具。,6.4 模板與類(lèi)參數(shù),以類(lèi)對(duì)象作為函數(shù)的實(shí)參，實(shí)現(xiàn)被積函數(shù)(類(lèi)對(duì)象的成員函數(shù))的傳遞：,【例6.12】設(shè)計(jì)梯形法求積分的函數(shù)模板。,以模板參數(shù)T來(lái)引入被積函數(shù)類(lèi)，由該參數(shù)調(diào)用欲求定積分的函數(shù),【例6.11】設(shè)計(jì)梯形法求積分的類(lèi)模板。,求積分的函數(shù)為獨(dú)立的非成員函數(shù)。該方法更簡(jiǎn)潔。,6.4 模板與類(lèi)參數(shù),函數(shù)模板常用方式： (1) 函數(shù)模板作為類(lèi)模板的成員函數(shù)，在模板類(lèi)型參數(shù)中重載函數(shù)和運(yùn)算符，直接訪問(wèn)私有數(shù)據(jù)成員，實(shí)現(xiàn)通用算法。這是標(biāo)準(zhǔn)的面向

28、對(duì)象的方法。 (2) 獨(dú)立的函數(shù)模板（非成員函數(shù)）處理模板類(lèi)（或普通類(lèi)，或普通數(shù)據(jù)），以類(lèi)模板（或類(lèi)對(duì)象，或普通數(shù)據(jù)）為參數(shù)，借助模板類(lèi)中重載的函數(shù)或運(yùn)算符，實(shí)現(xiàn)通用算法。但間接訪問(wèn)私有數(shù)據(jù)成員。這也是常見(jiàn)的。,6.5函數(shù)指針與指針識(shí)別（選讀）6.5.1 函數(shù)指針及其應(yīng)用（選讀）,函數(shù)名對(duì)應(yīng)于該函數(shù)執(zhí)行代碼的入口地址。通過(guò)取地址運(yùn)算符“/或者= (car.*pf)(); /將指針pf與對(duì)象car綁定，最終等效調(diào)用car. GetPrice ();,上式表示指針pf與對(duì)象car綁定，指向了car. GetPrice ()。所以指向成員函數(shù)的指針存儲(chǔ)的不是成員函數(shù)的地址，綁定后才獲得地址。,也可以

29、用對(duì)象代替類(lèi)進(jìn)行初始化，效果一樣： CGoods car,motor; float (CGoods:*pf)()=motor.GetPrice; /等效float (CGoods:*pf)()= CGoods:GetPrice; 并未綁定 (car.*pf)(); /將指針pf與對(duì)象car綁定,指向類(lèi)成員函數(shù)的指針的說(shuō)明及初始化： 以指向商品類(lèi) GetPrice()函數(shù)的指針為例： float (CGoods:*pf)()= CGoods:GetPrice;,6.5.3 指針的識(shí)別方法（選讀）,說(shuō)明中包括多種說(shuō)明符容易造成閱讀和理解的困難。一種理解和構(gòu)造對(duì)象說(shuō)明的方法是：先撇開(kāi)標(biāo)識(shí)符，按從右到

30、左的順序逐個(gè)解釋每個(gè)說(shuō)明符，如果有括號(hào)則改變解釋的先后，先解釋括號(hào)內(nèi)再解釋擴(kuò)號(hào)外。例如： int *arrp5; 按下列順序理解：五個(gè)元素的數(shù)組、每個(gè)元素是一個(gè)指針、指針指向整型，所以 arrp 是一個(gè)有五個(gè)整型指針作為數(shù)組元素的數(shù)組。 int (*parr)5; 是一個(gè)指針，指針指向一個(gè)包含五個(gè)元素的數(shù)組，每個(gè)元素是一個(gè)整型，所以 parr 是一個(gè)指向五個(gè)整型數(shù)的數(shù)組的指針。,復(fù)雜說(shuō)明閱讀和理解的方法：,6.5.3 指針的識(shí)別方法（選讀）,答案： i 是一個(gè)整型的變量； ip 是一個(gè)指向整型變量的指針，即 ip 中存儲(chǔ)的是另一個(gè)整 型變量的地址； f 是一個(gè)返回整型值的函數(shù)； fp 是一個(gè)返

31、回整型指針的函數(shù)，即 fp 返回的是一個(gè)指向整 型變量的指針； pf 是一個(gè)指向返回整型值的函數(shù)的指針；,復(fù)雜說(shuō)明的實(shí)例： int i, *ip, f(), *fp(), (*pf)();,6.5.3 指針的識(shí)別方法（選讀）,答案： pfp 是一個(gè)指向函數(shù)的指針，該函數(shù)返回一個(gè)整型指針； a 是一個(gè)有五個(gè)整型元素的數(shù)組； ap 是一個(gè)指針數(shù)組，每個(gè)元素是一個(gè)指向整型的指針； pa 是一個(gè)指向整型數(shù)組的指針，該數(shù)組有五個(gè)整型元素； fap 是一個(gè)指向數(shù)組的指針，該數(shù)組的每個(gè)元素都是一個(gè)指 向函數(shù)的指針，而所指的函數(shù)的返回值是整型。,復(fù)雜說(shuō)明的實(shí)例： int *(*pfp)(), a5, *ap5

32、, (*pa)5, (*(*fap)();,第六章 模板與數(shù)據(jù)結(jié)構(gòu),完,謝謝！,【例6.2】矩陣運(yùn)算,template void inverse(T1 *mat1,T2 *mat2,int a,int b) int i,j; for (i=0;ib;i+) for (j=0;ja;j+) mat2ji=mat1ij; return; ,【例6.2】矩陣運(yùn)算,template void multi(T1 *mat1,T2 *mat2,T2 *result,int a,int b,int c) int i,j,k; for(i=0;ia;i+) for(j=0;jc;j+) resultij =

33、0; for(k=0;kb;k+) resultij+=mat1ik*mat2kj; return; 注意：二維數(shù)組的類(lèi)型僅指其組成元素類(lèi)型(一維數(shù)組),而與元素?cái)?shù)量無(wú)關(guān)。如matrix2和result 是同一類(lèi)型，其元素同為整型4元素一維數(shù)組，盡管前者只有3個(gè)元素(一維數(shù)組),后者有6個(gè)元素,【例6.2】矩陣運(yùn)算,template void output(T *mat,char *s, int a,int b) int i,j; coutsendl; for(i=0;ia;i+) for(j=0;jb;j+) coutsetw(4)matij ; coutendl; return; ,【例6

34、.2】矩陣運(yùn)算,int main() int middle63, result64; int matrix136=8,10,12,23,1,3,5,7,9,2,4,6,34,45,56,2,4,6; int matrix234=3,2,1,0,-1,-2,9,8,7,6,5,4; char *s1=result; char *s2=middle; inverse(matrix1,middle,6,3); /顯式：inverse (matrix1,middle,6,3); multi(middle,matrix2,result,6,3,4); /顯式：multi (middle,matrix2,

35、result,6,3,4); output(matrix1,matrix1,3,6); output(middle,s2,6,3); output(matrix2,matrix2,3,4); output(result,s1,6,4); return 0; ,【例6.3】順序表類(lèi)模板,template int seqlist:Find(T /找到，返回下標(biāo) ,template T /取第i個(gè)元素之值 seqlist: Get(int i) if(ilast) cout下標(biāo)出界！endl;exit(1); return slisti; ,【例6.3】順序表類(lèi)模板,template bool se

36、qlist:IsIn(T ,template T ,【例6.3】順序表類(lèi)模板,template bool seqlist:Insert(T ,【例6.3】順序表類(lèi)模板,template bool seqlist:Remove(T /表中不存在x ,【例6.3】順序表類(lèi)模板,template int seqlist:Next(T ,【例6.3】順序表類(lèi)模板,int main() seqlist seqlisti; /順序表對(duì)象seqlisti的元素為整型 int i,j,k,a10=2,3,5,7,11,13,17,19,23,29; for(j=0;j10;j+) /把素?cái)?shù)寫(xiě)入 if (!se

37、qlisti.Insert(aj,j) cout表太大放不下了!endl; break; j=seqlisti.Length(); for(i=0;ij;i+) coutseqlisti.Get(i) ; cout endl ; /打印出seqlisti.slist-素?cái)?shù)表 for(j=0;j10;j+) seqlistij=0; /采用下標(biāo)運(yùn)算符運(yùn)算 for(j=0;j10;j+) coutseqlistij ; coutendl; for(j=0;j10;j+) seqlistij=aj;,【例6.3】順序表類(lèi)模板,seqlisti10=31; /實(shí)驗(yàn)?zāi)芊裨黾釉?for(j=0;j11;

38、j+) coutseqlistij ; coutendl; k=7; if (seqlisti.IsIn(k) cout素?cái)?shù)7在順序表中 endl; /因形參為引用，所以實(shí)參不可用整數(shù)常量7 else cout 素?cái)?shù)7不在順序表中endl; k=17; if (seqlisti.Remove (k) cout刪除素?cái)?shù)17endl; /刪除素?cái)?shù)17 else cout找不到素?cái)?shù)17，無(wú)法刪除; j=seqlisti.Length( ) ; for (i=0;ij;i+) coutseqlisti.Get(i) ; /打印剩下的素?cái)?shù) coutendl;,【例6.3】順序表類(lèi)模板,if (seqli

39、sti.Insert(k,j-1) / 把素?cái)?shù)17裝回去,成功則打印 j=seqlisti.Length ( ); for (i=0;ij;i+) coutseqlisti.Get(i) ; coutendl; cout打印17后一個(gè)素?cái)?shù)：“ seqlisti.Get(seqlisti.Next(k)endl; cout打印17前一個(gè)素?cái)?shù)：“ seqlisti.Get(seqlisti.Prior(k)endl; cout素?cái)?shù)17在表中位置（下標(biāo)）為：“ seqlisti.Find(k)endl; if(seqlisti.IsEmpty( ) cout表是空的endl; else cout表不

40、空endl; if (seqlisti.IsFull() cout表是滿的endl; else cout表也不滿endl; if (seqlisti.IsIn(k) cout素?cái)?shù)17在表中endl; return 0; ,【例6.4】對(duì)半查找遞歸算法,【例6.4】對(duì)半查找遞歸算法，作為有序表模板類(lèi)成員函數(shù)。 template int Orderedlist:Binarysearch (T 未找到但結(jié)束了，返回mid=-1 遞歸方法易讀易懂，但效率低。注意遞歸的隱式循環(huán)代碼編寫(xiě)。,有序表模板定義，基本元素為類(lèi)Elemen對(duì)象 ： class Element int key;/ 其他域省略 pub

41、lic: bool operatorclass Orderedlist int maxsize; int last; T slistsize; public: Orderedlist()last=-1;maxsize=size; int Binarysearch(T ,【例6.4】對(duì)半查找遞歸算法,template bool Orderedlist:Insert(T ,【例6.4】對(duì)半查找遞歸算法,int main() const int h=19;int i,k=37; Orderedlist ordlist; int ah=67,61,59,53,47,43,41,37,31,29,23,

42、 19,17,13,11,7,5,3,2; /降序 Element nh,elem; for(i=0;ih;i+) ni.putkey(ai); for(i=0;ih;i+) ordlist.Insert(ni,0); /始終在0號(hào)元素插入，建立升序順序表 elem.putkey(k); ordlist.print(); i=ordlist.Binarysearch(elem,0,h-1); cout整數(shù)k在表中位置（下標(biāo)）：iendl; return 0; ,【例6.5】對(duì)半查找迭代算法,【例6.5】對(duì)半查找迭代算法。 template int Orderedlist:BinarySearc

43、h(const T 該例中迭代算法的可讀性也不差，效率要高于遞歸。注意迭代的顯式循環(huán)代碼編寫(xiě) 的關(guān)鍵點(diǎn)。,【例6.6】升序直接插入排序算法,作為【例6.4】Orderedlist類(lèi)的成員函數(shù)InsertSort()，T為關(guān)鍵字類(lèi)型。 template void Orderedlist:InsertSort() T temp; int i,j; for (i=1;i0 ,class Element string key;/ 其他域省略 public: bool operator ordlist; string mslisth=cat,book,car,zoo,fish, cab,dog,cap,

44、fox,can; for(i=0;ih;i+) ni.putkey(mslisti); for(i=0;ih;i+) ordlist.Insert(ni,i); /建立順序表 cout未排序表：endl; ordlist.print(); ordlist.InsertSort(); cout已排序表：endl; ordlist.print(); return 0;,【例6.7】升序?qū)Π氩迦肱判蛩惴?Orderedlist類(lèi)的成員函數(shù)升序?qū)Π氩迦肱判蛩惴ā．?dāng)關(guān)鍵字相同時(shí)，插入排序原來(lái)在前的仍在前，稱穩(wěn)定排序。 template void Orderedlist:BinaryInsertSort(

45、) T temp; int low,high,mid,i,j; for (i=1;i=low;j-) slistj+1=slistj; slistlow=temp; ,【例6.8】冒泡排序算法,冒泡排序算法，作為Orderedlist類(lèi)的成員函數(shù)。 template void Orderedlist:BubbleSort() bool noswap; int i,j; T temp; for (i=0;ii;j-) /從下往上冒泡 if(slistjslistj-1) temp=slistj; slistj=slistj-1; slistj-1=temp; noswap=false; if(n

46、oswap) break; /本趟無(wú)交換，則終止算法。 冒泡排序的優(yōu)點(diǎn)在于可利用原來(lái)的數(shù)據(jù)排列的部分有序性。,【例6.8】冒泡排序算法,學(xué)生類(lèi)為數(shù)組元素 class student int id ; /學(xué)號(hào) string name; / 姓名 char sex; / 性別 int age; / 年齡 string address; /家庭地址 float eng, phy, math, electron; /英語(yǔ),物理,數(shù)學(xué)和電子學(xué)成績(jī) public: student() student(int,string,char,int,string,float,float,float,float);

47、bool operator(student ele)return idele.id; void show() coutidtnametsext agetaddresstengtphyt mathtelectronendl; ;,【例6.8】冒泡排序算法,int main() const int h=4; int i; Orderedlist ordlist; student nh= student(6004327,張菲,m,19,北京路58號(hào),80,85,90,78), student(6004121,關(guān)雨,w,19,天津路64號(hào),88,75,91,68), student(6004118,劉

48、蓓,w,18,上海路37號(hào),78,95,81,88), student(6004219,趙昀,m,18,重慶路95號(hào),78,95,81,88); for(i=0;ih;i+) ordlist.Insert(ni,i); /建立順序表 cout未排序表：endl; ordlist.print(); ordlist.BubbleSort(); cout已排序表：endl; ordlist.print(); return 0; ,【例6.9】直接選擇排序,作為Orderedlist類(lèi)的成員函數(shù)。 template void Orderedlist:SelectSort() int i,j,k;T t

49、emp; for(i=0;ilast;i+) k=i; temp=slisti; for(j=i;j=last;j+) if(slistjtemp) k=j; temp=slistj; if(k!=i) temp=slisti; slisti=slistk; slistk=temp; ,【例6.10】冒泡排序算法,自定義字符串類(lèi)重載的小于比較運(yùn)算符如下： bool mystring:operator(mystring ,【例6.10】冒泡排序算法函數(shù)模版,template void BubbleSort(T* slist,int n) bool noswap; int i,j; T temp;

50、 for (i=0;ii;j-) /從下往上冒泡 if(slistjslistj-1) temp=slistj; slistj=slistj-1; slistj-1=temp; noswap=false; if(noswap) break; /本趟無(wú)交換，則終止算法。 ,【例6.10】冒泡排序算法,int main() const int h=10; int i; mystring list10=cat,book,car,zoo,fish, cab,dog,cap,fox,can; cout未排序數(shù)組：endl; for(i=0;ih;i+) listi.show(); BubbleSort(

51、list,h); cout已排序數(shù)組：endl; for(i=0;ih;i+) listi.show(); return 0; ,【例6.11】求積分的類(lèi)模板,梯形法求積分是一種求函數(shù)定積分的近似方法。對(duì)函數(shù) f(x) 將積分區(qū)間 a,b 分成 n 份，每一份看作一個(gè)近似梯形，函數(shù)在該區(qū)間的定積分就是所有近似梯形的面積和。積分步長(zhǎng)為step=(b-a)/n，面積為 s = step*(f(x0)+f(x1)/2+step*(f(x1)+f(x2)/2+. +step*(f(xn-1)+f(xn)/2 = step*(f(x0)/2+f(x1)+f(x2)+.+f(xn-1)+f(xn)/2),class F1 public: double fun(double x)return (1+x+2*x*x); ; class F2 public: double fun(double x)return (1+x+2*x*x+3*x*x*x); ; class F3 public: double fun(double x) return (1+x+2*x*x+3*x*x*x+4*x*x*x*x); ;,【例6.11】求積分的類(lèi)模板,templateclass Integ