《數(shù)據(jù)結(jié)構(gòu)：思想與方法》第二章線性表

1表的概念表的實(shí)現(xiàn)線性表類的實(shí)現(xiàn)STL中表的實(shí)現(xiàn)第二章線性表2表的概念線性表是N個(gè)具有相同特征的結(jié)點(diǎn)A0,A1,…,AN-1構(gòu)成的集合。在這個(gè)集合中，除了A0

和AN-1

外，每個(gè)元素都有唯一的前趨和后繼。對(duì)于每個(gè)Ai，它的前驅(qū)是Ai-1，它的后繼是Ai+1。A0只有后繼沒有前驅(qū)，AN-1只有前驅(qū)沒有后繼。表的術(shù)語(yǔ)：N為表的大小A0稱為首結(jié)點(diǎn)，AN-1稱為尾結(jié)點(diǎn)空表：元素個(gè)數(shù)為零的表。位置：元素Ai在表中的位置為i3表的操作創(chuàng)建一個(gè)線性表create()：創(chuàng)建一個(gè)空的線性表;清除一個(gè)線性表clear()：刪除線性表中的所有數(shù)據(jù)元素；求線性表的長(zhǎng)度length()：返回線性表的長(zhǎng)度;在第i個(gè)位置插入一個(gè)元素insert(i,x)：使線性表從（a0,a1,…ai-1,ai,…an-1）變成（a0,a1,…ai-1,x,ai,…an-1），參數(shù)i的合法取值范圍是0到n；4刪除第i個(gè)位置的元素remove（i）：使線性表從（a0,a1,…ai-1,ai,ai+1

…an-1）變成（a0,a1,…ai-1,ai+1,…an-1），參數(shù)i的合法取值范圍是0到n-1;搜索某個(gè)元素在線性表中是否出現(xiàn)search(x)：在線性表中搜索x是否出現(xiàn)，并返回x的位置;訪問線性表的第i個(gè)元素visit（i）：返回線性表中第i個(gè)數(shù)據(jù)元素的值;遍歷線性表運(yùn)算traverse()：按序訪問線性表的每一數(shù)據(jù)元素。5線性表表的概念表的實(shí)現(xiàn)線性表類的實(shí)現(xiàn)STL中表的實(shí)現(xiàn)6表的實(shí)現(xiàn)線性表的順序?qū)崿F(xiàn)線性表的鏈接實(shí)現(xiàn)7線性表的順序存儲(chǔ)結(jié)構(gòu)線性表中結(jié)點(diǎn)存放在存儲(chǔ)器上一塊連續(xù)的空間中。借助存儲(chǔ)空間的連續(xù)性，結(jié)點(diǎn)可以按照其邏輯順序依次存放。結(jié)點(diǎn)存放的物理位置和它的邏輯位置是一致的。

