数据结构-第一部分.ppt

《数据结构-第一部分.ppt》由会员分享，可在线阅读，更多相关《数据结构-第一部分.ppt（272页珍藏版）》请在三一办公上搜索。

1、1,第一部分 线性表,具有线性关系的数据集合的处理包括三部分内容线性表栈队列,2,第二章 线性表,线性表的概念线性表的实现线性表类的实现STL中线性表的实现,3,线性表的概念,线性表是N个具有相同特征的结点A0,A1,AN-1构成的集合。在这个集合中，除了A0 和AN-1 外，每个元素都有唯一的前趋和后继。对于每个Ai，它的前驱是Ai-1，它的后继是Ai+1。A0只有后继没有前驱，AN-1只有前驱没有后继。表的术语：N为表的大小A0称为首结点，AN-1称为尾结点空表：元素个数为零的表。位置：元素Ai在表中的位置为i,4,表的基本操作,创建一个线性表create()：创建一个空的线性表;清除一个

2、线性表clear()：删除线性表中的所有数据元素；求线性表的长度length()：返回线性表的长度;在第i个位置插入一个元素insert(i,x)：使线性表从（a0,a1,ai-1,ai,an-1）变成（a0,a1,ai-1,x,ai,an-1），参数i的合法取值范围是0到n；,5,删除第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）：

3、返回线性表中第i个数据元素的值;遍历线性表运算traverse()：按序访问线性表的每一数据元素。,6,第二章 线性表,线性表的概念线性表的实现线性表类的实现STL中线性表的实现,7,线性表的实现,线性表的顺序实现线性表的链接实现,8,线性表的顺序存储结构,线性表中结点存放在存储器上一块连续的空间中。借助存储空间的连续性，结点可以按照其逻辑顺序依次存放。结点存放的物理位置和它的逻辑位置是一致的。线性表的顺序实现通常称为顺序表。,9,线性表的顺序存储,在程序设计语言中，一块连续的存储空间可以用一个数组实现。由于线性表中的元素个数是动态的，因此采用了动态数组。保存一个动态数组，需要两个变量：指向线

4、性表元素类型的指针，数组规模（容量），数组中的元素个数（表长）。线性表必须支持插入或删除，在申请空间时要留有余地。一般要比实际元素个数多一点。,10,顺序表的运算实现,length()：只需要返回length的值visit（i）：返回datai的值traverse()：输出数组data的前length个元素clear()：只要将length置为0即可create(maxSize)：申请一个maxSize大小的动态数组,11,search 运算的实现,int search(x)for(num=0;num length;+num)if(datanum=x)break;if(num=length)n

5、um=-1;return num;,12,insert(i,x)运算的实现,在插入时，表长会增加。当表长等于容量时，新增加的元素将无法存储。此时有两种解决方法：一种是不执行插入，报告一个错误消息；另一种是扩大数组的容量,13,void insert(i,x)if(length=maxSize)resize();for(j=n-1;j=i;-j)dataj+1=dataj;datai=x;+length;,14,resize 操作的实现,resize操作按一定的比例扩大数组的空间，常用的比例是扩大一倍。数组空间在内存中必须是连续的，因此，扩大数组空间的操作必须重新申请一个更大规模的动态数组，将原

6、有数组的内容拷贝到新数组中，释放原有数组空间，将新数组作为存储线性表的存储区。,15,data,tmp,16,remove（i）运算的实现,void remove(i)for(j=i;j length-1;+j)dataj=dataj+1;-length;,17,顺序实现的算法分析,length,visit和clear的实现与表中的元素个数无关，因此它们的时间复杂度是O（1）。traverse()操作遍历整个表中的所有元素，因此时间复杂度为O(n)。create操作需要申请一块动态数组的空间，并设表为空。因此也是O(1)的时间复杂度。插入操作，需要移动结点。当i等于n时，移动次数为0。当i等于

7、0时，移动次数为n。最好情况下的时间复杂度为O(1)最坏情况下的时间复杂度为O(n)平均的时间复杂度：如果在每个位置上的插入都是等概率的，则插入算法的平均时间复杂度为n/2,18,线性表的顺序实现总结,由于要保持逻辑次序和物理次序的一致性，顺序表在插入删除时需要移动大量的数据，性能不太理想。由于逻辑次序和物理次序的一致性使得定位访问的性能很好。顺序表比较适合静态的、经常做定位访问的线性表。,19,表的实现,线性表的顺序实现线性表的链接实现,20,线性表的链接存储结构,将每个结点放在一个独立的存储单元中，结点间的逻辑关系依靠存储单元中附加的值针来给出。结点的存储单元在物理位置上可以相邻，也可以不

