清華大學(xué)C++-第六講 函數(shù)模板與類模板ppt課件

1、第六講第六講 函數(shù)模板與類模板函數(shù)模板與類模板函數(shù)模板與類模板函數(shù)模板函數(shù)模板類模板類模板動態(tài)數(shù)組類模板動態(tài)數(shù)組類模板鏈表類模板鏈表類模板棧類模板棧類模板隊列類模板隊列類模板綜合實例綜合實例模板的實例化機(jī)制模板的實例化機(jī)制模板的特化模板的特化模板元編程簡介模板元編程簡介n函數(shù)模板可以用來創(chuàng)建一個通用功能的函數(shù)，以支持多種不同形參，進(jìn)一步簡化重載函數(shù)的函數(shù)體設(shè)計n定義方法：ntemplate n函數(shù)定義n模板參數(shù)表的內(nèi)容n類型參數(shù)：class或typename 標(biāo)識符n常量參數(shù)：類型闡明符 標(biāo)識符n模板參數(shù)：template class 標(biāo)識符函數(shù)模板函數(shù)模板#include #include

2、using namespace std;using namespace std;templatetemplateT abs(T x) T abs(T x) return x 0? -x : x;return x 0? -x : x; int main() int main() int n = -5;int n = -5;double d = -5.5;double d = -5.5;cout abs(n) endl;cout abs(n) endl;cout abs(d) endl;cout abs(d) endl;return 0;return 0; 運(yùn)轉(zhuǎn)結(jié)果：運(yùn)轉(zhuǎn)結(jié)果：5 55.55.5n

3、編譯器從調(diào)用abs()時實參的類型，推導(dǎo)出函數(shù)模板的類型參數(shù)。例如，對于調(diào)用表達(dá)式abs(n)，由于實參n為int型，所以推導(dǎo)出模板中類型參數(shù)T為intn當(dāng)類型參數(shù)的含義確定后，編譯器將以函數(shù)模板為樣板，生成一個函數(shù)：int abs(int x) return x 0 ? x : x;函數(shù)模板函數(shù)模板#include #include using namespace std;using namespace std;template template /定義函數(shù)模板定義函數(shù)模板void outputArray(const T void outputArray(const T * *array,

4、int count) array, int count) for (int i = 0; i count; i+)for (int i = 0; i count; i+)cout arrayi ;cout arrayi ;cout endl;cout endl; 函數(shù)模板int main() int main() / /主函數(shù)主函數(shù) const int A_COUNT = 8, B_COUNT = 8, C_COUNT = 20;const int A_COUNT = 8, B_COUNT = 8, C_COUNT = 20;int aA_COUNT = 1, 2, 3, 4, 5, 6, 7

5、, 8 ;int aA_COUNT = 1, 2, 3, 4, 5, 6, 7, 8 ;/定義定義intint數(shù)組數(shù)組double bB_COUNT = 1.1, 2.2, 3.3, 4.4, 5.5, double bB_COUNT = 1.1, 2.2, 3.3, 4.4, 5.5, 6.6, 7.7, 8.8 ;/6.6, 7.7, 8.8 ;/定義定義doubledouble數(shù)組數(shù)組char cC_COUNT = Welcome to see you! ;/char cC_COUNT = Welcome to see you! ;/定義定義charchar數(shù)組數(shù)組cout a arra

6、y contains: endl;cout a array contains: endl;outputArray(a, A_COUNT);outputArray(a, A_COUNT);/調(diào)用函數(shù)模板調(diào)用函數(shù)模板cout b array contains: endl;cout b array contains: endl;outputArray(b, B_COUNT);outputArray(b, B_COUNT);/調(diào)用函數(shù)模板調(diào)用函數(shù)模板cout c array contains: endl;cout c array contains: endl;outputArray(c, C_COUN

7、T);outputArray(c, C_COUNT);/調(diào)用函數(shù)模板調(diào)用函數(shù)模板return 0;return 0; 函數(shù)模板運(yùn)轉(zhuǎn)結(jié)果如下：運(yùn)轉(zhuǎn)結(jié)果如下：a array contains:a array contains:1 2 3 4 5 6 7 81 2 3 4 5 6 7 8b array contains:b array contains:1.1 2.2 3.3 4.4 5.5 6.6 7.7 8.8 1.1 2.2 3.3 4.4 5.5 6.6 7.7 8.8 c array contains:c array contains:W e l c o m e t o s e e y o

