第3章 顺序存储结构的表、堆栈和队列 3.1 顺序存储结构 3.2 表和顺序表 3.3 堆栈和顺序堆栈 3.4 队列和顺序队列

Presentation on theme: "第3章 顺序存储结构的表、堆栈和队列 3.1 顺序存储结构 3.2 表和顺序表 3.3 堆栈和顺序堆栈 3.4 队列和顺序队列"— Presentation transcript:

1 第3章 顺序存储结构的表、堆栈和队列 3.1 顺序存储结构 3.2 表和顺序表 3.3 堆栈和顺序堆栈 3.4 队列和顺序队列
第3章 顺序存储结构的表、堆栈和队列 3.1 顺序存储结构 3.2 表和顺序表   3.3 堆栈和顺序堆栈 3.4 队列和顺序队列 3.5 优先级队列和顺序优先级队列

2 3.1 顺序存储结构 计算机所处理的所有的数据都要存储在内存中。计算机高级语言系统对数据的存储结构有四种：顺序存储结构、链式存储结构、间接地址和仿真指针。其中，顺序存储结构和链式存储结构是两种最基本和最常用的存储结构。本节讨论顺序存储结构，其余三种存储结构依次在4.1节、5.2节和7.1节中讨论。

3 顺序存储结构是计算机中的一种最基本和最主要的数据存储结构。在顺序存储结构中，用户向系统申请一块地址连续的有限空间用于存储数据元素集合，这样，任意两个在逻辑上相邻的数据元素在物理上也必然相邻。在C++中，向系统申请一块地址连续的有限空间的方法是使用数组。数组有静态数组和动态数组两种。不论是静态数组还是动态数组，其功能都是向系统申请一块地址连续的有限空间，只是使用的方法不同。

