C 程序設(shè)計(jì)課件：第六章 模板與數(shù)據(jù)結(jié)構(gòu)

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

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

3、 /函數(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; 類型參數(shù)Groap在程序運(yùn)行中會(huì)被各種內(nèi)置（基本）類型或用戶定義類型所置換。 模板參數(shù)表的使用與函數(shù)形式參數(shù)表的使用相同，都是位置對(duì)應(yīng)。類型和值的置換過(guò)程稱為模板實(shí)例化 (template instantiation)。 形參size 表示 r_array

4、 數(shù)組的長(zhǎng)度。6.1.1 函數(shù)模板及應(yīng)用模板實(shí)參推演：函數(shù)模板根據(jù)一組實(shí)際類型或（和）值構(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; string s=max(sa,5)

5、;cout 字典排序最大為：sendl; return 0;6.1.1 函數(shù)模板及應(yīng)用 第一次調(diào)用時(shí)，Groap被int取代。第二次調(diào)用，Groap 被double取代。第三次Groap 被string取代。為了判斷用作模板實(shí)參的實(shí)際類型，編譯器需檢查函數(shù)調(diào)用中提供的函數(shù)實(shí)參的類型。ia 的類型為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,5);這樣可讀性更好。這里數(shù)組名是作為指向數(shù)組首元

6、素的指針進(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 void inverse(T1 *mat1, T2 *mat2,int

7、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屬同一類型，均為由具有相同元素?cái)?shù)量的一維數(shù)組所組成的二維數(shù)組。本例為mat34和result64。記住數(shù)組最高維是不檢查邊界的。函數(shù)模板的聲明：6.1.2 類模板與線性表類模板定義：template class 類名 /類定義體; /再次指出分號(hào)不可少template 返回類型 類名:成員函數(shù)名1(形參表) ；/成員

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

9、員函數(shù)只有在被調(diào)用（或取地址）時(shí)才被實(shí)例化。成員函數(shù)模板定義中，指定成員函數(shù)所在類域的類型名后跟的中成員，與類模板的中的類型參數(shù)名相同，但不加 typename 或class。與包含對(duì)象成員的構(gòu)造函數(shù)類似，實(shí)際是一個(gè)模板實(shí)例化的類型實(shí)參表，所以不加 typename 或class。 6.1.2 類模板與線性表從通用的類模板定義中生成類的過(guò)程稱為模板實(shí)例化（template instantiation），其格式為：typedef 類名 類實(shí)例名；也可以與定義對(duì)象同時(shí)完成：類名 對(duì)象名；模板實(shí)例化：例如：標(biāo)準(zhǔn)串類模板basic_string，它提供了復(fù)制、查找等典型串操作。它包含在頭文件中。文件中

10、包括有：typedef basic_string string; 標(biāo)準(zhǔn)串類模板basic_string實(shí)例化為上一章討論的字符串類string。因?yàn)樽址械淖址梢允茿SCII碼，也可以是中文漢字編碼，還可以是unicode編碼，所以使用類模板是合理的。 6.1.2 類模板與線性表線性表是數(shù)據(jù)結(jié)構(gòu)中的概念。數(shù)組中除第一個(gè)元素外，其他元素有且僅有一個(gè)直接前驅(qū)，第一個(gè)元素沒(méi)有前驅(qū)；除最后一個(gè)元素外，其他元素有且僅有一個(gè)直接后繼，最后一個(gè)元素?zé)o后繼。這樣的特性稱為線性關(guān)系。所以稱數(shù)組元素在一個(gè)線性表中。線性表實(shí)際包括順序表（數(shù)組）和鏈表。 對(duì)順序表的典型操作包括：計(jì)算表長(zhǎng)度，尋找變量或?qū)ο髕（其類