8、 u !W e l c o m e t o s e e y o u !函數(shù)模板與類模板函數(shù)模板函數(shù)模板類模板類模板動態(tài)數(shù)組類模板動態(tài)數(shù)組類模板鏈表類模板鏈表類模板棧類模板棧類模板隊列類模板隊列類模板綜合實例綜合實例模板的實例化機(jī)制模板的實例化機(jī)制模板的特化模板的特化模板元編程簡介模板元編程簡介n類模板的作用n運(yùn)用類模板運(yùn)用戶可以為類聲明一種方式，使得類中的某些數(shù)據(jù)成員、某些成員函數(shù)的參數(shù)、某些成員函數(shù)的前往值，能取恣意類型包括根本類型和用戶自定義類型類模板n類模板：ntemplate nclass 類名n類成員聲明n假設(shè)需求在類模板以外定義其成員函數(shù)，那么要采用以下的方式：ntemplate

9、n類型名 類名:函數(shù)名參數(shù)表類模板與函數(shù)模板中的與函數(shù)模板中的“模模板參數(shù)表完全一樣板參數(shù)表完全一樣類模板#include #include #include #include using namespace std;using namespace std;/ / 構(gòu)造體構(gòu)造體StudentStudentstruct Student struct Student int id; int id; /學(xué)號學(xué)號 float gpa; float gpa; /平均分平均分; ; 類模板/類模板：實現(xiàn)對恣意類型數(shù)據(jù)進(jìn)展存取類模板：實現(xiàn)對恣意類型數(shù)據(jù)進(jìn)展存取template template class

10、Store class Store private:private:T item;T item; / item/ item用于存放恣意類型的數(shù)據(jù)用于存放恣意類型的數(shù)據(jù)bool haveValue; / haveValuebool haveValue; / haveValue標(biāo)志標(biāo)志itemitem能否已被存能否已被存入內(nèi)容入內(nèi)容public:public:Store();Store();/ / 缺省方式無形參的構(gòu)造函數(shù)缺省方式無形參的構(gòu)造函數(shù)T &getElem();T &getElem();/提取數(shù)據(jù)函數(shù)提取數(shù)據(jù)函數(shù)void putElem(const T &x);

11、/void putElem(const T &x); /存入數(shù)據(jù)函數(shù)存入數(shù)據(jù)函數(shù);/以下實現(xiàn)各成員函數(shù)。以下實現(xiàn)各成員函數(shù)。template template /缺省構(gòu)造函數(shù)的實現(xiàn)缺省構(gòu)造函數(shù)的實現(xiàn) Store:Store(): haveValue(false) Store:Store(): haveValue(false) Store表示類型表示類型參數(shù)實例化之后的參數(shù)實例化之后的Store模板，相當(dāng)于模板，相當(dāng)于類名。類名。類模板template /template /提取數(shù)據(jù)函數(shù)的實現(xiàn)提取數(shù)據(jù)函數(shù)的實現(xiàn)T &Store:getElem() T &Store:get

12、Elem() /如試圖提取未初始化的數(shù)據(jù)，那么終止程序如試圖提取未初始化的數(shù)據(jù)，那么終止程序if (!haveValue) if (!haveValue) cout No item present! endl;cout No item present! endl;exit(1);exit(1);/使程序完全退出，前往到操作系統(tǒng)。使程序完全退出，前往到操作系統(tǒng)。 return item; return item; / / 前往前往itemitem中存放的數(shù)據(jù)中存放的數(shù)據(jù) template template /存入數(shù)據(jù)函數(shù)的實現(xiàn)存入數(shù)據(jù)函數(shù)的實現(xiàn) void Store:putElem(const

13、T &x) void Store:putElem(const T &x) / / 將將haveValue haveValue 置為置為truetrue，表示，表示itemitem中已存入數(shù)值中已存入數(shù)值haveValue = true;haveValue = true;item = x;item = x;/ / 將將x x值存入值存入itemitem 留意，函數(shù)模板中留意，函數(shù)模板中無法對參數(shù)化類型無法對參數(shù)化類型T進(jìn)展進(jìn)展“與詳細(xì)類型與詳細(xì)類型相關(guān)的處置。相關(guān)的處置。類模板int main() int main() Store s1, s2;Store s1, s2;s1.p

14、utElem(3);s1.putElem(3);s2.putElem(-7);s2.putElem(-7);cout s1.getElem() s2.getElem() endl;cout s1.getElem() s2.getElem() endl;Student g = 1000, 23 ;Student g = 1000, 23 ;Store s3;Store s3;s3.putElem(g); s3.putElem(g); cout The student id is s3.getElem().id endl;cout The student id is s3.getElem().id