8線性表的順序存儲(chǔ)在程序設(shè)計(jì)語(yǔ)言中，一塊連續(xù)的存儲(chǔ)空間可以用一個(gè)數(shù)組實(shí)現(xiàn)。由于線性表中的元素個(gè)數(shù)是動(dòng)態(tài)的，因此采用了動(dòng)態(tài)數(shù)組。保存一個(gè)動(dòng)態(tài)數(shù)組，需要三個(gè)變量：指向線性表元素類型的指針，數(shù)組規(guī)模（容量），數(shù)組中的元素個(gè)數(shù)（表長(zhǎng)）。anan-1…a2a1a0maxSizelengthdata9線性表的運(yùn)算實(shí)現(xiàn)length()：只需要返回length的值visit（i）：返回data[i]的值traverse()：輸出數(shù)組data的前l(fā)ength個(gè)元素clear()：只要將length置為0即可create(maxSize)：申請(qǐng)一個(gè)maxSize大小的動(dòng)態(tài)數(shù)組10search運(yùn)算的實(shí)現(xiàn)intsearch(x){num=0;for(num=0;num<length;++num)if(data[num]==x)break;if(num==length)num=-1;returnnum;}11insert(i,x)運(yùn)算的實(shí)現(xiàn)length在插入時(shí)，表長(zhǎng)會(huì)增加。當(dāng)表長(zhǎng)等于容量時(shí)，新增加的元素將無法存儲(chǔ)。此時(shí)有兩種解決方法：一種是不執(zhí)行插入，報(bào)告一個(gè)錯(cuò)誤消息；另一種是擴(kuò)大數(shù)組的容量a0a1…aiai+1…an-112voidinsert(i,x){if(length==maxSize)resize();for(j=n-1;j>=i;--j)data[j+1]=data[j];data[i]=x;++length;}13resize操作的實(shí)現(xiàn)resize操作按一定的比例擴(kuò)大數(shù)組的空間，常用的比例是擴(kuò)大一倍。數(shù)組空間在內(nèi)存中必須是連續(xù)的，因此，擴(kuò)大數(shù)組空間的操作必須重新申請(qǐng)一個(gè)更大規(guī)模的動(dòng)態(tài)數(shù)組，將原有數(shù)組的內(nèi)容拷貝到新數(shù)組中，釋放原有數(shù)組空間，將新數(shù)組作為存儲(chǔ)線性表的存儲(chǔ)區(qū)。14a0a1…an-1andatatmp15remove（i）運(yùn)算的實(shí)現(xiàn)an…ai+1ai…a1a0voidremove(i){for(j=i;j<length-1;++j)data[j]=data[j+1];--length;}16順序?qū)崿F(xiàn)的算法分析length,visit和clear的實(shí)現(xiàn)與表中的元素個(gè)數(shù)無關(guān)，因此它們的時(shí)間復(fù)雜度是O（1）。traverse()操作遍歷整個(gè)表中的所有元素，因此時(shí)間復(fù)雜度為O(n)。create操作需要申請(qǐng)一塊動(dòng)態(tài)數(shù)組的空間，并設(shè)表為空。因此也是O(1)的時(shí)間復(fù)雜度。插入操作，需要移動(dòng)結(jié)點(diǎn)。當(dāng)i等于n時(shí)，移動(dòng)次數(shù)為0。當(dāng)i等于0時(shí)，移動(dòng)次數(shù)為n。最好情況下的時(shí)間復(fù)雜度為O(1)最壞情況下的時(shí)間復(fù)雜度為O(n)平均的時(shí)間復(fù)雜度：如果在每個(gè)位置上的插入都是等概率的，則插入算法的平均時(shí)間復(fù)雜度為n/217線性表的順序?qū)崿F(xiàn)總結(jié)由于要保持邏輯次序和物理次序的一致性，順序表在插入刪除時(shí)需要移動(dòng)大量的數(shù)據(jù)，性能不太理想。由于邏輯次序和物理次序的一致性使得定位訪問的性能很好。順序表比較適合靜態(tài)的、經(jīng)常作定位訪問的線性表。18表的實(shí)現(xiàn)線性表的順序?qū)崿F(xiàn)線性表的鏈接實(shí)現(xiàn)19線性表的鏈接存儲(chǔ)結(jié)構(gòu)將每個(gè)結(jié)點(diǎn)放在一個(gè)獨(dú)立的存儲(chǔ)單元中，結(jié)點(diǎn)間的邏輯關(guān)系依靠存儲(chǔ)單元中附加的指針來給出。結(jié)點(diǎn)的存儲(chǔ)單元在物理位置上可以相鄰，也可以不相鄰。20線性表的鏈接存儲(chǔ)單鏈表雙鏈表循環(huán)鏈表21單鏈表每個(gè)結(jié)點(diǎn)附加了一個(gè)指針字段，如next，該指針指向它的直接后繼結(jié)點(diǎn)，最后一個(gè)結(jié)點(diǎn)的next字段為空。nilhead22insertai+1aixp23頭結(jié)點(diǎn)、頭指針、尾結(jié)點(diǎn)、尾指針為了消除特殊情況，通常在表頭額外增加一個(gè)相同類型的特殊結(jié)點(diǎn)，稱之為頭結(jié)點(diǎn)，在表尾也增加一個(gè)額外結(jié)點(diǎn)，稱為尾結(jié)點(diǎn)。它們不是線性表中的組成部分。頭尾結(jié)點(diǎn)的出現(xiàn)，使得在表頭和表尾位置上進(jìn)行插入和刪除和在其它結(jié)點(diǎn)位置上是完全一致的，從而使得插入和刪除算法得到簡(jiǎn)化。24帶頭結(jié)點(diǎn)的單鏈表a0a1an-1…∧head25Create函數(shù)的實(shí)現(xiàn)申請(qǐng)一塊存儲(chǔ)結(jié)點(diǎn)的空間，設(shè)結(jié)點(diǎn)的指針部分為空指針。將結(jié)點(diǎn)地址存入代表單鏈表的變量head。∧head26清除一個(gè)線性表clear()把所有結(jié)點(diǎn)的空間還給系統(tǒng)，把頭結(jié)點(diǎn)的指針部分置為空指針voidclear(){P=頭結(jié)點(diǎn)的直接后繼；

While(p!=空指針){q=p;p=p的直接后繼地址；釋放q的空間；}

頭結(jié)點(diǎn)的后繼指針置為空指針；}27求表的長(zhǎng)度length()方法1：從起始結(jié)點(diǎn)開始，沿著后繼指針鏈一個(gè)一個(gè)往后數(shù)，數(shù)到一個(gè)結(jié)點(diǎn)，長(zhǎng)度加1intlength(){len=0;p=頭結(jié)點(diǎn)的直接后繼；

While(p!=空指針){++len;p=p的直接后繼的地址；}}方法2：用空間換取時(shí)間的方法。在保存單鏈表的時(shí)候增加一個(gè)變量，保存表的長(zhǎng)度