11、型與表元素相同）在表中的位置（下標(biāo)值），判斷x是否在表中，刪除x，將x插入列表中第i個(gè)位置，尋找x的后繼，尋找x的前驅(qū)，判斷表是否空，判斷表是否滿（表滿不能再插入數(shù)據(jù)，否則會(huì)溢出，產(chǎn)生不可預(yù)知的錯(cuò)誤），取第i個(gè)元素的值。 這些操作與數(shù)組封裝在一起可以定義一個(gè)類，考慮到數(shù)組元素的類型可以各不相同，所以定義為類模板。 線性表：6.1.2 類模板與線性表 由編譯器編譯時(shí)分配內(nèi)存的數(shù)組稱為靜態(tài)數(shù)組，數(shù)組的長(zhǎng)度是不可改變的。 如果定義了30個(gè)元素的數(shù)組，后來(lái)需要40個(gè)元素，是不可能續(xù)上10個(gè)的，必然產(chǎn)生溢出。因系統(tǒng)不檢查數(shù)組邊界，進(jìn)而產(chǎn)生不可預(yù)知的運(yùn)行時(shí)錯(cuò)誤，所以一般采用“大開小用”的方法，即數(shù)組定義的

12、較大，而實(shí)用較小。 為防止不可避免的溢出，應(yīng)在添加新數(shù)據(jù)時(shí)判斷表是否滿。在順序表類模板中，添加了兩個(gè)數(shù)據(jù)成員專門用來(lái)完成這項(xiàng)任務(wù)：最大可容納項(xiàng)數(shù)和已用表項(xiàng)的最后位置。 靜態(tài)數(shù)組：6.1.2 類模板與線性表1431341096587241621892771185112110131234i圖a下標(biāo)1431341096587241621897118511211013圖b下標(biāo)圖6.1 從表中刪除一個(gè)數(shù)據(jù)當(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è)

13、元素拷入第i+1個(gè)元素,依此類推，直到最后一個(gè)元素（下標(biāo)為10），現(xiàn)在表長(zhǎng)度為10。刪除順序表元素：6.1.2 類模板與線性表1431341096587241621892771185112110135432i圖a下標(biāo)1273134109658724162189711511181214x013圖b下標(biāo)圖6.2 向表中插入一個(gè)數(shù)據(jù)當(dāng)需要在順序表的指定位置i 插入一個(gè)數(shù)據(jù)x時(shí)，必須為它騰出這個(gè)位置，把從該位置開始向后的所有元素?cái)?shù)據(jù)，后移一個(gè)位置，最后才插入。后移時(shí)從最后一個(gè)元素開始，參見圖6.2?，F(xiàn)在長(zhǎng)度為12，這樣的移動(dòng)也是不可少的，否則新插入的數(shù)據(jù)x會(huì)沖掉原來(lái)的數(shù)據(jù)，或先移的數(shù)據(jù)沖掉未移的數(shù)據(jù)。

14、添加順序表元素：【例6.3】順序表類模板template class seqlist T slistsize; /存放順序表的數(shù)組 int Maxsize; /最大可容納項(xiàng)數(shù) int last; /已存表項(xiàng)的最后位置public: seqlist()last=-1;Maxsize=size; /初始化為空表 int Length() constreturn last+1; /計(jì)算表長(zhǎng)度 int Find(T & x)const; / 尋找x在表中位置（下標(biāo)） bool IsIn(T & x); /判斷x是否在表中 bool Insert(T & x,int i); /x插入到列表中第i個(gè)位置處

15、（下標(biāo)） bool Remove(T & x); /刪除x int Next(T & x); /尋找x的后繼位置 int Prior(T & x); /尋找x的前驅(qū)位置 bool IsEmpty()return last=-1; /判斷表是否空 bool IsFull()return last=Maxsize -1; /判斷表是否滿 T Get(int i); /取第i個(gè)元素之值 T& operator(int i); ; /重載下標(biāo)運(yùn)算符檢驗(yàn)主程序用UML類圖表示模板模板參數(shù)化元素（parameterized element） 在UML中，模板是對(duì)一個(gè)帶有一個(gè)或多個(gè)未綁定的形式參數(shù)的元素的描

16、述符。因此它定義了一系列的潛在元素，其中每個(gè)元素都通過(guò)把參數(shù)綁定到實(shí)際值來(lái)說(shuō)明。 模板類是最常用的參數(shù)化元素，與C+的類模板對(duì)應(yīng)得十分完美，參數(shù)有類型參數(shù)和非類型參數(shù)（代表潛在的常量）。模板類的圖示方法是在類圖的右上角加一個(gè)虛線框，參數(shù)填在框內(nèi)。指定形式參數(shù)后由UML模板類產(chǎn)生相關(guān)類，稱為綁定（bind），即C+的模板實(shí)例化。相關(guān)類與模板類存在綁定依賴關(guān)系，用相關(guān)類指向模板類的虛箭頭表示，虛線邊加標(biāo)bind和圓括號(hào)中的實(shí)在參數(shù)。綁定可以是顯式的，相關(guān)類有自己的名字；也可以是隱式的，無(wú)名的類。用UML類圖表示模板下圖是線性表類模板的UML圖，同時(shí)給出綁定產(chǎn)生的新類64元素的整型線性表。對(duì)應(yīng)C+的