8、相邻。,21,线性表的链接存储,单链表双链表循环链表,22,单链表,每个结点附加了一个指针字段，如next，该指针指向它的直接后继结点，最后一个结点的next字段为空。,23,insert,p,24,头结点、头指针,为了消除特殊情况，通常在表头额外增加一个相同类型的特殊结点，称之为头结点。它们不是线性表中的组成部分。头结点的出现，使得在表头位置上进行插入和删除和在其它结点位置上是完全一致的，从而使得插入和删除算法得到简化。,25,带头结点的单链表,a0,a1,an-1,26,Create函数的实现,申请一块存储结点的空间，设结点的指针部分为空指针。将结点地址存入代表单链表的变量head。,27

9、,清除一个线性表clear(),把所有结点的空间还给系统，把头结点的指针部分置为空指针,void clear()p=头结点的直接后继；While(p!=空指针)q=p;p=p的直接后继地址；释放q的空间；头结点的后继指针置为空指针；,28,求表的长度length(),方法1：从起始结点开始，沿着后继指针链一个一个往后数，数到一个结点，长度加1,int length()len=0;p=头结点的直接后继；While(p!=空指针)+len;p=p的直接后继的地址；,方法2：用空间换取时间的方法。在保存单链表的时候增加一个变量，保存表的长度,29,在第i个位置插入一个元素insert(i,x),vo

