1、AB第九章 群體類和群體數(shù)據(jù)的組織,C+語言程序設(shè)計(jì),本章主要內(nèi)容,模板 群體類 群體數(shù)據(jù)的組織,第一部分模板,函數(shù)模板 類模板,函數(shù)模板,函數(shù)模板可以用來創(chuàng)建一個(gè)通用功能的函數(shù)，以支持多種不同形參，進(jìn)一步簡(jiǎn)化重載函數(shù)的函數(shù)體設(shè)計(jì)。 聲明方法： template 函數(shù)聲明,函 數(shù) 模 板,求絕對(duì)值函數(shù)的模板,#include using namespace std; template T abs(T x) return x0?-x:x; int main() int n=-5; double d=-5.5; coutabs(n)endl; coutabs(d)endl; ,函 數(shù) 模 板,運(yùn)行

2、結(jié)果： 5 5.5,求絕對(duì)值函數(shù)的模板分析,編譯器從調(diào)用abs()時(shí)實(shí)參的類型，推導(dǎo)出函數(shù)模板的類型參數(shù)。例如，對(duì)于調(diào)用表達(dá)式abs(n)，由于實(shí)參n為int型，所以推導(dǎo)出模板中類型參數(shù)T為int。 當(dāng)類型參數(shù)的含義確定后，編譯器將以函數(shù)模板為樣板，生成一個(gè)函數(shù)：int abs(int x) return x0?-x:x; ,函 數(shù) 模 板,類模板的作用,使用類模板使用戶可以為類聲明一種模式，使得類中的某些數(shù)據(jù)成員、某些成員函數(shù)的參數(shù)、某些成員函數(shù)的返回值，能取任意類型（包括基本類型的和用戶自定義類型）。,類 模 板,類模板的聲明,類模板： template class 類名 類成員聲明 如果

3、需要在類模板以外定義其成員函數(shù)，則要采用以下的形式： template 類型名 類名:函數(shù)名（參數(shù)表）,類 模 板,例9-2 類模板應(yīng)用舉例,#include #include using namespace std; / 結(jié)構(gòu)體Student struct Student int id; /學(xué)號(hào) float gpa; /平均分 ;,類 模 板,template /類模板：實(shí)現(xiàn)對(duì)任意類型數(shù)據(jù)進(jìn)行存取 class Store private: T item; / 用于存放任意類型的數(shù)據(jù) int haveValue; / 用于標(biāo)記item是否已被存入內(nèi)容 public: Store(void);

4、/ 默認(rèn)形式（無形參）的構(gòu)造函數(shù) T GetElem(void); /提取數(shù)據(jù)函數(shù) void PutElem(T x); /存入數(shù)據(jù)函數(shù) ; / 默認(rèn)形式構(gòu)造函數(shù)的實(shí)現(xiàn) template Store:Store(void): haveValue(0) ,10,template / 提取數(shù)據(jù)函數(shù)的實(shí)現(xiàn) T Store:GetElem(void) / 如果試圖提取未初始化的數(shù)據(jù)，則終止程序 if (haveValue = 0) cout / 存入數(shù)據(jù)函數(shù)的實(shí)現(xiàn) void Store:PutElem(T x) haveValue+; / 將haveValue 置為 TRUE，表示item中已存入數(shù)值

5、 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 student id is S3.GetElem().id endl; cout Retrieving object D ; cout D.GetElem() endl; /輸出對(duì)象D的數(shù)據(jù)成員 / 由于D未經(jīng)初始化,在執(zhí)行函數(shù)D.

6、GetElement()時(shí)出錯(cuò) ,12,第二部分群體數(shù)據(jù),線性群體 線性群體的概念 直接訪問群體-數(shù)組類 順序訪問群體-鏈表類 棧類 隊(duì)列類,群體的概念,群體是指由多個(gè)數(shù)據(jù)元素組成的集合體。群體可以分為兩個(gè)大類：線性群體和非線性群體。 線性群體中的元素按位置排列有序，可以區(qū)分為第一個(gè)元素、第二個(gè)元素等。 非線性群體不用位置順序來標(biāo)識(shí)元素。,線性群體的概念,線性群體中的元素次序與其位置關(guān)系是對(duì)應(yīng)的。在線性群體中，又可按照訪問元素的不同方法分為直接訪問、順序訪問和索引訪問。 在本章我們只介紹直接訪問和順序訪問。,數(shù)組,靜態(tài)數(shù)組是具有固定元素個(gè)數(shù)的群體，其中的元素可以通過下標(biāo)直接訪問。 缺點(diǎn)：大小在