17、模板實(shí)例化。.2 排序與查找 6.2.2 常用的排序法6.2.1 常用查找方法 排序（sorting）： 是最重要的計(jì)算應(yīng)用之一。例如查字典，字典中的詞條是按序存放的，我們才能按字母順序找到要查的字。又如圖書館的藏書也是按書的編號(hào)有序排列的。在計(jì)算機(jī)上數(shù)據(jù)庫(kù)里的資料也是有序排列的。查找（search）： 當(dāng)然也是最常見的運(yùn)算，就是在數(shù)據(jù)集合中尋找滿足條件的數(shù)據(jù)對(duì)象，找到后進(jìn)一步給出對(duì)象的具體信息，在數(shù)據(jù)庫(kù)技術(shù)中稱為檢索（retrieval）。6.2.1 常用查找方法 順序查找：從第一個(gè)元素開始，順序查找直到找到或查到最后一個(gè)元素為止。 查找是按關(guān)鍵字（key word）進(jìn)行?？梢晕ㄒ坏匕奄Y料區(qū)

18、分出來(lái)的數(shù)據(jù)被稱為主關(guān)鍵字。如學(xué)生的資料(結(jié)構(gòu)體變量):struct studentint id ; /學(xué)號(hào)char name20; / 姓名char sex; / 性別int age; / 年齡char 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 常用查找方法low8917131120719212331262925373923查找lowmidhigh202129262

19、3313739midhighlow202123midhigh23low mid high成功圖6.3 查找成功例首先安排兩個(gè)指針low和high指向首尾兩元素，取mid= (low+ high)/2，如mid指向元素是所查找的，則結(jié)束。如果該元素關(guān)鍵字大了，則取low=mid +1， high不變，繼續(xù)查找；如果該元素關(guān)鍵字小了，則取 high=mid-1，low不變，繼續(xù)查找。如果查到lowhigh仍未找到，則失敗，停止。對(duì)半查找:6.2.1 常用查找方法對(duì)半查找25781113179192023212629313710查找low39midhigh25781113179lowmidhigh1

20、113179lowmidhigh9low mid high圖6.4 查找失敗例注意：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ì)半查找遞歸算法，作為有序表模板類成員函數(shù)。遞歸方法易讀易懂，但效率低。注意遞歸的隱式循環(huán)代碼編寫?！纠?.5】對(duì)半查找迭代算法。該例中迭代算

21、法的可讀性也不差，效率要高于遞歸。注意迭代的顯式循環(huán)代碼編寫 的關(guān)鍵點(diǎn)。*本例中出現(xiàn)的成員函數(shù)Binarysearch(T & x)const ，稱為 const成員函數(shù)，該函數(shù)保證只讀。相應(yīng)線性表元素類重載的比較運(yùn)算符也必須是const。6.2.1 常用查找方法例6.5元素類重載的比較運(yùn)算符：class Element int key;/ 其他域省略public: bool operator(Element ele)constreturn key=1)個(gè)元素sli時(shí),前面的元素sl0,sl1,sli-1已經(jīng)排好序,我們將sli的關(guān)鍵字與sli-1, sli-2,的關(guān)鍵碼順序進(jìn)行比較,找到第一

22、個(gè)比它小的,則sli插到該元素之后。i0123456temp初始序列8679452616879452726789452936789452444678952554567892262456789直接插入排序算法中用了一個(gè)臨時(shí)變量temp，要插入的元素放到temp中，這樣插入前各元素后移時(shí)允許將該元素沖掉。6.6.2 常用的排序法【例6.6】升序直接插入排序算法*(2)對(duì)半插入排序（Binary Insert Sort）是用對(duì)半查找的思想取代順序查找。對(duì)半插入排序要快于插入排序?！纠?.7】升序?qū)Π氩迦肱判蛩惴?.2.2 常用的排序法圖6.6從下往上掃描的冒泡程序 2交換排序交換排序的基本思想是按關(guān)

