第9章群體類和群體數(shù)據(jù)的組織

1、C+語(yǔ)言程序設(shè)計(jì)（第4版）第九章 群體類和群體數(shù)據(jù)的組織清華大學(xué) 鄭 莉C+語(yǔ)言程序設(shè)計(jì)（第4版），鄭莉，清華大學(xué)目錄9.1 函數(shù)模板與類模板9.2 線性群體9.3 群體數(shù)據(jù)的組織9.4 綜合實(shí)例對(duì)個(gè)人銀行賬戶管理程序的改進(jìn)9.5 深度探索9.6 小結(jié)2C+語(yǔ)言程序設(shè)計(jì)（第4版），鄭莉，清華大學(xué)9.1.1 函數(shù)模板 函數(shù)模板可以用來(lái)創(chuàng)建一個(gè)通用功能的函數(shù)，以支持多種不同形參，進(jìn)一步簡(jiǎn)化重載函數(shù)的函數(shù)體設(shè)計(jì)。 定義方法：template 函數(shù)定義 模板參數(shù)表的內(nèi)容 類型參數(shù)：class（或typename） 標(biāo)識(shí)符 常量參數(shù)：類型說(shuō)明符 標(biāo)識(shí)符 模板參數(shù)：template class 標(biāo)識(shí)符39

2、.1 函數(shù)模板與類模板C+語(yǔ)言程序設(shè)計(jì)（第4版），鄭莉，清華大學(xué)4例：求絕對(duì)值函數(shù)的模板#include using namespace std;templateT 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;return 0;9.1 函數(shù)模板與類模板 9.1.1 函數(shù)模板運(yùn)行運(yùn)行結(jié)果：結(jié)果：55.5C+語(yǔ)言程序設(shè)計(jì)（第4版），鄭莉，清華大學(xué)求絕對(duì)值函數(shù)的模板分析 編譯器從調(diào)用abs()時(shí)實(shí)參的類型，推導(dǎo)出函數(shù)模板的類型參數(shù)。例如，對(duì)于調(diào)用

3、表達(dá)式abs(n)，由于實(shí)參n為int型，所以推導(dǎo)出模板中類型參數(shù)T為int。 當(dāng)類型參數(shù)的含義確定后，編譯器將以函數(shù)模板為樣板，生成一個(gè)函數(shù)：int abs(int x) return x 0 ? x : x;59.1 函數(shù)模板與類模板 9.1.1 函數(shù)模板C+語(yǔ)言程序設(shè)計(jì)（第4版），鄭莉，清華大學(xué)例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

4、;cout endl; 69.1 函數(shù)模板與類模板 9.1.1 函數(shù)模板C+語(yǔ)言程序設(shè)計(jì)（第4版），鄭莉，清華大學(xué)例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, 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 ar

5、ray contains: endl;outputArray(a, A_COUNT);/調(diào)用函數(shù)模板cout b array contains: endl;outputArray(b, B_COUNT);/調(diào)用函數(shù)模板cout c array contains: endl;outputArray(c, C_COUNT);/調(diào)用函數(shù)模板return 0;79.1 函數(shù)模板與類模板 9.1.1 函數(shù)模板C+語(yǔ)言程序設(shè)計(jì)（第4版），鄭莉，清華大學(xué)例9-1（續(xù)） 運(yùn)行結(jié)果如下：a array contains:1 2 3 4 5 6 7 8b array contains:1.1 2.2 3.3 4.

6、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ù)模板C+語(yǔ)言程序設(shè)計(jì)（第4版），鄭莉，清華大學(xué)9.1.2 類模板 類模板的作用使用類模板使用戶可以為類聲明一種模式，使得類中的某些數(shù)據(jù)成員、某些成員函數(shù)的參數(shù)、某些成員函數(shù)的返回值，能取任意類型（包括基本類型的和用戶自定義類型）。99.1 函數(shù)模板與類模板C+語(yǔ)言程序設(shè)計(jì)（第4版），鄭莉，清華大學(xué)類模板的聲明 類模板：template class 類名類成員聲明 如果需要在類模板以外定義其成員函數(shù)，則要采用以下的形式：t

7、emplate 類型名 類名:函數(shù)名（參數(shù)表）109.1 函數(shù)模板與類模板 9.1.2 類模板C+語(yǔ)言程序設(shè)計(jì)（第4版），鄭莉，清華大學(xué)例9-2 類模板示例#include #include using namespace std;struct Student int id; /學(xué)號(hào) float gpa; /平均分; template class Store /類模板：實(shí)現(xiàn)對(duì)任意類型數(shù)據(jù)進(jìn)行存取private:T item;/ item用于存放任意類型的數(shù)據(jù)bool haveValue; / haveValue標(biāo)記item是否已被存入內(nèi)容public:Store();/ 缺省形式（無(wú)形參）的構(gòu)

