线性表、栈和队列 (1)

1、王桂平信息学院信息技术教研室数据结构与算法数据结构与算法第2章 线性表、栈和队列2信息学院信息技术教研室线性表、栈和队列知识点2.1 2.1.1 2.1.2 2.1.3 2.2 2.2.1 2.2.2 2.3 2.3.1 2.3.2 2.3.3 2.4 2.4.1 2.4.2 2.4.3 2.4.4 2.4.5 2.4.6 2.5 2.5.1 2.5.2 2.5.3 2.5.4 2.5.5 2.5.6 本章和下一章介绍。3信息学院信息技术教研室: 本章讨论几种常用的(统称为)：（也称为向量，是用），类似于C/C+语言中的数组，。（用）：链式结构的线性表，在结点中附件来表达结点之间的关系。2单链

2、表；2双链表；2循环链表：循环单链表，循环双链表。：，插入元素和弹出元素都限制在表的一端(栈顶)。：，只允许在表的一端(队列尾)进入结点，在表的另一端(队列头)移出结点。4信息学院信息技术教研室2.1 线性表: 线性表是一类（区别于和）数据结构，它有多种存储结构和应用方法，从而可以细分为、等。是从的角度来描述数据结构的，它主要有两种存储结构：和。5信息学院信息技术教研室2.1.1 线性表的抽象数据类型: 线性表：直观地讲，。: 在线性表中： 有唯一的，它没有前驱；其他结点都有唯一的前驱结点。 有唯一的，它没有后继；其他结点都有唯一的后继结点。 除开始结点和末尾结点外，其他结点称为，中间结点有唯

3、一的前驱和后继。: 可以从的角度对线性表进行严格定义(略)。6信息学院信息技术教研室：线性表的抽象数据类型: 以下是线性表的，。#include #include /assert函数需要用到的头文件函数需要用到的头文件template class Listpublic:List( );/构造函数构造函数List( );/析构函数析构函数void append( const ELEM& item );/在表尾增加一个元素在表尾增加一个元素/插入一个元素，使之成为第插入一个元素，使之成为第index个元素个元素void insert( const ELEM& item, int i

4、ndex );void remove( int index );/删除第删除第index个元素个元素int search( ELEM data );/查找数据查找数据data查找结点，返回其位置查找结点，返回其位置bool isempty( );/判断线性表是否为空判断线性表是否为空bool isfull( );/判断线性表是否满判断线性表是否满void output( );/输出所有元素的值输出所有元素的值private:int Size; /线性表中当前结点个数线性表中当前结点个数int Length;/线性表的长度线性表的长度;7信息学院信息技术教研室2.1.2 线性表运算分类: 典型的

5、运算：(加)、(除)、(找)、(修)。8信息学院信息技术教研室2.1.3 线性表的存储结构: 线性表的：如何开辟存储空间，各结点存储空间的联系，如何实现等。: 线性表的存储结构主要有两种：。特点是线性表结点可以按地址相邻的顺序存储在一片连续的存储空间中，线性表的固定长度限制了线性表结点个数变化不能超过该固定长度。具体形式有链式存储结构，动态数组等。2在中，各结点的存储空间动态申请和释放，通过指针域来表达结点的前驱/后继关系。：定长数组的变形，当结点个数超出最大限度时，重新申请更长的数组（new和delete运算符）。9信息学院信息技术教研室2.2 顺序表向量(sequential list)又

6、称为(vector)，它。: 向量的：。中，每一个元素按其顺序有唯一的索引值，又称，用它可以方便地访问元素内容。: 顺序表类似于C/C+语言中的，将各种操作封装一个类。10信息学院信息技术教研室2.2.1 STL中的向量，Standard Template Library, 。教材1.7节。: STL提供了：、和。但。11信息学院信息技术教研室STL中的容器。不同类型的容器在其内部以不同的方式组织结点。: STL中常用的容器有：向量。：栈。：队列。：优先队列。: STL中的容器是用实现的。: STL中的容器提供了丰富的成员函数，用以实现所需的功能。12信息学院信息技术教研室STL中的迭代器:

7、STL中的迭代器，它是一个。: 没有支持stack、queue、priority_queue容器的迭代器。学完栈、队列和优先队列后，请回过来思考：为什么这些容器没有迭代器？13信息学院信息技术教研室STL中的算法: STL提供了大约，这些算法能够应用于STL中的容器和数组。: 例如，STL中提供了多个排序函数，下面的就是其中一个。void sort( first, last );/按照升序排列first, last)范围中的元素14信息学院信息技术教研室（教材1.8节）: 包含：#include : 使用：using namespace std;的方法：vector v1;/向量中的元素为字符