23、鍵字兩兩排序?qū)ο螅绻l(fā)生逆序則交換之，直到所有的對(duì)象都排好序?yàn)橹埂?9131313131313133849272727272727653849383838383897653849494949497697654949494949137697656565656527277697767676764949497697979797冒泡排序基本思想?yún)⒁妶D6.6。最左列為最初的情況，最右列為完成后的情況。首先我們從一列數(shù)據(jù)底部開始，相鄰的兩數(shù)據(jù)進(jìn)行比較，小的數(shù)放上面，一趟比較下來(lái)，最小的數(shù)據(jù)冒到了最上面。再縮小區(qū)域，按同樣方法繼續(xù)下一趟交換，如果有一趟比較中沒(méi)有發(fā)生交換，則已排好序。圖6.6中，第5列就已

24、排好序，若再繼續(xù)下一趟就不會(huì)發(fā)生交換。6.2.2 常用的排序法3選擇排序（Selection Sort）基本思想是：每一趟從待排序的記錄中選出關(guān)鍵字最小的元素，順序放在已排好序的子序列的后面，直到全部記錄排序完成。直接選擇排序（Straight Selection Sort）是最簡(jiǎn)單的。此方法的最大優(yōu)點(diǎn)是易讀。缺點(diǎn)是做過(guò)的工作和序列的部分有序性利用不上，效率低。選擇排序中也有可能利用到以前的工作的方法，如堆排列（Heap Sort） 493865977613274913386597764927491327659776493849132738977649654913273849769765491

25、32738494997657613273849496597761327384949657697 圖6.7直接選擇排序的過(guò)程6.3 索引查找與指針數(shù)組 指針數(shù)組： 數(shù)據(jù)元素為指針的數(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）。參見圖6.8。 學(xué)號(hào) 姓名 性

26、別 年齡 06002808張偉 男1806002804姚婕 女1706002802王茜 女1806002807朱明 女1806002809沈俊 男1706002806況鐘 女1706002801程毅 男1806002803李文 男1906002805胡鳳 女19下標(biāo) 012345678圖6.8用指針數(shù)組進(jìn)行索引查找6.3索引查找與指針數(shù)組 6.3索引查找與指針數(shù)組字符型指針數(shù)組可以實(shí)現(xiàn)字符串?dāng)?shù)組的功能。這些字符串的長(zhǎng)度可以不等；所以用指針數(shù)組更方便。如存儲(chǔ)每周7天的英文名稱，可定義一個(gè)char*name7的一維字符指針數(shù)組，如圖6.9。name5name2name0name1name3name

27、4name6“Wednesday”“Friday”“Monday”“Sunday”“Tuesday”“Thursday”“Saturday”圖6.9 字符指針數(shù)組指針數(shù)組與字符串：6.4 模板與類參數(shù) 模板的通用性：在前文所討論的排序與查找中，模板的通用性得到了很好的體現(xiàn)。關(guān)鍵技術(shù)是數(shù)組的數(shù)據(jù)元素說(shuō)明為類，并重載小于運(yùn)算符，該運(yùn)算符實(shí)際是將元素類對(duì)象的比較轉(zhuǎn)化為類對(duì)象關(guān)鍵字的比較。因使用標(biāo)準(zhǔn)字符串類string看不見其內(nèi)部構(gòu)成，下面用自定義字符串類來(lái)進(jìn)一步闡述這個(gè)問(wèn)題?！纠?.10】冒泡排序算法，關(guān)鍵字為自定義字符串。 【例6.6】中同樣可以用mystring代替標(biāo)準(zhǔn)字符串類string，不過(guò)

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

29、。這是標(biāo)準(zhǔn)的面向?qū)ο蟮姆椒ā?2) 獨(dú)立的函數(shù)模板（非成員函數(shù)）處理模板類（或普通類，或普通數(shù)據(jù)），以類模板（或類對(duì)象，或普通數(shù)據(jù)）為參數(shù)，借助模板類中重載的函數(shù)或運(yùn)算符，實(shí)現(xiàn)通用算法。但間接訪問(wèn)私有數(shù)據(jù)成員。這也是常見的。6.5函數(shù)指針與指針識(shí)別（選讀）6.5.1 函數(shù)指針及其應(yīng)用（選讀）函數(shù)名對(duì)應(yīng)于該函數(shù)執(zhí)行代碼的入口地址。通過(guò)取地址運(yùn)算符“&”也可以取得函數(shù)的入口地址。指向函數(shù)的指針可以作為函數(shù)的參數(shù)傳遞。定義方式如下：返回類型 (*指針變量名)(參數(shù)表)由于一個(gè)函數(shù)不能以函數(shù)作為參數(shù)，所以當(dāng)一個(gè)函數(shù)需要將函數(shù)作為參數(shù)時(shí)必須借用指向函數(shù)的指針（當(dāng)然建議用包含該函數(shù)的類對(duì)象）。 函數(shù)名與函

