二级公共基础知识完整版

1、1 算法及数据结构算法及数据结构程序设计基础程序设计基础软件软件 工程基础工程基础数据库设计基础数据库设计基础 2 3 4 5 6 7 8 algorithm 1 1、算法的基本概念、算法的基本概念( (汉诺塔的例子) ) 算法是对特定问题求解步骤的一种描述，它是指令的有 限序列，其中每一条指令表示一个或多个操作。它是一组严 谨地定义运算顺序的规则，并且每一个规则都是有效的，且 是明确的，此顺序将在有限的次数下终止。 算法具有可行性可行性、确定性确定性、有穷性有穷性、输入输入和输出输出（拥有 足够的情报）等个重要特性。 汉 诺 塔 1-b1-b 2-c 2-c 1-c 1-c 3-b 3-b

2、1-a 1-a 2-b 2-b 1-b 1-b abc 1 2 3 算法：算法： 算法：算法：对特定问题求解步骤的一种描述。对特定问题求解步骤的一种描述。 算法的描述方法：算法的描述方法：自然语言、专用工具或某种计算机语言。自然语言、专用工具或某种计算机语言。 返回 10 2 2、算法的基本要素、算法的基本要素 (1) 对数据对象的运算和操作： 算术运算、逻辑运算、关系运算、数据传输 算法中各操作之间的执行顺序； 描述算法的工具通常有传统流程图、n-s结构化流程 图、算法描述语言等； 一个算法一般可以用顺序、选择、循环三种基本结构 组合而成。 (2) 算法的控制结构： 11 3 3、算法设计的

3、基本方法、算法设计的基本方法及例子 1. 列举法（列出所有可能，再逐一检验，得到符合条件的结果）百钱买百鸡 2. 归纳法（通过特殊情况，经过分析，最后找出一般关系） 3. 递推（从已知的初始条件出发，逐步推算，得到结果）猴子分食桃子 4. 递归（将问题逐层分解，最后归结为一些最简单的问题）求年龄问题 5. 减半递推（重复将问题的规模减半，而问题性质不变）二分法求方程实根 6. 回溯法（以最优方式向前试探，如果失败，则后退再选）八皇后问题 12 (1)(1)时间复杂度时间复杂度 v 依据算法编制的程序在计算机上运行时所消耗的时间 来度量。通常有事后统计法和事前分析估算法。 v 一个算法是由控制结

4、构（顺序、分支和循环）和原操 作构成的，算法时间取决于两者的综合效果。 v 算法中基本操作重复执行次数n和算法执行时间同步 增长，称作算法的时间复杂度。 13 (2)(2)空间复杂度空间复杂度 v 一般是指执行这个算法所需要的内存空间。 v 一个算法所占用的存储空间包括算法程序所占的空间、 输入的初始数据所占的存储空间以及某种数据结构所需 要的附加存储空间。 v 一个上机执行的程序除了需要存储空间来寄存本身所用 指令、常数、变量和输入数据外，也需要一些对数据进 行操作的工作单元和存储一些为实现计算所需信息的辅 助空间。 14 3 3、例题讲解、例题讲解 v 算法的时间复杂度是指算法的时间复杂度

5、是指( ( c c ) ) a a、执行算法程序所需要的时间执行算法程序所需要的时间 b b、算法程序的长度算法程序的长度 c c、算法执行过程中所需要的基本运算次数算法执行过程中所需要的基本运算次数 d d、算法程序中的指令条数算法程序中的指令条数 v 算法的基本特征是可行性、确定性、算法的基本特征是可行性、确定性、 【1 1】和拥有足够和拥有足够 的情报。的情报。 【答案】【答案】: :有穷性有穷性 v 算法的空间复杂度是指算法的空间复杂度是指( ( d d ) ) a) a) 算法程序的长度算法程序的长度 b) b) 算法程序中的指令条数算法程序中的指令条数 c) c) 算法程序所占的存

6、储空间算法程序所占的存储空间 d) d) 执行过程中所需要的存储空间执行过程中所需要的存储空间 15 v 在计算机中，算法是指（ b b ） a) 加工方法 b) b) 解题方案的准确而完整的描述解题方案的准确而完整的描述 c) 排序方法 d) 查询方法 v 算法分析的目的是( d d ) a) 找出数据结构的合理性 b) 找出算法中输入和输出之间的关系 c) 分析算法的易懂性和可靠性 d) d) 分析算法的效率以求改进分析算法的效率以求改进 v 算法的工作量大小和实现算法所需的存储单元多少分别称 为算法的 【 1 1 】 。【答案】【答案】: :时间复杂度和空间复杂度时间复杂度和空间复杂度

7、16 data structure 1 1、数据结构研究的主要内容、数据结构研究的主要内容 v 当今计算机应用的特点： 1、所处理的数据量大且具有一定的关系； 2、对其操作不再是单纯的数值计算，而更多地是需 要对其进行组织、管理和检索。 对数据的讨论不单单是数据本身，还要包括数据与对数据的讨论不单单是数据本身，还要包括数据与 数据之间的关系。数据之间的关系。 下面各例表示不同的数据采用不同的数据结构来组织。下面各例表示不同的数据采用不同的数据结构来组织。 17 学 生 基 本 情 况 学 号 姓 名 性 别 出 生 年 月 . 99070101 李 军 男 80 12 . 99070102 王

