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

1、第九章第九章 群體類群體類和群體數(shù)據(jù)的組織和群體數(shù)據(jù)的組織C+C+語(yǔ)言程序設(shè)計(jì)語(yǔ)言程序設(shè)計(jì)說(shuō)明說(shuō)明目錄目錄群體的概念群體的概念群體是指由多個(gè)數(shù)據(jù)元素組成的集合體。群體是指由多個(gè)數(shù)據(jù)元素組成的集合體。群體可以分為兩個(gè)大類：群體可以分為兩個(gè)大類：線性群體線性群體和和非線性群非線性群體體。線性群體中的元素按位置排列有序，可以線性群體中的元素按位置排列有序，可以區(qū)分為第一個(gè)元素、第二個(gè)元素等。區(qū)分為第一個(gè)元素、第二個(gè)元素等。非線性群體不用位置順序來(lái)標(biāo)識(shí)元素。非線性群體不用位置順序來(lái)標(biāo)識(shí)元素。線性群體中的元素次序與其位置關(guān)系線性群體中的元素次序與其位置關(guān)系是對(duì)應(yīng)的。在線性群體中，又可按照訪問(wèn)是對(duì)應(yīng)的。在

2、線性群體中，又可按照訪問(wèn)元素的不同方法分為元素的不同方法分為直接訪問(wèn)直接訪問(wèn)、順序訪問(wèn)順序訪問(wèn)和和索引訪問(wèn)索引訪問(wèn)。第一個(gè)元素第二個(gè)元素第三個(gè)元素最后一個(gè)元素群體類群體類 直接訪問(wèn)群體直接訪問(wèn)群體-數(shù)組類數(shù)組類 順序訪問(wèn)群體順序訪問(wèn)群體-鏈表類鏈表類 棧類棧類 隊(duì)列類隊(duì)列類群群體數(shù)據(jù)的組織體數(shù)據(jù)的組織插入排序插入排序 選擇排序選擇排序 交換排序交換排序順序查找順序查找 折半查找折半查找5本章主要內(nèi)容本章主要內(nèi)容l模板模板l群體類群體類l群體數(shù)據(jù)的組織群體數(shù)據(jù)的組織l小結(jié)與復(fù)習(xí)建議小結(jié)與復(fù)習(xí)建議9.1 模板模板lC+C+最重要的特性之一就是代碼重用，為了實(shí)現(xiàn)代碼重最重要的特性之一就是代碼重用，為

3、了實(shí)現(xiàn)代碼重用，代碼必須具有通用性。用，代碼必須具有通用性。 通用代碼需要不受數(shù)據(jù)類型的影響，并且可以自通用代碼需要不受數(shù)據(jù)類型的影響，并且可以自動(dòng)適應(yīng)數(shù)據(jù)類型的變化。這種程序設(shè)計(jì)類型稱為參數(shù)動(dòng)適應(yīng)數(shù)據(jù)類型的變化。這種程序設(shè)計(jì)類型稱為參數(shù)化程序設(shè)計(jì)?；绦蛟O(shè)計(jì)。l模板是模板是C+C+支持參數(shù)化程序設(shè)計(jì)的工具，通過(guò)它可以實(shí)支持參數(shù)化程序設(shè)計(jì)的工具，通過(guò)它可以實(shí)現(xiàn)參數(shù)化多態(tài)性。現(xiàn)參數(shù)化多態(tài)性。 所謂參數(shù)化多態(tài)性，就是將程序所處理的對(duì)象的類所謂參數(shù)化多態(tài)性，就是將程序所處理的對(duì)象的類型參數(shù)化，使得一段程序可以用于處理多種不同類型型參數(shù)化，使得一段程序可以用于處理多種不同類型的對(duì)象。的對(duì)象。函數(shù)模板函

4、數(shù)模板類模板類模板9.1.1 函數(shù)模板函數(shù)模板l函數(shù)模板可以用來(lái)創(chuàng)建一個(gè)通用功能的函函數(shù)模板可以用來(lái)創(chuàng)建一個(gè)通用功能的函數(shù)，以支持多種不同形參，進(jìn)一步簡(jiǎn)化重?cái)?shù)，以支持多種不同形參，進(jìn)一步簡(jiǎn)化重載函數(shù)的函數(shù)體設(shè)計(jì)。載函數(shù)的函數(shù)體設(shè)計(jì)。l定義方法：定義方法：template 函數(shù)定義函數(shù)定義 templatetemplate T T abs(abs(T T x) x) return x 0? -x : x; return x 0? -x : x; 8其中：其中： template為模板關(guān)鍵字。為模板關(guān)鍵字。 模板參數(shù)表中的類型為參數(shù)化類型，也稱可變類型模板參數(shù)表中的類型為參數(shù)化類型，也稱可變類型，

5、類型名為，類型名為class (或或typename)；模板參數(shù)表中的類模板參數(shù)表中的類型也可包含普通類型。型也可包含普通類型。求絕對(duì)值函數(shù)的模板求絕對(duì)值函數(shù)的模板#include #include using namespace std;using namespace std;templatetemplate T T abs(abs(T T x) x) return x 0? -x : x;return x 0? -x : x; intint main() main() intint n = -5; n = -5;double d = -5.5;double d = -5.5;coutcou

