c++數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)

目錄13.1線(xiàn)性群體13.2群體數(shù)據(jù)的組織13.3小結(jié)1線(xiàn)性群體線(xiàn)性群體的概念直接訪(fǎng)問(wèn)群體--數(shù)組類(lèi)順序訪(fǎng)問(wèn)群體--鏈表類(lèi)棧類(lèi)隊(duì)列類(lèi)213.1線(xiàn)性群體群體的概念群體是指由多個(gè)數(shù)據(jù)元素組成的集合體。群體可以分為兩個(gè)大類(lèi)：線(xiàn)性群體和非線(xiàn)性群體。線(xiàn)性群體中的元素按位置排列有序，可以區(qū)分為第一個(gè)元素、第二個(gè)元素等。非線(xiàn)性群體不用位置順序來(lái)標(biāo)識(shí)元素。313.1線(xiàn)性群體13.1.1線(xiàn)性群體的概念線(xiàn)性群體中的元素次序與其位置關(guān)系是對(duì)應(yīng)的。在線(xiàn)性群體中，又可按照訪(fǎng)問(wèn)元素的不同方法分為直接訪(fǎng)問(wèn)、順序訪(fǎng)問(wèn)和索引訪(fǎng)問(wèn)。在本章我們只介紹直接訪(fǎng)問(wèn)和順序訪(fǎng)問(wèn)。413.1線(xiàn)性群體…第一個(gè)元素第二個(gè)元素第三個(gè)元素最后一個(gè)元素13.1.2直接訪(fǎng)問(wèn)群體——數(shù)組類(lèi)靜態(tài)數(shù)組是具有固定元素個(gè)數(shù)的群體，其中的元素可以通過(guò)下標(biāo)直接訪(fǎng)問(wèn)。缺點(diǎn)：大小在編譯時(shí)就已經(jīng)確定，在運(yùn)行時(shí)無(wú)法修改。動(dòng)態(tài)數(shù)組由一系列位置連續(xù)的，任意數(shù)量相同類(lèi)型的元素組成。優(yōu)點(diǎn)：其元素個(gè)數(shù)可在程序運(yùn)行時(shí)改變。vector就是用類(lèi)模板實(shí)現(xiàn)的動(dòng)態(tài)數(shù)組。動(dòng)態(tài)數(shù)組類(lèi)模板：例9-3（Array.h）513.1線(xiàn)性群體6例13-1（教材例9-3）

動(dòng)態(tài)數(shù)組類(lèi)模板程序#ifndefARRAY_H#defineARRAY_H#include<cassert>template<classT> //數(shù)組類(lèi)模板定義classArray{private: T*list; //用于存放動(dòng)態(tài)分配的數(shù)組內(nèi)存首地址

intsize; //數(shù)組大小（元素個(gè)數(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*類(lèi)型的轉(zhuǎn)換

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

voidresize(intsz); //修改數(shù)組的大小};13.1線(xiàn)性群體——13.1.2直接訪(fǎng)問(wèn)群體——數(shù)組類(lèi)template<classT>Array<T>::Array(intsz){//構(gòu)造函數(shù) assert(sz>=0);//sz為數(shù)組大小（元素個(gè)數(shù)），應(yīng)當(dāng)非負(fù)

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

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

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

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

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

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

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

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

for(inti=0;i<size;i++) list[i]=rhs.list[i]; } return*this; //返回當(dāng)前對(duì)象的引用}813.1線(xiàn)性群體——13.1.2直接訪(fǎng)問(wèn)群體——數(shù)組類(lèi)例13-1（續(xù)）//重載下標(biāo)運(yùn)算符，實(shí)現(xiàn)與普通數(shù)組一樣通過(guò)下標(biāo)訪(fǎng)問(wèn)元素，并且具有越界檢查功能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類(lèi)的對(duì)象名轉(zhuǎn)換為T(mén)類(lèi)型的指針template<classT>Array<T>::operatorT*(){ returnlist; //返回當(dāng)前對(duì)象中私有數(shù)組的首地址}

