C++课件第9章线性结构(guo20120509)

1、本章内容本章内容1. 1. 数据结构概述数据结构概述2. 2. 线性表线性表3. 3. 栈栈4. 4. 队列队列5. 5. 数组数组 数据：数据：计算机能够识别、存储和处理的符号的集合计算机能够识别、存储和处理的符号的集合 。 数据对象：数据对象：具有相同性质的数据元素集合。具有相同性质的数据元素集合。 数据元素：数据元素：数据的基本单位，由一个或多个数据项组成。又数据的基本单位，由一个或多个数据项组成。又称为结点、顶点、记录、表目等。称为结点、顶点、记录、表目等。 数据项：数据项：具有独立含义的数据的最小单位，又称为域、字段。具有独立含义的数据的最小单位，又称为域、字段。9.1 9.1 数据

2、结构概述数据结构概述数据结构：数据结构：数据对象中数据元素之间的结构关系数据对象中数据元素之间的结构关系n概念和术语概念和术语例：例：职工情况表职工情况表职工情况表是一种职工情况表是一种数据结构，数据结构，每个职工情况为一每个职工情况为一数据元素数据元素，职工的每项基本信息为一个职工的每项基本信息为一个数据项，数据项，部门的所有职工构成一部门的所有职工构成一个个数据对象数据对象。9.1 9.1 数据结构概述数据结构概述9.1 9.1 数据结构概述数据结构概述例：例：排队问题排队问题 Customer()Queue (B-1)Server () 逻辑结构：逻辑结构：排队方式，数据间的逻辑关系。排

3、队方式，数据间的逻辑关系。 存储结构：存储结构：计算机中队列的存储方法。计算机中队列的存储方法。 运算：运算：排队过程中各种操作的实现方法。排队过程中各种操作的实现方法。n 数据结构研究的主要内容：数据结构研究的主要内容：数据的逻辑结构、数据的逻辑结构、数据的存储结构、数据的运算数据的存储结构、数据的运算n 数据的逻辑结构：数据的逻辑结构：例：例：职工情况表职工情况表表尾元素 表头元素中间元素 数据的逻辑结构只抽象地反映出数据元素之间的数据的逻辑结构只抽象地反映出数据元素之间的逻辑关系逻辑关系，它与数据的存储无关，是它与数据的存储无关，是独立于计算机独立于计算机的。的。 9.1 9.1 数据结

4、构概述数据结构概述每个元素最多有一个直接前驱和一个直接后继，即为每个元素最多有一个直接前驱和一个直接后继，即为线性结构线性结构。n 数据逻辑结构的分类：数据逻辑结构的分类：1）集合结构：在集合结构中，数据元素之间的关系是集合结构：在集合结构中，数据元素之间的关系是“属于属于同一集合同一集合”，集合是元素关系极为松散的一种结构。，集合是元素关系极为松散的一种结构。例：例：2）线性结构：除第一个和最后一个元素外，其他每个元素）线性结构：除第一个和最后一个元素外，其他每个元素都仅有一个都仅有一个直接前驱元素直接前驱元素和一个和一个直接后继元素直接后继元素。例：例：9.1 9.1 数据结构概述数据结构

5、概述n 数据逻辑结构的分类：数据逻辑结构的分类：例：例：例：例：3）树形结构：每个元素若有直接前驱元素，只能有一个，但）树形结构：每个元素若有直接前驱元素，只能有一个，但可以有多个直接后继元素。可以有多个直接后继元素。 4）图形结构：每个元素都可以有多个直接前驱元素和多个直）图形结构：每个元素都可以有多个直接前驱元素和多个直接后继元素。接后继元素。 9.1 9.1 数据结构概述数据结构概述n 数据的存储结构：数据的存储结构：数据的存储结构是逻辑结构在计算机内存储器中的实现。数据的存储结构是逻辑结构在计算机内存储器中的实现。n 四种基本的存储映象方式：四种基本的存储映象方式：1）顺序方式顺序方式

