C++程序設(shè)計(jì)第6章2

1、習(xí)題：習(xí)題： 講義講義P217 基本概念與基礎(chǔ)知識自測題基本概念與基礎(chǔ)知識自測題 、習(xí)題、習(xí)題6.6本周實(shí)驗(yàn)：本周實(shí)驗(yàn)： 1） 習(xí)題習(xí)題6.6、 2）課堂補(bǔ)充題，調(diào)試并上傳）課堂補(bǔ)充題，調(diào)試并上傳預(yù)習(xí)：預(yù)習(xí)：6.4、第、第7章章7.17.3第第6章模板與數(shù)據(jù)結(jié)構(gòu)要求：章模板與數(shù)據(jù)結(jié)構(gòu)要求：（1）理解函數(shù)模板與類模版；）理解函數(shù)模板與類模版；（2）線性表：掌握模板編寫程序的方法，掌握順序表在）線性表：掌握模板編寫程序的方法，掌握順序表在 內(nèi)存中的分配與使用；內(nèi)存中的分配與使用；（3）掌握主要查找與排序的算法；）掌握主要查找與排序的算法；（4）模板與類參數(shù)，理解類型參數(shù)和參數(shù)化類型（模板）模板與類

2、參數(shù)，理解類型參數(shù)和參數(shù)化類型（模板） 注：本章注：本章6.5節(jié)不要求節(jié)不要求 .2 排序與查找排序與查找 人們經(jīng)常需要在一個數(shù)據(jù)集合中搜尋滿足特定條件的人們經(jīng)常需要在一個數(shù)據(jù)集合中搜尋滿足特定條件的數(shù)據(jù)元素?cái)?shù)據(jù)元素。 為了提高查找效率，應(yīng)當(dāng)先對集合中的數(shù)據(jù)進(jìn)行排序?yàn)榱颂岣卟檎倚剩瑧?yīng)當(dāng)先對集合中的數(shù)據(jù)進(jìn)行排序 查找查找 : : 從一個從一個數(shù)據(jù)集合數(shù)據(jù)集合中找出中找出特定元素特定元素的過程。的過程。 數(shù)據(jù)集合中的元素一般是同類型的對象。數(shù)據(jù)集合中的元素一般是同類型的對象。 特定元素特定元素: : 某個域具有特定的值。某個域具有特定的值。 用以區(qū)分各數(shù)據(jù)元素的域稱為用以區(qū)分各數(shù)據(jù)元素的域稱為關(guān)

3、鍵域或關(guān)鍵字關(guān)鍵域或關(guān)鍵字。順序查找順序查找: :依次地考察數(shù)據(jù)集合中的每個元素依次地考察數(shù)據(jù)集合中的每個元素。順序查找的執(zhí)行時間函數(shù)的階為順序查找的執(zhí)行時間函數(shù)的階為 n (n (線性階線性階) )。 若數(shù)據(jù)集合中的元素是有序的，并存貯在一維數(shù)組中，若數(shù)據(jù)集合中的元素是有序的，并存貯在一維數(shù)組中，就可以使用效率較高的折半查找方法。就可以使用效率較高的折半查找方法。6.2.1 常用查找方法常用查找方法 順序查找：順序查找：從第一個元素開始，順序查找直到找到或查到最后一個元素為止。從第一個元素開始，順序查找直到找到或查到最后一個元素為止。 查找是按查找是按關(guān)鍵字關(guān)鍵字（key word）進(jìn)行?？?/p>

4、以唯一地把資料區(qū)分出來）進(jìn)行。可以唯一地把資料區(qū)分出來的數(shù)據(jù)被稱為的數(shù)據(jù)被稱為主關(guān)鍵字主關(guān)鍵字。如學(xué)生的資料如學(xué)生的資料(結(jié)構(gòu)體變量結(jié)構(gòu)體變量):struct studentint id ; /學(xué)號學(xué)號char name20; / 姓名姓名char sex; / 性別性別int age; / 年齡年齡char address60; /家庭地址家庭地址float eng, phy,math , electron; /英語英語, ,物理物理, ,數(shù)學(xué)和電子學(xué)成績數(shù)學(xué)和電子學(xué)成績; 學(xué)號可作為學(xué)號可作為主關(guān)鍵字主關(guān)鍵字。 如果關(guān)鍵字小的排在前面，我們稱為升序排列，反之為降序排列。如果關(guān)鍵字小的排在前