4 C++中静态数组向系统申请一块地址连续的有限空间的方法是使用数组定义语句“［］”。当程序运行超出该静态数组定义的范围时，系统自动回收该静态数组的地址空间。一个静态数组定义的例子如下：
＃include<stdio.h> const int MaxSize=100; void main(void) { int i; int temp［MaxSize］; //静态申请MaxSize个整型元素的存储空间

5 for(i=0;i<6;i++) { temp［i］=i+1; printf("temp［%d］=%d＼n",i,temp［i］); //C函数输出 } }

6 当程序运行退出主函数时，系统将自动回收分配给静态数组temp的地址空间。
C++中动态数组向系统申请一块地址连续的有限空间的方法是使用动态存储分配函数。动态数组存储空间的回收方法是当不再需要该动态数组时，使用动态存储释放函数。C++中动态存储分配函数用new，动态存储释放函数用delete。new能自动计算要分配类型的空间大小并自动返回正确的指针类型。delete能自动释放由new分配的存储空间。

7 new的语法格式是：名字指针=new类型名(初始化值)。其中，初始化值可为空。
new分配动态数组的语法格式是：名字指针=new类型名［N］。其中，N必须是有确定值的整数型常量或变量。 delete的语法格式是：delete名字指针 delete释放动态数组的语法格式是：delete［］名字指针上例的动态数组定义的例子如下：

8 ＃include<iostream.h>
＃include<stdlib.h> void main(void) { int i,*temp; const int MaxSize=100; temp=new int［MaxSize］; //动态申请MaxSize个整型元素的存储空间

9 for(i=0;i<6;i++) { temp［i］=i+1; //动态数组测试 cout<<"i="<<i<<"temp［i］="<<temp［i］<<endl; } delete［ ］temp;//释放申请的动态存储空间 }

10 从上例可见，静态数组存储空间的申请和释放由系统自动完成，动态数组存储空间的申请和释放由用户通过调用系统函数完成。
设要存储的数据元素为a0,a1,a2,a3,a4,a5，顺序存储结构（不论是用静态数组还是用动态数组）向系统申请了MaxSize个ai数据类型的存储空间，size为数组的当前数组元素个数。其内存结构示意图如图3―1所示。

11 图3―1 顺序存储结构内存结构示意图

12 3.2 表和顺序表   表（List）是一种可在任意位置进行插入和删除操作的由n（n≥0）个相同类型数据元素组成的线性结构，n是表的长度，n=0的表称作空表。从数据元素之间的逻辑关系来划分，数据结构可分为线性结构和非线性结构两种。线性结构是指数据元素之间的逻辑关系为除第一个元素和最后一个元素外，每个数据元素都只有一个前驱元素和一个后继元素。表是最简单的一种线性结构。

13 对表的操作方法主要有初始化构造表、在表的某一位置插入一个元素、在表的某一位置删除一个元素、定位某个数据元素在表中的存储位置、取表中某个存储位置的数据元素、判表是否为空等。用顺序存储结构存储的表称作顺序表（SequentList）。顺序表中任意数据元素的存取和访问可通过它的位置指针（即数组下标）来进行。

14 顺序表的类定义 综合前面的讨论可知，一个顺序表涉及的数据成员包括数组、数组的最大元素个数和当前数组元素的个数。顺序表的操作方法和前面讨论的表的操作方法相同，主要有初始化构造表、在表的某一位置插入一个元素、在表的某一位置删除一个元素、定位某个数据元素在表中的存储位置、取表中某个存储位置的数据元素、判表是否为空等。使用静态数组方法的顺序表的类定义如下：

15 ＃include<iostream.h>
＃include<stdlib.h> const int MaxListSize=100; ∥MaxListSize是问题要求的元素数目的最大值 Class SeqList { private: Datatype data［MaxListSize］; //抽象类型Datatype定义的数组 int size;//数据元素个数

16 public: SeqList(void); //构造函数 ~SeqList(void); //析构函数 int ListSize(void)const; //返回元素的个数size int ListEmpty(void)const; //表空返回1；否则返回0 int Find(Datatype&item)const; //返回元素item在表中的位置 DatatypeGetData(intpos)const; //返回位置pos的元素 voidInsert(const Datatype& item,int pos); //在位置pos插入元素item Datatype Delete(constintpos); //删除位置pos的元素并返回 void ClearList(void); //把表清空 };

17 顺序表的类实现 顺序表类SeqList的实现如下： //构造函数。置顺序表的数据元素个数size为0 SeqList::SeqList(void):size(0){} //析构函数 SeqList::~SeqList(void){} //返回顺序表的数据元素个数size intSeqList::ListSize(void)const { return size;

18 } //判顺序表空否，为空返回1；不空返回0 intSeq List::ListEmpty(void)const { if(size==0)return1; else[KG*4]return0; //定位元素item的位置，返回值为item在顺序表中的位置；返回值为-1表示不存在 intSeq List::Find(Datatype&item)const {

19 if(size==0)return-1; inti=0; while(i<size&&item!=data［i］)i++; //寻找item if(i<size)returni; elsereturn-1; } //返回顺序表中位置pos上的元素。参数出错时退出 DatatypeSeqList::GetData(intpos)const { if(pos<0‖pos>size-1)//取的元素序号必须在0至size-1之间{

20 cerr<<"参数pos越界出错!"<<endl;
exit(1);//参数1表示出错退出 } returndata［pos］;} //在指定位置pos插入一个数据元素item voidSeqList::Insert(constDatatype&item,intpos) { inti; if(size==MaxListSize) cerr<<"顺序表已满无法插入！"<<endl; exit(1);

21 if(pos<0‖pos>size)//当pos等于size时表示插入在最后
{ cerr<<"参数pos越界出错!"<<endl; exit(1); } //从后向前把前一个元素迁移到后一个元素位置直到存储位置pos为止 for(i=size;i>pos;i--)data［i］=data［i-1］; data［pos］=item;//在pos位置插入item size++;//数据元素个数size加1

22 //删除指定位置pos上的数据元素并返回
DatatypeSeqList::Delete(constintpos) { if(size==0) cerr<<"顺序表已空无元素可删！"<<endl; exit(1); } if(pos<0||pos>size-1)//删除元素序号必须在0至size-1之间 cerr<<"参数pos越界出错!"<<endl;

23 } Datatypetemp=data［pos］; //从pos至size-2逐个元素左移,data［size-1］移入data［size-2］中 for(inti=pos;i<size-1;i++)data［i］=data［i+1］; size--;//数据元素个数size减1 returntemp; //置顺序表为空 voidSeqList::ClearList(void) { size=0;//数据元素个数size置为初始化值 }

24 顺序表上插入、删除算法的效率分析 顺序表上的插入和删除是顺序表类中时间复杂度最高的成员函数。顺序表上的插入和删除过程的图示如图3―2（a）和图3―2（b）。图3―2（a）是在原来已有6个元素的顺序表的pos=3位置插入数据元素item=13的过程图示；图3―2（b）是在原来已有7个元素的顺序表中删除pos=3位置的数据元素的过程图示。

25 图3―2 顺序表上的插入和删除   (a)插入一个数据元素；(b)删除一个数据元素

26 在顺序表中插入一个数据元素时，算法中时间复杂度最高的部分是循环移动数据元素。循环移动数据元素的效率和插入数据元素的位置pos有关，最坏情况是pos=0，需移动size个数据元素；最好情况是pos=size，需移动0个数据元素。设Pi是在第i个存储位置插入一个数据元素的概率，设顺序表中的数据元素个数为n，当在顺序表的任何位置上插入数据元素的概率相等时，有Pi=1／(n+1)，则向顺序表插入一个数据元素时所需移动的数据元素的平均次数为

27 在顺序表中删除一个数据元素时，算法中时间复杂度最高的部分也是循环移动数据元素。循环移动数据元素的效率和删除数据元素的位置pos有关，最坏情况是pos=0，需移动size-1个数据元素；最好情况是pos=size，需移动0个数据元素。设Qi是在第i个存储位置插入一个数据元素的概率，设顺序表中已有的数据元素个数为n，当在顺序表的任何位置上插入数据元素的概率相等时，有Qi=1/n，则向顺序表插入一个数据元素时所需移动的数据元素的平均次数为：

28 在顺序表中定位一个数据元素时，累加计数变量i次数的分析和在顺序表中删除一个数据元素的分析类同。
顺序表中的其余操作都和数据元素个数n无关，因此，在上述顺序表中插入和删除一个数据元素的时间复杂度为O（n）；定位一个数据元素的时间复杂度为O（n）；其余操作的时间复杂度均为O（1）。  

29 在进行面向对象的程序设计时，任何一个新类的设计都要考虑它的派生类对它的继承。当把顺序表上的插入和删除成员函数设计成如图3―3所示的方式时，任何类似顺序表但对顺序表上插入和删除操作要考虑数据元素原来顺序的都不能继承它。解决这个问题的一个方法是设计一个顺序表基类，然后分别设计两个派生类，一个设计成图3―2方式的插入和删除成员函数，另一个设计成图3―3方式的插入和删除成员函数。这样上述问题就可妥善解决。

30 图3―3 顺序表上不考虑原来顺序的插入和删除 (a)插入一个数据元素；(b)删除一个数据元素

31 顺序表的应用 例3―1 编写一个程序向顺序表中插入5个整数值，然后以插入次序删除这5个数。程序如下： typedefintDatatype; ∥具体应用时定义的数据类型Datatype ＃include"SeqList.h“ ∥类SeqList的定义和实现头文件 voidmain(void) { SeqListmyList; for(inti=0;i<5;i++) ∥插入5个整型元素

32 myList.Instert(i+10,i);
cout<<"测试GetData( )成员函数结果如下："<<endl; for(i=0;i<5;i++) cout<<myList.GetData(i)<<""; cout<<"测试Delete( )成员函数结果如下："<<endl; cout<<myList.Delete(0)<<""; }

33 程序输出为： 测试GetData( )成员函数结果如下：  测试Delete( )成员函数结果如下：

34 在上述顺序表类SeqList的定义中，数据类型Datatype是一个未定义的抽象符号。在上面我们定义数据类型Datatype为整型int，我们也可以定义数据类型Datatype为字符型char，我们还可以定义数据类型Datatype为任意一个自定义的结构体类型或一个类类型。定义数据类型Datatype为一个自定义的结构体类型的例子见本章例3―3；定义数据类型Datatype为一个类类型的概念见2.2节中类Line中对类Point类型变量的定义。下面是例3―1数据类型Datatype改为char类型的程序。

35 typedefcharDatatype;
//定义数据类型Datatype为char类型 ＃include"SeqList.h" voidmain(void) { SeqListlist; inti;

36 for(i=0;i<5;i++)//插入5个字符元素
list.Insert(′A′+i,i); for(i=0;i<5;i++)//依次删除5个字符元素并在屏幕显示 cout<<list.Delete(0)<<“ "; } 此时程序的输出为： A B C D E

37 3.3 堆栈和顺序堆栈 堆栈（Stack）是一种特殊的线性表，是一种只允许在表的一端进行插入和删除操作的线性表。堆栈中允许进行插入和删除操作的一端称为栈顶，另一端称为栈底。栈顶的当前位置是动态的，标识栈顶当前位置的称为栈顶指示器（或栈顶指针）。堆栈的插入和删除操作通常称为进栈或入栈，堆栈的删除操作通常称为出栈或退栈。当栈中没有数据元素时称之为空栈。

38 根据堆栈的定义，每次进栈的数据元素都放在原当前栈顶元素之前而成为新的栈顶元素，每次退栈的数据元素都是原当前栈顶元素，这样，最后进入堆栈的数据元素总是最先退出堆栈，因此，堆栈也称作后进先出表。
用顺序存储结构存储的堆栈称为顺序堆栈（SequentStack）。图3―4是一个顺序堆栈的动态示意图。图中，最大元素个数设为6，top为栈顶指示器。图3―4（a)表示一个空栈；图3―4(b)表示插入一个数据元素A后的状态；图3―4(c)表示插入数据元素B、C、D后的状态；图3―4(d)表示删除数据元素D、C后的状态；图3―4(e)表示删除数据元素B、A后的状态。

39 图3―4 顺序堆栈的动态示意图 （a)空栈；(b)插入数据元素A后； (c)插入数据元素B、C、D后； (d)删除数据元素D、C后；(e)删除数据元素B、A后

