C第7章模板與線性表課件

第7章模板與線性表

內容提要7.1模板概念的提出為了適應復雜的現(xiàn)實情況，C++當中引入了各種基本類型，并提供了類的設計；不同的類型當中存在著通用性的需求，如比較、復制、查找等；通過模板實現(xiàn)參數(shù)化的程序設計，將類型作為參數(shù)傳遞，配合運算符重載，實現(xiàn)通用設計；模板分為函數(shù)模板和類模板，引入模板的最終目的是提高編程效率。例1：求兩數(shù)中的大數(shù)比較兩個整型數(shù)

intmax(inta,intb) { returna>b?a:b; }比較兩個浮點數(shù)

floatmax(floata,floatb) { returna>b?a:b; }更多……解決方案參數(shù)的自動類型轉換可以部分解決問題，但遠遠不夠！對各種數(shù)據(jù)類型，執(zhí)行完全相同的操作，完全可以把類型作為特殊的參數(shù)來傳遞。函數(shù)模板定義這樣的參數(shù)化的函數(shù)，根據(jù)調用的情況編譯器實例化類型參數(shù)，從而生成不同的代碼函數(shù)。例1：函數(shù)模板maxtemplate<typenameT>Tmax(Ta,Tb){returna>b?a:b;}模板實參推演模板實參推演編譯器需檢查函數(shù)調用中提供的函數(shù)實參的類型。該過程稱為模板實參推演。編譯器根據(jù)實參類型，可以隱式（自動）進行模板實參推演，也可以由程序員顯式指定。如果隱式推演會帶來二義性的沖突的話，必須顯式指定！模板實參推演template<typenameT>Max(Ta,Tb,T&c){c=a+b;}下列選項正確的是（） A)floatx,y;charz;Max(x,y,z); B)intx,y,z;Max(x,y,z); C)intx,y;floatz;Max(x,y,z); D)floatx;inty,z;Max(x,y,z);其他選項會有錯誤：templateparameter'T'isambiguous函數(shù)模板的重載函數(shù)模板可以和同名模板以及普通函數(shù)重載如果存在同名普通函數(shù)，則普通函數(shù)的重載優(yōu)先級最高 template<classT>TFunc(Tt) { returnt; } intFunc(inti) { return2*i; } intmain() { cout<<Func(3);}//結果6函數(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ù)模板：通用矩陣轉置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];}intmiddle[6][3],intmatrix1[3][6]={8,10,12,23,1,3,5,7,9,2,4,6,34,45,56,2,4,6}; inverse(matrix1,middle,6,3);函數(shù)模板：通用矩陣轉置上例中的實參是隱式推演的，如果是顯式推演的話，怎么寫？ inverse<int[6],int[3]>(matrix1,middle,6,3);如果函數(shù)的聲明改為voidinverse(T1mat1,T2mat2,inta,intb)，代碼需要修改嗎？

答案：不需要！但模板推演出的類型不同了。 inverse<int(*)[6],int(*)[3]> (matrix1,middle,6,3);函數(shù)模板的聲明請注意：與函數(shù)聲明不同，函數(shù)模板的聲明必須含變量名。因為兩者編譯過程不一樣，函數(shù)模板必須先轉換為模板函數(shù)。

如：template<typenameT1,typenameT2>voidinverse(T1*mat1,T2*mat2,inta,intb);最后：區(qū)分函數(shù)模板和模板函數(shù)概念的區(qū)別7.2類模板概念的提出使用類模板使用戶可以為類聲明一種模式，使得類中的某些數(shù)據(jù)成員、某些成員函數(shù)的參數(shù)、某些成員函數(shù)的返回值，能取任意類型（包括基本類型的和用戶自定義類型）常用于建立通用的容器類，如線性表（數(shù)組、鏈表、棧和隊列）、二叉樹和圖等，對于所有的包容器來說，其維護方式是相同的。以類模板和運算符重載相結合的數(shù)據(jù)結構以及算法描述，是本書下半部分的核心。類模板的設計示例template<typenameT> classComplex { Treal，imag; public: Complex(Tx=0,Ty=0); ComplexAdd(constComplexx);…… };類模板的參數(shù)說明模板參數(shù)有兩種：模板類型參數(shù)和模板非類型參數(shù)。模板非類型參數(shù)由一個普通的參數(shù)聲明構成。表示該參數(shù)名代表了一個潛在的常量，企圖修改這種參數(shù)的值是一個錯誤。 template<typenameT,inti>classarray{ Tvector[i]; intsize; ……}類模板的聲明與實現(xiàn)如果在類模板外定義成員函數(shù)，則該成員函數(shù)必須是一個函數(shù)模板。在成員函數(shù)模板定義中，必須在指定類域的類型名后添加<模板參數(shù)名表>中成員。<模板參數(shù)名表>的成員與模板的<模板參數(shù)表>中的類型參數(shù)名相同，但不加typename或class。類模板函數(shù)的實現(xiàn)示例template<classT>//類模板函數(shù)的定義Complex<T>Complex<T>::Add(constComplex<T>x) { returnComplex<T>(real+x.real, imag+x.imag); }總結：類模板的定義語法類模板定義： template<模板參數(shù)表>

