第七讲数据结构优秀课件.ppt

《第七讲数据结构优秀课件.ppt》由会员分享，可在线阅读，更多相关《第七讲数据结构优秀课件.ppt（78页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第七讲数据结构第1页，本讲稿共78页程序程序数据结构算法数据结构算法程序设计语言程序设计语言第2页，本讲稿共78页主要学习内容主要学习内容第一章、第一章、数据结构概述数据结构概述1、基本概念、基本概念2、逻辑结构与物理结构、逻辑结构与物理结构3、顺序存储与链式存储、顺序存储与链式存储第二章、线性结构第二章、线性结构线性表、栈、队列、数组线性表、栈、队列、数组第三章、非线性结构第三章、非线性结构树与二叉树树与二叉树第3页，本讲稿共78页第一章第一章数据结构概述数据结构概述一、数据结构的基本概念和术语一、数据结构的基本概念和术语一、数据结构的基本概念和术语一、数据结构的基本概念和术语1.1.数据数

2、据数据数据：对客观事物的符号表示，在计算机中是指所有能输：对客观事物的符号表示，在计算机中是指所有能输：对客观事物的符号表示，在计算机中是指所有能输：对客观事物的符号表示，在计算机中是指所有能输入到计算机中并被计算机程序处理的符号的总称。包括入到计算机中并被计算机程序处理的符号的总称。包括入到计算机中并被计算机程序处理的符号的总称。包括入到计算机中并被计算机程序处理的符号的总称。包括文字、符号、数字、图像、声音等。文字、符号、数字、图像、声音等。文字、符号、数字、图像、声音等。文字、符号、数字、图像、声音等。2.2.数据元素：数据元素：数据元素：数据元素：数据的基本单位，在计算机程序中通常作为

3、一个整体数据的基本单位，在计算机程序中通常作为一个整体数据的基本单位，在计算机程序中通常作为一个整体数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。进行考虑和处理。进行考虑和处理。进行考虑和处理。3.3.数据项：数据项：数据项：数据项：数据元素的组成部分。数据元素的组成部分。数据元素的组成部分。数据元素的组成部分。4.4.数据结构：数据结构：数据结构：数据结构：是相互之间存在一种或多种特定关系的数据元是相互之间存在一种或多种特定关系的数据元是相互之间存在一种或多种特定关系的数据元是相互之间存在一种或多种特定关系的数据元素的集合。数据结构包括三方面的内容：逻辑结构（从素的集合。数据

4、结构包括三方面的内容：逻辑结构（从素的集合。数据结构包括三方面的内容：逻辑结构（从素的集合。数据结构包括三方面的内容：逻辑结构（从具体问题抽象出来的数学模型）、存储结构（逻辑结构具体问题抽象出来的数学模型）、存储结构（逻辑结构具体问题抽象出来的数学模型）、存储结构（逻辑结构具体问题抽象出来的数学模型）、存储结构（逻辑结构在计算机存储器里的实现）、数据运算（检索、插入、在计算机存储器里的实现）、数据运算（检索、插入、在计算机存储器里的实现）、数据运算（检索、插入、在计算机存储器里的实现）、数据运算（检索、插入、删除、更新、排序等）。删除、更新、排序等）。删除、更新、排序等）。删除、更新、排序等）

5、。第4页，本讲稿共78页二、数据的逻辑结构和存储结构（物理结构）二、数据的逻辑结构和存储结构（物理结构）1.1.数据的逻辑结构：数据元素之间原本存在的逻数据的逻辑结构：数据元素之间原本存在的逻数据的逻辑结构：数据元素之间原本存在的逻数据的逻辑结构：数据元素之间原本存在的逻辑关系，称为数据的逻辑结构。它只是抽象辑关系，称为数据的逻辑结构。它只是抽象辑关系，称为数据的逻辑结构。它只是抽象辑关系，称为数据的逻辑结构。它只是抽象地反映数据元素之间的关系。地反映数据元素之间的关系。地反映数据元素之间的关系。地反映数据元素之间的关系。2.2.四种基本的数据结构（集合、线性结构、树形四种基本的数据结构（集合

6、、线性结构、树形四种基本的数据结构（集合、线性结构、树形四种基本的数据结构（集合、线性结构、树形结构、图状结构）。结构、图状结构）。结构、图状结构）。结构、图状结构）。第5页，本讲稿共78页3.3.数据的存储结构：数据的逻辑结构在计算机中的表示称为数据的存储结构：数据的逻辑结构在计算机中的表示称为数据的存储结构：数据的逻辑结构在计算机中的表示称为数据的存储结构：数据的逻辑结构在计算机中的表示称为数据的存储结构，又称物理结构。为将逻辑结构全面正数据的存储结构，又称物理结构。为将逻辑结构全面正数据的存储结构，又称物理结构。为将逻辑结构全面正数据的存储结构，又称物理结构。为将逻辑结构全面正确地在计算