40 顺序堆栈类定义和实现 1.直接类定义和实现方法 直接定义是指直接定义顺序堆栈类，不考虑顺序堆栈类数据成员对顺序表类数据成员的继承。下面的顺序堆栈定义中部分类成员函数使用了内联函数的方法。 ＃include<stdlib.h> ＃include<iostream.h> cons tint MaxStackSize=100; class SeqStack {

41 private: Datatypedata［MaxStackSize］; //抽象类型Datatype的数组  inttop; //栈顶位置指示器 public: SeqStack(void) //构造函数 {top=0;}; //内联函数方式 ~SeqStack(void) //析构函数 {}; //内联函数方式

42 voidPush(constDatatype&item); //把元素item入栈
DatatypePop(void); //出栈数据元素并返回 DatatypePeek(void)const; //读栈顶数据元素并返回 intStackEmpty(void)const //堆栈空返回1；否则返回0 {return(top==0);}; //内联函数方式 intGetSize(void)const //读栈元素个数top {returntop;}; //内联函数方式 voidClearStack(void) //清空堆栈使之为初始化状态 {top=0;} //内联函数方式 };

43 栈顶位置指示器top和顺序表中的当前元素个数size的含义完全相同，只是在堆栈中用top更能反映它的栈顶位置指示器的含义，所以在此使用了不同的名字。此外，顺序堆栈中的数组data［］和顺序表中的数组data［］也完全相同。因此我们说，顺序堆栈和顺序表的逻辑结构完全相同，只是两者允许的操作集合不同，顺序表允许在任意位置插入和删除，而顺序堆栈只允许在栈顶位置插入和删除，所以我们也可以说，顺序堆栈是操作受限制的顺序表。

44 //把元素item入栈；堆栈满时出错退出
voidSeqStack::Push(constDatatype&item) { if(top==MaxStackSize) cerr<<"堆栈已满!"<<endl; exit(1); } data［top］=item; //top的初始值为0是有效存储单元,所以先存储item top++; //然后top加1

45 } //出栈并返回栈顶元素；堆栈空时出错退出 DatatypeSeqStack::Pop() { if(top==0) cout<<"堆栈已空!"<<endl; exit(1); } top--; //top先减1 returndata［top］; //然后取top位置上的元素返回