28在第i個(gè)位置插入一個(gè)元素insert(i,x)voidinsert(i,x){for(j=0,p=head;j<i;++j)p=p的直接后繼的地址；

tmp=new結(jié)點(diǎn)；

tmp指向的結(jié)點(diǎn)的數(shù)據(jù)部分=x；

tmp指向的結(jié)點(diǎn)的指針部分=p的直接后繼的地址；

p指向的結(jié)點(diǎn)的指針部分=tmp；}29刪除第i個(gè)位置的元素remove（i）voidremove(i){for(j=0,p=head;j<i;++j)p=p的直接后繼的地址；

tmp=p的直接后繼的地址；

p的指針部分=tmp的直接后繼的地址；

freetmp；}30搜索某個(gè)元素在線性表中是否出現(xiàn)search(x)intsearch(x){num=0;p=頭結(jié)點(diǎn)的直接后繼；

While(p!=空指針&&p的數(shù)據(jù)部分！=x){++num;p=p的直接后繼的地址；}if（p==空指針）num=-1；

returnnum;}31訪問線性表的第i個(gè)元素visit（i）dataTypevisit(i){for(j=0,p=head;j<i;++j)p=p的直接后繼的地址；

returnp指向的結(jié)點(diǎn)的數(shù)據(jù)部分；}32遍歷運(yùn)算traverse()voidtraverse(){p=頭結(jié)點(diǎn)的直接后繼；

While(p!=空指針){cout<<p指向結(jié)點(diǎn)的數(shù)據(jù)部分；

p=p的直接后繼的地址；

}}33線性表的鏈接存儲(chǔ)單鏈表雙鏈表循環(huán)鏈表34雙鏈表每個(gè)結(jié)點(diǎn)附加了兩個(gè)指針字段，如prior和next，其中prior字段給出直接前驅(qū)結(jié)點(diǎn)的地址，next給出直接后繼結(jié)點(diǎn)的地址。頭結(jié)點(diǎn)中prior字段為空，它的next字段給出線性表中的首結(jié)點(diǎn)的地址，尾結(jié)點(diǎn)中next字段為空，這種形式的鏈表稱為雙鏈表。headtail∧∧35Create運(yùn)算創(chuàng)建一個(gè)雙鏈表就是創(chuàng)建一個(gè)只有頭尾結(jié)點(diǎn)的鏈表，把頭結(jié)點(diǎn)的地址保存在head中，尾結(jié)點(diǎn)的地址保存在tail中head∧tail∧36insertxp37removexp38線性表的鏈接存儲(chǔ)單鏈表雙鏈表循環(huán)鏈表39單循環(huán)鏈表一般單循環(huán)鏈表不帶頭結(jié)點(diǎn)head40雙循環(huán)鏈表頭結(jié)點(diǎn)中prior字段給出尾結(jié)點(diǎn)的地址，尾結(jié)點(diǎn)中next字段給出頭結(jié)點(diǎn)的地址一般也不設(shè)頭尾結(jié)點(diǎn)41線性表表的概念表的實(shí)現(xiàn)線性表類的實(shí)現(xiàn)STL中表的實(shí)現(xiàn)42線性表類的實(shí)現(xiàn)線性表抽象類順序表類雙鏈表類43線性表的抽象類template<classelemType>classlist{public:virtualvoidclear()=0;virtualintlength()const=0;virtualvoidinsert(inti,constelemType&x)=0;virtualvoidremove(inti)=0;virtualintsearch(constelemType&x)const=0;virtualelemTypevisit(inti)const=0;virtualvoidtraverse()const=0virtual~list(){};};44線性表的抽象類線性表的抽象類是一個(gè)類模板抽象類不包括create函數(shù)。這個(gè)運(yùn)算由每個(gè)線性表類的構(gòu)造函數(shù)完成增加了一個(gè)析構(gòu)函數(shù)，以防內(nèi)存泄漏45線性表類的實(shí)現(xiàn)線性表抽象類順序表類雙鏈表類46順序表類的定義classOutOfBound{};classIllegalSize{};template<classelemType>classseqList:publiclist<elemType>{private:elemType*data;intcurrentLength;intmaxSize;voiddoubleSpace();47public:seqList(intinitSize=10);~seqList(){delete[]data;}voidclear(){currentLength=0;}intlength()const{returncurrentLength;}voidinsert(inti,constelemType&x);voidremove(inti);intsearch(constelemType&x)const;elemTypevisit(inti)const;voidtraverse()const;};48構(gòu)造函數(shù)template<classelemType>seqList<elemType>::seqList(intinitSize){if(initSize<=0)throwIllegalSize();data=newelemType[initSize];maxSize=initSize;currentLength=0;}maxSizelength49inserttemplate<classelemType>voidseqList<elemType>::insert(inti,constelemType&x){if(i<0||i>currentLength)throwOutOfBound();if(currentLength==maxSize)doubleSpace();for(intj=currentLength;j>i;j--)data[j]=data[j-1];data[i]=x;++currentLength;}50removetemplate<classelemType>voidseqList<elemType>::remove(inti){if(i<0||i>currentLength-1)throwOutOfBound();for(intj=i;j<currentLength-1;j++)data[j]=data[j+1];--currentLength;}51doubleSpacetemplate<classelemType>voidseqList<elemType>::doubleSpace(){elemType*tmp=data;maxSize*=2;data=newelemType[maxSize];for(inti=0;i<currentLength;++i)data[i]=tmp[i];

delete[]tmp;}52其他函數(shù)自己實(shí)現(xiàn)53線性表類的實(shí)現(xiàn)線性表抽象類順序表類雙鏈表類54鏈表類的設(shè)計(jì)以雙鏈表為例鏈表類的數(shù)據(jù)成員：頭指針、尾指針，以及為了提高時(shí)間性能而設(shè)置的數(shù)據(jù)成員currentLength鏈表類必須實(shí)現(xiàn)線性表的所有操作。為保證這一點(diǎn)，鏈表類從線性表的抽象類繼承。鏈表的插入、刪除操作都需要將指針移到被操作結(jié)點(diǎn)的前一結(jié)點(diǎn)。特設(shè)計(jì)函數(shù)move實(shí)現(xiàn)55結(jié)點(diǎn)及其組成鏈表中的結(jié)點(diǎn)包含三部分：數(shù)據(jù)字段、前趨指針和后繼指針字段。數(shù)據(jù)字段可以是任何類型的數(shù)據(jù)，這里仍然用ElemType表示；指針字段用于存放其他相關(guān)結(jié)點(diǎn)的地址值。由于結(jié)點(diǎn)類型是鏈表專用的，因此可設(shè)為內(nèi)嵌類。由于鏈表的操作是通過對(duì)結(jié)點(diǎn)的操作實(shí)現(xiàn)的，于是把結(jié)點(diǎn)類定義成struct，以方便鏈表類訪問。56雙鏈表類的定義template<classelemType>classlinkList:publiclist<elemType>

{private:structnode{elemTypedata; node*prev,*next; node(constelemType&x,node*p=NULL,node*n=NULL)

{data=x;next=n;prev=p;} node():next(NULL),prev(NULL){} ~node(){} };node*head,*tail;intcurrentLength;node*move(inti)const;57public:linkList();~linkList(){clear();deletehead;deletetail;}voidclear();intlength()const{returncurrentLength;}voidinsert(inti,constelemType&x);voidremove(inti);intsearch(constelemType&x)const;elemTypevisit(inti)const;voidtraverse()const;};58構(gòu)造函數(shù)template<classelemType>linkList<elemType>::linkList(){head=newnode;head->next=tail=newnode;tail->prev=head;currentLength=0;}