30、數(shù)指針：6.5.1 函數(shù)指針及其應(yīng)用（選讀）【例6.13】梯形法求積分的函數(shù)integer()作為通用函數(shù)，可求任一函數(shù)的定積分。函數(shù)指針的使用方法：如有函數(shù)void scopy(char *q,char *p)，函數(shù)名scopy代表函數(shù)的入口地址，或者說(shuō)是一個(gè)指向該函數(shù)的指針，該指針的類型為：void (*)(char *q,char *p) /q與p寫與不寫是一樣的定義這種函數(shù)指針類型的變量pf并用scopy初始化：void(* pf)(char *,char *)=scopy;/或者=&scopy，兩者等效pf將存儲(chǔ)scopy函數(shù)的入口地址。6.5.2指向類成員的指針（選讀） 在類對(duì)象中

31、有隱含的this指針，用以正確訪問(wèn)成員函數(shù)。所以指向類成員函數(shù)的指針有其特殊性。 指向類成員函數(shù)的指針： 普通函數(shù)指針存儲(chǔ)函數(shù)的地址，可以直接用來(lái)調(diào)用指定函數(shù)。成員函數(shù)指針必須首先被綁定在一個(gè)對(duì)象或指針上，才能獲得被調(diào)用對(duì)象的this指針，然后才能調(diào)用指針?biāo)赶虻某蓡T函數(shù)。雖然兩者都被稱為指針，但是它們是不同類型的數(shù)據(jù)。 成員函數(shù)有一個(gè)非成員函數(shù)沒(méi)有的屬性：它所屬的類（class）。所以指向成員函數(shù)的指針需要三個(gè)方面的匹配：參數(shù)的類型和個(gè)數(shù)，返回類型和所屬的類類型。6.5.2指向類成員的指針（選讀）成員函數(shù)指針的用法(綁定)：CGoods car;(car.*pf)(); /將指針pf與對(duì)象c

32、ar綁定，最終等效調(diào)用car. GetPrice ();上式表示指針pf與對(duì)象car綁定，指向了car. GetPrice ()。所以指向成員函數(shù)的指針存儲(chǔ)的不是成員函數(shù)的地址，綁定后才獲得地址。也可以用對(duì)象代替類進(jìn)行初始化，效果一樣：CGoods car,motor;float (CGoods:*pf)()=motor.GetPrice; /等效float (CGoods:*pf)()= CGoods:GetPrice; 并未綁定(car.*pf)(); /將指針pf與對(duì)象car綁定指向類成員函數(shù)的指針的說(shuō)明及初始化： 以指向商品類 GetPrice()函數(shù)的指針為例：float (CGoo

33、ds:*pf)()= CGoods:GetPrice; 6.5.3 指針的識(shí)別方法（選讀） 說(shuō)明中包括多種說(shuō)明符容易造成閱讀和理解的困難。一種理解和構(gòu)造對(duì)象說(shuō)明的方法是：先撇開標(biāo)識(shí)符，按從右到左的順序逐個(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

34、 指針的識(shí)別方法（選讀）答案：i 是一個(gè)整型的變量；ip 是一個(gè)指向整型變量的指針，即 ip 中存儲(chǔ)的是另一個(gè)整 型變量的地址；f 是一個(gè)返回整型值的函數(shù)；fp 是一個(gè)返回整型指針的函數(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è)指

35、向數(shù)組的指針，該數(shù)組的每個(gè)元素都是一個(gè)指 向函數(shù)的指針，而所指的函數(shù)的返回值是整型。復(fù)雜說(shuō)明的實(shí)例：int *(*pfp)(), a5, *ap5, (*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

36、,int b,int c) int i,j,k; for(i=0;ia;i+) for(j=0;jc;j+) resultij = 0; for(k=0;kb;k+) resultij+=mat1ik*mat2kj; return;注意：二維數(shù)組的類型僅指其組成元素類型(一維數(shù)組),而與元素?cái)?shù)量無(wú)關(guān)。如matrix2和result 是同一類型，其元素同為整型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;