8、 颜 霞 女 81 2 . 99070103 孙 涛 男 80 9 . 99070104 单 晓 宏 男 81 3 . . . . . . 特点： 每个学生的信息占据一行，所有学生的信息按学号顺序依次排列构成一 张表格； 表中每个学生的信息依据学号的大小存在着一种前后关系，这就是我们 所说的线性结构； 对它的操作通常是插入某个学生的信息，删除某个学生的信息，更新某 个学生的信息，按条件检索某个学生的信息等等。 v 应用举例1学籍档案管理 假设一个学籍档案管理系统应包含如下表所示的学生信息。 18 v 应用举例2家庭血缘关系图 表示家庭成员的辈分关系，使用下图1-1所示的形式描述。 3 1 21

9、 3 21 2 3 1 2 3 2 12 3 12 1 3 2 1 1 家庭血缘关系图 特点： 在求解过程中，所处理的数据之间具有层次关系，这是我们 所说的树形结构； 对它的操作有：建立树形结构，输出最结点内容等等。 v 应用举例3制定教学计划 在制定教学计划时，需要考虑各门课程的开设顺序。有些课 程需要先导课程，有些课程则不需要，而有些课程又是其他课程 的先导课程。比如，计算机专业课程的开设情况如下表所示： 计算机专业学生的必修课程 课课程程编编号号 课课程程名名称称 需需要要的的先先导导 课课程程编编号号 c 1 程序设计基础 无 c 2 离散数学 c 1 c 3 数据结构 c 1 ，c

10、2 c 4 汇编语言 c 1 c 5 算法分析与设计 c 3 ，c 4 c 6 计算机组成原理 c 1 1 c 7 编译原理 c 5 ，c 3 c 8 操作系统 c 3 ，c 6 c 9 高等数学 无 c 1 0 线性代数 c 9 c 1 1 普通物理 c 9 c 1 2 数值分析 c 9 ，c 1 0 ，c 1 19 这种数据可以用下面的图来表示： v 课程先后关系的图形描形式： c1 c9 c4 c2 c12 c10 c11 c5 c3 c6 c7 c8 图 1-2 计算机专业必修课程开设先后关系 20 1 1、数据的、数据的逻辑结构逻辑结构 2 2、数据的、数据的存储结构存储结构 3 3

11、、数据的、数据的运算运算：检索、排序、插入、删除、修改等。：检索、排序、插入、删除、修改等。 a a线性结构线性结构 b b非线性结构非线性结构 a a顺序存储顺序存储 b b链式存储链式存储 线性表线性表 栈栈 队队 树形结构树形结构 图形结构图形结构 数据结构的三个方面数据结构的三个方面 (亦称物理结构亦称物理结构) 数据结构的主要 研究问题： 21 2 2、基本概念和术语、基本概念和术语 数据结构是一门研究组织组织、存储存储和运算运算的一般方 法的学科。 例：整数整数(1,2)、实数实数(1.1,1.2) 字符串字符串(beijing)、图形图形、声音声音。 计算机管理图书问题 ： 在图

12、书馆里有各种卡片：有按书名编排的、有按作 者编排的、有按分类编排。如何将查询图书的这些信息 存入计算机中既要考虑查询时间短，又要考虑节省空间。 最简单的办法之一是建立一张表，每一本书的信息在表 中占一行，如： 22 数据元素在计算机中的表示 数据结构是一门研究组织组织、存储存储和运算运算的一般方法 的学科。 如何将0,1,2,3,4,5,6,7,8,9这10个数存放 在计算机中能最快地达到你所需要的目的？ 目的不同，最佳的存储方方法就不同。 从大到小排列：9,8,7,6,5,4,3,2,1,0 输出偶数：0,2,4,6,8,1,3,5,7,9 对数据结构中的节点进行操作处理对数据结构中的节点进

13、行操作处理 （插入、删除、修改、查找、排序）（插入、删除、修改、查找、排序） 23 v 数据元素数据元素( (data element)data element) 数据元素是数据的基本单位，即数据集合中的个体。 有时一个数据元素可由若干数据项数据项(data itemdata item)组成。数 据项是数据的最小单位。 数据元素亦称节点节点或记录记录。 数据结构可描述为数据结构可描述为 group=group=（d d，r r） 有限个数据元素的集合有限个数据元素的集合 有限个节点间关系的集合有限个节点间关系的集合 24 25 数据结构可描述为数据结构可描述为 group=（d，r） l 例例

14、1：一年四季的数据结构可表示成：一年四季的数据结构可表示成 b=（d，r） d=春，夏，秋，冬春，夏，秋，冬 r=（春，夏），（夏，秋），（秋，冬）（春，夏），（夏，秋），（秋，冬） l 例例2：家庭成员数据结构可表示成：家庭成员数据结构可表示成 b=（d，r） d=父亲，儿子，女儿父亲，儿子，女儿 r=（父亲，儿子），（父亲，女儿）（父亲，儿子），（父亲，女儿） 26 数据结构也可用图形表示数据结构也可用图形表示 l一年四季的数据结构可表示成一年四季的数据结构可表示成 l家庭成员数据结构可表示成家庭成员数据结构可表示成 冬冬春春夏夏秋秋 父亲父亲 儿子儿子女儿女儿 （ 概念：结点、前件、后件