ΛΛheadtail59cleartemplate<classelemType>voidlinkList<elemType>::clear(){node*p=head->next,*q;head->next=tail;tail->prev=head;while(p!=tail){q=p->next; deletep;p=q; }currentLength=0;}60template<classelemType>voidlinkList<elemType>::insert(inti,constelemType&x){node*pos,*tmp;pos=move(i);tmp=newnode(x,pos->prev,pos);pos->prev->next=tmp;pos->prev=tmp;++currentLength;}insertposxtmp61removetemplate<classelemType>voidlinkList<elemType>::remove(inti){node*pos;pos=move(i);pos->prev->next=pos->next;

pos->next->prev=pos->prev;deletepos;

--currentLength;}xpospos62searchtemplate<classelemType>intlinkList<elemType>::search(constelemType&x)const{node*p=head->next;inti=0;while(p!=tail&&p->data!=x){p=p->next;++i;}if(p==tail)return-1;elsereturni;}63visittemplate<classelemType>elemTypelinkList<elemType>::visit(inti)const{node*p=move(i);returnp->data;}64traversetemplate<classelemType>voidlinkList<elemType>::traverse()const{node*p=head->next;cout<<endl;while(p!=tail){ cout<<p->data<<""; p=p->next;}cout<<endl;} 65movetemplate<classelemType>linkList<elemType>::node*linkList<elemType>::move(inti)const{node*p=head->next;if(i<0||i>currentLength)throwOutOfBound();while(i--)p=p->next;returnp;}66缺點(diǎn)雙鏈表類僅實(shí)現(xiàn)了線性表的基本運(yùn)算，并沒有用到雙鏈表的特點(diǎn)，如逆向查找等67線性表表的概念表的實(shí)現(xiàn)線性表類的實(shí)現(xiàn)STL中表的實(shí)現(xiàn)68STLSTL（標(biāo)準(zhǔn)模版庫(kù)）是C++中數(shù)據(jù)結(jié)構(gòu)的實(shí)現(xiàn)。這些數(shù)據(jù)結(jié)構(gòu)被稱為集合或容器。STL中線性表的實(shí)現(xiàn)有兩種：Vector：線性表的順序?qū)崿F(xiàn)List：線性表的雙鏈表的實(shí)現(xiàn)69Vector和list共同支持的操作所有的容器都支持的整體操作：求規(guī)模、清空和判空在表尾的插入和刪除以及取表頭表尾元素List特有的操作：表頭的插入和刪除Vector特有的操作：[]的重載，按下標(biāo)取元素，求容量，重新設(shè)置數(shù)組的大小。迭代器：兩者都能用迭代器訪問70STL中的迭代器操作獲取一個(gè)迭代器：Begin：返回一個(gè)指向第一個(gè)節(jié)點(diǎn)的迭代器End：返回一個(gè)指向最后一個(gè)節(jié)點(diǎn)的迭代器迭代器本身的方法：向后移動(dòng)，取迭代器指向的元素值，判迭代器相等和不相等需要迭代器的容器操作：在指定位置上插入一元素刪除指定位置的元素刪除指定位置之間的所有元素71STL中線性表的實(shí)現(xiàn)Vector：線性表的順序?qū)崿F(xiàn)，且大小可增長(zhǎng)List：線性表的雙鏈表實(shí)現(xiàn)72Vector的特性Vector維護(hù)一個(gè)C的原始數(shù)組、容量及大小規(guī)模提供拷貝構(gòu)造函數(shù)和賦值運(yùn)算符的重載函數(shù)，實(shí)現(xiàn)了對(duì)數(shù)組的整體操作可以修改數(shù)組的容量提供[]運(yùn)算符重載提供了一個(gè)內(nèi)嵌的迭代器頭文件：vector73Vector的定義template<classobject>classVector{private:inttheSize;inttheCapacity;object*objects;public:enum{SPARE_CAPACITY=16};74explicitVector(intinitSize=0);Vector(constVector&R);~Vector();constVector&operator=(constVector&R);voidresize(intnewsize);//重新設(shè)置表的大小voidreserve(intnewCapacity);//重新設(shè)置數(shù)組的容量

//[]重載object&operator[](intindex);constobject&operator[](intindex)const;不允許隱式轉(zhuǎn)換75boolempty()const;intsize()const;intcapacity()const;//對(duì)數(shù)據(jù)元素的操作

voidpush_back(constobject&x);//添加在表尾

voidpop_back();//刪除表尾元素

constobject&back()const;//返回表尾元素的值76//迭代器操作typedefobject*iterator;typedefconstobject*const_iterator;iteratorbegin();//返回元素0的地址const_iteratorbegin()const;//返回元素0的地址iteratorend();//指向最后一個(gè)元素的地址const_iteratorend()const;//指向最后一個(gè)元素的地址};77Vector的使用#include<iostream>#include<vector>usingnamespacestd;intmain(){vector<int>v;

cout<<"theinitialsizeofvis:"<<v.size()<<"\ntheinitialcapacityofvis:"<<v.capacity()<<endl;

78v.push_back(2);cout<<"\nafterpush2,capacityofvis:"<<v.capacity()<<endl;v.push_back(3);cout<<"\nafterpust3,capacityofvis:“<<v.capacity()<<endl;v.push_back(4);cout<<"\nafterpush4,capacityofvis:“<<v.capacity()<<endl;cout<<"\nthesizeofvis:"<<v.size()<<"\nthecapacityofvis:“<<v.capacity()<<endl;79cout<<"\ncontentsofvusing[]:";

for(inti=0;i<v.size();i++)cout<<v[i]<<"";cout<<endl;cout<<"\ncontentsofvusingiteratornotation:";vector<int>::const_iteratorp;for(p=v.begin();p!=v.end();p++)cout<<*p<<"";cout<<endl;}80執(zhí)行結(jié)果theinitialsizeofvis:0theinitialcapacityofvis:0Afterpush2,capacityofvis:1Afterpush3,capacityofvis:2Afterpush4,capacityofvis:4thesizeofvis:3thecapacityofvis:4contentsofvusing[]:234contentsofvusingiteratornotation:23481STL中表的實(shí)現(xiàn)Vector：線性表的順序?qū)崿F(xiàn)，且大小可增長(zhǎng)List：線性表的雙鏈表實(shí)現(xiàn)STL（標(biāo)準(zhǔn)模版庫(kù)）是C++中數(shù)據(jù)結(jié)構(gòu)的實(shí)現(xiàn)。82List的實(shí)現(xiàn)采用了帶頭節(jié)點(diǎn)的雙鏈表實(shí)現(xiàn)ΛΛheadtail83List的功能允許在任何位置插入和刪除支持雙向迭代器頭文件：list84List的定義Template<classobject>Classlist{private:structnode{…..};intthesize;node*head,*tail;

voidinit();85Public:classconst_iterator{…}classiterator:publicconst_iterator{…}

list();list(constlist&r);~list();constlist&operator=(constlist&r);86//迭代器操作iteratorbegin();const_iteratorbegin()const;iteratorend();const_iteratorend()const;iteratorinsert(iteratoritr,constObject&x)；iteratorerase(iteratoritr)；iteratorerase(iteratorstart,iteratorend)；87Intsize()const;Boolempty()const;Voidclear();Object&front()；constObject&front()const；Object&back()；constObject&back()const；voidpush_front(constObject&x)；voidpush_back(constObject&x)；voidpop_front()；voidpop_back()；;88List的應(yīng)用#include<iostream>#include<list>usingnamespacestd;template<classobject>voidprintall(constlist<object>&v);intmain(){list<int>v1;

v1.push_front(1);v1.push_front(2);v1.push_back(4);v1.push_back(3);printall(v1);list<int>::iteratoritr=v1.begin(),itre=v1.end();for(inti=5;itr!=itre;++itr,++i)v1.insert(itr,i);printall(v1);return0;}contentsofvaluesis:2143contentsofvaluesis:5261748389template<classobject>voidprintall(constlist<object>&v){if(v.empty())cout<<"\nlistisempty!";else{ list<object>::const_iteratoritr,itre; itr=v.begin(); itre=v.end(); do{cout<<*itr<<''; ++itr; }while(itr!=itre); }cout<<endl;}90第三章棧棧的概念棧的順序?qū)崿F(xiàn)棧的鏈接實(shí)現(xiàn)棧類的實(shí)現(xiàn)STL中的棧棧的應(yīng)用91棧后進(jìn)先出(LIFO,LastInFirstOut)或先進(jìn)后出(FILO,FirstInLastOut)結(jié)構(gòu)，最先(晚)到達(dá)棧的結(jié)點(diǎn)將最晚(先)被刪除。