6、2 2）链接方式链接方式3 3）索引方式索引方式4 4）散列方式散列方式继续继续9.1 9.1 数据结构概述数据结构概述 将数据元素按照某种顺序存放到一片将数据元素按照某种顺序存放到一片连续的存储单元连续的存储单元内，内，数据元素之间的逻辑关系是通过它们在存储器中的数据元素之间的逻辑关系是通过它们在存储器中的相对位置相对位置来来体现的。体现的。例：例：英语字母表的顺序存储。英语字母表的顺序存储。ABCXYZ9.1 9.1 数据结构概述数据结构概述顺序方式顺序方式顺序存储方式的优点是：顺序存储方式的优点是： 元素之间的逻辑关系通过它们在存储位置体现，因此存储密度高。元素之间的逻辑关系通过它们在存

7、储位置体现，因此存储密度高。 可以快速地确定出任意元素的存储位置，从而能够实现对元素的可以快速地确定出任意元素的存储位置，从而能够实现对元素的 随机、快速访问。随机、快速访问。顺序存储方式的缺点是：顺序存储方式的缺点是： 插入或删除元素时，可能会引起大量元素的移动，实现效率低。插入或删除元素时，可能会引起大量元素的移动，实现效率低。 存储空间需预先分配，如果定的太大会造成空间的浪费，定的太存储空间需预先分配，如果定的太大会造成空间的浪费，定的太 小又可能会发生溢出。小又可能会发生溢出。 逻辑上相邻的元素在物理位置上逻辑上相邻的元素在物理位置上未必未必相邻，元素间的逻辑相邻，元素间的逻辑关系由关

8、系由附加的附加的指针域表示。指针域表示。第一个职工情况第一个职工情况第二个职工情况第二个职工情况最后一个职工情况最后一个职工情况head例：例：职工情况链表（链接方式存储的线性结构）职工情况链表（链接方式存储的线性结构）9.1 9.1 数据结构概述数据结构概述链接方式链接方式链接存储方式的优点是：链接存储方式的优点是： 元素之间的逻辑关系通过结点的指针域指出，因此，在插入和删除元元素之间的逻辑关系通过结点的指针域指出，因此，在插入和删除元 素时，不会引起大量元素的移动。素时，不会引起大量元素的移动。 可动态申请和释放结点空间，所使用的存储空间大小与实际存储的数可动态申请和释放结点空间，所使用的

9、存储空间大小与实际存储的数 据元素的数量保持一致。据元素的数量保持一致。链接存储方式的缺点是：链接存储方式的缺点是： 不能实现对数据元素的随机访问。不能实现对数据元素的随机访问。 每个结点中的指针域会耗费一些存储空间。每个结点中的指针域会耗费一些存储空间。索引表索引表数据数据9.1 9.1 数据结构概述数据结构概述关键字关键字 地址地址索引方式索引方式关键字：关键字：是指能够惟一标识一个数据元素是指能够惟一标识一个数据元素的一个或多个数据的一个或多个数据 项。项。索引方式的优点是：检索速度快。索引方式的优点是：检索速度快。索引方式的缺点是：索引方式的缺点是：增加的索引表会占用较多的存储空间；增

10、加的索引表会占用较多的存储空间；在插入和删除数据元素时需要修改索引表，因而会花费更多的时间。在插入和删除数据元素时需要修改索引表，因而会花费更多的时间。 数据元素的存储位置是用它的关键字计算出来的。数据元素的存储位置是用它的关键字计算出来的。 散列方式存储的数据结构又称为哈希表、杂凑表等。散列方式存储的数据结构又称为哈希表、杂凑表等。 9.1 9.1 数据结构概述数据结构概述散列方式散列方式散列方式的优点是：检索、增加和删除元素的操作都很快。散列方式的优点是：检索、增加和删除元素的操作都很快。散列方式的缺点是：如果使用了不好的散列函数，可能会出现存储单元散列方式的缺点是：如果使用了不好的散列函

11、数，可能会出现存储单元的冲突，为解决冲突需要额外的时间和空间开销。的冲突，为解决冲突需要额外的时间和空间开销。n 数据的运算：数据的运算：对数据对象中的数据所进行的加工和处理。对数据对象中的数据所进行的加工和处理。n 数据运算的特点：数据运算的特点： 数据的运算定义在逻辑结构之上，实现在存储结构之上。数据的运算定义在逻辑结构之上，实现在存储结构之上。 数据运算的实现用数据运算的实现用算法算法描述。描述。n 常用的数据运算：常用的数据运算：插入、删除、查找、排序、更新等。插入、删除、查找、排序、更新等。9.1 9.1 数据结构概述数据结构概述1.什么是算法什么是算法 算法是对解决问题方法的精确描