15、、根结点、叶子 ） 27 v 树形结构 全校学生档案管理的组织方式全校学生档案管理的组织方式 计算机程序管理系统也是典型的计算机程序管理系统也是典型的树形结构树形结构。 28 1 14 4 2 23 3 d=1 , 2 , 3 , 4 d=1 , 2 , 3 , 4 r=(1,2),(1,3), r=(1,2),(1,3), (1,4),(2,3), (1,4),(2,3), (3,4),(2,4) (3,4),(2,4) 2 2 1 1 3 3 d= 1 , 2 , 3 d= 1 , 2 , 3 r=(1,2),(2,3),(3,2),(1,3) r=(1,2),(2,3),(3,2),(1

16、,3) v 图形结构图形结构节点间的连结是任意的节点间的连结是任意的 29 3 3、例题讲解、例题讲解 v 数据处理的最小单位是数据处理的最小单位是( ( c c ) ) a)a)数据数据 b)b)数据元素数据元素 c) c) 数据项数据项 d) d) 数据结构数据结构 v 数据结构作为计算机的一门学科，主要研究数据的逻辑结构、数据结构作为计算机的一门学科，主要研究数据的逻辑结构、 对各种数据结构进行的运算，以及对各种数据结构进行的运算，以及( ( a a ) ) a) a) 数据的存储结构数据的存储结构 b) b) 计算方法计算方法 c) c) 数据映象数据映象 d) d) 逻辑存储逻辑存储

17、 v 数据结构包括数据的逻辑结构、数据的数据结构包括数据的逻辑结构、数据的 【4 4】 以及对数据的以及对数据的 操作运算。操作运算。 【答案【答案】物理结构（或存储结构）物理结构（或存储结构） 30 v 线性结构与非线性结构：线性结构与非线性结构： v 线性结构：有且只有一个根结点；每一个线性结构：有且只有一个根结点；每一个 结点最多有一个前件，也最多有一个后件。结点最多有一个前件，也最多有一个后件。 如：一年四季，如：一年四季，2626个英文字母个英文字母 v非线性结构：线性以外的数据结构。非线性结构：线性以外的数据结构。 如：反映家庭成员间辈分关系的数据结构如：反映家庭成员间辈分关系的数

18、据结构 31 结点间是以线性关系联结，结点间是以线性关系联结，如前面提到的： 一年四季 26个英文字母 线性 有限 序列 4、线性表、线性表（linear list） v 线性表线性表：具有线性结构的有限序列。 a ab bc cd dz z 春春夏夏秋秋冬冬 32 学生成绩表学生成绩表 线性表线性表 33 数据元素、结点、记录 数据项 线性 v 线性表的定义线性表的定义: : 线性表线性表是是n n个元素的有限序列，它们之间的关系可以排成个元素的有限序列，它们之间的关系可以排成 一个线性序列：一个线性序列：a1a1，a2a2， ，aiai， ，anan 其中其中n n称作表的称作表的长度长度

19、，当，当n=0n=0时，称作时，称作空表空表。 v 线性表的特点：线性表的特点： 1 1、线性表中所有元素的性质相同。、线性表中所有元素的性质相同。 2 2、除第一个和最后一个数据元素之外，其它数据元素有且、除第一个和最后一个数据元素之外，其它数据元素有且 仅有一个前驱和一个后继。第一个数据元素无前驱，最仅有一个前驱和一个后继。第一个数据元素无前驱，最 后一个数据元素无后继。后一个数据元素无后继。 3 3、数据元素在表中的位置只取决于它自身的序号。、数据元素在表中的位置只取决于它自身的序号。 v 在线性表上常用的运算有：在线性表上常用的运算有： 初始化、求长度、取元素、修改、前插、删除、检索、

20、排序初始化、求长度、取元素、修改、前插、删除、检索、排序 34 35 v 线性表的线性表的 顺序存储结构 及其及其 插入 与与 删除 操作操作 特点：特点： 1 1、线性表中数据元素类型一致，只有数据域，存储空间、线性表中数据元素类型一致，只有数据域，存储空间 利用率高。利用率高。 2 2、所有元素所占的存储空间是连续的。、所有元素所占的存储空间是连续的。 3 3、各数据元素在存储空间中是按逻辑顺序依次存放的、各数据元素在存储空间中是按逻辑顺序依次存放的 （a a）做插入、删除时需移动大量元素。做插入、删除时需移动大量元素。 （b b）空间估计不明时，按最大空间分配。空间估计不明时，按最大空间

21、分配。 36 顺顺 序序 存存 储储 存储地址存储地址存储内容存储内容 元素元素n n . 元素元素i i . 元素元素2 2 元素元素1 1 l lo o + + m l lo o+(i-1)+(i-1)m lo+lo+（n-1)n-1)m loc(loc(元素元素i)=li)=lo o+ +（i-1)i-1)m 每个元素所占用每个元素所占用 的存储单元个数的存储单元个数 v 线性表的线性表的 顺序存储结构顺序存储结构： 首地址首地址 起始地址起始地址 基地址基地址 v插入运算插入运算 a ai-1 i-1 .a a2 2a a1 1 a alength length a ai+1 i+1

