《数据结构：思想与方法》第二章线性表

1表的概念表的实现线性表类的实现STL中表的实现第二章线性表2表的概念线性表是N个具有相同特征的结点A0,A1,…,AN-1构成的集合。在这个集合中，除了A0

和AN-1

外，每个元素都有唯一的前趋和后继。对于每个Ai，它的前驱是Ai-1，它的后继是Ai+1。A0只有后继没有前驱，AN-1只有前驱没有后继。表的术语：N为表的大小A0称为首结点，AN-1称为尾结点空表：元素个数为零的表。位置：元素Ai在表中的位置为i3表的操作创建一个线性表create()：创建一个空的线性表;清除一个线性表clear()：删除线性表中的所有数据元素；求线性表的长度length()：返回线性表的长度;在第i个位置插入一个元素insert(i,x)：使线性表从（a0,a1,…ai-1,ai,…an-1）变成（a0,a1,…ai-1,x,ai,…an-1），参数i的合法取值范围是0到n；4删除第i个位置的元素remove（i）：使线性表从（a0,a1,…ai-1,ai,ai+1

…an-1）变成（a0,a1,…ai-1,ai+1,…an-1），参数i的合法取值范围是0到n-1;搜索某个元素在线性表中是否出现search(x)：在线性表中搜索x是否出现，并返回x的位置;访问线性表的第i个元素visit（i）：返回线性表中第i个数据元素的值;遍历线性表运算traverse()：按序访问线性表的每一数据元素。5线性表表的概念表的实现线性表类的实现STL中表的实现6表的实现线性表的顺序实现线性表的链接实现7线性表的顺序存储结构线性表中结点存放在存储器上一块连续的空间中。借助存储空间的连续性，结点可以按照其逻辑顺序依次存放。结点存放的物理位置和它的逻辑位置是一致的。

8线性表的顺序存储在程序设计语言中，一块连续的存储空间可以用一个数组实现。由于线性表中的元素个数是动态的，因此采用了动态数组。保存一个动态数组，需要三个变量：指向线性表元素类型的指针，数组规模（容量），数组中的元素个数（表长）。anan-1…a2a1a0maxSizelengthdata9线性表的运算实现length()：只需要返回length的值visit（i）：返回data[i]的值traverse()：输出数组data的前length个元素clear()：只要将length置为0即可create(maxSize)：申请一个maxSize大小的动态数组10search运算的实现intsearch(x){num=0;for(num=0;num<length;++num)if(data[num]==x)break;if(num==length)num=-1;returnnum;}11insert(i,x)运算的实现length在插入时，表长会增加。当表长等于容量时，新增加的元素将无法存储。此时有两种解决方法：一种是不执行插入，报告一个错误消息；另一种是扩大数组的容量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操作的实现resize操作按一定的比例扩大数组的空间，常用的比例是扩大一倍。数组空间在内存中必须是连续的，因此，扩大数组空间的操作必须重新申请一个更大规模的动态数组，将原有数组的内容拷贝到新数组中，释放原有数组空间，将新数组作为存储线性表的存储区。14a0a1…an-1andatatmp15remove（i）运算的实现an…ai+1ai…a1a0voidremove(i){for(j=i;j<length-1;++j)data[j]=data[j+1];--length;}16顺序实现的算法分析length,visit和clear的实现与表中的元素个数无关，因此它们的时间复杂度是O（1）。traverse()操作遍历整个表中的所有元素，因此时间复杂度为O(n)。create操作需要申请一块动态数组的空间，并设表为空。因此也是O(1)的时间复杂度。插入操作，需要移动结点。当i等于n时，移动次数为0。当i等于0时，移动次数为n。最好情况下的时间复杂度为O(1)最坏情况下的时间复杂度为O(n)平均的时间复杂度：如果在每个位置上的插入都是等概率的，则插入算法的平均时间复杂度为n/217线性表的顺序实现总结由于要保持逻辑次序和物理次序的一致性，顺序表在插入删除时需要移动大量的数据，性能不太理想。由于逻辑次序和物理次序的一致性使得定位访问的性能很好。顺序表比较适合静态的、经常作定位访问的线性表。18表的实现线性表的顺序实现线性表的链接实现19线性表的链接存储结构将每个结点放在一个独立的存储单元中，结点间的逻辑关系依靠存储单元中附加的指针来给出。结点的存储单元在物理位置上可以相邻，也可以不相邻。20线性表的链接存储单链表双链表循环链表21单链表每个结点附加了一个指针字段，如next，该指针指向它的直接后继结点，最后一个结点的next字段为空。nilhead22insertai+1aixp23头结点、头指针、尾结点、尾指针为了消除特殊情况，通常在表头额外增加一个相同类型的特殊结点，称之为头结点，在表尾也增加一个额外结点，称为尾结点。它们不是线性表中的组成部分。头尾结点的出现，使得在表头和表尾位置上进行插入和删除和在其它结点位置上是完全一致的，从而使得插入和删除算法得到简化。24带头结点的单链表a0a1an-1…∧head25Create函数的实现申请一块存储结点的空间，设结点的指针部分为空指针。将结点地址存入代表单链表的变量head。∧head26清除一个线性表clear()把所有结点的空间还给系统，把头结点的指针部分置为空指针voidclear(){P=头结点的直接后继；

While(p!=空指针){q=p;p=p的直接后继地址；释放q的空间；}

头结点的后继指针置为空指针；}27求表的长度length()方法1：从起始结点开始，沿着后继指针链一个一个往后数，数到一个结点，长度加1intlength(){len=0;p=头结点的直接后继；

While(p!=空指针){++len;p=p的直接后继的地址；}}方法2：用空间换取时间的方法。在保存单链表的时候增加一个变量，保存表的长度

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

