数据结构第一部分

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()：创建一个空的线性表; 清除一个线性表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）：返回线性表中第i个数据元素的值; 遍历线性表运算traverse()：按序访问线性表的每一数据元素。,6,第二章 线性表,线性表的概念 线性表的实现 线性表类的实现 STL中线性表的实现,7,线性表的实现,线性表的顺序实现 线性表的链接实现,8,线性表的顺序存储结构,线性表中结点存放在存储器上一块连续的空间中。 借助存储空间的连续性，结点可以按照其逻辑顺序依次存放。 结点存放的物理位置和它的逻辑位置是一致的。,9,线性表的顺序存储,在程序设计语言中，一块连续的存储空间可以用一个数组实现。由于线性表中的元素个数是动态的，因此采用了动态数组。 保存一个动态数组，需要三个变量：指向线性表元素类型的指针，数组规模（容量），数组中的元素个数（表长）。,an,an-1,a2,a1,a0,maxSize,length,data,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) num = -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操作按一定的比例扩大数组的空间，常用的比例是扩大一倍。 数组空间在内存中必须是连续的，因此，扩大数组空间的操作必须重新申请一个更大规模的动态数组，将原有数组的内容拷贝到新数组中，释放原有数组空间，将新数组作为存储线性表的存储区。,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等于0时，移动次数为n。 最好情况下的时间复杂度为O(1) 最坏情况下的时间复杂度为O(n) 平均的时间复杂度：如果在每个位置上的插入都是等概率的，则插入算法的平均时间复杂度为n/2,18,线性表的顺序实现总结,由于要保持逻辑次序和物理次序的一致性，顺序表在插入删除时需要移动大量的数据，性能不太理想。 由于逻辑次序和物理次序的一致性使得定位访问的性能很好。 顺序表比较适合静态的、经常做定位访问的线性表。,19,表的实现,线性表的顺序实现 线性表的链接实现,20,线性表的链接存储结构,将每个结点放在一个独立的存储单元中，结点间的逻辑关系依靠存储单元中附加的值针来给出。 结点的存储单元在物理位置上可以相邻，也可以不相邻。,21,线性表的链接存储,单链表 双链表 循环链表,22,单链表,每个结点附加了一个指针字段，如next，该指针指向它的直接后继结点，最后一个结点的next字段为空。,23,insert,p,24,头结点 、头指针,为了消除特殊情况，通常在表头额外增加一个相同类型的特殊结点，称之为头结点。它们不是线性表中的组成部分。 头结点的出现，使得在表头位置上进行插入和删除和在其它结点位置上是完全一致的，从而使得插入和删除算法得到简化。,25,带头结点的单链表,a0,a1,an-1,26,Create函数的实现,申请一块存储结点的空间，设结点的指针部分为空指针。 将结点地址存入代表单链表的变量head。,27,清除一个线性表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),void 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,搜索某个元素在线性表中是否出现search(x),int search(x) num = 0; p = 头结点的直接后继； While (p != 空指针 ,32,访问线性表的第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和next prior字段给出直接前驱结点的地址 next给出直接后继结点的地址。,36,双链表的头尾节点,为了消除在镖头、表尾插入删除的特殊情况，通常双链表设一头结点，设一尾节点 头结点中prior字段为空，它的next字段给出线性表中的首结点的地址 尾结点中next字段为空，它的prior字段给出线性表中最后一个节点的地址,37,Create运算,创建一个双链表就是创建一个只有头尾结点的链表，把头结点的地址保存在head中，尾结点的地址保存在tail中,38,insert,p,39,remove,x,p,40,线性表的链接存储,单链表 双链表 循环链表,41,单循环链表,一般单循环链表不带头结点,42,双循环链表,头结点中prior字段给出尾结点的地址，尾结点中next字段给出头结点的地址 一般也不设头尾结点,43,第二章 线性表,线性表的概念 线性表的实现 线性表类的实现 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,顺序表类的定义,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 ,50,构造函数,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 currentLength - 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,链表类的设计,以双链表为例 链表类的数据成员：头指针、尾指针，以及为了提高时间性能而设置的数据成员currentLength 链表类必须实现线性表的所有操作。为保证这一点，链表类从线性表的抽象类继承。 链表的插入、删除操作都需要将指针移到被操作结点的前一结点。特设计函数move实现,57,结点及其组成,链表中的结点包含三部分：数据字段、前趋指针和后继指针字段。 数据字段可以是任何类型的数据，这里仍然用ElemType表示；指针字段用于存放其他相关结点的地址值。 由于结点类型是链表专用的，因此可设为内嵌类。 由于链表的操作是通过对结点的操作实现的，于是把结点类定义成struct，以方便链表类访问。,58,双链表类的定义,template class linkList: public list private: struct 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; currentLength = 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,template void linkList:insert(int i, const elemType ,insert,pos,63,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; ,64,search,template int linkList:search(const elemType ,65,visit,template elemType linkList:visit(int i) const node *p = move(i); return p-data; ,66,traverse,template void linkList:traverse() const node *p = head-next; cout data next; cout endl; ,67,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; ,68,缺点,双链表类仅实现了线性表的基本运算，并没有用到双链表的特点，如逆向查找等,69,第二章 线性表,表的概念 表的实现 线性表类的实现 STL中表的实现,70,STL,STL（标准模版库）是C+中数据结构的实现。这些数据结构被称为集合或容器。 STL中线性表的实现有两种： Vector：线性表的顺序实现 List：线性表的双链表的实现,71,Vector和list,共同支持的操作 所有的容器都支持的整体操作：求规模、清空和判空 在表尾的插入和删除以及取表头表尾元素 List特有的操作：表头的插入和删除 Vector特有的操作：的重载，按下标取元素，求容量，重新设置数组的大小。 迭代器：两者都能用迭代器访问,72,STL中的迭代器操作,获取一个迭代器： Begin：返回一个指向第一个节点的迭代器 End：返回一个指向最后一个节点的迭代器 迭代器本身的方法：向后移动，取迭代器指向的元素值，判迭代器相等和不相等 需要迭代器的容器操作： 在指定位置上插入一元素 删除指定位置的元素 删除指定位置之间的所有元素,73,STL中线性表的实现,Vector：线性表的顺序实现，且大小可增长 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 ,不允许隐式转换,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; /指向最后一个元素的地址 ;,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.capacity() endl; v.push_back(4); cout “n after push 4, capacity of v is: “ v.capacity() endl; cout“n 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: 0 the initial capacity of v is: 0 After push 2, capacity of v is: 1 After push 3, capacity of v is: 2 After push 4, capacity of v is: 4 the size of v is: 3 the capacity of v is : 4 contents of v using : 2 3 4 contents of v using iterator notation: 2 3 4,83,STL中表的实现,Vector：线性表的顺序实现，且大小可增长 List：线性表的双链表实现,STL（标准模版库）是C+中数据结构的实现。,84,List的实现,采用了带头节点的双链表实现,85,List的功能,允许在任何位置插入和删除 支持双向迭代器 头文件：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() 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,contents 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）：结点从栈顶删除 进栈（Push）：结点在栈顶位置插入 空栈 ：栈中结点个数为零时,97,栈的运算,创建一个栈create()：创建一个空的栈； 进栈push(x)：将x插入栈中，使之成为栈顶元素； 出栈pop()：删除栈顶元素并返回栈顶元素值； 读栈顶元素top()：返回栈顶元素值但不删除栈顶元素； 判栈空isEmpty()：若栈为空，返回true，否则返回false。,98,第三章 栈,栈的概念 栈的顺序实现 栈的链接实现 栈类的实现 STL中的栈 栈的应用,99,栈的顺序实现,用连续的空间存储栈中的结点，即数组 进栈和出栈总是在栈顶一端进行，不会引起类似顺序表中的大量数据的移动。用数组的后端表示栈顶。,100,顺序存储时的运算实现,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。,101,顺序实现性能分析,除了进栈操作以外，所有运算实现的时间复杂度都是O（1）。 进栈运算在最坏情况下的时间复杂度是O（N）。 但最坏情况在N次进栈操作中至多出现一次。如果把扩展数组规模所需的时间均摊到每个插入操作，每个插入只多了一个拷贝操作，因此从平均的意义上讲，插入运算还是常量的时间复杂度。这种分析方法称为均摊分析法。,102,第三章 栈,栈的概念 栈的顺序实现 栈的链接实现 栈类的实现 STL中的栈 栈的应用,103,栈的链接实现,栈的操作都是在栈顶进行的，因此不需要双链表，用单链表就足够了，而且不需要头结点 对栈来讲，只需要考虑栈顶元素的插入删除。从栈的基本运算的实现方便性考虑，可将单链表的头指针指向栈顶。,104,栈的链接实现,105,链接存储时的运算实现,create()：将top_p设为空指针。 push(x)：将x插入到单链表的表头,void push(x) p = new 结点； 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,第三章 栈,栈的概念 栈的顺序实现 栈的链接实现 栈类的实现 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 elemTypeinitSize; 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 linkStack: 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,第三章 栈,栈的概念 栈的顺序实现 栈的链接实现 栈类的实现 STL中的栈 栈的应用,119,STL中的栈,栈本质上是一个线性表，在STL中栈类是借助于线性表类实现的。 STL中的栈提供四个标准运算：push、pop、top和empty。 在STL中，借助于其他容器存储数据的容器称为容器适配器。栈就是一个容器适配器,120,栈的类模板,定义一个栈对象要指明栈中元素的类型以及借助于哪一个容器，因此栈的类模板有两个模板参数：栈元素类型和所借助的容器类型。 栈可以借助的容器有vector, list和deque。 栈的类模板的第二个参数带有缺省值deque 四个标准运算分别通过调用push_back, pop_back, back 和 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,第三章 栈,栈的概念 栈的顺序实现 栈的链接实现 栈类的实现 STL中的栈 栈的应用,123,栈的应用,递归函数的非递归实现 符号平衡检查 表达式的计算,124,栈的应用递归函数的非递归实现,递归的本质是函数调用，而函数调用是通过栈实现的。因此，递归可以用栈消除。,125,函数执行过程,void main() r1: f1(); r2: ,void f1() t1: f2(); t2: ,void f2() ,126,函数调用的实现,设置一个栈模拟函数调用。当发生函数调用时，将当前的函数的现场进栈。,127,递归,递归是一种特殊的函数调用，是在一个函数中又调用了函数本身。 递归程序的本质是函数调用，而函数调用是要花费额外的时间和空间。 在系统内部，函数调用是用栈来实现，如果程序员可以自己控制这个栈，就可以消除递归调用。,128,快速排序,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); ,129,快速排序的非递归实现,设置一个栈，记录要做的工作，即要排序的数据段 先将整个数组进栈，然后重复下列工作，直到栈空： 从栈中弹出一个元素，即一个排序区间 将排序区间分成两半。 检查每一半，如果多于两个元素，则进栈， 栈元素的格式： struct node int left; int right; ;,130,131,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);,132,while (!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)； ,133,栈的应用,递归函数的非递归实现 符号平衡检查 表达式的计算,134,括号配对检查,编译程序的任务之一，就是检查括号是否配对。如：括号( 、 和 后面必须依次跟随相应的 、 及 )，“后面必须有”。 简单地用开括号和闭括号的数量是否相等来判断开括号与闭括号是否配对是不行的。例如，符号串（）是正确的，而符号串（ ）是不正确的。因为当遇到）那样的闭括号时，它与最近遇到开括号匹配。,135,使用栈解决符号配对,使用栈，遇到左括号进栈，见到右括号，则出栈，并比较两者是否配对。 如判断（3 +（5 - 2）*（6 + 4）/ 2）， （3 +（5 - 2）*（6 + 4）/ 2） “abc”， n （a3 + a4 a）,136,算法,首先创建一个空栈。 从源程序中读入符号。 如果读入的符号是开符号，那末就将其进栈。 如果读入的符号是一个闭符号但栈是空的，出错。否则，将栈中的符号出栈。 如果出栈的符号和和读入的闭符号不匹配，出错。 继续从文件中读入下一个符号，非空则转向3，否则执行7。 如果栈非空，报告出错，否则括号配对成功。,137,细节问题,如果对C+的源程序使用此算法，至少需要考虑三种括号：圆括号、方括号和花括号。 但有时又不需要考虑圆括号、花括号、方括号是否匹配的问题。例如，当括号出现在注释、字符串常量、字符常量中时，就不需要考虑它的匹配问题。 在C+中有很多转义字符，因此在读入一个字符时，还必须考虑如何识别转义字符。,138,要求,设计一个类Balance： 对象初始化时传给它一个源文件名。 这个类提供一个成员函数checkBalance 检查源文件中的符号是否配对。输出所有不匹配的符号及所在的行号,139,类的定义,class balance private: ifstream fin; /待检查的文件流 int currentLine ; /正在处理行的的行号 int Errors; /已发现的错误数 struct Symbol char Token; int TheLine; enum CommentType SlashSlash, SlashStar ; public: balance(const char *s) ; int CheckBalance() ;,140,private： bool CheckMatch(char Symb1, char Symb2, int Line1, int Line2 ) ; char GetNextSymbol(); void PutBackChar(char ch); void SkipComment(enum CommentType type); void SkipQuote(char type); char NextChar(); ; class noFile ;,141,构造函数,balance:balance(const char *s) fin.open(s); if (!fin) throw noFile(); currentLine = 1; Errors = 0; ,142,CheckBalance的实现,检查输入流对象中的括号是否匹配，并返回错误数 算法的实现需要用到一个栈，我们可以用本章中实现的栈类，如seqStack。 采用逐步精细化的方法分解这个函数,143,自顶向下的分解,初始化栈为空； While ( lastChar = 读文件，直到读入一括号 ) Switch (lastChar) case , , (：进栈 case ,)： if (栈空） 输出某行某符号不匹配；出错数加1; else match = 出栈的符号； 检查lastChar与match是否匹配； 如不匹配，输出出错信息，出错数加1； if (栈非空) 栈中元素均没有找到匹配的闭符号，输出这些错误 return 出错数,144,进一步需要细化,读文件，直到读入一括号； 输出某行某符号不匹配；出错数加1； 检查lastChar与match是否匹配。如不匹配，输出出错信息，出错数加1； 栈中元素均没有找到匹配的闭符号，输出这些错误,145,进一步抽取子函数,第1项工作： GetNextSymbol 功能：从文件的当前位置开始，跳过所有的非括号，读到第一个括号后返回。在遇到文件结束时，返回一个特定的符号，如NULL。 函数原型：函数有一个字符型的返回值。执行该函数必须有一个输入流，在读输入流的过程中，当前处理的行号会变，在读的过程中也可能遇到异常情况，因此出错数也会变。这三个信息：文件流对象，当前处理的行号，出错个数都是对象的数据成员。因此函数原型为：char GetNextSymbol（）。 第3项工作：CheckMatch 功能：比较两个指定位置的待比较的符号是否匹配 函数原型：bool balance:CheckMatch(char Symb1, char Symb2, int Line1, int Line2 ),146,CheckBalance的定义,int balance:CheckBalance() struct Symbol node; seqStack st; char LastChar, Match; /LastChar为读入的符号，Match为栈顶的符号,CheckBalance函数不需要参数。因为输入流对象是类的数据成员。返回值是一个整型数，表示出错个数,147,while( 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; ,148,while( !st.isEmpty() Errors+; node = st.pop(); cout “第“ node.TheLine “行的符号“ node.Token “不匹配n“; return Errors; ,149,CheckMatch,bool balance:CheckMatch(char Symb1, char Symb2, int Line1, int Line2 ) if ( Symb1 = ( ,150,GetNextSymbol,在读文件时要跳过其它符号，提取出各类括号 注释中的括号不用考虑，字符串常量和字符常量中的括号也不用考虑。 C+中的注释又有两种形式。一种是以“/”开始到本行结束。另一种是以“/*”开始到“*/”结束，可以跨行。不管是哪一种注释，都要判断两个符号才能决定,151,GetNextSymbol的伪代码,Char GetNextSymbol() while ( ch = 从文件中读入下一字符 ) if ( Ch = = /) /可能是注释的开始 if (ch = 从文件中读入下一字符 ) if ( Ch = = * ) 跳过标准C的注释; else if ( Ch = = / ) 跳过C+的注释; else 不是注释，把ch放回输入流; else if ( Ch = = | Ch = = ”) 跳过字符常量或字符串常量; else if ( Ch = = | Ch = = | Ch = = (| Ch = = )| Ch = = |Ch = = ) return Ch; return 0; / 文件结束。 ,152,进一步提取子函数,从文件中读入下一字符 ： char NextChar(); 跳过的注释： void SkipComment(enum CommentType type); 把ch放回输入流： void PutBackChar (char ch); 跳过字符常量或字符串常量： void SkipQuote(char type);,153,GetNextSymbol函数的实现,char balance:GetNextSymbol(