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

第九章群體類和群體數(shù)據(jù)(shùjù)的組織共一百零一頁9.1函數(shù)模板與類模板9.2線性群體9.3群體數(shù)據(jù)的組織9.4綜合實(shí)例——對個人銀行賬戶管理程序的改進(jìn)(gǎijìn)9.5深度探索9.6小結(jié)2目錄(mùlù)共一百零一頁函數(shù)模板(múbǎn)可以用來創(chuàng)建一個通用功能的函數(shù)，以支持多種不同形參，進(jìn)一步簡化重載函數(shù)的函數(shù)體設(shè)計。定義方法：template<模板參數(shù)表>函數(shù)定義模板參數(shù)表的內(nèi)容類型參數(shù)：class（或typename）標(biāo)識符常量參數(shù)：類型說明符標(biāo)識符模板參數(shù)：template<參數(shù)表>class

標(biāo)識符39.1.1函數(shù)(hánshù)模板9.1函數(shù)模板與類模板共一百零一頁#include<iostream>usingnamespacestd;template<typenameT>Tabs(Tx){ returnx<0?-x:x;}intmain(){ intn=-5; doubled=-5.5; cout<<abs(n)<<endl; cout<<abs(d)<<endl; return0;}4例：求絕對值函數(shù)(hánshù)的模板9.1函數(shù)(hánshù)模板與類模板——9.1.1函數(shù)模板運(yùn)行結(jié)果：55.5共一百零一頁編譯器從調(diào)用abs()時實(shí)參的類型，推導(dǎo)出函數(shù)模板的類型參數(shù)。例如，對于調(diào)用表達(dá)式abs(n)，由于(yóuyú)實(shí)參n為int型，所以推導(dǎo)出模板中類型參數(shù)T為int。當(dāng)類型參數(shù)的含義確定后，編譯器將以函數(shù)模板為樣板，生成一個函數(shù)（稱為函數(shù)模板的實(shí)例化）：

intabs(intx){

returnx<0?–x:x;

}5求絕對值函數(shù)(hánshù)的模板分析9.1函數(shù)模板與類模板——9.1.1函數(shù)模板共一百零一頁//9_1.cpp#include<iostream>usingnamespacestd;

template<classT> //定義函數(shù)(hánshù)模板voidoutputArray(constT*array,intcount){ for(inti=0;i<count;i++) cout<<array[i]<<""; cout<<endl;}

6例9-1函數(shù)(hánshù)模板的示例9.1函數(shù)模板與類模板——9.1.1函數(shù)模板共一百零一頁intmain(){ //主函數(shù)(hánshù)

constintA_COUNT=8,B_COUNT=8,C_COUNT=20; inta[A_COUNT]={1,2,3,4,5,6,7,8}; //定義int數(shù)組

doubleb[B_COUNT]={1.1,2.2,3.3,4.4,5.5,6.6,7.7,8.8};//定義double數(shù)組

charc[C_COUNT]="Welcometoseeyou!";//定義char數(shù)組

cout<<"aarraycontains:"<<endl; outputArray(a,A_COUNT); //調(diào)用函數(shù)模板

cout<<"barraycontains:"<<endl; outputArray(b,B_COUNT); //調(diào)用函數(shù)模板

cout<<"carraycontains:"<<endl; outputArray(c,C_COUNT); //調(diào)用函數(shù)模板

return0;}7例9-1（續(xù)）9.1函數(shù)(hánshù)模板與類模板——9.1.1函數(shù)模板共一百零一頁運(yùn)行(yùnxíng)結(jié)果如下：aarraycontains:12345678barraycontains:1.12.23.34.45.56.67.78.8carraycontains:Welcometoseeyou!8例9-1（續(xù)）9.1函數(shù)(hánshù)模板與類模板——9.1.1函數(shù)模板共一百零一頁類模板的作用使用類模板使用戶可以為類聲明一種模式，使得類中的某些數(shù)據(jù)(shùjù)成員、某些成員函數(shù)的參數(shù)、某些成員函數(shù)的返回值，能取任意類型（包括基本類型的和用戶自定義類型）。99.1.2類模板(múbǎn)9.1函數(shù)模板與類模板共一百零一頁類模板：template<模板參數(shù)表>class

類名{

類成員聲明}如果需要在類模板以外定義其成員函數(shù)，則要采用以下的形式(xíngshì)：template<模板參數(shù)表>類型名類名<模板參數(shù)標(biāo)識符列表>::函數(shù)名（參數(shù)表）10類模板(múbǎn)的聲明9.1函數(shù)模板與類模板——9.1.2類模板共一百零一頁#include<iostream>#include<cstdlib>usingnamespacestd;structStudent{intid; //學(xué)號

floatgpa; //平均分};template<classT>classStore{//類模板：實(shí)現(xiàn)對任意類型(lèixíng)數(shù)據(jù)進(jìn)行存取private:

Titem; //item用于存放任意類型的數(shù)據(jù)

boolhaveValue;//haveValue標(biāo)記item是否已被存入內(nèi)容public: Store(); //缺省形式（無形參）的構(gòu)造函數(shù)

T&getElem(); //提取數(shù)據(jù)函數(shù)

voidputElem(constT&x);//存入數(shù)據(jù)函數(shù)};11例9-2類模板(múbǎn)示例9.1函數(shù)模板與類模板——9.1.2類模板共一百零一頁template<classT> //默認(rèn)構(gòu)造函數(shù)的實(shí)現(xiàn)Store<T>::Store():haveValue(false){}template<classT>//提取數(shù)據(jù)函數(shù)的實(shí)現(xiàn)T&Store<T>::getElem(){ //如試圖提取未初始化的數(shù)據(jù)，則終止程序(chéngxù)