乒乓球進(jìn)盒、出盒92相關(guān)概念an-1an-2…a1a0…出棧進(jìn)棧棧底棧頂93相關(guān)概念棧底(bottom)：結(jié)構(gòu)的首部(結(jié)點(diǎn)最早到達(dá)的部分)棧頂（top）：結(jié)構(gòu)的尾部(結(jié)點(diǎn)最晚到達(dá)的部分)出棧（Pop）：結(jié)點(diǎn)從棧頂刪除進(jìn)棧（Push）：結(jié)點(diǎn)在棧頂位置插入空棧：棧中結(jié)點(diǎn)個(gè)數(shù)為零時(shí)94棧的運(yùn)算創(chuàng)建一個(gè)棧create()：創(chuàng)建一個(gè)空的棧；進(jìn)棧push(x)：將x插入棧中，使之成為棧頂元素；出棧pop()：刪除棧頂元素并返回棧頂元素值；讀棧頂元素top()：返回棧頂元素值但不刪除棧頂元素；判?？読sEmpty()：若棧為空，返回true，否則返回false。95棧棧的概念棧的順序?qū)崿F(xiàn)棧的鏈接實(shí)現(xiàn)棧類的實(shí)現(xiàn)STL中的棧棧的應(yīng)用96棧的順序?qū)崿F(xiàn)用連續(xù)的空間存儲(chǔ)棧中的結(jié)點(diǎn)，即數(shù)組進(jìn)棧和出棧總是在棧頂一端進(jìn)行，不會(huì)引起類似順序表中的大量數(shù)據(jù)的移動(dòng)。用數(shù)組的后端表示棧頂。an…a1a0top_p棧底maxSizeelem97順序存儲(chǔ)時(shí)的運(yùn)算實(shí)現(xiàn)create()：按照用戶估計(jì)的棧的規(guī)模申請(qǐng)一個(gè)動(dòng)態(tài)數(shù)組，將數(shù)組地址保存在data中，數(shù)組規(guī)模保存在maxSize中，并設(shè)top_p的值為-1。push(x)：將top_p加1，將x放入top_p指出的位置中。但要注意數(shù)組滿的情況。pop()：返回top_p指出的位置中的值并將top_p減1。top()：與pop類似，只是不需要將top_p減1。isEmpty()：若top_p的值為-1，返回true，否則返回false。98順序?qū)崿F(xiàn)性能分析除了進(jìn)棧操作以外，所有運(yùn)算實(shí)現(xiàn)的時(shí)間復(fù)雜度都是O（1）。進(jìn)棧運(yùn)算在最壞情況下的時(shí)間復(fù)雜度是O（N）。但最壞情況在N次進(jìn)棧操作中至多出現(xiàn)一次。如果把擴(kuò)展數(shù)組規(guī)模所需的時(shí)間均攤到每個(gè)插入操作，每個(gè)插入只多了一個(gè)拷貝操作，因此從平均的意義上講，插入運(yùn)算還是常量的時(shí)間復(fù)雜度。這種分析方法稱為均攤分析法。99棧棧的概念棧的順序?qū)崿F(xiàn)棧的鏈接實(shí)現(xiàn)棧類的實(shí)現(xiàn)STL中的棧棧的應(yīng)用100棧的鏈接實(shí)現(xiàn)棧的操作都是在棧頂進(jìn)行的，不需要找某一元素的直接前驅(qū)的操作，因此不需要雙鏈表，用單鏈表就足夠了，而且不需要頭結(jié)點(diǎn)對(duì)棧來講，只需要考慮棧頂元素的插入刪除。從棧的基本運(yùn)算的實(shí)現(xiàn)方便性考慮，可將單鏈表的頭指針指向棧頂。101棧的鏈接實(shí)現(xiàn)an-1an-2a0…∧top_p102鏈接存儲(chǔ)時(shí)的運(yùn)算實(shí)現(xiàn)create()：將top_p設(shè)為空指針。push(x)：將x插入到單鏈表的表頭voidpush(x){p=new結(jié)點(diǎn)；

p指向的結(jié)點(diǎn)的數(shù)據(jù)部分=x；

p指向的結(jié)點(diǎn)的指針部分=top_p；

top_p=p;}103鏈接存儲(chǔ)時(shí)的運(yùn)算實(shí)現(xiàn)pop()：刪除表頭元素dataTypepop(){p=top_p;top_p=top_p指向的結(jié)點(diǎn)的指針部分；

x=p指向的結(jié)點(diǎn)的數(shù)據(jù)部分；

deletep;returnx;}104鏈接存儲(chǔ)時(shí)的運(yùn)算實(shí)現(xiàn)top()：返回top_p指向的結(jié)點(diǎn)的值。isEmpty()：若top_p的值為空指針，返回true，否則返回false。105鏈接棧的性能分析由于所有的操作都是對(duì)棧頂?shù)牟僮?，郵展中的元素個(gè)數(shù)無關(guān)。所以，所有運(yùn)算的時(shí)間復(fù)雜度都是O（1）106棧棧的概念棧的順序?qū)崿F(xiàn)棧的鏈接實(shí)現(xiàn)棧類的實(shí)現(xiàn)STL中的棧棧的應(yīng)用107棧的抽象類template<classelemType>classstack{public: virtualboolisEmpty()const=0; virtualvoidpush(constelemType&x)=0; virtualelemTypepop()=0;virtualelemTypetop()const=0; virtual~stack(){}};108順序棧類template<classelemType>classseqStack:publicstack<elemType>{private:elemType*elem; inttop_p; intmaxSize; voiddoubleSpace();109public:seqStack(intinitSize=10){ elem=newelemType[initSize]; maxSize=initSize;top_p=-1;}

~seqStack(){delete[]elem;}boolisEmpty()const{returntop_p==-1;}110voidpush(constelemType&x){ if(top_p==maxSize-1)doubleSpace(); elem[++top_p]=x;}

elemTypepop(){returnelem[top_p--];}

elemTypetop()const{returnelem[top_p];} };111doubleSpacetemplate<classelemType>voidseqStack<elemType>::doubleSpace(){

elemType*tmp=elem;

elem=newelemType[2*maxSize]; for(inti=0;i<maxSize;++i) elem[i]=tmp[i];

maxSize*=2; delete[]tmp;}112鏈接棧類template<classelemType>classlinkStack:publicstack<elemType>

