第九章 群體類和群體數(shù)據(jù)的組織,C+語言程序設計,2,本章主要內容,模板 群體類 群體數(shù)據(jù)的組織,3,第一部分模板,函數(shù)模板 類模板,4,函數(shù)模板,函數(shù)模板可以用來創(chuàng)建一個通用功能的函數(shù)，以支持多種不同形參，進一步簡化重載函數(shù)的函數(shù)體設計。 聲明方法： template 函數(shù)聲明,函 數(shù) 模 板,5,求絕對值函數(shù)的模板,#include using namespace std; template T abs(T x) return x<0?-x:x; int main() int n=-5; double d=-5.5; cout<<abs(n)<<endl; cout<<abs(d)<<endl; ,函 數(shù) 模 板,運行結果： 5 5.5,6,求絕對值函數(shù)的模板分析,編譯器從調用abs()時實參的類型，推導出函數(shù)模板的類型參數(shù)。例如，對于調用表達式abs(n)，由于實參n為int型，所以推導出模板中類型參數(shù)T為int。 當類型參數(shù)的含義確定后，編譯器將以函數(shù)模板為樣板，生成一個函數(shù)：int abs(int x) return x<0?-x:x; ,函 數(shù) 模 板,7,類模板的作用,使用類模板使用戶可以為類聲明一種模式，使得類中的某些數(shù)據(jù)成員、某些成員函數(shù)的參數(shù)、某些成員函數(shù)的返回值，能取任意類型（包括基本類型的和用戶自定義類型）。,類 模 板,8,類模板的聲明,類模板： template class 類名 類成員聲明 如果需要在類模板以外定義其成員函數(shù)，則要采用以下的形式： template 類型名 類名:函數(shù)名（參數(shù)表）,類 模 板,9,例9-2 類模板應用舉例,#include #include using namespace std; / 結構體Student struct Student int id; /學號 float gpa; /平均分 ;,類 模 板,template /類模板：實現(xiàn)對任意類型數(shù)據(jù)進行存取 class Store private: T item; / 用于存放任意類型的數(shù)據(jù) int haveValue; / 用于標記item是否已被存入內容 public: Store(void); / 默認形式（無形參）的構造函數(shù) T GetElem(void); /提取數(shù)據(jù)函數(shù) void PutElem(T x); /存入數(shù)據(jù)函數(shù) ; / 默認形式構造函數(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 置為 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 student id is << S3.GetElem().id << endl; cout << Retrieving object D ; cout << D.GetElem() << endl; /輸出對象D的數(shù)據(jù)成員 / 由于D未經初始化,在執(zhí)行函數(shù)D.GetElement()時出錯 ,12,13,第二部分群體數(shù)據(jù),線性群體 線性群體的概念 直接訪問群體-數(shù)組類 順序訪問群體-鏈表類 棧類 隊列類,14,群體的概念,群體是指由多個數(shù)據(jù)元素組成的集合體。群體可以分為兩個大類：線性群體和非線性群體。 線性群體中的元素按位置排列有序，可以區(qū)分為第一個元素、第二個元素等。 非線性群體不用位置順序來標識元素。,15,線性群體的概念,線性群體中的元素次序與其位置關系是對應的。在線性群體中，又可按照訪問元素的不同方法分為直接訪問、順序訪問和索引訪問。 在本章我們只介紹直接訪問和順序訪問。,16,數(shù)組,靜態(tài)數(shù)組是具有固定元素個數(shù)的群體，其中的元素可以通過下標直接訪問。 缺點：大小在編譯時就已經確定，在運行時無法修改。 動態(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, 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 Error(ErrorType error,int badIndex=0) const; public: Array(int sz = 50); Array(const Array,18,19,數(shù)組類模板的構造函數(shù),/ 構造函數(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 (alist = NULL) /如果分配內存不成功，輸出錯誤信息 Error(memoryAllocationError); ,直接訪問的線性群體,20,數(shù)組類的拷貝構造函數(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ù)組類的重載下標操作符函數(shù),template T ,直接訪問的線性群體,25,為什么有的函數(shù)返回引用,如果一個函數(shù)的返回值是一個對象的值，它就被認為是一個常量，不能成為左值。 如果返回值為引用。由于引用是對象的別名，所以通過引用當然可以改變對象的值。,直接訪問的線性群體,26,重載指針轉換操作符,template Array:operator T* (void) const / 返回當前對象中私有數(shù)組的首地址 return alist; ,直接訪問的線性群體,27,指針轉換運算符的作用,#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; ,直接訪問的線性群體,28,Array類的應用,例9-4求范圍2N中的質數(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是一個質數(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,30,鏈表,鏈表是一種動態(tài)數(shù)據(jù)結構，可以用來表示順序訪問的線性群體。 鏈表是由系列結點組成的，結點可以在運行時動態(tài)生成。 每一個結點包括數(shù)據(jù)域和指向鏈表中下一個結點的指針（即下一個結點的地址）。如果鏈表每個結點中只有一個指向后繼結點的指針，則該鏈表稱為單鏈表。,順序訪問的線性群體,31,單鏈表,順序訪問的線性群體,32,單鏈表的結點類模板,template class Node private: Node *next; public: T data; Node(const T,順序訪問的線性群體,33,在結點之后插入一個結點,data1,p,data,template void Node:InsertAfter(Node *p) /p節(jié)點指針域指向當前節(jié)點的后繼節(jié)點 p-next = next; next = p; /當前節(jié)點的指針域指向p ,順序訪問的線性群體,34,刪除結點之后的結點,順序訪問的線性群體,data1,Node *Node:DeleteAfter(void) Node *tempPtr = next; if (next = NULL) return NULL; next = tempPtr-next; return tempPtr; ,tempPtr,35,鏈表的基本操作,生成結點 插入結點 查找結點 刪除結點 遍歷鏈表 清空鏈表,順序訪問的線性群體,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; 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,鏈表類應用舉例(例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; 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,特殊的線性群體棧,棧是只能從一端訪問的線性群體，可以訪問的這一端稱棧頂，另一端稱棧底。,特殊的線性群體棧,44,棧的應用舉例函數(shù)調用,特殊的線性群體棧,45,棧的應用舉例表達式處理,特殊的線性群體棧,46,棧的基本狀態(tài),?？?棧中沒有元素 棧滿 棧中元素個數(shù)達到上限 一般狀態(tài) 棧中有元素，但未達到棧滿狀態(tài),特殊的線性群體棧,47,48,棧的基本操作,初始化 入棧 出棧 清空棧 訪問棧頂元素 檢測棧的狀態(tài)（滿、空）,特殊的線性群體棧,49,棧類模板(例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;,public: Stack (void); void Push (const T /類的實現(xiàn)略,50,棧的應用,例9.9 一個簡單的整數(shù)計算器 實現(xiàn)一個簡單的整數(shù)計算器，能夠進行加、減、乘、除和乘方運算。使用時算式采用后綴輸入法，每個操作數(shù)、操作符之間都以空白符分隔。例如，若要計算3+5則輸入3 5 +。乘方運算符用表示。每次運算在前次結果基礎上進行，若要將前次運算結果清除，可鍵入c。當鍵入q時程序結束。 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 ,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(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,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); 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ù)達到上限 一般狀態(tài) 隊列中有元素，但未達到隊滿狀態(tài),特殊的線性群體隊列,元素移動方向,元素移動方向,58,59,循環(huán)隊列,在想象中將數(shù)組彎曲成環(huán)形，元素出隊時，后繼元素不移動，每當隊尾達到數(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, count; T qlistMaxQSize;,public: Queue (void); void QInsert(const T /成員函數(shù)的實現(xiàn)略,62,第三部分群體數(shù)據(jù)的組織,插入排序 選擇排序 交換排序 順序查找 折半查找,63,排序（sorting）,排序是計算機程序設計中的一種重要操作，它的功能是將一個數(shù)據(jù)元素的任意序列，重新排列成一個按關鍵字有序的序列。 數(shù)據(jù)元素：數(shù)據(jù)的基本單位。在計算機中通常作為一個整體進行考慮。一個數(shù)據(jù)元素可由若干數(shù)據(jù)項組成。 關鍵字：數(shù)據(jù)元素中某個數(shù)據(jù)項的值，用它可以標識（識別）一個數(shù)據(jù)元素。 在排序過程中需要完成兩種基本操作： 比較兩個數(shù)的大小 調整元素在序列中的位置,群體數(shù)據(jù)的組織,64,內部排序與外部排序,內部排序：待排序的數(shù)據(jù)元素存放在計算機內存中進行的排序過程。 外部排序：待排序的數(shù)據(jù)元素數(shù)量很大，以致內存存中一次不能容納全部數(shù)據(jù)，在排序過程中尚需對外存進行訪問的排序過程。,群體數(shù)據(jù)的組織,65,內部排序方法,插入排序 選擇排序 交換排序,群體數(shù)據(jù)的組織,66,插入排序的基本思想,每一步將一個待排序元素按其關鍵字值的大小插入到已排序序列的適當位置上，直到待排序元素插入完為止。,初始狀態(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 ,直接插入排序函數(shù)模板（9_11.h）,68,69,選擇排序的基本思想,每次從待排序序列中選擇一個關鍵字最小的元素，（當需要按關鍵字升序排列時），順序排在已排序序列的最后，直至全部排完。,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 ,直接選擇排序函數(shù)模板（9-12.h）,71,72,交換排序的基本思想,兩兩比較待排序序列中的元素，并交換不滿足順序要求的各對元素，直到全部滿足順序要求為止。,群體數(shù)據(jù)的組織,73,最簡單的交換排序方法 起泡排序,對具有n個元素的序列按升序進行起泡排序的步驟： 首先將第一個元素與第二個元素進行比較，若為逆序，則將兩元素交換。然后比較第二、第三個元素，依次類推，直到第n-1和第n個元素進行了比較和交換。此過程稱為第一趟起泡排序。經過第一趟，最大的元素便被交換到第n個位置。 對前n-1個元素進行第二趟起泡排序，將其中最大元素交換到第n-1個位置。 如此繼續(xù)，直到某一趟排序未發(fā)生任何交換時，排序完畢。對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),第一趟結果,第二趟結果,第三趟結果,第四趟結果,小的逐漸上升,每趟沉下一個最大的,群體數(shù)據(jù)的組織,75,例9-13 起泡排序函數(shù)模板,template 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,順序查找,其基本思想 從序列的首元素開始，逐個元素與待查找的關鍵字進行比較，直到找到相等的。若整個序列中沒有與待查找關鍵字相等的元素，就是查找不成功。 順序查找函數(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,折半查找的基本思想,對于已按關鍵字排序的序列，經過一次比較，可將序列分割成兩部分，然后只在有可能包含待查元素的一部分中繼續(xù)查找，并根據(jù)試探結果繼續(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ù)的組織,