46 //取栈顶元素返回 DatatypeSeqStack::Peek(void)const { if(top==0) cerr<<"堆栈空!"<<endl; exit(1); } returndata［top-1］; //top指在栈顶的下一个位置,取top-1上的元素返回 }

47 2. 继承类定义和实现方法 继承类定义指考虑顺序堆栈类数据成员对顺序表类数据成员继承性的定义。 ＃include"SeqList.h" classSeqStack:privateSeqList { public: SeqStack(void); //构造函数 ~SeqStack(void){}; //析构函数 voidPush(constDatatype&item); //元素item入栈  

48 DatatypePop(void); //出栈元素并返回
DatatypePeek(void)const; //读栈顶元素并返回 intStackEmpty(void)const; //栈空时返回1;否则返回0 intGetSize(void)const; //读栈元素个数size voidClearStack(void); //清空堆栈使之为初始化状态 };

49 在以下SeqStack类的实现中都是调用了基类SeqList的公有成员函数，因为是private派生方式，所以此时基类SeqList的所有公有成员函数成为派生类SeqStack的私有成员函数。派生类SeqStack通过调用基类SeqList的公有成员函数来实现成员函数的功能。

50 //构造函数 SeqStack::SeqStack(void){ SeqList(); } //把元素item入栈;栈满时出错退出voidSeqStack::Push(constDatatype&item) { if(ListSize()==MaxListSize) //基类的ListSize( )返回基类的size值 cerr<<"堆栈已满!"<<endl; exit(1);

51 } Insert(item,ListSize()); //在当前顶部位置插入元素} //出栈并返回栈顶元素;栈空时出错退出 DatatypeSeqStack::Pop(void) { if(ListSize()==0) cerr<<"堆栈已空!"<<endl; exit(1); returnDelete(ListSize()-1); //删除最后存入的元素并返回 }

52 //取栈顶元素返回 DatatypeSeqStack::Peek(void)const { returnGetData(ListSize()-1); //取最后存入的元素返回 } //判堆栈空否，空返回1；非空返回0 intSeqStack::StackEmpty(void)const returnListEmpty(); //读栈元素个数size intSeqStack::GetSize(void)const returnListSize();

53 } //清空堆栈使之为初始化状态 voidSeqStack::ClearStack(void) { ClearList( ); } 上述文件名为CSeqStack.h。

54 顺序堆栈应用——表达式计算 堆栈是各种软件系统中应用最广泛的数据结构之一。例如，表达式计算是编译系统中的基本问题，其实现方法是堆栈的一个典型应用。在编译系统中，要把便于人理解的表达式翻译成能正确求值的机器指令序列，通常需要先把表达式变换成机器便于理解的形式，这就要变换表达式的表示序列。借助顺序堆栈即可实现这样的变换。

55 在机器内部，任何一个表达式都是由操作数、运算符和分界符组成的。操作数和运算符是表达式的主要部分，分界符标志了一个表达式的结束。我们称操作数、运算符和分界符为一个表达式的单词。根据表达式的类型，表达式可分为三类，即算术表达式、关系表达式和逻辑表达式。为叙述简洁，我们仅讨论算术表达式的计算。算术表达式只包含加、减、乘、除、左括号和右括号。读者不难把他推广到其他类型表达式的计算中。假设计算机高级语言中的一个算术表达式为 A+(B-C/D)*E

56 这种算术表达式中的运算符总是出现在两个操作数之间（除单目运算符外），所以也称为中缀表达式。编译系统对中缀形式的算术表达式处理的方法是先把它转换为后缀形式的算术表达式。后缀形式的算术表达式就是表达式中的运算符出现在操作数之后，并且不含括号。例如，中缀算术表达式A+B的后缀表达式为AB+。要把一个中缀算术表达式变换成相应的后缀表达式要考虑算术运算规则。算术四则运算的规则是：  

57 （1）先乘除后加减； （2）先括号内后括号外； （3）同级别时先左后右。 上面的中缀表达式写成满足四则运算规则的相应的后缀表达式即为 ABCD/-E*+ 其运算次序为：T1=CD/；T2=BT1-；T3=T2E*；T4=AT2E+。可见，后缀表达式有以下两个特点：

58 （1）后缀表达式的操作数与中缀表达式的操作数先后次序相同，只是运算符的先后次序改变；
（2）后缀表达式中没有括号，后缀表达式的运算符次序就是其执行次序。 综上所述，编译系统中表达式的计算分为两个步骤： （1）把中缀表达式变换成相应的后缀表达式； （2）根据后缀表达式计算表达式的值。 表3―1给出了包括加、减、乘、除、左括号、右括号和分界符的算术运算符间的优先级关系表。表中，θ1代表栈顶运算符，θ2代表当前扫描读到的运算符。

59 表3―1 运算符优先级关系表

60 表3-1是四则运算三条规则的变形。当θ1为+或-，θ2为
表3-1是四则运算三条规则的变形。当θ1为+或-，θ2为*或/时，θ1的优先级高于θ2的优先级，满足规则（1）的先乘除后加减。当θ1为+、-、*或/，θ2为“（”时，θ1的优先级高于θ2的优先级，满足规则（2）的先括号内后括号外。当θ1的运算符和θ2的运算符同级别时，θ1的优先级高于θ2的优先级，满足规则（3）的同级别时先左后右。

