《《C語言程序設(shè)計》第九章：群體類和群體數(shù)據(jù)的組織.ppt》由會員分享，可在線閱讀，更多相關(guān)《《C語言程序設(shè)計》第九章：群體類和群體數(shù)據(jù)的組織.ppt（80頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、第九章 群體類和群體數(shù)據(jù)的組織,C+語言程序設(shè)計,2,本章主要內(nèi)容,模板 群體類 群體數(shù)據(jù)的組織,3,第一部分模板,函數(shù)模板 類模板,4,函數(shù)模板,函數(shù)模板可以用來創(chuàng)建一個通用功能的函數(shù)，以支持多種不同形參，進(jìn)一步簡化重載函數(shù)的函數(shù)體設(shè)計。 聲明方法： template 函數(shù)聲明,函 數(shù) 模 板,5,求絕對值函數(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ù)

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

3、 類名 類成員聲明 如果需要在類模板以外定義其成員函數(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 haveValue; / 用于標(biāo)記item是否已被存入內(nèi)容 public:

4、 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 / 存入數(shù)據(jù)函數(shù)的實現(xiàn) void Store:PutElem(T x) haveValue+; / 將haveValue 置為 TRU

5、E，表示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 student id is S3.GetElem().id endl; cout Retrieving object D ; cout D.GetElem() endl; /輸出對象D的數(shù)據(jù)成員 / 由于

6、D未經(jīng)初始化,在執(zhí)行函數(shù)D.GetElement()時出錯 ,12,13,第二部分群體數(shù)據(jù),線性群體 線性群體的概念 直接訪問群體-數(shù)組類 順序訪問群體-鏈表類 棧類 隊列類,14,群體的概念,群體是指由多個數(shù)據(jù)元素組成的集合體。群體可以分為兩個大類：線性群體和非線性群體。 線性群體中的元素按位置排列有序，可以區(qū)分為第一個元素、第二個元素等。 非線性群體不用位置順序來標(biāo)識元素。,15,線性群體的概念,線性群體中的元素次序與其位置關(guān)系是對應(yīng)的。在線性群體中，又可按照訪問元素的不同方法分為直接訪問、順序訪問和索引訪問。 在本章我們只介紹直接訪問和順序訪問。,16,數(shù)組,靜態(tài)數(shù)組是具有固定元素個數(shù)的

7、群體，其中的元素可以通過下標(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 std; #include #include #ifndef NULL const int NULL = 0; #endif / NULL enum ErrorType invalidArraySize, memoryAllocationEr

8、ror, indexOutOfRange ; char *errorMsg = Invalid array size, Memory allocation error, Invalid index: ;,動態(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,19,數(shù)組類模板的構(gòu)造函數(shù),/ 構(gòu)造函數(shù) template Array:

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

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

11、nst / 返回當(dāng)前對象中私有數(shù)組的首地址 return alist; ,直接訪問的線性群體,27,指針轉(zhuǎ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; ,直

12、接訪問的線性群體,28,Array類的應(yīng)用,例9-4求范圍2N中的質(zhì)數(shù)，N在程序運行時由鍵盤輸入。,直接訪問的線性群體,#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是一個質(zhì)數(shù) for(i = 3; i i/2) Aprimecount+ = i; for (i = 0; i

13、primecount; i+) cout setw(5) Ai; if (i+1) % 10 = 0) cout endl; cout endl; ,29,30,鏈表,鏈表是一種動態(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

14、data; Node(const T,順序訪問的線性群體,33,在結(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 ,順序訪問的線性群體,34,刪除結(jié)點之后的結(jié)點,順序訪問的線性群體,data1,Node *Node:DeleteAfter(void) Node *tempPtr = next; if (next = NULL) return NULL; next = tempPtr-next; retu

15、rn tempPtr; ,tempPtr,35,鏈表的基本操作,生成結(jié)點 插入結(jié)點 查找結(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 *fron

16、t, *rear; Node *prevPtr, *currPtr; 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

17、; int i, key, item; for (i=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 Link.Data() ; Link.Next(); cout endl; ,42,43,特殊的線性群體棧,棧是只能從一端訪問的線性群體

18、，可以訪問的這一端稱棧頂，另一端稱棧底。,特殊的線性群體棧,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 namespace s

19、td; 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é)果清除，可鍵入c。當(dāng)鍵入q時程序結(jié)束

20、。 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 Calculator:GetTwoOperands(int ,5

21、2,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(operand2*operand1); break; case /: if (operand1 = 0) cerr

22、Divide by 0! endl; S.ClearStack(); else S.Push(operand2/operand1); break; case : S.Push(pow(operand2,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); e

23、lse Compute(*c); break; case +: case *: case /: case : Compute(*c); break; default: Enter(atoi(c); break; ,54,void Calculator:Clear(void) S.ClearStack(); /9_9.cpp #include 9-9.h int main() Calculator CALC; CALC.Run(); ,55,56,特殊的線性群體隊列,隊列是只能向一端添加元素，從另一端刪除元素的線性群體,57,隊列的基本狀態(tài),隊空 隊列中沒有元素 隊滿 隊列中元素個數(shù)達(dá)到上限 一

24、般狀態(tài) 隊列中有元素，但未達(dá)到隊滿狀態(tài),特殊的線性群體隊列,元素移動方向,元素移動方向,58,59,循環(huán)隊列,在想象中將數(shù)組彎曲成環(huán)形，元素出隊時，后繼元素不移動，每當(dāng)隊尾達(dá)到數(shù)組最后一個元素時，便再回到數(shù)組開頭。,特殊的線性群體隊列,60,61,例9-10 隊列類模板,特殊的線性群體隊列,#ifndef QUEUE_CLASS #define QUEUE_CLASS #include #include using namespace std; const int MaxQSize = 50; template class Queue private: int front, rear, cou

25、nt; T qlistMaxQSize;,public: Queue (void); void QInsert(const T /成員函數(shù)的實現(xiàn)略,62,第三部分群體數(shù)據(jù)的組織,插入排序 選擇排序 交換排序 順序查找 折半查找,63,排序（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)整元素在序

26、列中的位置,群體數(shù)據(jù)的組織,64,內(nèi)部排序與外部排序,內(nèi)部排序：待排序的數(shù)據(jù)元素存放在計算機內(nèi)存中進(jìn)行的排序過程。 外部排序：待排序的數(shù)據(jù)元素數(shù)量很大，以致內(nèi)存存中一次不能容納全部數(shù)據(jù)，在排序過程中尚需對外存進(jìn)行訪問的排序過程。,群體數(shù)據(jù)的組織,65,內(nèi)部排序方法,插入排序 選擇排序 交換排序,群體數(shù)據(jù)的組織,66,插入排序的基本思想,每一步將一個待排序元素按其關(guān)鍵字值的大小插入到已排序序列的適當(dāng)位置上，直到待排序元素插入完為止。,初始狀態(tài)： 5 4 10 20 12 3,67,直接插入排序,在插入排序過程中，由于尋找插入位置的方法不同又可以分為不同的插入排序算法，這里我們只介紹最簡單的直接插

27、入排序算法。 例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.h）,68,69,選擇排序的基本思想,每次從待排序序列中選擇一個關(guān)鍵字最小的元素，（當(dāng)需要按關(guān)鍵字升序排列時），順序排在已排序序列的最后，直至全部排完。,3 4 10 20 12 5,3 4 10 20 12 5,第 i 次選擇后，將選出的那個記錄與第 i 個記錄做交換。,70,直接選擇排序,在選擇類排序方法中，從待排序序列中選擇元素的

28、方法不同，又分為不同的選擇排序方法，其中最簡單的是通過順序比較找出待排序序列中的最小元素，稱為直接選擇排序。 例9-12 直接選擇排序函數(shù)模板（9-12.h）,群體數(shù)據(jù)的組織,template void Swap (T ,直接選擇排序函數(shù)模板（9-12.h）,71,72,交換排序的基本思想,兩兩比較待排序序列中的元素，并交換不滿足順序要求的各對元素，直到全部滿足順序要求為止。,群體數(shù)據(jù)的組織,73,最簡單的交換排序方法 起泡排序,對具有n個元素的序列按升序進(jìn)行起泡排序的步驟： 首先將第一個元素與第二個元素進(jìn)行比較，若為逆序，則將兩元素交換。然后比較第二、第三個元素，依次類推，直到第n-1和第n

29、個元素進(jìn)行了比較和交換。此過程稱為第一趟起泡排序。經(jīng)過第一趟，最大的元素便被交換到第n個位置。 對前n-1個元素進(jìn)行第二趟起泡排序，將其中最大元素交換到第n-1個位置。 如此繼續(xù)，直到某一趟排序未發(fā)生任何交換時，排序完畢。對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ù)模板,te

30、mplate void Swap (T ,template void BubbleSort(T A, int n) int i,j; int lastExchangeIndex; i = 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)

31、鍵字相等的元素，就是查找不成功。 順序查找函數(shù)模板 例9-14,群體數(shù)據(jù)的組織,template int SeqSearch(T list, 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=

32、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ù)的組織,