tmp=new结点；

tmp指向的结点的数据部分=x；

tmp指向的结点的指针部分=p的直接后继的地址；

p指向的结点的指针部分=tmp；}29删除第i个位置的元素remove（i）voidremove(i){for(j=0,p=head;j<i;++j)p=p的直接后继的地址；

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

p的指针部分=tmp的直接后继的地址；

freetmp；}30搜索某个元素在线性表中是否出现search(x)intsearch(x){num=0;p=头结点的直接后继；

While(p!=空指针&&p的数据部分！=x){++num;p=p的直接后继的地址；}if（p==空指针）num=-1；

returnnum;}31访问线性表的第i个元素visit（i）dataTypevisit(i){for(j=0,p=head;j<i;++j)p=p的直接后继的地址；

returnp指向的结点的数据部分；}32遍历运算traverse()voidtraverse(){p=头结点的直接后继；

While(p!=空指针){cout<<p指向结点的数据部分；

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

}}33线性表的链接存储单链表双链表循环链表34双链表每个结点附加了两个指针字段，如prior和next，其中prior字段给出直接前驱结点的地址，next给出直接后继结点的地址。头结点中prior字段为空，它的next字段给出线性表中的首结点的地址，尾结点中next字段为空，这种形式的链表称为双链表。headtail∧∧35Create运算创建一个双链表就是创建一个只有头尾结点的链表，把头结点的地址保存在head中，尾结点的地址保存在tail中head∧tail∧36insertxp37removexp38线性表的链接存储单链表双链表循环链表39单循环链表一般单循环链表不带头结点head40双循环链表头结点中prior字段给出尾结点的地址，尾结点中next字段给出头结点的地址一般也不设头尾结点41线性表表的概念表的实现线性表类的实现STL中表的实现42线性表类的实现线性表抽象类顺序表类双链表类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线性表的抽象类线性表的抽象类是一个类模板抽象类不包括create函数。这个运算由每个线性表类的构造函数完成增加了一个析构函数，以防内存泄漏45线性表类的实现线性表抽象类顺序表类双链表类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构造函数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其他函数自己实现53线性表类的实现线性表抽象类顺序表类双链表类54链表类的设计以双链表为例链表类的数据成员：头指针、尾指针，以及为了提高时间性能而设置的数据成员currentLength链表类必须实现线性表的所有操作。为保证这一点，链表类从线性表的抽象类继承。链表的插入、删除操作都需要将指针移到被操作结点的前一结点。特设计函数move实现55结点及其组成链表中的结点包含三部分：数据字段、前趋指针和后继指针字段。数据字段可以是任何类型的数据，这里仍然用ElemType表示；指针字段用于存放其他相关结点的地址值。由于结点类型是链表专用的，因此可设为内嵌类。由于链表的操作是通过对结点的操作实现的，于是把结点类定义成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构造函数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缺点双链表类仅实现了线性表的基本运算，并没有用到双链表的特点，如逆向查找等67线性表表的概念表的实现线性表类的实现STL中表的实现68STLSTL（标准模版库）是C++中数据结构的实现。这些数据结构被称为集合或容器。STL中线性表的实现有两种：Vector：线性表的顺序实现List：线性表的双链表的实现69Vector和list共同支持的操作所有的容器都支持的整体操作：求规模、清空和判空在表尾的插入和删除以及取表头表尾元素List特有的操作：表头的插入和删除Vector特有的操作：[]的重载，按下标取元素，求容量，重新设置数组的大小。迭代器：两者都能用迭代器访问70STL中的迭代器操作获取一个迭代器：Begin：返回一个指向第一个节点的迭代器End：返回一个指向最后一个节点的迭代器迭代器本身的方法：向后移动，取迭代器指向的元素值，判迭代器相等和不相等需要迭代器的容器操作：在指定位置上插入一元素删除指定位置的元素删除指定位置之间的所有元素71STL中线性表的实现Vector：线性表的顺序实现，且大小可增长List：线性表的双链表实现72Vector的特性Vector维护一个C的原始数组、容量及大小规模提供拷贝构造函数和赋值运算符的重载函数，实现了对数组的整体操作可以修改数组的容量提供[]运算符重载提供了一个内嵌的迭代器头文件：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);//重新设置表的大小voidreserve(intnewCapacity);//重新设置数组的容量