if(!haveValue){ cout<<"Noitempresent!"<<endl; exit(1); //使程序完全退出，返回到操作系統(tǒng)。

} returnitem; //返回item中存放的數(shù)據(jù)}template<classT> //存入數(shù)據(jù)函數(shù)的實(shí)現(xiàn)voidStore<T>::putElem(constT&x){ //將haveValue置為true，表示item中已存入數(shù)值 haveValue=true; item=x; //將x值存入item}12例9-2(續(xù))9.1函數(shù)(hánshù)模板與類模板——9.1.2類模板共一百零一頁intmain(){

Store<int>s1,s2; s1.putElem(3); s2.putElem(-7); cout<<s1.getElem()<<""<<s2.getElem()<<endl; Studentg={1000,23};

Store<Student>s3; s3.putElem(g); cout<<"Thestudentidis"<<s3.getElem().id<<endl;

Store<double>d; cout<<"Retrievingobjectd..."; cout<<d.getElem()<<endl//由于d未經(jīng)初始化,在執(zhí)行(zhíxíng)函數(shù)d.getElem()過程中導(dǎo)致程序終止

return0;}13例9-2(續(xù))9.1函數(shù)(hánshù)模板與類模板——9.1.2類模板共一百零一頁線性群體的概念直接訪問群體--數(shù)組類順序(shùnxù)訪問群體--鏈表類棧類隊列類14線性群體(qúntǐ)9.2線性群體共一百零一頁群體是指由多個數(shù)據(jù)元素(yuánsù)組成的集合體。群體可以分為兩個大類：線性群體和非線性群體。線性群體中的元素按位置排列有序，可以區(qū)分為第一個元素、第二個元素等。非線性群體不用位置順序來標(biāo)識元素。15群體(qúntǐ)的概念9.2線性群體共一百零一頁線性群體(qúntǐ)中的元素次序與其位置關(guān)系是對應(yīng)的。在線性群體(qúntǐ)中，又可按照訪問元素的不同方法分為直接訪問、順序訪問和索引訪問。在本章我們只介紹直接訪問和順序訪問。169.2.1線性群體(qúntǐ)的概念9.2線性群體…第一個元素第二個元素第三個元素最后一個元素共一百零一頁靜態(tài)數(shù)組是具有固定元素個數(shù)的群體，其中的元素可以通過下標(biāo)直接訪問。缺點(diǎn)：大小在編譯時就已經(jīng)確定，在運(yùn)行時無法修改。動態(tài)數(shù)組由一系列位置連續(xù)的，任意數(shù)量(shùliàng)相同類型的元素組成。優(yōu)點(diǎn)：其元素個數(shù)可在程序運(yùn)行時改變。vector就是用類模板實(shí)現(xiàn)的動態(tài)數(shù)組。動態(tài)數(shù)組類模板：例9-3（Array.h）179.2.2直接(zhíjiē)訪問群體——數(shù)組類9.2線性群體共一百零一頁#ifndefARRAY_H#defineARRAY_H#include<cassert>template<classT> //數(shù)組類模板定義classArray{private: T*list; //用于存放動態(tài)分配的數(shù)組內(nèi)存(nèicún)首地址

intsize; //數(shù)組大小（元素個數(shù)）public: Array(intsz=50); //構(gòu)造函數(shù)

Array(constArray<T>&a); //拷貝構(gòu)造函數(shù)

~Array(); //析構(gòu)函數(shù)

Array<T>&operator=(constArray<T>&rhs); //重載"=“ T&operator[](inti);//重載"[]” constT&operator[](inti)const; operatorT*(); //重載到T*類型的轉(zhuǎn)換

operatorconstT*()const; intgetSize()const; //取數(shù)組的大小

voidresize(intsz); //修改數(shù)組的大小};18例9-3動態(tài)(dòngtài)數(shù)組類模板程序9.2線性群體——9.2.2直接訪問群體——數(shù)組類共一百零一頁template<classT>Array<T>::Array(intsz){//構(gòu)造函數(shù) assert(sz>=0);//sz為數(shù)組大?。ㄔ?yuánsù)個數(shù)），應(yīng)當(dāng)非負(fù)

size=sz; //將元素個數(shù)賦值給變量size list=newT[size]; //動態(tài)分配size個T類型的元素空間}template<classT>Array<T>::~Array(){//析構(gòu)函數(shù) delete[]list;}//拷貝構(gòu)造函數(shù)template<classT>Array<T>::Array(constArray<T>&a){

size=a.size;//從對象x取得數(shù)組大小，并賦值給當(dāng)前對象的成員 //為對象申請內(nèi)存并進(jìn)行出錯檢查

list=newT[size]; //動態(tài)分配n個T類型的元素空間

for(inti=0;i<size;i++)//從對象X復(fù)制數(shù)組元素到本對象 list[i]=a.list[i];}19例9-3（續(xù)）共一百零一頁//重載"="運(yùn)算符，將對象(duìxiàng)rhs賦值給本對象。實(shí)現(xiàn)對象之間的整體賦值template<classT>Array<T>&Array<T>::operator=(constArray<T>&rhs){ if(&rhs!=this){//如果本對象中數(shù)組大小與rhs不同，則刪除數(shù)組原有內(nèi)存，然后重新分配

if(size!=rhs.size){ delete[]list; //刪除數(shù)組原有內(nèi)存

size=rhs.size; //設(shè)置本對象的數(shù)組大小

list=newT[size]; //重新分配n個元素的內(nèi)存

} //從對象X復(fù)制數(shù)組元素到本對象