61 几个特殊处理考虑如下： (1)由于后缀表达式无括号，当θ1为“（”，θ2为“）”时，用标记“=”使算法在此时去掉该对括号。 (2)当θ1为“＃”，θ2为“＃”时，用标记“=”使算法在此时结束处理。 （3）表中值为空，表示不允许出现此种情况，一旦出现即为中缀表达式语法出错，如θ1为“）”，θ2为“（”的情况即为中缀表达式语法出错。为简化下面的算法设计，我们在下边的算法设计中未考虑此种中缀表达式语法出错情况。

62 根据以上分析，中缀表达式变换为后缀表达式的算法步骤是：
（1）设置一个堆栈，初始时将栈顶元素置为“＃”。 （2）顺序读入中缀表达式，当读到的单词为操作数时就将其输出，并接着读下一个单词。 （3）令x1为当前栈顶运算符的变量，x2为当前扫描读到运算符的变量，当顺序从中缀表达式中读入的单词为运算符时就赋予x2，然后比较x1的优先级与x2的优先级，若x1的优先级高于x2的优先级，将x1退栈并作为后缀表达式的一个单词输出，然后接着比较新的栈顶运算符x1的优先级与x2的优先级。

63 上述算法的C++实现如下,其中函数Proceed(charx1,charx2)完成两个运算符x1和x2优先级的比较，函数Postfix(SeqStack&s,char*Expression)借助堆栈s完成中缀表达式Expression到后缀表达式的转换和输出。主函数用中缀表达式等于“A+(B-C/D)*E＃”的例子验证算法。

64 图3―5 中缀表达式变换成后缀表达式的过程  

65 ＃include<string.h>
typedefcharDatatype; //定义具体问题的数据类型 Datatype ＃include"SeqStack.h" charProceed(charx1,charx2) //运算符x1和x2优先级的比较 { charResult; charMidString［2］;

66 Result=′<′; //Result的初始值为′<′
MidString［0］=x2; //x2赋于MidString［0］ MidString［1］=0; //添字符串的结束标记0 //x1大于x2。比较中利用了求子串函数strstr() if(((x1==′+′||x1==′-′)&&strstr("+-)＃",MidString)!=NULL)|| ((x1==′*′||x1==′/′)&&strstr("+-*/)＃",MidString)!=NULL)|| (x1==′)′&&strstr("+-*/)＃",MidString)!=NULL)) Result=′>′; x1等于x2

67 elseif((x1==′(′&&x2==′)′)||(x1==′＃′&&x2==′＃′))Result=′=′;
elseif((x1==′(′&&x2==′＃′)||(x1==′)′&&x2==′(′)||(x1==′ ＃′&&x2==′)′)) Result=′′; //当三种情况均不是时为x1小于x2。 returnResult; //返回Result } intPostfix(SeqStack&s,char*Expression)

68 //借助堆栈s的中缀表达式Expression到后缀表达式的转换和输出
{ charx1,x2; intj=0; s.Push(′＃′); //初始栈顶置为＃ x2=Expression［j］; //取第一个单词给x2 x1=s.Peek(); //栈顶的分界符＃给x1 while(1) //循环直到转换完毕 if(x2!=′+′&&x2!=′-′&&x2!=′*′&&x2!=′/′&&

69 x2!=′(′&&x2!=′)′&&x2!=′＃′) //x2为操作数
{ cout<<x2<<′′; //输出操作数x2 x2=Expression［++j］ //继续取下一个单词给x2 }  elseif(Proceed(x1,x2)==′<′) //x1的优先级<x2的优先级 s.Push(x2); //把x2入栈 x1=s.Peek(); //取新的栈顶元素给x1 x2=Expression［++j］; //继续取下一个单词给x2

70 elseif(Proceed(x1,x2)==′>′) //x1的优先级>x2的优先级
{ x1=s.Pop();[DW1]//退栈 cout<<x1<<′′; //输出x1 x1=s.Peek(); //取新的栈顶元素给x1 } //x1等于左括号x2等于右括号 elseif(Proceed(x1,x2)==′=′&&x1==′(′&&x2==′)′) s.Pop(); //退栈去掉左括号

71 x2=Expression［++j］; //重新取x2的值去掉右括号
} //转换完毕 elseif(Proceed(x1,x2)==′=′&&x1==′＃′&&x2==′＃′) { cout<<′＃′; return1; //转换成功返回1 } elseif(Proceed(x1,x2)==′′)break; //语法有错 cout<<"中缀表达式语法有错!"<<endl;

72 return0； //转换失败返回0 } voidmain(void) //主函数 { charExpression［80］={"A+(B-C/D)*E＃"}; SeqStacks; Postfix(s,Expression); }

73 程序运行输出转换后的后缀表达式，程序输出为：
A B C D / - E * + 在上述程序中若想使用继承方式的顺序堆栈，只需把包含宏语句改为： ＃include"CSeqStack.h" 即可。 设算法中单词个数为n，该算法对输入的中缀表达式进行了一次从左到右的扫描，对其中每个操作数执行了一次输出，对每个操作符执行进栈和出栈各一次，所以算法的时间复杂度为O（n）。

74 上述程序的中缀表达式为"A+(B-C/D)
上述程序的中缀表达式为"A+(B-C/D)*E"，这个中缀表达式中所有操作数变量均为单字符变量，程序中也是按单字符变量分割操作数变量的。实际上，所有计算机高级语言中均支持多字符变量，如何在此基础上允许中缀表达式的操作数变量为多字符变量已超出了本课程讨论的范围，我们不作讨论。

75 把中缀表达式变换为后缀表达式的另一种方法是设置一个堆栈用于临时存放操作符，给每个操作符按照四则运算规则规定一个栈内优先数和一个栈外优先数。当扫描到的操作符的栈外优先数大于当前栈顶操作符的栈内优先数时，则扫描到的操作符进栈；当扫描到的操作符的栈外优先数小于当前栈顶操作符的栈内优先数时，则当前栈顶操作符退栈并输出。这个过程一直进行到栈空为止。对这种方法的算法实现有兴趣的读者可参见相关文献或自己设计。

76 把中缀表达式变换成相应的后缀表达式后，计算后缀表达式的值的过程仍是一个堆栈应用问题。其算法思想是：设置一个堆栈存放操作数，从左到右依次扫描后缀表达式，每读到一个操作数就将其进栈；每读到一个运算符就从栈顶取出两个操作数施以该运算符所代表的运算操作，并把该运算结果作为一个新的操作数入栈；此过程一直进行到后缀表达式读完，最后栈顶的操作数就是该后缀表达式的运算结果。计算后缀表达式值的算法我们将作为链式堆栈的应用例子在第4章中讨论。 图3―6是以后缀表达式ABCD/-E*+为例说明上述算法思想的后缀表达式求值过程，其中设MaxStackSize=6。

77 图3―6 后缀表达式求值过程

78 3.4 队列和顺序队列   队列（Queue）也是一种特殊的线性表，是一种只允许在表的一端进行插入操作，在表的另一端进行删除操作的线性表。表中允许进行插入操作的一端称为队尾，允许进行删除操作的一端称为队头。队头和队尾分别由队头指示器（或称队头指针）和队尾指示器（或称队尾指针）指示。队列的插入操作通常称作入队列，队列的删除操作通常称作出队列。当队列中没有数据元素时称作空队列。

79 根据队列的定义，每次进队列的数据元素都放在原来的队尾之后成为新的队尾元素，每次出队列的数据元素都是原来的队头元素。这样，最先入队列的数据元素总是最先出队列，所以队列也称作先进先出表。
用顺序存储结构存储的队列称作顺序队列（SequentQueue）。图3―7是一个有6个存储空间的顺序队列的动态示意图。图中，front为队头指示器，rear为队尾指示器。  

80 图3―7（a)表示一个空队列；图3―7(b)表示入队列数据元素A、B、C后的状态；图3―7(c)表示出队列数据元素A、B后的状态；图3―7(d)表示入队列数据元素D、E、F后的状态。
对队列的操作主要有：初始化建立一个队列、入队列、出队列、取队头数据元素和判队列是否为空等操作。