//[]重载object&operator[](intindex);constobject&operator[](intindex)const;不允许隐式转换75boolempty()const;intsize()const;intcapacity()const;//对数据元素的操作

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

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

constobject&back()const;//返回表尾元素的值76//迭代器操作typedefobject*iterator;typedefconstobject*const_iterator;iteratorbegin();//返回元素0的地址const_iteratorbegin()const;//返回元素0的地址iteratorend();//指向最后一个元素的地址const_iteratorend()const;//指向最后一个元素的地址};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执行结果theinitialsizeofvis:0theinitialcapacityofvis:0Afterpush2,capacityofvis:1Afterpush3,capacityofvis:2Afterpush4,capacityofvis:4thesizeofvis:3thecapacityofvis:4contentsofvusing[]:234contentsofvusingiteratornotation:23481STL中表的实现Vector：线性表的顺序实现，且大小可增长List：线性表的双链表实现STL（标准模版库）是C++中数据结构的实现。82List的实现采用了带头节点的双链表实现ΛΛ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的应用#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第三章栈栈的概念栈的顺序实现栈的链接实现栈类的实现STL中的栈栈的应用91栈后进先出(LIFO,LastInFirstOut)或先进后出(FILO,FirstInLastOut)结构，最先(晚)到达栈的结点将最晚(先)被删除。