7、机中表示出来，存储结构应包括数据元素自确地在计算机中表示出来，存储结构应包括数据元素自确地在计算机中表示出来，存储结构应包括数据元素自确地在计算机中表示出来，存储结构应包括数据元素自身的值和数据元素之间的关系两个方面。通常将数据元身的值和数据元素之间的关系两个方面。通常将数据元身的值和数据元素之间的关系两个方面。通常将数据元身的值和数据元素之间的关系两个方面。通常将数据元素在计算机中的表示称为结点，而将组成数据元素的数素在计算机中的表示称为结点，而将组成数据元素的数素在计算机中的表示称为结点，而将组成数据元素的数素在计算机中的表示称为结点，而将组成数据元素的数据项在计算机中的表示称为数据域。据

8、项在计算机中的表示称为数据域。据项在计算机中的表示称为数据域。据项在计算机中的表示称为数据域。第6页，本讲稿共78页4.两种基本的存储方法两种基本的存储方法（1 1）顺序存储方法（数组）。）顺序存储方法（数组）。）顺序存储方法（数组）。）顺序存储方法（数组）。顺序存储结构是把数据元素存储在一段连续顺序存储结构是把数据元素存储在一段连续顺序存储结构是把数据元素存储在一段连续顺序存储结构是把数据元素存储在一段连续的存储单元里，结点之间的关系由存储单元的邻的存储单元里，结点之间的关系由存储单元的邻的存储单元里，结点之间的关系由存储单元的邻的存储单元里，结点之间的关系由存储单元的邻接关系来直接或间接地

9、反映。接关系来直接或间接地反映。接关系来直接或间接地反映。接关系来直接或间接地反映。顺序存储结构的主要特点是：结点中只有自顺序存储结构的主要特点是：结点中只有自顺序存储结构的主要特点是：结点中只有自顺序存储结构的主要特点是：结点中只有自身信息域，没有连接信息域，因此存储密度大，身信息域，没有连接信息域，因此存储密度大，身信息域，没有连接信息域，因此存储密度大，身信息域，没有连接信息域，因此存储密度大，存储空间利用率高；存储空间是连续的，因而可存储空间利用率高；存储空间是连续的，因而可存储空间利用率高；存储空间是连续的，因而可存储空间利用率高；存储空间是连续的，因而可以通过计算机直接确定数据结构

10、中任意一个节点以通过计算机直接确定数据结构中任意一个节点以通过计算机直接确定数据结构中任意一个节点以通过计算机直接确定数据结构中任意一个节点的存储地址。的存储地址。的存储地址。的存储地址。第7页，本讲稿共78页（2 2）链式存储方法（指针）。）链式存储方法（指针）。）链式存储方法（指针）。）链式存储方法（指针）。链式存储结构就是借助指针来指示逻辑上相邻的链式存储结构就是借助指针来指示逻辑上相邻的数据元素在存储器中的物理位置。因此，可以把逻辑数据元素在存储器中的物理位置。因此，可以把逻辑上相邻的两个元素存放在物理上不相邻的存储单元中。上相邻的两个元素存放在物理上不相邻的存储单元中。链式存储结构的

11、主要特点是：结构中除自身信息外，链式存储结构的主要特点是：结构中除自身信息外，还有表示连接信息的指针域，因此比顺序结构的存储还有表示连接信息的指针域，因此比顺序结构的存储密度小，存储空间利用率低。存储空间可以是不连续密度小，存储空间利用率低。存储空间可以是不连续的，因而更适合动态数据的管理。的，因而更适合动态数据的管理。第8页，本讲稿共78页5.两种结构之间的关系：两种结构之间的关系：一般地，程序算法的设计取决于逻辑一般地，程序算法的设计取决于逻辑结构的设计，而算法的实现依赖于采用的存结构的设计，而算法的实现依赖于采用的存储结构。储结构。第9页，本讲稿共78页三、数据的运算三、数据的运算1.1

12、.概念：数据的运算是指对所定义的数据结构进行访问或操作。数据的运算是定概念：数据的运算是指对所定义的数据结构进行访问或操作。数据的运算是定概念：数据的运算是指对所定义的数据结构进行访问或操作。数据的运算是定概念：数据的运算是指对所定义的数据结构进行访问或操作。数据的运算是定义在数据的逻辑结构上的，但是运算的实现要在存储结构上进行。义在数据的逻辑结构上的，但是运算的实现要在存储结构上进行。义在数据的逻辑结构上的，但是运算的实现要在存储结构上进行。义在数据的逻辑结构上的，但是运算的实现要在存储结构上进行。2.2.几种基本运算：几种基本运算：几种基本运算：几种基本运算：插入：在数据结构的指定位置上增