class類名{……

//類定義體 };

//再次指出分號不可少template<模板參數(shù)表>返回類型類名<模板參數(shù)名表>::成員函數(shù)名n(形參表) {……；//成員函數(shù)定義體}類模板的實例化過程模板函數(shù)模板類模板模板函數(shù)模板類對象對象對象參數(shù)實例化參數(shù)實例化類模板的實例化示例模板形參實例化：在外部程序中，用顯式方法給類模板傳遞實例化參數(shù)，生成模板類類實例化：使用模板類定義最終對象//使用復數(shù)類模板生成int復數(shù)類并創(chuàng)建對象： Complex<int>a(2,4),b(1,5),c=a+b; //使用復數(shù)類模板生成float復數(shù)類并創(chuàng)建對象： Complex<float>a(2.1,4.3),b(1.2,5.3),c=a+b;7.3線性表：最實用的通用類型線性表是最典型的數(shù)據(jù)結構之一。在其當中，每一個元素之間都有著前后的線性聯(lián)系，顧稱為線性表。之前學過的數(shù)組其實就是一種最簡單的線性表，也可以把數(shù)組看成是一種線性連續(xù)數(shù)據(jù)結構。鏈表也是線性表的一種，但它是線性非連續(xù)數(shù)據(jù)結構。棧和隊列也是線性表的特例，他們的主要特點是數(shù)據(jù)存取的時候有特別限制。維護通用的線性表類模板前面我們對數(shù)組的使用過于死板沒有區(qū)分數(shù)組長度和有效元素個數(shù)元素進行刪除與添加后的后續(xù)操作對數(shù)組長度進行有效性維護的問題對于每種類型的數(shù)組操作基本雷同維護一個通用的線性表類模板，解決上述問題，并增加常用的操作功能。線性表類模板的數(shù)據(jù)成員template<typenameT,intsize>classseqlist{ Tslist[size];//存放順序表的數(shù)組 intMaxsize;//最大可容納項數(shù) intlast;//已存表項的最后位置 …..};

利用非類型參數(shù)size可以相對靈活的控制數(shù)組長度。刪除線性表元素的操作解釋1431341096587241621892771185112110131234i下標1431341096587241621897118511211013下標圖6.1從表中刪除一個數(shù)據(jù)當需要在順序表中刪除一個元素時，必須把它后面的元素的數(shù)據(jù)全部順序前移一個位置，否則表中前驅后繼關系被破壞。刪去第i個元素的數(shù)據(jù)，就是把第i+1個元素拷入第i個元素，依此類推，直到最后一個元素。插入線性表元素的操作解釋1431341096587241621892771185112110135432i下標1273134109658724162189711511181214x013下標圖6.2向表中插入一個數(shù)據(jù)當需要在順序表的指定位置i插入一個數(shù)據(jù)x時，必須為它騰出這個位置，把從該位置開始向后的所有元素數(shù)據(jù)，后移一個位置，最后才插入。后移時從最后一個元素開始，見圖。線性表類模板template<typenameT,intsize>classseqlist{ Tslist[size];//存放順序表的數(shù)組

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

intlast;//已存表項的最后位置 public: seqlist(){last=-1;Maxsize=size;}//初始化為空表。注意為什么是-1？ intLength()const{returnlast+1;}//計算表長度線性表類模板boolIsEmpty(){returnlast==-1;}//判斷表是否空

boolIsFull(){returnlast==Maxsize-1;}//判斷表是否滿 TGet(inti){returni<0||i>last?NULL:slist[i];}//取第i個元素之值intFind(T&x)const;//尋找x在表中位置（下標） boolIsIn(T&x);//判斷x是否在表中 intNext(T&x);//尋找x的后繼位置

intPrior(T&x);//尋找x的前驅位置線性表類模板

boolInsert(T&x,inti);//

x插入到列表中第i個位置處（下標）

boolRemove(T&x);//刪除x T&operator[](inti);}; //重載下標運算符[]在閱讀相關函數(shù)的詳細定義之前，先自己揣摩函數(shù)的聲明，以及參數(shù)和返回值的定義。線性表類模板：Find函數(shù)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;//未找到，返回-1 elsereturni;//找到，返回下標 }線性表類模板：Isin函數(shù)template<typenameT,intsize>boolseqlist<T,size>::IsIn(T&x){

inti=0; boolfound=0;

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

if(slist[i]!=x)i++;

elsefound=1;//找到

returnfound;}線性表類模板：前驅后繼函數(shù)template<typenameT,intsize>intseqlist<T,size>::Next(T&x){ inti=Find(x); if(i>=0&&i<last)returni+1;//x后繼位置 elsereturn-1;//x不在表中，或在表末尾 }template<typenameT,intsize>intseqlist<T,size>::Prior(T&x){ inti=Find(x); if(i>0&&i<=last)returni-1;//x前驅的位置 elsereturn-1;}線性表類模板：重載[]函數(shù)template<typenameT,intsize>T&seqlist<T,size>::operator[](inti){

if(i>last+1||i<0||i>=Maxsize){ cout<<"下標出界！"<<endl; exit(1);}//如何處理更好？ if(i>last)last++;//下標運算符[]，只能增加表的元素，不能減少

returnslist[i];}//這里的[]比想象中多了一點線性表類模板：Insert函數(shù)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;}}//思考返回值的意義線性表類模板：Remove函數(shù)template<typenameT,intsize>

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

inti=Find(x),j;//先去找x在哪個位置

if(i>=0){ last--;

for(j=i;j<=last;j++)slist[j]=slist[j+1]; //依次前移，保證表連續(xù)

returntrue;}

returnfalse;//表中不存在x}線性表類模板定義總結上述成員函數(shù)當中，涉及的操作難點主要在于對數(shù)組長度和已有元素個數(shù)的判斷與控制、增加和刪除時保證數(shù)組連續(xù)的判斷控制。在這里，數(shù)組的操作必須精確，務必細心體會，特別注意看懂相關循環(huán)的起始和終止條件，來不得半點誤差。這個模板類還有不足嗎？線性表類可以改進的地方成員函數(shù)的功能覆蓋不夠全面。作為一個類，應該盡可能提供完善的接口。構造函數(shù)，增加從已有數(shù)組進行賦值的功能；增加元素，可以增加默認加到尾部的函數(shù)；刪除元素，可以增加指定刪除位置的函數(shù)。數(shù)組倒置功能，求和功能，求最大和最小值……線性表類可以改進的地方如果將普通線性表Seqlist改造為有序線性表Orderedlist，該如何修改現(xiàn)有代碼？

提示：在增加元素時，必須進行限制。如何對有序線性表進行控制，使得可以方便地實現(xiàn)遞增或遞減的要求？

提示：增加成員變量，用來保存遞增或遞減的設置。線性表可以改進的地方線性表已經(jīng)可以較方便地管理內存，但如果現(xiàn)有空間已經(jīng)占滿，就無法增加新的元素。這樣的情況并不總是合理，該如何解決？提示：臨時的手段是建立一個存儲空間更大的對象，將現(xiàn)有對象的內容轉移過去。真正的解決辦法將在后續(xù)章節(jié)當中揭開。線性表類模板和數(shù)組通過線性表類模板，實例化得到模板類，并可以建立對象來使用數(shù)組，那么和使用普通數(shù)組的區(qū)別到底在哪里？1、使用模板類得到的對象，屏蔽了底層的操作細節(jié)，提高了代碼的編寫效率，從而有利于編寫大規(guī)模的程序，也比較合適于團隊合作。2、使用普通數(shù)組，在運行效率上更高，且可以實現(xiàn)允許范圍內的所有操作；而如果模板類中沒有直接提供的功能，想要實現(xiàn)相對麻煩。3、二者之間可以建立相互轉換的通道。7.4基于模板的通用算法設計例：排序算法的四個實現(xiàn)形式直接針對特定數(shù)組進行排序編寫普通函數(shù)，針對特定類型的數(shù)組排序編寫函數(shù)模板，針對多種類型進行排序對線性表類模板增加排序功能例：直接對數(shù)組進行冒泡排序

inta[5]={2,3,1,5,4},i,j,t;

for(i=0;i<4;i++)

for(j=4;j>i;j--)//回憶冒泡排序的過程 {

if(a[j]<a[j-1])//升序 { t=a[j];a[j]=a[j-1];a[j-1]=t; } }

for(i=0;i<5;i++) cout<<a[i]<<'\t';評：直接對數(shù)組進行冒泡排序算法的通用性差，移植性差改進方案：將排序算法提煉為函數(shù)例：特定類型冒泡排序函數(shù)

voidbubblesort(inta[],intn) {

inti,j,t;

for(i=0;i<n-1;i++)

for(j=n-1;j>i;j--) {

if(a[j]<a[j-1]) { t=a[j]; a[j]=a[j-1]; a[j-1]=t; } } }例：特定類型冒泡排序函數(shù) //main函數(shù)

inta[5]={2,3,1,5,4},i; bubblesort(a,5);

for(i=0;i<5;i++) cout<<a[i]<<'\t'; cout<<endl;評：特定類型冒泡排序函數(shù)回憶數(shù)組作為函數(shù)參數(shù)的本質：形參其實是指針，形參數(shù)組完全依附于實參數(shù)組。實參必須是數(shù)組名，因此需要額外傳遞參數(shù)控制數(shù)組長度。能實現(xiàn)一定的通用性，但仍然需要針對不同類型如char、float或者不同的類來編寫不同的函數(shù)。將算法改造為函數(shù)模板就可以解決上述問題。例：冒泡排序函數(shù)模板

template<typenameT>voidbubblesort(Ta[],intn){

inti,j; Tt;

for(i=0;i<n-1;i++)

for(j=n-1;j>i;j--) { if(a[j]<a[j-1]) { t=a[j]; a[j]=a[j-1]; a[j-1]=t; } } }評：冒泡排序函數(shù)模板冒泡排序函數(shù)模板提供了強大的通用算法功能要配合函數(shù)模板使用，相關類型必須可以支持<和=等運算符的使用。有的情況下，數(shù)組可以支持上述運算符的使用，但可能意義和我們想要的并不同。

如：對用字符指針數(shù)組存放的多個字符串排序

解決：使用專門的字符串類對象例：線性表類的冒泡排序函數(shù)

template<typenameT,intsize>voidSeqlist<T,size>::BubbleSort(){

inti,j;Tt;

for(i=0;i<last;i++)

for(j=last;j>i;j--){

if(slist[j]<slist[j-1]){ temp=slist[j]; slist[j]=slist[j-1]; slist[j-1]=temp;}} }評：線性表類的冒泡排序函數(shù)將冒泡函數(shù)封裝為類的成員函數(shù)之后，僅能對對象中的數(shù)組進行排序。對這類通用算法，使用函數(shù)模板和類模板各有其優(yōu)勢，可根據(jù)實際情況靈活選擇。使用類模板，是標準的面向對象的用法。需要將相關數(shù)據(jù)封裝到類中，再調用算法函數(shù)。使用獨立的函數(shù)模板，也是比較常用的方式，運行效率相對更高。abxyf（x）xixi+1h梯型面積=（上底+下底）x高2例：定積分問題的算法問題的本質：如何傳遞一個函數(shù)來作為參數(shù)解決方案如果要把函數(shù)作為參數(shù)，可以通過傳遞擁有該函數(shù)的對象實現(xiàn)。類模板：定義積分類，數(shù)據(jù)成員包括上限、下限和等分數(shù)，函數(shù)則通過對象成員Tcf傳遞。函數(shù)模板：把上限、下限、等分數(shù)以及Tcf都