8、vector v2; /向量中的元素为整型数据; /向量中的元素为自定义结构体point变量: vector的：往向量的末端插入新的结点；：删除向量末端的结点；：返回最前面结点的迭代器(指针)；：返回最末端结点的迭代器(指针) 。15信息学院信息技术教研室STL向量应用对坐标点按x坐标排序：用向量存储二维平面上的10个点，最后输出这10个点。#include #include /使用使用STL中的向量需要包含的头文件中的向量需要包含的头文件#include /使用使用STL中的算法需要包含的头文件中的算法需要包含的头文件using namespace std;class pointpublic

9、:point( double x1 = 0, double y1 = 0 ) x = x1; y = y1; void setx( double x1 ) x = x1; void sety( double y1 ) y = y1; double getx( ) return x; double gety( ) return y; int operator( point t )/重载重载关系运算符关系运算符return ( x t.x );/根据根据x坐标比较大小坐标比较大小/重载输出运算符重载输出运算符(STL不支持友元函数不支持友元函数?)/friend ostream& oper

10、ator( ostream& ostr, point& t );private:double x, y;16信息学院信息技术教研室ostream& operator( ostream& ostr, point& t )/重载输出运算符重载输出运算符ostr t.getx( ) t.gety( ) endl;return ostr;int main( )/先将先将10个点的坐标存储在数组中个点的坐标存储在数组中double pos102 = -2.7, 3.9, 9.9, 2.0, -12.0, 3.0, 21.0, 13.9, 2.3, -6.0, 3.

11、4, 2.9, 7.2, 8.1, -5.3, 2.9, 37.9, 8.9, 7.7, 1.9 ;int j;/循环变量循环变量point t;/临时变量临时变量for( j=0; j10; j+ ) /往向量中添加往向量中添加10个点个点t.setx( posj0 ); t.sety( posj1 );vector:iterator i1 = /迭代器迭代器vector:iterator i2 = vector:iterator i;for( i=i1; ii2; i+ )cout *i;/迭代器相当于指针迭代器相当于指针(通过迭代器引用向量中的结点通过迭代器引用向量中的结点)return

12、 0;运行情况如下：运行情况如下：-12 3-5.3 2.9-2.7 3.92.3 -63.4 2.97.2 8.17.7 1.99.9 221 13.937.9 8.917信息学院信息技术教研室2.2.2 向量的抽象数据类型：向量的抽象数据类型：向量长度，当前元素个数，指向元素所占存储空间的指针。：追加元素、插入元素、删除元素、查找、判空、判满、输出所有结点的值。template class Vector/与与STL中的向量中的向量(vector)区分区分public:Vector( int L=10 ); /L为创建向量时指定的长度，默认为为创建向量时指定的长度，默认为10Vector(

13、);void append( const ELEM& item );/在表尾增加一个元素在表尾增加一个元素/插入一个元素，使之成为第插入一个元素，使之成为第index个元素个元素void insert( const ELEM& item, int index );void remove( int index );/删除第删除第index个元素个元素int search( ELEM data );/查找元素查找元素data，返回下标或，返回下标或-1bool isempty( );/判断向量是否为空判断向量是否为空bool isfull( );/判断向量是否满判断向量是否满voi

14、d output( );/输出所有元素的值输出所有元素的值private:int Size; /向量中当前元素个数向量中当前元素个数int Length;/向量的长度向量的长度ELEM* elmlist;/指向结点所占存储空间的指针指向结点所占存储空间的指针;18信息学院信息技术教研室template Vector:Vector( int L )assert( L0 );/如果括号内的条件不满足，则会报错如果括号内的条件不满足，则会报错Length = L; Size = 0;elmlist = new ELEML;template Vector:Vector( )delete elmlist

15、;elmlist = NULL;template void Vector:append( const ELEM& item )/在表尾增加一个元素在表尾增加一个元素assert( SizeLength );elmlistSize+ = item;19信息学院信息技术教研室在向量中插入元素/插入一个元素，使之成为第插入一个元素，使之成为第index个元素个元素template void Vector:insert( const ELEM& item, int index )assert( Size=0 & indexindex; i- )/移动元素移动元素elmlisti