{private:structnode{elemTypedata;

node*next; node(constelemType&x,node*N=NULL) {data=x;next=N;} node():next(NULL){} ~node(){} };node*elem;113public:linkStack(){elem=NULL;}

~linkStack();boolisEmpty()const{returnelem==NULL;}voidpush(constelemType&x){node*tmp=newnode(x,elem);

elem=tmp;}elemTypepop(){node*tmp=elem;elemTypex=tmp->data; elem=elem->next; deletetmp;

returnx;}elemTypetop()const{returnelem->data; } };114析構(gòu)函數(shù)template<classelemType>linkStack<elemType>::~linkStack(){ node*tmp; while(elem!=NULL){ tmp=elem; elem=elem->next; deletetmp; }}115棧棧的概念棧的順序?qū)崿F(xiàn)棧的鏈接實(shí)現(xiàn)棧類的實(shí)現(xiàn)STL中的棧棧的應(yīng)用116STL中的棧棧本質(zhì)上是一個(gè)線性表，在STL中棧類是借助于線性表類實(shí)現(xiàn)的。STL中的棧提供四個(gè)標(biāo)準(zhǔn)運(yùn)算：push、pop、top和empty。在STL中，借助于其他容器存儲(chǔ)數(shù)據(jù)的容器稱為容器適配器。棧就是一個(gè)容器適配器117棧的類模板定義一個(gè)棧對(duì)象要指明棧中元素的類型以及借助于哪一個(gè)容器，因此棧的類模板有兩個(gè)模板參數(shù)：棧元素類型和所借助的容器類型。?？梢越柚娜萜饔衯ector,list和deque。棧的類模板的第二個(gè)參數(shù)帶有缺省值deque118STL棧的使用#include<iostream>#include<stack>usingnamespacestd;intmain(){stack<int,vector<int>>s1;stack<int,list<int>>s2;inti;for(i=0;i<10;++i)s1.push(i);while(!s1.empty()){cout<<s1.top()<<'';s1.pop();}cout<<endl;for(i=0;i<10;++i)s2.push(i);while(!s2.empty()){cout<<s2.top()<<'';s2.pop();}cout<<endl;return0;}輸出：9876543210119棧棧的概念棧的順序?qū)崿F(xiàn)棧的鏈接實(shí)現(xiàn)棧類的實(shí)現(xiàn)STL中的棧棧的應(yīng)用120棧的應(yīng)用遞歸函數(shù)的非遞歸實(shí)現(xiàn)符號(hào)平衡檢查表達(dá)式的計(jì)算121棧的應(yīng)用—遞歸函數(shù)的非遞歸實(shí)現(xiàn)遞歸的本質(zhì)是函數(shù)調(diào)用，而函數(shù)調(diào)用是通過棧實(shí)現(xiàn)的。因此，遞歸可以用棧消除。voidf1(){…r1:f2();r2:…}voidf2(){…t1:f3();t2:…}voidf3(){……}122函數(shù)執(zhí)行過程f1f2f3r1t1r2t2123函數(shù)調(diào)用的實(shí)現(xiàn)設(shè)置一個(gè)棧模擬函數(shù)調(diào)用。當(dāng)發(fā)生函數(shù)調(diào)用時(shí)，將當(dāng)前的函數(shù)的現(xiàn)場(chǎng)進(jìn)棧。調(diào)用f2前Top調(diào)用f2后Topr2調(diào)用f3后Topr2t2返回f2后Topr2返回f1后Top124遞歸遞歸是一種特殊的函數(shù)調(diào)用，是在一個(gè)函數(shù)中又調(diào)用了函數(shù)本身。遞歸程序的本質(zhì)是函數(shù)調(diào)用，而函數(shù)調(diào)用是要花費(fèi)額外的時(shí)間和空間。在系統(tǒng)內(nèi)部，函數(shù)調(diào)用是用棧來實(shí)現(xiàn)，如果程序員可以自己控制這個(gè)棧，就可以消除遞歸調(diào)用。125快速排序voidquicksort(inta[],intlow,inthigh){intmid;if(low>=high)return;mid=divide(a,low,high);quicksort(a,low,mid-1);quicksort(a,mid+1,high);}126快速排序的非遞歸實(shí)現(xiàn)設(shè)置一個(gè)棧，記錄要做的工作，即要排序的數(shù)據(jù)段先將整個(gè)數(shù)組進(jìn)棧當(dāng)排序區(qū)間被分成兩半時(shí)，把一半進(jìn)棧，先排序另一半。排完后再去檢查棧是否為空，為空，則排序結(jié)束，否則從棧中彈出一個(gè)區(qū)間，排序該區(qū)間。棧元素的格式：