13、添新的数据元素；插入：在数据结构的指定位置上增添新的数据元素；插入：在数据结构的指定位置上增添新的数据元素；插入：在数据结构的指定位置上增添新的数据元素；删除：删除数据结构中某个指定的数据元素；删除：删除数据结构中某个指定的数据元素；删除：删除数据结构中某个指定的数据元素；删除：删除数据结构中某个指定的数据元素；更新：改变数据结构中某个数据元素的值；更新：改变数据结构中某个数据元素的值；更新：改变数据结构中某个数据元素的值；更新：改变数据结构中某个数据元素的值；查找：在数据结构中寻找满足某个特定要求的数据元素；查找：在数据结构中寻找满足某个特定要求的数据元素；查找：在数据结构中寻找满足某个特定

14、要求的数据元素；查找：在数据结构中寻找满足某个特定要求的数据元素；排序：重新安排数据元素之间的逻辑顺序关系，使之按值由排序：重新安排数据元素之间的逻辑顺序关系，使之按值由排序：重新安排数据元素之间的逻辑顺序关系，使之按值由排序：重新安排数据元素之间的逻辑顺序关系，使之按值由小到大或小到大或小到大或小到大或由大到小的次序排列。由大到小的次序排列。由大到小的次序排列。由大到小的次序排列。从运算的性质来分，所有的运算可以分为两类：一类是加工型运算，从运算的性质来分，所有的运算可以分为两类：一类是加工型运算，从运算的性质来分，所有的运算可以分为两类：一类是加工型运算，从运算的性质来分，所有的运算可以分

15、为两类：一类是加工型运算，其运算改变了数据结构的值；另一类是引用型运算，其运算不改变数其运算改变了数据结构的值；另一类是引用型运算，其运算不改变数其运算改变了数据结构的值；另一类是引用型运算，其运算不改变数其运算改变了数据结构的值；另一类是引用型运算，其运算不改变数据结构，只对数据进行访问。据结构，只对数据进行访问。据结构，只对数据进行访问。据结构，只对数据进行访问。3.3.数据类型：一组具有相同特点的数据及这组数据上的运算，用数据类型数据类型：一组具有相同特点的数据及这组数据上的运算，用数据类型数据类型：一组具有相同特点的数据及这组数据上的运算，用数据类型数据类型：一组具有相同特点的数据及这

16、组数据上的运算，用数据类型来刻划。所谓数据类型是指一组值的集合及这个集合上的一组运算的来刻划。所谓数据类型是指一组值的集合及这个集合上的一组运算的来刻划。所谓数据类型是指一组值的集合及这个集合上的一组运算的来刻划。所谓数据类型是指一组值的集合及这个集合上的一组运算的总称。总称。总称。总称。第10页，本讲稿共78页第二章、线性结构第二章、线性结构第一节第一节第一节第一节 线性表线性表线性表线性表一、线性表的基本概念一、线性表的基本概念一、线性表的基本概念一、线性表的基本概念1.1.定义：线性结构是定义：线性结构是定义：线性结构是定义：线性结构是n(n=0)n(n=0)个结点的有穷序列。当个结点的

17、有穷序列。当个结点的有穷序列。当个结点的有穷序列。当n=0n=0时线性结构记为时线性结构记为时线性结构记为时线性结构记为()()或或或或，称为空表。设，称为空表。设，称为空表。设，称为空表。设n(n0)n(n0)个结点的线性结构表示成：个结点的线性结构表示成：个结点的线性结构表示成：个结点的线性结构表示成：(a1,a2,.,an)(a1,a2,.,an)，其中每个，其中每个，其中每个，其中每个aiai代表一个结点。代表一个结点。代表一个结点。代表一个结点。a1a1称为起始结点，称为起始结点，称为起始结点，称为起始结点，anan称为终端结点。称为终端结点。称为终端结点。称为终端结点。i i称为称

18、为称为称为aiai在线性表中的序号或位置。对任意一对相邻结点在线性表中的序号或位置。对任意一对相邻结点在线性表中的序号或位置。对任意一对相邻结点在线性表中的序号或位置。对任意一对相邻结点ai,ai+1(1=in)ai,ai+1(1=in)，aiai称称称称为为为为ai+1ai+1的直接前趋，的直接前趋，的直接前趋，的直接前趋，ai+1ai+1称为称为称为称为aiai的直接后继。线性表的逻辑结构是线性的直接后继。线性表的逻辑结构是线性的直接后继。线性表的逻辑结构是线性的直接后继。线性表的逻辑结构是线性结构。所含结点的个数称为表长。没有结点的表称为空表。结构。所含结点的个数称为表长。没有结点的表称