6、t abs(abs(n n) ) endlendl; ;coutcout abs(abs(d d) ) endlendl; ;return 0;return 0; 運(yùn)行結(jié)果：運(yùn)行結(jié)果：5 55.55.5求絕對(duì)值函數(shù)的模板分析求絕對(duì)值函數(shù)的模板分析l編譯器從調(diào)用編譯器從調(diào)用abs()時(shí)實(shí)參的類型，推導(dǎo)出時(shí)實(shí)參的類型，推導(dǎo)出函數(shù)模板的類型參數(shù)。例如，對(duì)于調(diào)用表函數(shù)模板的類型參數(shù)。例如，對(duì)于調(diào)用表達(dá)式達(dá)式abs(n)，由于實(shí)參，由于實(shí)參n為為int型，所以推型，所以推導(dǎo)出模板中類型參數(shù)導(dǎo)出模板中類型參數(shù)T為為int。l當(dāng)類型參數(shù)的含義確定后，編譯器將以函當(dāng)類型參數(shù)的含義確定后，編譯器將以函數(shù)模板為樣

7、板，生成一個(gè)函數(shù)：數(shù)模板為樣板，生成一個(gè)函數(shù)：int abs(int x) return x 0 ? x : x;函數(shù)模板的重載函數(shù)模板的重載C+規(guī)定：函數(shù)模板可以重載。它既可以用函規(guī)定：函數(shù)模板可以重載。它既可以用函數(shù)模板重載，也可以用普通函數(shù)重載。數(shù)模板重載，也可以用普通函數(shù)重載。之所以允許之所以允許重載是因?yàn)楹瘮?shù)模板的參數(shù)重載是因?yàn)楹瘮?shù)模板的參數(shù)T T在實(shí)例化時(shí)實(shí)參類型在實(shí)例化時(shí)實(shí)參類型無(wú)隱式轉(zhuǎn)換功能。無(wú)隱式轉(zhuǎn)換功能。下面是函數(shù)模板重載的實(shí)例：下面是函數(shù)模板重載的實(shí)例： template /求兩個(gè)同類型求兩個(gè)同類型T的變量中的最大者的變量中的最大者 T max(T x, T y) ret

8、urn(xy)?x:y;template /重載 max 函數(shù)模板，求三個(gè)同類型 T 的變量中的最大者 T max(T x, T y, T z) T t; t=(xy)?x:y; return(tz)?t:z; 在下面的函數(shù)調(diào)用中： void fun(int i, char c, float f) coutmax(i,i); /正確! coutmax(c,c); /正確! coutmax(i,c); /錯(cuò)誤! 采用函數(shù)模板生成的模板函數(shù)虛實(shí)結(jié)合時(shí)無(wú)隱式類型轉(zhuǎn)換功能 coutmax(f,i); /錯(cuò)誤! 采用函數(shù)模板生成的模板函數(shù)虛實(shí)結(jié)合時(shí)無(wú)隱式類型轉(zhuǎn)換功能 / 上例代碼中的上例代碼中的max(

9、i,c)和和max(f,i)，由于模板函數(shù)在調(diào)用時(shí)，由于模板函數(shù)在調(diào)用時(shí)其參數(shù)類型不同，所以編譯器報(bào)錯(cuò)。其參數(shù)類型不同，所以編譯器報(bào)錯(cuò)。欲解決上述問(wèn)題，可用一普通函數(shù)重載函數(shù)模板，欲解決上述問(wèn)題，可用一普通函數(shù)重載函數(shù)模板，此時(shí)，此時(shí)，只需聲明該普通函數(shù)的接口即可。請(qǐng)看下述示例代碼：只需聲明該普通函數(shù)的接口即可。請(qǐng)看下述示例代碼：template /函數(shù)模板的定義函數(shù)模板的定義 T max(T x, T y) return(xy)?x:y; double max(double, double);/重載上述函數(shù)模重載上述函數(shù)模板，重載時(shí)只需給出函數(shù)接口板，重載時(shí)只需給出函數(shù)接口/測(cè)試函數(shù) voi

10、d main() int x=3,y=4; long l=5; double a=1.1, b=3.4; coutmax(x,y)endl; /調(diào)用模板函數(shù)，模板參數(shù)類型為 int coutmax(a,b)endl; /調(diào)用模板函數(shù)，模板參數(shù)類型為 double coutmax(l,a)endl; /調(diào)用重載的模板函數(shù)，虛實(shí)結(jié)合時(shí)類型自動(dòng)進(jìn)行隱式轉(zhuǎn)換 / 在使用上述 template T max(T x, T y)函數(shù)模板時(shí)， 若模板參數(shù)的類型為char*，則此時(shí)模板函數(shù)為 char* max(char* x, char* y) return(xy)?(x):(y); /該語(yǔ)句為何語(yǔ)義？ 該函