for(inti=0;i<size;i++) list[i]=rhs.list[i]; } return*this; //返回當(dāng)前對象的引用}20例9-3（續(xù)）共一百零一頁//重載下標(biāo)運(yùn)算符，實(shí)現(xiàn)與普通數(shù)組一樣通過下標(biāo)訪問元素，并且具有(jùyǒu)越界檢查功能template<classT>T&Array<T>::operator[](intn){ assert(n>=0&&n<size); //檢查下標(biāo)是否越界

returnlist[n]; //返回下標(biāo)為n的數(shù)組元素}template<classT>constT&Array<T>::operator[](intn)const{ assert(n>=0&&n<size); //檢查下標(biāo)是否越界

returnlist[n]; //返回下標(biāo)為n的數(shù)組元素}

//重載指針轉(zhuǎn)換運(yùn)算符，將Array類的對象名轉(zhuǎn)換為T類型的指針template<classT>Array<T>::operatorT*(){ returnlist; //返回當(dāng)前對象中私有數(shù)組的首地址}

21例9-3（續(xù)）共一百零一頁template<classT>Array<T>::operatorconstT*()const{ returnlist; //返回當(dāng)前(dāngqián)對象中私有數(shù)組的首地址}//取當(dāng)前數(shù)組的大小template<classT>intArray<T>::getSize()const{ returnsize;}//將數(shù)組大小修改為sztemplate<classT>voidArray<T>::resize(intsz){ assert(sz>=0); //檢查sz是否非負(fù)

if(sz==size) //如果指定的大小與原有大小一樣，什么也不做

return; T*newList=newT[sz]; //申請新的數(shù)組內(nèi)存

intn=(sz<size)?sz:size;//將sz與size中較小的一個賦值給n //將原有數(shù)組中前n個元素復(fù)制到新數(shù)組中

for(inti=0;i<n;i++) newList[i]=list[i]; delete[]list; //刪除原數(shù)組

list=newList; //使list指向新數(shù)組

size=sz; //更新size}#endif//ARRAY_H

22例9-3（續(xù)）共一百零一頁23深拷貝(kǎobèi)9.2線性群體——9.2.2直接(zhíjiē)訪問群體——數(shù)組類listsizeaa的數(shù)組元素占用的內(nèi)存拷貝前l(fā)istsizeaa的數(shù)組元素占用的內(nèi)存拷貝后listsizebb的數(shù)組元素占用的內(nèi)存共一百零一頁如果一個函數(shù)(hánshù)的返回值是一個對象的值，就不應(yīng)成為左值，即被再賦值。如果返回值為引用，由于引用是對象的別名，通過引用當(dāng)然可以改變對象的值，就可以被再賦值了。24為什么有的函數(shù)(hánshù)返回引用共一百零一頁#include<iostream>usingnamespacestd;voidread(int*p,intn){for(inti=0;i<n;i++)cin>>p[i];}intmain(){inta[10];read(a,10);return0;}#include"Array.h"#include<iostream>usingnamespacestd;voidread(int*p,intn){for(inti=0;i<n;i++)cin>>p[i];}intmain(){Array<int>a(10);read(a,10);return0;}25指針(zhǐzhēn)轉(zhuǎn)換運(yùn)算符的作用共一百零一頁例9-4求范圍(fànwéi)2~N中的質(zhì)數(shù)，N在程序運(yùn)行時由鍵盤輸入。26Array類的應(yīng)用(yìngyòng)共一百零一頁#include<iostream>#include<iomanip>#include"Array.h"usingnamespacestd;intmain(){ Array<int>a(10); //用來(yònɡlái)存放質(zhì)數(shù)的數(shù)組，初始狀態(tài)有10個元素。

intn,count=0; cout<<"Enteravalue>=2asupperlimitforprimenumbers:"; cin>>n; for(inti=2;i<=n;i++){ boolisPrime=true; for(intj=0;j<count;j++) if(i%a[j]==0){ //若i被a[j]整除，說明i不是質(zhì)數(shù)

isPrime=false;break; } if(isPrime){ if(count==a.getSize())a.resize(count*2); a[count++]=i; } } for(inti=0;i<count;i++)cout<<setw(8)<<a[i]; cout<<endl; return0;}27例9-4（續(xù)）共一百零一頁鏈表是一種動態(tài)數(shù)據(jù)結(jié)構(gòu)，可以用來表示順序訪問的線性群體。鏈表是由系列結(jié)點(diǎn)組成的，結(jié)點(diǎn)可以在運(yùn)行時動態(tài)生成。每一個結(jié)點(diǎn)包括數(shù)據(jù)域和指向鏈表中下一個結(jié)點(diǎn)的指針（即下一個結(jié)點(diǎn)的地址）。如果(rúguǒ)鏈表每個結(jié)點(diǎn)中只有一個指向后繼結(jié)點(diǎn)的指針，則該鏈表稱為單鏈表。289.2.3順序(shùnxù)訪問群體——鏈表類9.2線性群體共一百零一頁29單鏈表9.2線性群體(qúntǐ)