913.1線(xiàn)性群體——13.1.2直接訪(fǎng)問(wèn)群體——數(shù)組類(lèi)例13-1（續(xù)）template<classT>Array<T>::operatorconstT*()const{ returnlist; //返回當(dāng)前對(duì)象中私有數(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]; //申請(qǐng)新的數(shù)組內(nèi)存

intn=(sz<size)?sz:size;//將sz與size中較小的一個(gè)賦值給n //將原有數(shù)組中前n個(gè)元素復(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

1013.1線(xiàn)性群體——13.1.2直接訪(fǎng)問(wèn)群體——數(shù)組類(lèi)例13-1（續(xù)）11淺拷貝13.1線(xiàn)性群體——13.1.2直接訪(fǎng)問(wèn)群體——數(shù)組類(lèi)template<classT>Array<T>::Array(constArray<T>&x){size=x.size;list=x.list;}intmain(){Array<int>a(10);......Array<int>b(a);......}

listsizeaa的數(shù)組元素占用的內(nèi)存拷貝前

listsizeaa的數(shù)組元素占用的內(nèi)存拷貝后listsizeb12深拷貝13.1線(xiàn)性群體——13.1.2直接訪(fǎng)問(wèn)群體——數(shù)組類(lèi)listsizeaa的數(shù)組元素占用的內(nèi)存拷貝前l(fā)istsizeaa的數(shù)組元素占用的內(nèi)存拷貝后listsizebb的數(shù)組元素占用的內(nèi)存為什么有的函數(shù)返回引用如果一個(gè)函數(shù)的返回值是一個(gè)對(duì)象的值，就不應(yīng)成為左值。如果返回值為引用。由于引用是對(duì)象的別名，通過(guò)引用當(dāng)然可以改變對(duì)象的值。1313.1線(xiàn)性群體——13.1.2直接訪(fǎng)問(wèn)群體——數(shù)組類(lèi)指針轉(zhuǎn)換運(yùn)算符的作用舉例#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;}1413.1線(xiàn)性群體——13.1.2直接訪(fǎng)問(wèn)群體——數(shù)組類(lèi)Array類(lèi)的應(yīng)用例13-2（教材例9-4）求范圍2~N中的質(zhì)數(shù)，N在程序運(yùn)行時(shí)由鍵盤(pán)輸入。1513.1線(xiàn)性群體——13.1.2直接訪(fǎng)問(wèn)群體——數(shù)組類(lèi)16#include<iostream>#include<iomanip>#include"Array.h"usingnamespacestd;intmain(){ Array<int>a(10); //用來(lái)存放質(zhì)數(shù)的數(shù)組，初始狀態(tài)有10個(gè)元素。

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]整除，說(shuō)明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;}13.1線(xiàn)性群體——13.1.2直接訪(fǎng)問(wèn)群體——數(shù)組類(lèi)例13-2（續(xù)）13.1.3順序訪(fǎng)問(wèn)群體——鏈表類(lèi)鏈表是一種動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)，可以用來(lái)表示順序訪(fǎng)問(wèn)的線(xià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)的地址）。如果鏈表每個(gè)結(jié)點(diǎn)中只有一個(gè)指向后繼結(jié)點(diǎn)的指針，則該鏈表稱(chēng)為單鏈表。1713.1線(xiàn)性群體18單鏈表13.1線(xiàn)性群體——13.1.3順序訪(fǎng)問(wèn)群體——鏈表類(lèi)data1data2data3datanNULL…h(huán)eadrear19單鏈表的結(jié)點(diǎn)類(lèi)模板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;};13.1線(xiàn)性群體——13.1.3順序訪(fǎng)問(wèn)群體——鏈表類(lèi)20在結(jié)點(diǎn)之后插入一個(gè)結(jié)點(diǎn)13.1線(xiàn)性群體——13.1.3順序訪(fǎng)問(wèn)群體——鏈表類(lèi)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}21

