模板：總結(jié) 計(jì)劃 匯報(bào) 設(shè)計(jì) 純word可編輯

1、第十一章 模版本章概要： 模板概念是對(duì)類屬概念的繼承與開(kāi)展。利用模板機(jī)制可以顯著減少冗余信息，能大幅度地節(jié)約程序代碼，進(jìn)一步提高面向?qū)ο蟪绦虻目芍赜眯院涂删S護(hù)性。本章主要講述，類屬概念與模板概念，函數(shù)模板與模板函數(shù)，類模板與模板類，模板機(jī)制應(yīng)用實(shí)例等內(nèi)容。 本章快速索引11.1 從類屬到模板11.2 函數(shù)模板與模板函數(shù)11.3 類模板與模板類11.4 模板應(yīng)用實(shí)例11.5 小結(jié)11.1 從類屬到模板 ALGOL68語(yǔ)言最先引入類屬(genericity)的概念，最主要的類屬形式是類型參數(shù)化，即用一個(gè)或多個(gè)類型去參數(shù)化一個(gè)軟件元素的能力。 根本思想：在實(shí)際工作中人們經(jīng)常用到這樣一些程序模塊，從它

2、們的邏輯功能(或?qū)崿F(xiàn)算法)看，彼此是相同的，所不同的主要是處理對(duì)象(數(shù)據(jù))的類型。如果提供具有相同邏輯功能的程序正文(保存共性)，然后把數(shù)據(jù)類型作為參數(shù)傳遞(指出不同特性)，那么可節(jié)約大量程序代碼，這就是類屬機(jī)制的思想，又稱為參數(shù)化模板。 11.1 從類屬到模板 類屬又可分為無(wú)約束類屬機(jī)制和約束類屬機(jī)制，所謂無(wú)約束類屬機(jī)制是指對(duì)作為類屬參數(shù)的數(shù)據(jù)類型沒(méi)有任何特殊要求，而約束類屬機(jī)制那么意味著對(duì)類屬參數(shù)有明確要求，只有在類屬實(shí)參滿足一定條件時(shí)才有意義。 無(wú)約束類屬的例子void swap(T &x,T &y)T temp;temp = x;x = y;/只要是同類型就可以賦值y = temp;

3、11.1 從類屬到模板 約束類屬的例子T minimum(T x，T y)if(x=y) return x;/結(jié)構(gòu)變量的比較運(yùn)算與整型變量的比較 /運(yùn)算就有很大差異 else return x; 并不是任何數(shù)據(jù)類型都可以作為這個(gè)函數(shù)的類屬實(shí)參，只有滿足一定條件(即定義了“=操作)的數(shù)據(jù)類型，才能作為這個(gè)函數(shù)的類屬實(shí)參。 C+語(yǔ)言使用模板來(lái)實(shí)現(xiàn)類屬機(jī)制。圖11.1用直觀形象的形式說(shuō)明了模板、類、對(duì)象、函數(shù)之間的關(guān)系。 11.1 從類屬到模板 圖11.1 模板、類、對(duì)象和函數(shù)的關(guān)系11.2 函數(shù)模板與模板函數(shù) 11.2.1 概念 有多少種需要求最大值的數(shù)據(jù)類型，就需要定義多少個(gè)重載版本。這些版本的

4、代碼都相同，只是參數(shù)類型和函數(shù)返回值類型不同。解決這個(gè)問(wèn)題的最正確方法是使用模板。如果使用模板，那么數(shù)據(jù)類型本身就是一個(gè)參數(shù)，max函數(shù)的模板定義如下： template / 模板聲明T max(T x,T y) / 模板定義體return(xy)?x:y; 用關(guān)鍵字template說(shuō)明，現(xiàn)在正在聲明一個(gè)模板，數(shù)據(jù)類型參數(shù)T由模板參數(shù)給出，它既可以取系統(tǒng)的預(yù)定義類型，也可以取用戶自定義的類類型。 11.2.1 概念 函數(shù)模板不是一個(gè)完全的函數(shù)，它代表了一類函數(shù)，必須把它的模板參數(shù)T實(shí)例化之后，才能完成具體函數(shù)的功能。 把T實(shí)例化的參數(shù)稱為模板實(shí)參，同模板實(shí)參實(shí)例化的函數(shù)稱為模板函數(shù)。例如，用以

