面向對象程序設計(C++)：第9章 群體類和群體數(shù)據(jù)的組織

1、第九章 群體類和群體數(shù)據(jù)的組織目錄9.1 函數(shù)模板與類模板9.2 線性群體9.3 群體數(shù)據(jù)的組織9.4 綜合實例對個人銀行賬戶管理程序的改進9.5 深度探索9.6 小結29.1.1 函數(shù)模板函數(shù)模板可以用來創(chuàng)建一個通用功能的函數(shù)，以支持多種不同形參，進一步簡化重載函數(shù)的函數(shù)體設計。定義方法：template 函數(shù)定義模板參數(shù)表的內(nèi)容類型參數(shù)：class（或typename） 標識符常量參數(shù)：類型說明符 標識符模板參數(shù)：template class 標識符39.1 函數(shù)模板與類模板4求絕對值函數(shù)的模板#include using namespace std;templateT abs(T x)

2、return x 0? -x : x;int main() int n = -5;double d = -5.5;cout abs(n) endl;cout abs(d) endl;return 0;9.1 函數(shù)模板與類模板 9.1.1 函數(shù)模板運行結果：55.5求絕對值函數(shù)的模板分析編譯器從調用abs()時實參的類型，推導出函數(shù)模板的類型參數(shù)。例如，對于調用表達式abs(n)，由于實參n為int型，所以推導出模板中類型參數(shù)T為int。當類型參數(shù)的含義確定后，編譯器將以函數(shù)模板為樣板，生成一個函數(shù)：int abs(int x) return x 0 ? x : x;59.1 函數(shù)模板與類模板

3、9.1.1 函數(shù)模板例9-1函數(shù)模板的示例/9_1.cpp#include using namespace std;template /定義函數(shù)模板void outputArray(const T *array, int count) for (int i = 0; i count; i+)cout arrayi ;cout endl;69.1 函數(shù)模板與類模板 9.1.1 函數(shù)模板例9-1（續(xù)）int main() /主函數(shù)const int A_COUNT = 8, B_COUNT = 8, C_COUNT = 20;int a A_COUNT = 1, 2, 3, 4, 5, 6, 7,

4、 8 ;/定義int數(shù)組double bB_COUNT = 1.1, 2.2, 3.3, 4.4, 5.5, 6.6, 7.7, 8.8 ;/定義double數(shù)組char cC_COUNT = Welcome to see you!;/定義char數(shù)組cout a array contains: endl;outputArray(a, A_COUNT);/調用函數(shù)模板cout b array contains: endl;outputArray(b, B_COUNT);/調用函數(shù)模板cout c array contains: endl;outputArray(c, C_COUNT);/調用函

5、數(shù)模板return 0;79.1 函數(shù)模板與類模板 9.1.1 函數(shù)模板例9-1（續(xù)）運行結果如下：a array contains:1 2 3 4 5 6 7 8b array contains:1.1 2.2 3.3 4.4 5.5 6.6 7.7 8.8 c array contains:W e l c o m e t o s e e y o u !89.1 函數(shù)模板與類模板 9.1.1 函數(shù)模板9.1.2 類模板類模板的作用使用類模板使用戶可以為類聲明一種模式，使得類中的某些數(shù)據(jù)成員、某些成員函數(shù)的參數(shù)、某些成員函數(shù)的返回值，能取任意類型（包括基本類型的和用戶自定義類型）。99.1 函

6、數(shù)模板與類模板類模板的聲明類模板：template class 類名類成員聲明如果需要在類模板以外定義其成員函數(shù)，則要采用以下的形式：template 類型名 類名:函數(shù)名（參數(shù)表）109.1 函數(shù)模板與類模板 9.1.2 類模板例9-2 類模板應用舉例#include #include using namespace std;/ 結構體Studentstruct Student int id; /學號 float gpa; /平均分; 119.1 函數(shù)模板與類模板 9.1.2 類模板例9-2 (續(xù))template class Store /類模板：實現(xiàn)對任意類型數(shù)據(jù)進行存取private:

7、T item;/ item用于存放任意類型的數(shù)據(jù)bool haveValue; / haveValue標記item是否已被存入內(nèi)容public:Store();/ 缺省形式（無形參）的構造函數(shù)T &getElem();/提取數(shù)據(jù)函數(shù)void putElem(const T &x); /存入數(shù)據(jù)函數(shù);/以下實現(xiàn)各成員函數(shù)。template /缺省構造函數(shù)的實現(xiàn) Store:Store(): haveValue(false) 129.1 函數(shù)模板與類模板 9.1.2 類模板13例9-2 (續(xù))template /提取數(shù)據(jù)函數(shù)的實現(xiàn)T &Store:getElem() /如試圖提取未初始化的數(shù)據(jù)，則