8、造函數(shù)T &getElem();/提取數(shù)據(jù)函數(shù)void putElem(const T &x); /存入數(shù)據(jù)函數(shù);119.1 函數(shù)模板與類模板 9.1.2 類模板C+語(yǔ)言程序設(shè)計(jì)（第4版），鄭莉，清華大學(xué)12例9-2 (續(xù))template /默認(rèn)構(gòu)造函數(shù)的實(shí)現(xiàn) Store:Store(): haveValue(false) template /提取數(shù)據(jù)函數(shù)的實(shí)現(xiàn)T &Store:getElem() /如試圖提取未初始化的數(shù)據(jù)，則終止程序if (!haveValue) cout No item present! endl;exit(1);/使程序完全退出，返回到操作系統(tǒng)

9、。return item; / 返回item中存放的數(shù)據(jù) template /存入數(shù)據(jù)函數(shù)的實(shí)現(xiàn) void Store:putElem(const T &x) / 將haveValue 置為true，表示item中已存入數(shù)值haveValue = true;item = x;/ 將x值存入item9.1 函數(shù)模板與類模板 9.1.2 類模板C+語(yǔ)言程序設(shè)計(jì)（第4版），鄭莉，清華大學(xué)13例9-2 (續(xù))int main() Store s1, s2;s1.putElem(3);s2.putElem(-7);cout s1.getElem() s2.getElem() endl;Stude

10、nt 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()過(guò)程中導(dǎo)致程序終止return 0;9.1 函數(shù)模板與類模板 9.1.2 類模板C+語(yǔ)言程序設(shè)計(jì)（第4版），鄭莉，清華大學(xué)線性群體 線性群體的概念 直接訪問(wèn)群體-數(shù)組類 順序訪問(wèn)群體-鏈表類 棧類 隊(duì)列類149.2 線性群體C+語(yǔ)言程序設(shè)計(jì)（第4版），鄭莉，清

11、華大學(xué)群體的概念 群體是指由多個(gè)數(shù)據(jù)元素組成的集合體。群體可以分為兩個(gè)大類：線性群體和非線性群體。 線性群體中的元素按位置排列有序，可以區(qū)分為第一個(gè)元素、第二個(gè)元素等。 非線性群體不用位置順序來(lái)標(biāo)識(shí)元素。159.2 線性群體C+語(yǔ)言程序設(shè)計(jì)（第4版），鄭莉，清華大學(xué)9.2.1 線性群體的概念 線性群體中的元素次序與其位置關(guān)系是對(duì)應(yīng)的。在線性群體中，又可按照訪問(wèn)元素的不同方法分為直接訪問(wèn)、順序訪問(wèn)和索引訪問(wèn)。 在本章我們只介紹直接訪問(wèn)和順序訪問(wèn)。169.2 線性群體第一個(gè)元素第二個(gè)元素第三個(gè)元素最后一個(gè)元素C+語(yǔ)言程序設(shè)計(jì)（第4版），鄭莉，清華大學(xué)9.2.2 直接訪問(wèn)群體數(shù)組類 靜態(tài)數(shù)組是具有固

12、定元素個(gè)數(shù)的群體，其中的元素可以通過(guò)下標(biāo)直接訪問(wèn)。 缺點(diǎn)：大小在編譯時(shí)就已經(jīng)確定，在運(yùn)行時(shí)無(wú)法修改。 動(dòng)態(tài)數(shù)組由一系列位置連續(xù)的，任意數(shù)量相同類型的元素組成。 優(yōu)點(diǎn)：其元素個(gè)數(shù)可在程序運(yùn)行時(shí)改變。 vector就是用類模板實(shí)現(xiàn)的動(dòng)態(tài)數(shù)組。 動(dòng)態(tài)數(shù)組類模板：例9-3（Array.h）179.2 線性群體C+語(yǔ)言程序設(shè)計(jì)（第4版），鄭莉，清華大學(xué)18例9-3 動(dòng)態(tài)數(shù)組類模板程序#ifndef ARRAY_H#define ARRAY_H#include template /數(shù)組類模板定義class Array private:T* list;/用于存放動(dòng)態(tài)分配的數(shù)組內(nèi)存首地址int size;/數(shù)

13、組大小（元素個(gè)數(shù)）public:Array(int sz = 50);/構(gòu)造函數(shù)Array(const Array &a);/拷貝構(gòu)造函數(shù)Array();/析構(gòu)函數(shù)Array & operator = (const Array &rhs); /重載=“T & operator (int i); /重載”const T & operator (int i) const;operator T * ();/重載到T*類型的轉(zhuǎn)換operator const T * () const;int getSize() const;/取數(shù)組的大小void resize(i

14、nt sz);/修改數(shù)組的大小;9.2 線性群體 9.2.2 直接訪問(wèn)群體數(shù)組類C+語(yǔ)言程序設(shè)計(jì)（第4版），鄭莉，清華大學(xué)template Array:Array(int sz) /構(gòu)造函數(shù)assert(sz = 0);/sz為數(shù)組大小（元素個(gè)數(shù)），應(yīng)當(dāng)非負(fù)size = sz; / 將元素個(gè)數(shù)賦值給變量sizelist = new T size;/動(dòng)態(tài)分配size個(gè)T類型的元素空間template Array:Array() /析構(gòu)函數(shù)delete list;/拷貝構(gòu)造函數(shù)template Array:Array(const Array &a) size = a.size; /從對(duì)象x