5、面，我們稱為升序排列，反之為降序排列。這時可以采用這時可以采用對半查找對半查找（binary search）。 8917131120719212331262925373923查找查找midlowhigh2021292623313739lowmidhigh202123lowmid high23low mid high查找成功例查找成功例有序數(shù)據(jù)有序數(shù)據(jù)方法之一：方法之一：對半查找對半查找 定義兩個指針定義兩個指針low和和high指向首尾兩元素，取指向首尾兩元素，取mid= (low+high)/2，如，如mid指向元素是所查找的，則結(jié)束。如果該元指向元素是所查找的，則結(jié)束。如果該元素關(guān)鍵字大了

6、，則取素關(guān)鍵字大了，則取low=mid +1， high不變，繼續(xù)查找；如果該元素不變，繼續(xù)查找；如果該元素關(guān)鍵字小了，則取關(guān)鍵字小了，則取 high=mid-1，low不變，繼續(xù)查找。如果查到不變，繼續(xù)查找。如果查到lowhigh仍未找到，則失敗，停止。仍未找到，則失敗，停止。low25781113179192023212629313710查找查找39midhigh25781113179lowmidhigh1113179low midhigh9low mid high查找失敗例查找失敗例 while （區(qū)間低端值不大于高端值區(qū)間低端值不大于高端值） 計(jì)算區(qū)間的中點(diǎn)下標(biāo)值；計(jì)算區(qū)間的中點(diǎn)下標(biāo)值

7、； if （中點(diǎn)處的元素值等于指定值中點(diǎn)處的元素值等于指定值） 返回區(qū)間中點(diǎn)的下標(biāo)返回區(qū)間中點(diǎn)的下標(biāo) ； else 確定下一步考察的區(qū)間確定下一步考察的區(qū)間； 對半查找算法對半查找算法: :【例例6.4】對半查找遞歸算法，作為有序表模板類成員對半查找遞歸算法，作為有序表模板類成員函數(shù)。遞歸方法易讀易懂，但效率低。函數(shù)。遞歸方法易讀易懂，但效率低。（自學(xué)）（自學(xué)）【例例6.5】對半查找迭代算法。對半查找迭代算法。該例中迭代算法的可讀性也不差，效率要高于遞歸。該例中迭代算法的可讀性也不差，效率要高于遞歸。*本例中出現(xiàn)的成員函數(shù)本例中出現(xiàn)的成員函數(shù)Binarysearch(T & x)const ，

8、稱為稱為 const成員函數(shù)，該函數(shù)保證只讀。相應(yīng)節(jié)點(diǎn)對象成員函數(shù)，該函數(shù)保證只讀。相應(yīng)節(jié)點(diǎn)對象重載的比較運(yùn)算符也必須是重載的比較運(yùn)算符也必須是const。 const函數(shù)的函數(shù)的this指針?biāo)笇ο鬄槌Ａ?，即它不能修改對指針?biāo)笇ο鬄槌Ａ浚此荒苄薷膶ο蟮臄?shù)據(jù)成員，而且在函數(shù)體內(nèi)只能調(diào)用象的數(shù)據(jù)成員，而且在函數(shù)體內(nèi)只能調(diào)用const成員函數(shù)，成員函數(shù)，不能調(diào)用其他成員函數(shù)。如果編程時不慎修改對象的數(shù)據(jù)不能調(diào)用其他成員函數(shù)。如果編程時不慎修改對象的數(shù)據(jù)成員，編譯器會報錯。成員，編譯器會報錯。 【例【例6.5】對半查找迭代算法對半查找迭代算法。template int Orderedlist:

9、BinarySearch( const T & x)const int high=last ,low=0,mid; / last 當(dāng)前有序表最大下標(biāo)當(dāng)前有序表最大下標(biāo) while(low=high) mid=(low+high)/2; if(xslistmid) high=mid-1; /左縮查找區(qū)間左縮查找區(qū)間 else if(slistmidx) low=mid+1; / 右縮查找區(qū)間右縮查找區(qū)間 else return mid; if(slistmid!=x)mid=-1; return mid; class Elementint key;/ 其他域省略其他域省略public:bool

10、operator(Element ele)const return keyele.key; bool operator!=(Element ele)const return key!=ele.key; void putkey(int k) key=k; /要尋找的元素要尋找的元素 void show() coutkeyt; ；/重載比較運(yùn)算符，元素比較，實(shí)際是元素關(guān)鍵域的比較重載比較運(yùn)算符，元素比較，實(shí)際是元素關(guān)鍵域的比較int main() const int h=19; int i,k=47; Orderedlist ordlist; int ah=2,3,5,7,11,13,17,19,

