数据结构全册配套完整精品课件.ppt

1、数据结构全册配套完整精品课件 23:06 23:06 2 数数 据据 结结 构构 （第一章第一章 概述概述） Data Structures 23:06 3 第一章第一章 概概 述述 主要内容主要内容 1.1 研究内容 1.2 术语 1.3 算法及其描述 1.4 算法分析 23:06 4 1.1 研究内容 o 数据结构课程的研究内容：数据结构课程的研究内容： n 软件设计中常用的基本技术软件设计中常用的基本技术 包括哪些基本技术？包括哪些基本技术？ o 下面从采用计算机来解决实际问题的过程中所涉及下面从采用计算机来解决实际问题的过程中所涉及 到的各步骤中的相关技术来对此作一分析：到的各步骤中的

2、相关技术来对此作一分析： o 在用计算机解决实际问题时，在用计算机解决实际问题时， 一般要经过以下几个步骤：一般要经过以下几个步骤： n 首先，对具体问题首先，对具体问题抽象出数学模型抽象出数学模型， n 然后针对数学模型然后针对数学模型设计出求解算法设计出求解算法， n 选择或设计合适的选择或设计合适的数据结构数据结构存储相关数据，存储相关数据， n 最后最后编出程序编出程序上机调试，直至得到最终的解答。上机调试，直至得到最终的解答。 o 下面简述各环节的有关内容。下面简述各环节的有关内容。 23:06 5 1.1 研究内容 问题求解之一：问题建模问题求解之一：问题建模： o 一般情况下，实

3、际应用问题可能会各式各样，例如：一般情况下，实际应用问题可能会各式各样，例如： 我们所熟悉的工资表的处理问题，学生成绩管理问题，我们所熟悉的工资表的处理问题，学生成绩管理问题， 电话号码查询，数据加密、压缩问题等。电话号码查询，数据加密、压缩问题等。 o 这些问题中，无论是所涉及到的这些问题中，无论是所涉及到的数据数据，还是其，还是其操作操作要求，要求， 都可能存在一定的都可能存在一定的差异差异。 尽管如此，许多问题间还是具有一定尽管如此，许多问题间还是具有一定相似之处相似之处的。例如：的。例如： n虽然工资表和学生成绩表的具体信息（栏目）不同，虽然工资表和学生成绩表的具体信息（栏目）不同，

4、但如果将两个表中的每个人的但如果将两个表中的每个人的工资信息工资信息和和成绩信息成绩信息分别看作一分别看作一 个整体，则这两个个整体，则这两个表结构之间表结构之间就有了某些共性。就有了某些共性。 n从从操作方面操作方面来看，虽然对这两种表的操作存在差异，来看，虽然对这两种表的操作存在差异， 但也存在一些相同或相似的基本操作。但也存在一些相同或相似的基本操作。 例如，查询一个人的工资信息和成绩信息，修改有关信息等。例如，查询一个人的工资信息和成绩信息，修改有关信息等。 23:06 6 1.1 研究内容 o正因为许多不同的问题之间存在着的某些共性，正因为许多不同的问题之间存在着的某些共性， 可以将

5、一个具体问题用这些共性的形式描述出来可以将一个具体问题用这些共性的形式描述出来 -问题建模问题建模。 o问题建模通常问题建模通常包括包括： 所描述问题中的数据对象的集合；所描述问题中的数据对象的集合； 对象间关系及其描述；对象间关系及其描述； 问题求解的要求及方法等。问题求解的要求及方法等。 o建立问题模型的建立问题模型的好处好处： n通过建立模型，就可以将一个具体的问题转换为所熟悉的模型，然后通过建立模型，就可以将一个具体的问题转换为所熟悉的模型，然后 借助于这一模型来实现。借助于这一模型来实现。 n数据结构、离散数学及许多数学课程中就介绍了许多模型。例如：数据结构、离散数学及许多数学课程中

6、就介绍了许多模型。例如： o要描述一个群体中个体之间的关系时，可以采用要描述一个群体中个体之间的关系时，可以采用”数据结构数据结构”和和” 离散数学离散数学”中所介绍的中所介绍的图结构图结构。 o要描述一个工程内的关系或进展情况时，我们可以采用要描述一个工程内的关系或进展情况时，我们可以采用”数据结数据结 构构”中所介绍的中所介绍的AOV网或网或AOE网等。网等。 n即使所建立的模型没有现成的求解方法，借助于已有的模型的适当组即使所建立的模型没有现成的求解方法，借助于已有的模型的适当组 合也相对易于构造求解方法。合也相对易于构造求解方法。 23:06 7 1.1 研究内容 问题求解之二：问题求