5、下函數(shù)main來(lái)調(diào)用前面定義的函數(shù)模板如下： main()int i=18，j=-57；Myclass a b;int x = max(i,j); / 模板實(shí)參為整型模板函數(shù)模板的函數(shù)Myclass m = max(a,b);/ 模板實(shí)參為Myclass類的對(duì)象11.2.1 概念 這里生成了兩個(gè)模板函數(shù)：max(i,j)用模板實(shí)參int把類型參數(shù)T實(shí)例化，max(a,b)用類類型Myclass把T實(shí)例化。 總之，一個(gè)函數(shù)模板是對(duì)一類函數(shù)的抽象，它以任意類型T為參數(shù)(稱為模板參數(shù))。由一個(gè)函數(shù)模板經(jīng)把T實(shí)例化而產(chǎn)生的函數(shù)稱為模板函數(shù)，它是函數(shù)模板的具體實(shí)例。函數(shù)模板與模板函數(shù)之間的關(guān)系，類似類與

6、對(duì)象之間的關(guān)系。 11.2.2 重載 函數(shù)模板有一個(gè)特點(diǎn)，雖然模板參數(shù)T可以實(shí)例化成各種類型，但是采用模板參數(shù)T的每個(gè)參數(shù)必須實(shí)例化成完全相同的類型。模板類型不具有隱式的類型轉(zhuǎn)換。 解決問(wèn)題的方法是，允許函數(shù)模板參與重載，即允許用普通函數(shù)重載一個(gè)同名的函數(shù)模板。有以下兩種重載方式。 11.2.2 重載 與函數(shù)模板共享函數(shù)體 通過(guò)借用函數(shù)模板的函數(shù)體來(lái)定義重載函數(shù)模板的非模板函數(shù)。 重新定義函數(shù)體 在定義重載函數(shù)模板的非模板函數(shù)時(shí)，給出這個(gè)重載函數(shù)的函數(shù)體。 11.3 類模板與模板類 使用類模板(也稱為類屬類或類生成類)機(jī)制，用戶可以為類定義一種模式，使得類中的某些數(shù)據(jù)成員、某些成員函數(shù)的參數(shù)和

7、某些成員函數(shù)的返回值，可以是任意類型的。 類模板不再代表一個(gè)具體的、實(shí)際的類，而是代表一類類。11.3.1 定義類模板 定義類模板，包含兩方面內(nèi)容： 1. 定義類定義類模板中的類的格式如下：template / 模板聲明class Name / 類的定義； 向量類模板定義如下：#include stdafx.h#include iostream.htemplateclass VectorT *data;int size;public:Vector(int i) data=new Ti; Vector() delete data; T &operator(int i) return datai;

8、 ; 可見(jiàn)類中函數(shù)模板是指函數(shù)中的參數(shù)類型數(shù)據(jù)成員data的類型T是可變的11.3.1 定義類模板 11.3.1 定義類模板 在類定義體外定義成員函數(shù) 在類定義體外定義成員函數(shù)時(shí)，如果該成員函數(shù)中有模板參數(shù)，那么需先進(jìn)行模板聲明，而且用類模板名，而不是用類名來(lái)限定函數(shù)名，即在函數(shù)名前的類名后綴上“。例如：templateVector:Vector(int n)data = new T(n);size = n;11.3.2 使用類模板 使用類模板時(shí)首先把它實(shí)例化成一個(gè)具體的類(即模板類)，把類模板實(shí)例化為模板類的格式如下： 類名然后再說(shuō)明模板類的對(duì)象并使用這些對(duì)象完成所需要的功能。 如，向量類模

9、板的主函數(shù)：#include stdafx.h#include iostream.h void main()Vector x(7);for(int i=0;i7;i+)xi=10*i;for(int j=0;j7;j+)coutxj“ ;cout“n;此程序的輸出為：0 10 20 30 40 50 60類模板的派生 既可以從類模板派生出類模板，也可以派生出普通類(非模板類)。 從類模板派生出類模板從類模板派生出新的類模板的格式如下例所示：templateclass Base / 省略具體內(nèi)容;templateclass Derived : public Base; 11.3.3 類模板的派生