7、編譯時(shí)就已經(jīng)確定，在運(yùn)行時(shí)無法修改。 動(dòng)態(tài)數(shù)組由一系列位置連續(xù)的，任意數(shù)量相同類型的元素組成。 優(yōu)點(diǎn)：其元素個(gè)數(shù)可在程序運(yùn)行時(shí)改變。 動(dòng)態(tài)數(shù)組類模板：例9-3（9_3.h）,直接訪問的線性群體,#ifndef ARRAY_CLASS #define ARRAY_CLASS using namespace std; #include #include #ifndef NULL const int NULL = 0; #endif / NULL enum ErrorType invalidArraySize, memoryAllocationError, indexOutOfRange ; cha

8、r *errorMsg = Invalid array size, Memory allocation error, Invalid index: ;,動(dòng)態(tài)數(shù)組類模板程序,17,template class Array private: T* alist; int size; void Error(ErrorType error,int badIndex=0) const; public: Array(int sz = 50); Array(const Array,18,數(shù)組類模板的構(gòu)造函數(shù),/ 構(gòu)造函數(shù) template Array:Array(int sz) if (sz = 0) /sz

9、為數(shù)組大?。ㄔ貍€(gè)數(shù)），若小于0，則輸出錯(cuò)誤信息 Error(invalidArraySize); size = sz; / 將元素個(gè)數(shù)賦值給變量size alist = new Tsize; /動(dòng)態(tài)分配size個(gè)T類型的元素空間 if (alist = NULL) /如果分配內(nèi)存不成功，輸出錯(cuò)誤信息 Error(memoryAllocationError); ,直接訪問的線性群體,數(shù)組類的拷貝構(gòu)造函數(shù),template Array:Array(const Array ,直接訪問的線性群體,淺拷貝,int main() Array A(10); . Array B(A); . ,templat

10、e Array:Array( const Array ,深拷貝,數(shù)組類的重載=運(yùn)算符函數(shù),template Array ,直接訪問的線性群體,數(shù)組類的重載下標(biāo)操作符函數(shù),template T ,直接訪問的線性群體,為什么有的函數(shù)返回引用,如果一個(gè)函數(shù)的返回值是一個(gè)對(duì)象的值，它就被認(rèn)為是一個(gè)常量，不能成為左值。 如果返回值為引用。由于引用是對(duì)象的別名，所以通過引用當(dāng)然可以改變對(duì)象的值。,直接訪問的線性群體,重載指針轉(zhuǎn)換操作符,template Array:operator T* (void) const / 返回當(dāng)前對(duì)象中私有數(shù)組的首地址 return alist; ,直接訪問的線性群體,指針轉(zhuǎn)

11、換運(yùn)算符的作用,#include using namespace std; int main() int a10; void read(int *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; ,直接訪問的線性群體,Array類的應(yīng)用,例9-4求范圍2N中的質(zhì)數(shù)，N在程序運(yùn)行時(shí)由鍵盤輸入。,直接訪問的線

12、性群體,#include #include #include 9_3.h using namespace std; int main() Array A(10); int n; int primecount = 0, i, j; cout = 2 as upper limit for prime numbers: ; cin n; Aprimecount+ = 2; / 2是一個(gè)質(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

13、 endl; cout endl; ,29,鏈表,鏈表是一種動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)，可以用來表示順序訪問的線性群體。 鏈表是由系列結(jié)點(diǎn)組成的，結(jié)點(diǎn)可以在運(yùn)行時(shí)動(dòng)態(tài)生成。 每一個(gè)結(jié)點(diǎn)包括數(shù)據(jù)域和指向鏈表中下一個(gè)結(jié)點(diǎn)的指針（即下一個(gè)結(jié)點(diǎn)的地址）。如果鏈表每個(gè)結(jié)點(diǎn)中只有一個(gè)指向后繼結(jié)點(diǎn)的指針，則該鏈表稱為單鏈表。,順序訪問的線性群體,單鏈表,順序訪問的線性群體,單鏈表的結(jié)點(diǎn)類模板,template class Node private: Node *next; public: T data; Node(const T,順序訪問的線性群體,在結(jié)點(diǎn)之后插入一個(gè)結(jié)點(diǎn),data1,p,data,template vo

14、id Node:InsertAfter(Node *p) /p節(jié)點(diǎn)指針域指向當(dāng)前節(jié)點(diǎn)的后繼節(jié)點(diǎn) p-next = next; next = p; /當(dāng)前節(jié)點(diǎn)的指針域指向p ,順序訪問的線性群體,刪除結(jié)點(diǎn)之后的結(jié)點(diǎn),順序訪問的線性群體,data1,Node *Node:DeleteAfter(void) Node *tempPtr = next; if (next = NULL) return NULL; next = tempPtr-next; return tempPtr; ,tempPtr,鏈表的基本操作,生成結(jié)點(diǎn) 插入結(jié)點(diǎn) 查找結(jié)點(diǎn) 刪除結(jié)點(diǎn) 遍歷鏈表 清空鏈表,順序訪問的線性群體,鏈表

15、類模板(例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; int size; int position; Node *GetNode(cons

16、t T,37,public: LinkedList(void); LinkedList(const LinkedList,38,void InsertFront(const T #endif / LINKEDLIST_CLASS,39,鏈表類應(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=0;i item; Link.InsertFront(item); ,順序訪問的線性群體,cout key

17、; Link.Reset();,41,while (!Link.EndOfList() if(Link.Data() = key) Link.DeleteAt(); Link.Next(); cout List: ; Link.Reset(); while(!Link.EndOfList() cout Link.Data() ; Link.Next(); cout endl; ,42,特殊的線性群體棧,棧是只能從一端訪問的線性群體，可以訪問的這一端稱棧頂，另一端稱棧底。,特殊的線性群體棧,棧的應(yīng)用舉例函數(shù)調(diào)用,特殊的線性群體棧,棧的應(yīng)用舉例表達(dá)式處理,特殊的線性群體棧,棧的基本狀態(tài),棧空 棧中

18、沒有元素 棧滿 棧中元素個(gè)數(shù)達(dá)到上限 一般狀態(tài) 棧中有元素，但未達(dá)到棧滿狀態(tài),特殊的線性群體棧,47,棧的基本操作,初始化 入棧 出棧 清空棧 訪問棧頂元素 檢測(cè)棧的狀態(tài)（滿、空）,特殊的線性群體棧,棧類模板(例9-8),特殊的線性群體棧,/9-8.h #ifndef STACK_CLASS #define STACK_CLASS #include #include using namespace std; const int MaxStackSize = 50; template class Stack private: T stacklistMaxStackSize; int top;,p

19、ublic: Stack (void); void Push (const T /類的實(shí)現(xiàn)略,棧的應(yīng)用,例9.9 一個(gè)簡(jiǎn)單的整數(shù)計(jì)算器 實(shí)現(xiàn)一個(gè)簡(jiǎn)單的整數(shù)計(jì)算器，能夠進(jìn)行加、減、乘、除和乘方運(yùn)算。使用時(shí)算式采用后綴輸入法，每個(gè)操作數(shù)、操作符之間都以空白符分隔。例如，若要計(jì)算3+5則輸入3 5 +。乘方運(yùn)算符用表示。每次運(yùn)算在前次結(jié)果基礎(chǔ)上進(jìn)行，若要將前次運(yùn)算結(jié)果清除，可鍵入c。當(dāng)鍵入q時(shí)程序結(jié)束。 9-9.h 9-9.cpp,特殊的線性群體棧,/9_9.h #include #include #include #include using namespace std; enum Boolean

20、 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 Calculator:GetTwoOperands(int ,52,void Calculator:Compute(char op) Boolean result; int operand1, operand2; result = GetTwoOperands(op

21、erand1, operand2); if (result) switch(op) case +: S.Push(operand2+operand1); break; case -: S.Push(operand2-operand1); break; case *: S.Push(operand2*operand1); break; case /: if (operand1 = 0) cerr Divide by 0! endl; S.ClearStack(); else S.Push(operand2/operand1); break; case : S.Push(pow(operand2,

22、operand1); break; cout=S.Peek() ; else S.ClearStack(); ,53,void Calculator:Run(void) char 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); br

23、eak; ,54,void Calculator:Clear(void) S.ClearStack(); /9_9.cpp #include 9-9.h int main() Calculator CALC; CALC.Run(); ,55,特殊的線性群體隊(duì)列,隊(duì)列是只能向一端添加元素，從另一端刪除元素的線性群體,隊(duì)列的基本狀態(tài),隊(duì)空 隊(duì)列中沒有元素 隊(duì)滿 隊(duì)列中元素個(gè)數(shù)達(dá)到上限 一般狀態(tài) 隊(duì)列中有元素，但未達(dá)到隊(duì)滿狀態(tài),特殊的線性群體隊(duì)列,元素移動(dòng)方向,元素移動(dòng)方向,58,循環(huán)隊(duì)列,在想象中將數(shù)組彎曲成環(huán)形，元素出隊(duì)時(shí)，后繼元素不移動(dòng)，每當(dāng)隊(duì)尾達(dá)到數(shù)組最后一個(gè)元素時(shí)，便再回到數(shù)組開頭。,特殊

24、的線性群體隊(duì)列,60,例9-10 隊(duì)列類模板,特殊的線性群體隊(duì)列,#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ù)的實(shí)現(xiàn)略,第三部分群體數(shù)據(jù)的組織,插入排序 選擇排序 交換排序 順序查找 折半查找,排序

25、（sorting）,排序是計(jì)算機(jī)程序設(shè)計(jì)中的一種重要操作，它的功能是將一個(gè)數(shù)據(jù)元素的任意序列，重新排列成一個(gè)按關(guān)鍵字有序的序列。 數(shù)據(jù)元素：數(shù)據(jù)的基本單位。在計(jì)算機(jī)中通常作為一個(gè)整體進(jìn)行考慮。一個(gè)數(shù)據(jù)元素可由若干數(shù)據(jù)項(xiàng)組成。 關(guān)鍵字：數(shù)據(jù)元素中某個(gè)數(shù)據(jù)項(xiàng)的值，用它可以標(biāo)識(shí)（識(shí)別）一個(gè)數(shù)據(jù)元素。 在排序過程中需要完成兩種基本操作： 比較兩個(gè)數(shù)的大小 調(diào)整元素在序列中的位置,群體數(shù)據(jù)的組織,內(nèi)部排序與外部排序,內(nèi)部排序：待排序的數(shù)據(jù)元素存放在計(jì)算機(jī)內(nèi)存中進(jìn)行的排序過程。 外部排序：待排序的數(shù)據(jù)元素?cái)?shù)量很大，以致內(nèi)存存中一次不能容納全部數(shù)據(jù)，在排序過程中尚需對(duì)外存進(jìn)行訪問的排序過程。,群體數(shù)據(jù)的組織

26、,內(nèi)部排序方法,插入排序 選擇排序 交換排序,群體數(shù)據(jù)的組織,插入排序的基本思想,每一步將一個(gè)待排序元素按其關(guān)鍵字值的大小插入到已排序序列的適當(dāng)位置上，直到待排序元素插入完為止。,初始狀態(tài)： 5 4 10 20 12 3,直接插入排序,在插入排序過程中，由于尋找插入位置的方法不同又可以分為不同的插入排序算法，這里我們只介紹最簡(jiǎn)單的直接插入排序算法。 例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 ,直接插入排序函數(shù)模板（9_11.

27、h）,68,選擇排序的基本思想,每次從待排序序列中選擇一個(gè)關(guān)鍵字最小的元素，（當(dāng)需要按關(guān)鍵字升序排列時(shí)），順序排在已排序序列的最后，直至全部排完。,3 4 10 20 12 5,3 4 10 20 12 5,第 i 次選擇后，將選出的那個(gè)記錄與第 i 個(gè)記錄做交換。,直接選擇排序,在選擇類排序方法中，從待排序序列中選擇元素的方法不同，又分為不同的選擇排序方法，其中最簡(jiǎn)單的是通過順序比較找出待排序序列中的最小元素，稱為直接選擇排序。 例9-12 直接選擇排序函數(shù)模板（9-12.h）,群體數(shù)據(jù)的組織,template void Swap (T ,直接選擇排序函數(shù)模板（9-12.h）,71,交換排序

28、的基本思想,兩兩比較待排序序列中的元素，并交換不滿足順序要求的各對(duì)元素，直到全部滿足順序要求為止。,群體數(shù)據(jù)的組織,最簡(jiǎn)單的交換排序方法 起泡排序,對(duì)具有n個(gè)元素的序列按升序進(jìn)行起泡排序的步驟： 首先將第一個(gè)元素與第二個(gè)元素進(jìn)行比較，若為逆序，則將兩元素交換。然后比較第二、第三個(gè)元素，依次類推，直到第n-1和第n個(gè)元素進(jìn)行了比較和交換。此過程稱為第一趟起泡排序。經(jīng)過第一趟，最大的元素便被交換到第n個(gè)位置。 對(duì)前n-1個(gè)元素進(jìn)行第二趟起泡排序，將其中最大元素交換到第n-1個(gè)位置。 如此繼續(xù)，直到某一趟排序未發(fā)生任何交換時(shí)，排序完畢。對(duì)n個(gè)元素的序列，起泡排序最多需要進(jìn)行n-1趟。,群體數(shù)據(jù)的組織,起泡排序舉例,對(duì)整數(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é)果,小