7、解之二：构造求解算法构造求解算法 o通过问题建模，将一个具体的问题转换成一个用模型所描述的抽通过问题建模，将一个具体的问题转换成一个用模型所描述的抽 象的问题。象的问题。 o借助于这一模型以及已有的知识借助于这一模型以及已有的知识 （例如数据结构中有关图结构的基本知识），（例如数据结构中有关图结构的基本知识）， 可以相对容易地描述出原问题的求解方法，即可以相对容易地描述出原问题的求解方法，即算法算法。 算法设计过程中可能会涉及到算法设计过程中可能会涉及到多种技术多种技术， 例如：递归、分治法等。例如：递归、分治法等。 需要更多地实践。需要更多地实践。 算法设计是计算机专业的核心能力，算法设计是

8、计算机专业的核心能力， 是区别于其他专业的最核心能力之一。是区别于其他专业的最核心能力之一。 o从某种意义上说，该算法不仅能实现原问题的求解，从某种意义上说，该算法不仅能实现原问题的求解， 而且还可能实现许多类似的具体问题的求解，而且还可能实现许多类似的具体问题的求解， 尽管这些具体问题的背景及其描述形式可能存在较大的差异。尽管这些具体问题的背景及其描述形式可能存在较大的差异。 23:06 8 1.1 研究内容 问题求解之三：问题求解之三：选择或设计存储结构选择或设计存储结构 o 在构造出求解算法之后，需要考虑在计算机上实现求解了。在构造出求解算法之后，需要考虑在计算机上实现求解了。 为此，需

9、要做两方面的工作：为此，需要做两方面的工作： n选择或设计合适的存储结构，选择或设计合适的存储结构， 以便将问题所涉及到的数据存储到计算机中。以便将问题所涉及到的数据存储到计算机中。 （这包括数据中的基本对象及对象之间的关系）（这包括数据中的基本对象及对象之间的关系） 不同的存储形式对问题的求解实现有较大的影响，不同的存储形式对问题的求解实现有较大的影响， 所占用的存储空间也可能有较大的差异。所占用的存储空间也可能有较大的差异。 n设计程序，实现问题求解。设计程序，实现问题求解。 存储形式和问题要求决定了程序设计的方法。存储形式和问题要求决定了程序设计的方法。 另外，另外，程序设计环境程序设计

10、环境（如（如VC）的熟练掌握也是本课程的学习）的熟练掌握也是本课程的学习 过程中需要注意的教学目标之一。过程中需要注意的教学目标之一。 23:06 9 1.1 研究内容 问题求解之四：问题求解之四：测试测试 如何认定所设计的算法及程序能正确实现预定的功能和目标？如何认定所设计的算法及程序能正确实现预定的功能和目标？ o 理论证明：理论证明： n这是计算机科学领域曾经开展过的工作。这是计算机科学领域曾经开展过的工作。 n由于算法和程序的复杂性急剧增长，因而由于算法和程序的复杂性急剧增长，因而难以实用难以实用。 o 测试：通过对所开发的系统或模块，运行给定的测试数据，测试：通过对所开发的系统或模块

11、，运行给定的测试数据， 以发现存在的错误，而不是证明其正确。以发现存在的错误，而不是证明其正确。 n这是当前软件开发领域普遍采用方法，通常要占系统开发这是当前软件开发领域普遍采用方法，通常要占系统开发40 以上的工作量。详细描述可参考以上的工作量。详细描述可参考“软件工程软件工程”相关的描述。相关的描述。 n所设计的算法和程序，需要经过充分的测试才能交付使用。所设计的算法和程序，需要经过充分的测试才能交付使用。 n对程序的对程序的测试态度测试态度反映出学生的反映出学生的治学态度治学态度： o 如果是认真、负责的态度，就会认识到，如果是认真、负责的态度，就会认识到，任何设计都难免任何设计都难免

12、有疏漏有疏漏，或者，或者受环境受环境的影响。因而需要高度重视。的影响。因而需要高度重视。 n对程序的对程序的测试设计也测试设计也反映出学生的反映出学生的治学能力治学能力： o 如何设计测试用例？需要依据多种方法、策略和实践。如何设计测试用例？需要依据多种方法、策略和实践。 23:06 10 1.1 研究内容 问题求解的过程框架：问题求解的过程框架： 实际问题 求解算法测试 程序设计 数据结构组织 数据结构课程中的内容数据结构课程中的内容 数学模型 抽象 构造求解算法 数据结构设计 程序实现 数据结构：计算机类专业核心课程之一数据结构：计算机类专业核心课程之一 23:06 11 1.2 术语 下