19、为空表。结构。所含结点的个数称为表长。没有结点的表称为空表。结构。所含结点的个数称为表长。没有结点的表称为空表。2.2.基本特征：基本特征：基本特征：基本特征：均匀性：同一结构的结点具有相同的特性均匀性：同一结构的结点具有相同的特性均匀性：同一结构的结点具有相同的特性均匀性：同一结构的结点具有相同的特性(数据项的个数相同，对应项的类型也相数据项的个数相同，对应项的类型也相数据项的个数相同，对应项的类型也相数据项的个数相同，对应项的类型也相同同同同)。有序性：除起始结点没有直接前趋外，其他结点有且只有一个直接前趋；有序性：除起始结点没有直接前趋外，其他结点有且只有一个直接前趋；有序性：除起始结点

20、没有直接前趋外，其他结点有且只有一个直接前趋；有序性：除起始结点没有直接前趋外，其他结点有且只有一个直接前趋；除终端结点没有直接后继外，其他结点有且只有一个直接后继。除终端结点没有直接后继外，其他结点有且只有一个直接后继。除终端结点没有直接后继外，其他结点有且只有一个直接后继。除终端结点没有直接后继外，其他结点有且只有一个直接后继。第11页，本讲稿共78页3.3.基本运算：设基本运算：设基本运算：设基本运算：设L=(a1,a2,.,ai,.,an)L=(a1,a2,.,ai,.,an)（1 1）初始化）初始化）初始化）初始化INI(L)INI(L)，结果是一个空表，结果是一个空表，结果是一个空

21、表，结果是一个空表L=L=。（2 2）求表长）求表长）求表长）求表长LEN(L)LEN(L)，结果是，结果是，结果是，结果是L L的长度。的长度。的长度。的长度。（3 3）读表元）读表元）读表元）读表元(按位查找按位查找按位查找按位查找)GET(L,i)GET(L,i)，结果是，结果是，结果是，结果是L L的第的第的第的第i i个个个个结点。结点。结点。结点。（4 4）定位）定位）定位）定位(按值查找按值查找按值查找按值查找)LOC(L,X)LOC(L,X)，若，若，若，若L L中至少有一个值为中至少有一个值为中至少有一个值为中至少有一个值为X X的的的的结点且序号最小的是结点且序号最小的是结

22、点且序号最小的是结点且序号最小的是i i，结果为，结果为，结果为，结果为i i；否则，结果为；否则，结果为；否则，结果为；否则，结果为0 0。（5 5）插入）插入）插入）插入INS(L,X,i)INS(L,X,i)，结果是，结果是，结果是，结果是L=(a1,.,ai-1,X,ai,.,an)L=(a1,.,ai-1,X,ai,.,an)（6 6）删除）删除）删除）删除DEL(L,i)DEL(L,i)，结果是，结果是，结果是，结果是L=(a1,.,ai-1,ai+1,.,an)L=(a1,.,ai-1,ai+1,.,an)第12页，本讲稿共78页二、线性表的顺序存储结构二、线性表的顺序存储结构顺

23、序存储结构是指用一组地址连续的存贮单元依次存储线性表的顺序存储结构是指用一组地址连续的存贮单元依次存储线性表的顺序存储结构是指用一组地址连续的存贮单元依次存储线性表的顺序存储结构是指用一组地址连续的存贮单元依次存储线性表的元素，通常用数组实现。数组的物理实现是一块连续的存储空元素，通常用数组实现。数组的物理实现是一块连续的存储空元素，通常用数组实现。数组的物理实现是一块连续的存储空元素，通常用数组实现。数组的物理实现是一块连续的存储空间，它是按首址（表中第间，它是按首址（表中第间，它是按首址（表中第间，它是按首址（表中第1 1个元素的地址）十位移来访问每一个元素的地址）十位移来访问每一个元素的

24、地址）十位移来访问每一个元素的地址）十位移来访问每一个元素的。设个元素的。设个元素的。设个元素的。设loc(ai)aloc(ai)a表中元素表中元素表中元素表中元素i i的内存地址（的内存地址（的内存地址（的内存地址（cidcid）；）；）；）；loc(bi,j)bloc(bi,j)b表中（表中（表中（表中（i i，j j）元素的内存地址（）元素的内存地址（）元素的内存地址（）元素的内存地址（c1id1c1id1，c2jd2c2jd2）；）；）；）；loc(ai)=loc(ai)=loc(ac)loc(ac)+(i-c)*la(i-c)*lalaatypelaatype类型的长度；类型的长度；