15、取得數(shù)組大小，并賦值給當(dāng)前對(duì)象的成員/為對(duì)象申請(qǐng)內(nèi)存并進(jìn)行出錯(cuò)檢查list = new Tsize;/ 動(dòng)態(tài)分配n個(gè)T類型的元素空間for (int i = 0; i size; i+) /從對(duì)象X復(fù)制數(shù)組元素到本對(duì)象 listi = a.listi;199.2 線性群體 9.2.2 直接訪問(wèn)群體數(shù)組類例9-3（續(xù)）C+語(yǔ)言程序設(shè)計(jì)（第4版），鄭莉，清華大學(xué)/重載=運(yùn)算符，將對(duì)象rhs賦值給本對(duì)象。實(shí)現(xiàn)對(duì)象之間的整體賦值template Array &Array:operator = (const Array& rhs) if (&rhs != this) /如果本對(duì)象

16、中數(shù)組大小與rhs不同，則刪除數(shù)組原有內(nèi)存，然后重新分配if (size != rhs.size) delete list;/刪除數(shù)組原有內(nèi)存size = rhs.size;/設(shè)置本對(duì)象的數(shù)組大小list = new Tsize; /重新分配n個(gè)元素的內(nèi)存/從對(duì)象X復(fù)制數(shù)組元素到本對(duì)象 for (int i = 0; i size; i+)listi = rhs.listi;return *this;/返回當(dāng)前對(duì)象的引用209.2 線性群體 9.2.2 直接訪問(wèn)群體數(shù)組類例9-3（續(xù)）C+語(yǔ)言程序設(shè)計(jì)（第4版），鄭莉，清華大學(xué)/重載下標(biāo)運(yùn)算符，實(shí)現(xiàn)與普通數(shù)組一樣通過(guò)下標(biāo)訪問(wèn)元素，并且具有越界檢

17、查功能template T &Array:operator (int n) assert(n = 0 & n size);/檢查下標(biāo)是否越界return listn;/返回下標(biāo)為n的數(shù)組元素template const T &Array:operator (int n) const assert(n = 0 & n size);/檢查下標(biāo)是否越界return listn;/返回下標(biāo)為n的數(shù)組元素 /重載指針轉(zhuǎn)換運(yùn)算符，將Array類的對(duì)象名轉(zhuǎn)換為T類型的指針template Array:operator T * () return list;/返回當(dāng)前對(duì)象中私有

18、數(shù)組的首地址 219.2 線性群體 9.2.2 直接訪問(wèn)群體數(shù)組類例9-3（續(xù)）C+語(yǔ)言程序設(shè)計(jì)（第4版），鄭莉，清華大學(xué)template Array:operator const T * () const return list; /返回當(dāng)前對(duì)象中私有數(shù)組的首地址/取當(dāng)前數(shù)組的大小template int Array:getSize() const return size;/ 將數(shù)組大小修改為sztemplate void Array:resize(int sz) assert(sz = 0);/檢查sz是否非負(fù)if (sz = size)/如果指定的大小與原有大小一樣，什么也不做retur

19、n;T* newList = new T sz;/申請(qǐng)新的數(shù)組內(nèi)存int n = (sz size) ? sz : size;/將sz與size中較小的一個(gè)賦值給n/將原有數(shù)組中前n個(gè)元素復(fù)制到新數(shù)組中for (int i = 0; i n; i+)newListi = listi;delete list;/刪除原數(shù)組list = newList;/ 使list指向新數(shù)組size = sz;/更新size#endif /ARRAY_H 229.2 線性群體 9.2.2 直接訪問(wèn)群體數(shù)組類例9-3（續(xù)）C+語(yǔ)言程序設(shè)計(jì)（第4版），鄭莉，清華大學(xué)23深拷貝9.2 線性群體 9.2.2 直接訪問(wèn)群體

20、數(shù)組類 list sizeaa的數(shù)組元素占用的內(nèi)存拷貝前 list sizeaa的數(shù)組元素占用的內(nèi)存拷貝后 list sizebb的數(shù)組元素占用的內(nèi)存C+語(yǔ)言程序設(shè)計(jì)（第4版），鄭莉，清華大學(xué)為什么有的函數(shù)返回引用 如果一個(gè)函數(shù)的返回值是一個(gè)對(duì)象的值，就不應(yīng)成為左值。 如果返回值為引用。由于引用是對(duì)象的別名，通過(guò)引用當(dāng)然可以改變對(duì)象的值。249.2 線性群體 9.2.2 直接訪問(wèn)群體數(shù)組類C+語(yǔ)言程序設(shè)計(jì)（第4版），鄭莉，清華大學(xué)指針轉(zhuǎn)換運(yùn)算符的作用#include using namespace std;void read(int *p, int n) for (int i = 0; i p