10、id insert(i,x)for(j=0,p=head;j i;+j)p=p的直接后继的地址；tmp=new 结点；tmp指向的结点的数据部分=x；tmp指向的结点的指针部分=p的直接后继的地址；p指向的结点的指针部分=tmp；,30,删除第i个位置的元素remove（i）,void remove(i)for(j=0,p=head;j i;+j)p=p的直接后继的地址；tmp=p的直接后继的地址；p的指针部分=tmp的直接后继的地址；delete tmp；,31,搜索某个元素在线性表中是否出现,int search(x)num=0;p=头结点的直接后继；while(p!=空指针,32,访问线

11、性表的第i个元素visit（i）,dataType visit(i)for(j=0,p=head;j i;+j)p=p的直接后继的地址；return p指向的结点的数据部分；,33,遍历运算traverse(),void traverse()p=头结点的直接后继；While(p!=空指针)cout p指向结点的数据部分；p=p的直接后继的地址；,34,线性表的链接存储,单链表双链表循环链表,35,双链表,每个结点附加了两个指针字段，如prior和nextprior字段给出直接前驱结点的地址next给出直接后继结点的地址。,36,双链表的头尾节点,为了消除在表头、表尾插入删除的特殊情况，通常双链

12、表设一头结点，设一尾节点头结点中prior字段为空，它的next字段给出线性表中的首结点的地址尾结点中next字段为空，它的prior字段给出线性表中最后一个节点的地址,37,create运算,创建一个双链表就是创建一个只有头尾结点的链表，把头结点的地址保存在head中，尾结点的地址保存在tail中,38,insert,p,39,remove,x,p,40,线性表的链接存储,单链表双链表循环链表,41,单循环链表,一般单循环链表不带头结点,42,双循环链表,头结点中prior字段给出尾结点的地址，尾结点中next字段给出头结点的地址 一般也不设头尾结点,43,第二章 线性表,线性表的概念线性表

13、的实现线性表类的实现STL中线性表的实现,44,线性表类的实现,线性表抽象类顺序表类双链表类,45,线性表的抽象类,线性表的抽象类是一个类模板抽象类包括了除create运算以外的所有运算。create运算由每个线性表类的构造函数完成增加了一个虚析构函数，以防内存泄漏,46,线性表的抽象类,template class list public:virtual void clear()=0;virtual int length()const=0;virtual void insert(int i,const elemType,47,线性表类的实现,线性表抽象类顺序表类双链表类,48,顺序表类的定义

14、,class OutOfBound;class IllegalSize;template class seqList:public list private:elemType*data;int currentLength;int maxSize;void doubleSpace();,49,public:seqList(int initSize=10);seqList()delete data;void clear()currentLength=0;int length()const return currentLength;void insert(int i,const elemType,5

15、0,构造函数,template seqList:seqList(int initSize)if(initSize=0)throw IllegalSize();data=new elemTypeinitSize;maxSize=initSize;currentLength=0;,51,insert,template void seqList:insert(int i,const elemType,52,remove,template void seqList:remove(int i)if(i currentLength-1)throw OutOfBound();for(int j=i;j cu

16、rrentLength-1;j+)dataj=dataj+1;-currentLength;,53,doubleSpace,template void seqList:doubleSpace()elemType*tmp=data;maxSize*=2;data=new elemTypemaxSize;for(int i=0;i currentLength;+i)datai=tmpi;delete tmp;,54,其他函数,自己实现,55,线性表类的实现,线性表抽象类顺序表类双链表类,56,链表类的设计,以双链表为例链表类的数据成员：头指针、尾指针，以及为了提高时间性能而设置的数据成员curre

17、ntLength链表类必须实现线性表的所有操作。为保证这一点，链表类从线性表的抽象类继承。链表的插入、删除操作都需要将指针移到被操作结点。特设计函数move实现,57,结点及其组成,链表中的结点包含三部分：数据字段、前趋指针和后继指针字段。数据字段可以是任何类型的数据，这里仍然用ElemType表示；指针字段用于存放其他相关结点的地址值。由于结点类型是链表专用的，因此可设为内嵌类。由于链表的操作是通过对结点的操作实现的，于是把结点类定义成struct，以方便链表类访问。,58,双链表类的定义,template class linkList:public list private:struct

18、node elemType data;node*prev,*next;node(const elemType,59,public:linkList();linkList()clear();delete head;delete tail;void clear();int length()const return currentLength;void insert(int i,const elemType,60,构造函数,template linkList:linkList()head=new node;head-next=tail=new node;tail-prev=head;currentL

19、ength=0;,61,clear,template void linkList:clear()node*p=head-next,*q;head-next=tail;tail-prev=head;while(p!=tail)q=p-next;delete p;p=q;currentLength=0;,62,move,template linkList:node*linkList:move(int i)const node*p=head-next;if(i currentLength)throw OutOfBound();while(i-)p=p-next;return p;,63,templa

20、te void linkList:insert(int i,const elemType,insert,pos,64,remove,template void linkList:remove(int i)node*pos;pos=move(i);pos-prev-next=pos-next;pos-next-prev=pos-prev;delete pos;-currentLength;,65,search,template int linkList:search(const elemType,66,visit,template elemType linkList:visit(int i)co

21、nst node*p=move(i);return p-data;,67,traverse,template void linkList:traverse()constnode*p=head-next;cout data next;cout endl;,68,缺点,双链表类仅实现了线性表的基本运算，并没有用到双链表的特点，如逆向查找等,69,第二章 线性表,表的概念表的实现线性表类的实现STL中表的实现,70,STL,STL（标准模版库）是C+中数据结构的实现。这些数据结构被称为集合或容器。STL中线性表的实现有两种：vector：线性表的顺序实现list：线性表的双链表的实现,71,vect

22、or和list,共同支持的操作所有的容器都支持的整体操作：求规模、清空和判空在表尾的插入和删除以及取表头表尾元素list特有的操作：表头的插入和删除vector特有的操作：的重载，按下标取元素，求容量，重新设置数组的大小。迭代器：两者都能用迭代器访问,72,STL中的迭代器操作,获取一个迭代器：begin：返回一个指向第一个节点的迭代器end：返回一个指向最后一个节点的迭代器迭代器本身的方法：向后移动，取迭代器指向的元素值，判迭代器相等和不相等需要迭代器的容器操作：在指定位置上插入一元素删除指定位置的元素删除指定位置之间的所有元素,73,STL中线性表的实现,vector：线性表的顺序实现，且

23、大小可增长list：线性表的双链表实现,74,vector的特性,vector维护一个C+的原始数组、容量及大小规模提供拷贝构造函数和赋值运算符的重载函数，实现了对数组的整体操作可以修改数组的容量提供运算符重载提供了一个内嵌的迭代器头文件：vector,75,vector的定义,template class vector private:int theSize;int theCapacity;object*objects;public:enum SPARE_CAPACITY=16;,76,explicit vector(int initSize=0);vector(const Vector,不

24、允许隐式转换,77,bool empty()const;int size()const;int capacity()const;/对数据元素的操作 void push_back(const object/返回表尾元素的值,78,/迭代器操作typedef object*iterator;typedef const object*const_iterator;iterator begin();/返回元素0的地址const_iterator begin()const;/返回元素0的地址iterator end();/指向最后一个元素的地址const_iterator end()const;/指向最

25、后一个元素的地址;,79,vector的使用,#include#include using namespace std;int main()vector v;cout the initial size of v is:v.size()n the initial capacity of v is:v.capacity()endl;,80,v.push_back(2);cout n after push 2,capacity of v is:v.capacity()endl;v.push_back(3);cout n after pust 3,capacity of v is:“v.capacit

26、y()endl;v.push_back(4);cout n after push 4,capacity of v is:“v.capacity()endl;coutn the size of v is:v.size()n the capacity of v is:“v.capacity()endl;,81,cout:const_iterator p;for(p=v.begin();p!=v.end();p+)cout*p;cout endl;,82,执行结果,the initial size of v is:0the initial capacity of v is:0After push 2

27、,capacity of v is:1After push 3,capacity of v is:2After push 4,capacity of v is:4the size of v is:3the capacity of v is:4contents of v using:2 3 4contents of v using iterator notation:2 3 4,83,STL中表的实现,vector：线性表的顺序实现，且大小可增长list：线性表的双链表实现,STL（标准模版库）是C+中数据结构的实现。,84,list的实现,采用了带头节点的双链表实现,85,list的功能,允许

28、在任何位置插入和删除支持双向迭代器头文件：list,86,list的定义,template class list private:struct node.;int the size;node*head,*tail;void init();,87,public:class const_iterator class iterator:public const_iterator list();list(const list,88,/迭代器操作iterator begin();const_iterator begin()const;iterator end();const_iterator end()

29、const;iterator insert(iterator itr,const Object&x)；iterator erase(iterator itr)；iterator erase(iterator start,iterator end)；,89,int size()const;bool empty()const;void clear();object,90,list的应用,#include#include using namespace std;template void printall(const list,contents of values is:2 1 4 3,conten

30、ts of values is:5 2 6 1 7 4 8 3,91,template void printall(const list,92,作业,93,第三章 栈,栈的概念栈的顺序实现栈的链接实现栈类的实现STL中的栈栈的应用,94,栈,后进先出(LIFO,Last In First Out)或先进后出(FILO,First In Last Out)结构，最先(晚)到达栈的结点将最晚(先)被删除。,乒乓球进盒、出盒,95,相关概念,96,相关概念,栈底(bottom)：结构的首部(结点最早到达的部分)栈顶（top）：结构的尾部(结点最晚到达的部分)出栈（Pop）：结点从栈顶删除 进栈（Pu

31、sh）：结点在栈顶位置插入 空栈：栈中结点个数为零时,97,栈的运算,创建一个栈create()：创建一个空的栈；进栈push(x)：将x插入栈中，使之成为栈顶元素；出栈pop()：删除栈顶元素并返回栈顶元素值；读栈顶元素top()：返回栈顶元素值但不删除栈顶元素；判栈空isEmpty()：若栈为空，返回true，否则返回false。,98,第三章 栈,栈的概念栈的顺序实现栈的链接实现栈类的实现STL中的栈栈的应用,99,栈的顺序实现,用连续的空间存储栈中的结点，即数组进栈和出栈总是在栈顶一端进行，不会引起类似顺序表中的大量数据的移动。用数组的后端表示栈顶。,100,顺序存储时的运算实现,cr

32、eate()：按照用户估计的栈的规模申请一个动态数组，将数组地址保存在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。,101,顺序实现性能分析,除了进栈操作以外，所有运算实现的时间复杂度都是O（1）。进栈运算在最坏情况下的时间复杂度是O（N）。但最坏情况在N次进栈操作中至多出现一次。如果把扩展

33、数组规模所需的时间均摊到每个插入操作，每个插入只多了一个拷贝操作，因此从平均的意义上讲，插入运算还是常量的时间复杂度。这种分析方法称为均摊分析法。,102,第三章 栈,栈的概念栈的顺序实现栈的链接实现栈类的实现STL中的栈栈的应用,103,栈的链接实现,栈的操作都是在栈顶进行的，因此不需要双链表，用单链表就足够了，而且不需要头结点对栈来讲，只需要考虑栈顶元素的插入删除。从栈的基本运算的实现方便性考虑，可将单链表的头指针指向栈顶。,104,栈的链接实现,105,链接存储时的运算实现,create()：将top_p设为空指针。push(x)：将x插入到单链表的表头,void push(x)p=ne

34、w 结点；p指向的结点的数据部分=x；p指向的结点的指针部分=top_p；top_p=p;,106,链接存储时的运算实现,pop()：删除表头元素,dataType pop()p=top_p;top_p=top_p指向的结点的指针部分；x=p指向的结点的数据部分；delete p;return x;,107,链接存储时的运算实现,top()：返回top_p指向的结点的值。isEmpty()：若top_p的值为空指针，返回true，否则返回false。,108,链接栈的性能分析,由于所有的操作都是对栈顶的操作，邮展中的元素个数无关。所以，所有运算的时间复杂度都是O（1）,109,第三章 栈,栈的

35、概念栈的顺序实现栈的链接实现栈类的实现STL中的栈栈的应用,110,栈的抽象类,template class stack public:virtual bool isEmpty()const=0;virtual void push(const elemType,111,顺序栈类,template class seqStack:public stack private:elemType*elem;int top_p;int maxSize;void doubleSpace();,112,public:seqStack(int initSize=10)elem=new elemTypeinitSi

36、ze;maxSize=initSize;top_p=-1;seqStack()delete elem;bool isEmpty()const return top_p=-1;,113,void push(const elemType,114,doubleSpace,template void seqStack:doubleSpace()elemType*tmp=elem;elem=new elemType2*maxSize;for(int i=0;i maxSize;+i)elemi=tmpi;maxSize*=2;delete tmp;,115,链接栈类,template class lin

37、kStack:public stack private:struct node elemType data;node*next;node(const elemType,116,public:linkStack()elem=NULL;linkStack();bool isEmpty()const return elem=NULL;void push(const elemType,117,析构函数,template linkStack:linkStack()node*tmp;while(elem!=NULL)tmp=elem;elem=elem-next;delete tmp;,118,第三章 栈

38、,栈的概念栈的顺序实现栈的链接实现栈类的实现STL中的栈栈的应用,119,STL中的栈,栈本质上是一个线性表，在STL中栈类是借助于线性表类实现的。STL中的栈提供四个标准运算：push、pop、top和empty。在STL中，借助于其他容器存储数据的容器称为容器适配器。栈就是一个容器适配器,120,栈的类模板,定义一个栈对象要指明栈中元素的类型以及借助于哪一个容器，因此栈的类模板有两个模板参数：栈元素类型和所借助的容器类型。栈可以借助的容器有vector,list和deque。栈的类模板的第二个参数带有缺省值deque 四个标准运算分别通过调用push_back,pop_back,back

39、和 empty 实现,121,STL栈的使用,#include#include using namespace std;int main()stack s1;stack s2;int i;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;return 0;,输出：9 8 7 6 5 4 3 2 1 0,122,第三章 栈,栈的概念栈的顺序实

40、现栈的链接实现栈类的实现STL中的栈栈的应用,123,栈的应用,递归函数的非递归实现符号平衡检查表达式的计算,124,栈的应用递归函数的非递归实现,递归的本质是函数调用，而函数调用是通过栈实现的。因此，递归可以用栈消除。,125,函数执行过程,void main()r1:f1();r2:,void f1()t1:f2();t2:,void f2(),126,函数调用的实现,设置一个栈模拟函数调用。当发生函数调用时，将当前的函数的现场进栈。,127,递归,递归是一种特殊的函数调用，是在一个函数中又调用了函数本身。递归程序的本质是函数调用，而函数调用是要花费额外的时间和空间。在系统内部，函数调用是

41、用栈来实现，如果程序员可以自己控制这个栈，就可以消除递归调用。,128,快速排序,思路：将待排序的数据放入数组a中，数据为alow,ahigh从待排序的数据中任意选择一个，如alow，将它放入变量k将待排序的数据分成两组，一组比k小，放入数组的前一半；一组比k大，放入数组的后一半；将k放入中间位置。对前一半和后一半分别重复上述方法。最好时间效率：O(nlogn),129,low,high,130,快速排序要解决的问题,如何选择作为分段基准的元素？采用第一个元素选取第一个、中间一个和最后一个中的中间元素如何分段？考虑空间问题,131,快速排序函数,void quicksort(int a,int

42、 low,int high)int mid;if(low=high)return;mid=divide(a,low,high);quicksort(a,low,mid-1);quicksort(a,mid+1,high);,132,划分过程,从右向左开始检查。如果high的值大于k，high减1，继续往前检查，直到遇到一个小于k的值。将小于k的这个值放入low的位置。然后从low位置开始从左向右检查，直到遇到一个大于k的值。将low位置的值放入high位置，重复第一步，直到low和high重叠。将k放入此位置。,low,high,K=5,133,low,high,k=5,low,high,lo

43、w,high,low,high,low,high,134,divide函数,int divide(int a,int low,int high)int k=alow;do while(low=k)-high;if(low high)alow=ahigh;+low;while(low high,135,快速排序,void quicksort(int a,int low,int high)int mid;if(low=high)return;mid=divide(a,low,high);quicksort(a,low,mid-1);quicksort(a,mid+1,high);,136,快速排序

44、的非递归实现,设置一个栈，记录要做的工作，即要排序的数据段先将整个数组进栈，然后重复下列工作，直到栈空：从栈中弹出一个元素，即一个排序区间将排序区间分成两半。检查每一半，如果多于两个元素，则进栈，栈元素的格式：struct node int left;int right;,137,138,void quicksort(int a,int size)seqStack st;int mid,start,finish;node s;if(size=1)return;/排序整个数组 s.left=0;s.right=size-1;st.push(s);,139,while(!st.isEmpty()s

45、=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)；,140,栈的应用,递归函数的非递归实现符号平衡检查表达式的计算,141,括号配对检查,编译程序的任务之一，就是检查括号是否配对。如：括号(、和 后面必须依次跟随相应的、及)，“后面必须有”。简单地用开括号和闭括号的数量是否相等来判断开括号与闭括号是否配

46、对是不行的。例如，符号串（）是正确的，而符号串（）是不正确的。因为当遇到）那样的闭括号时，它与最近遇到开括号匹配。,142,使用栈解决符号配对,使用栈，遇到左括号进栈，见到右括号，则出栈，并比较两者是否配对。如判断（3+（5-2）*（6+4）/2），（3+（5-2）*（6+4）/2）“abc”，n（a3+a4 a）,143,算法,首先创建一个空栈。从源程序中读入符号。如果读入的符号是开符号，那末就将其进栈。如果读入的符号是一个闭符号但栈是空的，出错。否则，将栈中的符号出栈。如果出栈的符号和和读入的闭符号不匹配，出错。继续从文件中读入下一个符号，非空则转向3，否则执行7。如果栈非空，报告出错，否

47、则括号配对成功。,144,细节问题,如果对C+的源程序使用此算法，至少需要考虑三种括号：圆括号、方括号和花括号。但有时又不需要考虑圆括号、花括号、方括号是否匹配的问题。例如，当括号出现在注释、字符串常量、字符常量中时，就不需要考虑它的匹配问题。在C+中有很多转义字符，因此在读入一个字符时，还必须考虑如何识别转义字符。,145,要求,设计一个类Balance：对象初始化时传给它一个源文件名。这个类提供一个成员函数checkBalance 检查源文件中的符号是否配对。输出所有不匹配的符号及所在的行号,146,类的定义,class balance private:ifstream fin;/待检查的

48、文件流int currentLine;/正在处理行的的行号int Errors;/已发现的错误数struct Symbol char Token;int TheLine;enum CommentType SlashSlash,SlashStar;public:balance(const char*s);int CheckBalance();,147,private：bool CheckMatch(char Symb1,char Symb2,int Line1,int Line2);char GetNextSymbol();void PutBackChar(char ch);void SkipC

49、omment(enum CommentType type);void SkipQuote(char type);char NextChar();class noFile;,148,构造函数,balance:balance(const char*s)fin.open(s);if(!fin)throw noFile();currentLine=1;Errors=0;,149,CheckBalance的实现,检查输入流对象中的括号是否匹配，并返回错误数算法的实现需要用到一个栈，我们可以用本章中实现的栈类，如seqStack。采用逐步精细化的方法分解这个函数,150,自顶向下的分解,初始化栈为空；Wh

50、ile(lastChar=读文件，直到读入一括号)Switch(lastChar)case,(：进栈 case,)：if(栈空）输出某行某符号不匹配；出错数加1;else match=出栈的符号；检查lastChar与match是否匹配；如不匹配，输出出错信息，出错数加1；if(栈非空)栈中元素均没有找到匹配的闭符号，输出这些错误 return 出错数,151,进一步需要细化,读文件，直到读入一括号；输出某行某符号不匹配；出错数加1；检查lastChar与match是否匹配。如不匹配，输出出错信息，出错数加1；栈中元素均没有找到匹配的闭符号，输出这些错误,152,进一步抽取子函数,第1项工作：