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

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

2、基于數(shù)據(jù)成員)： 設(shè)置半徑，移動(dòng)圓心位置，圓的大小比較，計(jì)算面積和周長(zhǎng)以及判斷某點(diǎn)是否在圓內(nèi)等;Point類(lèi)struct Point數(shù)據(jù)成員： x,y坐標(biāo);類(lèi)、對(duì)象相關(guān)知識(shí)回顧公有私有程序源代碼函數(shù)重載int a,b;.if(0=compare(a,b) .string s1,s2;.if(1=compare(s1,s2).int compare(string a,string b)if(ab) return 1;else if(ba) return -1;else return 0;int compare(int a,int b)if(ab) return 1;else if(ba) ret

3、urn -1;else return 0;這兩個(gè)函數(shù)的區(qū)別？有沒(méi)有簡(jiǎn)化代碼的方法？第三章遺留的問(wèn)題3.8.1 函數(shù)重載【例3.16】 3+5=調(diào)用sum(3,5 )函數(shù)sum(3,5 )return 8 2.2+5.6=調(diào)用sum(2.2,5.6 )函數(shù)double sum(2.2,5.6 )return 7.8 3.5+4+8=調(diào)用sum(3.5, 4, 8 )函數(shù)float sum(3.5, 4.0, 8.0 )return 15.5 結(jié)束87.815.5【例3.16】 重載函數(shù)的應(yīng)用。int sum(int a,int b) return a+b;Double sum(double a,

4、double b)return a+b;float sum(float a,float b,float c)return a+b+c;int main()cout3+5=sum(3,5) endl;cout2.2+5.6=“ sum(2.2,5.6)endl;cout3.5+4+8=“ sum(3.5,4,8)endl;return 0;思考：重載有沒(méi)有需要改進(jìn)的地方？6.1 模板 參數(shù)化程序設(shè)計(jì)：通用的代碼就必須不受數(shù)據(jù)類(lèi)型的限制，可以把數(shù)據(jù)類(lèi)型改為一個(gè)設(shè)計(jì)參數(shù)。這種類(lèi)型的程序設(shè)計(jì)稱(chēng)為參數(shù)化(parameterize) 程序設(shè)計(jì)。 這種設(shè)計(jì)由模板(template) 完成。包括函數(shù)模板(fu

5、nction template)和類(lèi)模板(class template)。6.1.2 類(lèi)模板與線性表 6.1.1 函數(shù)模板及應(yīng)用 個(gè)人理解：模板是從代碼實(shí)現(xiàn)的角度為某一類(lèi)問(wèn)題提供通用的代碼解決方案。大大減輕了程序員的代碼開(kāi)發(fā)代價(jià)6.1.1 函數(shù)模板及應(yīng)用 （template parameter list）尖括號(hào)中一般（課本說(shuō)法有誤）不能為空，參數(shù)可以有多個(gè)，用逗號(hào)分開(kāi)。模板參數(shù)有兩種情況：模板類(lèi)型參數(shù)（常用）或者模板非類(lèi)型參數(shù)。模板類(lèi)型參數(shù)(template type parameter)代表一種類(lèi)型，由關(guān)鍵字 class 或 typename（建議用typename ） 后加一個(gè)標(biāo)識(shí)符構(gòu)成，

6、在這里兩個(gè)關(guān)鍵字的意義相同，它們表示后面的參數(shù)名代表一個(gè)潛在的內(nèi)置或用戶(hù)定義的類(lèi)型。函數(shù)模板用來(lái)創(chuàng)建一個(gè)通用函數(shù)，支持多種不同類(lèi)型形參。函數(shù)模板定義：template返回類(lèi)型 函數(shù)名(形式參數(shù)表)；/函數(shù)體函數(shù)模板實(shí)例template /T:模板類(lèi)型參數(shù)int compare(Ta, T b)if(ba) return 1;else if(ab) return -1;else return 0;int a,b;.if(0=compare(a,b) .string s1,s2;.if(1=compare(s1,s2).typename可以被class替換注意：函數(shù)模板不是普通函數(shù)，是具有特定操作

7、的一類(lèi)函數(shù)的設(shè)計(jì)框架。編譯時(shí)模板參數(shù)T被實(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在程序編譯時(shí)（非運(yùn)行時(shí),課本錯(cuò)誤）會(huì)被各種內(nèi)置（基本）類(lèi)型或用戶(hù)定義類(lèi)型所置換。 模板參數(shù)表的使用與函數(shù)形式參數(shù)表的使用相同，都是位置對(duì)應(yīng)。類(lèi)型和值的置換過(guò)程稱(chēng)為模板實(shí)例化 (template inst

8、antiation)。 形參size 表示 r_array 數(shù)組的長(zhǎng)度。6.1.1 函數(shù)模板及應(yīng)用模板實(shí)參推演：函數(shù)模板根據(jù)一組實(shí)際類(lèi)型或（和）值構(gòu)造出獨(dú)立的函數(shù)的過(guò)程通常是隱式發(fā)生的，稱(chēng)為模板實(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ù)最

9、大值為：dendl; string s=max(sa,5);cout 字典排序最大為：sendl; return 0;編譯器如何知道具體的參數(shù)類(lèi)型？非類(lèi)型模板形參模板形參不必都是類(lèi)型，可以為非類(lèi)型形參（補(bǔ)充知識(shí)： 數(shù)組作為函數(shù)形參）template void arr_init(T (&arr)N )for(int i=0;iN;i+) arri=0; int a42;double b10;arr_init(a); /顯示調(diào)用：arr_init(a);arr_init(b); /顯示調(diào)用：arr_init(b);表示什么？數(shù)組名作為函數(shù)參數(shù)傳遞的是數(shù)組的首地址， 當(dāng)作普通指針來(lái)處理，以下三個(gè)聲明

10、等價(jià)void test(int * arr); void test(int arr); void test(int arr10);數(shù)組訪問(wèn)越界問(wèn)題；也可以通過(guò)引用來(lái)傳遞數(shù)組，即傳遞數(shù)組本身（檢查邊界）void test(int (&arr)10); int i2=0,2; int k10=3;test(i);/ error test(k);/ okint (&arr)10: arr 指向具有10個(gè)int的數(shù)組int &arr10; 一個(gè)有10個(gè)引用類(lèi)型(整形)的數(shù)組同理 int * arr10; ：具有10個(gè)指針元素的數(shù)組； int (*arr)10; 指向具有10個(gè)數(shù)據(jù)元素的數(shù)組類(lèi)型形參和實(shí)

11、參的轉(zhuǎn)換1. 多個(gè)類(lèi)型形參的實(shí)參必須嚴(yán)格完全匹配template int compare(Ta, T b);short s1,s2;int x1,x2;compare(s1,s2); / ok compare(x1,x2);/okcompare(s1,x1);/ error 不能實(shí)例化compare(short, int);2.兩種轉(zhuǎn)換：const 轉(zhuǎn)換和數(shù)組或函數(shù)到指針的轉(zhuǎn)換const 轉(zhuǎn)換： 接受const引用或const指針的函數(shù)可以分別用非const 對(duì)象或者非const 指針來(lái)實(shí)例化。如果函數(shù)形參接受非引用類(lèi)型，形參和實(shí)參都忽略const數(shù)組或函數(shù)到指針的轉(zhuǎn)換：形參為非引用類(lèi)型，數(shù)組

12、名當(dāng)作指向第一個(gè)元素的指針(了解)template T fobj(T o1,T o2);template T fref(const T& r1, const T & r2);string s1(a value);const string s2(another value);fobj(s1,s2); /ok const s2 is igoredfref(s1,s2); / ok, non-const s1 is coverted to const referenceint a10,b40;fobj(a,b);/ok, T=int *;fref(a,b);/error 編寫(xiě)函數(shù)模板的原則1. 模板

13、參數(shù)用const 引用. template int compare(const T &a, const T &b)；可以用于不允許復(fù)制的類(lèi)型：比如IO類(lèi)型2. 函數(shù)體中如果有比較測(cè)設(shè)，進(jìn)來(lái)用單一關(guān)系運(yùn)算符if(ab) return 1;else if(ba) return -1;else return 0;if(ab) return 1;else if(ab) return -1;else return 0;設(shè)計(jì)模板時(shí)，T的類(lèi)型是什么？ofstream out1;ofstream out2=out1; / error 不允許兩個(gè)或以上的對(duì)象指向同一個(gè)輸入輸出流思考？template int c

14、ompare(const T &a, const T &b)if(ba) return 1;else if(ab) return -1;else return 0;int a,b;.if(0=compare(a,b) .string s1,s2;.if(compare(s1,s2).char *p1=world,*p2=class;if(1=compare(p1,p2). 比較的是什么？模板特化模板特化形式關(guān)鍵字template后面接一對(duì)空的；然后接模板名和，中指定特化的模板形參；函數(shù)形參表函數(shù)體template int compare(const char* const &v1, const

15、 char* const &v2)return strcmp(v1,v2);int a,b;.if(compare(a,b) .string s1,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ù)模板(functron template) 而生成的函數(shù)，稱(chēng)為模板函數(shù)(template function)。這兩個(gè)概念須分清楚。函數(shù)模板與模板函數(shù)：【例6.2】矩陣運(yùn)算：矩陣轉(zhuǎn)置與矩陣相乘函數(shù)模板。下標(biāo)作為參數(shù)傳遞。解決例5.5程序的通用性問(wèn)題。6.1.2 類(lèi)

16、模板類(lèi)模板定義：template class 類(lèi)名 /類(lèi)定義體返回類(lèi)型 成員函數(shù)名1(形參表)；/相當(dāng)于/返回類(lèi)型 成員函數(shù)名1(形參表)；; /再次指出分號(hào)不可少template 返回類(lèi)型 類(lèi)名:成員函數(shù)名1(形參表) ；/成員函數(shù)1定義體模板參數(shù)有兩種：模板類(lèi)型參數(shù)和模板非類(lèi)型參數(shù)。注意： 和函數(shù)模板一樣，類(lèi)模板的聲明和定義最好放在同一個(gè)文件，避免產(chǎn)生編譯錯(cuò)誤。 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 arrayT vect

17、ori;int size;public:array():size(i) /等效array()size=i;見(jiàn)4.4.3節(jié)（不等價(jià)）int find(const T &x)const;. .;templateint array:find(const T &x )const.模板非類(lèi)型參數(shù)：類(lèi)外必須聲明為函數(shù)模板類(lèi)模板參數(shù)必須指明無(wú)類(lèi)型聲明類(lèi)模板中的友元和成員模板1. 非模板類(lèi)或非模板函數(shù)可以是類(lèi)模板的友元template class Xfriend class Y; friend void fun();類(lèi)Y的成員可以訪問(wèn)類(lèi)模板任意實(shí)例的私有和受保護(hù)的成員。2. 函數(shù)模板或類(lèi)模板也可以聲明為類(lèi)模板

18、的友元template class Xtemplate friend class Y; template friend void fun();類(lèi)模板中的友元和成員模板3. 類(lèi)模板成員函數(shù)可以為模板函數(shù)template class X template void fun(IT i);/聲明;類(lèi)外定義template template void X:fun(IT i).6.1.2 類(lèi)模板與線性表線性表是數(shù)據(jù)結(jié)構(gòu)中的概念。數(shù)組中除第一個(gè)元素外，其他元素有且僅有一個(gè)直接前驅(qū)，第一個(gè)元素沒(méi)有前驅(qū)；除最后一個(gè)元素外，其他元素有且僅有一個(gè)直接后繼，最后一個(gè)元素?zé)o后繼。這樣的特性稱(chēng)為線性關(guān)系。所議稱(chēng)數(shù)組元素在

19、一個(gè)線性表中。線性表實(shí)際包括順序表（數(shù)組）和鏈表（后面章節(jié)）。線性表：273134109658724162189711511181214x013線性表圖例下標(biāo)以存儲(chǔ)整形數(shù)據(jù)為例：類(lèi)模板與線性表 對(duì)順序表的典型操作包括：計(jì)算表長(zhǎng)度，尋找變量或?qū)ο髕（其類(lèi)型與表元素相同）在表中的位置（下標(biāo)值），判斷x是否在表中，刪除x，將x插入列表中第i個(gè)位置，尋找x的后繼，尋找x的前驅(qū)，判斷表是否空，判斷表是否滿(mǎn)（表滿(mǎn)不能再插入數(shù)據(jù)，否則會(huì)溢出，產(chǎn)生不可預(yù)知的錯(cuò)誤），取第i個(gè)元素的值。 這些操作與數(shù)組封裝在一起可以定義一個(gè)類(lèi)，考慮到數(shù)組元素的類(lèi)型可以各不相同，所以定義為類(lèi)模板。 2731341096587241

20、62189711511181214x013圖b下標(biāo)6.1.2 類(lèi)模板與線性表 由編譯器編譯時(shí)分配內(nèi)存的數(shù)組稱(chēng)為靜態(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ò)誤，所以一般采用“大開(kāi)小用”的方法，即數(shù)組定義的較大，而實(shí)用較小。 為防止不可避免的溢出，應(yīng)在添加新數(shù)據(jù)時(shí)判斷表是否滿(mǎn)。靜態(tài)數(shù)組：使用靜態(tài)數(shù)組有什么缺點(diǎn)？（程序的通用性角度考慮）6.1.2 類(lèi)模板與線性表1431341096587241621892771185112110131234i圖a下標(biāo)14313410965872

21、41621897118511211013圖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è)元素拷入第i+1個(gè)元素,依此類(lèi)推，直到最后一個(gè)元素（下標(biāo)為10），現(xiàn)在表長(zhǎng)度為10。刪除順序表元素：6.1.2 類(lèi)模板與線性表1431341096587241621892771185112110135432i圖a下標(biāo)1273134109658724162189711511181214x013圖b下標(biāo)圖6.2 向表中插入一

22、個(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)的最后位置public: seqlist():Maxsize(size),last(-1) /初始化為空表 int

23、Length() constreturn last+1; /計(jì)算表長(zhǎng)度 int Find(const T & x)const; / 尋找x在表中位置（下標(biāo)） bool IsIn(const T & x)const ; /判斷x是否在表中 bool Insert(const T & x,int i); /x插入到列表中第i個(gè)位置處（下標(biāo)） bool Remove(const T & x); /刪除x int Next(const T & x); /尋找x的后繼位置 int Prior(const T & x); /尋找x的前驅(qū)位置 bool IsEmpty()return last=-1; /判

24、斷表是否空 bool IsFull()return last=Maxsize -1; /判斷表是否滿(mǎn) const T&Get(int i) const return ilast?NULL:slisti; /取第i個(gè)元素 T& operator(int i); /重載下標(biāo)運(yùn)算符()只考慮非const對(duì)象; 檢驗(yàn)主程序.2 排序與查找 6.2.2 常用的排序法6.2.1 常用查找方法 排序（sorting）： 是最重要的計(jì)算應(yīng)用之一。例如查字典，字典中的詞條是按序存放的，我們才能按字母順序找到要查的字。又如圖書(shū)館的藏書(shū)也是按書(shū)的編號(hào)有序排列的。在計(jì)算機(jī)上數(shù)據(jù)庫(kù)里的資料也是有序排列的。查找（sear

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

26、n;/英語(yǔ),物理,數(shù)學(xué)和電子學(xué)成績(jī);學(xué)號(hào)可作為主關(guān)鍵字。 如果關(guān)鍵字小的排在前面，我們稱(chēng)為升序排列，反之為降序排列。這時(shí)可以采用對(duì)半查找（binary search）。 6.2.1 常用查找方法low mid high首先安排兩個(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ì)半查找:low8917131120719212331262925

27、373923查找lowmidhigh2021292623313739midhighlow202123midhigh23成功圖6.3 查找成功例16806.2.1 常用查找方法對(duì)半查找25781113179192023212629313710查找low39midhigh25781113179lowmidhigh1113179lowmidhigh9low mid high圖6.4 查找失敗例注意：low=mid+1和high=mid-1非常重要.0836.2.1 常用查找方法【例6.4】對(duì)半查找遞歸算法，作為有序表模板類(lèi)成員函數(shù)。遞歸方法易讀易懂，但效率低。注意遞歸的隱式循環(huán)代碼編寫(xiě)?！纠?.5】

28、對(duì)半查找迭代算法。該例中迭代算法的可讀性也不差，效率要高于遞歸。注意迭代的顯式循環(huán)代碼編寫(xiě) 的關(guān)鍵點(diǎn)。*本例中出現(xiàn)的成員函數(shù)Binarysearch(T & x)const ，稱(chēng)為 const成員函數(shù)，該函數(shù)保證只讀。相應(yīng)節(jié)點(diǎn)對(duì)象重載的比較運(yùn)算符也必須是const。【例6.4】對(duì)半查找遞歸算法，作為有序表模板類(lèi)成員函數(shù)。遞歸方法易讀易懂，但效率低。注意遞歸的隱式循環(huán)代碼編寫(xiě)。6.2.1 常用查找方法例6.5節(jié)點(diǎn)對(duì)象重載的比較運(yùn)算符：templateclass Element T key;/ 其他域省略public: bool operator( Element ele)constreturn

29、key=1)個(gè)元素sli時(shí),前面的元素sl0,sl1,sli-1已經(jīng)排好序,我們將sli的關(guān)鍵字與sli-1, sli-2,的關(guān)鍵碼順序進(jìn)行比較,找到第一個(gè)比它小的,則sli插到該元素之后。i0123456temp初始序列8679452616879452726789452936789452444678952554567892262456789直接插入排序算法中用了一個(gè)臨時(shí)變量temp，要插入的元素放到temp中，這樣插入前各元素后移時(shí)允許將該元素沖掉。6.6.2 常用的排序法【例6.6】升序直接插入排序算法(算法演示)*(2)對(duì)半插入排序（Binary Insert Sort）是用對(duì)半查找的思

30、想取代順序查找。對(duì)半插入排序要快于插入排序。（略）【例6.7】升序?qū)Π氩迦肱判蛩惴ㄋ惴ㄓ袥](méi)有改進(jìn)的地方？從執(zhí)行效率角度結(jié)合查找算法分析。6.2.2 常用的排序法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ā)生交換。494949

31、494913383838381349656565133838979713656565761397979797137676767676272727272727494949494949冒泡排序示例49131313131313133849272727272727653849383838383897653849494949497697654949494949137697656565656527277697767676764949497697979797圖6.6從下往上掃描的冒泡程序 6.2.2 常用的排序法3選擇排序（Selection Sort，略）基本思想是：每一趟從待排序的記錄中選出關(guān)鍵字最小的

32、元素，順序放在已排好序的子序列的后面，直到全部記錄排序完成。直接選擇排序（Straight Selection Sort）是最簡(jiǎn)單的。此方法的最大優(yōu)點(diǎn)是易讀。缺點(diǎn)是做過(guò)的工作和序列的部分有序性利用不上，效率低。選擇排序中也有可能利用到以前的工作的方法，如堆排列（Heap Sort） 49386597761327491338659776492749132765977649384913273897764965491327384976976549132738494997657613273849496597761327384949657697 圖6.7直接選擇排序的過(guò)程6.3 索引查找與指針數(shù)組 指針

33、數(shù)組： 數(shù)據(jù)元素為指針的數(shù)組稱(chēng)指針數(shù)組 。 類(lèi)型 * 數(shù)組名size/常量; int * arr10;arr： 包含10個(gè)指針元素的數(shù)組注意和指向數(shù)組的指針區(qū)別類(lèi)型 (* 數(shù)組名)size; int (* arr)10;arr:指向含有10個(gè)整形數(shù)據(jù)的一維數(shù)組索引查找（略）： 6.3索引查找與指針數(shù)組字符型指針數(shù)組可以實(shí)現(xiàn)字符串?dāng)?shù)組的功能。這些字符串的長(zhǎng)度可以不等；所以用指針數(shù)組更方便。如存儲(chǔ)每周7天的英文名稱(chēng)，可定義一個(gè)char*name7的一維字符指針數(shù)組，如圖6.9。name5name2name0name1name3name4name6“Wednesday”“Friday”“Monday