12、述，是用来完成某个特算法是对解决问题方法的精确描述，是用来完成某个特定任务的有限步骤序列。定任务的有限步骤序列。 9.1 9.1 数据结构概述数据结构概述例如例如:用辗转相除法求两个正整数用辗转相除法求两个正整数M和和N的最大公因的最大公因数的算法为数的算法为: step1: 求求M除以除以N的余数的余数R; step2: 若若R=0,算法结束算法结束,即即N为为M和和N的最大公因数的最大公因数 Step3: 否则否则,置置MN,NR,返回返回step12. 算法的基本特征算法的基本特征有穷性有穷性 一个算法必须在执行有穷步后结束，并且一个算法必须在执行有穷步后结束，并且每一步都能在有限的时间

13、内完成。每一步都能在有限的时间内完成。确定性确定性 算法中的每一条指令必须具有确切的含义，算法中的每一条指令必须具有确切的含义，且无二义性。且无二义性。可行性可行性 算法中描述的所有操作都可以通过让已实算法中描述的所有操作都可以通过让已实现的基本运算执行有限次完成。现的基本运算执行有限次完成。输入输入 一个算法应该有个或多个输入。一个算法应该有个或多个输入。输出输出 一个算法应该有一个或多个输出。一个算法应该有一个或多个输出。3. 算法的描述算法的描述 4. 算法的评价算法的评价 自然语言描述、程序设计语言描述、流程图描述等。自然语言描述、程序设计语言描述、流程图描述等。以下采用以下采用C+语

14、言语言作为描述算法的工具作为描述算法的工具 1 1）算法的时间复杂度算法的时间复杂度：根据算法编写出的程序在计算机上：根据算法编写出的程序在计算机上 运行时所消耗的时间。运行时所消耗的时间。2 2）算法的空间复杂度算法的空间复杂度：根据算法编写出的程序在计算机上：根据算法编写出的程序在计算机上 运行时所需要的存储空间的大小。运行时所需要的存储空间的大小。9.1 9.1 数据结构概述数据结构概述n算法时间复杂度的度量算法时间复杂度的度量 一般把程序运行时一般把程序运行时语句的执行语句的执行次数（不包括说明语句）次数（不包括说明语句）作为估算程序执行时间的量度。作为估算程序执行时间的量度。 例：例

15、：估算以下函数的时间复杂度。估算以下函数的时间复杂度。int min( int a , int n ) int k,i; k=0; /执行执行 1 次次 for(i=1; in; i+) /执行执行 n 次次 if(aiak) k=i;/执行执行n-1次次 return k; /执行执行 1 次次语句执行频度：语句执行频度：f(n)=2n+1忽略低次项，记为：忽略低次项，记为： f(n)=O(n) 它与它与 n 成正比成正比n 常见的算法时间复杂度常见的算法时间复杂度O(1)、O(log2n)、O(n)、O(nlog2n)、O(n2)、O(n3) 、O(2n)n 时间函数的增长率时间函数的增长

16、率 9.1 9.1 数据结构概述数据结构概述 线性表是由（线性表是由（）个）个相同类型相同类型的数据元素的数据元素e e0 0、e e1 1、e en-1 n-1 组成的有限序列组成的有限序列 。可抽象的表示为：。可抽象的表示为：（e0，e1，ei-1，ei，ei+1，en-1） 开始元素开始元素 中间元素中间元素 终端元素终端元素建空表、求表长、查找、插入、删除、排序等。建空表、求表长、查找、插入、删除、排序等。9.2 9.2 线性表线性表1.线性表的定义线性表的定义 线性表中元素的个数称为表的线性表中元素的个数称为表的长度长度。长度为。长度为0的表为的表为空表空表。元素在表中的序号称做元素

17、的元素在表中的序号称做元素的下标下标。2. 线性表常用的基本运算线性表常用的基本运算 n 以顺序方式存储的线性表称为以顺序方式存储的线性表称为顺序表顺序表。n 可以用一维数组实现顺序表。可以用一维数组实现顺序表。例例：用用C+的一维数组实现对英文字母表的顺序存储。的一维数组实现对英文字母表的顺序存储。char table26;或：或： char *table=new char26; 应该把存储线性表的一维数组和实现顺序表各种运算的应该把存储线性表的一维数组和实现顺序表各种运算的函数封装在一起，即定义函数封装在一起，即定义顺序表类顺序表类。 9.2 9.2 线性表线性表继续继续n单击超链接查看以