10、 從類模板派生出普通類從類模板派生出非模板類的格式如下例所示：templateclass Base ;class Derived : public Base; 首先，作為新派生出來(lái)的非模板類的父類，必須是類模板實(shí)例化后生成的模板類，例如，Base;其次，在派生類定義之前不需要模板聲明語(yǔ)句template。 11.4 模板應(yīng)用實(shí)例 11.4.1 用類模板實(shí)現(xiàn)類屬鏈表 鏈表是程序設(shè)計(jì)中經(jīng)常使用的數(shù)據(jù)結(jié)構(gòu)，可以把它抽象成鏈表類。 首先定義一個(gè)結(jié)構(gòu)模板，以表示類屬鏈表的節(jié)點(diǎn)，結(jié)構(gòu)模板實(shí)質(zhì)上就是類模板，只是不包含成員函數(shù)；然后定義鏈表類模板。結(jié)構(gòu)模板和類模板使用同樣的模板參數(shù)T。 11.4.1 用類模板

11、實(shí)現(xiàn)類屬鏈表 這個(gè)類屬鏈表的根本功能是，在表頭插入一個(gè)節(jié)點(diǎn)，刪除一個(gè)指定內(nèi)容的節(jié)點(diǎn)，判斷給定的數(shù)據(jù)內(nèi)容是否在鏈表內(nèi)，以及打印鏈表內(nèi)容等?？紤]到將來(lái)從鏈表類模板派生出的類模板或非模板類的插入功能可能和鏈表插入功能有差異，我們把實(shí)現(xiàn)插入功能的成員函數(shù)聲明為虛函數(shù)。該類的類圖如圖11.2所示： 下面給出鏈表類模板的定義及使用這個(gè)類模板的一個(gè)主函數(shù)：.#include stdafx.h#include iostream.htemplate / 模板聲明struct Node / 定義結(jié)構(gòu)模板T val;Node *next;template/ 模板聲明class ListNode *head; / 定

12、義類模板int size;public:List()head = 0;size = 0;virtual bool insert(T val);bool deletes(T val);bool contains(T val);void print();List(); 11.4.1 用類模板實(shí)現(xiàn)類屬鏈表template/ 模板聲明List : List()/ 定義函數(shù)模板Node *temp;for(Node *p = head;p;)temp = p;p = p - next;delete temp;template/ 模板聲明bool List : insert(T x)/ 定義函數(shù)模板Nod

13、e *nodes = new Node;if(nodes)nodes - val = x;nodes - next = head;head = nodes;size +;return true;return false; 11.4.1 用類模板實(shí)現(xiàn)類屬鏈表template/ 模板聲明bool List : deletes(T x)/ 定義函數(shù)模板Node *temp;if(head - val = x)temp = head - next;delete head;size - ;head = temp;return true;for(Node *p = temp = head;p;temp =

14、 p, p = p - next)if(p - val = x)temp - next = p - next;delete p;size -;return true;return false;template/ 模板聲明bool List : contains(T x)/ 定義函數(shù)模板for(Node *p = head;p;p = p - next)if(p - val = x)return true;return false;11.4.1 用類模板實(shí)現(xiàn)類屬鏈表template/ 模板聲明void List : print()/ 定義函數(shù)模板for(Node *p = head;p;p =

15、p - next)cout val ;cout n;void main()/ 主函數(shù)List intlist;/ 說(shuō)明整型鏈表對(duì)象intlist.insert(-11);intlist.insert(35);intlist.insert(48);intlist.insert(57);intlist.insert(79);intlist.deletes(48);intlist.print();List floatlist;/ 說(shuō)明浮點(diǎn)型鏈表對(duì)象floatlist.insert(3.1416);floatlist.insert(29.78);floatlist.print();List charl