15、 endl;Store d;Store d;cout Retrieving object D. ;cout Retrieving object D. ;cout d.getElem() endl;cout d.getElem() endl;/由于由于d d未經(jīng)初始化未經(jīng)初始化, ,在執(zhí)行函數(shù)在執(zhí)行函數(shù)D.getElement()D.getElement()過程中導(dǎo)致程序終止過程中導(dǎo)致程序終止return 0;return 0; 等效原那么：等效原那么： “Store相當(dāng)相當(dāng)于一個類名于一個類名等效原那么：等效原那么： “Store相當(dāng)于一個類名相當(dāng)于一個類名等效原那么：等效原那么： “Stor

16、e相當(dāng)于一個類名相當(dāng)于一個類名函數(shù)模板與類模板函數(shù)模板函數(shù)模板類模板類模板動態(tài)數(shù)組類模板動態(tài)數(shù)組類模板鏈表類模板鏈表類模板棧類模板棧類模板隊列類模板隊列類模板綜合實例綜合實例模板的實例化機(jī)制模板的實例化機(jī)制模板的特化模板的特化模板元編程簡介模板元編程簡介動態(tài)數(shù)組類模板#ifndef ARRAY_H#ifndef ARRAY_H#define ARRAY_H#define ARRAY_H#include #include template template /數(shù)組類模板定義數(shù)組類模板定義class Array class Array private:private:T T* * list; li

17、st;/用于存放動態(tài)分配的數(shù)組內(nèi)存首地址用于存放動態(tài)分配的數(shù)組內(nèi)存首地址int size;int size;/數(shù)組大小元素個數(shù)數(shù)組大小元素個數(shù)public:public:Array(int sz = 50);Array(int sz = 50);/構(gòu)造函數(shù)構(gòu)造函數(shù)Array(const Array &a);Array(const Array &a);/拷貝構(gòu)造函數(shù)拷貝構(gòu)造函數(shù)Array();Array();/析構(gòu)函數(shù)析構(gòu)函數(shù)Array & operator = (const Array &rhs); Array & operator = (const A

18、rray &rhs); /重載重載=“=“T & operator (int i); /T & operator (int i); /重載重載const T & operator (int i) const;const T & operator (int i) const;operator T operator T * * (); ();/重載到重載到T T* *類型的轉(zhuǎn)換類型的轉(zhuǎn)換operator const T operator const T * * () const; () const;int getSize() const;int getSiz

19、e() const;/取數(shù)組的大小取數(shù)組的大小void resize(int sz);void resize(int sz);/修正數(shù)組的大小修正數(shù)組的大小;Array表示類型表示類型參數(shù)實例化之后的參數(shù)實例化之后的Array模板，相當(dāng)于模板，相當(dāng)于類名。類名。賦值函數(shù)賦值函數(shù)(即拷即拷貝函數(shù)貝函數(shù))針對常對象定針對常對象定義常函數(shù)義常函數(shù)類型轉(zhuǎn)換重載：在類體中經(jīng)過指定關(guān)鍵字類型轉(zhuǎn)換重載：在類體中經(jīng)過指定關(guān)鍵字operator，并在其后加上轉(zhuǎn)換的目的類型后，就，并在其后加上轉(zhuǎn)換的目的類型后，就可以聲明轉(zhuǎn)換函數(shù)。轉(zhuǎn)換函數(shù)必需是成員函數(shù)，它的聲明不能指定前往類型和參數(shù)表?？梢月暶鬓D(zhuǎn)換函數(shù)。轉(zhuǎn)換函數(shù)

20、必需是成員函數(shù)，它的聲明不能指定前往類型和參數(shù)表。針對常對象定針對常對象定義常函數(shù)義常函數(shù)T作為類型參數(shù)，在作為類型參數(shù)，在模板的定義中可以模板的定義中可以當(dāng)作類名運(yùn)用。當(dāng)作類名運(yùn)用。動態(tài)數(shù)組類模板template Array:Array(int sz) /template Array:Array(int sz) /構(gòu)造函數(shù)構(gòu)造函數(shù) assert(sz = 0);/szassert(sz = 0);/sz為數(shù)組大小元素個數(shù)，該當(dāng)非負(fù)為數(shù)組大小元素個數(shù)，該當(dāng)非負(fù)size = sz;size = sz;/ / 將元素個數(shù)賦值給變量將元素個數(shù)賦值給變量sizesizelist = new T siz