16、 = elmlisti-1;elmlistindex = item;Size+;动画仅供参考顺序表的：设顺序表的当前元素个数为 ，在各个位置插入的概率相等，则插入算法平均需要移动个元素。其复杂度为。20信息学院信息技术教研室template void Vector:remove( int index )/删除第删除第index个元素个元素assert( index=0 & indexSize );for( int i=index; iSize-1; i+ )/移动元素移动元素elmlisti = elmlisti+1;Size-;在向量中删除元素动画仅供参考顺序表的：删除算法的复杂度也

17、为 。21信息学院信息技术教研室在向量中查找元素template int Vector:search( ELEM data )/查找元素查找元素data，返回下标或，返回下标或-1int index = -1, i;for( i=0; iSize; i+ )if( elmlisti=data ) index = i;return index;动画仅供参考22信息学院信息技术教研室其他操作template bool Vector:isempty( )/判断向量是否为空判断向量是否为空return (Size=0);template bool Vector:isfull( )/判断向量是否满判断向

18、量是否满return (Size=Length);template void Vector:output( )/输出所有元素的值输出所有元素的值assert( Size0 );cout elmlist0;for( int i=1; iSize; i+ )/输出输出cout elmlisti;cout endl;23信息学院信息技术教研室测试int main( )Vector V1(20);/测试测试V1.append( -17 ); V1.append( 25 ); V1.insert( 66, 2 );V1.remove( 1 ); V1.insert( 19, 1 ); V1.insert

19、( -21, 2 );V1.output( );cout V1.search( 19 ) V1.search( 22 ) endl;return 0;顺序表总结：，每个元素。2) 直接访问元素，与n无关。：，复杂度为。，复杂度为。运行情况如下：运行情况如下：-17 19 -21 661 -124信息学院信息技术教研室2.3 链表( )的特点是，并通过指针来链接结点，按照线性表的把一个个结点链接起来。: 几种用于线性表的链式存储结构：；。: 链表存储是最常用的存储方式之一，它，如树结构和图结构。25信息学院信息技术教研室2.3.1 单链表: 在单链表中，： 存放结点数据的； 存放指向后继结点的。

20、: 因为，因此由这种结点链接而成的链表，称为。：指向单链表中第0个结点()。template class ListNode/单链表中的结点类单链表中的结点类public:ELEM data;ListNode *next;26信息学院信息技术教研室：单链表的抽象数据类型：表首指针first，单链表长度len。：查找结点、插入结点、删除结点、求单链表长度、输出所有结点的值。template class LinkedList/单链表类单链表类public:LinkedList( );/构造函数构造函数LinkedList( );/析构函数析构函数/查找单链表中第查找单链表中第i个结点，返回该结点的指

21、针个结点，返回该结点的指针ListNode* FindIndex( int i );/插入新结点，使之成为第插入新结点，使之成为第i个结点，返回该结点的指针个结点，返回该结点的指针ListNode* Insert( ELEM value, int i );void Remove( int i );/删除第删除第i个结点个结点int Length( );/求链表长度求链表长度void output( );/输出所有结点的值输出所有结点的值bool isEmpty( ) return first=NULL; /判断单链表是否为空判断单链表是否为空private:ListNode *first;/指

22、向单链表首结点的指针指向单链表首结点的指针int len;/单链表长度单链表长度;27信息学院信息技术教研室template LinkedList:LinkedList( )/构造函数构造函数first = NULL; len = 0;template LinkedList:LinkedList( )/析构函数析构函数ListNode *tmp;while( first!=NULL )/释放所有结点释放所有结点tmp = first;first = first-next;delete tmp;28信息学院信息技术教研室查找单链表中第i个结点: 以下：。：，。: 查找的实现：通过结点的指针实现所

23、有的结点，直至找到满足要求的结点为止。动画仅供参考29信息学院信息技术教研室/查找单链表中第查找单链表中第i个结点，返回该结点的指针个结点，返回该结点的指针template ListNode* LinkedList:FindIndex( int i )assert( i=0 & ilen );/确保确保i有效有效int index = 0;ListNode *tmp = first;while( tmp!=NULL )if( index=i ) break;tmp = tmp-next;index+;return tmp;30信息学院信息技术教研室在单链表中插入结点: 以下：。：。:

24、插入结点的实现：特别需要。动画仅供参考31信息学院信息技术教研室/插入新结点，使之成为第插入新结点，使之成为第i个结点，返回该结点的指针个结点，返回该结点的指针template ListNode* LinkedList:Insert( ELEM value, int i )assert( i=0 & i=len );/确保确保i有效有效ListNode *pt1 = new ListNode;assert( pt1!=NULL );pt1-data = value; pt1-next = NULL;if( i=0 )return pt1;ListNode *pt2 = FindInde

25、x( i-1 );/新结点前面的结点新结点前面的结点return pt1;在单链表中插入结点时，为什么要对i为0的情况特殊处理？32信息学院信息技术教研室在单链表中删除结点: 以下：。：。: 删除结点的实现：特别需要。动画仅供参考33信息学院信息技术教研室template void LinkedList:Remove( int i )/删除第删除第i个结点个结点assert( i=0 & ilen );/确保确保i有效有效ListNode *pt1, *pt2;if( i=0 ) return;/待删除结点前面的结点待删除结点前面的结点在单链表中删除结点时，为什么要对i为0的情况特殊处

26、理？34信息学院信息技术教研室求单链表长度: 实现方法1：，直至最后一个结点(注意)。: 实现方法2：单链表类中已经有了，在插入、删除结点时会更新len的值，所以求链表长度时也可以。template int LinkedList:Length( )/求链表长度求链表长度/直接返回成员变量直接返回成员变量len也可以也可以int Len = 0;ListNode *tmp = first;while( tmp!=NULL )Len+;tmp = tmp-next;return Len;35信息学院信息技术教研室: 测试：template void LinkedList:output( )/输出所

27、有结点的值输出所有结点的值assert( len0 );ListNode *pt = first;bool bfirst = true;while( pt!=NULL )if( bfirst ) bfirst = false;else cout ;cout data;pt = pt-next;cout endl;int main( )LinkedList L1;L1.Insert( 21, 0 ); L1.Insert( -17, 1 ); L1.Insert( 99, 1 );L1.Insert( 65, 1 ); L1.Insert( 85, 2 ); L1.Insert( -7, 3 )

28、;L1.output( );L1.Remove( 1 ); L1.Insert( -45, 2 );L1.output( );return 0;运行情况如下：运行情况如下：21 65 85 -7 99 -1721 85 -45 -7 99 -17请画出该单链表的示意图。36信息学院信息技术教研室顺序表与单链表比较分析。，(如需要频繁删除和插入结点)。顺序表单链表存储单个结点/元素只需存储元素的数据即可除了数据外，还要存储指针域整个数据结构的存储空间需要预先申请较大的存储空间每个结点的存储空间都是动态申请/释放，不会浪费空间。访问单个结点/元素O(1)需要从表首结点开始查找插入新结点/元素O(n

29、)O(1)删除元素O(n)O(1)37信息学院信息技术教研室课程设计参考：: 采用面向对象及可视化编程技术，单链表（以及后面的双链表和循环链表）的、等操作。38信息学院信息技术教研室2.3.2 双链表：由于它的next指针仅指向后继结点，因此。: 在双链表中，除data域外，有：指向前驱结点；：指向后继结点。: 因为，因此由这种结点链接而成的链表，称为。template class DListNode/双链表中的结点类双链表中的结点类public:ELEM data;DListNode *Llink, *Rlink;/分别指向前驱结点和后继结点的指针分别指向前驱结点和后继结点的指针;39信息学

30、院信息技术教研室：双链表抽象数据类型：。: 提示：双链表结点有指向前驱结点的指针域，因此可以在双链表类中增加。template class DLinkedList /双链表类双链表类public:DLinkedList( );/构造函数构造函数DLinkedList( );/析构函数析构函数/查找双链表中第查找双链表中第i个结点，返回该结点的指针个结点，返回该结点的指针DListNode* FindIndex( int i );/插入新结点，使之成为第插入新结点，使之成为第i个结点，返回该结点的指针个结点，返回该结点的指针DListNode* Insert( ELEM value, int i

31、 );void Remove( int i );/删除第删除第i个结点个结点int Length( );/求链表长度求链表长度void output( );/输出所有结点的值输出所有结点的值bool isEmpty( );/判断双链表是否为空判断双链表是否为空private:DListNode *first, *last;/指向双链表首结点和末结点的指针指向双链表首结点和末结点的指针int len;/双链表长度双链表长度;40信息学院信息技术教研室在双链表中41信息学院信息技术教研室在双链表中42信息学院信息技术教研室在双链表中43信息学院信息技术教研室2.3.3 循环链表：将单链表末尾结点的