37、ia;i+) for(j=0;jb;j+) coutsetw(4)matij ; coutendl; return;【例6.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); mu

38、lti(middle,matrix2,result,6,3,4); /顯式：multi (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); return 0;【例6.3】順序表類模板template int seqlist:Find(T & x)const/const表示該函數(shù)的this指針為const，即被訪問(wèn)對(duì)象的數(shù)/據(jù)不能被修改。如被修改編譯器會(huì)警告，防止編程時(shí)失誤。 in

39、t i=0; while(ilast) return -1; /未找到，返回-1 else return i; /找到，返回下標(biāo)template T /取第i個(gè)元素之值seqlist: Get(int i)if(ilast)cout下標(biāo)出界！endl;exit(1);return slisti;【例6.3】順序表類模板template bool seqlist:IsIn(T & x) int i=0; bool found=0; while(i=last & !found) /換了一種方法來(lái)查找 if (slisti!=x) i+; else found=1; /找到 return found

40、;template T& seqlist:operator(int i) if(ilast|i0) cout下標(biāo)出界！endl; exit(1); return slisti;【例6.3】順序表類模板template bool seqlist:Insert(T & x, int i) int j; if (ilast+1|last=Maxsize -1) return false; /插入位置不合理，不能插入（穩(wěn)健性） else last+; for(j=last;ji;j-) slistj=slistj-1; /從表最后位置向前依次后移，空出指定位置來(lái) slisti=x; return tr

41、ue; 【例6.3】順序表類模板template bool seqlist:Remove(T & x) int i=Find(x),j; /先去找x在哪個(gè)位置 if(i=0) last-; for(j=i;j=last;j+) slistj=slistj+1; /依次前移，保證表連續(xù) return true; return false; /表中不存在x【例6.3】順序表類模板template int seqlist:Next(T & x) int i=Find(x); if(i=0 & ilast) return i+1; /x后繼位置 else return -1; /x不在表中，或在表末尾

42、template int seqlist:Prior(T & x) int i=Find(x); if(i0 & i=last) return i-1; /x前驅(qū)的位置 else return -1; 【例6.3】順序表類模板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ù)寫入 if (!seqlisti.Insert(aj,j) cout表太大放不下了!endl; break; j=seqlisti.Length();

43、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】順序表類模板 seqlisti10=31; /實(shí)驗(yàn)?zāi)芊裨黾釉?for(j=0;j11;j+) coutseqlistij ; coutendl; k=7; if (seqlisti.IsIn(k) cout素?cái)?shù)7在順序