16、ist;/ 說(shuō)明字符串型鏈表對(duì)象charlist.insert(programming);charlist.insert(object_oriented);charlist.insert(C +);charlist.print();11.4.1 用類模板實(shí)現(xiàn)類屬鏈表程序輸出如下：79 57 35 -1129.78 3.1416C +object_oriented programming需求鏈表的根本功能在表頭插入節(jié)點(diǎn)內(nèi)容是：T 類型的數(shù)據(jù)和一個(gè)指向節(jié)點(diǎn)類型的指針，其中 T是模板參數(shù)打印鏈表輸出鏈表的節(jié)點(diǎn)數(shù)判斷給定的數(shù)據(jù)內(nèi)容是否在鏈表內(nèi)刪除一個(gè)指定內(nèi)容的節(jié)點(diǎn)刪除整個(gè)鏈表釋放內(nèi)存分析與設(shè)計(jì)根據(jù)需求

17、我們可以把節(jié)點(diǎn)說(shuō)明為結(jié)構(gòu)類型：template /說(shuō)明T是模板參數(shù)struct NodeT a;Node* next;head: 鏈表的頭，找到了頭就找到了整個(gè)鏈表根據(jù)需求我們給出鏈表類模版的定義：template class ListNode * head; int size;public:List() head = 0; size = 0; bool insert(T x)；void print()；int Get_size() return size; bool contains( T x)；bool deletes(T x)；List();分析與設(shè)計(jì)功能1：在表頭插入一個(gè)節(jié)點(diǎn)算法分析：

18、 鏈表中一個(gè)節(jié)點(diǎn)都沒(méi)有時(shí)，head=0,表示鏈表是空的。我們首先要在內(nèi)存中產(chǎn)生一個(gè)節(jié)點(diǎn)用 new 來(lái)產(chǎn)生一個(gè)Node 類型的內(nèi)存空間，并獲得這個(gè)空間的地址 current。即 Node* current = new Node ;此節(jié)點(diǎn)作為鏈表的第一個(gè)節(jié)點(diǎn)，也是鏈表的頭節(jié)點(diǎn)，也是鏈表的尾節(jié)點(diǎn)最后一個(gè)，此時(shí)，我們可以認(rèn)為這個(gè)鏈表只有一個(gè)節(jié)點(diǎn)。 通常我們把最后的一個(gè)節(jié)點(diǎn)的next設(shè)為0，即 next = 0 或 next = head;head的初始值為0；另外，這時(shí)頭指針head 的值不再是初始值0，而應(yīng)該是當(dāng)前節(jié)點(diǎn)的首地址， 即 head = current ; 當(dāng)有下一個(gè)節(jié)點(diǎn)產(chǎn)生時(shí)，必然要產(chǎn)生

19、一個(gè)新的current，先給這個(gè)新的節(jié)點(diǎn)賦值， current-a = x; 新節(jié)點(diǎn)中的next值，必須指向原來(lái)鏈表的頭，即：current-next = head; 否那么，就不能和原來(lái)的鏈表鏈接。這樣一來(lái)，鏈表的頭，就應(yīng)該是剛生成的這個(gè)節(jié)點(diǎn)，頭指針head，應(yīng)該重新設(shè)為這個(gè)新節(jié)點(diǎn)的首地址，即 head = current ; 總之，head 永遠(yuǎn)指向鏈表的頭，打印鏈表、遍歷鏈表、刪除鏈表等操作都是從鏈表達(dá)的頭開(kāi)始的。 bool insert(T x)Node *current = new Node;if(current) /判斷內(nèi)存節(jié)點(diǎn)是否創(chuàng)立成功current-a = x; /節(jié)點(diǎn)中存放

20、的數(shù)據(jù)current-next = head; /節(jié)點(diǎn)中用來(lái)指向下一個(gè)節(jié)點(diǎn)的指針head = current; /注意給head 賦值的順序size+;return true;elsereturn false;功能2：打印鏈表 打印鏈表是從鏈表的頭開(kāi)始的，即從head開(kāi)始用來(lái)鏈接鏈表的指針next的值，每個(gè)都是有效值，唯有最后一個(gè)節(jié)點(diǎn)的next 值是0 打印鏈表的實(shí)現(xiàn)代碼void print()for(Node* node = head; node ; node = node-next )couta endl;注意：Node* node = head;/循環(huán)變量賦初值。執(zhí)行一次，指向鏈表頭 n