22、a ai i a alengt lengt h h 插入算法的分析 假设线性表中含有n个数据元素，在进行插入操作时，若 假定在n+1个位置上插入元素的可能性均等，则平均移动元素 的个数为： 1n 1i is 2 n 1)i(n 1n 1 e 37 x x a ai-1 i-1 .a a2 2a a1 1 a alength length a ai+1 i+1 a ai ix x 在进行删除操作时，若假定删除每个元素的可能性均等， 则平均移动元素的个数为： 分析结论分析结论 顺序存储结构表示的线性表，在做插入或删除操作时，平 均需要移动大约一半的数据元素。当线性表的数据元素量较大， 并且经常要对

23、其做插入或删除操作时，这一点需要值得考虑。 n 1i dl 2 1n i)(n n 1 e v删除算法的分析删除算法的分析 38 q 线性表的例题讲解线性表的例题讲解 v 顺序存储方法是把逻辑上相邻的结点存储在物理位置顺序存储方法是把逻辑上相邻的结点存储在物理位置 【1 1】 的存储单元中。的存储单元中。 【答案【答案】相邻相邻 v 长度为长度为n n的顺序存储线性表中，当在任何位置上插入一个元的顺序存储线性表中，当在任何位置上插入一个元 素概率都相等时，插入一个元素所需移动元素的平均个数素概率都相等时，插入一个元素所需移动元素的平均个数 为为【2 2】 。 【答案【答案】 n/2n/2 v

24、线性表线性表l=(a1,a2,a3,l=(a1,a2,a3,aiai，an)an)，下列说法正确的是（下列说法正确的是（d d） a) a) 每个元素都有一个直接前件和直接后件每个元素都有一个直接前件和直接后件 b) b) 线性表中至少要有一个元素线性表中至少要有一个元素 c) c) 表中诸元素的排列顺序必须是由小到大或由大到小表中诸元素的排列顺序必须是由小到大或由大到小 d) d) 除第一个元素和最后一个元素外，其余每个元素都有一除第一个元素和最后一个元素外，其余每个元素都有一 个且只有一个直接前件和直接后件个且只有一个直接前件和直接后件 39 40 数据结构中，与所使用的计算机无关的是数据

25、的数据结构中，与所使用的计算机无关的是数据的( ( c c ) ) a) a) 存储结构存储结构b) b) 物理结构物理结构 c) c) 逻辑结构逻辑结构d) d) 物理和存储结构物理和存储结构 下列叙述中，错误的是（下列叙述中，错误的是（ b b ） a) a) 数据的存储结构与数据处理的效率密切相关数据的存储结构与数据处理的效率密切相关 b) b) 数据的存储结构与数据处理的效率无关数据的存储结构与数据处理的效率无关 c) c) 数据的存储结构在计算机中所占的空间不一定是连续的数据的存储结构在计算机中所占的空间不一定是连续的 d) d) 一种数据的逻辑结构可以有多种存储结构一种数据的逻辑结

26、构可以有多种存储结构 数据的存储结构是指（数据的存储结构是指（ b b ） a a）数据所占的存储空间数据所占的存储空间 b b）数据的逻辑结构在计算机中的表示数据的逻辑结构在计算机中的表示 c c）数据在计算机中的顺序存储方式数据在计算机中的顺序存储方式 d d）存储在外存中的数据存储在外存中的数据 根据数据结构中各数据元素之间前后件关系的复杂程度，一般根据数据结构中各数据元素之间前后件关系的复杂程度，一般 将数据结构分成将数据结构分成( ( c c ) ) a) a) 动态结构和静态结构动态结构和静态结构 b) b) 紧凑结构和非紧凑结构紧凑结构和非紧凑结构 c) c) 线性结构和非线性结

27、构线性结构和非线性结构 d) d) 内部结构和外部结构内部结构和外部结构 数据的逻辑结构有线性结构和数据的逻辑结构有线性结构和 【2 2】两大类。两大类。非线性结构非线性结构 当线性表采用顺序存储结构实现存储时，其主要特点是当线性表采用顺序存储结构实现存储时，其主要特点是【1】。 【答案【答案】逻辑结构中相邻的结点在存储结构中仍相邻。逻辑结构中相邻的结点在存储结构中仍相邻。 41 a1 a2 . an 进栈进栈出栈出栈 栈顶栈顶 栈底栈底 5 5、堆栈和队列、堆栈和队列 q 堆栈和队列的定义堆栈和队列的定义 栈和队列栈和队列是两种特殊的线性表，它们是运算时要受到是两种特殊的线性表，它们是运算时

28、要受到 某些限制的线性表，故也称为某些限制的线性表，故也称为限定性的数据结构。限定性的数据结构。 v 堆栈的定义堆栈的定义 堆栈：堆栈：限定只能在表的一端进行插入和删除的特殊的线性表限定只能在表的一端进行插入和删除的特殊的线性表, ,此种此种 结构称为结构称为后进先出。后进先出。设栈设栈s=s=（a a1 1，a a2 2，a ai i， ，a an n）, , 其中其中a a1 1是是栈底栈底元素，元素， a an n是是栈顶栈顶元素。元素。 栈顶（栈顶（top)top)：允许插入和删除的一端；允许插入和删除的一端； 约定约定toptop始终指向新数据元素将存放的位置。始终指向新数据元素将存