11、數(shù)的作用是比較兩個(gè)字符串指針，而不是比較兩個(gè)指該函數(shù)的作用是比較兩個(gè)字符串指針，而不是比較兩個(gè)指針?biāo)赶虻淖址膬?nèi)容，這與我們所定義的函數(shù)模板的語(yǔ)義針?biāo)赶虻淖址膬?nèi)容，這與我們所定義的函數(shù)模板的語(yǔ)義相違背。相違背。 因此，此時(shí)須提供一個(gè)可以替換該函數(shù)模板實(shí)例的函數(shù)，因此，此時(shí)須提供一個(gè)可以替換該函數(shù)模板實(shí)例的函數(shù)，用來(lái)替換的函數(shù)稱為特定的模板函數(shù)，即：用來(lái)替換的函數(shù)稱為特定的模板函數(shù)，即：char* max(char* c1, char* c2) return (strcmp(c1,c2)?(c1):(c2); 9.1.2 類模板的作用類模板的作用 使用類模板使用戶可以為類聲明一種模使用

12、類模板使用戶可以為類聲明一種模式，使得類中的某些數(shù)據(jù)成員、某些成員函式，使得類中的某些數(shù)據(jù)成員、某些成員函數(shù)的參數(shù)、某些成員函數(shù)的返回值，能取任數(shù)的參數(shù)、某些成員函數(shù)的返回值，能取任意類型（包括基本類型的和用戶自定義類意類型（包括基本類型的和用戶自定義類型）。型）。l類模板：類模板：template template class class 類名類名 類成員聲明類成員聲明 l如果需要在類模板以外定義其成員函數(shù)，則要如果需要在類模板以外定義其成員函數(shù)，則要采用以下的形式：采用以下的形式：template template 類型名類型名 類名類名 :函數(shù)名函數(shù)名( (參數(shù)表參數(shù)表) )類模板的聲明

13、類模板的聲明template class StoreT& Store:getElem()例例9-2 類模板應(yīng)用舉例類模板應(yīng)用舉例#include #include #include #include using namespace std;using namespace std;/ / 結(jié)構(gòu)體結(jié)構(gòu)體StudentStudentstructstruct Student Student intint id; / id; /學(xué)號(hào)學(xué)號(hào) float float gpagpa; /; /平均分平均分; ; template class Store /class Store /類模板：實(shí)現(xiàn)對(duì)任意類型

14、數(shù)據(jù)進(jìn)行存取類模板：實(shí)現(xiàn)對(duì)任意類型數(shù)據(jù)進(jìn)行存取private:private:T item; / item / item用于存放任意類型的數(shù)據(jù)用于存放任意類型的數(shù)據(jù)boolbool haveValuehaveValue; / ; / haveValuehaveValue標(biāo)記標(biāo)記itemitem是否已被存入內(nèi)容是否已被存入內(nèi)容public:public:Store();Store();/ / 缺省形式（無(wú)形參）的構(gòu)造函數(shù)缺省形式（無(wú)形參）的構(gòu)造函數(shù)T &getElem();/提取數(shù)據(jù)函數(shù)提取數(shù)據(jù)函數(shù)void putElem(const T &x); / /存入數(shù)據(jù)函數(shù)存入數(shù)據(jù)函數(shù)

15、;/以下實(shí)現(xiàn)各成員函數(shù)。以下實(shí)現(xiàn)各成員函數(shù)。template template /缺省構(gòu)造函數(shù)的實(shí)現(xiàn)缺省構(gòu)造函數(shù)的實(shí)現(xiàn) Store:Store(): haveValue(falsehaveValue(false) ) 19template /template /提取數(shù)據(jù)函數(shù)的實(shí)現(xiàn)提取數(shù)據(jù)函數(shù)的實(shí)現(xiàn)T &Store:getElem() /如試圖提取未初始化的數(shù)據(jù)，則終止程序如試圖提取未初始化的數(shù)據(jù)，則終止程序if (!if (!haveValuehaveValue) ) coutcout No item present! No item present! endlendl; ;exit(

16、1);exit(1);/使程序完全退出，返回到操作系統(tǒng)。使程序完全退出，返回到操作系統(tǒng)。 return item; / return item; / 返回返回itemitem中存放的數(shù)據(jù)中存放的數(shù)據(jù) template template /存入數(shù)據(jù)函數(shù)的實(shí)現(xiàn)存入數(shù)據(jù)函數(shù)的實(shí)現(xiàn) void Store:putElem(const T &x) / / 將將haveValuehaveValue 置為置為truetrue，表示，表示itemitem中已存入數(shù)值中已存入數(shù)值haveValuehaveValue = true; = true;item = x;item = x;/ / 將將x x值存入

17、值存入itemitem intint main() main() Store s1, s2; s1, s2;s1.putElem(3);s1.putElem(3);s2.putElem(-7);s2.putElem(-7);coutcout s1.getElem() s2.getElem() s1.getElem() s2.getElem() endlendl; ;Student g = 1000, 23 ;Student g = 1000, 23 ;Store s3; s3;s3.putElem(g); s3.putElem(g); coutcout The student id is s3

18、.getElem().id The student id is s3.getElem().id endlendl; ;Store d;coutcout Retrieving object D. ; Retrieving object D. ;coutcout d.getElemd.getElem() () endlendl /由于由于d d未經(jīng)初始化未經(jīng)初始化, ,執(zhí)行函數(shù)執(zhí)行函數(shù)D.getElementD.getElement()()時(shí)導(dǎo)致程序終止時(shí)導(dǎo)致程序終止return 0;return 0; 9.2 群體類群體類線性群體線性群體群體的概念群體的概念直接訪問(wèn)群體直接訪問(wèn)群體-數(shù)組類數(shù)組類

19、順序訪問(wèn)群體順序訪問(wèn)群體-鏈表類鏈表類棧類棧類隊(duì)列類隊(duì)列類9.2.1 群體的概念群體的概念群體是指由多個(gè)數(shù)據(jù)元素組成的集合體。群體是指由多個(gè)數(shù)據(jù)元素組成的集合體。群體可以分為兩個(gè)大類：群體可以分為兩個(gè)大類：線性群體線性群體和和非線性群非線性群體體。線性群體中的元素按位置排列有序，可以線性群體中的元素按位置排列有序，可以區(qū)分為第一個(gè)元素、第二個(gè)元素等。區(qū)分為第一個(gè)元素、第二個(gè)元素等。非線性群體不用位置順序來(lái)標(biāo)識(shí)元素。非線性群體不用位置順序來(lái)標(biāo)識(shí)元素。線性群體的概念線性群體的概念 線性群體中的元素次序與其位置關(guān)系是線性群體中的元素次序與其位置關(guān)系是對(duì)應(yīng)的。在線性群體中，又可按照訪問(wèn)元素對(duì)應(yīng)的。在線

20、性群體中，又可按照訪問(wèn)元素的不同方法分為直接訪問(wèn)、順序訪問(wèn)和索引的不同方法分為直接訪問(wèn)、順序訪問(wèn)和索引訪問(wèn)。訪問(wèn)。 在本章我們只介紹直接訪問(wèn)和順序訪問(wèn)。在本章我們只介紹直接訪問(wèn)和順序訪問(wèn)。第一個(gè)元素第二個(gè)元素第三個(gè)元素最后一個(gè)元素9.2.2 數(shù)組數(shù)組l靜態(tài)數(shù)組是具有固定元素個(gè)數(shù)的群體，其靜態(tài)數(shù)組是具有固定元素個(gè)數(shù)的群體，其中的元素可以通過(guò)下標(biāo)直接訪問(wèn)。中的元素可以通過(guò)下標(biāo)直接訪問(wèn)。 缺點(diǎn)：大小在編譯時(shí)就已經(jīng)確定，在運(yùn)缺點(diǎn)：大小在編譯時(shí)就已經(jīng)確定，在運(yùn)行時(shí)無(wú)法修改。行時(shí)無(wú)法修改。l動(dòng)態(tài)數(shù)組由一系列位置連續(xù)的，任意數(shù)量動(dòng)態(tài)數(shù)組由一系列位置連續(xù)的，任意數(shù)量相同類型的元素組成。相同類型的元素組成。 優(yōu)

21、點(diǎn)：其元素個(gè)數(shù)可在程序運(yùn)行時(shí)改變。優(yōu)點(diǎn)：其元素個(gè)數(shù)可在程序運(yùn)行時(shí)改變。l動(dòng)態(tài)數(shù)組類模板：例動(dòng)態(tài)數(shù)組類模板：例9-3（Array.h）# #ifndefifndef ARRAY_H ARRAY_H#define ARRAY_H#define ARRAY_H#include #include template class template / /數(shù)組類模板定義數(shù)組類模板定義class Array class Array private:private:T* * list;/ list;/用于存放動(dòng)態(tài)分配的數(shù)組內(nèi)存首地址用于存放動(dòng)態(tài)分配的數(shù)組內(nèi)存首地址intint size; size; /數(shù)組大小

22、（元素個(gè)數(shù)）數(shù)組大?。ㄔ貍€(gè)數(shù)）public:public:Array(intArray(int szsz = 50); = 50);/構(gòu)造函數(shù)構(gòu)造函數(shù)Array(constArray(const Array Array &a); &a);/拷貝構(gòu)造函數(shù)拷貝構(gòu)造函數(shù)Array();Array();/析構(gòu)函數(shù)析構(gòu)函數(shù)ArrayArray & operator & operator = (const Array (const Array & &rhsrhs); /); /重載重載=“=“T & operator & operator

23、( (intint i); / i); /重載重載”const const T & operator ( & operator (intint i) const; i) const;operator operator T * (); (); /重載到重載到T T* *類型的轉(zhuǎn)換類型的轉(zhuǎn)換operator const operator const T * () const; () const;intint getSizegetSize() const;() const;/取數(shù)組的大小取數(shù)組的大小void void resize(intresize(int szsz););/修改數(shù)

24、組的大小修改數(shù)組的大小;26數(shù)組類模板的構(gòu)造函數(shù)數(shù)組類模板的構(gòu)造函數(shù)/ / 構(gòu)造函數(shù)構(gòu)造函數(shù)template template Array:Array:Array(intArray(int szsz) ) /szsz為數(shù)組大?。ㄔ貍€(gè)數(shù)），應(yīng)當(dāng)非負(fù)為數(shù)組大小（元素個(gè)數(shù)），應(yīng)當(dāng)非負(fù) / / 將元素個(gè)數(shù)賦值給變量將元素個(gè)數(shù)賦值給變量sizesizesize = size = szsz; ; /動(dòng)態(tài)分配動(dòng)態(tài)分配sizesize個(gè)個(gè)T T類型的元素空間類型的元素空間list = new T size;list = new T size; 數(shù)組數(shù)組類模板的類模板的拷貝構(gòu)造函數(shù)拷貝構(gòu)造函數(shù)/拷貝構(gòu)造函數(shù)拷

25、貝構(gòu)造函數(shù)template template Array:Array:Array(constArray(const Array &a) Array &a) /從對(duì)象從對(duì)象a a取得數(shù)組大小，并賦值給當(dāng)前對(duì)象的成員取得數(shù)組大小，并賦值給當(dāng)前對(duì)象的成員size = a.size;/為對(duì)象申請(qǐng)內(nèi)存并進(jìn)行出錯(cuò)檢查為對(duì)象申請(qǐng)內(nèi)存并進(jìn)行出錯(cuò)檢查list = new Tsize; / / 動(dòng)態(tài)分配動(dòng)態(tài)分配n n個(gè)個(gè)T T類型的元素空間類型的元素空間/從對(duì)象從對(duì)象X X復(fù)制數(shù)組元素到本對(duì)象復(fù)制數(shù)組元素到本對(duì)象 for (int i = 0; i size; i+)listi = a.listi

26、; 淺拷貝淺拷貝 list sizeaa的數(shù)組元素占用的內(nèi)存拷貝前拷貝前 list sizeaa的數(shù)組元素占用的內(nèi)存拷貝后拷貝后 list sizebintint main() main() Array Array a(10); a(10); . . Array Array b(ab(a);); . . template template Array:Array(Array:Array(const Array& x) const Array& x) size = size = x.sizex.size; ; list = list = x.listx.list; ; templ

27、ate template Array:Array:Array(constArray(const Array &a) Array &a) size = a.size;list = new Tsize; for (int i = 0; i size; i+)listi = a.listi; 深拷貝深拷貝 list sizeaa的數(shù)組元素占用的內(nèi)存拷貝前拷貝前 list sizeaa的數(shù)組元素占用的內(nèi)存拷貝后拷貝后 list sizebb的數(shù)組元素占用的內(nèi)存數(shù)組數(shù)組類類模板模板的的重載重載=運(yùn)算符函數(shù)運(yùn)算符函數(shù)/重載重載“=”“=”運(yùn)算符運(yùn)算符template template Ar

28、ray &Array:Array &Array:operator = (const Array &rhs) if (&if (&rhsrhs != this) != this) if (size != if (size != rhs.sizerhs.size) ) delete list;delete list;/刪除數(shù)組原有內(nèi)存刪除數(shù)組原有內(nèi)存size = size = rhs.sizerhs.size; ;/設(shè)置設(shè)置本對(duì)象的數(shù)組大小本對(duì)象的數(shù)組大小list = new list = new TsizeTsize; /重新分配重新分配n n個(gè)元素的內(nèi)存

29、個(gè)元素的內(nèi)存 / /從對(duì)象從對(duì)象X X復(fù)制數(shù)組元素到本對(duì)象復(fù)制數(shù)組元素到本對(duì)象 for (for (intint i = 0; i size; i+) i = 0; i size; i+)listilisti = = rhs.listirhs.listi; return return * *this;this;/返回當(dāng)前對(duì)象的引用返回當(dāng)前對(duì)象的引用 數(shù)組數(shù)組類模板的類模板的重載下標(biāo)操作符函數(shù)重載下標(biāo)操作符函數(shù)template template T &Array:T &Array:operator (int n) assert(nassert(n = 0 & n = 0

30、& n size);/越界檢查越界檢查return return listnlistn; / /返回下標(biāo)為返回下標(biāo)為n n的數(shù)組元素的數(shù)組元素 template template const T &Array:const T &Array:operator (int n) const assert(nassert(n = 0 & n = 0 & n size); /越界檢查越界檢查return return listnlistn; / /返回下標(biāo)為返回下標(biāo)為n n的數(shù)組元素的數(shù)組元素 數(shù)組類的重載下標(biāo)操作符函數(shù)數(shù)組類的重載下標(biāo)操作符函數(shù)template

31、T& Array:operator (int n) / 檢查下標(biāo)是否越界檢查下標(biāo)是否越界 if (n size-1) Error(indexOutOfRange,n); / 返回下標(biāo)為返回下標(biāo)為n的數(shù)組元素的數(shù)組元素 return alistn;重載指針轉(zhuǎn)換操作符重載指針轉(zhuǎn)換操作符template template Array:Array:operator T * () return list;return list; /返回返回當(dāng)前對(duì)象中私有當(dāng)前對(duì)象中私有數(shù)組的首地址數(shù)組的首地址 template template Array:Array:operator const T * ()

32、const return list;return list; /返回返回當(dāng)前對(duì)象中私有當(dāng)前對(duì)象中私有數(shù)組的首地址數(shù)組的首地址 指針轉(zhuǎn)換運(yùn)算符的作用指針轉(zhuǎn)換運(yùn)算符的作用#include #include using namespace std;using namespace std;void void read(read(int *p, , intint n) n) for ( for (intint i = 0; i n; i+) i = 0; i pipi; intint main() main() int a10; read(read(a, 10);, 10); return 0; ret

33、urn 0; #include Array.h#include #include using namespace std;using namespace std;void void read(read(int *p, , intint n) n) for ( for (intint i = 0; i n; i+) i = 0; i pipi; intint main() main() Array a(10); read(read(a, 10);, 10); return 0; return 0; ArrayArray類的應(yīng)用類的應(yīng)用l例例9-4求范圍求范圍2N中的質(zhì)數(shù)，中的質(zhì)數(shù)，N在程序在程序

34、運(yùn)行時(shí)由鍵盤(pán)輸入。運(yùn)行時(shí)由鍵盤(pán)輸入。 質(zhì)數(shù)（質(zhì)數(shù)（prime numberprime number）又稱素?cái)?shù)，有無(wú)限個(gè)。一個(gè)大于）又稱素?cái)?shù)，有無(wú)限個(gè)。一個(gè)大于1 1的自然數(shù)，除了的自然數(shù)，除了1 1和它本身外，不能被其他自然數(shù)（質(zhì)數(shù)）和它本身外，不能被其他自然數(shù)（質(zhì)數(shù)）整除。整除。#include #include #include #include #include Array.husing namespace std;using namespace std;intint main() main() Array a(10);/ / 用來(lái)存放質(zhì)數(shù)的數(shù)組，初始狀態(tài)有用來(lái)存放質(zhì)數(shù)的數(shù)組，初始狀態(tài)有