21、e;list = new T size;/動態(tài)分配動態(tài)分配sizesize個個T T類型的元素空間類型的元素空間 template Array:Array() template Array:Array() / /析構(gòu)函數(shù)析構(gòu)函數(shù) delete list;delete list; /拷貝構(gòu)造函數(shù)拷貝構(gòu)造函數(shù)template Array:Array(const Array &a) template Array:Array(const Array &a) size = a.size; /size = a.size; /從對象從對象x x獲得數(shù)組大小，并賦值給當(dāng)前對象的成員獲得數(shù)組大小

22、，并賦值給當(dāng)前對象的成員/為對象懇求內(nèi)存并進(jìn)展出錯檢查為對象懇求內(nèi)存并進(jìn)展出錯檢查list = new Tsize;list = new Tsize;/ / 動態(tài)分配動態(tài)分配n n個個T T類型的元素空間類型的元素空間for (int i = 0; i size; i+) /for (int i = 0; i size; i+) /從對象從對象X X復(fù)制數(shù)組元素到本對象復(fù)制數(shù)組元素到本對象 listi = a.listi;listi = a.listi; 采用深拷貝，會調(diào)用類型采用深拷貝，會調(diào)用類型T的賦的賦值函數(shù)。值函數(shù)。(思索：為什么不是拷思索：為什么不是拷貝構(gòu)造函數(shù)？貝構(gòu)造函數(shù)？)針對每

23、個元素針對每個元素都會調(diào)用都會調(diào)用T的的缺省構(gòu)造函數(shù)缺省構(gòu)造函數(shù)動態(tài)數(shù)組類模板/重載重載=運(yùn)算符，將對象運(yùn)算符，將對象rhsrhs賦值給本對象。實現(xiàn)對象之間的整體賦值賦值給本對象。實現(xiàn)對象之間的整體賦值template template Array &Array:operator = (const Array& rhs) Array &Array:operator = (const Array& rhs) /假設(shè)本對象中數(shù)組大小與假設(shè)本對象中數(shù)組大小與rhsrhs不同，那么刪除數(shù)組原有內(nèi)存，然后重新分配不同，那么刪除數(shù)組原有內(nèi)存，然后重新分配if (&r

24、hs != this) if (&rhs != this) if (size != rhs.size) if (size != rhs.size) delete list;delete list; /刪除數(shù)組原有內(nèi)存刪除數(shù)組原有內(nèi)存size = rhs.size;size = rhs.size;/設(shè)置本對象的數(shù)組大小設(shè)置本對象的數(shù)組大小list = new Tsize;list = new Tsize;/重新分配重新分配n n個元素的內(nèi)存?zhèn)€元素的內(nèi)存 /從對象從對象X X復(fù)制數(shù)組元素到本對象復(fù)制數(shù)組元素到本對象 for (int i = 0; i size; i+)for (int i

25、 = 0; i size; i+)listi = rhs.listi;listi = rhs.listi; return return * *this;this;/前往當(dāng)前對象的援用前往當(dāng)前對象的援用 留意對函數(shù)留意對函數(shù)頭的了解頭的了解留意，賦值函數(shù)必需判留意，賦值函數(shù)必需判別能否為自賦值別能否為自賦值(由于由于能夠出現(xiàn)間接的自賦值能夠出現(xiàn)間接的自賦值)采用深拷貝，會調(diào)用類采用深拷貝，會調(diào)用類型型T的賦值函數(shù)。的賦值函數(shù)。為了實現(xiàn)鏈?zhǔn)奖磉_(dá)，應(yīng)該前往當(dāng)前對象的援為了實現(xiàn)鏈?zhǔn)奖磉_(dá)，應(yīng)該前往當(dāng)前對象的援用。用。(思索：能否前往思索：能否前往this？能否前往？能否前往rhs？)動態(tài)數(shù)組類模板/重載

26、下標(biāo)運(yùn)算符，實現(xiàn)與普通數(shù)組一樣經(jīng)過下標(biāo)訪問元素，并且具有越界檢查功能重載下標(biāo)運(yùn)算符，實現(xiàn)與普通數(shù)組一樣經(jīng)過下標(biāo)訪問元素，并且具有越界檢查功能template template T &Array:operator (int n) T &Array:operator (int n) assert(n = 0 & n = 0 & n size);/檢查下標(biāo)能否越界檢查下標(biāo)能否越界return listn;return listn;/前往下標(biāo)為前往下標(biāo)為n n的數(shù)組元素的數(shù)組元素 template template const T &Array:operator