13、面介绍课程中所涉及到的一些术语下面介绍课程中所涉及到的一些术语 o数据（数据（data） 能够输入到计算机中，并能被计算机处理的能够输入到计算机中，并能被计算机处理的 符号的集合。符号的集合。 n例如，工资表，学生成绩，电话号码簿，电子字典，例如，工资表，学生成绩，电话号码簿，电子字典， 编号编号姓姓 名名 基本基本 工资工资 奖金奖金 工资表示例工资表示例 学号学号姓姓 名名 考试考试 成绩成绩 备注备注 学生成绩表示例学生成绩表示例 *工资表工资表 *班级班级 *课程课程 成绩表成绩表 23:06 12 1.2 术语 A1A2 A3 A5 A4 A6 A8 A7 群体之间的认识关系图群体之

14、间的认识关系图 A A2A1 A11 A3 A12 A311 A21A32A31 A121 家族关系示例家族关系示例 n一个家族关系的表示形式，一个家族关系的表示形式， n表示一个群体中个体之间关系的图形描述等。表示一个群体中个体之间关系的图形描述等。 23:06 13 1.2 术语 虽然数据的虽然数据的形式及运算形式及运算存在较大的差异，但存在共性：存在较大的差异，但存在共性： o 由若干由若干具有独立意义具有独立意义的的个体个体所组成，所组成， 个体间存在着某些关系。个体间存在着某些关系。 o 对这些数据的对这些数据的运算运算也有某些相似之处。也有某些相似之处。 o 例如，在家族关系数据中

15、，例如，在家族关系数据中， n组成数据的基本个体是组成数据的基本个体是个人信息个人信息， n其中各人之间存在着其中各人之间存在着多种关系多种关系， o 如父子关系、兄弟关系、祖先后代关系等。如父子关系、兄弟关系、祖先后代关系等。 其中有些关系是其中有些关系是直接表示直接表示出来的，出来的， 还有一些关系则是还有一些关系则是隐含隐含的。的。 对家族关系数据，通常要涉及到查询特定个体间的关系、插入对家族关系数据，通常要涉及到查询特定个体间的关系、插入 和删除个体等。和删除个体等。 23:06 14 1.2 术语 由前述示例可见，由前述示例可见， 数据可以数据可以分解分解为为元素元素的集合的集合-

16、o数据元素数据元素（data element） 构成数据的基本单位（具有完整的独立意义）。构成数据的基本单位（具有完整的独立意义）。 n例如，工资表中的个人工资信息，例如，工资表中的个人工资信息， n成绩表中的学生成绩信息，家族关系中的个人等。成绩表中的学生成绩信息，家族关系中的个人等。 n在有些场合下，也称之为元素、记录、结点、顶点等。在有些场合下，也称之为元素、记录、结点、顶点等。 o数据项数据项（字段）（字段） 元素的具体描述信息。元素的具体描述信息。 学号学号姓姓 名名 考试考试 成绩成绩 备注备注 表中一行对应表中一行对应 一个元素一个元素 表中一列对应表中一列对应 一个字段一个字段

17、 23:06 15 1.2 术语 o 数据结构数据结构（data structure） 构成数据的元素之间的结构关系。构成数据的元素之间的结构关系。 n 数据元素之间存在以下几类内在的关系：数据元素之间存在以下几类内在的关系： 线性结构线性结构：元素之间具有次序关系：元素之间具有次序关系 树形结构（树型结构）：树形结构（树型结构）： 元素之间的关系类似于现实中的树。元素之间的关系类似于现实中的树。 图结构图结构（网状结构）：元素间的关系较复杂。（网状结构）：元素间的关系较复杂。 集合集合 ：元素之间没有关系。：元素之间没有关系。 逻辑结构逻辑结构 23:06 16 1.2 术语 更一般地，数据

18、结构包括以下几个方面：更一般地，数据结构包括以下几个方面： o逻辑结构逻辑结构 元素之间的内在结构关系（逻辑关系）元素之间的内在结构关系（逻辑关系） n线性、树形（树型）、图（网状）、集合线性、树形（树型）、图（网状）、集合 o存储结构存储结构 数据结构在内存中的实现形式数据结构在内存中的实现形式 o运算运算-对数据所施加的运算。对数据所施加的运算。 有关数据结构几个方面的联系图有关数据结构几个方面的联系图 逻辑结构逻辑结构 分析分析 运算实现（算法）运算实现（算法） 运算定义运算定义 存储结构存储结构 抽象数据类型抽象数据类型 （ADT） 数据结构的组成数据结构的组成 背景背景 应用应用 2