81 图3―7 顺序队列的动态示意图   （a)空队列；(b)入队列A、B、C后的状态； (c)出队列A、B后的状态；(d)入队列D、E、F后的状态

82 顺序循环队列 对于顺序队列，从图3―7(d)可以看出，此时若继续进行入队列操作将使队尾指示器rear的值超出顺序队列定义的6个存储空间的范围而“溢出”，但此时队列中还有2个存储空间可供存储，因此，这时的“溢出”并不是由于存储空间不够而产生的溢出，这种溢出通常称作假溢出。由于存在假溢出问题，所以顺序队列很少在实际软件系统中使用。实际软件系统中使用的顺序队列基本都是这里要讨论的顺序循环队列。

83 假溢出是由于队尾指示器rear的值和队头指示器front的值不能由所定义存储空间的最大值自动转为所定义存储空间的最小值而产生的，因此，解决的方法是把顺序队列所使用的存储空间构造成一个逻辑上首尾相连的循环队列。当rear和front达到MaxQueueSize-1后，再前进一个位置就自动到0，这可以利用求模（或称取余）运算（%）来实现。

84 如何判断顺序循环队列的队列满和队列空条件呢？首先，我们看顺序循环队列队头指示器front和队尾指示器rear的初始化值，设顺序循环队列的MaxQueueSize=6，令front=rear=0，其状态如图3―8(a)所示；当入队列数据元素A、B、C、D、E、F后顺序循环队列满，此时有front=rear=0，其状态如图3―8(b)所示；当出队列数据元素A、B、C、D、E、F后顺序循环队列空，此时有front=rear=0，其状态如图3―8(c)所示。

85 图3―8 顺序循环队列的队列满和队列空状态(a)初始化状态；
(b)队列满状态；(c)队列空状态

86 可见，此时队列满和队列空的队头指示器front和队尾指示器rear的取值状态相同，这是无法区分的。解决的方法通常是少用一个存储空间，以队尾指示器rear加1等于队头指示器front为队列满的条件。即顺序循环队列的队列满条件为 (rear+1)%MaxQueueSize==front 顺序循环队列的队列空条件仍然为 rear==front