——9.2.3順序訪問群體——鏈表類data1data2data3datanNULL…h(huán)eadrear共一百零一頁template<classT>classNode{private:Node<T>*next;public:Tdata;Node(constT&item,Node<T>*next=0);voidinsertAfter(Node<T>*p);Node<T>*deleteAfter();Node<T>*nextNode()const;};30單鏈表的結(jié)點(diǎn)(jiédiǎn)類模板9.2線性群體——9.2.3順序(shùnxù)訪問群體——鏈表類共一百零一頁31在結(jié)點(diǎn)之后(zhīhòu)插入一個結(jié)點(diǎn)9.2線性群體——9.2.3順序(shùnxù)訪問群體——鏈表類data1data2…pdata…template<classT>voidNode<T>::insertAfter(Node<T>*p){//p節(jié)點(diǎn)指針域指向當(dāng)前節(jié)點(diǎn)的后繼節(jié)點(diǎn)

p->next=next;next=p;//當(dāng)前節(jié)點(diǎn)的指針域指向p}共一百零一頁32

刪除(shānchú)結(jié)點(diǎn)之后的結(jié)點(diǎn)9.2線性群體(qúntǐ)

——9.2.3順序訪問群體——鏈表類data1data2data3…tempPtrNode<T>*Node<T>::deleteAfter(void){Node<T>*tempPtr=next;if(next==0)return0;next=tempPtr->next;returntempPtr;}共一百零一頁//Node.h#ifndefNODE_H#defineNODE_H//類模板的定義(dìngyì)template<classT>classNode{private: Node<T>*next; //指向后繼結(jié)點(diǎn)的指針public: Tdata; //數(shù)據(jù)域

Node(constT&data,Node<T>*next=0);//構(gòu)造函數(shù)

voidinsertAfter(Node<T>*p); //在本結(jié)點(diǎn)之后插入一個同類結(jié)點(diǎn)p Node<T>*deleteAfter(); //刪除本結(jié)點(diǎn)的后繼結(jié)點(diǎn)，并返回其地址

Node<T>*nextNode(); //獲取后繼結(jié)點(diǎn)的地址

constNode<T>*nextNode()const; //獲取后繼結(jié)點(diǎn)的地址};33例9-5結(jié)點(diǎn)(jiédiǎn)類模扳9.2線性群體——9.2.3順序訪問群體——鏈表類共一百零一頁//類的實(shí)現(xiàn)部分//構(gòu)造函數(shù)，初始化數(shù)據(jù)(shùjù)和指針成員template<classT>Node<T>::Node(constT&data,Node<T>*next/*=0*/):data(data),next(next){}

//返回后繼結(jié)點(diǎn)的指針template<classT>Node<T>*Node<T>::nextNode(){ returnnext;}

//返回后繼結(jié)點(diǎn)的指針template<classT>constNode<T>*Node<T>::nextNode()const{ returnnext;}34例9-5（續(xù)）9.2線性群體(qúntǐ)

——9.2.3順序訪問群體——鏈表類共一百零一頁//在當(dāng)前結(jié)點(diǎn)之后插入一個結(jié)點(diǎn)ptemplate<classT>voidNode<T>::insertAfter(Node<T>*p){p->next=next;//p結(jié)點(diǎn)指針域指向(zhǐxiànɡ)當(dāng)前結(jié)點(diǎn)的后繼結(jié)點(diǎn)

next=p; //當(dāng)前結(jié)點(diǎn)的指針域指向p}//刪除當(dāng)前結(jié)點(diǎn)的后繼結(jié)點(diǎn)，并返回其地址template<classT>Node<T>*Node<T>::deleteAfter(){ Node<T>*tempPtr=next; //將欲刪除的結(jié)點(diǎn)地址存儲到tempPtr中

if(next==0) //如果當(dāng)前結(jié)點(diǎn)沒有后繼結(jié)點(diǎn)，則返回空指針

return0; next=tempPtr->next; //使當(dāng)前結(jié)點(diǎn)的指針域指向tempPtr的后繼結(jié)點(diǎn)

returntempPtr; //返回被刪除的結(jié)點(diǎn)的地址}#endif//NODE_H35例9-5（續(xù)）9.2線性群體——9.2.3順序(shùnxù)訪問群體——鏈表類共一百零一頁生成結(jié)點(diǎn)插入(chārù)結(jié)點(diǎn)查找結(jié)點(diǎn)刪除結(jié)點(diǎn)遍歷鏈表清空鏈表36鏈表的基本操作9.2線性群體(qúntǐ)

——9.2.3順序訪問群體——鏈表類共一百零一頁#ifndefLINKEDLIST_H#defineLINKEDLIST_H#include"Node.h"template<classT>classLinkedList{private: //數(shù)據(jù)(shùjù)成員：

Node<T>*front,*rear； Node<T>*prevPtr,*currPtr; intsize; intposition; Node<T>*newNode(constT&item,Node<T>*ptrNext=NULL); voidfreeNode(Node<T>*p); voidcopy(constLinkedList<T>&L);public: LinkedList(); LinkedList(constLinkedList<T>&L); ~LinkedList(); LinkedList<T>&operator=(constLinkedList<T>&L); intgetSize()const; boolisEmpty()const; voidreset(intpos=0); voidnext(); boolendOfList()const; intcurrentPosition(void)const; voidinsertFront(constT&item); voidinsertRear(constT&item); voidinsertAt(constT&item); voidinsertAfter(constT&item); TdeleteFront(); voiddeleteCurrent(); T&data(); constT&data()const voidclear();};#endif//LINKEDLIST_H//鏈表類模板函數(shù)實(shí)現(xiàn)(shíxiàn)代碼可以從網(wǎng)上下載37例9-6鏈表類模板共一百零一頁//9_7.cpp#include<iostream>#include"LinkedList.h"usingnamespacestd;intmain(){ LinkedList<int>list; for(inti=0;i<10;i++){ intitem; cin>>item; list.insertFront(item); } cout<<"List:"; list.reset(); while(!list.endOfList()){ cout<<list.data()<<""; list.next(); } cout<<endl; intkey; cout<<"Pleaseentersomeintegerneededtobedeleted:"; cin>>key; list.reset(); while(!list.endOfList()){ if(list.data()==key) list.deleteCurrent(); list.next(); } cout<<"List:"; list.reset(); while(!list.endOfList()){ cout<<list.data()<<""; list.next } cout<<endl; return0;}38例9-7鏈表類應(yīng)用(yìngyòng)舉例共一百零一頁運(yùn)行(yùnxíng)結(jié)果如下：36575245910List:10954257563Pleaseentersomeintegerneededtobedeleted:5List:1094276339例9-7（續(xù)）9.2線性群體——9.2.3順序(shùnxù)訪問群體——鏈表類共一百零一頁棧是只能從一端(yīduān)訪問的線性群體，可以訪問的這一端(yīduān)稱棧頂，另一端(yīduān)稱棧底。409.2.4棧類9.2線性群體(qúntǐ)an┆a2a1入棧出棧棧頂棧底共一百零一頁41棧的應(yīng)用舉例(jǔlì)——表達(dá)式處理9.2線性群體(qúntǐ)