27、 (int n) const const T &Array:operator (int n) const assert(n = 0 & n = 0 & n size);/檢查下標(biāo)能否越界檢查下標(biāo)能否越界return listn;return listn;/前往下標(biāo)為前往下標(biāo)為n n的數(shù)組元素的數(shù)組元素 /重載指針轉(zhuǎn)換運(yùn)算符，將重載指針轉(zhuǎn)換運(yùn)算符，將ArrayArray類的對象名轉(zhuǎn)換為類的對象名轉(zhuǎn)換為T T類型的指針類型的指針template template Array:operator T Array:operator T * * () () return list;

28、return list;/前往當(dāng)前對象中私有數(shù)組的首地址前往當(dāng)前對象中私有數(shù)組的首地址 針對常對象定針對常對象定義常函數(shù)義常函數(shù)這是類型轉(zhuǎn)換重載。轉(zhuǎn)換函數(shù)必需是成員函這是類型轉(zhuǎn)換重載。轉(zhuǎn)換函數(shù)必需是成員函數(shù)，它的聲明不能指定前往類型和參數(shù)表。數(shù)，它的聲明不能指定前往類型和參數(shù)表。動態(tài)數(shù)組類模板template template Array:operator const T Array:operator const T * * () const () const return list;return list;/前往當(dāng)前對象中私有數(shù)組的首地址前往當(dāng)前對象中私有數(shù)組的首地址 /取當(dāng)前數(shù)組的大小取當(dāng)

29、前數(shù)組的大小template template int Array:getSize() const int Array:getSize() const return size;return size; / / 將數(shù)組大小修正為將數(shù)組大小修正為szsztemplate template void Array:resize(int sz) void Array:resize(int sz) assert(sz = 0);assert(sz = 0);/檢查檢查szsz能否非負(fù)能否非負(fù)if (sz = size)if (sz = size) /假設(shè)指定的大小與原有大小一樣，什么也不做假設(shè)指定的大小與

30、原有大小一樣，什么也不做return;return;T T* * newList = new T sz; newList = new T sz;/懇求新的數(shù)組內(nèi)存懇求新的數(shù)組內(nèi)存int n = (sz size) ? sz : size;/int n = (sz size) ? sz : size;/將將szsz與與sizesize中較小的一個賦值給中較小的一個賦值給n n/將原有數(shù)組中前將原有數(shù)組中前n n個元素復(fù)制到新數(shù)組中個元素復(fù)制到新數(shù)組中for (int i = 0; i n; i+)for (int i = 0; i n; i+)newListi = listi;newListi

31、= listi;delete list;delete list;/刪除原數(shù)組刪除原數(shù)組list = newList;list = newList; / / 使使listlist指向新數(shù)組指向新數(shù)組size = sz;size = sz;/更新更新sizesize #endif /ARRAY_H#endif /ARRAY_H針對常對象定針對常對象定義常函數(shù)義常函數(shù)動態(tài)數(shù)組類模板template Array:Array(const Array& x) size = x.size; list = x.list;int main() Array a(10); . Array b(a); . l

32、istsizeaa的數(shù)組元素占用的內(nèi)存拷貝前 list sizeaa的數(shù)組元素占用的內(nèi)存拷貝后 list sizeb動態(tài)數(shù)組類模板 list sizeaa的數(shù)組元素占用的內(nèi)存拷貝前 list sizeaa的數(shù)組元素占用的內(nèi)存拷貝后 list sizebb的數(shù)組元素占用的內(nèi)存n假設(shè)一個函數(shù)的前往值是一個對象的值，就不應(yīng)成為左值n假設(shè)前往值為援用。由于援用是對象(變量)的別名，經(jīng)過援用當(dāng)然可以改動對象(變量)的值。這種情況下，函數(shù)的前往值可以成為左值動態(tài)數(shù)組類模板動態(tài)數(shù)組類模板#include #include using namespace std;using namespace std;voi