11、23,29,31,37,41,43, 47,53,59,61,67; /升序升序 Element nh,elem; for(i=0;ih;i+) ni.putkey(ai); /用用ai為當(dāng)前對象為當(dāng)前對象ni賦值賦值 for(i=0;ih;i+) ordlist.Insert(ni,i); /在線性表尾插入，建立升序順序表在線性表尾插入，建立升序順序表 ordlist.print(); elem.putkey(k); i=ordlist.Binarysearch(elem); cout整數(shù)整數(shù)k在表中位置（下標(biāo)）：在表中位置（下標(biāo)）：iendl; k=33; elem.putkey(k);

12、i=ordlist.Binarysearch(elem); cout整數(shù)整數(shù)k在表中位置（下標(biāo)）：在表中位置（下標(biāo)）：iendl; return 0;6.6.2 常用的排序法常用的排序法排序功能排序功能: : 將數(shù)據(jù)元素的無序序列調(diào)整為一個有序序?qū)?shù)據(jù)元素的無序序列調(diào)整為一個有序序列。列。 數(shù)據(jù)元素中一般有多個數(shù)據(jù)項(xiàng)，排序可選擇其中數(shù)據(jù)元素中一般有多個數(shù)據(jù)項(xiàng)，排序可選擇其中一個可排序的數(shù)據(jù)項(xiàng)（可進(jìn)行比較運(yùn)算）作為依據(jù)，一個可排序的數(shù)據(jù)項(xiàng)（可進(jìn)行比較運(yùn)算）作為依據(jù)，稱為稱為排序關(guān)鍵字排序關(guān)鍵字。 為了能使用高效率的折半查找算法，通常希望數(shù)為了能使用高效率的折半查找算法，通常希望數(shù)據(jù)序列按關(guān)鍵域有

13、序排列。據(jù)序列按關(guān)鍵域有序排列。排序：將數(shù)據(jù)元素的任意序列重新排列成按關(guān)鍵域有排序：將數(shù)據(jù)元素的任意序列重新排列成按關(guān)鍵域有序的序列。序的序列。 和查找相比，排序相對費(fèi)時。是否要對數(shù)組排序，和查找相比，排序相對費(fèi)時。是否要對數(shù)組排序，取決于對數(shù)組的訪問次數(shù)。取決于對數(shù)組的訪問次數(shù)。 從小到大排序稱從小到大排序稱升序升序，反之為，反之為降序降序。 最常見的是最常見的是插入排序插入排序、選擇排序選擇排序和和交換排序交換排序。 1 8 10 24 35 58 60 24 8 35 1 60 10 58 8 24 35 1 60 10 58 8 24 35 1 60 10 58 1 8 24 35 6

14、0 10 581插入排序插入排序(Insert Sorting)設(shè)整數(shù)數(shù)組為設(shè)整數(shù)數(shù)組為a： 24 8 35 1 60 10 58排序目標(biāo)是使數(shù)組元素按升序排列。排序目標(biāo)是使數(shù)組元素按升序排列。對具有對具有n個元素的數(shù)組插入排序需要處理個元素的數(shù)組插入排序需要處理(n1)遍。遍。排序過程：排序過程： 第第i遍處理時，按冒泡方式將遍處理時，按冒泡方式將ai插入已排序部分。插入已排序部分。直接插入排序直接插入排序:【例【例6.66.6】升序直接插入排序算法】升序直接插入排序算法templatevoid Orderedlist:InsertSort()T temp;int i,j;for (i=1;

15、i0&tempslistj-1)slistj=slistj-1;j-; /查找與移動同時做查找與移動同時做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 h=10; Element nh;int i;Orderedlist ordlist;string m

16、slisth=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.76.7】升序?qū)Π氩迦肱判蛩惴ā可驅(qū)Π氩迦肱判蛩惴ㄓ脤Π氩檎宜枷肴〈樞虿檎遥煊诓迦肱判颍┯脤Π氩檎宜枷肴〈樞虿檎遥?/p>

17、于插入排序）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) / /請注意與對半查找的不同之處請注意與對半查找的不同之處 mid=(low+high)/2;if(temp=low;j-) slistj+1=slistj; slistlow=temp; 插入排序：插入排序： 在每次循環(huán)中設(shè)法把一個元素插入到已經(jīng)排序的部分在每次循環(huán)中設(shè)法把一個元素插入到已經(jīng)排序的部分