25、类型的长度；类型的长度；首址首址首址首址位移位移位移位移loc(bi,j)=loc(bi,j)=loc(bc1,c2)loc(bc1,c2)+(d2-c2+1)*(i-c1)+(j-c2)*lb(d2-c2+1)*(i-c1)+(j-c2)*lblbbtypelbbtype类类类类型的长度；型的长度；型的长度；型的长度；首址首址首址首址位移位移位移位移一维数组按照下标递增的顺序访问表中元素一维数组按照下标递增的顺序访问表中元素一维数组按照下标递增的顺序访问表中元素一维数组按照下标递增的顺序访问表中元素acacac+1ac+1adad二维数组按照先行后列的顺序访问表中元素二维数组按照先行后列的顺

26、序访问表中元素二维数组按照先行后列的顺序访问表中元素二维数组按照先行后列的顺序访问表中元素bc1,c2bc1,c2+1bc1,d2bi-1,d2bi,c2bd1,d2-bc1,c2bc1,c2+1bc1,d2bi-1,d2bi,c2bd1,d2-1bd1,d21bd1,d2第13页，本讲稿共78页例如例如例如例如varvara:array4.100ofintegera:array4.100ofinteger；b:array3.7,2.4ofrealb:array3.7,2.4ofreal；已知已知已知已知a4a4的地址为的地址为的地址为的地址为x x，b3b3，22的地址为的地址为的地址为的地

27、址为y y。按照上述公式。按照上述公式。按照上述公式。按照上述公式loc(a15)=loc(a15)=loc(a4)loc(a4)+(15-4)*2(15-4)*2=x+22integer=x+22integer类型的长度为类型的长度为类型的长度为类型的长度为2 2；首址首址首址首址位移位移位移位移loc(b5loc(b5,3)=3)=loc(b3loc(b3,2)2)+(4-2+1)*(5-3)+(3-2)*4=y+(3*2+1)*4=y+28(4-2+1)*(5-3)+(3-2)*4=y+(3*2+1)*4=y+28realreal的长度为的长度为的长度为的长度为6 6；在数组中，数据元素

28、的下标间接反映了数据元素的存储地址。计算机内存是随机在数组中，数据元素的下标间接反映了数据元素的存储地址。计算机内存是随机在数组中，数据元素的下标间接反映了数据元素的存储地址。计算机内存是随机在数组中，数据元素的下标间接反映了数据元素的存储地址。计算机内存是随机存取的装置，所以在数组中存取一个数据元素只要通过下标计算它的存储地存取的装置，所以在数组中存取一个数据元素只要通过下标计算它的存储地存取的装置，所以在数组中存取一个数据元素只要通过下标计算它的存储地存取的装置，所以在数组中存取一个数据元素只要通过下标计算它的存储地址就行了，数组中任意一个元素的存取时间都相等。从这个意义上说，数组址就行了

29、，数组中任意一个元素的存取时间都相等。从这个意义上说，数组址就行了，数组中任意一个元素的存取时间都相等。从这个意义上说，数组址就行了，数组中任意一个元素的存取时间都相等。从这个意义上说，数组的存储局势一个随机存取的结构。的存储局势一个随机存取的结构。的存储局势一个随机存取的结构。的存储局势一个随机存取的结构。各种操作（顺序表用数组实现，复习提问。）各种操作（顺序表用数组实现，复习提问。）各种操作（顺序表用数组实现，复习提问。）各种操作（顺序表用数组实现，复习提问。）链表操作用指针实现。链表操作用指针实现。链表操作用指针实现。链表操作用指针实现。第14页，本讲稿共78页第二节第二节栈栈5.15.

30、1栈栈栈栈栈是一种线性表，对它的插入和删除都限制地表的同一端进行。这一端叫做栈栈是一种线性表，对它的插入和删除都限制地表的同一端进行。这一端叫做栈栈是一种线性表，对它的插入和删除都限制地表的同一端进行。这一端叫做栈栈是一种线性表，对它的插入和删除都限制地表的同一端进行。这一端叫做栈的的的的“顶顶顶顶”，另一端则叫做栈的，另一端则叫做栈的，另一端则叫做栈的，另一端则叫做栈的“底底底底”。根据栈的定义，每次删除的总是当前根据栈的定义，每次删除的总是当前根据栈的定义，每次删除的总是当前根据栈的定义，每次删除的总是当前“最年轻最年轻最年轻最年轻”的表目，即最后插入的表目，的表目，即最后插入的表目，的表

31、目，即最后插入的表目，的表目，即最后插入的表目，而最先插入的表目则被放在栈的底部，要到最后才能删除。因此，栈又被而最先插入的表目则被放在栈的底部，要到最后才能删除。因此，栈又被而最先插入的表目则被放在栈的底部，要到最后才能删除。因此，栈又被而最先插入的表目则被放在栈的底部，要到最后才能删除。因此，栈又被称为称为称为称为“后进先出表后进先出表后进先出表后进先出表”（LIFOlastinputfirstoutputLIFOlastinputfirstoutput）或下推表。仿佛食堂）或下推表。仿佛食堂）或下推表。仿佛食堂）或下推表。仿佛食堂里的一叠盘子，每次只许一个一个地往上堆，一个一个地往下取。