35、1010個(gè)元素。個(gè)元素。intint n, count = 0; n, count = 0;coutcout = 2 as upper limit for prime numbers: ; = 2 as upper limit for prime numbers: ;cincin n; n;for (for (intint i = 2; i = n; i+) i = 2; i = n; i+) boolbool isPrimeisPrime = true; = true;for (for (intint j = 0; j count; j+) j = 0; j count; j+)if (i

36、% if (i % aj = 0) = 0) /若若i i被被ajaj 整除，說(shuō)明整除，說(shuō)明i i不是質(zhì)數(shù)不是質(zhì)數(shù)isPrimeisPrime = false; break; = false; break; if (if (isPrimeisPrime) ) if (count = if (count = a.getSizea.getSize()() a.resize(counta.resize(count * * 2); 2); acount+ = i; for (for (intint i = 0; i count; i+) i = 0; i count; i+)coutcout setw

37、(8) setw(8) aiai;coutcout endlendl; ;return 0; return 0; 9.2.3 鏈表鏈表l鏈表是一種動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)，可以用來(lái)表示鏈表是一種動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)，可以用來(lái)表示順序訪問(wèn)的線性群體。順序訪問(wèn)的線性群體。l鏈表是由系列鏈表是由系列結(jié)點(diǎn)結(jié)點(diǎn)組成的，結(jié)點(diǎn)可以在運(yùn)組成的，結(jié)點(diǎn)可以在運(yùn)行時(shí)動(dòng)態(tài)生成。行時(shí)動(dòng)態(tài)生成。l每一個(gè)結(jié)點(diǎn)包括每一個(gè)結(jié)點(diǎn)包括數(shù)據(jù)域數(shù)據(jù)域和指向鏈表中下一和指向鏈表中下一個(gè)結(jié)點(diǎn)的個(gè)結(jié)點(diǎn)的指針指針（即下一個(gè)結(jié)點(diǎn)的地址）。（即下一個(gè)結(jié)點(diǎn)的地址）。如果鏈表每個(gè)結(jié)點(diǎn)中只有一個(gè)指向后繼結(jié)如果鏈表每個(gè)結(jié)點(diǎn)中只有一個(gè)指向后繼結(jié)點(diǎn)的指針，則該鏈表稱為單鏈表。點(diǎn)