87 顺序循环队列类的定义和实现 根据上面对顺序循环队列的分析，我们有顺序循环队列类的定义和实现如下：   ＃include<iostream.h> ＃include<stdlib.h> constintMaxQueueSize=100; classSeqQueue { private: Datatypedata［MaxQueueSize］; //抽象类型Datatype定义的数组

88 intfront; //队头指示器 intrear; //队尾指示器 intcount; //元素个数计数器 public: SeqQueue(void) //构造函数 {front=rear=0;count=0;}; ~SeqQueue(void){}; //析构函数 voidQInsert(constDatatype&item); //入队列 DatatypeQDelete(void); //出队列 DatatypeQFront(void)const; //读队头元素值

89 intQueueEmpty(void)const //判队列是否为空
{returnfront==rear;}; voidClearQueue(void) //清空队列 {front=rear=0;count=0;} intGetSize(void)const //取队列元素个数 {returncount;}; } //把元素item入队列voidSeqQueue::QInsert(constDatatype&item) {

90 if(count==MaxQueueSize)
{ cerr<<"队列已满!"<<endl; exit(1); } data［rear］=item; //把元素item加在队尾 rear=(rear+1)%MaxQueueSize; ///队尾指示器加1 count++; //计数器加1 } //把队头元素出队列，出队列元素由返回值带回

91 DatatypeSeqQueue::QDelete()
{ Datatypetemp; if(count==0) cerr<<"队列已空!"<<endl; exit(1); } temp=data［front］; //保存原队头元素值 front=(front+1)%MaxQueueSize; //队头指示器加1 count--; //计数器减1 returntemp; //返回原队头元素} 

92 //读队头元素，队头元素由返回值带回 DatatypeSeqQueue::QFront(void)const { if(count==0) cerr<<"队列空!"<<endl; exit(1); } returndata［front］; //返回队头元素 }

93 上述文件名为SeqQueue.h。一个6个元素的顺序循环队列的入队列过程见图3―9。其中图3―9（a）为初始状态，图3―9（b）为无循环情况的入队列过程，图3―9（c）为循环情况的入队列过程。

94 图3―9 顺序循环队列的入队列过程

95 一个6个元素的顺序循环队列的出队列过程见图3―10。其中图3―10（a）为初始状态，图3―10（b）为无循环情况的出队列过程，图3―10（c）为循环情况的出队列过程。

96 图3―10 顺序循环队列的出队列过程  

97 顺序循环队列的应用 由于顺序循环队列和顺序队列结构近似，但顺序循环队列的功能大大优于顺序队列的功能，所以顺序队列几乎不被采用。 顺序循环队列的应用很广泛。例如，操作系统中的各种数据缓冲区的先进先出管理，应用系统中的各种事件排队管理，等等。这里我们讨论一个用顺序循环队列和顺序堆栈实现判断一个字符序列是否是回文的例子。

98 例3―2 编程序判断一个字符序列是否是回文(回文是指一个字符序列以中间字符为基准两边字符完全相同)。
程序从键盘输入一个字符序列存入字符串str中，字符串长度小于等于80，输入字符序列以回车换行符为结束标记，字符串str中不包括回车换行符。把字符串中字符逐个分别存入队列和堆栈，然后逐个出队列和退栈并比较出队列的元素和退栈的元素是否相等，若全部相等则该字符序列是回文，否则就不是回文。程序如下：

99 ＃include<string.h>
typedefcharDatatype; //定义具体应用的数据类型Datatype ＃include"SeqQueue.h" ＃include"SeqStack.h" voidmain(void) { SeqStackmyStack; SeqQueuemyQueue; charstr［80］; cout<<"输入字符序列，回车换行符结束："<<endl;

100 cin.getline(str,80); //从键盘接收字符序列
inth=strlen(str); //求字符序列长度 for(inti=0;i<h;i++) { myQueue.QInsert(str［i］); myStack.Push(str［i］); } while(!myQueue.QueueEmpty()) if(myQueue.QDelete()!=myStack.Pop()) cout<<"不是回文!"<<endl;

101 return; } cout<<"是回文!"<<endl; } 第一次程序运行状态为： 输入字符序列，回车换行符结束： ABCDEDCBA 字符序列是回文!

102 第二次程序运行状态为： 输入字符序列，回车换行符结束： ABCDEDC 字符序列不是回文! 判断一个字符序列是否是回文还有更简单的方法。这里的程序主要是为了举例说明顺序队列类和顺序堆栈类的使用方法。

103 3.5 优先级队列和顺序优先级队列 优先级队列（PriorityQueue）是带有优先级的队列。队列是数据元素的先进先出表，即最先进入队列的元素将最先被删除。但在有些软件系统中有时也要求把进入队列中的元素分优先级，出队列（即删除）时，首先选择优先级最高的元素出队列，对优先级相同的元素则按先进先出的原则出队列。简单的优先级队列也可不考虑优先级相同的元素的先进先出问题。

104 顺序优先级队列类定义和类实现 通常优先级队列的优先级为一数值，并规定数值越小优先级越高。一个不考虑优先级相同元素的先进先出问题的顺序优先级队列类的定义和实现如下： ＃include<iostream.h> ＃include<stdlib.h> constintMaxPQueueSize=100; classSeqPQueue { private: Datatypedata［MaxPQueueSize］; //抽象类型Datatype定义的数组

105 intsize; //数据元素个数 public: SeqPQueue() //构造函数 {size=0;} ~SeqPQueue(void){} //析构函数 voidPQInsert(constDatatype&item); //把元素item插入队尾 DatatypePQDelete(void); //把队头元素删除并由函数返回 DatatypePQFront(void)const; //读队头元素值并由函数返回 intPQueueEmpty(void)const //判队列是否为空

106 {returnsize==0;} voidClearPQueue(void) //清空队列 {size=0;} intGetSize(void)const //取队列元素个数 {returnsize;} }; voidSeqPQueue::PQInsert(constDatatype&item) //把元素item插入队尾 { if(size==MaxPQueueSize) cout<<"队列已满!"<<endl;

107 exit(1); } data［size］=item; //把元素item加在队尾 size++; //数据元素个数加1 } DatatypeSeqPQueue::PQDelete(void) //把优先级最高的元素删除并由函数返回 { if(size<=0) cout<<"队列已空!"<<endl;

