3、： template class 類名 類成員聲明 如果需要在類模板以外定義其成員函數(shù)，則要采用以下的形式： template 類型名 類名::函數(shù)名（參數(shù)表）,類 模 板,,9,例9-2 類模板應(yīng)用舉例,#include #include using namespace std; // 結(jié)構(gòu)體Student struct Student int id; //學(xué)號 float gpa; //平均分 ;,類 模 板,template //類模板：實現(xiàn)對任意類型數(shù)據(jù)進(jìn)行存取 class Store private: T item; // 用于存放任意類型的數(shù)據(jù) int h
4、aveValue; // 用于標(biāo)記item是否已被存入內(nèi)容 public: Store(void); // 默認(rèn)形式（無形參）的構(gòu)造函數(shù) T GetElem(void); //提取數(shù)據(jù)函數(shù) void PutElem(T x); //存入數(shù)據(jù)函數(shù) ; // 默認(rèn)形式構(gòu)造函數(shù)的實現(xiàn) template Store::Store(void): haveValue(0) ,10,template // 提取數(shù)據(jù)函數(shù)的實現(xiàn) T Store::GetElem(void) // 如果試圖提取未初始化的數(shù)據(jù)，則終止程序 if (haveValue == 0) cout /
5、/ 存入數(shù)據(jù)函數(shù)的實現(xiàn) void Store::PutElem(T x) haveValue++; // 將haveValue 置為 TRUE，表示item中已存入數(shù)值 item = x; // 將x值存入item ,11,int main() Student g= 1000, 23; Store S1, S2; Store S3; Store D; S1.PutElem(3); S2.PutElem(-7); cout << S1.GetElem() << << S2.GetElem() << endl; S3.PutElem(g); cout << The st
6、udent id is << S3.GetElem().id << endl; cout << Retrieving object D ; cout << D.GetElem() << endl; //輸出對象D的數(shù)據(jù)成員 // 由于D未經(jīng)初始化,在執(zhí)行函數(shù)D.GetElement()時出錯 ,12,13,第二部分群體數(shù)據(jù),線性群體 線性群體的概念 直接訪問群體--數(shù)組類 順序訪問群體--鏈表類 棧類 隊列類,14,群體的概念,群體是指由多個數(shù)據(jù)元素組成的集合體。群體可以分為兩個大類：線性群體和非線性群體。 線性群體中的元素按位置排列有序，可以區(qū)分為第一個元素、第二個元素等。 非線性群體不用
7、位置順序來標(biāo)識元素。,15,線性群體的概念,線性群體中的元素次序與其位置關(guān)系是對應(yīng)的。在線性群體中，又可按照訪問元素的不同方法分為直接訪問、順序訪問和索引訪問。 在本章我們只介紹直接訪問和順序訪問。,16,數(shù)組,靜態(tài)數(shù)組是具有固定元素個數(shù)的群體，其中的元素可以通過下標(biāo)直接訪問。 缺點：大小在編譯時就已經(jīng)確定，在運行時無法修改。 動態(tài)數(shù)組由一系列位置連續(xù)的，任意數(shù)量相同類型的元素組成。 優(yōu)點：其元素個數(shù)可在程序運行時改變。 動態(tài)數(shù)組類模板：例9-3（9_3.h）,直接訪問的線性群體,#ifndef ARRAY_CLASS #define ARRAY_CLASS using namespace s
8、td; #include #include #ifndef NULL const int NULL = 0; #endif // NULL enum ErrorType invalidArraySize, memoryAllocationError, indexOutOfRange ; char *errorMsg = Invalid array size, Memory allocation error, Invalid index: ;,動態(tài)數(shù)組類模板程序,17,template class Array private: T* alist; int size; void
9、 Error(ErrorType error,int badIndex=0) const; public: Array(int sz = 50); Array(const Array,18,19,數(shù)組類模板的構(gòu)造函數(shù),// 構(gòu)造函數(shù) template Array::Array(int sz) if (sz <= 0) //sz為數(shù)組大?。ㄔ貍€數(shù)），若小于0，則輸出錯誤信息 Error(invalidArraySize); size = sz; // 將元素個數(shù)賦值給變量size alist = new Tsize; //動態(tài)分配size個T類型的元素空間 if (a
10、list == NULL) //如果分配內(nèi)存不成功，輸出錯誤信息 Error(memoryAllocationError); ,直接訪問的線性群體,20,數(shù)組類的拷貝構(gòu)造函數(shù),template Array::Array(const Array ,直接訪問的線性群體,21,淺拷貝,,int main() Array A(10); ...... Array B(A); ...... ,template Array::Array( const Array ,22,深拷貝,23,數(shù)組類的重載=運算符函數(shù),template Array ,直接訪問的線性群體,24,數(shù)組類的重載下標(biāo)操作符函數(shù),t
11、emplate T ,直接訪問的線性群體,25,為什么有的函數(shù)返回引用,如果一個函數(shù)的返回值是一個對象的值，它就被認(rèn)為是一個常量，不能成為左值。 如果返回值為引用。由于引用是對象的別名，所以通過引用當(dāng)然可以改變對象的值。,直接訪問的線性群體,26,重載指針轉(zhuǎn)換操作符,template Array::operator T* (void) const // 返回當(dāng)前對象中私有數(shù)組的首地址 return alist; ,直接訪問的線性群體,27,指針轉(zhuǎn)換運算符的作用,#include using namespace std; int main() int a10; void read(int
12、 *p, int n); read(a, 10); void read(int *p, int n) for (int i=0; ipi; ,int main() Array a(10); void read(int *p, n); read(a, 10); void read(int *p, int n) for (int i=0; ipi; ,,直接訪問的線性群體,28,Array類的應(yīng)用,例9-4求范圍2N中的質(zhì)數(shù)，N在程序運行時由鍵盤輸入。,直接訪問的線性群體,#include #include #include 9_3.h using namespace std; int
13、 main() Array A(10); int n; int primecount = 0, i, j; cout = 2 as upper limit for prime numbers: ; cin n; Aprimecount++ = 2; // 2是一個質(zhì)數(shù) for(i = 3; i i/2) Aprimecount++ = i; for (i = 0; i < primecount; i++) cout << setw(5) << Ai; if ((i+1) % 10 == 0) cout << endl; cout << endl; ,29,3
14、0,鏈表,鏈表是一種動態(tài)數(shù)據(jù)結(jié)構(gòu)，可以用來表示順序訪問的線性群體。 鏈表是由系列結(jié)點組成的，結(jié)點可以在運行時動態(tài)生成。 每一個結(jié)點包括數(shù)據(jù)域和指向鏈表中下一個結(jié)點的指針（即下一個結(jié)點的地址）。如果鏈表每個結(jié)點中只有一個指向后繼結(jié)點的指針，則該鏈表稱為單鏈表。,順序訪問的線性群體,31,單鏈表,順序訪問的線性群體,32,單鏈表的結(jié)點類模板,template class Node private: Node *next; public: T data; Node(const T,順序訪問的線性群體,33,在結(jié)點之后插入一個結(jié)點,data1,,,,p,data,,,,,,template vo
15、id Node::InsertAfter(Node *p) //p節(jié)點指針域指向當(dāng)前節(jié)點的后繼節(jié)點 p-next = next; next = p; //當(dāng)前節(jié)點的指針域指向p ,,順序訪問的線性群體,34,刪除結(jié)點之后的結(jié)點,順序訪問的線性群體,data1,,,,,,,,Node *Node::DeleteAfter(void) Node *tempPtr = next; if (next == NULL) return NULL; next = tempPtr-next; return tempPtr; ,tempPtr,,35,鏈表的基本操作,生成結(jié)點 插入結(jié)點
16、 查找結(jié)點 刪除結(jié)點 遍歷鏈表 清空鏈表,順序訪問的線性群體,36,鏈表類模板(例9-6),//9_6.h #ifndef LINKEDLIST_CLASS #define LINKEDLIST_CLASS #include #include using namespace std; #ifndef NULL const int NULL = 0; #endif // NULL #include 9_5.h,順序訪問的線性群體,template class LinkedList private: Node *front, *rear; Node *prevPtr, *currPtr;
17、int size; int position; Node *GetNode(const T,37,public: LinkedList(void); LinkedList(const LinkedList,38,void InsertFront(const T #endif // LINKEDLIST_CLASS,39,40,鏈表類應(yīng)用舉例(例9-7),#include using namespace std; #include 9_6.h #include 9_6.cpp int main() LinkedList Link; int i, key, item; for (i=
18、0;i item; Link.InsertFront(item); ,順序訪問的線性群體,cout key; Link.Reset();,41,while (!Link.EndOfList()) if(Link.Data() == key) Link.DeleteAt(); Link.Next(); cout << List: ; Link.Reset(); while(!Link.EndOfList()) cout <
19、群體，可以訪問的這一端稱棧頂，另一端稱棧底。,特殊的線性群體棧,44,棧的應(yīng)用舉例函數(shù)調(diào)用,特殊的線性群體棧,45,棧的應(yīng)用舉例表達(dá)式處理,特殊的線性群體棧,46,棧的基本狀態(tài),?？?棧中沒有元素 棧滿 棧中元素個數(shù)達(dá)到上限 一般狀態(tài) 棧中有元素，但未達(dá)到棧滿狀態(tài),特殊的線性群體棧,47,48,棧的基本操作,初始化 入棧 出棧 清空棧 訪問棧頂元素 檢測棧的狀態(tài)（滿、空）,特殊的線性群體棧,49,棧類模板(例9-8),特殊的線性群體棧,//9-8.h #ifndef STACK_CLASS #define STACK_CLASS #include #include using namespac
20、e std; const int MaxStackSize = 50; template class Stack private: T stacklistMaxStackSize; int top;,public: Stack (void); void Push (const T //類的實現(xiàn)略,,50,棧的應(yīng)用,例9.9 一個簡單的整數(shù)計算器 實現(xiàn)一個簡單的整數(shù)計算器，能夠進(jìn)行加、減、乘、除和乘方運算。使用時算式采用后綴輸入法，每個操作數(shù)、操作符之間都以空白符分隔。例如，若要計算3+5則輸入3 5 +。乘方運算符用表示。每次運算在前次結(jié)果基礎(chǔ)上進(jìn)行，若要將前次運算結(jié)果清除，可鍵入
21、c。當(dāng)鍵入q時程序結(jié)束。 9-9.h 9-9.cpp,特殊的線性群體棧,//9_9.h #include #include #include #include using namespace std; enum Boolean False, True; #include 9_8.h class Calculator private: Stack S; void Enter(int num); Boolean GetTwoOperands(int,51,void Calculator::Enter(int num) S.Push(num); Boolean Calculato
22、r::GetTwoOperands(int ,52,void Calculator::Compute(char op) Boolean result; int operand1, operand2; result = GetTwoOperands(operand1, operand2); if (result) switch(op) case +: S.Push(operand2+operand1); break; case -: S.Push(operand2-operand1); break; case *: S.Push(operand
23、2*operand1); break; case /: if (operand1 == 0) cerr << Divide by 0! << endl; S.ClearStack(); else S.Push(operand2/operand1); break; case : S.Push(pow(operand2,operand1)); break; cout<<=<
24、 c20; while(cin c, *c != q) switch(*c) case c: S.ClearStack(); break; case -: if (strlen(c)1) Enter(atoi(c)); else Compute(*c); break; case +: case *: case /: case : Compute(*c); break; default: Enter(atoi(c)); break; ,54,void Calculator::Clear(vo
25、id) S.ClearStack(); //9_9.cpp #include 9-9.h int main() Calculator CALC; CALC.Run(); ,55,56,特殊的線性群體隊列,隊列是只能向一端添加元素，從另一端刪除元素的線性群體,57,隊列的基本狀態(tài),隊空 隊列中沒有元素 隊滿 隊列中元素個數(shù)達(dá)到上限 一般狀態(tài) 隊列中有元素，但未達(dá)到隊滿狀態(tài),特殊的線性群體隊列,,元素移動方向,,元素移動方向,,58,59,循環(huán)隊列,在想象中將數(shù)組彎曲成環(huán)形，元素出隊時，后繼元素不移動，每當(dāng)隊尾達(dá)到數(shù)組最后一個元素時，便再回到數(shù)組開頭。,特殊的線性群體隊列,60,61,例9
26、-10 隊列類模板,特殊的線性群體隊列,#ifndef QUEUE_CLASS #define QUEUE_CLASS #include #include using namespace std; const int MaxQSize = 50; template class Queue private: int front, rear, count; T qlistMaxQSize;,public: Queue (void); void QInsert(const T //成員函數(shù)的實現(xiàn)略,,62,第三部分群體數(shù)據(jù)的組織,插入排序 選擇排序 交換排序 順序查找 折半查找,6
27、3,排序（sorting）,排序是計算機程序設(shè)計中的一種重要操作，它的功能是將一個數(shù)據(jù)元素的任意序列，重新排列成一個按關(guān)鍵字有序的序列。 數(shù)據(jù)元素：數(shù)據(jù)的基本單位。在計算機中通常作為一個整體進(jìn)行考慮。一個數(shù)據(jù)元素可由若干數(shù)據(jù)項組成。 關(guān)鍵字：數(shù)據(jù)元素中某個數(shù)據(jù)項的值，用它可以標(biāo)識（識別）一個數(shù)據(jù)元素。 在排序過程中需要完成兩種基本操作： 比較兩個數(shù)的大小 調(diào)整元素在序列中的位置,群體數(shù)據(jù)的組織,64,內(nèi)部排序與外部排序,內(nèi)部排序：待排序的數(shù)據(jù)元素存放在計算機內(nèi)存中進(jìn)行的排序過程。 外部排序：待排序的數(shù)據(jù)元素數(shù)量很大，以致內(nèi)存存中一次不能容納全部數(shù)據(jù)，在排序過程中尚需對外存進(jìn)行訪問的排序過程。,
28、群體數(shù)據(jù)的組織,65,內(nèi)部排序方法,插入排序 選擇排序 交換排序,群體數(shù)據(jù)的組織,66,插入排序的基本思想,每一步將一個待排序元素按其關(guān)鍵字值的大小插入到已排序序列的適當(dāng)位置上，直到待排序元素插入完為止。,初始狀態(tài)： 5 4 10 20 12 3,67,直接插入排序,在插入排序過程中，由于尋找插入位置的方法不同又可以分為不同的插入排序算法，這里我們只介紹最簡單的直接插入排序算法。 例9-11 直接插入排序函數(shù)模板（9_11.h）,群體數(shù)據(jù)的組織,template void InsertionSort(T A, int n) int i, j; T temp; for (i = 1; i 0
29、 ,直接插入排序函數(shù)模板（9_11.h）,68,69,選擇排序的基本思想,每次從待排序序列中選擇一個關(guān)鍵字最小的元素，（當(dāng)需要按關(guān)鍵字升序排列時），順序排在已排序序列的最后，直至全部排完。,3 4 10 20 12 5,3 4 10 20 12 5,第 i 次選擇后，將選出的那個記錄與第 i 個記錄做交換。,70,直接選擇排序,在選擇類排序方法中，從待排序序列中選擇元素的方法不同，又分為不同的選擇排序方法，其中最簡單的是通過順序比較找出待排序序列中的最小元素，稱為直接選擇排序。 例9-12 直接選擇排序函數(shù)模板（9-12.h）,群體數(shù)據(jù)的組織,template void Swap (T
30、,直接選擇排序函數(shù)模板（9-12.h）,71,72,交換排序的基本思想,兩兩比較待排序序列中的元素，并交換不滿足順序要求的各對元素，直到全部滿足順序要求為止。,群體數(shù)據(jù)的組織,73,,最簡單的交換排序方法 起泡排序,對具有n個元素的序列按升序進(jìn)行起泡排序的步驟： 首先將第一個元素與第二個元素進(jìn)行比較，若為逆序，則將兩元素交換。然后比較第二、第三個元素，依次類推，直到第n-1和第n個元素進(jìn)行了比較和交換。此過程稱為第一趟起泡排序。經(jīng)過第一趟，最大的元素便被交換到第n個位置。 對前n-1個元素進(jìn)行第二趟起泡排序，將其中最大元素交換到第n-1個位置。 如此繼續(xù)，直到某一趟排序未發(fā)生任何交換
31、時，排序完畢。對n個元素的序列，起泡排序最多需要進(jìn)行n-1趟。,群體數(shù)據(jù)的組織,74,起泡排序舉例,對整數(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ù)的組織,75,例9-13 起泡排序函數(shù)模板,template void Swap (T ,template void BubbleSort(T A, int n) int i,j; int lastExchangeIndex; i =
32、 n-1; while (i 0) lastExchangeIndex = 0; for (j = 0; j < i; j++) if (Aj+1 < Aj) Swap(Aj,Aj+1); lastExchangeIndex = j; i = lastExchangeIndex; ,,群體數(shù)據(jù)的組織,76,順序查找,其基本思想 從序列的首元素開始，逐個元素與待查找的關(guān)鍵字進(jìn)行比較，直到找到相等的。若整個序列中沒有與待查找關(guān)鍵字相等的元素，就是查找不成功。 順序查找函數(shù)模板 例9-14,群體數(shù)據(jù)的組織,template int SeqSearch(T li
33、st, int n, T key) for(int i=0;i < n;i++) if (listi == key) return i; return -1; ,順序查找函數(shù)模板,77,78,折半查找的基本思想,對于已按關(guān)鍵字排序的序列，經(jīng)過一次比較，可將序列分割成兩部分，然后只在有可能包含待查元素的一部分中繼續(xù)查找，并根據(jù)試探結(jié)果繼續(xù)分割，逐步縮小查找范圍，直至找到或找不到為止。,群體數(shù)據(jù)的組織,79,折半查找舉例,用折半查找法，在下列序列中查找值為21的元素：,M=INT((L+H)/2)=3,L=M+1=4,M=INT((L+H)/2)=4,80,例10-5 折半查找函數(shù)模板,template int BinSearch(T list, int n, T key) int mid, low, high; T midvalue; low=0; high=n-1; while (low <= high) mid = (low+high)/2; midvalue = listmid; if (key == midvalue) return mid; else if (key < midvalue) high = mid-1; else low = mid+1; return -1; ,群體數(shù)據(jù)的組織,
《C語言程序設(shè)計》第九章：群體類和群體數(shù)據(jù)的組織.ppt