18、序列里的合適位置，是得到的序列任然是有序的。序列里的合適位置，是得到的序列任然是有序的。 當(dāng)被處理的最后一個元素也插入到有序序列后，整個當(dāng)被處理的最后一個元素也插入到有序序列后，整個排序工作完成。排序工作完成。優(yōu)點(diǎn)：優(yōu)點(diǎn)： 利用一個一個元素的插入比較，將元素放入適當(dāng)?shù)奈焕靡粋€一個元素的插入比較，將元素放入適當(dāng)?shù)奈恢檬且环N簡單的排序方式。置是一種簡單的排序方式。缺點(diǎn)：缺點(diǎn)： 由于每插入一個元素都必須與之前已排序好的元素比由于每插入一個元素都必須與之前已排序好的元素比較，需要花費(fèi)較長時間。較，需要花費(fèi)較長時間。 2 . 交換排序交換排序 設(shè)數(shù)組有設(shè)數(shù)組有n n個元素，目標(biāo)是使數(shù)組元素按個元素，目

19、標(biāo)是使數(shù)組元素按升序升序排列。排列。在最壞情況下，冒泡排序方法也要對數(shù)組處理在最壞情況下，冒泡排序方法也要對數(shù)組處理(n-1)(n-1)遍。遍。 冒泡排序冒泡排序 交換排序的基本思想是按關(guān)鍵字兩兩排序?qū)ο?，如果交換排序的基本思想是按關(guān)鍵字兩兩排序?qū)ο螅绻l(fā)生逆序則交換之，直到所有的對象都排好序?yàn)橹?。發(fā)生逆序則交換之，直到所有的對象都排好序?yàn)橹埂?將相鄰的兩個數(shù)據(jù)加以比較，若下面一個小于上面一將相鄰的兩個數(shù)據(jù)加以比較，若下面一個小于上面一個，則兩數(shù)交換，若下面一個大于上面一個，則兩個位置個，則兩數(shù)交換，若下面一個大于上面一個，則兩個位置不變。繼續(xù)將上面一個小的值與它上面的值進(jìn)行比較，重不變。繼

20、續(xù)將上面一個小的值與它上面的值進(jìn)行比較，重復(fù)此操作，直到比較到最上面一個值。（完成一次排序）復(fù)此操作，直到比較到最上面一個值。（完成一次排序）第第1 1遍冒泡處理過程遍冒泡處理過程iai045451151527070334344602852860 iai045454511515152707070334342846028345286060第第1 1遍冒泡處理過程遍冒泡處理過程iai045454545115151515270707028334342870460283434528606060第第1 1遍冒泡處理過程遍冒泡處理過程iai045454545451151515151527070702828

21、334342870704602834343452860606060第第1 1遍冒泡處理過程遍冒泡處理過程iai第一遍第一遍處理后處理后045454545451511515151515452707070282828334342870707046028343434345286060606060第第1 1遍冒泡處理過程遍冒泡處理過程對數(shù)組對數(shù)組 a 進(jìn)行各遍冒泡處理的結(jié)果進(jìn)行各遍冒泡處理的結(jié)果第第 1 遍遍第第 2 遍遍第第 3 遍遍第第 4 遍遍iai處理后處理后處理后處理后處理后處理后處理后處理后04515151515115452828282702845343433470344545460347

22、0606052860607070第第1 1遍冒泡：遍冒泡：a0a5的最小元素上冒到的最小元素上冒到a0；第第2 2遍冒泡：遍冒泡：a1a5的最小元素上冒到的最小元素上冒到a1；第第i+1i+1遍冒泡：遍冒泡：aia5的最小元素上冒到的最小元素上冒到ai；for(i=0;ii; k-) /第第i次冒泡次冒泡 if(slistk-1slistk) 交換兩者；交換兩者； 改進(jìn)算法改進(jìn)算法過程當(dāng)中排好序，則提前終止冒泡過程當(dāng)中排好序，則提前終止冒泡noswap=true;noswap=false; /發(fā)生交換發(fā)生交換if(noswap) break; /終止終止i循環(huán)循環(huán)【例【例6.86.8】冒泡排序

23、算法】冒泡排序算法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; /本趟無交換，則終止算法。本趟無交換，則終止算法。 3選擇排序（選擇排序（Selection Sort）基本思想：基本思想：每一趟從待排序的記錄中選出關(guān)鍵字最每一趟從待排序的記錄中選出關(guān)鍵字最小