刪除結(jié)點(diǎn)之后的結(jié)點(diǎn)13.1線(xiàn)性群體——13.1.3順序訪(fǎng)問(wèn)群體——鏈表類(lèi)data1data2data3…tempPtrNode<T>*Node<T>::deleteAfter(void){Node<T>*tempPtr=next;if(next==0)return0;next=tempPtr->next;returntempPtr;}例13-3（教材例9-5）結(jié)點(diǎn)類(lèi)模扳//Node.h#ifndefNODE_H#defineNODE_H//類(lèi)模板的定義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)之后插入一個(gè)同類(lèi)結(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)的地址};2213.1線(xiàn)性群體——13.1.3順序訪(fǎng)問(wèn)群體——鏈表類(lèi)//類(lèi)的實(shí)現(xiàn)部分//構(gòu)造函數(shù)，初始化數(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;}2313.1線(xiàn)性群體——13.1.3順序訪(fǎng)問(wèn)群體——鏈表類(lèi)例13-3（續(xù)）//在當(dāng)前結(jié)點(diǎn)之后插入一個(gè)結(jié)點(diǎn)ptemplate<classT>voidNode<T>::insertAfter(Node<T>*p){p->next=next;//p結(jié)點(diǎ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)地址存儲(chǔ)到tempPtr中

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

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

returntempPtr; //返回被刪除的結(jié)點(diǎn)的地址}#endif//NODE_H2413.1線(xiàn)性群體——13.1.3順序訪(fǎng)問(wèn)群體——鏈表類(lèi)例13-3（續(xù)）鏈表的基本操作生成結(jié)點(diǎn)插入結(jié)點(diǎn)查找結(jié)點(diǎn)刪除結(jié)點(diǎn)遍歷鏈表清空鏈表2513.1線(xiàn)性群體——13.1.3順序訪(fǎng)問(wèn)群體——鏈表類(lèi)例13-4（教材例9-6）

鏈表類(lèi)模板#ifndefLINKEDLIST_H#defineLINKEDLIST_H#include"Node.h"template<classT>classLinkedList{private: //數(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_H2613.1線(xiàn)性群體——13.1.3順序訪(fǎng)問(wèn)群體——鏈表類(lèi)例13-5（教材例9-7）

鏈表類(lèi)應(yīng)用舉例//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;}2713.1線(xiàn)性群體——13.1.3順序訪(fǎng)問(wèn)群體——鏈表類(lèi)例13-5（續(xù)）運(yùn)行結(jié)果如下：36575245910List:10954257563Pleaseentersomeintegerneededtobedeleted:5List:109427632813.1線(xiàn)性群體——13.1.3順序訪(fǎng)問(wèn)群體——鏈表類(lèi)13.1.4棧類(lèi)棧是只能從一端訪(fǎng)問(wèn)的線(xiàn)性群體，可以訪(fǎng)問(wèn)的這一端稱(chēng)棧頂，另一端稱(chēng)棧底。2913.1線(xiàn)性群體an┆a2a1入棧出棧棧頂棧底棧的應(yīng)用舉例——表達(dá)式處理3013.1線(xiàn)性群體——13.1.4棧類(lèi)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)棧空棧中沒(méi)有元素棧滿(mǎn)棧中元素個(gè)數(shù)達(dá)到上限一般狀態(tài)棧中有元素，但未達(dá)到棧滿(mǎn)狀態(tài)3113.1線(xiàn)性群體——13.1.4棧類(lèi)3213.1線(xiàn)性群體——13.1.4棧類(lèi)棧頂┆an┆a1a0入棧出棧數(shù)組下標(biāo)maxn10一般狀態(tài)棧頂入棧出棧數(shù)組下標(biāo)初始狀態(tài)（棧空）maxn10棧頂amax┆an┆a1a0入棧出棧數(shù)組下標(biāo)maxn10棧滿(mǎn)狀態(tài)棧的基本操作初始化入棧出棧清空棧訪(fǎng)問(wèn)棧頂元素檢測(cè)棧的狀態(tài)（滿(mǎn)、空）3313.1線(xiàn)性群體——13.1.4棧類(lèi)例13-6（教材例9-8）