29、放的位置。 栈底栈底（bottom):bottom):不允许插入和删除的一端。不允许插入和删除的一端。 42 v 队列的定义队列的定义 队列：队列：一种特殊的线性结构，限定只能在表的一端进行插入，一种特殊的线性结构，限定只能在表的一端进行插入， 在表的另一端进行删除的线性表在表的另一端进行删除的线性表 。此种结构称为。此种结构称为先进先进 先出（先出（fifo）表表。 a1 , a2 , a3 , a4 , an-1 , an 队队 列列 示示 意意 图图 队头队头 队尾队尾 v 队列的主要运算队列的主要运算 （1）设置一个空队列； （2）插入一个新的队尾元素，称为进队； （3）删除队头元素，

30、称为出队； （4）读取队头元素； 43 q 堆栈和队列的例题讲解堆栈和队列的例题讲解 v栈和队列的共同特点是（栈和队列的共同特点是（ c c ） a)a)都是先进先出都是先进先出 b) b) 都是先进后出都是先进后出 c) c) 只允许在端点处插入和删除元素只允许在端点处插入和删除元素 d) d) 没有共同点没有共同点 v如果进栈序列为如果进栈序列为e1,e2,e3,e4e1,e2,e3,e4，则可能的出栈序列是（则可能的出栈序列是（ b b ） a) e3,e1,e4,e2 a) e3,e1,e4,e2 b) e4,e3,e2,e1b) e4,e3,e2,e1 c) e3,e4,e1,e2

31、c) e3,e4,e1,e2 d) d) 任意顺序任意顺序 44 45 la = 42+b 8 8 2 2 6 6 lb = 63+c lc = 32+d ld = 1+2 = 8 + b = 2 + c = 6 + d = 3 8 2 6 u 一些重要的程序语言一些重要的程序语言( (如如c c语言和语言和pascalpascal语言语言) ) 允许过程允许过程 的递归调用。而实现递归调用中的存储分配通常用（的递归调用。而实现递归调用中的存储分配通常用（ a a ） a) a) 栈栈b) b) 堆堆 c) c) 数组数组 d) d) 链表链表 v 当循环队列非空且队尾指针等于队头指针时，说明

32、循环队列当循环队列非空且队尾指针等于队头指针时，说明循环队列 已满，不能进行入队运算。这种情况称为已满，不能进行入队运算。这种情况称为【2 2】。答案：答案：上溢上溢 v 由两个栈共享一个存储空间的好处是（由两个栈共享一个存储空间的好处是（ b b ） a) a) 减少存取时间，降低下溢发生的机率减少存取时间，降低下溢发生的机率 b) b) 节省存储空间，降低上溢发生的机率节省存储空间，降低上溢发生的机率 c) c) 减少存取时间，降低上溢发生的机率减少存取时间，降低上溢发生的机率 d) d) 节省存储空间，降低下溢发生的机率节省存储空间，降低下溢发生的机率 v 下列关于栈的叙述中正确的是（下

33、列关于栈的叙述中正确的是（ d d ） ) )在栈中只能插入数据在栈中只能插入数据 b b）在栈中只能删除数据在栈中只能删除数据 c c）栈是先进先出的线性表栈是先进先出的线性表 d d）栈是后进先出的线性表栈是后进先出的线性表 v 下列关于队列的叙述中正确的是（下列关于队列的叙述中正确的是（ c c ） ）在队列中只能插入数据）在队列中只能插入数据 b b）在队列中只能删除数据在队列中只能删除数据 c c）队列是先进先出的线性表队列是先进先出的线性表 d d）队列是后进先出的线性表队列是后进先出的线性表 46 两个栈共享只有两个栈两个栈共享只有两个栈 都多时才溢出。不共享都多时才溢出。不共享

34、 的话，两个栈只有一个的话，两个栈只有一个 栈多就溢出，栈多就溢出， rearrear队尾队尾 frontfront 队头队头 v 栈底至栈顶依次存放元素栈底至栈顶依次存放元素a a、b b、c c、d d，在第五个元素在第五个元素e e 入栈前，栈中元素可以出栈，则出栈序列可能是（入栈前，栈中元素可以出栈，则出栈序列可能是（ b b ） a) abceda) abced b) dcbeab) dcbea c) dbcea c) dbcea d) cdabe d) cdabe 47 d d出出c c出出b b出出 e e出出a a出出 e e进进 顺序 出栈：出栈： 进栈：进栈： 顺序存储结构

35、常用于线性数据结 构，将逻辑上相邻的数据元素存储在 物理上相邻的存储单元里。 v 顺序存储结构的三个缺点： 1.作插入或删除操作时，需移动大量元数。 2.长度变化较大时，需按最大空间分配。 3.表的容量难以扩充。 存储内容存储内容 元素元素n n . 元素元素i i . 元素元素2 2 元素元素1 1 48 49 6 6、线性表的链式存储 线性链表线性链表 v线性链表的基本概念：线性链表的基本概念： 线性表的链式存储结构称为线性链表。 为了适应线性表的链式存储结构，计 算机存储空间被划分为一个一个小块，每 一小块占若干字节，通常称这些小块为存 储结点。 将存储空间中的每一个存储结点分为两部：

36、v一部分称为数据域，用于存储数据元素的值； v另一部分称为指针域，用于存放下一个数据元 素的存储序号（即存储结点的地址），也就是指 向后件结点. 线性链表中存储结点的结构如图2.20所示 50 1536元素21400元素11346元素3 元素4 head 1346 元素3 1536 . . . 1536 元素2 1400 . . . 元素4 1346 1400 元素1 1345 指针 存储内容存储地址 链式存储 1345 52 指向线性表中第一个结点的指针head称为 头指针。 当head=null（或0）时称为空表。 对于线性链表，可以从头指针开始，沿着各 个结点的指针扫描到链表中的所有结点