structnode{intleft;intright;};12794183650941836startfinish5240986134mid20startfinish986134finishstart986134986431mid10128voidquicksort(inta[],intsize){seqStack<node>st;intmid,start,finish;nodes;if(size<=1)return;//排序整個(gè)數(shù)組

s.left=0;s.right=size-1;st.push(s);129while(!st.isEmpty()){s=st.pop();start=s.left;finish=s.right;mid=divide(a,start,finish);if(mid-start>1){s.left=start;s.right=mid-1;st.push(s);}if(finish-mid>1){s.left=mid+1;s.right=finish;st.push(s)；}}}130棧的應(yīng)用遞歸函數(shù)的非遞歸實(shí)現(xiàn)符號(hào)平衡檢查表達(dá)式的計(jì)算131括號(hào)配對(duì)檢查編譯程序的任務(wù)之一，就是檢查括號(hào)是否配對(duì)。如：括號(hào)(、[和{后面必須依次跟隨相應(yīng)的}、]及)，“后面必須有”。簡(jiǎn)單地用開括號(hào)和閉括號(hào)的數(shù)量是否相等來判斷開括號(hào)與閉括號(hào)是否配對(duì)是不行的。例如，符號(hào)串[（）]是正確的，而符號(hào)串（[）]是不正確的。因?yàn)楫?dāng)遇到）那樣的閉括號(hào)時(shí)，它與最近遇到開括號(hào)匹配。132使用棧解決符號(hào)配對(duì)使用棧，遇到左括號(hào)進(jìn)棧，見到右括號(hào)，則出棧，并比較兩者是否配對(duì)。如判斷（3+（5-2）*（6+4）/2），（3+（（5-2）*（6+4）/2）

“abc”，‘n’

（a[3]+a[4]–‘a(chǎn)’）133算法首先創(chuàng)建一個(gè)空棧。從源程序中讀入符號(hào)。如果讀入的符號(hào)是開符號(hào)，那末就將其進(jìn)棧。如果讀入的符號(hào)是一個(gè)閉符號(hào)但棧是空的，出錯(cuò)。否則，將棧中的符號(hào)出棧。如果出棧的符號(hào)和和讀入的閉符號(hào)不匹配，出錯(cuò)。繼續(xù)從文件中讀入下一個(gè)符號(hào)，非空則轉(zhuǎn)向3，否則執(zhí)行7。如果棧非空，報(bào)告出錯(cuò)，否則括號(hào)配對(duì)成功。134細(xì)節(jié)問題如果對(duì)C++的源程序使用此算法，需要考慮三種括號(hào)：圓括號(hào)、方括號(hào)和花括號(hào)。但有時(shí)又不需要考慮圓括號(hào)、花括號(hào)、方括號(hào)是否匹配的問題。例如，當(dāng)括號(hào)出現(xiàn)在注釋、字符串常量、字符常量中時(shí)，就不需要考慮它的匹配問題。在C++中有很多轉(zhuǎn)義字符，因此在讀入一個(gè)字符時(shí)，還必須考慮如何識(shí)別轉(zhuǎn)義字符。135要求設(shè)計(jì)一個(gè)類Balance：對(duì)象初始化時(shí)傳給它一個(gè)源文件名。這個(gè)類提供一個(gè)成員函數(shù)checkBalance檢查源文件中的符號(hào)是否配對(duì)。輸出所有不匹配的符號(hào)及所在的行號(hào)136類的定義classbalance{private: ifstreamfin;//待檢查的文件流

intcurrentLine;//正在處理行的的行號(hào)

intErrors;//已發(fā)現(xiàn)的錯(cuò)誤數(shù)

structSymbol{charToken;intTheLine;};enumCommentType{SlashSlash,SlashStar};public: balance(constchar*s); intCheckBalance();137private：

boolCheckMatch(charSymb1,charSymb2,intLine1,intLine2);charGetNextSymbol();voidPutBackChar(charch);voidSkipComment(enumCommentTypetype);voidSkipQuote(chartype);charNextChar();};classnoFile{};138構(gòu)造函數(shù)balance::balance(constchar*s){fin.open(s);if(!fin)thrownoFile();currentLine=1;Errors=0;}139CheckBalance的實(shí)現(xiàn)檢查輸入流對(duì)象中的括號(hào)是否匹配，并返回錯(cuò)誤數(shù)算法的實(shí)現(xiàn)需要用到一個(gè)棧，我們可以用本章中實(shí)現(xiàn)的棧類，如seqStack。采用逐步精細(xì)化的方法分解這個(gè)函數(shù)140自頂向下的分解初始化棧為空；While(lastChar=讀文件，直到讀入一括號(hào))Switch(lastChar){case‘{‘,‘[‘,‘(‘：進(jìn)棧

case‘}’,’]’,’)’：

if(?？眨┹敵瞿承心撤?hào)不匹配；出錯(cuò)數(shù)加1;else{match=出棧的符號(hào)；檢查lastChar與match是否匹配；如不匹配，輸出出錯(cuò)信息，出錯(cuò)數(shù)加1；

}}if(棧非空)棧中元素均沒有找到匹配的閉符號(hào)，輸出這些錯(cuò)誤

