顺序存储结构的表、堆栈和队列.ppt

《顺序存储结构的表、堆栈和队列.ppt》由会员分享，可在线阅读，更多相关《顺序存储结构的表、堆栈和队列.ppt（81页珍藏版）》请在三一办公上搜索。

1、第3章 顺序存储结构的线性表、堆栈和队列,3.1 顺序存储结构3.2 表和顺序表 3.3 堆栈和顺序堆栈3.4 队列和顺序队列3.5 优先级队列和顺序优先级队列,3.1 顺序存储结构,计算机所处理的所有的数据都要存储在内存中。计算机高级语言系统对数据的存储结构有四种：顺序存储结构、链式存储结构、间接地址和仿真指针。其中，顺序存储结构和链式存储结构是两种最基本和最常用的存储结构。本节讨论顺序存储结构，其余三种存储结构依次在4.1节、5.2节和7.1节中讨论。,顺序存储结构是计算机中的一种最基本和最主要的数据存储结构。在顺序存储结构中，用户向系统申请一块地址连续的有限空间用于存储数据元素集合，这样

2、，任意两个在逻辑上相邻的数据元素在物理上也必然相邻。在C+中，向系统申请一块地址连续的有限空间的方法是使用数组。数组有静态数组和动态数组两种。不论是静态数组还是动态数组，其功能都是向系统申请一块地址连续的有限空间，只是使用的方法不同。,C+中静态数组向系统申请一块地址连续的有限空间的方法是使用数组定义语句“”。当程序运行超出该静态数组定义的范围时，系统自动回收该静态数组的地址空间。一个静态数组的例子如下：产生10个随机整数存放在一静态数组中，并输出？,当程序运行退出主函数时，系统将自动回收分配给静态数组temp的地址空间。C+中动态数组向系统申请一块地址连续的有限空间的方法是使用动态存储分配函

3、数。动态数组存储空间的回收方法是当不再需要该动态数组时，使用动态存储释放函数。C+中动态存储分配函数用new，动态存储释放函数用delete。new能自动计算要分配类型的空间大小并自动返回正确的指针类型。delete能自动释放由new分配的存储空间。,new的语法格式是：名字指针=new类型名(初始化值)。其中，初始化值可为空。new分配动态数组的语法格式是：名字指针=new类型名N。其中，N必须是有确定值的整数型常量或变量。delete的语法格式是：delete名字指针 delete释放动态数组的语法格式是：delete名字指针 将上例改为由动态数组实现？,从示例可知，静态数组存储空间的申请

4、和释放由系统自动完成，动态数组存储空间的申请和释放由用户通过调用系统函数完成。设要存储的数据元素为a0,a1,a2,a3,a4,a5，顺序存储结构（不论是用静态数组还是用动态数组）向系统申请了MaxSize个数据元素的存储空间，data为数组名，size为数组的当前存储位置，即数组元素个数。其内存结构示意图如图31所示。,图31 顺序存储结构内存结构示意图,3.2 线性表和顺序表,线性表（List）是一种可在任意位置进行插入和删除操作的由n（n0）个相同类型数据元素组成的线性结构。通常记为：(a1，a2，ai-1，ai，ai+1，an)其中n是表的长度，n=0的表称作空表。从数据元素之间的逻辑

5、关系来划分，数据结构可分为线性结构和非线性结构两种。线性结构是指数据元素之间的逻辑关系为除第一个元素和最后一个元素外，每个数据元素都只有一个前驱元素和一个后继元素。线性表是最简单的一种线性结构。线性表中相邻元素之间存在着顺序关系，将 ai-1 称为 ai 的直接前趋，ai+1 称为 ai 的直接后继。就是说：对于ai，当 i=2，.，n 时，有且仅有一个直接前趋 ai-1.，当i=1，2，.，n-1 时，有且仅有一个直接后继 ai+1，而 a1 是表中第一个元素，它没有前趋，an 是最后一个元素无后继。,对表的操作方法主要有初始化构造表、在表的某一位置插入一个元素、在表的某一位置删除一个元素、