37、。 线性链表的逻辑结构图所示 53 1、比顺序存储结构的存储密度小 (每个节点都由数据域和指针域组成，所以相同空间内 假设全存满的话顺序比链式存储更多)。 2、逻辑上相邻的节点物理上不必相邻。 3、插入、删除灵活 (不必移动节点，只要改变节点中的指针)。 4、查找结点时链式存储要比顺序存储慢。 v 链接存储结构特点：链接存储结构特点： 5454 55 v 线性链表的基本运算：线性链表的基本运算： 线性链表的运算主要有以下几个：线性链表的运算主要有以下几个： 在线性链表中包含指定元素的结点之前在线性链表中包含指定元素的结点之前 插入插入一个新元素。一个新元素。 在线性链表中在线性链表中删除删除包

38、含指定元素的结点。包含指定元素的结点。 将两个线性链表按要求将两个线性链表按要求合并合并成一个线性成一个线性 链表。链表。 56 线性链表的线性链表的 插入插入 运算：运算： 线性链表的插入线性链表的插入是指在链式存储结构下是指在链式存储结构下 的线性表中插入一个新元素。的线性表中插入一个新元素。 为了要在线性链表中插入一个新元素，为了要在线性链表中插入一个新元素， 首先要给该元素分配一个新结点，然后将存首先要给该元素分配一个新结点，然后将存 放新元素值的结点链接到线性链表中指定的放新元素值的结点链接到线性链表中指定的 位置。位置。 5757 58 线性链表的删除线性链表的删除指在链式存储结构

39、下的指在链式存储结构下的 线性表中删除包含指定元素的结点。线性表中删除包含指定元素的结点。 为了在线性链表中删除包含指定元素的为了在线性链表中删除包含指定元素的 结点，首先要在线性链表中找到这个结点，结点，首先要在线性链表中找到这个结点， 然后将要删除结点放回到可利用栈。然后将要删除结点放回到可利用栈。 线性链表的线性链表的 删除删除 运算：运算： 5959 a1a 2 ana3 l . 线性表的链式存储结构可用线性表的链式存储结构可用 “结构指针结构指针”来描述来描述 带头结点的线性链表带头结点的线性链表 datanext typedef struct lnode int data; str