21、ode;/循環(huán)結(jié)束的條件。判斷是否為0，即最后一個(gè)節(jié)點(diǎn)node = node-next /改變循環(huán)變量的值。將 node中的next賦給node 將此循環(huán)形式，作為遍歷鏈表的一般循環(huán)形式 ，今后遇到遍歷鏈表的操作都可以套用此形式的循環(huán)。功能3：輸出鏈表的節(jié)點(diǎn)數(shù) 通常函數(shù)原形采用int Get_size() 形式應(yīng)為在對(duì)節(jié)點(diǎn)的操作中，隨時(shí)統(tǒng)計(jì)了節(jié)點(diǎn)數(shù)，所以，直接 return size即可以了，否那么，還要遍歷整個(gè)鏈表統(tǒng)計(jì)其節(jié)點(diǎn)個(gè)數(shù)： int Get_size()return size; 功能4：判斷給定的數(shù)據(jù)內(nèi)容是否在鏈表內(nèi) 首先應(yīng)該考慮，此項(xiàng)操作必須遍歷整個(gè)鏈表才能知道，鏈表中是否包含要查找

22、的數(shù)據(jù)內(nèi)容一般循環(huán)形式如前所述：for(Node * node = head ; node ;node = node-next ) 判斷給定的數(shù)據(jù)內(nèi)容是否在鏈表內(nèi)代碼bool contains( T x)for(Node * node = head ; node; node = node-next )if(node-a = x) return true;else false;功能5：刪除一個(gè)指定內(nèi)容的節(jié)點(diǎn) 要?jiǎng)h除一個(gè)指定內(nèi)容的節(jié)點(diǎn)，有兩種情況：一種是第一個(gè)節(jié)點(diǎn)以外的節(jié)點(diǎn)；另一種情況是第一個(gè)節(jié)點(diǎn)采用的循環(huán)形式還是：Node* temp;for(Node * node = temp=head ;n

23、ode;temp=node,node = node-next )具體實(shí)現(xiàn)如下：bool deletes(T x)Node* temp;for(Node * node = temp=head ;node;temp=node,node = node-next ) if(node-a = x) if(node=head)/頭節(jié)點(diǎn)單獨(dú)處理head = node-next ;delete node;size-;return true; else /其他節(jié)點(diǎn)，統(tǒng)一處理temp-next = node-next ; /假設(shè)是頭節(jié)點(diǎn)那么 temp=node,所以 /有節(jié)點(diǎn)單獨(dú)處理delete node;siz

24、e-; return true; return false;功能5：刪除一個(gè)指定內(nèi)容的節(jié)點(diǎn) 功能6：釋放鏈表 首先要獲得鏈表的頭指針，從頭節(jié)點(diǎn)開(kāi)始刪除，在刪除頭節(jié)點(diǎn)以前，先要保存頭節(jié)點(diǎn)中next的值，因?yàn)樗鼘⑹莿h除后的頭節(jié)點(diǎn)的指針，只有保存好以后，才能刪除，這個(gè)頭節(jié)點(diǎn)，依次進(jìn)行直到最后一個(gè)節(jié)點(diǎn)。釋放鏈表的代碼List()for(Node* current = head; current; ) /注意這種形式/current = current-next )head = current-next ;/指向下一個(gè)節(jié)點(diǎn)cout“*x = currentendl;/觀察刪除了幾個(gè)delete curr

25、ent;/刪除當(dāng)前節(jié)點(diǎn)，非0那么刪除current = head; /指向下一個(gè)節(jié)點(diǎn)，準(zhǔn)備刪除注意： 假設(shè)current = 0，那么delete current； delete current都可以。因?yàn)?，它不指向一個(gè)有效內(nèi)存空間但int x = 5；current = &x;那么delete current；delete current;不可以，屬連續(xù)釋放一個(gè)內(nèi)存空間。11.4.2 派生出集合類模板和集合類 集合與鏈表的唯一差異是，集合中沒(méi)有相同的元素，因此，在進(jìn)行插入操作時(shí)要先判斷集合中是否已存在要插入的元素，僅當(dāng)集合中原來(lái)沒(méi)有這個(gè)元素時(shí)才真正做插入操作。 11.4.2 派生出集合類模板和集合類派生出集合類模板template/模板聲明class Set : public List/ 定義集合類模板public:boolean insert(T val); ; te