32、指针域，就成为一个循环单链表。：将。: 循环链表的：。44信息学院信息技术教研室：循环单链表和循环双链表的抽象数据类型：。45信息学院信息技术教研室在循环单链表中46信息学院信息技术教研室在循环单链表中47信息学院信息技术教研室在循环单链表中48信息学院信息技术教研室循环链表的应用约瑟夫环问题：给定n个人编号依次为1，2，n，站成一圈，循环报数，报数到m的人将依次被处决，直到只剩下最后一个人。约瑟夫(Josephus)聪明地为自己选择最后剩下的那个位置，以使自己得救。例如，n = 8，m = 4时，依次被处决的人是：4，8，5，2，1，3，7，只剩下第6个人。：。49信息学院信息技术教研室12

33、345678 8214852137453766号是胜利者！开始报数位置：s=1游戏人数：n=8间隔：m=4：从起始位置开始，第m个位置上的数依次出列，循环直至只剩下一个数。：n个人围成一圈，从第1个人开始报数，报数报到m的人出列；然后又从下一个人开始从1开始报数；重复n-1轮游戏，每轮游戏淘汰1个人，最后剩下的人就是胜利者。模拟该游戏，输出依次出列的位置及最后的胜利者。50信息学院信息技术教研室循环链表的应用带密码的约瑟夫环问题：给定n个人编号依次为1，2，n，站成一圈，每个人都有一个密码(为正整数)。这n个人循环报数。第1轮从第1个人开始报数，设他的密码为m，则报数到m的人出列；设这个人的密

34、码为s，则第2轮报数到s的人出列。如此循环直至剩下一个人。：。51信息学院信息技术教研室2.4 栈: 栈()是一种的线性表，常称为(Last In, First Out)。: 栈的一端称为“”，；表的另一端成为“”。，成为()。，称为()。52信息学院信息技术教研室:栈的操作演示1：53信息学院信息技术教研室:栈的操作演示2：54信息学院信息技术教研室：。55信息学院信息技术教研室：的火车站。56信息学院信息技术教研室课程设计参考：: 采用面向对象及可视化编程技术，模拟日常生活中的栈，如折反型的火车站，能。57信息学院信息技术教研室2.4.1 栈的引入。 转换方法：，余数0不能舍去。：通常用一

35、个数组存储得到的余数，然后。：，用一个栈存储得到的余数，转换完毕后，。58信息学院信息技术教研室#include int main( )int dec;/十进制整数十进制整数int binary32;/除除2得到的余数得到的余数scanf( %d, &dec );int i = 0; /循环变量循环变量while( dec )binaryi = dec%2;dec /= 2;i+;for( i-;i=0; i- )/逆序输出得到的余数逆序输出得到的余数printf( %d, binaryi );printf( n );return 0;：用数组存储得到的余数，即可。59信息学院信息技术

36、教研室。 括号：圆括号( )，方括号 ，花括号 。 匹配例子：、。 不匹配例子：、。：依次读入每个括号，；如果是，则，如果是，则，如果，则可以判定。前面匹配与不匹配的例子的判定方法。60信息学院信息技术教研室2.4.2 STL中的栈: 包含：#include : 使用：using namespace std;的方法：stack S1;/栈中的结点为字符stack S2; /栈中的结点为整型数据; /栈中的结点为自定义结构体pos变量: stack的：，参数为需要压入栈的结点；：，返回值为出栈的结点；：，返回值为栈顶结点，该操作并不会弹出栈顶结点；：，返回值为bool型。：。61信息学院信息技术

37、教研室:“例2.7：十进制整数转换成二进制”的实现。#include #include using namespace std;int main( )int dec;/十进制整数十进制整数scanf( %d, &dec );while( dec )S.push(dec%2);/压栈压栈dec /= 2;while( !S.empty( ) )/一次输出栈顶元素并弹出一次输出栈顶元素并弹出printf( %d, S.top( ) );S.pop( );printf( n );return 0;62信息学院信息技术教研室:“例2.8：括号匹配”的实现。#include #include #