40、uct lnode *next; jd; b a ba x p p 单链表的插入运算单链表的插入运算 s 在在p所指向的结点之后插入新的结点所指向的结点之后插入新的结点 b a ba x anai a1a2 p p ai-1 x l 单链表的插入运算单链表的插入运算 s 单链表的插入运算单链表的插入运算 void lbcr (jd *p, int x) / * 在在p所指向的结点之后插入新的结点所指向的结点之后插入新的结点 */ jd *s; /* 定义指向结点类型的指针定义指向结点类型的指针 */ s=(jd *)malloc(sizeof(jd ); /* 生成新结点生成新结点 */ s-

41、data=x; s-next=p-next; p-next=s; return ok; anai a1a2 p ai-1 l 单链表的插入运算单链表的插入运算 void lbcr (jd *p, int x) / * 在在p所指向的结点之后插入新的结点所指向的结点之后插入新的结点 */ jd *s; /* 定义指向结点类型的指针定义指向结点类型的指针 */ s=(jd *)malloc(sizeof(jd ); /* 生成新结点生成新结点 */ s-data=x; s-next=p-next; p-next=s; return ok; anai a1a2 p ai-1 l 单链表的插入运算单链

42、表的插入运算 void lbcr (jd *p, int x) / * 在在p所指向的结点之后插入新的结点所指向的结点之后插入新的结点 */ jd *s; /* 定义指向结点类型的指针定义指向结点类型的指针 */ s=(jd *)malloc(sizeof(jd ); /* 生成新结点生成新结点 */ s-data=x; s-next=p-next; p-next=s; return ok; s anai a1a2 p ai-1 x l 单链表的插入运算单链表的插入运算 void lbcr (jd *p, int x) / * 在在p所指向的结点之后插入新的结点所指向的结点之后插入新的结点 *

43、/ jd *s; /* 定义指向结点类型的指针定义指向结点类型的指针 */ s=(jd *)malloc(sizeof(jd ); /* 生成新结点生成新结点 */ s-data=x; s-next=p-next; p-next=s; return ok; s anai a1a2 p ai-1 x l 单链表的插入运算单链表的插入运算 void lbcr (jd *p, int x) / * 在在p所指向的结点之后插入新的结点所指向的结点之后插入新的结点 */ jd *s; /* 定义指向结点类型的指针定义指向结点类型的指针 */ s=(jd *)malloc(sizeof(jd ); /*

44、生成新结点生成新结点 */ s-data=x; s-next=p-next; p-next=s; return ok; s anai a1a2 p ai-1 x l 单链表的插入运算单链表的插入运算 void lbcr (jd *p, int x) / * 在在p所指向的结点之后插入新的结点所指向的结点之后插入新的结点 */ jd *s; /* 定义指向结点类型的指针定义指向结点类型的指针 */ s=(jd *)malloc(sizeof(jd ); /* 生成新结点生成新结点 */ s-data=x; s-next=p-next; p-next=s; return ok; void lbsc

45、(jd *p) /* 删除删除p指针指向结点的后一个结点指针指向结点的后一个结点 */ jd *q; if(p-next !=null) q=p-next ; / * q指向指向p的后继结点的后继结点 */ p-next=q-next; /* 修改修改p结点的指针域结点的指针域 */ free(q); /* 删除并释放结点删除并释放结点 */ 单链表的删除运算单链表的删除运算 ai-1a1aiai+1 lp void lbsc(jd *p) /* 删除删除p指针指向结点的后一个结点指针指向结点的后一个结点 */ jd *q; if(p-next !=null) q=p-next ; / * q

46、指向指向p的后继结点的后继结点 */ p-next=q-next; /* 修改修改p结点的指针域结点的指针域 */ free(q); /* 删除并释放结点删除并释放结点 */ 单链表的删除运算单链表的删除运算 ai-1a1aiai+1 lp void lbsc(jd *p) /* 删除删除p指针指向结点的后一个结点指针指向结点的后一个结点 */ jd *q; if(p-next !=null) q=p-next ; / * q指向指向p的后继结点的后继结点 */ p-next=q-next; /* 修改修改p结点的指针域结点的指针域 */ free(q); /* 删除并释放结点删除并释放结点

47、*/ 单链表的删除运算单链表的删除运算 a1 q q ai-1a1aiai+1 lp q void lbsc(jd *p) /*删除删除p指针指向结点的后一个结点指针指向结点的后一个结点 */ jd *q; if(p-next !=null) q=p-next ; / * q指向指向p的后继结点的后继结点 */ p-next=q-next; /* 修改修改p结点的指针域结点的指针域 */ free(q); /* 删除并释放结点删除并释放结点 */ 单链表的删除运算单链表的删除运算 ai-1a1aiai+1 lp q void lbsc(jd *p) /*删除删除p指针指向结点的后一个结点指针指

48、向结点的后一个结点 */ jd *q; if(p-next !=null) q=p-next ; / * q指向指向p的后继结点的后继结点 */ p-next=q-next; /* 修改修改p结点的指针域结点的指针域 */ free(q); /* 删除并释放结点删除并释放结点 */ 单链表的删除运算单链表的删除运算 ai-1a1aiai+1 lp void lbsc(jd *p) /*删除删除p指针指向结点的后一个结点指针指向结点的后一个结点 */ jd *q; if(p-next !=null) q=p-next ; / * q指向指向p的后继结点的后继结点 */ p-next=q-next

49、; /* 修改修改p结点的指针域结点的指针域 */ free(q); /* 删除并释放结点删除并释放结点 */ 单链表的删除运算单链表的删除运算 线性链表的查找操作：线性链表的查找操作： 设无表头结点的线性链表的头指针为设无表头结点的线性链表的头指针为h, h, 沿着链表的沿着链表的 开始往后找结点开始往后找结点x x，若找到，则返回该结点在链表中，若找到，则返回该结点在链表中 的位置，否则返回空地址。的位置，否则返回空地址。 jd *lbcz (jd *h,int x) jd *p; p=h; while (p!=null return(p); 2.5.2 2.5.2 循环链表循环链表: :

50、 首尾相接的链表。首尾相接的链表。 将最后一个结点的空指针改为指向头结点，从任一将最后一个结点的空指针改为指向头结点，从任一 结点出发均可找到其它结点。结点出发均可找到其它结点。 a1a2ana3l. 带头结点的单链表带头结点的单链表 a1a2ana3l. 循环单链表循环单链表 l s 28375 pr (1) l=p-next; 28375 pr s l l 对以下单链表分别执行下列各程序段对以下单链表分别执行下列各程序段,并并 画出结果示意图画出结果示意图. l s 28375 pr (2) r-data=p-data; 28575 pr s (3) r-data=p-next-data;

51、 28775 pr s l s 28375 pr (4) p-next-next-next-data=p-data; 25375 pr s l s 28375 pr (7) p=(jd*)malloc(sizeof(jd); p-data=10; r-link=p; p-link=s; l s 28375 pr (7) p=(jd*)malloc(sizeof(jd); p-data=10; r-link=p; p-link=s; p l s 28375 pr l s 28375 pr (7) p=(jd*)malloc(sizeof(jd); p-data=10; r-next=p; p-n

52、ext=s; p 10 l s 28375 pr l s 28375 pr (5) p=(jd*)malloc(sizeof(jd); p-data=10; r-next=p; p-next=s; l s 28375 r p 10 l s 28375 pr (7) p=(jd*)malloc(sizeof(jd); p-data=10; r-next=p; p-next=s; l s 28375 r p 10 l s 28375 pr (8) t=l; t-next=p-next; free(p); l s 2837 p r t 5 l s 28375 pr (9) s-next=l; l s

53、 28375 pr 如果如果 s-next= =l 则则s所指向的结点为尾结点所指向的结点为尾结点. l s 28375 pr 循环链表的结构与前面所讨论的线性链表相比，具有以下循环链表的结构与前面所讨论的线性链表相比，具有以下 两个特点：两个特点： 循环链表的头指针指向表头结点。循环链表的头指针指向表头结点。 在循环链表中，所有结点的指针构成了一个环状链。在循环链表中，所有结点的指针构成了一个环状链。 图图2.292.29是循环链表的示意图。是循环链表的示意图。 v循环链表：循环链表： 88 89 在实际应用中，循环链表与线性单链表相在实际应用中，循环链表与线性单链表相 比主要有以下两个方面

54、的优点：比主要有以下两个方面的优点： 在循环链表中，只要指出表中任何一个结点在循环链表中，只要指出表中任何一个结点 的位置，就可以从它出发访问到表中其他所的位置，就可以从它出发访问到表中其他所 有的结点。有的结点。 由于在循环链表中设置了一个表头结点，因由于在循环链表中设置了一个表头结点，因 此，在任何情况下，循环链表中至少有一个此，在任何情况下，循环链表中至少有一个 结点存在，结点存在，从而使空表与非空表的运算统一从而使空表与非空表的运算统一。 v链表不具有的特点是（链表不具有的特点是（ b b ） a) a) 不必事先估计存储空间不必事先估计存储空间 b) b) 可随机访问任一元素可随机访

55、问任一元素 c) c) 插入删除不需要移动元素插入删除不需要移动元素 d) d) 所需空间与线性表长度成正比所需空间与线性表长度成正比 v数据结构分为逻辑结构与存储结构，线性链表属于数据结构分为逻辑结构与存储结构，线性链表属于 【1 1】 。 【答案【答案】存储结构存储结构 u 栈通常采用的两种存储结构是（栈通常采用的两种存储结构是（ a a ） a) a) 顺序存储结构和链表存储结构顺序存储结构和链表存储结构 b) b) 散列方式和索引方式散列方式和索引方式 c) c) 链表存储结构和数组链表存储结构和数组 d) d) 线性存储结构和非线性存储结构线性存储结构和非线性存储结构 q 线性链表的