——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)共一百零一頁?？諚Ｖ袥]有元素(yuánsù)棧滿棧中元素個數(shù)達(dá)到上限一般狀態(tài)棧中有元素，但未達(dá)到棧滿狀態(tài)42棧的基本(jīběn)狀態(tài)9.2線性群體——9.2.4棧類共一百零一頁439.2線性群體(qúntǐ)

——9.2.4棧類棧頂┆an┆a1a0入棧出棧數(shù)組下標(biāo)maxn10一般狀態(tài)棧頂入棧出棧數(shù)組下標(biāo)初始狀態(tài)（棧空）maxn10棧頂amax┆an┆a1a0入棧出棧數(shù)組下標(biāo)maxn10棧滿狀態(tài)共一百零一頁初始化入棧出棧清空棧訪問棧頂元素(yuánsù)檢測棧的狀態(tài)（滿、空）44棧的基本操作9.2線性群體(qúntǐ)

——9.2.4棧類共一百零一頁//Stack.h#ifndefSTACK_H#defineSTACK_H#include<cassert>template<classT,intSIZE=50>classStack{private: Tlist[SIZE]; inttop;public: Stack(); voidpush(constT&item); Tpop(); voidclear(); constT&peek()const; boolisEmpty()const; boolisFull()const;};45例9-8棧類模板(múbǎn)共一百零一頁//模板(múbǎn)的實(shí)現(xiàn)template<classT,intSIZE>Stack<T,SIZE>::Stack():top(-1){} template<classT,intSIZE>voidStack<T,SIZE>::push(constT&item){

assert(!isFull());

list[++top]=item; }template<classT,intSIZE>TStack<T,SIZE>::pop(){

assert(!isEmpty());

returnlist[top--]; }template<classT,intSIZE>constT&Stack<T,SIZE>::peek()const{

assert(!isEmpty());

returnlist[top]; //返回棧頂元素}template<classT,intSIZE>boolStack<T,SIZE>::isEmpty()const{

returntop==-1;}template<classT,intSIZE>boolStack<T,SIZE>::isFull()const{

returntop==SIZE-1;}

template<classT,intSIZE>voidStack<T,SIZE>::clear(){

top=-1;}

#endif //STACK_H46例9-8（續(xù)）共一百零一頁例9.9一個簡單的整數(shù)計算器

實(shí)現(xiàn)一個簡單的整數(shù)計算器，能夠進(jìn)行加、減、乘、除和乘方運(yùn)算。使用時算式采用后綴輸入法，每個操作數(shù)、操作符之間都以空白符分隔。例如，若要計算"3+5"則輸入"35+"。乘方運(yùn)算符用"^"表示。每次運(yùn)算在前次結(jié)果基礎(chǔ)上進(jìn)行，若要將前次運(yùn)算結(jié)果清除(qīngchú)，可鍵入"c"。當(dāng)鍵入"q"時程序結(jié)束。Calculator.hCalculator.cpp9_9.cpp47棧的應(yīng)用(yìngyòng)9.2線性群體——9.2.4棧類共一百零一頁//Calculator.h#ifndefCALCULATOR_H#defineCALCULATOR_H#include"Stack.h" //包含棧類模板定義文件classCalculator{ //計算器類private: Stack<double>s; //操作數(shù)棧

voidenter(doublenum); //將操作數(shù)num壓入棧

//連續(xù)將兩個操作數(shù)彈出棧，放在opnd1和opnd2中

boolgetTwoOperands(double&opnd1,double&opnd2); voidcompute(charop); //執(zhí)行由操作符op指定的運(yùn)算public: voidrun(); //運(yùn)行計算器程序(chéngxù)

voidclear(); //清空操作數(shù)棧};#endif//CALCULATOR_H48例9-99.2線性群體(qúntǐ)

——9.2.4棧類共一百零一頁//Calculator.cpp#include"Calculator.h"#include<iostream>#include<sstream>#include<cmath>usingnamespacestd;//工具(gōngjù)函數(shù)，用于將字符串轉(zhuǎn)換為實(shí)數(shù)inlinedoublestringToDouble(conststring&str){ istringstreamstream(str); //字符串輸入流

doubleresult; stream>>result; returnresult;}voidCalculator::enter(doublenum){ //將操作數(shù)num壓入棧

s.push(num);}49例9-9(續(xù))9.2線性群體(qúntǐ)

——9.2.4棧類共一百零一頁boolCalculator::getTwoOperands(double&opnd1,double&opnd2){ if(s.isEmpty()){ //檢查(jiǎnchá)棧是否空

cerr<<"Missingoperand!"<<endl; returnfalse; } opnd1=s.pop(); //將右操作數(shù)彈出棧

if(s.isEmpty()){ //檢查棧是否空

cerr<<"Missingoperand!"<<endl; returnfalse; } opnd2=s.pop(); //將左操作數(shù)彈出棧

returntrue;}50例9-9(續(xù))9.2線性群體(qúntǐ)