32、里的一叠盘子，每次只许一个一个地往上堆，一个一个地往下取。里的一叠盘子，每次只许一个一个地往上堆，一个一个地往下取。里的一叠盘子，每次只许一个一个地往上堆，一个一个地往下取。通常栈可以用顺序的方式存储，分配一块连续的存储区域存放栈中的表目，并通常栈可以用顺序的方式存储，分配一块连续的存储区域存放栈中的表目，并通常栈可以用顺序的方式存储，分配一块连续的存储区域存放栈中的表目，并通常栈可以用顺序的方式存储，分配一块连续的存储区域存放栈中的表目，并用一个变量用一个变量用一个变量用一个变量t t指向当前栈顶（图）。指向当前栈顶（图）。指向当前栈顶（图）。指向当前栈顶（图）。第15页，本讲稿共78页第1

33、6页，本讲稿共78页假设栈中表目数的上限为假设栈中表目数的上限为假设栈中表目数的上限为假设栈中表目数的上限为mm，所有表目都具有同一类，所有表目都具有同一类，所有表目都具有同一类，所有表目都具有同一类型型型型stypestype，则可以用下列方式定义栈：，则可以用下列方式定义栈：，则可以用下列方式定义栈：，则可以用下列方式定义栈：ConstConstm=m=栈表目数的上限；栈表目数的上限；栈表目数的上限；栈表目数的上限；TypeTypestack=array1stack=array1mofstypemofstype；栈类型栈类型栈类型栈类型 VarVars:stack;s:stack;栈栈栈栈

34、 t t：integerinteger；栈顶指针栈顶指针栈顶指针栈顶指针 第17页，本讲稿共78页1.过程过程push(s，x，t)往栈往栈s中压入一中压入一个值为个值为x的表目的表目procedurepush(varsprocedurepush(vars：stackstack；x x：stypestype；vartvart：integer)integer)；beginbeginift=mthenwriteln(overflow)ift=mthenwriteln(overflow)上溢上溢上溢上溢 elsebegintt+1elsebegintt+1；stxstx；endend；elseels

35、exx入栈入栈入栈入栈 endend；PushPush第18页，本讲稿共78页2.函数函数pop(s，t)从栈中弹出一个从栈中弹出一个表目表目functionpop(vars：stack；vart：integer)：stype；beginift=0thenwriteln(underflow)下溢下溢elsebeginpopst；tt-1；end；else栈顶元素出栈栈顶元素出栈end；pop第19页，本讲稿共78页3函数函数top(s，t)读栈顶元素读栈顶元素functiontop(s：stack；t：integer)：stype；beginift=0thenwriteln(stackempt

36、y)elsetopst；返回栈顶元素返回栈顶元素end；top第20页，本讲稿共78页【竞赛试题】【竞赛试题】以下哪一个不是栈的基本运算以下哪一个不是栈的基本运算()(NOIP7)A)删除栈顶元素删除栈顶元素B)删除栈底的元素删除栈底的元素C)判断栈是否为空判断栈是否为空D)将栈置为空栈将栈置为空栈一个栈的输入顺序为一个栈的输入顺序为1、2、3、4、5，下列序列中可能是栈的，下列序列中可能是栈的输出序列是输出序列是()。(A)54312(B)2415(C)21543(D)1253若已知一个栈的入栈顺序是若已知一个栈的入栈顺序是1，2，3，n，其输出序，其输出序列为列为P1，P2，P3，Pn，若

37、，若P1是是n，则，则Pi是是()(NOIP7)A)iB)n-1C)n-i+1D)不确定不确定第21页，本讲稿共78页4、设有一个顺序栈、设有一个顺序栈S，元素，元素S1,S2,S3,S4,S5,S6依次进栈，依次进栈，如果如果6个元素的出栈顺序为个元素的出栈顺序为S2,S3,S4,S6,S5,S1，则顺序，则顺序栈的容量至少应为多少？栈的容量至少应为多少？A)3B)4C)5D)65、向顺序栈中压入新元素时，应当（、向顺序栈中压入新元素时，应当（）。）。A先移动栈顶指针，再存入元素先移动栈顶指针，再存入元素B先存入元素，再移动栈顶指针先存入元素，再移动栈顶指针C先后次序无关紧要先后次序无关紧要