56、例题讲解线性链表的例题讲解 90 91 u 线性表的顺序存储结构和线性表的链式存储结构分别是线性表的顺序存储结构和线性表的链式存储结构分别是( ( c c ) ) a) a) 顺序存取的存储结构、顺序存取的存储结构顺序存取的存储结构、顺序存取的存储结构 b) b) 顺序存取的存储结构、随机存取的存储结构顺序存取的存储结构、随机存取的存储结构 c) c) 随机存取的存储结构、顺序存取的存储结构随机存取的存储结构、顺序存取的存储结构 d) d) 任意存取的存储结构、任意存取的存储结构任意存取的存储结构、任意存取的存储结构 顺序存储结构的地址在内存中是连续的所以可以通过计算 地址实现随机存取，而链式

57、存储结构的存储地址不一定连 续，只能通过第1个结点的指针顺序存取； 92 7 7、树与二叉树：、树与二叉树： v 树的基本概念：树的基本概念： 前面我们讨论的线性表，栈、队列和数 组等都是线性结构。而树是一种非线性数据 结构，它的每一个结点，都可以有不止一个 直接后继，除根外的所有结点，都有且只有 一个直接前趋。这些数据结点按分支关系组 织起来，清晰地反映了数据元素之间的层次 关系。 93 现实世界中，能用树的结构表示的例子现实世界中，能用树的结构表示的例子： 学校的行政关系、书的层次结构、人类的家族血缘关系等。学校的行政关系、书的层次结构、人类的家族血缘关系等。 9494 9595 二叉树(

58、binary tree)是一种很有用的非线 性结构。 二叉树具有以下两个特点： （1）非空二叉树只有一个根结点； （2）每一个结点最多有两棵子树，且分别 称为该结点的左子树与右子树。 v 二叉树（二叉树（binary treebinary tree）：）： 因为树的每个结点的度不同，存储困难， 使对树的处理算法很复杂。所以引出二叉树 的讨论。 96 9797 性质性质1 1：在任意一棵二叉树中，度为0的结点 （即叶子结点）总是比度为2的结点多一 个。 二叉树的性质：二叉树的性质： 特别要注意：二叉树是树的特殊情况。 a aa a b bb b 两棵不同的二叉树 98 例子例子1 1：某二叉树中

59、度为2的结点有18个，则 该二叉树中有 19 19 个叶子结点。 99 性质性质2 2：二叉树的第i层上至多有2 i-1（i 1）个结点 二叉树的性质：二叉树的性质： 4 23 1 67 89101112131415 5 第三层上(i=3)，有23-1=4个节点。 第四层上(i=4)，有24-1=8个节点。 100 二叉树的性质：二叉树的性质： 性质性质3 3：深度为深度为h h的二叉树中的二叉树中至多至多含有含有2 2h h-1 -1个结点个结点 4 23 1 67 89101112131415 5 此树的深度此树的深度h=4h=4，共有共有2 24 4-1=15-1=15个节点。个节点。

60、101 v满二叉树与完全二叉树满二叉树与完全二叉树 满二叉树是指除最后一层外，每一层上的所 有结点都有两个子结点。 完全二叉树是指这样的二叉树：除最后一层 外，每一层上的结点数均达到最大值；在最后 一层上只缺少右边的若干结点。 注意：满二叉树是完全二叉树，完全二叉树 不一定是满二叉树。 102 v 满二叉树的特点：满二叉树的特点： 每一层上都含有最大结点数。每一层上都含有最大结点数。 10 2 103 v完全二叉树的特点：完全二叉树的特点：除最后一层外，每一层都取最大除最后一层外，每一层都取最大 结点数，最后一层结点都集中在该层最左边的若干位置结点数，最后一层结点都集中在该层最左边的若干位置