棧類(lèi)模板//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;};3413.1線(xiàn)性群體——13.1.4棧類(lèi)例13-6（續(xù)）//模板的實(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_H3513.1線(xiàn)性群體——13.1.4棧類(lèi)棧的應(yīng)用例13-7（教材例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"則輸入"35+"。乘方運(yùn)算符用"^"表示。每次運(yùn)算在前次結(jié)果基礎(chǔ)上進(jìn)行，若要將前次運(yùn)算結(jié)果清除，可鍵入"c"。當(dāng)鍵入"q"時(shí)程序結(jié)束。Calculator.hCalculator.cpp9_9.cpp3613.1線(xiàn)性群體——13.1.4棧類(lèi)37例13-7//Calculator.h#ifndefCALCULATOR_H#defineCALCULATOR_H#include"Stack.h" //包含棧類(lèi)模板定義文件classCalculator{ //計(jì)算器類(lèi)private: Stack<double>s; //操作數(shù)棧

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

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

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

voidclear(); //清空操作數(shù)棧};#endif//CALCULATOR_H13.1線(xiàn)性群體——13.1.4棧類(lèi)38例13-7(續(xù))//Calculator.cpp#include"Calculator.h"#include<iostream>#include<sstream>#include<cmath>usingnamespacestd;//工具函數(shù)，用于將字符串轉(zhuǎn)換為實(shí)數(shù)inlinedoublestringToDouble(conststring&str){ istringstreamstream(str); //字符串輸入流

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

s.push(num);}13.1線(xiàn)性群體——13.1.4棧類(lèi)39例13-7(續(xù))boolCalculator::getTwoOperands(double&opnd1,double&opnd2){ if(s.isEmpty()){ //檢查棧是否空

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

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

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

returntrue;}13.1線(xiàn)性群體——13.1.4棧類(lèi)40voidCalculator::compute(charop){ //執(zhí)行運(yù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時(shí)清空棧

}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ù)不夠，清空棧}13.1線(xiàn)性群體——13.1.4棧類(lèi)例13-7(續(xù))41voidCalculator::run(){//讀入并處理后綴表達(dá)式

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

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

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

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

s.clear();}13.1線(xiàn)性群體——13.1.4棧類(lèi)例13-7(續(xù))42例13-7(續(xù))//9_9.cpp#include"Calculator.h"intmain(){ Calculatorc; c.run(); return0;}13.1線(xiàn)性群體——13.1.4棧類(lèi)13.1.5隊(duì)列類(lèi)隊(duì)列是只能向一端添加元素，從另一端刪除元素的線(xiàn)性群體4313.1線(xiàn)性群體a1a2an-1an……隊(duì)頭隊(duì)尾入隊(duì)出隊(duì)a0隊(duì)列的基本狀態(tài)隊(duì)空隊(duì)列中沒(méi)有元素隊(duì)滿(mǎn)隊(duì)列中元素個(gè)數(shù)達(dá)到上限一般狀態(tài)隊(duì)列中有元素，但未達(dá)到隊(duì)滿(mǎn)狀態(tài)4413.1線(xiàn)性群體——13.1.5隊(duì)列類(lèi)4513.1線(xiàn)性群體——13.1.5隊(duì)列類(lèi)a0a1an-1an……隊(duì)頭隊(duì)尾入隊(duì)出隊(duì)數(shù)組下標(biāo)01n-1nmax(一般狀態(tài))……隊(duì)頭隊(duì)尾入隊(duì)出隊(duì)數(shù)組下標(biāo)01n-1nmax(隊(duì)空狀態(tài))a0a1an-1anamax……隊(duì)頭隊(duì)尾入隊(duì)出隊(duì)數(shù)組下標(biāo)01n-1nmax(隊(duì)滿(mǎn)狀態(tài))元素移動(dòng)方向元素移動(dòng)方向45循環(huán)隊(duì)列在想象中將數(shù)組彎曲成環(huán)形，元素出隊(duì)時(shí)，后繼元素不移動(dòng)，每當(dāng)隊(duì)尾達(dá)到數(shù)組最后一個(gè)元素時(shí)，便再回到數(shù)組開(kāi)頭。4613.1線(xiàn)性群體——13.1.5隊(duì)列類(lèi)4713.1線(xiàn)性群體——13.1.5隊(duì)列類(lèi)1234……m-1m-2m-30amam+1am+2a3隊(duì)頭隊(duì)尾a4am-2am-3am-1隊(duì)滿(mǎn)狀態(tài)元素個(gè)數(shù)=m1234……m-1m-2m-30隊(duì)尾隊(duì)頭隊(duì)空狀態(tài)元素個(gè)數(shù)=0隊(duì)尾1234……m-1m-2m-30a0a1a2a3隊(duì)頭一般狀態(tài)47例13-8（教材例9-10）