44、表中 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】順序表類模板 if (seqlisti.Insert(k,j-1) / 把素?cái)?shù)17裝回去,成功則打印 j=seqlisti.Length ( ); for (i=0;

45、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表不空endl; if (seqlisti.IsFull() cout表是滿的endl; else cout表也不滿endl; if (s

46、eqlisti.IsIn(k) cout素?cái)?shù)17在表中endl; return 0; 【例6.4】對(duì)半查找遞歸算法【例6.4】對(duì)半查找遞歸算法，作為有序表模板類成員函數(shù)。template int Orderedlist:Binarysearch(T & x,const int low,const int high) / x為定值 int mid=-1; if (low=high) mid=(low+high)/2; if(slistmidx) mid=Binarysearch(x,mid+1,high);/中間點(diǎn)小于定值，查找右區(qū)間，注意mid+1 else if(xslistmid) mid

47、=Binarysearch(x,low,mid-1);/中間點(diǎn)大于定值，查找左區(qū)間，注意 mid-1 return mid;/找到返回下標(biāo);未找到但結(jié)束了，返回mid=-1遞歸方法易讀易懂，但效率低。注意遞歸的隱式循環(huán)代碼編寫。有序表模板定義，基本元素為類Elemen對(duì)象 ：class Elementint key;/ 其他域省略public:bool operator(Element ele)return keyele.key;void putkey(int k)key=k;void show()coutkeyt; /重載了比較運(yùn)算符，元素的比較，實(shí)際是元素關(guān)鍵字的比較 template c

48、lass Orderedlistint maxsize;int last;T slistsize;public:Orderedlist()last=-1;maxsize=size;int Binarysearch(T & x,const int low,const int high);bool Insert(T & elem,int i);void print();/ 無(wú)關(guān)成員函數(shù)省略; 【例6.4】對(duì)半查找遞歸算法template bool Orderedlist:Insert(T & elem ,int i)int j；if (ilast+1|last=maxsize-1) return

49、false;elselast+;for (j=last;ji;j-) slistj=slistj-1;slisti=elem;return true; template void Orderedlist:print()int i;for(i=0;i=last;i+)slisti.show();if(i%5=4) coutendl;coutendl;【例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, 19,17,13,11,7,

50、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:BinarySearch(const T & x)const int hig

51、h=last ,low=0,mid; / last 當(dāng)前有序表最大下標(biāo) if(last=-1) return -1; /避免空表出錯(cuò) while(low=high) mid=(low+high)/2; if(xslistmid) high=mid-1; /左縮查找區(qū)間 else if(slistmidx) low=mid+1; / 右縮查找區(qū)間 else return mid; if(slistmid!=x) mid=-1; return mid;該例中迭代算法的可讀性也不差，效率要高于遞歸。注意迭代的顯式循環(huán)代碼編寫 的關(guān)鍵點(diǎn)。【例6.6】升序直接插入排序算法作為【例6.4】Orderedl

52、ist類的成員函數(shù)InsertSort()，T為關(guān)鍵字類型。template void Orderedlist:InsertSort()T temp;int i,j;for (i=1;i0&tempslistj-1)slistj=slistj-1;j-; /查找與移動(dòng)同時(shí)做slistj=temp;class Elementstring key;/ 其他域省略public:bool operator(Element ele)return keyele.key;void putkey(string k)key=k;void show()coutkeyt; ;int main()const int

53、h=10; Element nh;int i;Orderedlist ordlist;string mslisth=cat,book,car,zoo,fish, cab,dog,cap,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ū)Π氩迦肱判蛩惴∣rderedlist類的成員函

54、數(shù)升序?qū)Π氩迦肱判蛩惴?。?dāng)關(guān)鍵字相同時(shí)，插入排序原來(lái)在前的仍在前，稱穩(wěn)定排序。template void Orderedlist:BinaryInsertSort() T temp; int low,high,mid,i,j; for (i=1;i=last;i+) temp=slisti; low=0; high=i-1; while (low=high) /請(qǐng)注意與對(duì)半查找的不同之處 mid=(low+high)/2;if(temp=low;j-) slistj+1=slistj; slistlow=temp; 【例6.8】冒泡排序算法冒泡排序算法，作為Orderedlist類的成員函數(shù)。

55、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(noswap) break; /本趟無(wú)交換，則終止算法。 冒泡排序的優(yōu)點(diǎn)在于可利用原來(lái)的數(shù)據(jù)排列的部分有序性。【例6.8】冒泡排序算法學(xué)生類為數(shù)組元素 class studentint id ; /學(xué)號(hào)string name; / 姓名char sex; / 性別

56、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);bool operator(student ele)return idele.id;void show() coutidtnametsext agetaddresstengtphyt mathtelectronendl;【例6.8】冒泡排序算法int main()const int h

57、=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,劉蓓,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.Bub

58、bleSort();cout已排序表：endl;ordlist.print();return 0;【例6.9】直接選擇排序作為Orderedlist類的成員函數(shù)。 template void Orderedlist:SelectSort() int i,j,k;T temp; 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】冒泡排序算法 自定義字符串類重載的小于比較運(yùn)算符如

59、下：bool mystring:operator(mystring & ms) /重載運(yùn)算符int i=0,k;dok=stri-ms.stri;i+;while(k=0&ilast&ims.last);if(k0) return true;if(i=last&i!=ms.last) return true;return false;【例6.10】冒泡排序算法函數(shù)模版template void BubbleSort(T* slist,int n)bool noswap;int i,j;T temp;for (i=0;ii;j-) /從下往上冒泡if(slistjslistj-1)temp=sl

60、istj;slistj=slistj-1;slistj-1=temp;noswap=false;if(noswap) break; /本趟無(wú)交換，則終止算法?！纠?.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(list,h);cout已排序數(shù)組：endl;for(i=0;ih;i+) listi.show(); return 0;【例