21、i;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;259.2 線性群體 9.2.2 直接訪問(wèn)群體數(shù)組類C+語(yǔ)言程序設(shè)計(jì)（第4版），鄭莉，清華大學(xué)Array類的應(yīng)用 例9-4求范圍2N中的質(zhì)數(shù)，N在程序運(yùn)行時(shí)由鍵盤輸入。269.2 線性群體 9.2.2 直接訪問(wèn)群體數(shù)組類C+語(yǔ)言程序設(shè)計(jì)（

22、第4版），鄭莉，清華大學(xué)27#include #include #include Array.husing namespace std;int main() Array a(10);/ 用來(lái)存放質(zhì)數(shù)的數(shù)組，初始狀態(tài)有10個(gè)元素。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 count; j+)if (i % aj = 0) /若i被aj整除，說(shuō)明i不是質(zhì)數(shù)isPrime = fa

23、lse; 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 直接訪問(wèn)群體數(shù)組類例9-4（續(xù)）C+語(yǔ)言程序設(shè)計(jì)（第4版），鄭莉，清華大學(xué)9.2.3 順序訪問(wèn)群體鏈表類 鏈表是一種動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)，可以用來(lái)表示順序訪問(wèn)的線性群體。 鏈表是由系列結(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)的地址

24、）。如果鏈表每個(gè)結(jié)點(diǎn)中只有一個(gè)指向后繼結(jié)點(diǎn)的指針，則該鏈表稱為單鏈表。289.2 線性群體C+語(yǔ)言程序設(shè)計(jì)（第4版），鄭莉，清華大學(xué)29單鏈表9.2 線性群體 9.2.3 順序訪問(wèn)群體鏈表類 data1 data2 data3 datan NULLheadrearC+語(yǔ)言程序設(shè)計(jì)（第4版），鄭莉，清華大學(xué)30單鏈表的結(jié)點(diǎn)類模板template class Node private: Node *next;public: T data; Node(const T& item,Node* next = 0); void insertAfter(Node *p); Node *deleteA

25、fter(); Node *nextNode() const; 9.2 線性群體 9.2.3 順序訪問(wèn)群體鏈表類C+語(yǔ)言程序設(shè)計(jì)（第4版），鄭莉，清華大學(xué)31在結(jié)點(diǎn)之后插入一個(gè)結(jié)點(diǎn)9.2 線性群體 9.2.3 順序訪問(wèn)群體鏈表類 data1 data2 p datatemplate void 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 C+語(yǔ)言程序設(shè)計(jì)（第4版），鄭莉，清華大學(xué)32 刪除結(jié)點(diǎn)之后的結(jié)點(diǎn)9.2 線性群體 9.2.3 順序訪問(wèn)群體鏈表類 data1 data2

26、data3tempPtrNode *Node:deleteAfter(void) Node *tempPtr = next; if (next = 0) return 0; next = tempPtr-next; return tempPtr; C+語(yǔ)言程序設(shè)計(jì)（第4版），鄭莉，清華大學(xué)例9-5結(jié)點(diǎn)類模扳/Node.h#ifndef NODE_H#define NODE_H/類模板的定義template class Node private:Node *next;/指向后繼結(jié)點(diǎn)的指針public:T data;/數(shù)據(jù)域Node (const T &data, Node *next =

27、 0); /構(gòu)造函數(shù)void insertAfter(Node *p); /在本結(jié)點(diǎn)之后插入一個(gè)同類結(jié)點(diǎn)p Node *deleteAfter(); /刪除本結(jié)點(diǎn)的后繼結(jié)點(diǎn)，并返回其地址Node *nextNode();/獲取后繼結(jié)點(diǎn)的地址const Node *nextNode() const; /獲取后繼結(jié)點(diǎn)的地址;339.2 線性群體 9.2.3 順序訪問(wèn)群體鏈表類C+語(yǔ)言程序設(shè)計(jì)（第4版），鄭莉，清華大學(xué)/類的實(shí)現(xiàn)部分/構(gòu)造函數(shù)，初始化數(shù)據(jù)和指針成員template Node:Node(const T& data, Node *next/* = 0 */) : data(dat

28、a), next(next) /返回后繼結(jié)點(diǎn)的指針template Node *Node:nextNode() return next; /返回后繼結(jié)點(diǎn)的指針template const Node *Node:nextNode() const return next; 349.2 線性群體 9.2.3 順序訪問(wèn)群體鏈表類例9-5（續(xù)）C+語(yǔ)言程序設(shè)計(jì)（第4版），鄭莉，清華大學(xué)/在當(dāng)前結(jié)點(diǎn)之后插入一個(gè)結(jié)點(diǎn)p template void Node:insertAfter(Node *p) p-next = next; /p結(jié)點(diǎn)指針域指向當(dāng)前結(jié)點(diǎn)的后繼結(jié)點(diǎn) next = p; /當(dāng)前結(jié)點(diǎn)的指針域指向

