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

《顺序存储结构的表堆栈和队列》由会员分享，可在线阅读，更多相关《顺序存储结构的表堆栈和队列（81页珍藏版）》请在金锄头文库上搜索。

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

2、基本和最主要的数据存储结构。在顺序存储结构中，用户向系统申请一块地址连续的有限空间用于存储数据元素集合，这样，任意两个在逻辑上相邻的数据元素在物理上也 必然相邻。在C+中，向系统申请一块地址连续的有限空间的方法是使用数组。数组有静态数组和动态数组两种。不论是静态数组还是动态数组，其功能都是向系统申请一块地址连续的有限空间，只是使用的方法不同。第3章 顺序存储结构的表、堆栈和队列C+中静态数组向系统申请一块地址连续的有限空间的方法是使用数组定义语句“”。当程序运行超出该静态数组定义的范围时，系统自动回收该静态数组的地址空间。一个静态数组的例子如下：产生10个随机整数存放在一静态数组中，并输出？第

3、3章 顺序存储结构的表、堆栈和队列当程序运行退出主函数时，系统将自动回收分配给静态数组temp的地址空间。C+中动态数组向系统申请一块地址连续的有限空间的方法是使用动态存储分配函数。动态数组存储空间的回收方法是当不再需要该动态数组时，使用动 态存储释放函数。C+中动态存储分配函数用new，动态存储释放函数用delete。new能自动计算要分配类型的空间大小并自动返回正确的指针类型。delete能自动释放由new分配的存储空间。第3章 顺序存储结构的表、堆栈和队列new的语法格式是：名字指针=new类型名(初始化值)。其中，初始化值可为空。new分配动态数组的语法格式是：名字指针=new类型名N

4、。其中，N必须是有确定值的整数型常量或变量。delete的语法格式是：delete名字指针delete释放动态数组的语法格式是：delete名字指针将上例改为由动态数组实现？ 第3章 顺序存储结构的表、堆栈和队列从示例可知，静态数组存储空间的申请和释放由系统自动完成，动态数组存储空间的申请和释放由用户通过调用系统函数完成。设要存储的数据元素为a0,a1,a2,a3,a4,a5，顺序存储结构（不论是用静态数组还是用动态数组）向系统申请了 MaxSize个数据元素的存储空间，data为数组名，size为数组的当前存储位置，即数组元素个数。其内存结构示 意图如图31所示。第3章 顺序存储结构的表、堆

5、栈和队列图31 顺序存储结构内存结构示意图 第3章 顺序存储结构的表、堆栈和队列3.2 线性表和顺序表 线性表（List）是一种可在任意位置进行插入和删除操作的由n （n0）个相同类型数据元素组成的线性结构。通常记为：(a1，a2， ai-1，ai，ai+1，an)其中n是表的长度，n=0的表称作空表。从数据元素之间的逻辑关系来划分，数据结构可分为线性结构和非线性结构两种。线性结构 是指数据元素之间的逻辑关系为除第一个元素和最后一个元素外，每 个数据元素都只有一个前驱元素和一个后继元素。线性表是最简单的一种线性结构。线性表中相邻元素之间存在 着顺序关系，将 ai-1 称为 ai 的直接前趋，a

6、i+1 称为 ai 的直接后继。就 是说：对于ai，当 i=2，.，n 时，有且仅有一个直接前趋 ai-1.，当i=1 ，2，.，n-1 时，有且仅有一个直接后继 ai+1，而 a1 是表中第一个元 素，它没有前趋，an 是最后一个元素无后继。第3章 顺序存储结构的表、堆栈和队列对表的操作方法主要有初始化构造表、在表的某一位置插入一个元素、在表的某一位置删除一个元素、定位某个数据元素在表中的存储位置、取表中某个存储位置的数据元素、判表是否为空等。用顺序存储 结构存储的表称作顺序表（SequentList）。顺序表中任意数据元素的存取和访问可通过它的位置指针（即数组下标）来进行。第3章 顺序存储

7、结构的表、堆栈和队列3.2.1 顺序表的类定义综合前面的讨论可知，一个顺序表涉及的数据成员包括数组、数组的最大元素个数和当前数组元素的个数。顺序表的操作方法和前面讨论的表的操作方法相同，主要有初始化构造表、在表的某一位置插入一个元素、在表的某一位置删除一个元素、定位某个数据元素在表中的存储位置、取表中某个存储位置的数据元素、判表是否为空等。使用静态数组方法的顺序表的类定义如下： 第3章 顺序存储结构的表、堆栈和队列class SeqListprivate:Datatype dataMaxListSize; /抽象类型Datatype定义的数组int size;/数据元素个数第3章 顺序存储结构

8、的表、堆栈和队列public:SeqList(void); /构造函数SeqList(void); /析构函数int ListSize(void)const; /返回元素的个数sizeint ListEmpty(void)const; /表空返回1；否则返回0void Insert(const Datatype/在位置pos插入元素itemint Find(Datatype /返回元素item在表中的位置Datatype GetData(int pos)const; /返回位置pos的元素Datatype Delete(const int pos); /删除位置pos的元素并返回 void C

9、learList(void); /把表清空; 第3章 顺序存储结构的表、堆栈和队列3.2.2 顺序表的类实现顺序表类SeqList的实现如下：/构造函数。置顺序表的数据元素个数size为0SeqList:SeqList(void)size=0;/析构函数SeqList:SeqList(void)/返回顺序表的数据元素个数sizeint SeqList:ListSize(void)constreturn size; 第3章 顺序存储结构的表、堆栈和队列/判顺序表空否，为空返回1；不空返回0int SeqList:ListEmpty(void)constif(size=0)return 1;els

10、e return 0;第3章 顺序存储结构的表、堆栈和队列/在指定位置pos插入一个数据元素itemvoid SeqList:Insert(const Datatypeif(size=MaxListSize)coutsize)cout=pos;i+)datai+1=datai;datapos=item;/在pos位置插入itemsize+;/数据元素个数size加1第3章 顺序存储结构的表、堆栈和队列/定位元素item的位置，返回值为item在顺序表中的位置；返回值为-1表示不存在int SeqList:Find(Datatypeint i=0;while(item!=datai/定义具体应用

11、的数据类型Datatype#include“SeqQueue.h“#include“SeqStack.h“void main()SeqQueue queue1;SeqStack stack1;char str80;cout“输入字符序列，回车换行符结束：“endl;第3章 顺序存储结构的表、堆栈和队列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 ()!=st

12、ack1.Pop ()cout“不是回文!“endl;exit(0);cout“是回文!“endl;第3章 顺序存储结构的表、堆栈和队列第一次程序运行状态为：输入字符序列，回车换行符结束：ABCDEDCBA字符序列是回文!第3章 顺序存储结构的表、堆栈和队列第二次程序运行状态为：输入字符序列，回车换行符结束：ABCDEDC字符序列不是回文!判断一个字符序列是否是回文还有更简单的方法。这里的程序主要是为了举例说明顺序队列类和顺序堆栈类的使用方法。第3章 顺序存储结构的表、堆栈和队列3.6 顺序存储结构的特点 顺序存储结构是数据结构中最基本、最常用、最重要的一种存储结构。顺序存储结构的最主要特征是

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