108 } Datatypemin=data［0］; //初始选data［0］为优先级最高的元素 intminIndex=0; //minIndex为优先级最高元素的下标 for(inti=1;i<size;i++) //寻找优先级最高的元素及对应下标 if(data［i］<min) { min=data［i］; minIndex=i; } data［minIndex］=data［size-1］; //把最后一个元素放在被删除元素的位置 size--; //数据元素个数减1

109 returnmin; //返回优先级最高的元素
} DatatypeSeqPQueue::PQFront(void)const //读优先级最高元素并由函数返回 { if(size<=0) cout<<"队列已空!"<<endl; exit(1); //方法和把优先级最高的元素删除并由函数返回方法类同

110 Datatypemin=data［0］;
intminIndex=0; for(inti=1;i<size;i++) if(data［i］<min) { min=data［i］; minIndex=i; } returnmin; }

111 上述文件名为SeqPQueue.h。考虑优先级相同元素的先进先出问题的顺序优先级队列，只需把出队列成员函数改为如下形式即可。
//把队头元素删除并由函数返回，对相同优先级的元素按先进先出原则删除并返回 DatatypeSeqPQueue::PQDelete(void) { if(size<=0) cout<<"队列已空!"<<endl; exit(1);

112 }  Datatypemin=data［0］; //初始选data［0］为优先级最高的元素 intminIndex=0; //minIndex为优先级最高元素的下标for(inti=1;i<size;i++) //寻找优先级最高的元素及对应下标 if(data［i］<min) { min=data［i］; minIndex=i;

113 } //从minIndex起至size-2止，把后一个元素放在前一个元素位置上 //这样对优先级相同的元素将保持先进先出的顺序 for(i=minIndex;i<size-1;i++) //不同之处！ data［i］=data［i+1］; size--; //数据元素个数减1 returnmin; //返回优先级最高的元素 }

114 顺序优先级队列应用 对于前面我们讨论过的操作系统的进程管理问题，每一个进程的数据类型应包含任务号和优先级两个数据项，其定义如下： struct Datatype { int taskNo; int priority; };

115 当用如上定义的数据类型Datatype作用于顺序优先级队列类SeqPQueu时，出队列成员函数中的运算符小于（<）就要重载。操作符重载可以定义为成员函数，也可以定义为一般函数。若定义为一般函数，则可不改变已编译完成的顺序优先级队列类的定义和实现。关于操作符重载的方法讨论见1.3.3节。 intoperator<(constDatatype&a,constDatatype&b) { returna.priority<b.priority; }

116 例3―3 设计一个程序模仿操作系统的进程管理问题。进程服务按优先级级别顺序，进程服务请求放在数据文件task.dat中。程序如下：
＃include<fstream.h> structDatatype { inttaskNo; intpriority; }; //定义具体问题的数据类型Da

117 taty peintoperator<(constDatatype&a,constDatatype&b) //重载操作符< { returna.priority<b.priority; } ＃include"SeqPQueue.h" //包含顺序优先级队列类定义和实现 voidmain(void)

118 SeqPQueuemyPQueue; ifstreamfin; Datatypetask; fin.open("task.dat",ios::in|ios::nocreate); if(!fin) { cerr<<"不能打开文件task.dat!"<<endl; exit(1); } while(!fin.eof())

119 { fin>>task.taskNo; //文件方式读入taskNo项 fin>>task.priority; //文件方式读入priority项 myPQueue.PQInsert(task); //插入 } inti=1; cout<<"序号"<<"任务号"<<"优先级"<<endl; while(!myPQueue.PQueueEmpty()) cout<<i<<"";

120 task=myPQueue.PQDelete();
//依次把优先级最高的元素出队列 cout<<task.taskNo<<""; //输出显示 cout<<task.priority<<endl; //输出显示 i++; }}

121 设数据文件task.dat中存放的数据如下所示：
   

122 程序的输出为： 序号任务号优先级    

123 当考虑优先级相同元素的先进先出问题时,例3―3程序中的宏包含语句改为
＃include"SeqPQueue2.h“ 程序中的文件打开语句改为 fin.open("task2.dat",ios::in|ios::nocreate); 设数据文件task2.dat中存放的数据如下所示：    

124 注意：进程任务号2和进程任务号4的优先级相同，均为20。此时程序的输出为：
序号 任务号 优先级     

125 3.6 顺序存储结构的特点 顺序存储结构是数据结构中最基本、最常用、最重要的一种存储结构。顺序存储结构的最主要特征是逻辑上相邻的数据元素在物理上也相邻。向系统申请一片物理上相邻的存储空间的方法主要有两种：一种是静态数组方法，另一种是动态数组方法。静态数组方法是在程序编译时即分配数组元素空间的方法。本章讲述的顺序存储结构方法都是静态数组方法。动态数组方法是在程序运行时分配数组元素空间的方法，动态数组方法将在第5章讨论。

126 顺序存储结构的特点主要有： （1）使用简便。根据具体问题确定出所需最大数据元素个数后，只需定义一次，就可任意多次使用。 （2）可随机存取数据元素。如对顺序表中所有位置上的数据元素只要给出位置下标即可方便地存取该位置上的数据元素。

127 顺序存储结构也有使用不方便之处，主要表现在：
（1）数据元素最大个数需预先给定。当数据元素最大个数预先难以确定或变化较大时常常难以处理； （2）顺序表插入和删除时为保持数据元素的顺序需移动较多的数据元素。这在3.2.3节已作了分析，在顺序表中插入和删除一个数据元素的时间复杂度为O（n）。