38、D同时进行同时进行第22页，本讲稿共78页【例题【例题1】计算后缀表达式】计算后缀表达式所谓后缀表达式是指这样的一种表达式：式中不再引入括号，运算符放在两个运算对象之所谓后缀表达式是指这样的一种表达式：式中不再引入括号，运算符放在两个运算对象之所谓后缀表达式是指这样的一种表达式：式中不再引入括号，运算符放在两个运算对象之所谓后缀表达式是指这样的一种表达式：式中不再引入括号，运算符放在两个运算对象之后。所有计算按运算符出现的顺序，严格地由左而右进行（不再考虑运算符的优先规后。所有计算按运算符出现的顺序，严格地由左而右进行（不再考虑运算符的优先规后。所有计算按运算符出现的顺序，严格地由左而右进行（

39、不再考虑运算符的优先规后。所有计算按运算符出现的顺序，严格地由左而右进行（不再考虑运算符的优先规则）。例如则）。例如则）。例如则）。例如3*3*（5-25-2）+7+7对应的后缀表达式为对应的后缀表达式为对应的后缀表达式为对应的后缀表达式为335 52 2-*7-*7+其中其中其中其中为后缀表达式的结束标记，为后缀表达式的结束标记，为后缀表达式的结束标记，为后缀表达式的结束标记，为操作数的结束符。为操作数的结束符。为操作数的结束符。为操作数的结束符。335 52 2-*7-*7+=3=33 3*7*7+=9=97 7+=16=16 输入：输入：输入：输入：后缀表达式后缀表达式后缀表达式后缀表达

40、式A A（假定（假定（假定（假定A A合乎文法，不需判错）；合乎文法，不需判错）；合乎文法，不需判错）；合乎文法，不需判错）；输出：输出：输出：输出：表达式的值。表达式的值。表达式的值。表达式的值。第23页，本讲稿共78页题解题解n n设后缀表达式串为设后缀表达式串为设后缀表达式串为设后缀表达式串为A A。操作数和计算结果存放在栈。操作数和计算结果存放在栈。操作数和计算结果存放在栈。操作数和计算结果存放在栈s s中，中，中，中，s s的元素类型的元素类型的元素类型的元素类型stypestype为整型。计算过程如下：为整型。计算过程如下：为整型。计算过程如下：为整型。计算过程如下：n n由左而右

41、处理由左而右处理由左而右处理由左而右处理A A中的每一个字符。如遇到一个操作中的每一个字符。如遇到一个操作中的每一个字符。如遇到一个操作中的每一个字符。如遇到一个操作数，就送入数，就送入数，就送入数，就送入s s栈中保存；如遇到一个运算符，就从栈栈中保存；如遇到一个运算符，就从栈栈中保存；如遇到一个运算符，就从栈栈中保存；如遇到一个运算符，就从栈中取出栈顶的两个操作数进行计算，然后将计算结中取出栈顶的两个操作数进行计算，然后将计算结中取出栈顶的两个操作数进行计算，然后将计算结中取出栈顶的两个操作数进行计算，然后将计算结果重新压入栈中。依次类推，直至表达式最后一个果重新压入栈中。依次类推，直至表

42、达式最后一个果重新压入栈中。依次类推，直至表达式最后一个果重新压入栈中。依次类推，直至表达式最后一个运算符处理完毕，这时的栈顶元素值即为计算结果：运算符处理完毕，这时的栈顶元素值即为计算结果：运算符处理完毕，这时的栈顶元素值即为计算结果：运算符处理完毕，这时的栈顶元素值即为计算结果：第24页，本讲稿共78页n nvarvarn nss：stackstack；栈栈栈栈 n nAA：stringstring；后缀表达式后缀表达式后缀表达式后缀表达式 n ntt，i i，j j，kk：integerinteger；tt栈顶指针；栈顶指针；栈顶指针；栈顶指针；ii后缀表达式的字符指针；后缀表达式的字符

43、指针；后缀表达式的字符指针；后缀表达式的字符指针；k k、jj操作数值操作数值操作数值操作数值 n nbeginbeginn n读后缀表达式读后缀表达式读后缀表达式读后缀表达式A A；n ni1i1；t0t0；后缀表达式的字符指针和栈顶指针初始化后缀表达式的字符指针和栈顶指针初始化后缀表达式的字符指针和栈顶指针初始化后缀表达式的字符指针和栈顶指针初始化 n nwhileAidowhileAido若后缀表达式末处理完，则循环若后缀表达式末处理完，则循环若后缀表达式末处理完，则循环若后缀表达式末处理完，则循环 n nbeginbeginn ncaseAiofcaseAiofn n0099：begi