34、”“Sunday”“Tuesday”“Thursday”“Saturday”圖6.9 字符指針數(shù)組指針數(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)和字符串類(lèi)。運(yùn)算符的重載可以由對(duì)象成員的重

35、載的運(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ù)和運(yùn)算符，直接訪問(wèn)私有數(shù)據(jù)成員，實(shí)現(xiàn)通用算法。這是標(biāo)準(zhǔn)的面向?qū)ο蟮姆椒ā?2) 獨(dú)立的（非成員函數(shù)）函數(shù)模板處理模板

36、類(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í)別指針內(nèi)置類(lèi)型int x;int *p=&x;類(lèi)類(lèi)型class x;class *p;p=&x;數(shù)組int x10;int *p=x;函數(shù)int fun();6.5函數(shù)指針與指針識(shí)別指向函數(shù)而非指向?qū)ο蟮闹羔?，函?shù)指針的類(lèi)型由其返回類(lèi)型和形參表來(lái)確定，與函數(shù)名無(wú)關(guān)。定義方式如下：返回類(lèi)型 (*指針變量名)(參數(shù)表)例： bool (*pf)(const string&, const string &);指針pf 指向返回值

37、為bool類(lèi)型且?guī)в袃蓚€(gè)為const string & 形參的函數(shù)。注意： 與下面聲明的區(qū)別()優(yōu)先級(jí)高于*bool *pf(const string&, const string &); 函數(shù)指針：6.5函數(shù)指針與指針識(shí)別typedef 簡(jiǎn)化函數(shù)指針的定義,格式如下typedef bool (*pFun)(const string&,const string &);pFun: 指向函數(shù)的指針類(lèi)型名定義和初始化如下：bool compare(const string &, const string &);pFun pf1=0; pFun pf2=compare;/隱式pf1=pf2; pf2=