——9.2.4棧類共一百零一頁voidCalculator::compute(charop){ //執(zhí)行運(yùn)算(yùnsuàn)

doubleoperand1,operand2; boolresult=getTwoOperands(operand1,operand2); 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ù)是否為0 cerr<<"Dividedby0!"<<endl; s.clear(); //除數(shù)為0時清空棧

}else s.push(operand2/operand1); break; case'^':s.push(pow(operand2,operand1));break; default: cerr<<"Unrecognizedoperator!"<<endl; break; } cout<<"="<<s.peek()<<""; //輸出本次運(yùn)算結(jié)果

}else s.clear(); //操作數(shù)不夠，清空棧}51例9-9(續(xù))9.2線性群體(qúntǐ)

——9.2.4棧類共一百零一頁voidCalculator::run(){//讀入并處理后綴表達(dá)式

stringstr; while(cin>>str,str!="q"){ switch(str[0]){ case'c':s.clear();break; case'-'://遇'-'需判斷是減號還是負(fù)號

if(str.size()>1) enter(stringToDouble(str)); else compute(str[0]); break; case'+': //遇到其它操作符時

case'*': case'/': case'^': compute(str[0]); default://若讀入的是操作數(shù)，轉(zhuǎn)換(zhuǎnhuàn)為整型后壓入棧

enter(stringToDouble(str));break; } }}voidCalculator::clear(){ //清空操作數(shù)棧

s.clear();}52例9-9(續(xù))9.2線性群體(qúntǐ)

——9.2.4棧類共一百零一頁//9_9.cpp#include"Calculator.h"intmain(){ Calculatorc; c.run(); return0;}53例9-9(續(xù))9.2線性群體(qúntǐ)

——9.2.4棧類共一百零一頁隊列是只能向一端添加(tiānjiā)元素，從另一端刪除元素的線性群體549.2.5隊列(duìliè)類9.2線性群體a1a2an-1an……隊頭隊尾入隊出隊a0共一百零一頁隊空隊列(duìliè)中沒有元素隊滿隊列中元素個數(shù)達(dá)到上限一般狀態(tài)隊列中有元素，但未達(dá)到隊滿狀態(tài)55隊列的基本(jīběn)狀態(tài)9.2線性群體——9.2.5隊列類共一百零一頁569.2線性群體(qúntǐ)

——9.2.5隊列類a0a1an-1an……隊頭隊尾入隊出隊數(shù)組下標(biāo)01n-1nmax(一般狀態(tài))……隊頭隊尾入隊出隊數(shù)組下標(biāo)01n-1nmax(隊空狀態(tài))a0a1an-1anamax……隊頭隊尾入隊出隊數(shù)組下標(biāo)01n-1nmax(隊滿狀態(tài))元素移動(yídòng)方向元素移動方向56共一百零一頁在想象(xiǎngxiàng)中將數(shù)組彎曲成環(huán)形，元素出隊時，后繼元素不移動，每當(dāng)隊尾達(dá)到數(shù)組最后一個元素時，便再回到數(shù)組開頭。57循環(huán)(xúnhuán)隊列9.2線性群體——9.2.5隊列類共一百零一頁589.2線性群體(qúntǐ)

——9.2.5隊列類1234……m-1m-2m-30amam+1am+2a3隊頭隊尾a4am-2am-3am-1隊滿狀態(tài)元素個數(shù)=m1234……m-1m-2m-30隊尾隊頭隊空狀態(tài)元素個數(shù)=0隊尾1234……m-1m-2m-30a0a1a2a3隊頭一般狀態(tài)58共一百零一頁//Queue.h#ifndefQUEUE_H#defineQUEUE_H#include<cassert>//類模板(múbǎn)的定義template<classT,intSIZE=50>classQueue{private: intfront,rear,count; //隊頭指針、隊尾指針、元素個數(shù)

Tlist[SIZE]; //隊列元素數(shù)組public: Queue();//構(gòu)造函數(shù)，初始化隊頭指針、隊尾指針、元素個數(shù)

voidinsert(constT&item); //新元素入隊

Tremove(); //元素出隊

voidclear(); //清空隊列

constT&getFront()const; //訪問隊首元素59例9-10隊列(duìliè)類模板9.2線性群體——9.2.5隊列類共一百零一頁

//測試隊列狀態(tài)

intgetLength()const;//求隊列長度

boolisEmpty()const;//判隊隊列空否

boolisFull()const;//判斷隊列滿否};//構(gòu)造函數(shù)，初始化隊頭指針、隊尾指針、元素個數(shù)template<classT,intSIZE>Queue<T,SIZE>::Queue():front(0),rear(0),count(0){}template<classT,intSIZE>voidQueue<T,SIZE>::insert(constT&item){//向隊尾插入元素

assert(count!=SIZE); count++; //元素個數(shù)增1 list[rear]=item; //向隊尾插入元素

rear=(rear+1)%SIZE; //隊尾指針增1，用取余運(yùn)算(yùnsuàn)實(shí)現(xiàn)循環(huán)隊列}template<classT,intSIZE>TQueue<T,SIZE>::remove(){

assert(count!=0); inttemp=front; //記錄下原先的隊首指針

count--; //元素個數(shù)自減

front=(front+1)%SIZE;//隊首指針增1。取余以實(shí)現(xiàn)循環(huán)隊列

returnlist[temp]; //返回首元素值}60例9-10（續(xù)）9.2線性群體(qúntǐ)