38、的指針，則該鏈表稱為單鏈表。單鏈表單鏈表 data1 data1 data2 data2 data3 data3 datandatan NULL NULLheadheadrearrear單鏈表的結(jié)點(diǎn)類模板單鏈表的結(jié)點(diǎn)類模板template class template class Node class Node private:private: Node Node * *next;next;public:public: T data; data; Node(constNode(const T & T &item,Nodeitem,Node* * next = 0); next

39、= 0); void void insertAfter(NodeinsertAfter(Node * *p);p); Node Node * *deleteAfterdeleteAfter();(); Node Node * *nextNodenextNode() const;() const; ; 41在結(jié)點(diǎn)之后插入一個(gè)結(jié)點(diǎn)在結(jié)點(diǎn)之后插入一個(gè)結(jié)點(diǎn) data1 data2 p datatemplate template void Node:void Node:insertAfter(Node *p) /p /p節(jié)點(diǎn)指針域指向當(dāng)前節(jié)點(diǎn)的后繼節(jié)點(diǎn)節(jié)點(diǎn)指針域指向當(dāng)前節(jié)點(diǎn)的后繼節(jié)點(diǎn) p-next =

40、p-next = nextnext; ; next = p; / next = p; /當(dāng)前節(jié)點(diǎn)的指針域指向當(dāng)前節(jié)點(diǎn)的指針域指向p p 刪除結(jié)點(diǎn)之后的結(jié)點(diǎn)刪除結(jié)點(diǎn)之后的結(jié)點(diǎn) data1 data2 data3Node Node * *Node:Node:deleteAfter(void) Node Node * *tempPtrtempPtr = next; = next; if (next = 0) if (next = 0) return 0; return 0; next = next = tempPtrtempPtr-next; -next; return return tempPtr