38、include using namespace std;int main( )char bracket50;/读入的括号串读入的括号串(假定除括号外没有其他字符假定除括号外没有其他字符)scanf( %s, bracket );int len = strlen(bracket), i;bool prejudge = false;/是否能提前判定不匹配的状态变量是否能提前判定不匹配的状态变量for( i=0; ilen; i+ )if( bracketi=( | bracketi= | bracketi= )/左括号左括号S.push(bracketi);63信息学院信息技术教研室else/右括

39、号右括号if( S.empty( ) )/栈空，不匹配栈空，不匹配prejudge = true; break;elseif( bracketi=) & S.top()!=( |bracketi= & S.top()!= |bracketi= & S.top()!= )prejudge = true; break;else S.pop( );if( prejudge ) printf( not match!n ); /能提前判定不匹配能提前判定不匹配elseif( !S.empty( ) )/扫描完毕后，如果栈非空，则不匹配扫描完毕后，如果栈非空，则不匹配printf(

40、 not match!n );else printf( match!n );return 0;64信息学院信息技术教研室2.4.3 顺序栈的实现：栈的：/以下实现的栈，除了类名跟以下实现的栈，除了类名跟STL中的栈名不一样外，使用方法完全一样中的栈名不一样外，使用方法完全一样template class Stack/与与STL中的栈中的栈(stack)区分区分public:Stack( int L=10 );/L为创建栈时指定的长度，默认为为创建栈时指定的长度，默认为10Stack( );void push( ELEM item );/将将item压栈压栈void pop( );/将栈顶结点弹

41、出将栈顶结点弹出ELEM top( );/取得栈顶结点取得栈顶结点(不弹出不弹出)bool empty( );/判断栈是否为空判断栈是否为空int size( );/返回栈中结点的个数返回栈中结点的个数void clearstack( ); /将栈清空将栈清空private:int Size; /栈中结点的个数栈中结点的个数;: 栈的实现主要分为两种：和。65信息学院信息技术教研室顺序栈的实现(): 用一段存储各结点(实现时，在构造函数里动态申请一段存储空间，并用指针elmlist指向它)。: 用Length表示(即申请存储空间能存储结点的最大数目)，用Size表示。: 用tpos指示当前。注

42、意：所谓栈的后进先出，队列的先进先出，并不是因为它们所使用的存储结构具有这样的特点，而是因为它们的。66信息学院信息技术教研室：#include #include /assert函数需要用到的头文件函数需要用到的头文件/以下实现的栈，除了类名跟以下实现的栈，除了类名跟STL中的栈名不一样外，使用方法完全一样中的栈名不一样外，使用方法完全一样template class Stack/与与STL中的栈中的栈(stack)区分区分public:Stack( int L=10 );/L为创建栈时指定的长度，默认为为创建栈时指定的长度，默认为10Stack( );void push( ELEM item

43、 );/将将item压栈压栈void pop( );/将栈顶结点弹出将栈顶结点弹出ELEM top( );/取得栈顶结点取得栈顶结点(不弹出不弹出)bool empty( );/判断栈是否为空判断栈是否为空int size( );/返回栈中结点的个数返回栈中结点的个数void clearstack( ); /将栈清空将栈清空/以下是新增的成员函数以下是新增的成员函数bool full( );/判断栈是否满了判断栈是否满了private:int Size; /栈中结点的个数栈中结点的个数/新增的数据成员新增的数据成员int Length;/栈的长度栈的长度ELEM* elmlist;/指向结点所

44、占存储空间的指针指向结点所占存储空间的指针int tpos; /该变量指示栈顶结点的位置该变量指示栈顶结点的位置;67信息学院信息技术教研室：template Stack:Stack( int L )assert( L0 );/如果括号内的条件不满足，则会报错如果括号内的条件不满足，则会报错Length = L;Size = 0;elmlist = new ELEML;tpos = -1;template Stack:Stack( )delete elmlist;elmlist = NULL;template void Stack:push( ELEM item )/将将item压栈压栈ass

45、ert( tposLength-1 );elmlist+tpos = item;Size+;68信息学院信息技术教研室：template void Stack:pop( )/将栈顶结点弹出将栈顶结点弹出assert( tpos=0 );tpos-; Size-;template ELEM Stack:top( ) /取得栈顶结点取得栈顶结点(不弹出不弹出)assert( tpos=0 );return elmlisttpos;template bool Stack:empty( )/判断栈是否为空判断栈是否为空return (tpos=-1);69信息学院信息技术教研室：template in