33、d read(int void read(int * *p, int n) p, int n) for (int i = 0; i n; i+) for (int i = 0; i pi; cin pi; int main() int main() int a10; int a10; read(a, 10); read(a, 10); return 0; return 0; #include Array.h#include Array.h#include #include using namespace std;using namespace std;void read(int void re

34、ad(int * *p, int n) p, int n) for (int i = 0; i n; i+) for (int i = 0; i pi; cin pi; int main() int main() Array a(10); Array a(10); read(a, 10); read(a, 10); return 0; return 0; 數(shù)組需求在函數(shù)組需求在函數(shù)之外創(chuàng)建數(shù)之外創(chuàng)建n例9-4求范圍2N中的質(zhì)數(shù)，N在程序運(yùn)轉(zhuǎn)時由鍵盤輸入動態(tài)數(shù)組類模板動態(tài)數(shù)組類模板#include #include #include #include #include Array.h#inclu

35、de Array.husing namespace std;using namespace std;int main() int main() Array a(10);Array a(10);/ / 用來存放質(zhì)數(shù)的數(shù)組，初始形狀有用來存放質(zhì)數(shù)的數(shù)組，初始形狀有1010個元素。個元素。int n, count = 0;int n, count = 0;cout = 2 as upper limit for prime numbers: ;cout = 2 as upper limit for prime numbers: ;cin n;cin n;for (int i = 2; i = n; i

36、+) for (int i = 2; i = n; i+) bool isPrime = true;bool isPrime = true;for (int j = 0; j count; j+)for (int j = 0; j count; j+)if (i % aj = 0) /if (i % aj = 0) /假設(shè)假設(shè)i i被被ajaj整除，闡明整除，闡明i i不是質(zhì)數(shù)不是質(zhì)數(shù) isPrime = false; break;isPrime = false; break; if (isPrime) if (isPrime) if (count = a.getSize() a.resize

37、(count if (count = a.getSize() a.resize(count * * 2); 2);acount+ = i;acount+ = i; for (int i = 0; i count; i+)for (int i = 0; i count; i+) cout setw(8) ai;cout setw(8) ai;cout endl;cout endl;return 0;return 0; count表示曾經(jīng)求表示曾經(jīng)求得的素數(shù)的個數(shù)得的素數(shù)的個數(shù)函數(shù)模板與類模板函數(shù)模板函數(shù)模板類模板類模板動態(tài)數(shù)組類模板動態(tài)數(shù)組類模板鏈表類模板鏈表類模板棧類模板棧類模板隊列類模板隊列

38、類模板綜合實例綜合實例模板的實例化機(jī)制模板的實例化機(jī)制模板的特化模板的特化模板元編程簡介模板元編程簡介n鏈表是一種動態(tài)數(shù)據(jù)構(gòu)造，可以用來表示順序訪問的線性群體n鏈表是由系列結(jié)點組成的，結(jié)點可以在運(yùn)轉(zhuǎn)時動態(tài)生成n每一個結(jié)點包括數(shù)據(jù)域和指向鏈表中下一個結(jié)點的指針即下一個結(jié)點的地址;假設(shè)鏈表每個結(jié)點中只需一個指向后繼結(jié)點的指針，那么該鏈表稱為單鏈表鏈表類模板鏈表類模板data1data2data3 datan NULLheadrear鏈表類模板template template class Node class Node private:private: Node Node * *next;next

39、;public:public: T data; T data; Node(const T& item,Node Node(const T& item,Node* * next = 0); next = 0); void insertAfter(Node void insertAfter(Node * *p);p); Node Node * *deleteAfter();deleteAfter(); Node Node * *nextNode();nextNode(); const Node const Node * *nextNode() const;nextNode() co

40、nst; ; 實例化之后的實例化之后的Node模板模板鏈表類模板data1data2 p datatemplate void Node:insertAfter(Node *p) /p節(jié)點指針域指向當(dāng)前節(jié)點的后繼節(jié)點 p-next = next; next = p; /當(dāng)前節(jié)點的指針域指向p 鏈表類模板data1data1data2data2data3data3tempPtrtempPtrNode *Node:deleteAfter(void) Node *tempPtr = next; if (next = 0) return 0; next = tempPtr-next; return te

41、mpPtr; 鏈表類模板/Node.h/Node.h#ifndef NODE_H#ifndef NODE_H#define NODE_H#define NODE_H/類模板的定義類模板的定義template template class Node class Node private:private:Node Node * *next;next;/指向后繼結(jié)點的指針指向后繼結(jié)點的指針public:public:T data;T data; /數(shù)據(jù)域數(shù)據(jù)域Node (const T &data, Node Node (const T &data, Node * *next = 0

42、); /next = 0); /構(gòu)造函數(shù)構(gòu)造函數(shù)void insertAfter(Node void insertAfter(Node * *p);p);/在本結(jié)點之后插入一個同類結(jié)點在本結(jié)點之后插入一個同類結(jié)點p p Node Node * *deleteAfter();deleteAfter(); /刪除本結(jié)點的后繼結(jié)點，并前往其地址刪除本結(jié)點的后繼結(jié)點，并前往其地址Node Node * *nextNode();nextNode();/獲取后繼結(jié)點的地址獲取后繼結(jié)點的地址const Node const Node * *nextNode() const;nextNode() const;

43、 / /獲取后繼結(jié)點的地址獲取后繼結(jié)點的地址;鏈表類模板/類的實現(xiàn)部分類的實現(xiàn)部分/構(gòu)造函數(shù)，初始化數(shù)據(jù)和指針成員構(gòu)造函數(shù)，初始化數(shù)據(jù)和指針成員template template Node:Node(const T& data, Node Node:Node(const T& data, Node * *next/next/* * = 0 = 0 * */) : data(data), /) : data(data), next(next) next(next) /前往后繼結(jié)點的指針前往后繼結(jié)點的指針template template Node Node * *Node:nex

44、tNode() Node:nextNode() return next;return next; /前往后繼結(jié)點的指針前往后繼結(jié)點的指針template template const Node const Node * *Node:nextNode() const Node:nextNode() const return next;return next; 鏈表類模板/在當(dāng)前結(jié)點之后插入一個結(jié)點在當(dāng)前結(jié)點之后插入一個結(jié)點p p template template void Node:insertAfter(Node void Node:insertAfter(Node * *p) p) p-n

45、ext = next; /p p-next = next; /p結(jié)點指針域指向當(dāng)前結(jié)點的后繼結(jié)點結(jié)點指針域指向當(dāng)前結(jié)點的后繼結(jié)點 next = p; next = p; / /當(dāng)前結(jié)點的指針域指向當(dāng)前結(jié)點的指針域指向p p /刪除當(dāng)前結(jié)點的后繼結(jié)點，并前往其地址刪除當(dāng)前結(jié)點的后繼結(jié)點，并前往其地址template template Node Node * *Node:deleteAfter() Node:deleteAfter() Node Node * *tempPtr = next;tempPtr = next;/將欲刪除的結(jié)點地址存儲到將欲刪除的結(jié)點地址存儲到tempPtrtempPtr

46、中中if (next = 0)if (next = 0)/假設(shè)當(dāng)前結(jié)點沒有后繼結(jié)點，那么前往空指針假設(shè)當(dāng)前結(jié)點沒有后繼結(jié)點，那么前往空指針return 0;return 0;next = tempPtr-next;next = tempPtr-next;/使當(dāng)前結(jié)點的指針域指向使當(dāng)前結(jié)點的指針域指向tempPtrtempPtr的后繼結(jié)點的后繼結(jié)點return tempPtr;return tempPtr;/前往被刪除的結(jié)點的地址前往被刪除的結(jié)點的地址 #endif /NODE_H#endif /NODE_Hn生成結(jié)點n插入結(jié)點n查找結(jié)點n刪除結(jié)點n遍歷鏈表n清空鏈表鏈表類模板鏈表類模板#ifn

47、def LINKEDLIST_H#ifndef LINKEDLIST_H#define LINKEDLIST_H#define LINKEDLIST_H#include Node.h#include Node.htemplate template class LinkedList class LinkedList private:private:/數(shù)據(jù)成員：數(shù)據(jù)成員：Node Node * *front, front, * *rearrearNode Node * *prevPtr, prevPtr, * *currPtr; currPtr; int size;int size;int pos

48、ition;int position;Node Node * *newNode(const T newNode(const T &item,Node &item,Node * *ptrNext=NULL);ptrNext=NULL);void freeNode(Node void freeNode(Node * *p);p);void copy(const void copy(const LinkedList &L);LinkedList &L);public:public:LinkedList();LinkedList();LinkedList(const L

49、inkedList(const LinkedList &L); LinkedList &L); LinkedList();LinkedList();LinkedList & operator = LinkedList & operator = (const LinkedList &L); (const LinkedList &L); int getSize() const;int getSize() const;bool isEmpty() const;bool isEmpty() const;void reset(int pos = 0);vo

50、id reset(int pos = 0);void next();void next();bool endOfList() const;bool endOfList() const;int currentPosition(void) int currentPosition(void) const;const;void insertFront(const T void insertFront(const T &item);&item);void insertRear(const T void insertRear(const T &item);&item);vo

51、id insertAt(const T &item);void insertAt(const T &item);void insertAfter(const T void insertAfter(const T &item);&item);T deleteFront();T deleteFront();void deleteCurrent();void deleteCurrent();T& data();T& data();const T& data() constconst T& data() constvoid clear()

52、;void clear();#endif /LINKEDLIST_H#endif /LINKEDLIST_H鏈表類模板/main.cpp/main.cpp#include #include #include LinkedList.h#include LinkedList.husing namespace std;using namespace std;int main() int main() LinkedList list;LinkedList list;for (int i = 0; i 10; i+) for (int i = 0; i item;cin item;list.insert

53、Front(item);list.insertFront(item); cout List: ;cout List: ;list.reset();list.reset();while (!list.endOfList() while (!list.endOfList() cout list.data() ;cout list.data() ;list.next();list.next(); cout endl;cout endl;鏈表類模板int key;int key;cout Please enter some integer needed to be deleted: ;cout key

54、;cin key;list.reset();list.reset();while (!list.endOfList() while (!list.endOfList() if (list.data() = key) if (list.data() = key) list.deleteCurrent();list.deleteCurrent();list.next();list.next(); cout List: ;cout List: ;list.reset();list.reset();while (!list.endOfList() while (!list.endOfList() co

55、ut list.data() ;cout list.data() ;list.next;list.next; cout endl;cout endl;return 0;return 0; 鏈表類模板運(yùn)轉(zhuǎn)結(jié)果如下：運(yùn)轉(zhuǎn)結(jié)果如下：3 6 5 7 5 2 4 5 9 103 6 5 7 5 2 4 5 9 10List: 10 9 5 4 2 5 7 5 6 3List: 10 9 5 4 2 5 7 5 6 3Please enter some integer needed to be deleted: 5Please enter some integer needed to be deleted

56、: 5List: 10 9 4 2 7 6 3List: 10 9 4 2 7 6 3函數(shù)模板與類模板函數(shù)模板函數(shù)模板類模板類模板動態(tài)數(shù)組類模板動態(tài)數(shù)組類模板鏈表類模板鏈表類模板棧類模板棧類模板隊列類模板隊列類模板綜合實例綜合實例模板的實例化機(jī)制模板的實例化機(jī)制模板的特化模板的特化模板元編程簡介模板元編程簡介n棧是只能從一端訪問的線性群體，可以訪問的這一端稱棧頂，另一端稱棧底。棧類模板anana2a2a1a1入棧入棧出棧出棧棧頂棧頂棧底棧底棧類模板ba/a/b+c*d(a)t1+a/b+c*dt1=a/b(b)dct1*+a/b+c*d(c)t3a/b+c*dt3=t1+t2(e)t2t1+a

57、/b+c*dt2=c*d(d)n棧空n棧中沒有元素n棧滿n棧中元素個數(shù)到達(dá)上限n普通形狀n棧中有元素，但未到達(dá)棧滿形狀棧類模板棧類模板棧頂ana1a0入棧出棧數(shù)組下標(biāo)maxn10普通形狀棧頂入棧出棧數(shù)組下標(biāo)初始形狀棧空maxn10棧頂amaxana1a0入棧出棧數(shù)組下標(biāo)maxn10棧滿形狀n初始化n入棧n出棧n清空棧n訪問棧頂元素n檢測棧的形狀滿、空棧類模板棧類模板/Stack.h/Stack.h#ifndef STACK_H#ifndef STACK_H#define STACK_H#define STACK_H#include #include template template clas

58、s Stack class Stack private:private:T listSIZE;T listSIZE;int top;int top;public:public:Stack();Stack();void push(const T &item);void push(const T &item);T pop();T pop();void clear();void clear();const T &peek() const;const T &peek() const;bool isEmpty() const;bool isEmpty() const;bo

59、ol isFull() const;bool isFull() const;棧類模板/模板的實現(xiàn)模板的實現(xiàn)template template Stack:Stack() : top(-1) Stack:Stack() : top(-1) template template void Stack:push(const T &item) void Stack:push(const T &item) assert(!isFull();assert(!isFull();list+top = item;list+top = item; template template T Stack:

60、pop() T Stack:pop() assert(!isEmpty();assert(!isEmpty();return listtop-;return listtop-; template template const T &Stack:peek() const const T &Stack:peek() const assert(!isEmpty();assert(!isEmpty();return listtop;return listtop;/前往棧頂元素前往棧頂元素 棧類模板template template bool Stack:isEmpty() const bool Stack:isEmpty() const return top = -1;return top = -1; template template bool Stack:isFull() const bool Stack:isFull() const return top = SIZE - 1;return top = SIZE - 1; template template void Stack:clear() void Stack:clear() top = -1;top = -1; #endif#endif /STACK_H/STACK_Hn例：一個簡單的整數(shù)計算器