44、nbeginn nk0k0；n nrepeatrepeat从后缀表达式中取出操作数从后缀表达式中取出操作数从后缀表达式中取出操作数从后缀表达式中取出操作数kkn nk10*k+ord(Ai)-ord(0)k10*k+ord(Ai)-ord(0)；n nii+1ii+1；n nuntilAi=untilAi=；n npush(spush(s，k k，t)t)；操作数操作数操作数操作数k k压入栈中压入栈中压入栈中压入栈中 n nendend；0099n n+：push(spush(s，pop(spop(s，t)+pop(st)+pop(s，t)t)，t)t)；n n取出栈顶的两个操作数进行加法运

45、算，其和重新压入栈中取出栈顶的两个操作数进行加法运算，其和重新压入栈中取出栈顶的两个操作数进行加法运算，其和重新压入栈中取出栈顶的两个操作数进行加法运算，其和重新压入栈中 n n第25页，本讲稿共78页n n-：beginbegin取出栈顶的两个操作数进行减法运算，取出栈顶的两个操作数进行减法运算，取出栈顶的两个操作数进行减法运算，取出栈顶的两个操作数进行减法运算，n n其差重新压入栈中其差重新压入栈中其差重新压入栈中其差重新压入栈中 n njpop(sjpop(s，t)t)；n npush(spush(s，pop(spop(s，t)jt)j，t)t)；n nendend；-n n*：push

46、(spush(s，pop(spop(s，t)*pop(st)*pop(s，t)t)，t)t)；n n取出栈顶的两个操作数进行乘法运算，取出栈顶的两个操作数进行乘法运算，取出栈顶的两个操作数进行乘法运算，取出栈顶的两个操作数进行乘法运算，n n其积重新其积重新其积重新其积重新压入栈中压入栈中压入栈中压入栈中 n n/：beginbegin取出栈顶的两个操作数进行除法运算，取出栈顶的两个操作数进行除法运算，取出栈顶的两个操作数进行除法运算，取出栈顶的两个操作数进行除法运算，n n其商重新压入栈中其商重新压入栈中其商重新压入栈中其商重新压入栈中 n njpop(sjpop(s，t)t)；push(s

47、push(s，pop(spop(s，t)divjt)divj，t)t)；n nendend；/n nendend；casecasen nii+1ii+1；n nendend；whilewhilen nwriteln(pop(swriteln(pop(s，t)t)；endend；mainmainn n第26页，本讲稿共78页第三节第三节队列队列n n队列是不同于栈的另一种线性表。在日常生队列是不同于栈的另一种线性表。在日常生活中，无论是购物、订票或候车都有可能要排队。活中，无论是购物、订票或候车都有可能要排队。n n排队所遵循的原则是排队所遵循的原则是“先来先服务先来先服务”，后来者总是，后来者

48、总是加到队尾，排头者总是先离开队伍。加到队尾，排头者总是先离开队伍。n n队列就是从日常生活中的排队现象抽象出来的。队列就是从日常生活中的排队现象抽象出来的。所谓队列，就是允许在一端进行插入，在另一端所谓队列，就是允许在一端进行插入，在另一端所谓队列，就是允许在一端进行插入，在另一端所谓队列，就是允许在一端进行插入，在另一端进行删除的线性表。允许插入的一端称为队尾，进行删除的线性表。允许插入的一端称为队尾，进行删除的线性表。允许插入的一端称为队尾，进行删除的线性表。允许插入的一端称为队尾，通常用一个队尾指针通常用一个队尾指针通常用一个队尾指针通常用一个队尾指针r r指向队尾元素，即指向队尾元素

49、，即指向队尾元素，即指向队尾元素，即r r总是指总是指总是指总是指向最后被插入的元素；允许删除的一端称为队首，向最后被插入的元素；允许删除的一端称为队首，向最后被插入的元素；允许删除的一端称为队首，向最后被插入的元素；允许删除的一端称为队首，通常也用一个队首指针通常也用一个队首指针通常也用一个队首指针通常也用一个队首指针f f指向排头元素的前面。指向排头元素的前面。指向排头元素的前面。指向排头元素的前面。初始时初始时初始时初始时f=r=0f=r=0（如图）（如图）。第27页，本讲稿共78页 显然，在队列这种数据结构中，最先插入在元素将是最先被删除；反之最后插入显然，在队列这种数据结构中，最先插

50、入在元素将是最先被删除；反之最后插入的元素将最后被删除，因此队列又称为的元素将最后被删除，因此队列又称为“先进先出先进先出”（FIFOfirst in first out）的线性表。与栈相似，队列的顺序存储空间可以用一维数组）的线性表。与栈相似，队列的顺序存储空间可以用一维数组q1m模拟：模拟：3265419队列头队列头 F队列尾队列尾 R第28页，本讲稿共78页我们按照如下方式定义队列：我们按照如下方式定义队列：我们按照如下方式定义队列：我们按照如下方式定义队列：ConstConstm=m=队列元素的上限；队列元素的上限；队列元素的上限；队列元素的上限；TypeTypeequeue=arra