38、&compare; /顯式注意：函數(shù)指針可以初始化為0，且指向不同類(lèi)型的函數(shù)指針不能相互轉(zhuǎn)化。6.5函數(shù)指針與指針識(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)用typedef bool (*pFun)(const string&,const string &);bool compare1(const string &, const string &);int compare2(const string

39、&, const string &);pFun pf1=compare1; /okpFun pf1=compare2; /error6.5.2指向類(lèi)成員的指針（選讀） 在類(lèi)對(duì)象中有隱含的this指針，用以正確訪問(wèn)成員函數(shù)。所以指向類(lèi)成員函數(shù)的指針有其特殊性。 指向類(lèi)成員函數(shù)的指針： 成員函數(shù)有一個(gè)非成員函數(shù)沒(méi)有的屬性：它所屬的類(lèi)（class）。所以指向成員函數(shù)的指針需要三個(gè)方面的匹配：參數(shù)的類(lèi)型和個(gè)數(shù)，返回類(lèi)型和所屬的類(lèi)類(lèi)型。6.5.2指向類(lèi)成員的指針（選讀）定義指向類(lèi)成員函數(shù)的指針的說(shuō)明及初始化：必須在三個(gè)方面嚴(yán)格匹配(1) 函數(shù)形參類(lèi)型和數(shù)目，包括函數(shù)是否為const(2) 函數(shù)返回類(lèi)型(

40、3) 所屬類(lèi)的類(lèi)型 以指向商品類(lèi) GetPrice()函數(shù)的指針為例：float (CGoods:*pf)() const =&CGoods:GetPrice; 不能寫(xiě)成float (CGoods:*pf)() const = CGoods:GetPrice; /錯(cuò)誤上述定義可簡(jiǎn)化為typedef float (CGoods:*pFun)() const;pFun pf=&CGoods:GetPrice; class CGoodsfloat GetPrice() const;6.5.2指向類(lèi)成員的指針（選讀）成員函數(shù)指針的用法(綁定)：CGoods car,*p=&car;(car.*pf)(

41、); / 注意不能寫(xiě)成這樣car.*pf(); 編譯錯(cuò)誤 ()不能省略/將指針pf與對(duì)象car綁定，最終等效調(diào)用car. GetPrice ();(p-*pf)();/指針?lè)绞秸{(diào)用上式表示指針pf與對(duì)象car綁定，指向了car. GetPrice ()。所以指向成員函數(shù)的指針存儲(chǔ)的不是成員函數(shù)的地址，綁定后才獲得地址。課本錯(cuò)誤：也可以用對(duì)象代替類(lèi)進(jìn)行初始化，效果一樣：CGoods car,motor;float (CGoods:*pf)()=motor.GetPrice; typedef float (CGoods:*pFun)() const;pFun pf=&CGoods:GetPrice

42、;/&不可省 error: ISO C+ forbids taking the address of a bound member function to form a pointer to member function.6.5.2指向類(lèi)成員的指針（選讀）普通函數(shù)指針int (*p)(double);成員函數(shù)指針int (className:*p)(double); 普通函數(shù)指針存儲(chǔ)函數(shù)的地址，可以直接用來(lái)調(diào)用指定函數(shù)。成員函數(shù)指針必須首先被綁定在一個(gè)對(duì)象或指針上，才能獲得被調(diào)用對(duì)象的this指針，然后才能調(diào)用指針?biāo)赶虻某蓡T函數(shù)。6.5.3 指針的識(shí)別方法（選讀） 說(shuō)明中包括多種說(shuō)明符容易