8、終止程序if (!haveValue) cout No item present! endl;exit(1);/使程序完全退出，返回到操作系統(tǒng)。return item; / 返回item中存放的數(shù)據(jù) template /存入數(shù)據(jù)函數(shù)的實現(xiàn) void Store:putElem(const T &x) / 將haveValue 置為true，表示item中已存入數(shù)值haveValue = true;item = x;/ 將x值存入item9.1 函數(shù)模板與類模板 9.1.2 類模板14例9-2 (續(xù))int main() Store s1, s2;s1.putElem(3);s2.putElem

9、(-7);cout s1.getElem() s2.getElem() endl;Student g = 1000, 23 ;Store s3;s3.putElem(g); cout The student id is s3.getElem().id endl;Store d;cout Retrieving object D. ;cout d.getElem() endl/由于d未經(jīng)初始化,在執(zhí)行函數(shù)D.getElement()過程中導致程序終止return 0;9.1 函數(shù)模板與類模板 9.1.2 類模板線性群體線性群體的概念直接訪問群體-數(shù)組類順序訪問群體-鏈表類棧類隊列類159.2 線性

10、群體群體的概念群體是指由多個數(shù)據(jù)元素組成的集合體。群體可以分為兩個大類：線性群體和非線性群體。線性群體中的元素按位置排列有序，可以區(qū)分為第一個元素、第二個元素等。非線性群體不用位置順序來標識元素。169.2 線性群體9.2.1 線性群體的概念線性群體中的元素次序與其位置關系是對應的。在線性群體中，又可按照訪問元素的不同方法分為直接訪問、順序訪問和索引訪問。在本章我們只介紹直接訪問和順序訪問。179.2 線性群體第一個元素第二個元素第三個元素最后一個元素9.2.2 直接訪問群體數(shù)組類靜態(tài)數(shù)組是具有固定元素個數(shù)的群體，其中的元素可以通過下標直接訪問。缺點：大小在編譯時就已經(jīng)確定，在運行時無法修改。

11、動態(tài)數(shù)組由一系列位置連續(xù)的，任意數(shù)量相同類型的元素組成。優(yōu)點：其元素個數(shù)可在程序運行時改變。vector就是用類模板實現(xiàn)的動態(tài)數(shù)組。動態(tài)數(shù)組類模板：例9-3（Array.h）189.2 線性群體19例9-3 動態(tài)數(shù)組類模板程序#ifndef ARRAY_H#define ARRAY_H#include template /數(shù)組類模板定義class Array private:T* list;/用于存放動態(tài)分配的數(shù)組內(nèi)存首地址int size;/數(shù)組大?。ㄔ貍€數(shù)）public:Array(int sz = 50);/構造函數(shù)Array(const Array &a);/拷貝構造函數(shù)Array(

12、);/析構函數(shù)Array & operator = (const Array &rhs); /重載=“T & operator (int i); /重載”const T & operator (int i) const;operator T * ();/重載到T*類型的轉換operator const T * () const;int getSize() const;/取數(shù)組的大小void resize(int sz);/修改數(shù)組的大小;9.2 線性群體 9.2.2 直接訪問群體數(shù)組類template Array:Array(int sz) /構造函數(shù)assert(sz = 0);/sz為數(shù)組

13、大小（元素個數(shù)），應當非負size = sz;/ 將元素個數(shù)賦值給變量sizelist = new T size;/動態(tài)分配size個T類型的元素空間template Array:Array() /析構函數(shù)delete list;/拷貝構造函數(shù)template Array:Array(const Array &a) size = a.size; /從對象x取得數(shù)組大小，并賦值給當前對象的成員/為對象申請內(nèi)存并進行出錯檢查list = new Tsize;/ 動態(tài)分配n個T類型的元素空間for (int i = 0; i size; i+) /從對象X復制數(shù)組元素到本對象 listi = a.l