return出錯(cuò)數(shù)141進(jìn)一步需要細(xì)化讀文件，直到讀入一括號(hào)；輸出某行某符號(hào)不匹配；出錯(cuò)數(shù)加1；檢查lastChar與match是否匹配。如不匹配，輸出出錯(cuò)信息，出錯(cuò)數(shù)加1；棧中元素均沒有找到匹配的閉符號(hào)，輸出這些錯(cuò)誤142進(jìn)一步抽取子函數(shù)第1項(xiàng)工作：GetNextSymbol功能：從文件的當(dāng)前位置開始，跳過所有的非括號(hào)，讀到第一個(gè)括號(hào)后返回。在遇到文件結(jié)束時(shí)，返回一個(gè)特定的符號(hào)，如NULL。函數(shù)原型：函數(shù)有一個(gè)字符型的返回值。執(zhí)行該函數(shù)必須有一個(gè)輸入流，在讀輸入流的過程中，當(dāng)前處理的行號(hào)會(huì)變，在讀的過程中也可能遇到異常情況，因此出錯(cuò)數(shù)也會(huì)變。這三個(gè)信息：文件流對(duì)象，當(dāng)前處理的行號(hào)，出錯(cuò)個(gè)數(shù)都是對(duì)象的數(shù)據(jù)成員。因此函數(shù)原型為：charGetNextSymbol（）。第3項(xiàng)工作：CheckMatch功能：比較兩個(gè)指定位置的待比較的符號(hào)是否匹配函數(shù)原型：boolbalance::CheckMatch(charSymb1,charSymb2,intLine1,intLine2)143CheckBalance的定義intbalance::CheckBalance(){structSymbolnode;seqStack<Symbol>st;charLastChar,Match;//LastChar為讀入的符號(hào)，Match為棧頂?shù)姆?hào)CheckBalance函數(shù)不需要參數(shù)。因?yàn)檩斎肓鲗?duì)象是類的數(shù)據(jù)成員。返回值是一個(gè)整型數(shù)，表示出錯(cuò)個(gè)數(shù)144while(LastChar=GetNextSymbol()){switch(LastChar){ case'(':case'[':case'{':node.Token=LastChar;node.TheLine=currentLine;st.push(node);break; case')':case']':case'}': if(st.isEmpty()){Errors++; cout<<"在第"<<currentLine<<"有一個(gè)多余的"<<LastChar<<endl; }else{node=st.pop();Match=node.Token; if(!CheckMatch(Match,LastChar,node.TheLine,currentLine))++Errors; } break;} }145while(!st.isEmpty()){ Errors++; node=st.pop(); cout<<"第"<<node.TheLine<<"行的符號(hào)"<<node.Token<<"不匹配\n"; }returnErrors;}146CheckMatchboolbalance::CheckMatch(charSymb1,charSymb2,intLine1,intLine2){if(Symb1=='('&&Symb2!=')'||Symb1=='['&&Symb2!=']'||Symb1=='{'&&Symb2!='}'){ cout<<"發(fā)現(xiàn)第"<<Line2<<"的符號(hào)"<<Symb2<<"與第"<<Line1<<"的符號(hào)"<<Symb1<<"不匹配\n"; returnfalse; }elsereturntrue;}147GetNextSymbol在讀文件時(shí)要跳過其它符號(hào)，提取出各類括號(hào)注釋中的括號(hào)不用考慮，字符串常量和字符常量中的括號(hào)也不用考慮。C++中的注釋又有兩種形式。一種是以“//”開始到本行結(jié)束。另一種是以“/*”開始到“*/”結(jié)束，可以跨行。不管是哪一種注釋，都要判斷兩個(gè)符號(hào)才能決定148GetNextSymbol的偽代碼CharGetNextSymbol(){while(ch=從文件中讀入下一字符){ if(Ch==‘/’){//可能是注釋的開始

if(ch=從文件中讀入下一字符) if(Ch==‘*’)跳過標(biāo)準(zhǔn)C的注釋;elseif(Ch==‘/’)跳過C++的注釋; else不是注釋，把ch放回輸入流; }elseif(Ch==‘\’’||Ch==‘”’)跳過字符常量或字符串常量;elseif(Ch==‘{’||Ch==’[’||Ch==‘(’||Ch==’)’||Ch==‘]’||Ch==’}’)returnCh;}return0;//文件結(jié)束。}149進(jìn)一步提取子函數(shù)從文件中讀入下一字符：

charNextChar();跳過的注釋：voidSkipComment(enumCommentTypetype);把ch放回輸入流：

voidPutBackChar(charch);跳過字符常量或字符串常量：

voidSkipQuote(chartype);150GetNextSymbol函數(shù)的實(shí)現(xiàn)charbalance::GetNextSymbol(){charch;while(ch=NextChar()){ if(ch=='/'){ ch=NextChar(); if(ch=='*')SkipComment(SlashStar);elseif(ch=='/')SkipComment(SlashSlash); elsePutBackChar(ch); } elseif(ch=='\''||ch=='"')SkipQuote(ch); elseif(ch=='{'||ch=='['||ch=='('||ch==')'||ch==']'||ch=='}')returnch; } returnNULL;//文件結(jié)束。}151NextChar函數(shù)的實(shí)現(xiàn)NextChar函數(shù)從輸入文件流中讀入一個(gè)字符，返回給調(diào)用程序，遇到文件結(jié)束符，返回NULL。如遇到換行符，則當(dāng)前處理行加1。charbalance::NextChar(){charch;if((ch=fin.get())==EOF)returnNULL;if(ch=='\n')currentLine++;returnch;}152PutBackChar函數(shù)的實(shí)現(xiàn)PutBackChar函數(shù)將傳入的字符放回輸入流，這是通過調(diào)用輸入流對(duì)象的成員函數(shù)putback實(shí)現(xiàn)的。如放回的字符是回車，當(dāng)前處理行號(hào)減1。voidbalance::PutBackChar(charch){fin.putback(ch);if(ch=='\n')currentLine--;}153SkipQuote函數(shù)的實(shí)現(xiàn)讀文件，直到讀到一個(gè)和參數(shù)值相同的符號(hào)。要注意幾個(gè)特殊情況：字符或字符串常量是不允許跨行的。也就是說，如果在讀文件的過程中遇到了回車，則表示字符或字符串常量的開始和結(jié)束符不匹配，輸出出錯(cuò)信息。在字符或字符串常量中可能會(huì)包含單引號(hào)或雙引號(hào)，此時(shí)不能將這個(gè)單引號(hào)或雙引號(hào)作為結(jié)束符。如何知道這個(gè)單引號(hào)或雙引號(hào)代表的是普通的字符而不是結(jié)束符呢？C++采用了轉(zhuǎn)義字符來表示，因此當(dāng)讀到一個(gè)表示轉(zhuǎn)義字符開始的標(biāo)記（\）時(shí)，不管它后面是什么符號(hào)，都不用檢查。