43、造成閱讀和理解的困難。一種理解和構(gòu)造對(duì)象說(shuō)明的方法是：先撇開(kāi)標(biāo)識(shí)符，按從右到左的順序逐個(gè)解釋每個(gè)說(shuō)明符，如果有括號(hào)則改變解釋的先后，先解釋括號(hào)內(nèi)再解釋擴(kuò)號(hào)外。例如：int *arrp5;- int * 5;按下列順序理解：五個(gè)元素的數(shù)組、每個(gè)元素是一個(gè)指針、指針指向整型，所以 arrp 是一個(gè)有五個(gè)整型指針作為數(shù)組元素的數(shù)組。int (*parr)5;-int (*) 5;是一個(gè)指針，指針指向一個(gè)包含五個(gè)元素的數(shù)組，每個(gè)元素是一個(gè)整型，所以 parr 是一個(gè)指向五個(gè)整型數(shù)的數(shù)組的指針。復(fù)雜說(shuō)明閱讀和理解的方法：6.5.3 指針的識(shí)別方法（選讀）答案：int i; 是一個(gè)整型的變量；int *i

44、p; 是一個(gè)指向整型變量的指針，即 ip 中存儲(chǔ)的是另一個(gè)整型變量的地址；int f(); 是一個(gè)返回整型值的函數(shù)；int *fp(); 是一個(gè)返回整型指針的函數(shù)，即 fp 返回的是一個(gè)指向整型變量的指針；int (*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ù)組