14、isti;209.2 線性群體 9.2.2 直接訪問群體數(shù)組類例9-3（續(xù)）/重載=運算符，將對象rhs賦值給本對象。實現(xiàn)對象之間的整體賦值template Array &Array:operator = (const Array& rhs) if (&rhs != this) /如果本對象中數(shù)組大小與rhs不同，則刪除數(shù)組原有內(nèi)存，然后重新分配if (size != rhs.size) delete list;/刪除數(shù)組原有內(nèi)存size = rhs.size;/設置本對象的數(shù)組大小list = new Tsize;/重新分配n個元素的內(nèi)存/從對象X復制數(shù)組元素到本對象 for (int i

15、= 0; i size; i+)listi = rhs.listi;return *this;/返回當前對象的引用219.2 線性群體 9.2.2 直接訪問群體數(shù)組類例9-3（續(xù)）/重載下標運算符，實現(xiàn)與普通數(shù)組一樣通過下標訪問元素，并且具有越界檢查功能template T &Array:operator (int n) assert(n = 0 & n size);/檢查下標是否越界return listn;/返回下標為n的數(shù)組元素template const T &Array:operator (int n) const assert(n = 0 & n size);/檢查下標是否越界re

16、turn listn;/返回下標為n的數(shù)組元素/重載指針轉換運算符，將Array類的對象名轉換為T類型的指針template Array:operator T * () return list;/返回當前對象中私有數(shù)組的首地址229.2 線性群體 9.2.2 直接訪問群體數(shù)組類例9-3（續(xù)）template Array:operator const T * () const return list;/返回當前對象中私有數(shù)組的首地址/取當前數(shù)組的大小template int Array:getSize() const return size;/ 將數(shù)組大小修改為sztemplate void A

17、rray:resize(int sz) assert(sz = 0);/檢查sz是否非負if (sz = size)/如果指定的大小與原有大小一樣，什么也不做return;T* newList = new T sz;/申請新的數(shù)組內(nèi)存int n = (sz size) ? sz : size;/將sz與size中較小的一個賦值給n/將原有數(shù)組中前n個元素復制到新數(shù)組中for (int i = 0; i n; i+)newListi = listi;delete list;/刪除原數(shù)組list = newList;/ 使list指向新數(shù)組size = sz;/更新size#endif /ARRA

18、Y_H239.2 線性群體 9.2.2 直接訪問群體數(shù)組類例9-3（續(xù)）24數(shù)組類模板的構造函數(shù)/ 構造函數(shù)template Array:Array(int sz) /sz為數(shù)組大?。ㄔ貍€數(shù)），應當非負assert(sz = 0);/ 將元素個數(shù)賦值給變量sizesize = sz;/動態(tài)分配size個T類型的元素空間list = new T size;9.2 線性群體 9.2.2 直接訪問群體數(shù)組類25數(shù)組類模板的拷貝構造函數(shù)/拷貝構造函數(shù)template Array:Array(const Array &a) /從對象x取得數(shù)組大小，并賦值給當前對象的成員size = a.size;/為

19、對象申請內(nèi)存并進行出錯檢查list = new Tsize;/ 動態(tài)分配n個T類型的元素空間/從對象X復制數(shù)組元素到本對象 for (int i = 0; i size; i+)listi = a.listi;9.2 線性群體 9.2.2 直接訪問群體數(shù)組類26淺拷貝9.2 線性群體 9.2.2 直接訪問群體數(shù)組類template Array:Array(const Array& x) size = x.size; list = x.list;int main() Array a(10); . Array b(a); . list sizeaa的數(shù)組元素占用的內(nèi)存拷貝前 list sizeaa

20、的數(shù)組元素占用的內(nèi)存拷貝后 list sizeb27深拷貝9.2 線性群體 9.2.2 直接訪問群體數(shù)組類 list sizeaa的數(shù)組元素占用的內(nèi)存拷貝前 list sizeaa的數(shù)組元素占用的內(nèi)存拷貝后 list sizebb的數(shù)組元素占用的內(nèi)存28數(shù)組類模板的重載=運算符函數(shù)/重載“=”運算符template Array &Array:operator = (const Array& rhs) if (&rhs != this) if (size != rhs.size) delete list;/刪除數(shù)組原有內(nèi)存size = rhs.size;/設置本對象的數(shù)組大小list = new

21、 Tsize;/重新分配n個元素的內(nèi)存/從對象X復制數(shù)組元素到本對象 for (int i = 0; i size; i+)listi = rhs.listi;return *this;/返回當前對象的引用9.2 線性群體 9.2.2 直接訪問群體數(shù)組類29數(shù)組類模板的重載下標操作符函數(shù)template T &Array:operator (int n) assert(n = 0 & n size);/越界檢查return listn; /返回下標為n的數(shù)組元素template const T &Array:operator (int n) const assert(n = 0 & n siz

22、e); /越界檢查return listn; /返回下標為n的數(shù)組元素9.2 線性群體 9.2.2 直接訪問群體數(shù)組類為什么有的函數(shù)返回引用如果一個函數(shù)的返回值是一個對象的值，就不應成為左值。如果返回值為引用。由于引用是對象的別名，通過引用當然可以改變對象的值。309.2 線性群體 9.2.2 直接訪問群體數(shù)組類31重載指針轉換操作符template Array:operator T * () return list;/返回私有數(shù)組的首地址template Array:operator const T * () const return list;/返回私有數(shù)組的首地址9.2 線性群體 9.2