19、3:06 17 1.3 算法及其描述 算法以及算法设计是计算机专业的核心能力。算法以及算法设计是计算机专业的核心能力。 下面讨论算法的相关概念。下面讨论算法的相关概念。 o 算法算法 特定问题的求解方法。特定问题的求解方法。 这种说法较为粗略，不够严格。这种说法较为粗略，不够严格。 另一种定义另一种定义：指令的有限序列：指令的有限序列 满足：满足： (1) 输入：输入： 0n个个 (2) 输出：输出： 1n 个个 (3) 确定性确定性（无二义性）：（无二义性）： 指令的描述是确定的，指令的描述是确定的， 使得对相同的输入能产生相同的输出结果。使得对相同的输入能产生相同的输出结果。 (4) 有限

20、性有限性：指令的执行次数有限。：指令的执行次数有限。 (5) 可行性可行性：算法中每条指令可用计算机指令的有限次执行来实现。：算法中每条指令可用计算机指令的有限次执行来实现。 23:06 18 1.3 算法及其描述 o算法描述语言算法描述语言 易懂，灵活易懂，灵活 自然语言自然语言 不准确不准确 准确，严格准确，严格 计算机语言计算机语言 死板死板 伪语言（类语言）：类伪语言（类语言）：类pascal、类、类C、类、类C+ 本课程中将采用本课程中将采用C+ 的函数形式来描述。的函数形式来描述。 o 算法举例：算法举例： 1. 求最大公因子（辗转相除法）求最大公因子（辗转相除法） 2. 韩信点兵

21、问题韩信点兵问题 3. 幻方问题（纵横图）幻方问题（纵横图） 23:06 19 1.3 算法及其描述 例例1.求最大公因子（辗转相除法）求最大公因子（辗转相除法） 求任意两个整数求任意两个整数M,N最大公因子最大公因子(M,N)的方法如下：的方法如下： 若若M=N*Q+R 其中其中: R为为余数余数,满足满足 ORN-1 则则(M,N)=(N,R) 且当且当R=0时，时， (M,N)=N 按照这种方法，可以快速而方便地求出任意两个整数的最大公因子。按照这种方法，可以快速而方便地求出任意两个整数的最大公因子。 例如，例如，（1500，550）的求解过程如下：的求解过程如下： （1500，550）

22、=（550，400） =（400，150）=（150，100） =（100，50）=（50，0）=50 最终求得最终求得1500和和550的最大公因子为的最大公因子为50。 1500 % 550 400 23:06 20 1.3 算法及其描述 由此，可得到求任意两个整数由此，可得到求任意两个整数M和和N最大公因子的算法的语言函数如下：最大公因子的算法的语言函数如下： int hcf(int m, int n) while (n!=0) r=m % n; m=n; n=r; return m; 其对应的其对应的递归函数递归函数如下：如下： int hcf(int m, int n) if (n=

23、0) return m; else return hcf(n, m % n); 23:06 21 1.3 算法及其描述 例例2.“韩信点兵韩信点兵”问题的求解方法问题的求解方法 有一队士兵，确切人数不知，但若每人一组，则余人；有一队士兵，确切人数不知，但若每人一组，则余人； 每人一组，余人；每人一组，余人；每人一组，余每人一组，余人；每人一组，余人；每人一组，余 人。人。 请解答下列问题：请解答下列问题： 至少有多少人？至少有多少人？ 若已知人数在若已知人数在500010000之间，问有多少个答案？之间，问有多少个答案？ 解解：初学者容易想到用逐个试探的方法来求解，：初学者容易想到用逐个试探的

24、方法来求解， 这样显然很耗时间，特别是在所求解的值非常大时。这样显然很耗时间，特别是在所求解的值非常大时。 求解方法求解方法是：逐个满足条件，在寻找满足下一个条件的解时保证前面是：逐个满足条件，在寻找满足下一个条件的解时保证前面 条件继续成立。条件继续成立。 如何做到这一点？如何做到这一点？ 可以这样实现可以这样实现：探索满足下一个条件的的值时，：探索满足下一个条件的的值时， 以累加前面各数的最小公倍数来试探。以累加前面各数的最小公倍数来试探。 由此得到求解的程序段。由此得到求解的程序段。 23:06 22 1.3 算法及其描述 o问题（）的语言程序段如下：问题（）的语言程序段如下： n=2;