24、的元素，順序放在已排好序的子序列的后面，直小的元素，順序放在已排好序的子序列的后面，直到全部記錄排序完成。到全部記錄排序完成。4938659776132749 1338659776492749 1327659776493849 1327389776496549 1327384976976549 1327384949976576 1327384949659776 1327384949657697【例【例6.96.9】直接選擇排序】直接選擇排序作為作為Orderedlist類的成員函數(shù)。類的成員函數(shù)。 template void Orderedlist:SelectSort() int i,j,k

25、;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; 算法：算法：1 初始化初始化2 while (i a1.length) & (j a2.length) 將將a1i、a2j中的較小者送入中的較小者送入anew； 指向較小元素的指針后移一個位置指向較小元素的指針后移一個位置 3 while (a1尚有剩余元素尚有剩余元素) 將將a1剩余

26、元素添到新數(shù)組尾部剩余元素添到新數(shù)組尾部 4 while (a2尚有剩余元素尚有剩余元素) 將將a2剩余元素添到新數(shù)組尾部剩余元素添到新數(shù)組尾部 合并合并 問題：問題：將兩個有序的數(shù)組合并成一個有序的數(shù)組。將兩個有序的數(shù)組合并成一個有序的數(shù)組。a1 a24 6 8 10 11 14 3 5 5 9 i j anew: k=0 a1 a24 6 8 10 11 14 3 5 5 9 i j anew: k=1 3 a1 a24 6 8 10 11 14 3 5 5 9 i j anew: k=2 3 4 a1 a24 6 8 10 11 14 3 5 5 9 i j anew: k=3 3 4

27、5 a1 a24 6 8 10 11 14 3 5 5 9 i j anew: k=4 3 4 5 5 a1 a24 6 8 10 11 14 3 5 5 9 i j anew: k=5 3 4 5 5 6 a1 a24 6 8 10 11 14 3 5 5 9 i j anew: k=6 3 4 5 5 68 a1 a24 6 8 10 11 14 3 5 5 9 i j anew: k=7 3 4 5 5 6 8 9 a1 a24 6 8 10 11 14 3 5 5 9 i j anew: k=8 3 4 5 5 6 8 910a1 a24 6 8 10 11 14 3 5 5 9 i

28、j anew: k=8 3 4 5 5 6 8 910 11a1 a24 6 8 10 11 14 3 5 5 9 i j anew: k=8 3 4 5 5 6 8 910 11 14template void Orderedlist:Merge(Orderedlist & ls1,Orderedlist & ls2)int i=0,j=0,k=0;while(i=ls1.last)&(j=ls2.last)if(ls1.slistils2.slistj) slistk=ls1.slisti; i+; else slistk=ls2.slistj; j+; k+; last+;while(i

29、=ls1.last) /復(fù)制第一個表的剩余元素復(fù)制第一個表的剩余元素slistk=ls1.slisti; i+;k+; last+;while(j=ls2.last) /復(fù)制第二個表的剩余元素復(fù)制第二個表的剩余元素slistk=ls2.slistj; j+;k+; last+;6.4 模板與類參數(shù)模板與類參數(shù) 以類對象作為函數(shù)的實(shí)參，實(shí)現(xiàn)被積函數(shù)以類對象作為函數(shù)的實(shí)參，實(shí)現(xiàn)被積函數(shù)( (類對象的類對象的成員函數(shù)成員函數(shù)) )的傳遞：的傳遞： 【例【例6.12】設(shè)計(jì)梯形法求積分的函數(shù)模板。設(shè)計(jì)梯形法求積分的函數(shù)模板。以模板參數(shù)以模板參數(shù)T來引入被積函數(shù)類，由該參數(shù)調(diào)用來引入被積函數(shù)類，由該參數(shù)調(diào)

30、用欲求定積分的函數(shù)欲求定積分的函數(shù)【例【例6.11】設(shè)計(jì)梯形法求積分的類模板。設(shè)計(jì)梯形法求積分的類模板。求積分的函數(shù)為獨(dú)立的非成員函數(shù)。該方法更簡潔。求積分的函數(shù)為獨(dú)立的非成員函數(shù)。該方法更簡潔。 梯形法求積分是一種求函數(shù)定積分的近似方法。對函數(shù)梯形法求積分是一種求函數(shù)定積分的近似方法。對函數(shù) f(x) 將積分將積分區(qū)間區(qū)間 a,b 分成分成 n 份，每一份看作一個近似梯形，函數(shù)在該區(qū)間的份，每一份看作一個近似梯形，函數(shù)在該區(qū)間的定積分就是所有近似梯形的面積和。積分步長為：定積分就是所有近似梯形的面積和。積分步長為： 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)