乒乓球进盒、出盒92相关概念an-1an-2…a1a0…出栈进栈栈底栈顶93相关概念栈底(bottom)：结构的首部(结点最早到达的部分)栈顶（top）：结构的尾部(结点最晚到达的部分)出栈（Pop）：结点从栈顶删除进栈（Push）：结点在栈顶位置插入空栈：栈中结点个数为零时94栈的运算创建一个栈create()：创建一个空的栈；进栈push(x)：将x插入栈中，使之成为栈顶元素；出栈pop()：删除栈顶元素并返回栈顶元素值；读栈顶元素top()：返回栈顶元素值但不删除栈顶元素；判栈空isEmpty()：若栈为空，返回true，否则返回false。95栈栈的概念栈的顺序实现栈的链接实现栈类的实现STL中的栈栈的应用96栈的顺序实现用连续的空间存储栈中的结点，即数组进栈和出栈总是在栈顶一端进行，不会引起类似顺序表中的大量数据的移动。用数组的后端表示栈顶。an…a1a0top_p栈底maxSizeelem97顺序存储时的运算实现create()：按照用户估计的栈的规模申请一个动态数组，将数组地址保存在data中，数组规模保存在maxSize中，并设top_p的值为-1。push(x)：将top_p加1，将x放入top_p指出的位置中。但要注意数组满的情况。pop()：返回top_p指出的位置中的值并将top_p减1。top()：与pop类似，只是不需要将top_p减1。isEmpty()：若top_p的值为-1，返回true，否则返回false。98顺序实现性能分析除了进栈操作以外，所有运算实现的时间复杂度都是O（1）。进栈运算在最坏情况下的时间复杂度是O（N）。但最坏情况在N次进栈操作中至多出现一次。如果把扩展数组规模所需的时间均摊到每个插入操作，每个插入只多了一个拷贝操作，因此从平均的意义上讲，插入运算还是常量的时间复杂度。这种分析方法称为均摊分析法。99栈栈的概念栈的顺序实现栈的链接实现栈类的实现STL中的栈栈的应用100栈的链接实现栈的操作都是在栈顶进行的，不需要找某一元素的直接前驱的操作，因此不需要双链表，用单链表就足够了，而且不需要头结点对栈来讲，只需要考虑栈顶元素的插入删除。从栈的基本运算的实现方便性考虑，可将单链表的头指针指向栈顶。101栈的链接实现an-1an-2a0…∧top_p102链接存储时的运算实现create()：将top_p设为空指针。push(x)：将x插入到单链表的表头voidpush(x){p=new结点；

p指向的结点的数据部分=x；

p指向的结点的指针部分=top_p；

top_p=p;}103链接存储时的运算实现pop()：删除表头元素dataTypepop(){p=top_p;top_p=top_p指向的结点的指针部分；

x=p指向的结点的数据部分；

deletep;returnx;}104链接存储时的运算实现top()：返回top_p指向的结点的值。isEmpty()：若top_p的值为空指针，返回true，否则返回false。105链接栈的性能分析由于所有的操作都是对栈顶的操作，邮展中的元素个数无关。所以，所有运算的时间复杂度都是O（1）106栈栈的概念栈的顺序实现栈的链接实现栈类的实现STL中的栈栈的应用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析构函数template<classelemType>linkStack<elemType>::~linkStack(){ node*tmp; while(elem!=NULL){ tmp=elem; elem=elem->next; deletetmp; }}115栈栈的概念栈的顺序实现栈的链接实现栈类的实现STL中的栈栈的应用116STL中的栈栈本质上是一个线性表，在STL中栈类是借助于线性表类实现的。STL中的栈提供四个标准运算：push、pop、top和empty。在STL中，借助于其他容器存储数据的容器称为容器适配器。栈就是一个容器适配器117栈的类模板定义一个栈对象要指明栈中元素的类型以及借助于哪一个容器，因此栈的类模板有两个模板参数：栈元素类型和所借助的容器类型。栈可以借助的容器有vector,list和deque。栈的类模板的第二个参数带有缺省值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栈栈的概念栈的顺序实现栈的链接实现栈类的实现STL中的栈栈的应用120栈的应用递归函数的非递归实现符号平衡检查表达式的计算121栈的应用—递归函数的非递归实现递归的本质是函数调用，而函数调用是通过栈实现的。因此，递归可以用栈消除。voidf1(){…r1:f2();r2:…}voidf2(){…t1:f3();t2:…}voidf3(){……}122函数执行过程f1f2f3r1t1r2t2123函数调用的实现设置一个栈模拟函数调用。当发生函数调用时，将当前的函数的现场进栈。调用f2前Top调用f2后Topr2调用f3后Topr2t2返回f2后Topr2返回f1后Top124递归递归是一种特殊的函数调用，是在一个函数中又调用了函数本身。递归程序的本质是函数调用，而函数调用是要花费额外的时间和空间。在系统内部，函数调用是用栈来实现，如果程序员可以自己控制这个栈，就可以消除递归调用。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快速排序的非递归实现设置一个栈，记录要做的工作，即要排序的数据段先将整个数组进栈当排序区间被分成两半时，把一半进栈，先排序另一半。排完后再去检查栈是否为空，为空，则排序结束，否则从栈中弹出一个区间，排序该区间。栈元素的格式：

