C++第九章函數(shù)模板.ppt

1,本章主要內(nèi)容,模板 群體類 群體數(shù)據(jù)的組織 深度探索,2,第一部分：模板,函數(shù)模板 類模板,3,函數(shù)模板,函數(shù)模板可以用來創(chuàng)建一個通用功能的函數(shù)，以支持多種不同形參，進一步簡化重載函數(shù)的函數(shù)體設(shè)計。 定義方法： template 函數(shù)定義 模板參數(shù)表的內(nèi)容 類型參數(shù)：class（或typename） 標(biāo)識符 常量參數(shù)：類型說明符 標(biāo)識符 模板參數(shù)：template class 標(biāo)識符,函 數(shù) 模 板,4,求絕對值函數(shù)的模板,#include using namespace std; template T abs(T x) return x 0? -x : x; int main() int n = -5; double d = -5.5; cout abs(n) endl; cout abs(d) endl; return 0; ,函 數(shù) 模 板,運行結(jié)果： 5 5.5,5,求絕對值函數(shù)的模板分析,編譯器從調(diào)用abs()時實參的類型，推導(dǎo)出函數(shù)模板的類型參數(shù)。例如，對于調(diào)用表達式abs(n)，由于實參n為int型，所以推導(dǎo)出模板中類型參數(shù)T為int。 當(dāng)類型參數(shù)的含義確定后，編譯器將以函數(shù)模板為樣板，生成一個函數(shù)： int abs(int x) return x 0 ? x : x; ,函 數(shù) 模 板,6,類模板的作用,使用類模板使用戶可以為類聲明一種模式，使得類中的某些數(shù)據(jù)成員、某些成員函數(shù)的參數(shù)、某些成員函數(shù)的返回值，能取任意類型（包括基本類型的和用戶自定義類型）。,類 模 板,7,類模板的聲明,類模板： template class 類名 類成員聲明 如果需要在類模板以外定義其成員函數(shù)，則要采用以下的形式： template 類型名 類名:函數(shù)名（參數(shù)表）,類 模 板,8,例9-2 類模板應(yīng)用舉例,#include #include using namespace std; / 結(jié)構(gòu)體Student struct Student int id; /學(xué)號 float gpa; /平均分 ;,類 模 板,template class Store /類模板：實現(xiàn)對任意類型數(shù)據(jù)進行存取 private: T item; / item用于存放任意類型的數(shù)據(jù) bool haveValue; / haveValue標(biāo)記item是否已被存入內(nèi)容 public: Store(); / 缺省形式（無形參）的構(gòu)造函數(shù) T /以下實現(xiàn)各成員函數(shù)。 template /缺省構(gòu)造函數(shù)的實現(xiàn) Store:Store(): haveValue(false) ,9,template /提取數(shù)據(jù)函數(shù)的實現(xiàn) T / 將x值存入item ,10,int main() Store s1, s2; s1.putElem(3); s2.putElem(-7); cout s3; s3.putElem(g); cout d; cout “Retrieving object D. “; cout d.getElem() endl /由于d未經(jīng)初始化,在執(zhí)行函數(shù)D.getElement()過程中導(dǎo)致程序終止 return 0; ,11,12,第二部分：群體數(shù)據(jù),線性群體 線性群體的概念 直接訪問群體-數(shù)組類 順序訪問群體-鏈表類 棧類 隊列類,13,群體的概念,群體是指由多個數(shù)據(jù)元素組成的集合體。群體可以分為兩個大類：線性群體和非線性群體。 線性群體中的元素按位置排列有序，可以區(qū)分為第一個元素、第二個元素等。 非線性群體不用位置順序來標(biāo)識元素。,14,線性群體的概念,線性群體中的元素次序與其位置關(guān)系是對應(yīng)的。在線性群體中，又可按照訪問元素的不同方法分為直接訪問、順序訪問和索引訪問。 在本章我們只介紹直接訪問和順序訪問。,15,數(shù)組,靜態(tài)數(shù)組是具有固定元素個數(shù)的群體，其中的元素可以通過下標(biāo)直接訪問。 缺點：大小在編譯時就已經(jīng)確定，在運行時無法修改。 動態(tài)數(shù)組由一系列位置連續(xù)的，任意數(shù)量相同類型的元素組成。 優(yōu)點：其元素個數(shù)可在程序運行時改變。 vector就是用類模板實現(xiàn)的動態(tài)數(shù)組。 動態(tài)數(shù)組類模板：例9-3（Array.h）,直接訪問的線性群體,#ifndef ARRAY_H #define ARRAY_H #include template /數(shù)組類模板定義 class Array private: T* list;/用于存放動態(tài)分配的數(shù)組內(nèi)存首地址 int size; /數(shù)組大小（元素個數(shù)） public: Array(int sz = 50); /構(gòu)造函數(shù) Array(const Array ,16,動態(tài)數(shù)組類模板程序,17,數(shù)組類模板模板的構(gòu)造函數(shù),/ 構(gòu)造函數(shù) template Array:Array(int sz) /sz為數(shù)組大?。ㄔ貍€數(shù)），應(yīng)當(dāng)非負 assert(sz = 0); / 將元素個數(shù)賦值給變量size size = sz; /動態(tài)分配size個T類型的元素空間 list = new T size; ,直接訪問的線性群體,18,數(shù)組類模板的拷貝構(gòu)造函數(shù),/拷貝構(gòu)造函數(shù) template Array:Array(const Array ,直接訪問的線性群體,19,淺拷貝,int main() Array a(10); Array b(a); ,template Array:Array( const Array ,20,深拷貝,21,數(shù)組類模板的重載“=“運算符函數(shù),/重載“=”運算符 template Array /返回當(dāng)前對象的引用 ,直接訪問的線性群體,22,數(shù)組類模板的重載下標(biāo)操作符函數(shù),template T /返回下標(biāo)為n的數(shù)組元素 ,直接訪問的線性群體,23,為什么有的函數(shù)返回引用,如果一個函數(shù)的返回值是一個對象的值，就不應(yīng)成為左值。 如果返回值為引用。由于引用是對象的別名，通過引用當(dāng)然可以改變對象的值。,直接訪問的線性群體,24,重載指針轉(zhuǎn)換操作符,template Array:operator T * () return list; /返回私有數(shù)組的首地址 template Array:operator const T * () const return list; /返回私有數(shù)組的首地址 ,直接訪問的線性群體,25,指針轉(zhuǎn)換運算符的作用,#include using namespace std; void read(int *p, int n) for (int i = 0; i pi; int main() int a10; read(a, 10); return 0; ,#include “Array.h“ #include using namespace std; void read(int *p, int n) for (int i = 0; i pi; int main() Array a(10); read(a, 10); return 0; ,直接訪問的線性群體,26,Array類的應(yīng)用,例9-4求范圍2N中的質(zhì)數(shù)，N在程序運行時由鍵盤輸入。,直接訪問的線性群體,#include #include #include “Array.h“ using namespace std; int main() Array a(10); / 用來存放質(zhì)數(shù)的數(shù)組，初始狀態(tài)有10個元素。 int n, count = 0; cout = 2 as upper limit for prime numbers: “; cin n; for (int i = 2; i = n; i+) bool isPrime = true; for (int j = 0; j count; j+) if (i % aj = 0) /若i被aj整除，說明i不是質(zhì)數(shù) isPrime = false; break; if (isPrime) if (count = a.getSize() a.resize(count * 2); acount+ = i; for (int i = 0; i count; i+) cout setw(8) ai; cout endl; return 0; ,27,28,鏈表,鏈表是一種動態(tài)數(shù)據(jù)結(jié)構(gòu)，可以用來表示順序訪問的線性群體。 鏈表是由系列結(jié)點組成的，結(jié)點可以在運行時動態(tài)生成。 每一個結(jié)點包括數(shù)據(jù)域和指向鏈表中下一個結(jié)點的指針（即下一個結(jié)點的地址）。如果鏈表每個結(jié)點中只有一個指向后繼結(jié)點的指針，則該鏈表稱為單鏈表。,順序訪問的線性群體,29,單鏈表,順序訪問的線性群體,30,單鏈表的結(jié)點類模板,template class Node private: Node *next; public: T data; Node(const T,順序訪問的線性群體,31,在結(jié)點之后插入一個結(jié)點,data1,p,data,template void Node:insertAfter(Node *p) /p節(jié)點指針域指向當(dāng)前節(jié)點的后繼節(jié)點 p-next = next; next = p; /當(dāng)前節(jié)點的指針域指向p ,順序訪問的線性群體,32,刪除結(jié)點之后的結(jié)點,順序訪問的線性群體,data1,Node *Node:deleteAfter(void) Node *tempPtr = next; if (next = 0) return 0; next = tempPtr-next; return tempPtr; ,tempPtr,33,鏈表的基本操作,生成結(jié)點 插入結(jié)點 查找結(jié)點 刪除結(jié)點 遍歷鏈表 清空鏈表,順序訪問的線性群體,34,鏈表類模板(例9-6),順序訪問的線性群體,#ifndef LINKEDLIST_H #define LINKEDLIST_H #include “Node.h“ template class LinkedList private: /數(shù)據(jù)成員： Node *front, *rear Node *prevPtr, *currPtr; int size; int position; Node *newNode(const T ,LinkedList #endif /LINKEDLIST_H,35,鏈表類應(yīng)用舉例(例9-7),順序訪問的線性群體,/9_7.cpp #include #include “LinkedList.h“ using namespace std; int main() LinkedList list; for (int i = 0; i item; list.insertFront(item); cout “List: “; list.reset(); while (!list.endOfList() cout list.data() “ “; list.next(); cout endl;,int key; cout key; list.reset(); while (!list.endOfList() if (list.data() = key) list.deleteCurrent(); list.next(); cout “List: “; list.reset(); while (!list.endOfList() cout list.data() “ “; list.next cout endl; return 0; ,36,特殊的線性群體棧,棧是只能從一端訪問的線性群體，可以訪問的這一端稱棧頂，另一端稱棧底。,特殊的線性群體棧,37,棧的應(yīng)用舉例表達式處理,特殊的線性群體棧,38,棧的基本狀態(tài),?？?棧中沒有元素 棧滿 棧中元素個數(shù)達到上限 一般狀態(tài) 棧中有元素，但未達到棧滿狀態(tài),特殊的線性群體棧,39,40,棧的基本操作,初始化 入棧 出棧 清空棧 訪問棧頂元素 檢測棧的狀態(tài)（滿、空）,特殊的線性群體棧,41,棧類模板(例9-8),特殊的線性群體棧,/Stack.h #ifndef STACK_H #define STACK_H #include template class Stack private: T listSIZE; int top;,public: Stack(); void push(const T /類的實現(xiàn)略,42,棧的應(yīng)用,例9.9 一個簡單的整數(shù)計算器 實現(xiàn)一個簡單的整數(shù)計算器，能夠進行加、減、乘、除和乘方運算。使用時算式采用后綴輸入法，每個操作數(shù)、操作符之間都以空白符分隔。例如，若要計算“3+5“則輸入“3 5 +“。乘方運算符用“表示。每次運算在前次結(jié)果基礎(chǔ)上進行，若要將前次運算結(jié)果清除，可鍵入“c“。當(dāng)鍵入“q“時程序結(jié)束。 Calculator.h Calculator.cpp 9_9.cpp,特殊的線性群體棧,/Calculator.h #ifndef CALCULATOR_H #define CALCULATOR_H #include “Stack.h“ / 包含棧類模板定義文件 class Calculator /計算器類 private: Stack s; / 操作數(shù)棧 void enter(double num); /將操作數(shù)num壓入棧 /連續(xù)將兩個操作數(shù)彈出棧，放在opnd1和opnd2中 bool getTwoOperands(double #endif /CALCULATOR_H,43,/Calculator.cpp #include “Calculator.h“ #include #include #include using namespace std; /工具函數(shù)，用于將字符串轉(zhuǎn)換為實數(shù) inline double stringToDouble(const string ,44,bool Calculator:getTwoOperands(double ,45,void Calculator:compute(char op) /執(zhí)行運算 double operand1, operand2; bool result = getTwoOperands(operand1, operand2); if (result) /如果成功，執(zhí)行運算并將運算結(jié)果壓入棧 switch(op) case +: s.push(operand2 + operand1); break; case -: s.push(operand2 - operand1); break; case *: s.push(operand2 * operand1); break; case /: if (operand1 = 0) /檢查除數(shù)是否為0 cerr “Divided by 0!“ endl; s.clear(); /除數(shù)為0時清空棧 else s.push(operand2 / operand1); break; case : s.push(pow(operand2, operand1); break; default: cerr “Unrecognized operator!“ endl; break; cout “= “ s.peek() “ “; /輸出本次運算結(jié)果 else s.clear(); /操作數(shù)不夠，清空棧 ,46,void Calculator:run() /讀入并處理后綴表達式 string str; while (cin str, str != “q“) switch(str0) case c: s.clear(); break; case -: /遇-需判斷是減號還是負號 if (str.size() 1) enter(stringToDouble(str); else compute(str0); break; case +: /遇到其它操作符時 case *: case /: case : compute(str0); default: /若讀入的是操作數(shù)，轉(zhuǎn)換為整型后壓入棧 enter(stringToDouble(str); break; void Calculator:clear() /清空操作數(shù)棧 s.clear(); ,47,/9_9.cpp #include “Calculator.h“ int main() Calculator c; c.run(); return 0; ,48,49,特殊的線性群體隊列,隊列是只能向一端添加元素，從另一端刪除元素的線性群體,50,隊列的基本狀態(tài),隊空 隊列中沒有元素 隊滿 隊列中元素個數(shù)達到上限 一般狀態(tài) 隊列中有元素，但未達到隊滿狀態(tài),特殊的線性群體隊列,元素移動方向,元素移動方向,51,52,循環(huán)隊列,在想象中將數(shù)組彎曲成環(huán)形，元素出隊時，后繼元素不移動，每當(dāng)隊尾達到數(shù)組最后一個元素時，便再回到數(shù)組開頭。,特殊的線性群體隊列,53,54,第三部分：群體數(shù)據(jù)的組織,插入排序 選擇排序 交換排序 順序查找 折半查找,55,排序（sorting）,排序是計算機程序設(shè)計中的一種重要操作，它的功能是將一個數(shù)據(jù)元素的任意序列，重新排列成一個按關(guān)鍵字有序的序列。 數(shù)據(jù)元素：數(shù)據(jù)的基本單位。在計算機中通常作為一個整體進行考慮。一個數(shù)據(jù)元素可由若干數(shù)據(jù)項組成。 關(guān)鍵字：數(shù)據(jù)元素中某個數(shù)據(jù)項的值，用它可以標(biāo)識（識別）一個數(shù)據(jù)元素。 在排序過程中需要完成兩種基本操作： 比較兩個數(shù)的大小 調(diào)整元素在序列中的位置,群體數(shù)據(jù)的組織,56,內(nèi)部排序與外部排序,內(nèi)部排序：待排序的數(shù)據(jù)元素存放在計算機內(nèi)存中進行的排序過程。 外部排序：待排序的數(shù)據(jù)元素數(shù)量很大，以致內(nèi)存存中一次不能容納全部數(shù)據(jù)，在排序過程中尚需對外存進行訪問的排序過程。,群體數(shù)據(jù)的組織,57,內(nèi)部排序方法,插入排序 選擇排序 交換排序,群體數(shù)據(jù)的組織,58,插入排序的基本思想,每一步將一個待排序元素按其關(guān)鍵字值的大小插入到已排序序列的適當(dāng)位置上，直到待排序元素插入完為止。,初始狀態(tài)： 5 4 10 20 12 3,59,直接插入排序,在插入排序過程中，由于尋找插入位置的方法不同又可以分為不同的插入排序算法，這里我們只介紹最簡單的直接插入排序算法。 例9-11 直接插入排序函數(shù)模板（9_11.h）,群體數(shù)據(jù)的組織,template void insertionSort(T a, int n) int i, j; T temp; for (int i = 1; i 0 ,直接插入排序函數(shù)模板（9_11.h）,60,61,選擇排序的基本思想,每次從待排序序列中選擇一個關(guān)鍵字最小的元素，（當(dāng)需要按關(guān)鍵字升序排列時），順序排在已排序序列的最后，直至全部排完。,3 4 10 20 12 5,3 4 10 20 12 5,第 i 次選擇后，將選出的那個記錄與第 i 個記錄做交換。,62,直接選擇排序,在選擇類排序方法中，從待排序序列中選擇元素的方法不同，又分為不同的選擇排序方法，其中最簡單的是通過順序比較找出待排序序列中的最小元素，稱為直接選擇排序。 例9-12 直接選擇排序函數(shù)模板（9-12.h）,群體數(shù)據(jù)的組織,template void mySwap(T ,直接選擇排序函數(shù)模板（9-12.h）,63,64,交換排序的基本思想,兩兩比較待排序序列中的元素，并交換不滿足順序要求的各對元素，直到全部滿足順序要求為止。,群體數(shù)據(jù)的組織,65,最簡單的交換排序方法 起泡排序,對具有n個元素的序列按升序進行起泡排序的步驟： 首先將第一個元素與第二個元素進行比較，若為逆序，則將兩元素交換。然后比較第二、第三個元素，依次類推，直到第n-1和第n個元素進行了比較和交換。此過程稱為第一趟起泡排序。經(jīng)過第一趟，最大的元素便被交換到第n個位置。 對前n-1個元素進行第二趟起泡排序，將其中最大元素交換到第n-1個位置。 如此繼續(xù)，直到某一趟排序未發(fā)生任何交換時，排序完畢。對n個元素的序列，起泡排序最多需要進行n-1趟。,群體數(shù)據(jù)的組織,66,起泡排序舉例,對整數(shù)序列 8 5 2 4 3 按升序排序,8 5 2 4 3,5,2,4,3,8,2,4,3,5,8,2,3,4,5,8,2,3,4,5,8,初始狀態(tài),第一趟結(jié)果,第二趟結(jié)果,第三趟結(jié)果,第四趟結(jié)果,小的逐漸上升,每趟沉下一個最大的,群體數(shù)據(jù)的組織,67,例9-13 起泡排序函數(shù)模板,template void mySwap(T ,template void bubbleSort(T a, int n) int i = n 1; while (i 0) int lastExchangeIndex = 0; for (int j = 0; j i; j+) if (aj + 1 aj) mySwap(aj, aj + 1); lastExchangeIndex = j; i = lastExchangeIndex; ,群體數(shù)據(jù)的組織,68,順序查找,其基本思想 從序列的首元素開始，逐個元素與待查找的關(guān)鍵字進行比較，直到找到相等的。若整個序列中沒有與待查找關(guān)鍵字相等的元素，就是查找不成功。 順序查找函數(shù)模板 例9-14,群體數(shù)據(jù)的組織,template int seqSearch(const T list, int n, const T ,順序查找函數(shù)模板,69,70,折半查找的基本思想,對于已按關(guān)鍵字排序的序列，經(jīng)過一次比較，可將序列分割成兩部分，然后只在有可能包含待查元素的一部分中繼續(xù)查找，并根據(jù)試探結(jié)果繼續(xù)分割，逐步縮小查找范圍，直至找到或找不到為止。,群體數(shù)據(jù)的組織,71,折半查找舉例,用折半查找法，在下列序列中查找值為21的元素：,M=INT(L+H)/2)=3,L=M+1=4,M=INT(L+H)/2)=4,72,例9-15 折半查找函數(shù)模板,template int binSearch(const T list, int n, const T ,群體數(shù)據(jù)的組織,類模板 vs 類,類模板不能表示具體的數(shù)據(jù)類型，但類模板的實例化類是數(shù)據(jù)類型 例：如要使reverse函數(shù)接收Array的參數(shù) void reverse(Array 正確。T雖未定，但Array表示的是一個類模板實例。 同一模板在不同參數(shù)下的實例是完全無關(guān)的類型 彼此不兼容，無法相互賦值 通過Store的對象調(diào)用的成員函數(shù)，無法直接訪問Store對象的私有成員,73,深度探索,函數(shù)模板 vs 函數(shù),函數(shù)模板本身不是函數(shù) 編譯器不會為函數(shù)模板本身生成目標(biāo)代碼 只有函數(shù)模板的實例能被調(diào)用 例：考慮下列模板 template void outputArray(const T *array, int count); 若a是int數(shù)組，outputArray(a, 10)等價于outputArray(a, 10)，被調(diào)用的是outputArray實例,74,深度探索,隱含實例化,模板的實例化 根據(jù)函數(shù)模板生成具體的函數(shù)、或根據(jù)類模板生成具體的類的過程 隱含實例化 編譯器會自動按需對模板實例化 所有會被使用的模板實例會被生成 對類模板的隱含實例化并不意味著對它成員函數(shù)的定義也進行實例化，當(dāng)類模板成員函數(shù)會被使用時，才會被實例化,75,深度探索,多文件結(jié)構(gòu)中模板的組織,模板實例化機制帶來的新問題 不能把下面與模板相關(guān)的定義放在源文件中 函數(shù)模板的定義 類模板成員函數(shù) 類模板靜態(tài)數(shù)據(jù)成員 解決方法 把與模板相關(guān)的定義放在頭文件中最通常的解決辦法 編譯器有特殊處理，保證不會有連接沖突 使用export關(guān)鍵字編譯器支持不好 使用模板的顯式實例化機制,76,深度探索,顯式實例化,語法形式 template 實例化目標(biāo)的聲明; 作用 一個模板實例無論是否在本編譯單元中被使用，都會被生成 例 template void outputArray(const int *array, int count); template class Store; 在多文件結(jié)構(gòu)中的用途 使用在程序中可能會被用到的各種參數(shù)對模板顯式實例化，使得與模板相關(guān)的定義可以放在源文件中,77,深度探索,為模板定義特殊的實現(xiàn),為什么要定義特殊的實現(xiàn)？ 模板抓住了算法與數(shù)據(jù)結(jié)構(gòu)上的共性，但忽略了類型的個性 設(shè)計出的模板對于具體的數(shù)據(jù)類型而言未必具有最好的效率 例：Stack類模板 如果以bool作為類型參數(shù)，則有7/8的空間浪費 Stack中的list數(shù)組占32個字節(jié)，實際上4個字節(jié)就夠,78,深度探索,模板的特化,什么是特化 為一個模板在特定參數(shù)下提供特殊定義 既適用于類模板，又適用于函數(shù)模板 對Stack特化的類定義,template class Stack private: unsigned list; int top; public: Stack(); void push(bool item); bool pop(); void clear(); bool peek() const; bool isEmpty() const; bool isFull() const; ;,79,深度探索,/特化類的部分成員函數(shù)定義 void Stack:push(bool item) assert(!isFull(); +top; list = (list :pop() assert(!isEmpty(); bool result = (list ,80,類模板的偏特化,對Stack特化的問題 適用范圍過窄，SIZE必須是32 類模板的偏特化 將一部分參數(shù)固定，而使另一部分參數(shù)可變，設(shè)計特殊的定義 只適用于類模板 對Stack偏特化的類定義,template class Stack private: enum UNIT_BITS = sizeof(unsigned) * 8, ARRAY_SIZE = (SIZE - 1) / UNIT_BITS + 1 ; unsigned listARRAY_SIZE; int top; public: Stack(); void push(bool item); bool pop(); void clear(); bool peek() const; bool isEmpty() const; bool isFull() const; ;,81,深度探索,/偏特化類的部分成員函數(shù)定義 template void Stack:push(bool item) assert(!isFull(); int index = +top / UNIT_BITS; listindex = (listindex bool Stack:pop() assert(!isEmpty(); int index = top- / UNIT_BITS; bool result = (listindex ,82,類模板的偏特化,偏特化不僅允許將一部分模板參數(shù)固定，