【正文】 A[smallIndex])。 i++) { smallIndex = i。 } template class T void SelectionSort(T A[], int n) { int smallIndex。 ? 例 912 直接選擇排序函數(shù)模板（ 9） 群體數(shù)據(jù)的組織 template class T void Swap (T x, T y) { T temp。 } A[j] = temp。 i++) { j = i。 ? 例 911 直接插入排序函數(shù)模板（ ） 群體數(shù)據(jù)的組織 template class T void InsertionSort(T A[], int n) { int i, j。 ? 在排序過程中需要完成兩種基本操作： – 比較兩個數(shù)的大小 – 調(diào)整元素在序列中的位置 群體數(shù)據(jù)的組織 64 內(nèi)部排序與外部排序 ? 內(nèi)部排序： 待排序的數(shù)據(jù)元素存放在計算機內(nèi)存中進行的排序過程。 – 數(shù)據(jù)元素： 數(shù)據(jù)的基本單位。 int QEmpty(void) const。 T QDelete(void)。 template class T class Queue { private: int front, rear, count。 ()。 default: Enter(atoi(c))。: case 39。: case 39。 else Compute(*c)。 break。q39。 39。 break。 break。/39。*39。39。+39。 } 52 void Calculator::Compute(char op) { Boolean result。 if (()) { cerr Missing operand! endl。 51 void Calculator::Enter(int num) { (num)。 void Compute(char op)。 enum Boolean {False, True}。乘方運算符用 ^表示。 }。 void ClearStack(void)。 int top。 } 42 43 特殊的線性群體 —— 棧 棧是只能從一端訪問的線性群體，可以訪問的這一端稱棧頂，另一端稱棧底。 ()。 ()。 ()。 (item)。 int i, key, item。 void ClearList(void)。 void InsertAfter(const T item)。 int CurrentPosition(void) const。 int ListEmpty(void) const。 LinkedList(const LinkedListT L)。 NodeT *GetNode(const T item, NodeT *ptrNext=NULL)。 endif // NULL include 順序訪問的線性群體 template class T class LinkedList { private: NodeT *front, *rear。 next = tempPtrnext。 順序訪問的線性群體 33 在結(jié)點之后插入一個結(jié)點 data1 data2 … p data … template class T void NodeT::InsertAfter(NodeT *p) { //p節(jié)點指針域指向當前節(jié)點的后繼節(jié)點 pnext = next。 void InsertAfter(NodeT *p)。如果鏈表每個結(jié)點中只有一個指向后繼結(jié)點的指針，則該鏈表稱為單鏈表。 } cout endl。 } for (i = 0。 if (i % 2 == 0) continue。 A[primecount++] = 2。 int n。 i++) cinp[i]。 void read(int *p, n)。 } void read(int *p, int n) { for (int i=0。 } 直接訪問的線性群體 27 指針轉(zhuǎn)換運算符的作用 include iostream using namespace std。 } 直接訪問的線性群體 25 為什么有的函數(shù)返回引用 ? 如果一個函數(shù)的返回值是一個對象的值，它就被認為是一個常量，不能成為左值。 while (n) *destptr++ = *srcptr++。 if (alist == NULL) Error(memoryAllocationError)。 alist= 。 // alist是本對象中的數(shù)組首地址 while (n) // 逐個復(fù)制數(shù)組元素 *destptr++ = *srcptr++。 alist = new T[n]。 // 將元素個數(shù)賦值給變量 size alist = new T[size]。 void Resize(int sz)。 ArrayT operator= (const ArrayT rhs)。 void Error(ErrorType error,int badIndex=0) const。 endif // NULL enum ErrorType { invalidArraySize, memoryAllocationError, indexOutOfRange }。 ? 動態(tài)數(shù)組由一系列位置連續(xù)的，任意數(shù)量相同類型的元素組成。在線性群體中，又可按照訪問元素的不同方法分為 直接訪問 、 順序訪問 和 索引訪問 。群體可以分為兩個大類： 線性群體 和 非線性群體 。 cout The student id is ().id endl。 (3)。 // 將 x值存入 item } 11 int main() { Student g= {1000, 23}。 exit(1)。 // 默認形式（無形參）的構(gòu)造函數(shù) T GetElem(void)。 //平均分 }。 } 函 數(shù) 模 板 7 類模板的作用 使用類模板使用戶可以為類聲明一種模式，使得類中的某些數(shù)據(jù)成員、某些成員函數(shù)的參數(shù)、某些成員函數(shù)的返回值，能取任意類型（包括基本類型的和用戶自定義類型）。 coutabs(d)endl。 templatetypename T T abs(T x) { return x0?x:x。 ? 聲明方法： template typename 標識符 函數(shù)聲明 函 數(shù) 模 板 5 求絕對值函數(shù)的模板 includeiostream using namespace std。 coutabs(n)endl。 ? 當類型參數(shù)的含義確定后，編譯器將以函數(shù)模板為樣板，生成一個函數(shù)： int abs(int x) { return x0?x:x。 //學號 float gpa。 // 用于標記 item是否已被存入內(nèi)容 public: Store(void)。 // 默認形式構(gòu)造函數(shù)的實現(xiàn) template class T StoreT::Store(void): haveValue(0) {} 10 template class T // 提取數(shù)據(jù)函數(shù)的實現(xiàn) T StoreT::GetElem(void) { // 如果試圖提取未初始化的數(shù)據(jù)，則終止程序 if (haveValue == 0) { cout No item present! endl。 // 將 haveValue 置為 TRUE，表示item中已存入數(shù)值 item = x。 Storedouble D。 (g)。 //輸出對象 D的數(shù)據(jù)成員 // 由于 D未經(jīng)初始化 ,在執(zhí)行函數(shù) ()時出錯 } 12 13 第二部分 — 群 體數(shù)據(jù) ? 線性群體 – 線性群體的概念 –