46、t Stack:size( )/返回栈中结点的个数返回栈中结点的个数return Size;template bool Stack:full( )/判断栈是否满判断栈是否满return (tpos=Length-1);template void Stack:clearstack( )/将栈清空将栈清空tpos = -1; Size = 0;70信息学院信息技术教研室：int main( )S1.push(2); S1.push(5);printf( %dn, S1.top( ) ); S1.pop( );S1.push(17); S1.push(93); S1.push(-38);while(

47、 !S1.empty( ) )printf( %dn, S1.top( ) ); S1.pop( );return 0;运行情况如下：运行情况如下：5-389317271信息学院信息技术教研室2.4.4 链式栈的实现: 用存储栈中的各结点。: 在链式栈的类声明中增加。: 用head，在压栈、出栈等操作时，将会修改该指针。: 因为链表中各结点所占存储空间都是动态申请的，所以不需要表示栈长度的Length成员。72信息学院信息技术教研室链式栈的实现()：/以下实现的栈，除了类名跟以下实现的栈，除了类名跟STL中的栈名不一样外，使用方法完全一样中的栈名不一样外，使用方法完全一样template cl

48、ass Stack/与与STL中的栈中的栈(stack)区分区分public:/Stack( int L=10 ); /L为创建栈时指定的长度，默认为为创建栈时指定的长度，默认为10Stack( ); /修改后的构造函数修改后的构造函数Stack( );void push( ELEM item );/将将item压栈压栈void pop( );/将栈顶结点弹出将栈顶结点弹出ELEM top( );/取得栈顶结点取得栈顶结点(不弹出不弹出)bool empty( );/判断栈是否为空判断栈是否为空int size( );/返回栈中结点的个数返回栈中结点的个数void clearstack( );

49、 /将栈清空将栈清空private:int Size; /栈中结点的个数栈中结点的个数/新增的结构体声明新增的结构体声明struct ListNode/单链表中的结点单链表中的结点ELEM data;ListNode* next;/新增的数据成员新增的数据成员ListNode* head;/指向栈顶结点的指针指向栈顶结点的指针;73信息学院信息技术教研室：template Stack:Stack( )head = NULL;template Stack:Stack( )while( head!=NULL )ListNode* tmp = head;head = head-next;delete

50、 tmp;template void Stack:push( ELEM item )/将将item压栈压栈ListNode* tmp = new ListNode;assert( tmp!=NULL );/tmp为为NULL表示申请空间失败表示申请空间失败tmp-data = item;tmp-next = head;head = tmp;Size+;74信息学院信息技术教研室：template void Stack:pop( )/将栈顶结点弹出将栈顶结点弹出assert( !empty( ) ); /确保栈非空确保栈非空ListNode* tmp = head;head = head-nex

51、t;delete tmp;Size-;template ELEM Stack:top( ) /取得栈顶结点取得栈顶结点(不弹出不弹出)assert( !empty( ) ); /确保栈非空确保栈非空return head-data;template bool Stack:empty( )/判断栈是否为空判断栈是否为空return (head=NULL);75信息学院信息技术教研室：template int Stack:size( )/返回栈中结点的个数返回栈中结点的个数return Size;template void Stack:clearstack( )/将栈清空将栈清空while( he

52、ad!=NULL )ListNode* tmp = head;head = head-next;delete tmp;Size = 0;76信息学院信息技术教研室：int main( )S1.push(2); S1.push(5);printf( %dn, S1.top( ) ); S1.pop( );S1.push(17); S1.push(93); S1.push(-38);while( !S1.empty( ) )printf( %dn, S1.top( ) ); S1.pop( );return 0;运行情况如下：运行情况如下：5-389317277信息学院信息技术教研室顺序栈与链式栈

53、的比较： 缺点：； 优点：（但这个优势无法在栈中体现，因为栈的操作无需访问中间结点）。：。 缺点：。（但这个缺点，因为栈的操作只需在栈顶进行，而这个个结点有指针直接指向它） 优点：，无需实现设定好，适合结点个数变换频繁的情形。78信息学院信息技术教研室2.4.5 栈的应用计算表达式的值: 表达式求解：是栈的重要应用。: 思考：里对的： 名词短语 = 冠词名词 动词短语 = 动词副词 The girl walks gracefully.冠词名词动词 副词79信息学院信息技术教研室(1) 中缀表达式的递归定义：由数字符号09以及加、减、乘、除符号和括号共16个符号组成。：一共有5个语法成分。：语法