18、下函数的实现：单击超链接查看以下函数的实现：构造函数构造函数 Find() Search() Insert() Delete() output() 重载重载“”的函数的函数9.2 9.2 线性表线性表#include class SeqListprivate:int Maxsize; /线性表的容量线性表的容量int length; /线性表的长度线性表的长度char *element; public: SeqList(int m=10); /构造函数构造函数 SeqList()delete element; /析构函数析构函数 bool IsEmpty()return length=0; /

19、判表是否为空判表是否为空 int Length()return length; /返回表长返回表长 bool Find(int i,char &x); /把下标为把下标为i的元的元SeqList:SeqList(int m) element=new charm; Maxsize=m; length=0;n函数的功能是：建立一个函数的功能是：建立一个空表空表。9.2 9.2 线性表线性表bool SeqList:Find(int i,char &x)if(ilength-1) return false;x=elementi;return true; n函数的功能是：把下标为函数的功能是：把下标为

20、i i的元素取至的元素取至x x。9.2 9.2 线性表线性表n函数的功能是：返回函数的功能是：返回x在表中的下标在表中的下标 。int SeqList:Search(const char &x) for(int i=0;ilength;i+)if(elementi=x) return i; return -1; 9.2 9.2 线性表线性表n函数的功能是：在下标函数的功能是：在下标i处插入元素处插入元素x 。bool SeqList:Insert(int i,const char &x) if(ilength) return false; /下标越界下标越界 if(length=Maxsiz

21、e) return false; /表已满表已满 for(int k=length-1;k=i;k-) elementk+1=elementk; elementi=x; length+; return true; 9.2 9.2 线性表线性表n函数的功能是：返回下标为函数的功能是：返回下标为i的元素至的元素至x，并删除之，并删除之 。bool SeqList:Delete(int i,char &x) if(Find(i,x)for(int k=i;klength-1;k+) elementk=elementk+1;length-;return true; else return false;

22、 9.2 9.2 线性表线性表n函数的功能是：输出表中所有元素的值函数的功能是：输出表中所有元素的值 。void SeqList:output(ostream &out)constfor(int i=0;ilength;i+)outelementi ;9.2 9.2 线性表线性表n函数的功能是：为方便输出，重载函数的功能是：为方便输出，重载“” 。ostream& operator(ostream &out,const SeqList &x)x.output(out);return out; 9.2 9.2 线性表线性表n 优点：优点： 1）存储密度高；）存储密度高； 2）可方便地访问给定下标

23、的元素。（随机存取）可方便地访问给定下标的元素。（随机存取） 顺序表的优缺点顺序表的优缺点n 缺点：缺点： 1）插入和删除运算的实现效率低。）插入和删除运算的实现效率低。 2）表的容量需预先指定，适应性差。）表的容量需预先指定，适应性差。n 顺序表适用于表长已知且插入和删除操作不频繁的线性表顺序表适用于表长已知且插入和删除操作不频繁的线性表9.2 9.2 线性表线性表例：例：将一串字符存入顺序表，删除其中所有的数字字符。将一串字符存入顺序表，删除其中所有的数字字符。 程序的输出结果是：程序的输出结果是： 1C+ 2FORTRAN 3PASCAL 4BASIC C+ FORTRAN PASCAL

24、 BASIC9.2 9.2 线性表线性表#include seqlist.hvoid main()char str=1C+ 2FORTRAN 3PASCAL 4BASIC SeqList L(100); /建空表建空表int i;for(i=0;stri!=0;i+)if(L.Insert(i,stri)=false)/向表中放数据向表中放数据 cout”插入异常插入异常n”;break;coutLendl; /利用重载的插入运算符输出表中元素利用重载的插入运算符输出表中元素i=0;char x ;while(iL.Length()n以链接方式存储的线性表称为链表。以链接方式存储的线性表称为链

25、表。n常用的链表形式有单链表、双链表和循环链表等常用的链表形式有单链表、双链表和循环链表等 。单链表的一般形式：单链表的一般形式：单链表中结点的一般形式：单链表中结点的一般形式：datanext在一般形式的单链表中进行插入、删除操作时，必须在一般形式的单链表中进行插入、删除操作时，必须针对不同的情况采取不同的处理方法，这为编写程序带来一定针对不同的情况采取不同的处理方法，这为编写程序带来一定的难度和潜在的危险。的难度和潜在的危险。 空表：空表：head=NULL9.2 9.2 线性表线性表9.2 9.2 线性表线性表 空表：空表：n 带头结点的单链表的一般形式：带头结点的单链表的一般形式： 单

26、链表的常用操作：单链表的常用操作：建空表、判表空、求表长、查找表中建空表、判表空、求表长、查找表中元素、插入元素、删除元素、清空表、输出表中元素等元素、插入元素、删除元素、清空表、输出表中元素等继续继续n 单击超链接查看以下函数的实现：单击超链接查看以下函数的实现：构造函数构造函数 析构函数析构函数 Find() Search() Insert() Delete() ClearList() output() 重载重载“”的函数的函数9.2 9.2 线性表线性表#include class Chain;/单链表类单链表类Chain的前视声明的前视声明class Node/单链表结点类的定义单链表

27、结点类的定义 friend class Chain;/定义类定义类Chain为友元为友元 private:char data;/结点的数据域结点的数据域 Node *next; /结点的指针域结点的指针域;class Chain /单链表类的定义单链表类的定义private:Node *head;/头指针头指针int length; /表长表长 public:Chain:Chain()head=new Node;head-next=0;length=0; n函数的功能是：建立一个函数的功能是：建立一个空表空表。9.2 9.2 线性表线性表 空表：空表：Chain:Chain()ClearLis

28、t(); /释放数据结点空间释放数据结点空间delete head; /释放头结点空间释放头结点空间 head=0; n函数的功能是：释放链表空间。函数的功能是：释放链表空间。9.2 9.2 线性表线性表n函数的功能是：把下标为函数的功能是：把下标为i的元素取至的元素取至x。9.2 9.2 线性表线性表bool Chain:Find(int i,char &x)if(ilength-1) return false;Node *p=head-next;int k=0; /指针指针p的移动次数的移动次数while(knext;k+;x=p-data;return true;n函数的功能是：返回函数

29、的功能是：返回x在表中的下标在表中的下标 。9.2 9.2 线性表线性表int Chain:Search(const char &x)Node *p=head-next;int i=0;while(p!=0)if(p-data=x) return i;p=p-next;i+;return -1;n函数的功能是：在下标函数的功能是：在下标i处插入元素处插入元素x 。ai-1ai p q x 插入过程演示插入过程演示9.2 9.2 线性表线性表a0head.bool Chain:Insert(int i,char &x)if(ilength) return false;/下标越界下标越界Node

30、*p=head; /从头结点开始从头结点开始int k=0;while(knext;k+;Node *q;n函数的功能是：返回下标为函数的功能是：返回下标为i的元素至的元素至x，并删除之，并删除之 。删除结点过程演示删除结点过程演示ai-1aiai+1 p q9.2 9.2 线性表线性表a0head.bool Chain:Delete(int i,char &x)if(ilength-1) return false;/下标越界下标越界Node *p=head; /从头结点开始从头结点开始for(int k=0;knext;Node *q=p-next; /保存要删除的结点地址保存要删除的结点地

31、址x=q-data; /保存删除结点的值保存删除结点的值p-next=q-next; /改变第改变第i-1个结点的指个结点的指n函数的功能是：把表清空，即将单链表置为空表函数的功能是：把表清空，即将单链表置为空表 。9.2 9.2 线性表线性表void Chain:ClearList()Node *p=head-next,*q;while(p!=0)q=p; /保存被删除结点地址保存被删除结点地址p=p-next; /p保存下一个待删除结点地址保存下一个待删除结点地址delete q; /释放被删除结点的空间释放被删除结点的空间head-next=0; length=0;n函数的功能是：输出表

32、中所有元素的值函数的功能是：输出表中所有元素的值 。void Chain:output(ostream &out)const Node *p=head-next; while(p!=0)outdatanext; 9.2 9.2 线性表线性表n函数的功能是：为方便输出，重载函数的功能是：为方便输出，重载“” 。ostream& operator(ostream &out,const Chain &x)x.output(out);return out;9.2 9.2 线性表线性表n 优点：优点： 1）插入和删除运算的实现效率比较高。）插入和删除运算的实现效率比较高。 2）在存储长度变化比较大的线性

33、表时适应性较好。）在存储长度变化比较大的线性表时适应性较好。 以链接方式存储线性表的优缺点以链接方式存储线性表的优缺点缺点：缺点： 1）需要增加额外的空间表示元素之间的逻辑关系。）需要增加额外的空间表示元素之间的逻辑关系。 2）不便于对线性表中元素进行随机存取。）不便于对线性表中元素进行随机存取。 链表适用于表长不确定且插入和删除操作频繁的线性表链表适用于表长不确定且插入和删除操作频繁的线性表9.2 9.2 线性表线性表例：例：将一字符串存入单链表，删除其中所有的数字字符。将一字符串存入单链表，删除其中所有的数字字符。 程序的输出结果是：程序的输出结果是： 1C+ 2FORTRAN 3PASC

34、AL 4BASIC C+ FORTRAN PASCAL BASIC9.2 9.2 线性表线性表#include chain.hvoid main()char str=1C+ 2FORTRAN 3PASCAL 4BASIC Chain L; /建立单链表对象，空表建立单链表对象，空表int i;for(i=0;stri!=0;i+)if(L.Insert(i,stri)=false) cout”插入异常插入异常n”; break; coutLendl; /输出表中元素输出表中元素i=0;char x;while(inext , *q; while( ) p = p - next; if( p=N

35、ULL) q= ; q-data=x; = head-next; head-next=q; else coutxnext , *q; while(p!=NULL&p-data!=x) p = p - next; if( p=NULL) q=new Node; q-data=x; q-next= head-next; head-next=q; else coutx已存在已存在!n; n单循环链表单循环链表n设置尾指针的单循环链表设置尾指针的单循环链表9.2 9.2 线性表线性表n双链表双链表n双循环链表双循环链表9.2 9.2 线性表线性表栈的概念（栈的概念（1）1.栈的定义栈的定义 3. 栈的

36、特点栈的特点 栈中元素的变化是栈中元素的变化是按按后进先出后进先出原则进行，因此又称栈原则进行，因此又称栈为为后进先出后进先出（Last In First Out，简称，简称LIFO）表）表 。 栈是限定只能在栈是限定只能在表的同一端表的同一端进行插入和删除运算的进行插入和删除运算的线性表线性表。9.3 9.3 栈栈2.栈的术语栈的术语 栈顶：栈顶：允许进行插入和删除的一端。允许进行插入和删除的一端。 栈底栈底：与栈顶相对的一端。与栈顶相对的一端。 入栈入栈：向栈顶插入一个元素。向栈顶插入一个元素。 出栈出栈：从栈顶取出一个元素。从栈顶取出一个元素。栈的入栈和出栈操作可以穿插进行，所以对应于相

37、同的入栈的入栈和出栈操作可以穿插进行，所以对应于相同的入栈序列其出栈序列可以有多种。栈序列其出栈序列可以有多种。例：例：设设A , B , C 三个元素依次进栈，则可能的出栈序列有：三个元素依次进栈，则可能的出栈序列有：栈的概念（栈的概念（2）9.3 9.3 栈栈A , B , C A , C , B B , A , C B , C , AC , B , A 不可能的出栈序列：不可能的出栈序列： C , A , B 4. 栈的基本运算：栈的基本运算：入栈、出栈、判栈空、取栈顶元素、置栈空入栈、出栈、判栈空、取栈顶元素、置栈空练习练习9.3 9.3 栈栈n 以顺序方式存储的栈称为以顺序方式存储的

38、栈称为顺序栈顺序栈。n 顺序栈可以用一维数组实现。顺序栈可以用一维数组实现。n 栈顶指示器（栈顶指示器（top）：指示当前栈顶位置）：指示当前栈顶位置 。n 栈容量（栈容量（Maxsize）：栈中最多可以存放的元素个数。）：栈中最多可以存放的元素个数。顺序栈（顺序栈（1）9.3 9.3 栈栈 A B C D E 0 1 2 3 4 . Maxsize-1top栈底栈底栈顶栈顶stack运算：运算：判栈空、判栈满、入栈、出栈、取栈顶元素、置栈空判栈空、判栈满、入栈、出栈、取栈顶元素、置栈空; 空栈：空栈：top=-1 栈满：栈满：top=Maxsize-1 9.3 9.3 栈栈n 字符型顺序栈类

39、的定义与实现：字符型顺序栈类的定义与实现：#include class SeqStackprivate: int top;/栈顶指示器栈顶指示器int Maxsize; /栈容量栈容量char * stack; public:SeqStack(int m=10)/构造函数，建立空栈构造函数，建立空栈 stack=new charm; /动态申请栈空间动态申请栈空间 Maxsize=m; top=-1; SeqStack()delete stack;/析构函数析构函数9.3 9.3 栈栈例：例：利用栈实现将一个非负的十进制整数转换为利用栈实现将一个非负的十进制整数转换为B（2B16)进进制整数。

40、制整数。#include seqstack.h /顺序栈类的定义和实现顺序栈类的定义和实现void Base_conversion(long x,int base)char digit=0123456789ABCDEF,remainder,ch; SeqStack stk; /缺省栈容量为缺省栈容量为10 int temp=x; while(temp!=0) remainder=digittemp%base; if(stk.Push(remainder)=false)cout”栈满栈满n”; temp/=base; coutx对应的对应的base进制数是：进制数是：; while(!stk.I

41、sEmpty() stk.Top(ch); coutch; stk.Pop(); 队列的概念（队列的概念（1）1.队列的定义队列的定义 2. 队列的特点队列的特点 队列中元素的变化是队列中元素的变化是按按先进先出先进先出原则进行，因此又称队原则进行，因此又称队为为先进先出先进先出（First In First Out，简称，简称FIFO）表）表 。 只能在只能在表的一端表的一端进行插入，而在另一端进行删除的进行插入，而在另一端进行删除的线性表线性表。9.4 9.4 队列队列3. 队列的基本运算队列的基本运算 入队、出队、判队空、判队满、取队头元素、置队空入队、出队、判队空、判队满、取队头元素、

42、置队空 顺序队列（顺序队列（1）9.4 9.4 队列队列n 以顺序方式存储的队称为以顺序方式存储的队称为顺序队顺序队。n 顺序队可以用一维数组实现。顺序队可以用一维数组实现。n 队头指示器（队头指示器（ front）：）：指示当前队头位置。指示当前队头位置。n 队尾指示器（队尾指示器（rear）：）：指示指示将要入队元素将要入队元素所在的位置。所在的位置。队列操作演示队列操作演示假溢出：假溢出：当队中还有空间可放数据，但不能执行入队操作。当队中还有空间可放数据，但不能执行入队操作。9.4 9.4 队列队列解决解决假溢出假溢出问题的三种方法问题的三种方法1）建立一个足够大的存储空间。）建立一个足

43、够大的存储空间。rear9.4 9.4 队列队列 C D 0 1 2 3 4frontE2）平移元素。）平移元素。3）循环队列方式循环队列方式。队头、队尾指针循环移动。队头、队尾指针循环移动。rear 1.入队、出队和取队头元素：入队、出队和取队头元素： 9.4 9.4 队列队列l入队：入队： elemrear=x; elemrear=x; rear=rear=（rear+1rear+1）%Maxsize%Maxsize; ;l出队：出队：front=front=（front+1front+1）%Maxsize%Maxsize; ;l取队头元素：取队头元素： x=elemfront;x=ele

44、mfront;l求队列长度：求队列长度：方法方法1：(Maxsize+rear-front)%Maxsize方法方法2：设一个计数变量：设一个计数变量(count),由入队和出队操作控制计数由入队和出队操作控制计数9.4 9.4 队列队列2.判队空和判队满的方法判队空和判队满的方法 循环队列队空时：循环队列队空时： front=rear 9.4 9.4 队列队列 0 1 2 3 4frontrear循环队列队满时：循环队列队满时： front=rear A B C D E 0 1 2 3 4frontrear9.4 9.4 队列队列2.判队空和判队满的方法判队空和判队满的方法 方法方法1： 利用利用front和和rear的值判断的值判断“队空队空”和和“队队满满”： 队空时：队空时： front=rear 9.