structnode{intleft;intright;};12794183650941836startfinish5240986134mid20startfinish986134finishstart986134986431mid10128voidquicksort(inta[],intsize){seqStack<node>st;intmid,start,finish;nodes;if(size<=1)return;//排序整个数组

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栈的应用递归函数的非递归实现符号平衡检查表达式的计算131括号配对检查编译程序的任务之一，就是检查括号是否配对。如：括号(、[和{后面必须依次跟随相应的}、]及)，“后面必须有”。简单地用开括号和闭括号的数量是否相等来判断开括号与闭括号是否配对是不行的。例如，符号串[（）]是正确的，而符号串（[）]是不正确的。因为当遇到）那样的闭括号时，它与最近遇到开括号匹配。132使用栈解决符号配对使用栈，遇到左括号进栈，见到右括号，则出栈，并比较两者是否配对。如判断（3+（5-2）*（6+4）/2），（3+（（5-2）*（6+4）/2）

“abc”，‘n’

（a[3]+a[4]–‘a’）133算法首先创建一个空栈。从源程序中读入符号。如果读入的符号是开符号，那末就将其进栈。如果读入的符号是一个闭符号但栈是空的，出错。否则，将栈中的符号出栈。如果出栈的符号和和读入的闭符号不匹配，出错。继续从文件中读入下一个符号，非空则转向3，否则执行7。如果栈非空，报告出错，否则括号配对成功。134细节问题如果对C++的源程序使用此算法，需要考虑三种括号：圆括号、方括号和花括号。但有时又不需要考虑圆括号、花括号、方括号是否匹配的问题。例如，当括号出现在注释、字符串常量、字符常量中时，就不需要考虑它的匹配问题。在C++中有很多转义字符，因此在读入一个字符时，还必须考虑如何识别转义字符。135要求设计一个类Balance：对象初始化时传给它一个源文件名。这个类提供一个成员函数checkBalance检查源文件中的符号是否配对。输出所有不匹配的符号及所在的行号136类的定义classbalance{private: ifstreamfin;//待检查的文件流

intcurrentLine;//正在处理行的的行号

intErrors;//已发现的错误数

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构造函数balance::balance(constchar*s){fin.open(s);if(!fin)thrownoFile();currentLine=1;Errors=0;}139CheckBalance的实现检查输入流对象中的括号是否匹配，并返回错误数算法的实现需要用到一个栈，我们可以用本章中实现的栈类，如seqStack。采用逐步精细化的方法分解这个函数140自顶向下的分解初始化栈为空；While(lastChar=读文件，直到读入一括号)Switch(lastChar){case‘{‘,‘[‘,‘(‘：进栈

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

if(栈空）输出某行某符号不匹配；出错数加1;else{match=出栈的符号；检查lastChar与match是否匹配；如不匹配，输出出错信息，出错数加1；

}}if(栈非空)栈中元素均没有找到匹配的闭符号，输出这些错误

return出错数141进一步需要细化读文件，直到读入一括号；输出某行某符号不匹配；出错数加1；检查lastChar与match是否匹配。如不匹配，输出出错信息，出错数加1；栈中元素均没有找到匹配的闭符号，输出这些错误142进一步抽取子函数第1项工作：GetNextSymbol功能：从文件的当前位置开始，跳过所有的非括号，读到第一个括号后返回。在遇到文件结束时，返回一个特定的符号，如NULL。函数原型：函数有一个字符型的返回值。执行该函数必须有一个输入流，在读输入流的过程中，当前处理的行号会变，在读的过程中也可能遇到异常情况，因此出错数也会变。这三个信息：文件流对象，当前处理的行号，出错个数都是对象的数据成员。因此函数原型为：charGetNextSymbol（）。第3项工作：CheckMatch功能：比较两个指定位置的待比较的符号是否匹配函数原型：boolbalance::CheckMatch(charSymb1,charSymb2,intLine1,intLine2)143CheckBalance的定义intbalance::CheckBalance(){structSymbolnode;seqStack<Symbol>st;charLastChar,Match;//LastChar为读入的符号，Match为栈顶的符号CheckBalance函数不需要参数。因为输入流对象是类的数据成员。返回值是一个整型数，表示出错个数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<<"有一个多余的"<<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<<"行的符号"<<node.Token<<"不匹配\n"; }returnErrors;}146CheckMatchboolbalance::CheckMatch(charSymb1,charSymb2,intLine1,intLine2){if(Symb1=='('&&Symb2!=')'||Symb1=='['&&Symb2!=']'||Symb1=='{'&&Symb2!='}'){ cout<<"发现第"<<Line2<<"的符号"<<Symb2<<"与第"<<Line1<<"的符号"<<Symb1<<"不匹配\n"; returnfalse; }elsereturntrue;}147GetNextSymbol在读文件时要跳过其它符号，提取出各类括号注释中的括号不用考虑，字符串常量和字符常量中的括号也不用考虑。C++中的注释又有两种形式。一种是以“//”开始到本行结束。另一种是以“/*”开始到“*/”结束，可以跨行。不管是哪一种注释，都要判断两个符号才能决定148GetNextSymbol的伪代码CharGetNextSymbol(){while(ch=从文件中读入下一字符){ if(Ch==‘/’){//可能是注释的开始

if(ch=从文件中读入下一字符) if(Ch==‘*’)跳过标准C的注释;elseif(Ch==‘/’)跳过C++的注释; else不是注释，把ch放回输入流; }elseif(Ch==‘\’’||Ch==‘”’)跳过字符常量或字符串常量;elseif(Ch==‘{’||Ch==’[’||Ch==‘(’||Ch==’)’||Ch==‘]’||Ch==’}’)returnCh;}return0;//文件结束。}149进一步提取子函数从文件中读入下一字符：

charNextChar();跳过的注释：voidSkipComment(enumCommentTypetype);把ch放回输入流：

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

voidSkipQuote(chartype);150GetNextSymbol函数的实现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;//文件结束。}151NextChar函数的实现NextChar函数从输入文件流中读入一个字符，返回给调用程序，遇到文件结束符，返回NULL。如遇到换行符，则当前处理行加1。charbalance::NextChar(){charch;if((ch=fin.get())==EOF)returnNULL;if(ch=='\n')currentLine++;returnch;}152PutBackChar函数的实现PutBackChar函数将传入的字符放回输入流，这是通过调用输入流对象的成员函数putback实现的。如放回的字符是回车，当前处理行号减1。voidbalance::PutBackChar(charch){fin.putback(ch);if(ch=='\n')currentLine--;}153SkipQuote函数的实现读文件，直到读到一个和参数值相同的符号。要注意几个特殊情况：字符或字符串常量是不允许跨行的。也就是说，如果在读文件的过程中遇到了回车，则表示字符或字符串常量的开始和结束符不匹配，输出出错信息。在字符或字符串常量中可能会包含单引号或双引号，此时不能将这个单引号或双引号作为结束符。如何知道这个单引号或双引号代表的是普通的字符而不是结束符呢？C++采用了转义字符来表示，因此当读到一个表示转义字符开始的标记（\）时，不管它后面是什么符号，都不用检查。