29、p /刪除當(dāng)前結(jié)點(diǎn)的后繼結(jié)點(diǎn)，并返回其地址template Node *Node:deleteAfter() Node *tempPtr = next;/將欲刪除的結(jié)點(diǎn)地址存儲(chǔ)到tempPtr中if (next = 0)/如果當(dāng)前結(jié)點(diǎn)沒(méi)有后繼結(jié)點(diǎn)，則返回空指針return 0;next = tempPtr-next;/使當(dāng)前結(jié)點(diǎn)的指針域指向tempPtr的后繼結(jié)點(diǎn)return tempPtr;/返回被刪除的結(jié)點(diǎn)的地址#endif /NODE_H359.2 線性群體 9.2.3 順序訪問(wèn)群體鏈表類例9-5（續(xù)）C+語(yǔ)言程序設(shè)計(jì)（第4版），鄭莉，清華大學(xué)鏈表的基本操作 生成結(jié)點(diǎn) 插入結(jié)點(diǎn) 查找結(jié)點(diǎn)

30、 刪除結(jié)點(diǎn) 遍歷鏈表 清空鏈表369.2 線性群體 9.2.3 順序訪問(wèn)群體鏈表類C+語(yǔ)言程序設(shè)計(jì)（第4版），鄭莉，清華大學(xué)例9-6 鏈表類模板#ifndef LINKEDLIST_H#define LINKEDLIST_H#include Node.htemplate class LinkedList private:/數(shù)據(jù)成員：Node *front, *rearNode *prevPtr, *currPtr; int size;int position;Node *newNode(const T &item,Node *ptrNext=NULL);void freeNode(No

31、de *p);void copy(const LinkedList& L);public:LinkedList();LinkedList(const LinkedList &L); LinkedList();LinkedList & operator = (const LinkedList &L); int getSize() const;bool isEmpty() const;void reset(int pos = 0);void next();bool endOfList() const;int currentPosition(void) const;v

32、oid 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();#endif /LINKEDLIST_H/鏈表類模板函數(shù)實(shí)現(xiàn)代碼可以從網(wǎng)上下載379.2 線性群體 9.2.3 順序訪問(wèn)群體鏈表類C+語(yǔ)言程序設(shè)