6、定位某个数据元素在表中的存储位置、取表中某个存储位置的数据元素、判表是否为空等。用顺序存储结构存储的表称作顺序表（SequentList）。顺序表中任意数据元素的存取和访问可通过它的位置指针（即数组下标）来进行。,3.2.1 顺序表的类定义 综合前面的讨论可知，一个顺序表涉及的数据成员包括数组、数组的最大元素个数和当前数组元素的个数。顺序表的操作方法和前面讨论的表的操作方法相同，主要有初始化构造表、在表的某一位置插入一个元素、在表的某一位置删除一个元素、定位某个数据元素在表中的存储位置、取表中某个存储位置的数据元素、判表是否为空等。使用静态数组方法的顺序表的类定义如下：,class SeqLi

7、stprivate:Datatype dataMaxListSize;/抽象类型Datatype定义的数组 int size;/数据元素个数,public:SeqList(void);/构造函数 SeqList(void);/析构函数 int ListSize(void)const;/返回元素的个数size int ListEmpty(void)const;/表空返回1；否则返回0 void Insert(const Datatype,3.2.2 顺序表的类实现顺序表类SeqList的实现如下：/构造函数。置顺序表的数据元素个数size为0SeqList:SeqList(void)size=0

8、;/析构函数SeqList:SeqList(void)/返回顺序表的数据元素个数sizeint SeqList:ListSize(void)constreturn size;,/判顺序表空否，为空返回1；不空返回0int SeqList:ListEmpty(void)constif(size=0)return 1;else return 0;,/在指定位置pos插入一个数据元素itemvoid SeqList:Insert(const Datatype,if(possize)cout=pos;i+)datai+1=datai;datapos=item;/在pos位置插入item size+;/

9、数据元素个数size加1,/定位元素item的位置，返回值为item在顺序表中的位置；返回值为-1表示不存在int SeqList:Find(Datatype,/返回顺序表中位置pos上的元素。参数出错时退出Datatype SeqList:GetData(int pos)const if(possize-1)/取的元素序号必须在0至size-1之间 cout参数pos越界出错!endl;exit(0);return datapos;,/删除指定位置pos上的数据元素并返回Datatype SeqList:Delete(const int pos)if(size=0)coutsize-1)/删

10、除元素序号必须在0至size-1之间 cout参数pos越界出错!endl;exit(0);,Datatype temp=datapos;/从pos至size-2逐个元素左移,datasize-1移入datasize-2中 for(int i=pos+1;i=size-1;i+)datai-1=datai;size-;/数据元素个数size减1 return temp;Void SeqList:ClearList(void)Size=0;,3.2.3 一、顺序表上插入算法的效率分析 顺序表上的插入和删除是顺序表类中时间复杂度最高的成员函数。顺序表上的插入过程的图示如图所示：,19,11,21,

11、20,15,16,-,0,1,2,3,4,5,6,7,MaxListSize,-,1,data,19,11,21,13,20,15,16,-,0,1,2,3,4,5,6,7,MaxListSize,-,1,data,pos=3,size=6,Pos=3,Size=7,13,item,(,a,),插入一个数据元素,在顺序表中插入一个数据元素时，算法中时间复杂度最高的部分是循环移动数据元素。循环移动数据元素的效率和插入数据元素的位置pos有关，最坏情况是pos=0，需移动size个数据元素；最好情况是pos=size，需移动0个数据元素。设Pi是在第i个存储位置插入一个数据元素的概率，设顺序表中的

12、数据元素个数为n，当在顺序表的任何位置上插入数据元素的概率相等时，有Pi=1(n+1)，则向顺序表插入一个数据元素时所需移动的数据元素的平均次数为：,时间复杂度即为O（n）,二、顺序表上删除算法的效率分析,顺序表上的删除过程的图示如图所示：,Size=7,10,11,12,13,14,15,16,-,0,1,2,3,4,5,6,7,MaxListSize,-,1,data,10,11,12,14,15,16,-,0,1,2,3,4,5,6,7,MaxListSize-1,data,Pos=3,Size=6,13,temp,(,b,),删除一个数据元素,在顺序表中删除一个数据元素时，算法中时间复

13、杂度最高的部分也是循环移动数据元素。循环移动数据元素的效率和删除数据元素的位置pos有关，最坏情况是pos=0，需移动size-1个数据元素；最好情况是pos=size-1，需移动0个数据元素。设Qi是在第i个存储位置删除一个数据元素的概率，设顺序表中已有的数据元素个数为n，当在顺序表的任何位置上删除数据元素的概率相等时，有Qi=1/n，则向顺序表删除一个数据元素时所需移动的数据元素的平均次数为：,时间复杂度为O（n）,同样定位一个数据元素的时间复杂度为O（n），其余操作的时间复杂度则均为O（1）。,3.2.4 顺序表的应用 例31 编写一个程序向顺序表中插入5个整数值，然后以插入次序删除这5

14、个数。,思考：若向顺序表中依次插入5个字符，如何修改程序？,深化：若向顺序表中依次插入5个学生记录，如何修改程序？,3.3 堆栈和顺序堆栈,堆栈（Stack）是一种特殊的线性表，是一种只允许在表的一端进行插入和删除操作的线性表。堆栈中允许进行插入和删除操作的一端称为栈顶，另一端称为栈底。栈顶的当前位置是动态的，标识栈顶当前位置的称为栈顶指示器（或栈顶指针）。堆栈的插入和删除操作通常称为进栈或入栈，堆栈的删除操作通常称为出栈或退栈。当栈中没有数据元素时称之为空栈。,根据堆栈的定义，每次进栈的数据元素都放在原当前栈顶元素之前而成为新的栈顶元素，每次退栈的数据元素都是原当前栈顶元素，这样，最后进入堆

15、栈的数据元素总是最先退出堆栈，因此，堆栈也称作后进先出表。用顺序存储结构存储的堆栈称为顺序堆栈（SequentStack）。下图是一个顺序堆栈的动态示意图，图中，最大元素个数设为6，top为栈顶指示器。,data,5,4,3,2,1,0,top,a,),图34 顺序堆栈的动态示意图(b)插入数据元素A后；(c)插入数据元素B、C、D后；(d)删除数据元素D、C后；(e)删除数据元素B、A后,(,data,5,4,3,2,1,0,(,b,),A,top,data,5,4,3,2,1,0,top,(,c,),A,B,C,D,data,5,4,3,2,1,0,(,d,),data,5,4,3,2,1

16、,0,top,(,e,),top,A,B,思考：数据元素A、B、C依次进栈，则可能的出栈有几种？,3.3.1 顺序堆栈类定义和实现 1.直接类定义和实现方法 直接定义是指直接定义顺序堆栈类，方法如下：class SeqStack,private:Datatype dataMaxStackSize;/抽象类型Datatype的数组int top;/栈顶位置指示器public:SeqStack(void)/构造函数top=0;SeqStack(void)/析构函数;,int StackEmpty(void)const/堆栈空返回1；否则返回0return(top=0);int GetSize(vo

17、id)const/读栈元素个数topreturn top;void ClearStack(void)/清空堆栈使之为初始化状态top=0;void Push(const Datatype,/把元素item入栈；堆栈满时出错退出void SeqStack:Push(Datatype item)if(top=MaxStackSize)cout堆栈已满!endl;exit(0);datatop=item;top+;,/出栈并返回栈顶元素；堆栈空时出错退出Datatype SeqStack:Pop()if(top=0)cout堆栈已空!endl;exit(0);top-;/top先减1 return

18、datatop;/然后取top位置上的元素返回,/取栈顶元素返回Datatype SeqStack:Peek(void)if(top=0)cout堆栈空!endl;exit(0);return datatop-1;/top指在栈顶的下一个位置,取top-1上的元素返回,注意：栈顶位置指示器top和顺序表中的当前元素个数size的含义完全相同，只是在堆栈中用top更能反映它的栈顶位置指示器的含义，所以在此使用了不同的名字。此外，顺序堆栈中的数组data和顺序表中的数组data也完全相同。因此我们说，顺序堆栈和顺序表的逻辑结构完全相同，只是两者允许的操作集合不同，顺序表允许在任意位置插入和删除，而

19、顺序堆栈只允许在栈顶位置插入和删除，所以我们也可以说，顺序堆栈是操作受限制的顺序表。,2.继承类定义和实现方法 继承类定义指考虑顺序堆栈类数据成员对顺序表类数据成员继承性的定义。class SeqStack:private SeqListpublic:SeqStack(void);/构造函数SeqStack(void)/析构函数,int StackEmpty(void)const;/堆栈空返回1；否则返回0int GetSize(void)const;/读栈元素个数topvoid ClearStack(void);/清空堆栈使之为初始化状态void Push(const Datatype,/构

20、造函数SeqStack:SeqStack(void)SeqList();/判堆栈空否，空返回1；非空返回0int SeqStack:StackEmpty(void)constreturn ListEmpty();,/读栈元素个数sizeint SeqStack:GetSize(void)constreturn ListSize();/清空堆栈使之为初始化状态void SeqStack:ClearStack(void)ClearList();,/把元素item入栈;栈满时出错退出void SeqStack:Push(const Datatype,/出栈并返回栈顶元素;栈空时出错退出Datatyp

21、e SeqStack:Pop(void)if(ListSize()=0)cout堆栈已空!endl;exit(0);return Delete(ListSize()-1);,Datatype Peek(void)constif(ListSize()=0)cout堆栈已空!endl;exit(0);return GetData(ListSize()-1);,3.3.2 顺序堆栈应用1.求数制转换（M进制数转换N进制数）,*2.表达式计算:在机器内部，任何一个表达式都是由操作数、运算符和分界符组成的。操作数和运算符是表达式的主要部分，分界符标志了一个表达式的结束。我们称操作数、运算符和分界符为一个

22、表达式的单词。根据表达式的类型，表达式可分为三类，即算术表达式、关系表达式和逻辑表达式。为叙述简洁，我们仅讨论算术表达式的计算。算术表达式只包含加、减、乘、除、左括号和右括号。读者不难把他推广到其他类型表达式的计算中。假设计算机高级语言中的一个算术表达式为 A+(B-C/D)*E,这种算术表达式中的运算符总是出现在两个操作数之间（除单目运算符外），所以也称为中缀表达式。编译系统对中缀形式的算术表达式处理的方法是先把它转换为后缀形式的算术表达式。后缀形式的算术表达式就是表达式中的运算符出现在操作数之后，并且不含括号。例如，中缀算术表达式A+B的后缀表达式为AB+。要把一个中缀算术表达式变换成相应

23、的后缀表达式要考虑算术运算规则。算术四则运算的规则是：,（1）先乘除后加减；（2）先括号内后括号外；（3）同级别时先左后右。上面的中缀表达式写成满足四则运算规则的相应的后缀表达式即为 ABCD/-E*+,编译系统中表达式的计算分为两个步骤：（1）把中缀表达式变换成相应的后缀表达式；（2）根据后缀表达式计算表达式的值。表31给出了包括加、减、乘、除、左括号、右括号和分界符的算术运算符间的优先级关系表。表中，1代表栈顶运算符，2代表当前扫描读到的运算符。,表31 运算符优先级关系表,中缀表达式变换为后缀表达式的算法步骤是：（1）设置一个堆栈，初始时将栈顶元素置为“”。（2）顺序读入中缀表达式，当读

24、到的单词为操作数时就将其输出，并接着读下一个单词。（3）令x1为当前栈顶运算符的变量，x2为当前扫描读到运算符的变量，当顺序从中缀表达式中读入的单词为运算符时就赋予x2，然后比较x1的优先级与x2的优先级，若x1的优先级高于x2的优先级，将x1退栈并作为后缀表达式的一个单词输出，然后接着比较新的栈顶运算符x1的优先级与x2的优先级。,图35 中缀表达式变换成后缀表达式的过程,把中缀表达式变换成相应的后缀表达式后，计算后缀表达式的值的过程仍是一个堆栈应用问题。其算法思想是：设置一个堆栈存放操作数，从左到右依次扫描后缀表达式，每读到一个操作数就将其进栈；每读到一个运算符就从栈顶取出两个操作数施以该

25、运算符所代表的运算操作，并把该运算结果作为一个新的操作数入栈；此过程一直进行到后缀表达式读完，最后栈顶的操作数就是该后缀表达式的运算结果。计算后缀表达式值的算法我们将作为链式堆栈的应用例子在第4章中讨论。,3.4 队列和顺序队列,队列（Queue）也是一种特殊的线性表，是一种只允许在表的一端进行插入操作，在表的另一端进行删除操作的线性表。表中允许进行插入操作的一端称为队尾，允许进行删除操作的一端称为队头。队头和队尾分别由队头指示器（或称队头指针）和队尾指示器（或称队尾指针）指示。队列的插入操作通常称作入队列，队列的删除操作通常称作出队列。当队列中没有数据元素时称作空队列。,如图所示是一个有5

26、个元素的队列。入队的顺序依次为a1、a2、a3、a4、a5，出队时的顺序将依然是a1、a2、a3、a4、a5。根据队列的定义，每次进队列的数据元素都放在原来的队尾之后成为新的队尾元素，每次出队列的数据元素都是原来的队头元素。这样，最先入队列的数据元素总是最先出队列，所以队列也称作先进先出表。,用顺序存储结构存储的队列称作顺序队列（SequentQueue）。下图（a）是一个有6个存储空间的顺序队列的动态示意图。图中，front为队头指示器，rear为队尾指示器。,0,1,2,3,5,4,rear,front,(,a,),空队列,思考：顺序队列为空队列的条件是？（不是唯一的方法）,下图(b)表示

27、入队列数据元素A、B、C后的状态；图(c)表示出队列数据元素A、B后的状态；图(d)表示入队列数据元素D、E、F后的状态。,0,1,2,3,5,4,rear,front,(,b,),A,B,C,0,1,2,3,5,4,rear,front,(,c,),C,rear,front,思考：顺序队列为满队列的条件是？（不是唯一的方法）,对队列的操作主要有：初始化建立一个队列、入队列、出队列、取队头数据元素和判队列是否为空等操作。,3.4.1 顺序循环队列 对于顺序队列，从图(d)可以看出，此时若继续进行入队列操作将使队尾指示器rear的值超出顺序队列定义的6个存储空间的范围而“溢出”，但此时队列中还有

28、2个存储空间可供存储，因此，这时的“溢出”并不是由于存储空间不够而产生的溢出，这种溢出通常称作假溢出。由于存在假溢出问题，所以顺序队列很少在实际软件系统中使用。实际软件系统中使用的顺序队列基本都是这里要讨论的顺序循环队列。,顺序表的假溢出是由于“队尾入队头出”这种受限制的操作所造成，因此，解决的方法是把顺序队列所使用的存储空间构造成一个逻辑上首尾相连的循环队列。当rear和front达到MaxQueueSize-1后，再前进一个位置就自动到0，这可以利用求模（或称取余）运算（%）来实现。,如何判断顺序循环队列的队列满和队列空条件呢？首先，我们看顺序循环队列队头指示器front和队尾指示器rea

29、r的初始化值，设顺序循环队列的MaxQueueSize=6，令front=rear=0，其状态如图(a)所示:,顺序循环队列队空状态,当数据元素A、B、C、D、E、F入顺序循环队列后为满队列，如图（b），此时有front=rear=0。,顺序循环队列满状态,当数据元素A、B、C、D、E、F依次出队列后顺序循环队列空，此时有front=rear=0，其状态如图(c)所示。,可见，队列满和队列空的队头指示器front和队尾指示器rear的取值状态相同，这是无法区分的。解决的方法之一：通常是少用一个存储空间，以队尾指示器rear加1等于队头指示器front为队列满的条件(见下图)。即顺序循环队列的队

30、列满条件为(rear+1)%MaxQueueSize=front 顺序循环队列的队列空条件仍然为 rear=front,rear,0,1,2,3,5,4,front,(,b,),A,B,C,D,E,解决的方法之二：是附设一个存储队中元素个数的变量如count，当count=0时队空，当count=MaxQueueSize时为队满。,rear,0,1,2,3,5,4,front,A,B,C,D,E,F,3.4.2 顺序循环队列类的定义和实现 根据上面对顺序循环队列的分析，我们有顺序循环队列类的定义和实现如下：class SeqQueueprivate:Datatype dataMaxQueueS

31、ize;/抽象类型Datatype定义的数组,int front;/队头指示器int rear;/队尾指示器int count;/元素个数计数器public:SeqQueue(void)/构造函数 front=rear=0;count=0;SeqQueue(void);/析构函数 int QueueEmpty(void)const/判队列是否为空 return count=0;void ClearQueue(void)/清空队列 front=rear=0;count=0;int GetSize(void)const/取队列元素个数 return count;,void QInsert(cons

32、t Datatype,/把元素item入队列void SeqQueue:QInsert(const Datatype/计数器加1,Datatype SeqQueue:QDelete(void)Datatype temp;if(count=0)cout队列已空!endl;exit(0);temp=datafront;/保存原队头元素值front=(front+1)%MaxQueueSize;/队头指示器加1count-;/计数器减1return temp;/返回原队头元素,/读队头元素，队头元素由返回值带回Datatype SeqQueue:QFront(void)constif(count=0

33、)cout队列空!endl;exit(0);return datafront;/返回队头元素,上述文件名为SeqQueue.h。一个6个元素的顺序循环队列的入队列、出队列过程见下图。其中图（a）为初始状态，图（b）为入队列过程，图（c）为出队列过程。,0,1,2,3,5,4,front,(,a,),0,1,2,3,5,4,front,rear,(,b,),5,10,(,c,),rear,6,7,8,9,0,1,2,3,5,4,front,(,c,rear,3.4.3 顺序循环队列的应用 由于顺序循环队列和顺序队列结构近似，但顺序循环队列的功能大大优于顺序队列的功能，所以顺序队列几乎不被采用。顺

34、序循环队列的应用很广泛。例如，操作系统中的各种数据缓冲区的先进先出管理，应用系统中的各种事件排队管理，等等。这里我们讨论一个用顺序循环队列和顺序堆栈实现判断一个字符序列是否是回文的例子。,例32 编程序判断一个字符序列是否是回文(回文是指一个字符序列以中间字符为基准两边字符完全相同)。算法思想：从键盘输入一个字符序列存入字符串str中，字符串长度小于等于80，输入字符序列以回车换行符为结束标记，字符串str中不包括回车换行符。把字符串中字符逐个分别存入队列和堆栈，然后逐个出队列和退栈并比较出队列的元素和退栈的元素是否相等，若全部相等则该字符序列是回文，否则就不是回文。,#includetype

35、def char Datatype;/定义具体应用的数据类型Datatype#includeSeqQueue.h#includeSeqStack.hvoid main()SeqQueue queue1;SeqStack stack1;char str80;cout输入字符序列，回车换行符结束：endl;,cin.getline(str,80);int h=strlen(str);for(int i=0;ih;i+)queue1.QInsert(stri);stack1.Push(stri);while(!queue1.QueueEmpty()if(queue1.QDelete()!=stack

36、1.Pop()cout不是回文!endl;exit(0);cout是回文!endl;,第一次程序运行状态为：输入字符序列，回车换行符结束：ABCDEDCBA 字符序列是回文!,第二次程序运行状态为：输入字符序列，回车换行符结束：ABCDEDC 字符序列不是回文!判断一个字符序列是否是回文还有更简单的方法。这里的程序主要是为了举例说明顺序队列类和顺序堆栈类的使用方法。,3.6 顺序存储结构的特点,顺序存储结构是数据结构中最基本、最常用、最重要的一种存储结构。顺序存储结构的最主要特征是逻辑上相邻的数据元素在物理上也相邻。向系统申请一片物理上相邻的存储空间的方法主要有两种：一种是静态数组方法，另一种

37、是动态数组方法。静态数组方法是在程序编译时即分配数组元素空间的方法。本章讲述的顺序存储结构方法都是静态数组方法。动态数组方法是在程序运行时分配数组元素空间的方法，动态数组方法将在第5章讨论。,顺序存储结构的特点主要有：（1）使用简便。根据具体问题确定出所需最大数据元素个数后，只需定义一次，就可任意多次使用。（2）可随机存取数据元素。如对顺序表中所有位置上的数据元素只要给出位置下标即可方便地存取该位置上的数据元素。,顺序存储结构也有使用不方便之处，主要表现在：（1）数据元素最大个数需预先给定。当数据元素最大个数预先难以确定或变化较大时常常难以处理；（2）顺序表插入和删除时为保持数据元素的顺序需移动较多的数据元素。这在节已作了分析，在顺序表中插入和删除一个数据元素的时间复杂度为O（n）。,