25、 / 满足满足 3人一组余人一组余2 while （n % 5！=3） n=n+3; / 在保证在保证 3人一组余人一组余2的前提下寻找满足的前提下寻找满足5人一组余人一组余3的的n值值 while （n % 7！=5） n=n+15; /在满足前两个条件的前提下寻找满足在满足前两个条件的前提下寻找满足7人一组余人一组余5的的n值值 while （n % 11！=4） n=n+105; /在满足前三个条件的前提下寻找满足在满足前三个条件的前提下寻找满足11人一组余人一组余4的的n值值 其中每次所加上的是前面数的最小公倍数其中每次所加上的是前面数的最小公倍数3，15，105 o问题（）的语言程序

26、段如下：问题（）的语言程序段如下： while （n5000 ） n=n+1155; while （n=10000） Coutn;n=n+1155;/输出满足条件的各解输出满足条件的各解 23:06 23 1.3 算法及其描述 3.幻方问题（纵横图）幻方问题（纵横图） 将将1n 放在 放在nn（n为奇数）为奇数） 的方阵中，使得任意一行任意一的方阵中，使得任意一行任意一 列以及两条对角线上的所有元素之和均相等。如列以及两条对角线上的所有元素之和均相等。如n=5时的方时的方 阵如下图所示。阵如下图所示。 152417 1614723 22201364 321191210 92251811 23:

27、06 24 1.3 算法及其描述 o 这一问题如果采用试探的方法，在值较大时，将这一问题如果采用试探的方法，在值较大时，将 难以求出，因为可能的状态数是难以求出，因为可能的状态数是 ！个。 ！个。 o 经典的经典的构造方法构造方法如下：如下： n 将数将数1 1 放在第一行的中间元素，放在第一行的中间元素， 然后往左上的位置然后往左上的位置 上放入下一个数。上放入下一个数。 n 若左上的位置已有数，则将其放入该数的下一行中若左上的位置已有数，则将其放入该数的下一行中 的同一列的位置上。的同一列的位置上。 n 若已是最左或最上面位置上的元素，则其下一个位若已是最左或最上面位置上的元素，则其下一个

28、位 置的寻找方法是：置的寻找方法是： 将方阵卷成一个纸筒，将方阵卷成一个纸筒， 然后依然后依 此再按同样的方向再找下一个位置，直到此再按同样的方向再找下一个位置，直到n nn n个元个元 素全部放入为止。素全部放入为止。 23:06 25 1.3 算法及其描述 时的求解过程如下： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 23:06 26 1.4 算法分析 o由前面例题可知，不同的算法花费时间是有差异的，某些方法就由前面例题可知，不同的算法花费时间是有差异的，某些方法就 难以实际应用。难以实际应用。 o除

29、了时间方面外，还有哪些需要考虑的性能？除了时间方面外，还有哪些需要考虑的性能？ o算法的衡量指标：在正确性的前提下，重点关注以下指标算法的衡量指标：在正确性的前提下，重点关注以下指标: : （1 1）时间性能）时间性能运行算法所需的时间开销。运行算法所需的时间开销。 （2 2）空间性能）空间性能运行算法所需的辅助空间的规模。运行算法所需的辅助空间的规模。 （3 3）其它性能）其它性能如可读性如可读性/ /可移植性等。可移植性等。 o时间性能（时间复杂度）的描述方法讨论：时间性能（时间复杂度）的描述方法讨论： 方式方式(1)(1)： 以运行算法的以运行算法的机器机器时间开销时间开销来度量来度量