41、tempPtr; ; tempPtr鏈表的基本操作鏈表的基本操作l生成結(jié)點(diǎn)生成結(jié)點(diǎn)l插入結(jié)點(diǎn)插入結(jié)點(diǎn)l查找結(jié)點(diǎn)查找結(jié)點(diǎn)l刪除結(jié)點(diǎn)刪除結(jié)點(diǎn)l遍歷鏈表遍歷鏈表l清空鏈表清空鏈表鏈表類模板鏈表類模板( (例例9-6)9-6)# #ifndefifndef LINKEDLIST_H LINKEDLIST_H#define LINKEDLIST_H#define LINKEDLIST_H#include #include Node.hNode.h template template class class LinkedListLinkedList private:private:/數(shù)據(jù)成員：數(shù)據(jù)成員：N

42、ode Node * *front, front, * *rearrearNode Node * *prevPtrprevPtr, , * *currPtrcurrPtr; ; intint size; size;intint position; position;Node Node * *newNode(constnewNode(const T T & &item,Nodeitem,Node * *ptrNextptrNext=NULL);=NULL); void void freeNode(NodefreeNode(Node * *p);p);void void copy(

43、constcopy(const LinkedListLinkedList &L); &L);public:public:LinkedListLinkedList();();LinkedList(constLinkedList(const LinkedListLinkedList &L); &L); LinkedListLinkedList();();LinkedListLinkedList & operator = (const & operator = (const LinkedListLinkedList &L); &L);