23、.2 直接訪問群體數(shù)組類指針轉換運算符的作用#include using namespace std;void read(int *p, int n) for (int i = 0; i pi;int main() int a10; read(a, 10); return 0;#include Array.h#include using namespace std;void read(int *p, int n) for (int i = 0; i pi;int main() Array a(10); read(a, 10); return 0;329.2 線性群體 9.2.2 直接訪問群體數(shù)

24、組類Array類的應用例9-4求范圍2N中的質數(shù)，N在程序運行時由鍵盤輸入。339.2 線性群體 9.2.2 直接訪問群體數(shù)組類34#include #include #include Array.husing namespace std;int main() Array a(10);/ 用來存放質數(shù)的數(shù)組，初始狀態(tài)有10個元素。int n, count = 0;cout = 2 as upper limit for prime numbers: ;cin n;for (int i = 2; i = n; i+) bool isPrime = true;for (int j = 0; j co

25、unt; j+)if (i % aj = 0) /若i被aj整除，說明i不是質數(shù)isPrime = false; break;if (isPrime) if (count = a.getSize() a.resize(count * 2);acount+ = i;for (int i = 0; i count; i+)cout setw(8) ai;cout endl;return 0;9.2 線性群體 9.2.2 直接訪問群體數(shù)組類例9-4（續(xù)）9.2.3 順序訪問群體鏈表類鏈表是一種動態(tài)數(shù)據(jù)結構，可以用來表示順序訪問的線性群體。鏈表是由系列結點組成的，結點可以在運行時動態(tài)生成。每一個結點包

26、括數(shù)據(jù)域和指向鏈表中下一個結點的指針（即下一個結點的地址）。如果鏈表每個結點中只有一個指向后繼結點的指針，則該鏈表稱為單鏈表。359.2 線性群體36單鏈表9.2 線性群體 9.2.3 順序訪問群體鏈表類 data1 data2 data3 datan NULLheadrear37單鏈表的結點類模板template class Node private: Node *next;public: T data; Node(const T& item,Node* next = 0); void insertAfter(Node *p); Node *deleteAfter(); Node *next

27、Node() const; 9.2 線性群體 9.2.3 順序訪問群體鏈表類38在結點之后插入一個結點9.2 線性群體 9.2.3 順序訪問群體鏈表類 data1 data2 p datatemplate void Node:insertAfter(Node *p) /p節(jié)點指針域指向當前節(jié)點的后繼節(jié)點 p-next = next; next = p; /當前節(jié)點的指針域指向p 39 刪除結點之后的結點9.2 線性群體 9.2.3 順序訪問群體鏈表類 data1 data2 data3tempPtrNode *Node:deleteAfter(void) Node *tempPtr = nex

28、t; if (next = 0) return 0; next = tempPtr-next; return tempPtr; 例9-5結點類模扳/Node.h#ifndef NODE_H#define NODE_H/類模板的定義template class Node private:Node *next;/指向后繼結點的指針public:T data;/數(shù)據(jù)域Node (const T &data, Node *next = 0); /構造函數(shù)void insertAfter(Node *p);/在本結點之后插入一個同類結點p Node *deleteAfter();/刪除本結點的后繼結點，

29、并返回其地址Node *nextNode();/獲取后繼結點的地址const Node *nextNode() const; /獲取后繼結點的地址;409.2 線性群體 9.2.3 順序訪問群體鏈表類/類的實現(xiàn)部分/構造函數(shù)，初始化數(shù)據(jù)和指針成員template Node:Node(const T& data, Node *next/* = 0 */) : data(data), next(next) /返回后繼結點的指針template Node *Node:nextNode() return next;/返回后繼結點的指針template const Node *Node:nextNode

30、() const return next; 419.2 線性群體 9.2.3 順序訪問群體鏈表類例9-5（續(xù)）/在當前結點之后插入一個結點p template void Node:insertAfter(Node *p) p-next = next; /p結點指針域指向當前結點的后繼結點 next = p; /當前結點的指針域指向p /刪除當前結點的后繼結點，并返回其地址template Node *Node:deleteAfter() Node *tempPtr = next;/將欲刪除的結點地址存儲到tempPtr中if (next = 0)/如果當前結點沒有后繼結點，則返回空指針retu

31、rn 0;next = tempPtr-next;/使當前結點的指針域指向tempPtr的后繼結點return tempPtr;/返回被刪除的結點的地址#endif /NODE_H429.2 線性群體 9.2.3 順序訪問群體鏈表類例9-5（續(xù)）鏈表的基本操作生成結點插入結點查找結點刪除結點遍歷鏈表清空鏈表439.2 線性群體 9.2.3 順序訪問群體鏈表類例9-6 鏈表類模板#ifndef LINKEDLIST_H#define LINKEDLIST_H#include Node.htemplate class LinkedList private:/數(shù)據(jù)成員：Node *front, *r

32、earNode *prevPtr, *currPtr; int size;int position;Node *newNode(const T &item,Node *ptrNext=NULL);void freeNode(Node *p);void copy(const LinkedList& L);public:LinkedList();LinkedList(const LinkedList &L); LinkedList();LinkedList & operator = (const LinkedList &L); int getSize() const;bool isEmpty()

33、const;void reset(int pos = 0void next();bool endOfList() const;int currentPosition(void) const;void insertFront(const T &item);void insertRear(const T &item);void insertAt(const T &item);void insertAfter(const T &item);T deleteFront();void deleteCurrent();T& data();const T& data() constvoid clear();

34、#endif /LINKEDLIST_H449.2 線性群體 9.2.3 順序訪問群體鏈表類例9-7 鏈表類應用舉例/9_7.cpp#include #include LinkedList.husing namespace std;int main() LinkedList list;for (int i = 0; i item;list.insertFront(item);cout List: ;list.reset();while (!list.endOfList() cout list.data() ;list.next();cout endl;int key;cout key;list

35、.reset();while (!list.endOfList() if (list.data() = key) list.deleteCurrent();list.next();cout List: ;list.reset();while (!list.endOfList() cout list.data() ;list.nextcout endl;return 0;459.2 線性群體 9.2.3 順序訪問群體鏈表類例9-7（續(xù)）運行結果如下：3 6 5 7 5 2 4 5 9 10List: 10 9 5 4 2 5 7 5 6 3Please enter some integer ne

36、eded to be deleted: 5List: 10 9 4 2 7 6 3469.2 線性群體 9.2.3 順序訪問群體鏈表類9.2.4 棧類棧是只能從一端訪問的線性群體，可以訪問的這一端稱棧頂，另一端稱棧底。479.2 線性群體ana2a1入棧出棧棧頂棧底棧的應用舉例表達式處理489.2 線性群體 9.2.4 棧類ba/a/b+c*d(a)t1+a/b+c*dt1=a/b(b)dct1*+a/b+c*d(c)t3a/b+c*dt3=t1+t2(e)t2t1+a/b+c*dt2=c*d(d)棧的基本狀態(tài)?？諚Ｖ袥]有元素棧滿棧中元素個數(shù)達到上限一般狀態(tài)棧中有元素，但未達到棧滿狀態(tài)499.

37、2 線性群體 9.2.4 棧類509.2 線性群體 9.2.4 棧類50棧頂ana1a0入棧出棧數(shù)組下標maxn10一般狀態(tài)棧頂入棧出棧數(shù)組下標初始狀態(tài)（?？眨﹎axn10棧頂amaxana1a0入棧出棧數(shù)組下標maxn10棧滿狀態(tài)50棧的基本操作初始化入棧出棧清空棧訪問棧頂元素檢測棧的狀態(tài)（滿、空）519.2 線性群體 9.2.4 棧類例9-8 棧類模板/Stack.h#ifndef STACK_H#define STACK_H#include template class Stack private:T listSIZE;int top;public:Stack();void push(c

38、onst T &item);T pop();void clear();const T &peek() const;bool isEmpty() const;bool isFull() const;529.2 線性群體 9.2.4 棧類例9-8 （續(xù)）/模板的實現(xiàn)template Stack:Stack() : top(-1) template void Stack:push(const T &item) assert(!isFull();list+top = item;template T Stack:pop() assert(!isEmpty();return listtop-;templa

39、te const T &Stack:peek() const assert(!isEmpty();return listtop;/返回棧頂元素template bool Stack:isEmpty() const return top = -1;template bool Stack:isFull() const return top = SIZE - 1;template void Stack:clear() top = -1;#endif/STACK_H539.2 線性群體 9.2.4 棧類棧的應用例9.9 一個簡單的整數(shù)計算器實現(xiàn)一個簡單的整數(shù)計算器，能夠進行加、減、乘、除和乘方運算。使

40、用時算式采用后綴輸入法，每個操作數(shù)、操作符之間都以空白符分隔。例如，若要計算3+5則輸入3 5 +。乘方運算符用表示。每次運算在前次結果基礎上進行，若要將前次運算結果清除，可鍵入c。當鍵入q時程序結束。Calculator.h Calculator.cpp 9_9.cpp549.2 線性群體 9.2.4 棧類55例9-9/Calculator.h#ifndef CALCULATOR_H#define CALCULATOR_H#include Stack.h/ 包含棧類模板定義文件class Calculator /計算器類private:Stack s;/ 操作數(shù)棧void enter(dou

41、ble num);/將操作數(shù)num壓入棧/連續(xù)將兩個操作數(shù)彈出棧，放在opnd1和opnd2中bool getTwoOperands(double &opnd1, double &opnd2);void compute(char op);/執(zhí)行由操作符op指定的運算public:void run();/運行計算器程序void clear();/清空操作數(shù)棧;#endif /CALCULATOR_H9.2 線性群體 9.2.4 棧類56例9-9 (續(xù))/Calculator.cpp#include Calculator.h#include #include #include using name

42、space std;/工具函數(shù)，用于將字符串轉換為實數(shù)inline double stringToDouble(const string &str) istringstream stream(str);/字符串輸入流double result;stream result;return result;void Calculator:enter(double num) /將操作數(shù)num壓入棧s.push(num);9.2 線性群體 9.2.4 棧類57例9-9 (續(xù))bool Calculator:getTwoOperands(double &opnd1, double &opnd2) if (s

43、.isEmpty() /檢查棧是否空cerr Missing operand! endl;return false;opnd1 = s.pop();/將右操作數(shù)彈出棧if (s.isEmpty() /檢查棧是否空cerr Missing operand! endl;return false;opnd2 = s.pop();/將左操作數(shù)彈出棧return true;9.2 線性群體 9.2.4 棧類58void Calculator:compute(char op) /執(zhí)行運算double operand1, operand2;bool result = getTwoOperands(opera

44、nd1, operand2); if (result) /如果成功，執(zhí)行運算并將運算結果壓入棧switch(op) case +: s.push(operand2 + operand1); break;case -: s.push(operand2 - operand1); break;case *: s.push(operand2 * operand1); break;case /:if (operand1 = 0) /檢查除數(shù)是否為0cerr Divided by 0! endl;s.clear();/除數(shù)為0時清空棧 elses.push(operand2 / operand1);bre

45、ak;case : s.push(pow(operand2, operand1); break;default:cerr Unrecognized operator! endl;break;cout = s.peek() str, str != q) switch(str0) case c: s.clear(); break;case -: /遇-需判斷是減號還是負號if (str.size() 1)enter(stringToDouble(str);elsecompute(str0);break;case +:/遇到其它操作符時case *:case /:case :compute(str0

46、);default: /若讀入的是操作數(shù)，轉換為整型后壓入棧enter(stringToDouble(str); break;void Calculator:clear() /清空操作數(shù)棧s.clear(); 9.2 線性群體 9.2.4 棧類例9-9 (續(xù))60例9-9 (續(xù))/9_9.cpp#include Calculator.hint main() Calculator c;c.run();return 0;9.2 線性群體 9.2.4 棧類9.2.5 隊列類隊列是只能向一端添加元素，從另一端刪除元素的線性群體619.2 線性群體a1 a2an-1 an隊頭隊尾入隊出隊a0隊列的基本狀

47、態(tài)隊空隊列中沒有元素隊滿隊列中元素個數(shù)達到上限一般狀態(tài)隊列中有元素，但未達到隊滿狀態(tài)629.2 線性群體 9.2.5 隊列類639.2 線性群體 9.2.5 隊列類a0 a1an-1 an隊頭隊尾入隊出隊數(shù)組下標 0 1 n-1 n max(一般狀態(tài))隊頭隊尾入隊出隊數(shù)組下標 0 1 n-1 n max(隊空狀態(tài)) a0 a1 an-1 an amax隊頭隊尾入隊出隊數(shù)組下標 0 1 n-1 n max(隊滿狀態(tài))元素移動方向元素移動方向63循環(huán)隊列在想象中將數(shù)組彎曲成環(huán)形，元素出隊時，后繼元素不移動，每當隊尾達到數(shù)組最后一個元素時，便再回到數(shù)組開頭。649.2 線性群體 9.2.5 隊列類6

48、59.2 線性群體 9.2.5 隊列類1234m-1m-2m-30amam+1am+2a3隊頭隊尾a4am-2am-3am-1隊滿狀態(tài) 元素個數(shù)=m1234m-1m-2m-30隊尾隊頭隊空狀態(tài) 元素個數(shù)=0隊尾1234m-1m-2m-30a0a1a2a3隊頭一般狀態(tài)65例9-10 隊列類模板/Queue.h#ifndef QUEUE_H#define QUEUE_H#include /類模板的定義template class Queue private:int front, rear, count;/隊頭指針、隊尾指針、元素個數(shù)T listSIZE;/隊列元素數(shù)組public:Queue();

49、 /構造函數(shù)，初始化隊頭指針、隊尾指針、元素個數(shù)void insert(const T &item);/新元素入隊T remove();/元素出隊void clear();/清空隊列const T &getFront() const;/訪問隊首元素669.2 線性群體 9.2.5 隊列類/測試隊列狀態(tài)int getLength() const;/求隊列長度bool isEmpty() const;/判隊隊列空否bool isFull() const;/判斷隊列滿否;/構造函數(shù)，初始化隊頭指針、隊尾指針、元素個數(shù)template Queue:Queue() : front(0), rear(0)

50、, count(0) template void Queue:insert (const T& item) /向隊尾插入元素assert(count != SIZE);count+;/元素個數(shù)增1listrear = item;/向隊尾插入元素rear = (rear + 1) % SIZE;/隊尾指針增1，用取余運算實現(xiàn)循環(huán)隊列template T Queue:remove() assert(count != 0);int temp = front;/記錄下原先的隊首指針 count-;/元素個數(shù)自減 front = (front + 1) % SIZE;/隊首指針增1。取余以實現(xiàn)循環(huán)隊列

51、return listtemp;/返回首元素值679.2 線性群體 9.2.5 隊列類例9-10（續(xù)）template const T &Queue:getFront() const return listfront;template int Queue:getLength() const /返回隊列元素個數(shù)return count;template bool Queue:isEmpty() const /測試隊空否return count = 0;template bool Queue:isFull() const /測試隊滿否return count = SIZE;template voi

52、d Queue:clear() /清空隊列count = 0;front = 0; rear = 0; #endif /QUEUE_H689.2 線性群體 9.2.5 隊列類例9-10（續(xù)）9.3 群體數(shù)據(jù)的組織插入排序選擇排序交換排序順序查找折半查找699.3 群體數(shù)據(jù)的組織排序（sorting）排序是計算機程序設計中的一種重要操作，它的功能是將一個數(shù)據(jù)元素的任意序列，重新排列成一個按關鍵字有序的序列。數(shù)據(jù)元素：數(shù)據(jù)的基本單位。在計算機中通常作為一個整體進行考慮。一個數(shù)據(jù)元素可由若干數(shù)據(jù)項組成。關鍵字：數(shù)據(jù)元素中某個數(shù)據(jù)項的值，用它可以標識（識別）一個數(shù)據(jù)元素。在排序過程中需要完成兩種基本操

53、作：比較兩個數(shù)的大小調整元素在序列中的位置709.3 群體數(shù)據(jù)的組織內(nèi)部排序與外部排序內(nèi)部排序：待排序的數(shù)據(jù)元素存放在計算機內(nèi)存中進行的排序過程。外部排序：待排序的數(shù)據(jù)元素數(shù)量很大，以致內(nèi)存存中一次不能容納全部數(shù)據(jù)，在排序過程中尚需對外存進行訪問的排序過程。719.3 群體數(shù)據(jù)的組織內(nèi)部排序方法插入排序選擇排序交換排序729.3 群體數(shù)據(jù)的組織插入排序的基本思想每一步將一個待排序元素按其關鍵字值的大小插入到已排序序列的適當位置上，直到待排序元素插入完為止。739.3 群體數(shù)據(jù)的組織 9.3.1 插入排序初始狀態(tài)： 5 4 10 20 12 3插入操作：1 4 4 5 10 20 12 32 1

54、0 4 5 10 20 12 33 20 4 5 10 20 12 34 12 4 5 10 12 20 35 3 3 4 5 10 12 20直接插入排序在插入排序過程中，由于尋找插入位置的方法不同又可以分為不同的插入排序算法，這里我們只介紹最簡單的直接插入排序算法。例9-11 直接插入排序函數(shù)模板（9_11.h）749.3 群體數(shù)據(jù)的組織 9.3.1 插入排序75例9-11 直接插入排序函數(shù)模板template void insertionSort(T a, int n) int i, j;T temp;for (int i = 1; i 0 & temp aj - 1) aj = aj

55、- 1;j-;aj = temp;9.3 群體數(shù)據(jù)的組織 9.3.1 插入排序選擇排序的基本思想每次從待排序序列中選擇一個關鍵字最小的元素，（當需要按關鍵字升序排列時），順序排在已排序序列的最后，直至全部排完。769.3 群體數(shù)據(jù)的組織 9.3.2 選擇排序5 4 10 20 12 3初始狀態(tài)：3 4 10 20 12 53 4 10 20 12 5第 i 次選擇后，將選出的那個記錄與第 i 個記錄做交換。3 4 5 20 12 10.直接選擇排序在選擇類排序方法中，從待排序序列中選擇元素的方法不同，又分為不同的選擇排序方法，其中最簡單的是通過順序比較找出待排序序列中的最小元素，稱為直接選擇排

56、序。例9-12 直接選擇排序函數(shù)模板（9-12.h）779.3 群體數(shù)據(jù)的組織 9.3.2 選擇排序78例9-12 直接選擇排序函數(shù)模板template void mySwap(T &x, T &y) T temp = x;x = y;y = temp;template void selectionSort(T a, int n) for (int i = 0; i n - 1; i+) int leastIndex = i;for (int j = i + 1; j n; j+)if (aj aleastIndex)leastIndex = j;mySwap(ai, aleastIndex)

57、;9.3 群體數(shù)據(jù)的組織 9.3.2 選擇排序交換排序的基本思想兩兩比較待排序序列中的元素，并交換不滿足順序要求的各對元素，直到全部滿足順序要求為止。799.3 群體數(shù)據(jù)的組織 9.3.3 交換排序最簡單的交換排序方法起泡排序對具有n個元素的序列按升序進行起泡排序的步驟：首先將第一個元素與第二個元素進行比較，若為逆序，a則將兩元素交換。然后比較第二、第三個元素，依次類推，直到第n-1和第n個元素進行了比較和交換。此過程稱為第一趟起泡排序。經(jīng)過第一趟，最大的元素便被交換到第n個位置。對前n-1個元素進行第二趟起泡排序，將其中最大元素交換到第n-1個位置。如此繼續(xù)，直到某一趟排序未發(fā)生任何交換時，

58、排序完畢。對n個元素的序列，起泡排序最多需要進行n-1趟。809.3 群體數(shù)據(jù)的組織 9.3.3 交換排序起泡排序舉例對整數(shù)序列 8 5 2 4 3 按升序排序819.3 群體數(shù)據(jù)的組織 9.3.3 交換排序8524352438243582345823458初始狀態(tài)第一趟結果第二趟結果第三趟結果第四趟結果小的逐漸上升每趟沉下一個最大的例9-13 起泡排序函數(shù)模板template void mySwap(T &x, T &y) T temp = x;x = y;y = temp;template void bubbleSort(T a, int n) int i = n 1;while (i 0

59、) int lastExchangeIndex = 0; for (int j = 0; j i; j+) if (aj + 1 aj) mySwap(aj, aj + 1); lastExchangeIndex = j; i = lastExchangeIndex;829.3 群體數(shù)據(jù)的組織 9.3.3 交換排序9.3.4 順序查找其基本思想從序列的首元素開始，逐個元素與待查找的關鍵字進行比較，直到找到相等的。若整個序列中沒有與待查找關鍵字相等的元素，就是查找不成功。順序查找函數(shù)模板例9-14839.3 群體數(shù)據(jù)的組織84例9-14 順序查找函數(shù)模板template int seqSearc

60、h(const T list, int n, const T &key) for(int i = 0; i n; i+)if (listi = key)return i; return -1; 9.3 群體數(shù)據(jù)的組織 9.3.4 順序查找折半查找的基本思想對于已按關鍵字排序的序列，經(jīng)過一次比較，可將序列分割成兩部分，然后只在有可能包含待查元素的一部分中繼續(xù)查找，并根據(jù)試探結果繼續(xù)分割，逐步縮小查找范圍，直至找到或找不到為止。859.3 群體數(shù)據(jù)的組織 9.3.5 折半查找折半查找舉例用折半查找法，在下列序列中查找值為21的元素：869.3 群體數(shù)據(jù)的組織 9.3.5 折半查找L=1513192