【正文】 } 87 深度探索 C++語言程序設(shè)計(jì) 清華大學(xué) 鄭莉 92 小結(jié)與復(fù)習(xí)建議 ? 主要內(nèi)容 – 模板、群體類和群體數(shù)據(jù)的組織 ? 達(dá)到的目標(biāo) – 理解模板的作用，學(xué)會簡單的應(yīng)用。 ? 原模板， T可以是所有類型參數(shù) – template class T class XT * { … }。 1) == 1)。 list[index] = (list[index] 1) | (item ? 1 : 0)。 bool isFull() const。 bool pop()。 unsigned list[ARRAY_SIZE]。 list = 1。 list = (list 1) | (item ? 1 : 0)。 bool isFull() const。 bool pop()。 ? 在多文件結(jié)構(gòu)中的用途 – 使用在程序中可能會被用到的各種參數(shù)對模板顯式實(shí)例化，使得與模板相關(guān)的定義可以放在源文件中 80 深度探索 C++語言程序設(shè)計(jì) 清華大學(xué) 鄭莉 為模板定義特殊的實(shí)現(xiàn) ? 為什么要定義特殊的實(shí)現(xiàn)？ – 模板抓住了算法與數(shù)據(jù)結(jié)構(gòu)上的共性，但忽略了類型的個性 – 設(shè)計(jì) 出的模板對于具體的數(shù)據(jù)類型而言未必具有最好的效率 ? 例： Stack類模板 – 如果以 bool作為類型參數(shù)，則有 7/8的空間浪費(fèi) – Stackbool,32中的 list數(shù)組占 32個字節(jié)，實(shí)際上 4個字節(jié)就夠 81 深度探索 C++語言程序設(shè)計(jì) 清華大學(xué) 鄭莉 模板的特化 ? 什么是特化 – 為一個模板在特定參數(shù)下提供特殊定義 ? 既適用于類模板，又適用于函數(shù)模板 ? 對 Stackbool, 32特化的類定義 template class Stackbool, 32 { private: unsigned list。 ? 同 一模板在不同參數(shù)下的實(shí)例是完全無關(guān)的類型 – 彼此不兼容，無法相互賦值 – 通過 Storeint的對象調(diào)用的成員函數(shù)，無法直接訪問 Storedouble對象的私有成員 76 深度探索 C++語言程序設(shè)計(jì) 清華大學(xué) 鄭莉 函數(shù)模板 vs 函數(shù) ? 函數(shù)模板本身不是函數(shù) – 編譯器不會為函數(shù)模板本身生成目標(biāo)代碼 – 只有函數(shù)模板的實(shí)例能被調(diào)用 ? 例：考慮下列模板 template class T void outputArray(const T *array, int count)。 – template class T reverse (ArrayT amp。 – void reverse(Arrayint amp。 } return 1。 while (low = high) { int mid = (low + high) / 2。 } 順序查找函數(shù)模板 71 C++語言程序設(shè)計(jì) 清華大學(xué) 鄭莉 72 折半查找的基本思想 對于已按關(guān)鍵字排序的序列，經(jīng)過一次比較，可將序列分割成兩部分，然后只在有可能包含待查元素的一部分中繼續(xù)查找，并根據(jù)試探結(jié)果繼續(xù)分割，逐步縮小查找范圍，直至找到或找不到為止。key) { for(int i = 0。 } i = lastExchangeIndex。 for (int j = 0。 x = y。對 n個元素的序列，起泡排序最多需要進(jìn)行 n1趟。此過程稱為第一趟起泡排序。 mySwap(a[i], a[leastIndex ])。 i++) { int leastIndex = i。 x = y。 3 4 5 [20 12 10] ... ... C++語言程序設(shè)計(jì) 清華大學(xué) 鄭莉 64 直接選擇排序 ? 在選擇類排序方法中，從待排序序列中選擇元素的方法不同，又分為不同的選擇排序方法，其中最簡單的是通過順序比較找出待排序序列中的最小元素，稱為直接選擇排序。 j。 T temp = a[i]。 T temp。 ? 外部排序： 待排序的數(shù)據(jù)元素?cái)?shù)量很大，以致內(nèi)存存中一次不能容納全部數(shù)據(jù)，在排序過程中尚需對外存進(jìn)行訪問的排序過程。在計(jì)算機(jī)中通常作為一個整體進(jìn)行考慮。 }。 const T amp。 void push(const T amp。 } C++語言程序設(shè)計(jì) 清華大學(xué) 鄭莉 38 特殊的線性群體 ——棧 棧是只能從一端訪問的線性群體，可以訪問的這一端稱棧頂，另一端稱棧底。 ()。 ()。 } cout endl。 } cout List: 。 i 10。在程序結(jié)束之前清空鏈表。 data() const void clear()。 void deleteCurrent()。item)。item)。 void reset(int pos = 0 void next()。 operator = (const LinkedListT amp。 LinkedList(const LinkedListT amp。 void freeNode(NodeT *p)。 int size。 if (next == 0) return 0。 }。 item,NodeT* next = 0)。如果鏈表每個結(jié)點(diǎn)中只有一個指向后繼結(jié)點(diǎn)的指針，則該鏈表稱為單鏈表。 return 0。 } } for (int i = 0。 j++) if (i % a[j] == 0) { //若 i被 a[j]整除，說明 i不是質(zhì)數(shù) isPrime = false。 i = n。 int n, count = 0。 } 直接訪問的線性群體 C++語言程序設(shè)計(jì) 清華大學(xué) 鄭莉 27 Array類的應(yīng)用 ? 例 94求范圍 2~N中的質(zhì)數(shù)， N在程序運(yùn)行時由鍵盤輸入。 i++) cin p[i]。 return 0。 i n。 直接訪問的線性群體 C++語言程序設(shè)計(jì) 清華大學(xué) 鄭莉 25 重載指針轉(zhuǎn)換操作符 template class T ArrayT::operator T * () { return list。 //越界檢查 return list[n]。 //返回下標(biāo)為 n的數(shù)組元素 } template class T const T amp。ArrayT::operator[] (int n) { assert(n = 0 amp。 i size。rhs != this) { if (size != ) { delete [] list。 list = 。 } 直接訪問的線性群體 C++語言程序設(shè)計(jì) 清華大學(xué) 鄭莉 20 淺拷貝 list size a a的數(shù)組元素 占用的內(nèi)存 拷貝前 list size a a的數(shù)組元素 占用的內(nèi)存 拷貝后 list size b int main() { Arrayint a(10)。 //為對象申請內(nèi)存并進(jìn)行出錯檢查 list = new T[size]。 // 將元素個數(shù)賦值給變量 size size = sz。 int getSize() const。 //重載 []” const T amp。 operator = (const ArrayT amp。 //構(gòu)造函數(shù) Array(const ArrayT amp。 ? vector就是用類模板實(shí)現(xiàn)的動態(tài)數(shù)組。 … 第一個元素 第二個元素 第三個元素 最后一個元素 C++語言程序設(shè)計(jì) 清華大學(xué) 鄭莉 16 數(shù)組 ? 靜態(tài)數(shù)組是具有固定元素個數(shù)的群體，其中的元素可以通過下標(biāo)直接訪問。 非線性群體不用位置順序來標(biāo)識元素。 cout () endl //由于 d未經(jīng)初始化 ,執(zhí)行函數(shù) ()時導(dǎo)致程序終止 return 0。 (g)。 (7)。x) { // 將 haveValue 置為 true，表示 item中已存入數(shù)值 haveValue = true。 exit(1)。 //存入數(shù)據(jù)函數(shù) }。 // 缺省形式（無形參）的構(gòu)造函數(shù) T amp。 //平均分 }。 } 函 數(shù) 模 板 C++語言程序設(shè)計(jì) 清華大學(xué) 鄭莉 7 類模板的作用 使用類模板使用戶可以為類聲明一種模式，使得類中的某些數(shù)據(jù)成員、某些成員函數(shù)的參數(shù)、某些成員函數(shù)的返回值，能取任意類型（包括基本類型的和用戶自定義類型）。 return 0。 } int main() { int n = 5。第九章 群體類 和群體數(shù)據(jù)的組織 清華大學(xué) 鄭 莉 C++語言程序設(shè)計(jì) C++語言程序設(shè)計(jì) 清華大學(xué) 鄭莉 2 本章主要內(nèi)容 ? 模板 ? 群體類