——9.2.5隊列類共一百零一頁template<classT,intSIZE>constT&Queue<T,SIZE>::getFront()const{

returnlist[front];}template<classT,intSIZE>intQueue<T,SIZE>::getLength()const{ //返回(fǎnhuí)隊列元素個數(shù)

returncount;}template<classT,intSIZE>boolQueue<T,SIZE>::isEmpty()const{ //測試隊空否

returncount==0;}template<classT,intSIZE>boolQueue<T,SIZE>::isFull()const{ //測試隊滿否

returncount==SIZE;}template<classT,intSIZE>voidQueue<T,SIZE>::clear(){ //清空隊列

count=0; front=0; rear=0;}#endif//QUEUE_H61例9-10（續(xù)）9.2線性群體(qúntǐ)

——9.2.5隊列類共一百零一頁插入排序選擇(xuǎnzé)排序交換排序順序查找折半查找629.3群體(qúntǐ)數(shù)據(jù)的組織9.3群體數(shù)據(jù)的組織共一百零一頁排序是計算機(jī)程序設(shè)計中的一種重要操作，它的功能是將一個數(shù)據(jù)元素的任意序列，重新排列成一個按關(guān)鍵字有序的序列。數(shù)據(jù)元素：數(shù)據(jù)的基本單位。在計算機(jī)中通常作為一個整體進(jìn)行考慮。一個數(shù)據(jù)元素可由若干數(shù)據(jù)項(xiàng)組成。關(guān)鍵字：數(shù)據(jù)元素中某個(mǒuɡè)數(shù)據(jù)項(xiàng)的值，用它可以標(biāo)識（識別）一個數(shù)據(jù)元素。在排序過程中需要完成兩種基本操作：比較兩個數(shù)的大小調(diào)整元素在序列中的位置63排序(páixù)（sorting）9.3群體數(shù)據(jù)的組織共一百零一頁內(nèi)部排序：待排序的數(shù)據(jù)元素存放(cúnfàng)在計算機(jī)內(nèi)存中進(jìn)行的排序過程。外部排序：待排序的數(shù)據(jù)元素數(shù)量很大，以致內(nèi)存中一次不能容納全部數(shù)據(jù)，在排序過程中尚需對外存進(jìn)行訪問的排序過程。64內(nèi)部(nèibù)排序與外部排序9.3群體數(shù)據(jù)的組織共一百零一頁插入排序選擇排序(páixù)交換排序65內(nèi)部(nèibù)排序方法9.3群體數(shù)據(jù)的組織共一百零一頁每一步將一個待排序元素按其關(guān)鍵字值的大小插入到已排序序列(xùliè)的適當(dāng)位置上，直到待排序元素插入完為止。66插入排序的基本(jīběn)思想9.3群體數(shù)據(jù)的組織——9.3.1插入排序初始狀態(tài)：[5]41020123插入操作：1[4][45]10201232[10][4510]201233[20][451020]1234[12][45101220]35[3][345101220]共一百零一頁template<classT>voidinsertionSort(Ta[],intn){ inti,j; Ttemp; for(inti=1;i<n;i++){ intj=i; Ttemp=a[i]; while(j>0&&temp<a[j-1]){ a[j]=a[j-1]; j--; } a[j]=temp; }}67例9-11直接(zhíjiē)插入排序函數(shù)模板9.3群體數(shù)據(jù)(shùjù)的組織——9.3.1插入排序共一百零一頁每次從待排序序列中選擇(xuǎnzé)一個關(guān)鍵字最小的元素，（當(dāng)需要按關(guān)鍵字升序排列時），順序排在已排序序列的最后，直至全部排完。68選擇(xuǎnzé)排序的基本思想9.3群體數(shù)據(jù)的組織——9.3.2選擇排序[541020123]初始狀態(tài)：3[41020125]34[1020125]第i次選擇后，將選出的那個記錄與第i個記錄做交換。345[201210]......共一百零一頁template<classT>voidmySwap(T&x,T&y){ Ttemp=x; x=y; y=temp;}template<classT>voidselectionSort(Ta[],intn){ for(inti=0;i<n-1;i++){ intleastIndex=i; for(intj=i+1;j<n;j++) if(a[j]<a[leastIndex]) leastIndex=j; mySwap(a[i],a[leastIndex]); }}69例9-12簡單選擇(xuǎnzé)排序函數(shù)模板9.3群體數(shù)據(jù)的組織——9.3.2選擇(xuǎnzé)排序共一百零一頁兩兩比較待排序序列中的元素，并交換(jiāohuàn)不滿足順序要求的各對元素，直到全部滿足順序要求為止。70交換排序(páixù)的基本思想9.3群體數(shù)據(jù)的組織——9.3.3交換排序共一百零一頁對具有n個元素的序列按升序進(jìn)行起泡排序的步驟：首先將第一個元素與第二個元素進(jìn)行比較，若為逆序，a則將兩元素交換。然后比較第二、第三個元素，依次類推，直到第n-1和第n個元素進(jìn)行了比較和交換。此過程稱為第一趟起泡排序。經(jīng)過第一趟，最大的元素便被交換到第n個位置(wèizhi)。對前n-1個元素進(jìn)行第二趟起泡排序，將其中最大元素交換到第n-1個位置。如此繼續(xù)，直到某一趟排序未發(fā)生任何交換時，排序完畢。對n個元素的序列，起泡排序最多需要進(jìn)行n-1趟。71最簡單(jiǎndān)的交換排序方法——起泡排序9.3群體數(shù)據(jù)的組織——9.3.3交換排序共一百零一頁對整數(shù)(zhěngshù)序列85243按升序排序72起泡排序(páixù)舉例9.3群體數(shù)據(jù)的組織——9.3.3交換排序8524352438243582345823458初始狀態(tài)第一趟結(jié)果第二趟結(jié)果第三趟結(jié)果第四趟結(jié)果小的逐漸上升每趟沉下一個最大的共一百零一頁template<classT>voidmySwap(T&x,T&y){ Ttemp=x; x=y; y=temp;}template<classT>voidbubbleSort(Ta[],intn){ inti=n–1; while(i>0){ intlastExchangeIndex=0; for(intj=0;j<i;j++) if(a[j+1]<a[j]){mySwap(a[j],a[j+1]);lastExchangeIndex=j; } i=lastExchangeIndex; }}73例9-13起泡排序函數(shù)(hánshù)模板共一百零一頁其基本思想從序列的首元素開始，逐個元素與待查找的關(guān)鍵字進(jìn)行比較，直到找到相等的。若整個序列中沒有(méiyǒu)與待查找關(guān)鍵字相等的元素，就是查找不成功。例9-14順序查找函數(shù)模板749.3.4順序(shùnxù)查找9.3群體數(shù)據(jù)的組織template<classT>intseqSearch(constTlist[],intn,constT&key){ for(inti=0;i<n;i++) if(list[i]==key) returni; return-1;}共一百零一頁對于已按關(guān)鍵字排序的序列，經(jīng)過一次比較，可將序列分割成兩部分，然后只在有可能包含待查元素的一部分中繼續(xù)查找，并根據(jù)(gēnjù)試探結(jié)果繼續(xù)分割，逐步縮小查找范圍，直至找到或找不到為止。75折半(zhébàn)查找（二分法查找）9.3群體數(shù)據(jù)的組織——9.3.5折半查找共一百零一頁用折半(zhébàn)查找法，在下列序列中查找值為21的元素：76折半(zhébàn)查找示例9.3群體數(shù)據(jù)的組織——9.3.5折半查找L=1513192137566475808892H=11M