30、问题：问题：与具体机器相关，难以比较与具体机器相关，难以比较 方式（方式（2 2）：以算法中语句的）：以算法中语句的执行次数执行次数来衡量来衡量 问题：问题：计算麻烦，可以简化为计算麻烦，可以简化为 方式（方式（3 3）：以算法中语句的执行次数的）：以算法中语句的执行次数的数量级数量级来替代。来替代。 23:06 27 1.4 算法分析 数量级：数量级：如果变量如果变量n的函数的函数f(n)和和g(n)满足：满足： lim f(n)/g(n)=常数常数 k (k,0)， 则称则称f(n)和和g(n) 是同一数量级的，是同一数量级的， 并用并用f(n)=O(g(n)的形式来表示。的形式来表示。

31、较为常见的算法的时间复杂度从小到大依次如下：较为常见的算法的时间复杂度从小到大依次如下： O(1)O(log2n) O(n) O(nlog2n) O(n2)O(n3)O(2n)O(n!) 难以实际应用难以实际应用! 23:06 28 1.4 算法分析 o 例：求解以下程序段的时间复杂度：例：求解以下程序段的时间复杂度： for（i=1; i=n; i+）x=x+1; 该语句的流程图如下该语句的流程图如下: 由此可知，数量级为：由此可知，数量级为：lim f(n)/g(n)= lim (3n+2)/n = 3， 相应的时间复杂度为为相应的时间复杂度为为O (n) 语句执行次数语句执行次数 i =

32、 n N Y i=1； x=x+1； i+； 1次 n+1次 n次 n次 共：3n+2次 23:06 29 练习：练习： 1. 求下列语句段的时间复杂度求下列语句段的时间复杂度(难度：难度：*)： (1) for (i=1; in; i+) for (j=1; j= i; j+) x+; (2) i = 1; while (in) i = i*2; (3) for (i=1; i=n; i+) for (j=1; j=n; j+) for (k=1; k=n; k+) x+; （4）for (i=1; in; i+) for (j=1; jn; j+) x+; for (k=1; kn;k+)

33、 x+; 23:06 30 练习：练习： 2. 编写算法以计算在给定各系数和变量x的值时的多项式fn(x)的值，要求时间 尽可能少(难度：难度：*) 。 （提示：可将各系数存储在数组A中； 另外，乘法运算的时间是加法运算时间的数倍） fn(x)= anxn +an-1xn-1+an-1xn-2+. a2x2+a1x+a0 3. 设计算法求集合1,2,.,n的幂集(难度：难度：*) 。 4. 设计算法将整型数组An中的元素调整为左右两部分，其中左边所有元素为 奇数，右边所有元素为偶数。并要求算法的时间复杂度为O(n) (难度：难度： *) 。 5. 已知输入序列中各元素的值至少有两个元素。设计算

34、法求出该序列中元素的 所有最大升、降子序列。例如，若元素依次为（1，20，30，12，3，5，7， 4，6，100，11，8），则输出结果为（1，20，30），（30，12，3）， （3，5，7），（7，4），（4，6，100），（100，11，8） (难度：难度： *) 。 23:06 31 练习：练习： 6.背包问题：设有个物品，其重量分别为背包问题：设有个物品，其重量分别为w1，w2，w3，wn，所，所 有物品的重量之和有物品的重量之和背包所能放置的重量。设计算法从中找出若背包所能放置的重量。设计算法从中找出若 干物品放入背包中，使得其重量之和正好为干物品放入背包中，使得其重量之和正好为

35、(难度：难度：*) 。 例如，例如，S=50, n=10, w=( 29 26 18 16 13 10 8 5 3 1) （其中每一行为一个解。每一对数中，第一个为该元素在中的序号，（其中每一行为一个解。每一对数中，第一个为该元素在中的序号， 第二个为元素的值）：第二个为元素的值）： (1,29) (3,18) (9,3) (1,29) (4,16) (8,5) (1,29) (5,13) (7,8) (1,29) (5,13) (8,5) (9,3) (1,29) (6,10) (7,8) (9,3) (2,26) (3,18) (8,5) (10,1) (2,26) (4,16) (7,8

36、) (2,26) (4,16) (8,5) (9,3) (2,26) (5,13) (6,10) (10,1) (2,26) (5,13) (7,8) (9,3) (2,26) (6,10) (7,8) (8,5) (10,1) (3,18) (4,16) (5,13) (9,3) (3,18) (4,16) (6,10) (8,5) (10,1) (3,18) (4,16) (7,8) (8,5) (9,3) (3,18) (5,13) (6,10) (7,8) (10,1) (3,18) (5,13) (6,10) (8,5) (9,3) (10,1) (4,16) (5,13) (6,1

37、0) (7,8) (9,3) 23:06 32 结束 o 本章内容回顾 谢 谢 33 数数 据据 结结 构构 （第二章第二章 栈栈） Data Structures 张玉红张玉红 计算机与信息学院计算机与信息学院 2021-8-92021-8-9 34 o 张玉红联络方式张玉红联络方式 n Email: ， n 电话电话 13855103036， 18056055030 o 胡学钢联络方式胡学钢联络方式 n Email: n 电话：电话：13856988808 o 助教李培培联络方式助教李培培联络方式 n Email: peipeili_ n 电话电话 18019957310 35 上课要求

38、o 作业本作业本2本本 o 上课请带作业本上课请带作业本 o 有课堂作业有课堂作业 36 第二章第二章 栈栈 第二章第二章 栈（栈（stack） 2.1 栈的定义和运算 2.2 顺序栈 2.3 栈的应用 37 第二章第二章 栈栈 栈栈是软件设计中最基本的数据结构，是软件设计中最基本的数据结构， 这是本课程所介绍的第一种数据结构。这是本课程所介绍的第一种数据结构。 学习栈结构时，需要掌握哪些方面的内容？学习栈结构时，需要掌握哪些方面的内容？ 为此，回顾一下上一章所介绍的数据结构的组成部分。为此，回顾一下上一章所介绍的数据结构的组成部分。 由此可知，对每一种结构的学习的组成部分。由此可知，对每一种

39、结构的学习的组成部分。 逻辑结构 分析 运算实现（算法） 运算定义 存储结构 数据结构的组成 2.1应用场景 o 1 一人巷 o 2 火车站调度 38 39 2.1 栈的定义和运算 2.1.1 栈的定义栈的定义 o栈栈是只能在一端插入和删除元素的线性表。是只能在一端插入和删除元素的线性表。 术语术语：栈顶栈顶, 栈底栈底, 入栈（压栈）入栈（压栈）, 出栈（弹栈）出栈（弹栈） an an-1 a1 入栈 (PUSH) 出栈 (POP) 栈 顶 (top) 栈底 (botto m) 逻辑结构和运 算 a1 a2 an 特性：后进先出 ( LIFO ) -Last in First out a1a

40、2 an an a2 a1 40 2.1 栈的定义和运算 2.1.2 2.1.2 栈的运算栈的运算 o 1.1.栈的基本运算定义栈的基本运算定义 对栈的基本运算有如下几个：对栈的基本运算有如下几个： (1)(1)初始化初始化 ：设置栈为空。：设置栈为空。 (2)(2)判断判断栈为栈为空空： 若为空，则返回若为空，则返回TRUETRUE，否则返回，否则返回FALSE. FALSE. (3)(3)判断判断栈为栈为满满： 若为满，则返回若为满，则返回TRUETRUE，否则返回，否则返回FALSE. FALSE. (4)(4)取取栈顶栈顶元素：元素：取出栈顶元素。取出栈顶元素。 条件：栈不空。条件：栈

41、不空。 否则，应能明确给出标识，以便程序的处理。否则，应能明确给出标识，以便程序的处理。 (5)(5)入栈入栈：将元素入栈，即放到栈顶。：将元素入栈，即放到栈顶。 如果栈满，怎样处理？如果栈满，怎样处理？ (6)(6)出栈出栈：删除当前栈顶的元素。：删除当前栈顶的元素。 如因为栈空而不能进行，如因为栈空而不能进行，应怎样处理？应怎样处理？ 运算定 义 41 2.1.2 栈的运算 2. 栈的运算的栈的运算的C+描述描述 o 如何用如何用C+描述栈的内容和运算？描述栈的内容和运算？ 一种方法是：一种方法是： n 将栈的有关将栈的有关数据数据和和运算运算封装在一起，封装在一起， n 以以C+的的类类

42、的形式来的形式来封装封装描述。描述。 n 封装的数据和运算要便于被有关程序来调用。封装的数据和运算要便于被有关程序来调用。 o 因此，栈的因此，栈的C+描述的框架如下所示： class stack ; 运算描述部 分 数据描述部 分 类的名 称 类的框 架 42 2.1.2 栈的运算 o下面讨论栈的运算的下面讨论栈的运算的C+描述的细节，先给出每一个运算的对应描述：描述的细节，先给出每一个运算的对应描述： n初始化函数的描述初始化函数的描述 栈的C+类描述： class stack stack(); 栈的数据成员 ; 栈的运算 (1)初始化 ：设置栈为空。 (2)判断栈为空： 若为空，则返回T

43、RUE，否则返回FALSE. (3)判断栈为满： 若为满，则返回TRUE，否则返回FALSE. (4)取栈顶元素：取出栈顶元素。 条件：栈不空。 否则，应能明确给出标识，以便程 序的处理。 (5)入栈：将元素入栈，即放到栈顶。 如果栈满，怎样处理？ (6)出栈：删除当前栈顶的元素。 如因为栈空而不能进行，应怎样处理？ 采用C+ 的 构造函数 43 2.1.2 栈的运算 o 判断函数的对应判断函数的对应 栈的C+类描述： class stack stack(); Bool empty() Bool full() 栈的数据成员 ; 栈的运算 (1)初始化 ：设置栈为空。 (2)判断栈为空： 若为空

44、，则返回TRUE，否则返回FALSE. (3)判断栈为满： 若为满，则返回TRUE，否则返回FALSE. (4)取栈顶元素：取出栈顶元素。 条件：栈不空。 否则，应能明确给出标识，以便程 序的处理。 (5)入栈：将元素入栈，即放到栈顶。 如果栈满，怎样处理？ (6)出栈：删除当前栈顶的元素。 如因为栈空而不能进行，应怎样处理？ 判断为空的函数 判断为满的函数 const; const; 44 2.1.2 栈的运算 o 其他几个函数的对应描述其他几个函数的对应描述 分析分析： （1）几个运算的条件可能有不成立的情况，）几个运算的条件可能有不成立的情况， 因此，需要给予明确的反映。因此，需要给予明

45、确的反映。 （2）设立运算是否正常的类型）设立运算是否正常的类型error_code， 正常时返回正常时返回success, 否则返回错误类型，如否则返回错误类型，如overflow, underflow等。等。 enum error_code success, overflow, underflow; （3）可以将这几个函数的类型设置为）可以将这几个函数的类型设置为error_code； （4）如果需要返回其他的值，可以作为参数来返回。）如果需要返回其他的值，可以作为参数来返回。 45 2.1.2 栈的运算 由上述讨论可得到其他几个函数的功能描述： （4)取栈顶元素的运算功能描述： 如果栈不