54、公式又称为，用于定义语法成分。在语法公式中，符号是规则定义符。左边：被定义的语法成分。右边：定义该语法成分的语法规则。：不是语法成分，而是用于分隔其他语法成分，含义是“或者”。80信息学院信息技术教研室全部：。 语法公式：采用定义。 = + | | = * |/ | = | （ ） = | = 0 | 1 | 2 | 3 | 4 | 5 | 6| 7 | 8 | 981信息学院信息技术教研室:中缀表达式的求解(人工求解)： 以下求解过程对人来说是没有问题的，因为人可以从全局把握整个表达式的计算过程。1) 先执行括号内的计算，后执行括号外的计算。在具有多层括号时，按层次反复地脱括号，左右括号必须

55、配对。2) 在无括号或同层括号时，先乘(*) 、除()，后作加(+)、减(-)。3) 在同一个层次，若有多个乘除（*、）或加减(+，-)的运算，那就按自左至右顺序执行。82信息学院信息技术教研室:中缀表达式的求解(用计算机程序求解)： 中缀表达式。 中缀表达式的运算次序，。为了方便用计算机求解表达式，需要。：。83信息学院信息技术教研室(2) 后缀表达式(逆波兰表示式)全部： = + | | = * | / | = = | = 0 | 1 | 2 | 3 | 4 | 5 | 6| 7 | 8 | 9后缀表达式例子：84信息学院信息技术教研室:后缀表达式的求解： 中缀表达式与后缀表达式：。 后缀

56、表达式可以。85信息学院信息技术教研室(3) 设计表达式类，实现中缀表达式的求解：设计一个表达式类，实现中缀表达式的求解： 综合运用STL中的队列和栈，实现 ；。/表达式中的项表达式中的项/为简化起见，约定表达式中操作数及中间结果均为正整数，且除法不保留余数为简化起见，约定表达式中操作数及中间结果均为正整数，且除法不保留余数struct term/表达式中的每一项表达式中的每一项(运算符也认为是一项运算符也认为是一项)char str20;/从表达式中提取得到的项从表达式中提取得到的项(字符形式字符形式)int v;/对应的值对应的值(约定约定-1表示表示+和和-,-2表示表示*和和/,-3表

57、示表示(,-4表示表示);86信息学院信息技术教研室表达式类class Exp/表达式类表达式类public:Exp( const char* pstr );/构造函数：用字符串常量构造构造函数：用字符串常量构造Exp( ) /析构函数析构函数void extract( );/从中缀表达式中提取每一项，存放到队列中从中缀表达式中提取每一项，存放到队列中1)void in2pos( );/将中缀表达式转换成后缀表达式将中缀表达式转换成后缀表达式2)void compute( );/计算后缀表达式的值计算后缀表达式的值3)void output( ) cout value endl; /输出求得的

58、值输出求得的值private:char infixExpMAXL;/中缀表达式中缀表达式char postfixExpMAXL;/对应的后缀表达式对应的后缀表达式int value;/表达式的值表达式的值queue Q1; /用队列存储中缀表达式中的每一项用队列存储中缀表达式中的每一项queue Q2; /用队列存储后缀表达式中的每一项用队列存储后缀表达式中的每一项;Exp:Exp( const char* pstr ) /构造函数：用字符串常量构造构造函数：用字符串常量构造strcpy( infixExp, pstr ); value = 0;memset( postfixExp, 0, s

59、izeof(postfixExp) );87信息学院信息技术教研室1) 从表达式中提取每一项，存放在队列中void Exp:extract( )/从中缀表达式中提取每一项，存放到队列中从中缀表达式中提取每一项，存放到队列中int len = strlen(infixExp), i;char tmpMAXL; strcpy( tmp, infixExp );term t;/用于往用于往Q1中加入结点的临时结点变量中加入结点的临时结点变量bool fdigit = true;/数字项第一个数字的标志数字项第一个数字的标志bool bnum = false;/当前这一项是否数值项的标志当前这一项是否

60、数值项的标志int num; /数值项对应的值数值项对应的值int s, lnum;/数值项开始位置，长度数值项开始位置，长度for( i=0; i=0 & tmpi=9 )/数字字符数字字符if( fdigit )fdigit = false; bnum = true;num = 0; s = i; lnum = 0;lnum+; num = num*10 + tmpi - 0;else/非数字字符非数字字符if( bnum )/提取到一个数值项提取到一个数值项t.v = num; memset( t.str, 0, sizeof(t.str) );strncpy( t.str, tmp+s, lnum ); Q1.push(t);fdigit = true; bnum = false;88信息学院信息技术教研室if( tmpi=+ )/符号：符号：+