=INT((L+H)/2)=6513192137L=1H=M-1=5M=INT((L+H)/2)=3M2137HL=M+1=4LM=INT((L+H)/2)=4M共一百零一頁template<classT>intbinSearch(constTlist[],intn,constT&key){ intlow=0; inthigh=n-1; while(low<=high){ intmid=(low+high)/2; if(key==list[mid]) returnmid; elseif(key<list[mid]) high=mid–1; else low=mid+1; } return-1;}77例9-15折半查找函數(shù)(hánshù)模板9.3群體數(shù)據(jù)(shùjù)的組織——9.3.5折半查找共一百零一頁使用動態(tài)(dòngtài)數(shù)組類模板Array來實(shí)現(xiàn)多態(tài)性調(diào)用此外，由于Array數(shù)組允許動態(tài)改變大小，因此可以向Array數(shù)組中動態(tài)添加新的元素，因此本例的主程序中允許用戶隨時動態(tài)添加新的賬戶。例9-16個人銀行賬戶管理程序只有9_16.cpp有所改動，其它文件未做任何修改，因此這里只將9_16.cpp列出。789.4綜合(zōnghé)實(shí)例——對個人銀行賬戶管理程序的改進(jìn)共一百零一頁//9_16.cpp#include"account.h"#include"Array.h"#include<iostream>usingnamespacestd;intmain(){ Datedate(2008,11,1); //起始日期

Array<Account*>accounts(0); //創(chuàng)建賬戶數(shù)組，元素(yuánsù)個數(shù)為0 cout<<"(a)addaccount(d)deposit(w)withdraw(s)show(c)changeday(n)nextmonth(e)exit"<<endl; charcmd; do{ //顯示日期和總金額

date.show(); cout<<"\tTotal:"<<Account::getTotal()<<"\tcommand>"; chartype; intindex,day; doubleamount,credit,rate,fee; stringid,desc; Account*account; cin>>cmd; switch(cmd){79例9-16（續(xù)）共一百零一頁 case'a': //增加賬戶

cin>>type>>id; if(type=='s'){ cin>>rate; account=newSavingsAccount(date,id,rate); }else{ cin>>credit>>rate>>fee; account=newCreditAccount(date,id,credit,rate,fee); } accounts.resize(accounts.getSize()+1); accounts[accounts.getSize()-1]=account; break; case'd': //存入(cúnrù)現(xiàn)金

cin>>index>>amount; getline(cin,desc); accounts[index]->deposit(date,amount,desc); break; case'w': //取出現(xiàn)金

cin>>index>>amount; getline(cin,desc); accounts[index]->withdraw(date,amount,desc); break;80例9-16（續(xù)）共一百零一頁 case'c': //改變?nèi)掌?rìqī)

cin>>day; if(day<date.getDay()) cout<<"Youcannotspecifyapreviousday"; elseif(day>date.getMaxDay()) cout<<"Invalidday"; else date=Date(date.getYear(),date.getMonth(),day); break; case'n': //進(jìn)入下個月

if(date.getMonth()==12) date=Date(date.getYear()+1,1,1); else date=Date(date.getYear(),date.getMonth()+1,1); for(inti=0;i<accounts.getSize();i++) accounts[i]->settle(date); break; } }while(cmd!='e'); for(inti=0;i<accounts.getSize();i++) deleteaccounts[i]; return0;}81例9-16（續(xù)）共一百零一頁運(yùn)行(yùnxíng)結(jié)果如下：(a)addaccount(d)deposit(w)withdraw(s)show(c)changeday(n)nextmonth(e)exit2008-11-1Total:0command>asS37552170.0152008-11-1#S3755217created2008-11-1Total:0command>as023423420.0152008-11-1#02342342created2008-11-1Total:0command>acC5392394100000.0005502008-11-1#C5392394created2008-11-1Total:0command>c52008-11-5Total:0command>d05000salary2008-11-5#S375521750005000salary2008-11-5Total:5000co