46、空，则取出栈顶元素到参数x中，然后返回success。 否则，返回downflow。 对应的运算函数为： error_code get_top(elementtype (5)入栈的运算功能描述： 如果栈不满，则将元素入栈，并返回success。 否则，返回overflow。 对应的运算函数为： error_code push(const elementtype x); 46 2.1.2 栈的运算 (6)(6)出栈出栈的运算功能描述：的运算功能描述： 如果栈不空，删除当前栈顶的元素，并返回如果栈不空，删除当前栈顶的元素，并返回successsuccess。 否则，返回否则，返回underflow

47、underflow。 对应的运算函数为：对应的运算函数为： error_code pop(); 47 2.1.2 栈的运算 o 由此得到栈的类由此得到栈的类stack的函数成员列表如下：的函数成员列表如下： class stack stack(); / 初始化初始化 Bool empty( ) const; / 判断空判断空 Bool full( ) const; / 判断满判断满 error_code get_top(elementtype / 取栈顶元素取栈顶元素 error_code push(const elementtype x); /入栈入栈 error_code pop(); /

48、 出栈出栈 栈的数据成员栈的数据成员; ; 问题：上述类的描述是否还需要补充什么？问题：上述类的描述是否还需要补充什么？ 48 2.2 顺序栈 o2.2.1 存储结构：存储结构： n 假设有一个足够大的存储空间（数组）假设有一个足够大的存储空间（数组）data,可用于存可用于存 储栈的元素。储栈的元素。 n 则可将栈中元素连续地存储到数组的各元素则可将栈中元素连续地存储到数组的各元素-顺序存顺序存 储方式储方式。 n 如下图所示：如下图所示： o其中：为了能随时知道栈中的元素个数，设置了一个计数变量其中：为了能随时知道栈中的元素个数，设置了一个计数变量count。 o将数组将数组data和和c

49、ount作为类作为类stack的数据成员。的数据成员。 栈的存储结构 a1a2 an 01 n-1maxle n n data coun t 顺序栈存储结 构 49 2.2 顺序栈 o由此而得到类由此而得到类stack的完整描述。的完整描述。 o封装类封装类: class stack public: stack(); Bool empty()const; Bool full() const; error_code get_top(elementtype error_code push(const elementtype x); error_code pop(); private: int count; elementtype datamaxlen; /定义其它成员定义其它成员 ; 这是起什么作用的？ 作用是什么？ 50 2.2 顺序栈 o 2.2.2 运算实现：即类运算实现：即类class的各函数成员的具体实现。的各函数成员的具体实现。 初始化函数的实现：初始化函数的实现： stack:stack() count = 0; a1a2 an 01 n-1maxle n n data coun t 51 2.2 顺序栈 判断空的函数的实现：判断空的函数的实现： Bool stack:empty()const if ( count = 0 ) return TRUE; else re