隊(duì)列類(lèi)模板//Queue.h#ifndefQUEUE_H#defineQUEUE_H#include<cassert>//類(lèi)模板的定義template<classT,intSIZE=50>classQueue{private: intfront,rear,count; //隊(duì)頭指針、隊(duì)尾指針、元素個(gè)數(shù)

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

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

Tremove(); //元素出隊(duì)

voidclear(); //清空隊(duì)列

constT&getFront()const; //訪(fǎng)問(wèn)隊(duì)首元素4813.1線(xiàn)性群體——13.1.5隊(duì)列類(lèi)

//測(cè)試隊(duì)列狀態(tài)

intgetLength()const;//求隊(duì)列長(zhǎng)度

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

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

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

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

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

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

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

returnlist[temp]; //返回首元素值}4913.1線(xiàn)性群體——13.1.5隊(duì)列類(lèi)例13-8（續(xù)）template<classT,intSIZE>constT&Queue<T,SIZE>::getFront()const{

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

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

returncount==0;}template<classT,intSIZE>boolQueue<T,SIZE>::isFull()const{ //測(cè)試隊(duì)滿(mǎn)否

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

count=0; front=0; rear=0;}#endif//QUEUE_H5013.1線(xiàn)性群體——13.1.5隊(duì)列類(lèi)例13-8（續(xù)）13.2群體數(shù)據(jù)的組織插入排序選擇排序交換排序順序查找折半查找5113.2群體數(shù)據(jù)的組織排序（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)整元素在序列中的位置5213.2群體數(shù)據(jù)的組織內(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)行訪(fǎng)問(wèn)的排序過(guò)程。5313.2群體數(shù)據(jù)的組織內(nèi)部排序方法插入排序選擇排序交換排序5413.2群體數(shù)據(jù)的組織插入排序的基本思想每一步將一個(gè)待排序元素按其關(guān)鍵字值的大小插入到已排序序列的適當(dāng)位置上，直到待排序元素插入完為止。5513.2群體數(shù)據(jù)的組織——13.2.1插入排序初始狀態(tài)：[5]41020123插入操作：1[4][45]10201232[10][4510]201233[20][451020]1234[12][45101220]35[3][345101220]直接插入排序在插入排序過(guò)程中，由于尋找插入位置的方法不同又可以分為不同的插入排序算法，這里我們只介紹最簡(jiǎn)單的直接插入排序算法。例13-9（教材例9-11）直接插入排序函數(shù)模板（9_11.h）5613.2群體數(shù)據(jù)的組織——13.2.1插入排序57例13-9直接插入排序函數(shù)模板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; }}13.2群體數(shù)據(jù)的組織——13.2.1插入排序選擇排序的基本思想每次從待排序序列中選擇一個(gè)關(guān)鍵字最小的元素，（當(dāng)需要按關(guān)鍵字升序排列時(shí)），順序排在已排序序列的最后，直至全部排完。5813.2群體數(shù)據(jù)的組織——13.2.2選擇排序[541020123]初始狀態(tài)：3[41020125]34[1020125]第i次選擇后，將選出的那個(gè)記錄與第i個(gè)記錄做交換。345[201210]......直接選擇排序在選擇類(lèi)排序方法中，從待排序序列中選擇元素的方法不同，又分為不同的選擇排序方法，其中最簡(jiǎn)單的是通過(guò)順序比較找出待排序序列中的最小元素，稱(chēng)為直接選擇排序。例13-10（教材例9-12

直接選擇排序函數(shù)模板（9-12.h）5913.2群體數(shù)據(jù)的組織——13.2.2選擇排序60例13-10直接選擇排序函數(shù)模板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 ]); }}13.2群體數(shù)據(jù)的組織——13.2.2選擇排序交換排