45、，每個(gè)指針指向一個(gè)返回int的無(wú)參函數(shù)fpa 是一個(gè)指向數(shù)組的指針，該數(shù)組的每個(gè)元素都是一個(gè)指 向函數(shù)的指針，而所指的函數(shù)的返回值是整型。復(fù)雜說(shuō)明的實(shí)例：int *(*pfp)(),a5, *ap5,(*pa)5, (*fap5)(), (*(*fpa)5)(); int (*(*fap)(); 1. (*fap) 是個(gè)指針;2 (*fap) :指向一個(gè)數(shù)組;3 int (*(*fap)(); 數(shù)組的元素是指向返回類(lèi)型為int 的無(wú)參函數(shù)指針6.5.3 指針的識(shí)別方法（選讀）int f1() return 1;int f2() return 2;int f3() return 3;int (*

46、(*pf)3)();int (*arr3)()=f1,f2,f3; /arr0=f1; arr1=f2;arr2=f3;pf=&arr; /一維數(shù)組arr的引用cout(*pf)2()endl; /calls f3();cout(arr2)()endl; /等價(jià)調(diào)用6.5.3 指針的識(shí)別方法（選讀）返回指向函數(shù)的指針int ( *pf(int)(int *, int);閱讀技巧： 從名字開(kāi)始，從里向外理解pf(int)pf為一個(gè)函數(shù)，帶一個(gè)int形參，返回值為：int (*)(int *, int);指向函數(shù)的指針，函數(shù)返回int并帶int*和int形參利用typedef簡(jiǎn)化函數(shù)指針的定義 t

47、ypedef int (FF*)(int *, int);FF pf(int); /pf返回一個(gè)指向函數(shù)的指針第六章 模板與數(shù)據(jù)結(jié)構(gòu)作業(yè)： 將學(xué)生成績(jī)管理系統(tǒng)中的成績(jī)管理類(lèi)設(shè)計(jì)成類(lèi)模板class Studentprivate:string m_id,m_name;int m_math,m_eng,m_phy;templateclass Managementfriend class Student;/可以訪問(wèn)Student類(lèi)私有數(shù)據(jù)private:vector mv_stu;/vector stu; / 存儲(chǔ)所有學(xué)生的信息;【例6.2】矩陣運(yùn)算template void inverse(T1 *

48、mat1,T2 *mat2,int a,int b) int i,j; for (i=0;ib;i+) for (j=0;ja;j+) mat2ji=mat1ij; return; 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 = 0; for(k=0;kb;k+) resultij+=mat1ik*mat2kj; return;【例6.2】矩陣運(yùn)算template void output(T *mat,

49、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.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

50、,middle,6,3); /顯式：inverse (matrix1,middle,6,3); multi(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】順序表類(lèi)模板template int seqlist:Find(T & x)const/const表示該函數(shù)的t

51、his指針為const，即被訪問(wèn)對(duì)象的數(shù)/據(jù)不能被修改。如被修改編譯器會(huì)警告，防止編程時(shí)失誤。 int i=0; while(ilast) return -1; /未找到，返回-1 else return i; /找到，返回下標(biāo)【例6.3】順序表類(lèi)模板template bool seqlist:IsIn(T & x) int i=-1; bool found=0; while(i=last & !found) /換了一種方法來(lái)查找 if (slist+i=x) found=1; /找到 return found;template T& seqlist:operator(int i) if(il

52、ast|ilast+1|i=Maxsize) last永遠(yuǎn)小于Maxsize cout下標(biāo)出界！endl; exit(1);/程序運(yùn)行結(jié)束，不合理，動(dòng)態(tài)內(nèi)存無(wú)法釋放 return slisti;【例6.3】順序表類(lèi)模板template bool seqlist:Insert(T & x, int i) int j; if (ilast+1|last=Maxsize -1) return false; /插入位置不合理，不能插入（健壯性） else last+; for(j=last;ji;j-) slistj=slistj-1; /從表最后位置向前依次后移，空出指定位置來(lái) slisti=x;

53、return true; 【例6.3】順序表類(lèi)模板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】順序表類(lèi)模板template int seqlist:Next(T & x)int i=Find(x);if(i=0 & ilast) return i+1; /x后繼位置else return -1; /x不在表中

54、，或在表末尾template int seqlist:Prior(T & x)int i=Find(x);if(i0 & i=last) return i-1; /x前驅(qū)的位置else return -1; 【例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 (!seqlisti.Insert(aj,j) cout表太大放不下了!endl; break; j=seqlisti.Length(

55、); 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;j+) coutseqlistij ; /coutendl; k=7; if (seqlisti.IsIn(k) cout

56、素?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 (seqlisti.Insert(k,j-1) / 把素?cái)?shù)17裝回去,成功則打印 j=seqlisti.Length ( ); for

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

58、 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(const 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(xs

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

60、實(shí)際是元素關(guān)鍵字的比較 template class 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|l