44、intint getSizegetSize() const;() const;boolbool isEmptyisEmpty() const;() const;void void reset(intreset(int pos = 0 pos = 0void next();void next();boolbool endOfListendOfList() const;() const;intint currentPosition(voidcurrentPosition(void) const;) const;void void insertFront(constinsertFront(const

45、 T &item); T &item);void void insertRear(constinsertRear(const T &item); T &item);void void insertAt(constinsertAt(const T &item); T &item);void void insertAfter(constinsertAfter(const T &item); T &item);T T deleteFrontdeleteFront();();void void deleteCurrentdeleteCur

46、rent();();T& data();T& data();const T& data() constconst T& data() constvoid clear();void clear();# #endifendif /LINKEDLIST_H /LINKEDLIST_H鏈表類應(yīng)用舉例鏈表類應(yīng)用舉例(例例9-7)l從鍵盤(pán)輸入從鍵盤(pán)輸入10個(gè)整數(shù)，用這些整數(shù)值作為結(jié)點(diǎn)個(gè)整數(shù)，用這些整數(shù)值作為結(jié)點(diǎn)數(shù)據(jù)，生成一個(gè)鏈表，按順序輸出鏈表中結(jié)點(diǎn)數(shù)據(jù)，生成一個(gè)鏈表，按順序輸出鏈表中結(jié)點(diǎn)的數(shù)值。的數(shù)值。l然后從鍵盤(pán)輸入一個(gè)待查找整數(shù)，在鏈表中查然后從鍵盤(pán)輸入一個(gè)待查找整數(shù)

47、，在鏈表中查找該整數(shù)，若找到則刪除該整數(shù)所在的結(jié)點(diǎn)（找該整數(shù)，若找到則刪除該整數(shù)所在的結(jié)點(diǎn)（如果出現(xiàn)多次，全部刪除）。如果出現(xiàn)多次，全部刪除）。l然后輸出刪除結(jié)點(diǎn)以后的鏈表。在程序結(jié)束之然后輸出刪除結(jié)點(diǎn)以后的鏈表。在程序結(jié)束之前清空鏈表。前清空鏈表。/9_7.cpp/9_7.cpp#include #include #include #include LinkedList.hLinkedList.h using namespace std;using namespace std;intint main() main() LinkedListLinkedList list; list;for (

48、for (intint i = 0; i 10; i+) i = 0; i item; item;list.insertFront(itemlist.insertFront(item);); coutcout List: ; List: ;list.resetlist.reset();();while (!while (!list.endOfListlist.endOfList() () coutcout list.datalist.data() ;() ;list.nextlist.next();(); coutcout endlendl; ;intint key; key;coutcout

49、 Please enter some integer key; key;list.resetlist.reset();();while (!while (!list.endOfListlist.endOfList() () if (if (list.datalist.data() = key) () = key) list.deleteCurrentlist.deleteCurrent();();list.nextlist.next();(); coutcout List: ; List: ;list.resetlist.reset();();while (!while (!list.endO

50、fListlist.endOfList() () coutcout list.datalist.data() ;() ;list.nextlist.next coutcout endlendl; ;return 0;return 0; 9.2.4 特殊的線性群體特殊的線性群體棧棧棧是只能從一端訪問(wèn)的線性群體，可以棧是只能從一端訪問(wèn)的線性群體，可以訪問(wèn)的這一端稱棧頂，另一端稱棧底。訪問(wèn)的這一端稱棧頂，另一端稱棧底。ana2a1入棧出棧棧頂棧底棧的應(yīng)用舉例棧的應(yīng)用舉例函數(shù)調(diào)用函數(shù)調(diào)用main調(diào)調(diào)fun(參數(shù)參數(shù))結(jié)束結(jié)束fun(參數(shù)參數(shù))返回返回參數(shù)參數(shù)當(dāng)前現(xiàn)場(chǎng)當(dāng)前現(xiàn)場(chǎng)返回地址返回地址入棧入棧當(dāng)前

51、現(xiàn)場(chǎng)當(dāng)前現(xiàn)場(chǎng)返回地址返回地址出棧出棧參數(shù)參數(shù)出棧出棧當(dāng)前現(xiàn)場(chǎng)當(dāng)前現(xiàn)場(chǎng) 返回地址返回地址49棧的基本狀態(tài)棧的基本狀態(tài)l棧空?？?棧中沒(méi)有元素棧中沒(méi)有元素l棧滿棧滿 棧中元素個(gè)數(shù)達(dá)到上限棧中元素個(gè)數(shù)達(dá)到上限l一般狀態(tài)一般狀態(tài) 棧中有元素，但未達(dá)到棧滿狀態(tài)棧中有元素，但未達(dá)到棧滿狀態(tài)棧頂ana1a0入棧出棧數(shù)組下標(biāo)maxn10一般狀態(tài)一般狀態(tài)棧頂入棧出棧數(shù)組下標(biāo)初始狀態(tài)（?？粘跏紶顟B(tài)（棧空）maxn10棧頂amaxana1a0入棧出棧數(shù)組下標(biāo)maxn10棧滿狀態(tài)棧滿狀態(tài)5051棧的基本操作棧的基本操作l初始化初始化l入棧入棧l出棧出棧l清空棧清空棧l訪問(wèn)棧頂元素訪問(wèn)棧頂元素l檢測(cè)棧的狀態(tài)（滿、空）檢

52、測(cè)棧的狀態(tài)（滿、空）棧類模板棧類模板(例例9-8)/Stack.hStack.h# #ifndefifndef STACK_H STACK_H#define STACK_H#define STACK_H#include #include template class T, template SIZE = 50class Stack class Stack private:private:T T listSIZElistSIZE;intint top; top;public:public:Stack();Stack();void void push(constpush(const T &

53、item); T &item);T pop();T pop();void clear();void clear();const T &peek() const;const T &peek() const;boolbool isEmptyisEmpty() const;() const;boolbool isFullisFull() const;() const;/類的實(shí)現(xiàn)略類的實(shí)現(xiàn)略棧的應(yīng)用棧的應(yīng)用例例9.9 一個(gè)簡(jiǎn)單的整數(shù)計(jì)算器一個(gè)簡(jiǎn)單的整數(shù)計(jì)算器實(shí)現(xiàn)一個(gè)簡(jiǎn)單的整數(shù)計(jì)算器，能夠進(jìn)行加、實(shí)現(xiàn)一個(gè)簡(jiǎn)單的整數(shù)計(jì)算器，能夠進(jìn)行加、減、乘、除和乘方運(yùn)算。使用時(shí)算式采用后綴輸減、

54、乘、除和乘方運(yùn)算。使用時(shí)算式采用后綴輸入法，每個(gè)操作數(shù)、操作符之間都以空白符分隔。入法，每個(gè)操作數(shù)、操作符之間都以空白符分隔。例如，若要計(jì)算例如，若要計(jì)算3+5則輸入則輸入3 5 +。乘方運(yùn)算。乘方運(yùn)算符用符用表示。每次運(yùn)算在前次結(jié)果基礎(chǔ)上進(jìn)行，表示。每次運(yùn)算在前次結(jié)果基礎(chǔ)上進(jìn)行，若要將前次運(yùn)算結(jié)果清除，可鍵入若要將前次運(yùn)算結(jié)果清除，可鍵入c。當(dāng)鍵入。當(dāng)鍵入q時(shí)程序結(jié)束。時(shí)程序結(jié)束。/Calculator.hCalculator.h# #ifndefifndef CALCULATOR_H CALCULATOR_H#define CALCULATOR_H#define CALCULATOR_H#

55、include #include Stack.hStack.h / / 包含棧類模板定義文件包含棧類模板定義文件class Calculator class Calculator /計(jì)算器類計(jì)算器類private:private:Stack s; s;/ / 操作數(shù)棧操作數(shù)棧void void enter(doubleenter(double num); num); /將操作數(shù)將操作數(shù)numnum壓入棧壓入棧/連續(xù)將兩個(gè)操作數(shù)彈出棧，放在連續(xù)將兩個(gè)操作數(shù)彈出棧，放在opnd1opnd1和和opnd2opnd2中中boolbool getTwoOperands(doublegetTwoOpera

56、nds(double &opnd1, double &opnd2); &opnd1, double &opnd2);void void compute(charcompute(char op); op); /執(zhí)行由操作符執(zhí)行由操作符opop指定的運(yùn)算指定的運(yùn)算public:public:void run();void run();/運(yùn)行計(jì)算器程序運(yùn)行計(jì)算器程序void clear();void clear();/清空操作數(shù)棧清空操作數(shù)棧;# #endifendif /CALCULATOR_H /CALCULATOR_H/Calculator.cppCalcula

57、tor.cpp#include #include Calculator.hCalculator.h #include #include #include #include #include #include using namespace std;using namespace std;/工具函數(shù)，用于將字符串轉(zhuǎn)換為實(shí)數(shù)工具函數(shù)，用于將字符串轉(zhuǎn)換為實(shí)數(shù)inline double inline double stringToDouble(conststringToDouble(const string & string &strstr) ) istringstreamistrin

58、gstream stream(strstream(str););/字符串輸入流字符串輸入流double result;double result;stream result;stream result;return result;return result; void void Calculator:enter(doubleCalculator:enter(double num) num) /將操作數(shù)將操作數(shù)numnum壓入棧壓入棧s.push(nums.push(num);); boolbool Calculator:getTwoOperands(doubleCalculator:getTw

59、oOperands(double &opnd1, double &opnd1, double &opnd2) &opnd2) if (if (s.isEmptys.isEmpty() () /檢查棧是否空檢查棧是否空cerrcerr Missing operand! Missing operand! endlendl; ;return false;return false; opnd1 = opnd1 = s.pops.pop();(); /將右操作數(shù)彈出棧將右操作數(shù)彈出棧if (if (s.isEmptys.isEmpty() () /檢查棧是否空檢查棧是否空

60、cerrcerr Missing operand! Missing operand! endlendl; ;return false;return false; opnd2 = opnd2 = s.pops.pop();(); /將左操作數(shù)彈出棧將左操作數(shù)彈出棧return true;return true; 56void Calculator:compute(char op) void Calculator:compute(char op) /執(zhí)行運(yùn)算執(zhí)行運(yùn)算double operand1, operand2;double operand1, operand2;boolbool result = result = getTwoOperandsgetTwoOperands(operand1, operand2); (operand1, operand2); if (result) if (result) /如果成功，執(zhí)行運(yùn)算并將運(yùn)算結(jié)果壓入棧如果成功，執(zhí)行運(yùn)算并將運(yùn)算結(jié)果壓入棧switch(op) switch(op) case +: case +: s.pushs.push(operand2 + operand1); break;(operand2 + operand1); break;case -: ca