33、計(jì)（第4版），鄭莉，清華大學(xué)例9-7 鏈表類應(yīng)用舉例/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.reset();while (!list.endOfList(

34、) if (list.data() = key) list.deleteCurrent();list.next();cout List: ;list.reset();while (!list.endOfList() cout list.data() ;list.nextcout endl;return 0;389.2 線性群體 9.2.3 順序訪問(wèn)群體鏈表類C+語(yǔ)言程序設(shè)計(jì)（第4版），鄭莉，清華大學(xué)例9-7（續(xù)） 運(yùn)行結(jié)果如下：3 6 5 7 5 2 4 5 9 10List: 10 9 5 4 2 5 7 5 6 3Please enter some integer needed to be

35、 deleted: 5List: 10 9 4 2 7 6 3399.2 線性群體 9.2.3 順序訪問(wèn)群體鏈表類C+語(yǔ)言程序設(shè)計(jì)（第4版），鄭莉，清華大學(xué)9.2.4 棧類 棧是只能從一端訪問(wèn)的線性群體，可以訪問(wèn)的這一端稱棧頂，另一端稱棧底。409.2 線性群體ana2a1入棧出棧棧頂棧底C+語(yǔ)言程序設(shè)計(jì)（第4版），鄭莉，清華大學(xué)棧的應(yīng)用舉例表達(dá)式處理419.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)C+語(yǔ)言程序設(shè)計(jì)（第4版），鄭

36、莉，清華大學(xué)棧的基本狀態(tài) ?？?棧中沒(méi)有元素 棧滿 棧中元素個(gè)數(shù)達(dá)到上限 一般狀態(tài) 棧中有元素，但未達(dá)到棧滿狀態(tài)429.2 線性群體 9.2.4 棧類C+語(yǔ)言程序設(shè)計(jì)（第4版），鄭莉，清華大學(xué)439.2 線性群體 9.2.4 棧類棧頂ana1a0入棧出棧數(shù)組下標(biāo)maxn10一般狀態(tài)棧頂入棧出棧數(shù)組下標(biāo)初始狀態(tài)（?？眨﹎axn10棧頂amaxana1a0入棧出棧數(shù)組下標(biāo)maxn10棧滿狀態(tài)C+語(yǔ)言程序設(shè)計(jì)（第4版），鄭莉，清華大學(xué)棧的基本操作 初始化 入棧 出棧 清空棧 訪問(wèn)棧頂元素 檢測(cè)棧的狀態(tài)（滿、空）449.2 線性群體 9.2.4 棧類C+語(yǔ)言程序設(shè)計(jì)（第4版），鄭莉，清華大學(xué)例9-8

37、棧類模板/Stack.h#ifndef STACK_H#define STACK_H#include template class Stack private:T listSIZE;int top;public:Stack();void push(const T &item);T pop();void clear();const T &peek() const;bool isEmpty() const;bool isFull() const;459.2 線性群體 9.2.4 棧類C+語(yǔ)言程序設(shè)計(jì)（第4版），鄭莉，清華大學(xué)例9-8 （續(xù)）/模板的實(shí)現(xiàn)template Stack:

38、Stack() : top(-1) template void Stack:push(const T &item) assert(!isFull();list+top = item;template T Stack:pop() assert(!isEmpty();return listtop-;template const T &Stack:peek() const assert(!isEmpty();return listtop; /返回棧頂元素template bool Stack:isEmpty() const return top = -1;template bool

39、Stack:isFull() const return top = SIZE - 1; template void Stack:clear() top = -1; #endif/STACK_H469.2 線性群體 9.2.4 棧類C+語(yǔ)言程序設(shè)計(jì)（第4版），鄭莉，清華大學(xué)棧的應(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é)束。 Calculator.

40、h Calculator.cpp 9_9.cpp479.2 線性群體 9.2.4 棧類C+語(yǔ)言程序設(shè)計(jì)（第4版），鄭莉，清華大學(xué)48例9-9/Calculator.h#ifndef CALCULATOR_H#define CALCULATOR_H#include Stack.h/ 包含棧類模板定義文件class Calculator /計(jì)算器類private:Stack s;/ 操作數(shù)棧void enter(double num);/將操作數(shù)num壓入棧/連續(xù)將兩個(gè)操作數(shù)彈出棧，放在opnd1和opnd2中bool getTwoOperands(double &opnd1, doubl

41、e &opnd2);void compute(char op);/執(zhí)行由操作符op指定的運(yùn)算public:void run();/運(yùn)行計(jì)算器程序void clear();/清空操作數(shù)棧;#endif /CALCULATOR_H9.2 線性群體 9.2.4 棧類C+語(yǔ)言程序設(shè)計(jì)（第4版），鄭莉，清華大學(xué)49例9-9 (續(xù))/Calculator.cpp#include Calculator.h#include #include #include using namespace std;/工具函數(shù)，用于將字符串轉(zhuǎn)換為實(shí)數(shù)inline double stringToDouble(const

42、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 棧類C+語(yǔ)言程序設(shè)計(jì)（第4版），鄭莉，清華大學(xué)50例9-9 (續(xù))bool Calculator:getTwoOperands(double &opnd1, double &opnd2) if (s.isEmpty() /檢查棧是否空cerr Missin

43、g 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 棧類C+語(yǔ)言程序設(shè)計(jì)（第4版），鄭莉，清華大學(xué)51void Calculator:compute(char op) /執(zhí)行運(yùn)算double operand1, operand2;bool result = getTwoOperands(operand1, ope

44、rand2); if (result) /如果成功，執(zhí)行運(yùn)算并將運(yùn)算結(jié)果壓入棧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時(shí)清空棧 elses.push(operand2 / operand1);break;case

45、: 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 -: /遇-需判斷是減號(hào)還是負(fù)號(hào)if (str.size() 1)enter(stringToDouble(str);elsecompute(str0);break;case +:/遇到其它操作符時(shí)case *:case /:case :compute(str0);defaul

46、t: /若讀入的是操作數(shù)，轉(zhuǎn)換為整型后壓入棧enter(stringToDouble(str); break;void Calculator:clear() /清空操作數(shù)棧s.clear(); 9.2 線性群體 9.2.4 棧類例9-9 (續(xù))C+語(yǔ)言程序設(shè)計(jì)（第4版），鄭莉，清華大學(xué)53例9-9 (續(xù))/9_9.cpp#include Calculator.hint main() Calculator c;c.run();return 0;9.2 線性群體 9.2.4 棧類C+語(yǔ)言程序設(shè)計(jì)（第4版），鄭莉，清華大學(xué)9.2.5 隊(duì)列類 隊(duì)列是只能向一端添加元素，從另一端刪除元素的線性群體549

47、.2 線性群體a1 a2an-1 an隊(duì)頭隊(duì)尾入隊(duì)出隊(duì)a0C+語(yǔ)言程序設(shè)計(jì)（第4版），鄭莉，清華大學(xué)隊(duì)列的基本狀態(tài) 隊(duì)空 隊(duì)列中沒(méi)有元素 隊(duì)滿 隊(duì)列中元素個(gè)數(shù)達(dá)到上限 一般狀態(tài) 隊(duì)列中有元素，但未達(dá)到隊(duì)滿狀態(tài)559.2 線性群體 9.2.5 隊(duì)列類C+語(yǔ)言程序設(shè)計(jì)（第4版），鄭莉，清華大學(xué)569.2 線性群體 9.2.5 隊(duì)列類a0 a1an-1 an隊(duì)頭隊(duì)尾入隊(duì)出隊(duì)數(shù)組下標(biāo) 0 1 n-1 n max(一般狀態(tài))隊(duì)頭隊(duì)尾入隊(duì)出隊(duì)數(shù)組下標(biāo) 0 1 n-1 n max(隊(duì)空狀態(tài)) a0 a1 an-1 an amax隊(duì)頭隊(duì)尾入隊(duì)出隊(duì)數(shù)組下標(biāo) 0 1 n-1 n max(隊(duì)滿狀態(tài))元素移動(dòng)方向元素

48、移動(dòng)方向56C+語(yǔ)言程序設(shè)計(jì)（第4版），鄭莉，清華大學(xué)循環(huán)隊(duì)列 在想象中將數(shù)組彎曲成環(huán)形，元素出隊(duì)時(shí)，后繼元素不移動(dòng)，每當(dāng)隊(duì)尾達(dá)到數(shù)組最后一個(gè)元素時(shí)，便再回到數(shù)組開(kāi)頭。579.2 線性群體 9.2.5 隊(duì)列類C+語(yǔ)言程序設(shè)計(jì)（第4版），鄭莉，清華大學(xué)589.2 線性群體 9.2.5 隊(duì)列類1234m-1m-2m-30amam+1am+2a3隊(duì)頭隊(duì)尾a4am-2am-3am-1隊(duì)滿狀態(tài) 元素個(gè)數(shù)=m1234m-1m-2m-30隊(duì)尾隊(duì)頭隊(duì)空狀態(tài) 元素個(gè)數(shù)=0隊(duì)尾1234m-1m-2m-30a0a1a2a3隊(duì)頭一般狀態(tài)58C+語(yǔ)言程序設(shè)計(jì)（第4版），鄭莉，清華大學(xué)例9-10 隊(duì)列類模板/Queue.

49、h#ifndef QUEUE_H#define QUEUE_H#include /類模板的定義template class Queue private:int front, rear, count;/隊(duì)頭指針、隊(duì)尾指針、元素個(gè)數(shù)T listSIZE;/隊(duì)列元素?cái)?shù)組public:Queue(); /構(gòu)造函數(shù)，初始化隊(duì)頭指針、隊(duì)尾指針、元素個(gè)數(shù)void insert(const T &item);/新元素入隊(duì)T remove(); /元素出隊(duì)void clear();/清空隊(duì)列const T &getFront() const;/訪問(wèn)隊(duì)首元素599.2 線性群體 9.2.5 隊(duì)列類

50、C+語(yǔ)言程序設(shè)計(jì)（第4版），鄭莉，清華大學(xué)/測(cè)試隊(duì)列狀態(tài)int getLength() const;/求隊(duì)列長(zhǎng)度bool isEmpty() const;/判隊(duì)隊(duì)列空否bool isFull() const;/判斷隊(duì)列滿否;/構(gòu)造函數(shù)，初始化隊(duì)頭指針、隊(duì)尾指針、元素個(gè)數(shù)template Queue:Queue() : front(0), rear(0), count(0) template void Queue:insert (const T& item) /向隊(duì)尾插入元素assert(count != SIZE);count+;/元素個(gè)數(shù)增1listrear = item; /向隊(duì)尾

51、插入元素rear = (rear + 1) % SIZE; /隊(duì)尾指針增1，用取余運(yùn)算實(shí)現(xiàn)循環(huán)隊(duì)列template T Queue:remove() assert(count != 0);int temp = front;/記錄下原先的隊(duì)首指針 count-;/元素個(gè)數(shù)自減 front = (front + 1) % SIZE;/隊(duì)首指針增1。取余以實(shí)現(xiàn)循環(huán)隊(duì)列 return listtemp;/返回首元素值609.2 線性群體 9.2.5 隊(duì)列類例9-10（續(xù)）C+語(yǔ)言程序設(shè)計(jì)（第4版），鄭莉，清華大學(xué)template const T &Queue:getFront() const

52、return listfront;template int Queue:getLength() const /返回隊(duì)列元素個(gè)數(shù)return count;template bool Queue:isEmpty() const /測(cè)試隊(duì)空否return count = 0;template bool Queue:isFull() const /測(cè)試隊(duì)滿否return count = SIZE;template void Queue:clear() /清空隊(duì)列count = 0;front = 0; rear = 0; #endif /QUEUE_H619.2 線性群體 9.2.5 隊(duì)列類例9-10

53、（續(xù)）C+語(yǔ)言程序設(shè)計(jì)（第4版），鄭莉，清華大學(xué)9.3 群體數(shù)據(jù)的組織 插入排序 選擇排序 交換排序 順序查找 折半查找629.3 群體數(shù)據(jù)的組織C+語(yǔ)言程序設(shè)計(jì)（第4版），鄭莉，清華大學(xué)排序（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ù)元素。 在排序過(guò)程中需要完成兩種基本操作： 比較兩個(gè)數(shù)的大小 調(diào)整元素在序列中的位置639.3 群體數(shù)據(jù)的組織C+語(yǔ)言程

54、序設(shè)計(jì)（第4版），鄭莉，清華大學(xué)內(nèi)部排序與外部排序 內(nèi)部排序：待排序的數(shù)據(jù)元素存放在計(jì)算機(jī)內(nèi)存中進(jìn)行的排序過(guò)程。 外部排序：待排序的數(shù)據(jù)元素?cái)?shù)量很大，以致內(nèi)存存中一次不能容納全部數(shù)據(jù)，在排序過(guò)程中尚需對(duì)外存進(jìn)行訪問(wèn)的排序過(guò)程。649.3 群體數(shù)據(jù)的組織C+語(yǔ)言程序設(shè)計(jì)（第4版），鄭莉，清華大學(xué)內(nèi)部排序方法 插入排序 選擇排序 交換排序659.3 群體數(shù)據(jù)的組織C+語(yǔ)言程序設(shè)計(jì)（第4版），鄭莉，清華大學(xué)插入排序的基本思想 每一步將一個(gè)待排序元素按其關(guān)鍵字值的大小插入到已排序序列的適當(dāng)位置上，直到待排序元素插入完為止。669.3 群體數(shù)據(jù)的組織 9.3.1 插入排序初始狀態(tài)： 5 4 10 20

55、12 3插入操作：1 4 4 5 10 20 12 32 10 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 20C+語(yǔ)言程序設(shè)計(jì)（第4版），鄭莉，清華大學(xué)67例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 - 1;j-;aj = temp;9.3 群體數(shù)據(jù)的組織 9.3.1 插入排序C+語(yǔ)言程序設(shè)計(jì)（第4版），鄭莉，

56、清華大學(xué)選擇排序的基本思想 每次從待排序序列中選擇一個(gè)關(guān)鍵字最小的元素，（當(dāng)需要按關(guān)鍵字升序排列時(shí)），順序排在已排序序列的最后，直至全部排完。689.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 次選擇后，將選出的那個(gè)記錄與第 i 個(gè)記錄做交換。3 4 5 20 12 10.C+語(yǔ)言程序設(shè)計(jì)（第4版），鄭莉，清華大學(xué)69例9-12 簡(jiǎn)單選擇排序函數(shù)模板template void mySwap(T &x, T &y) T temp = x;x = y;y = temp;template

57、 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);9.3 群體數(shù)據(jù)的組織 9.3.2 選擇排序C+語(yǔ)言程序設(shè)計(jì)（第4版），鄭莉，清華大學(xué)交換排序的基本思想 兩兩比較待排序序列中的元素，并交換不滿足順序要求的各對(duì)元素，直到全部滿足順序要求為止。709.3 群體數(shù)據(jù)的組織 9.3.3 交換排序C+語(yǔ)言程序設(shè)計(jì)（第4版），

58、鄭莉，清華大學(xué)最簡(jiǎn)單的交換排序方法起泡排序 對(duì)具有n個(gè)元素的序列按升序進(jìn)行起泡排序的步驟： 首先將第一個(gè)元素與第二個(gè)元素進(jìn)行比較，若為逆序，a則將兩元素交換。然后比較第二、第三個(gè)元素，依次類推，直到第n-1和第n個(gè)元素進(jìn)行了比較和交換。此過(guò)程稱為第一趟起泡排序。經(jīng)過(guò)第一趟，最大的元素便被交換到第n個(gè)位置。 對(duì)前n-1個(gè)元素進(jìn)行第二趟起泡排序，將其中最大元素交換到第n-1個(gè)位置。 如此繼續(xù)，直到某一趟排序未發(fā)生任何交換時(shí)，排序完畢。對(duì)n個(gè)元素的序列，起泡排序最多需要進(jìn)行n-1趟。719.3 群體數(shù)據(jù)的組織 9.3.3 交換排序C+語(yǔ)言程序設(shè)計(jì)（第4版），鄭莉，清華大學(xué)起泡排序舉例 對(duì)整數(shù)序列 8

59、 5 2 4 3 按升序排序729.3 群體數(shù)據(jù)的組織 9.3.3 交換排序8524352438243582345823458初始狀態(tài)第一趟結(jié)果第二趟結(jié)果第三趟結(jié)果第四趟結(jié)果小的逐漸上升每趟沉下一個(gè)最大的C+語(yǔ)言程序設(shè)計(jì)（第4版），鄭莉，清華大學(xué)例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) int lastExchangeIndex = 0; for (int

60、 j = 0; j i; j+) if (aj + 1 aj) mySwap(aj, aj + 1); lastExchangeIndex = j; i = lastExchangeIndex;739.3 群體數(shù)據(jù)的組織 9.3.3 交換排序C+語(yǔ)言程序設(shè)計(jì)（第4版），鄭莉，清華大學(xué)9.3.4 順序查找 其基本思想 從序列的首元素開(kāi)始，逐個(gè)元素與待查找的關(guān)鍵字進(jìn)行比較，直到找到相等的。若整個(gè)序列中沒(méi)有與待查找關(guān)鍵字相等的元素，就是查找不成功。 例9-14順序查找函數(shù)模板749.3 群體數(shù)據(jù)的組織template int seqSearch(const T list, int n, const T &key) for(int i = 0; i n; i+)if (listi = key)return i; return -1; C+語(yǔ)言程序設(shè)計(jì)（第4版），鄭莉，清華大學(xué)折半查找（二分法查找） 對(duì)于已按關(guān)鍵字排序的序列，經(jīng)過(guò)一次比較，可將序列分割成兩部分，然后只在有可能包含待查元素的一部分中繼續(xù)查找，并根據(jù)試探結(jié)果繼續(xù)分割，逐步縮小查找范圍，直至找到