数据结构（第6版）高职全套教学课件.pptx

数据结构;第1章 绪 论;第1章 绪 论;第1章 绪 论;例1.1 电话号码自动查找问题。;例1.2 计算机磁盘中文件的目录结构。 ;网络结构示意图统。它是由各个 网站和终端用户所组成，利用网线或电话线连接到一起的。;1.2 数据的逻辑结构;2. 数据元素（Data Element） 数据元素是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。 但它还可以分割成若干个具有不同属性的项（字段）。数据元素一般由一个或多个数据项组成。;3. 数据项（Data Item） 数据项是具有独立意义的最小数据单位，是对数据元素属性的描述。;4. 数据类型（Data Type） 数据类型是一组性质相同的值的集合以及定义于这个值的集合上的一组操作的总称。每个数据项属于某一确定的基本数据类型。;5. 数据对象（Data Object） 数据对象是性质相同的数据元素的集合，是数据的一个子集。例如，整数数据对象的集合是｛0，±1，±2，…｝;字母字符数据对象的集合是｛′A′，′B′，′C′，…，′Z′｝;电话号码查找系统中，数据对象就是全体电话用户。;6. 数据结构（Data Structure） 数据结构的基本含义是指数据元素之间的关系，它是按照某种关系组织起来的一批数据，以一定的存储方式把它们存储到计算机存储器中，并在这些数据上定义了一个运算的集合。 在任何问题中，数据元素都不是孤立存在的，而是在它们之间存在着某种关系，数据元素之间的这种相互关系就称为结构，带有结构的数据对象称为数据结构。;1.2.2 数据的逻辑结构;（a） 集合结构示意图;数据结构可用二元组S=（D，R）的形式来描述。其中，D表示数据元素的集合，R表示D上关系的集合。 关于二元组S=（D，R）中前驱和后继的关系，可以描述如下，假设a1，a2是D中的两个元素，则在二元组a1，a2中，a1是a2的直接前驱，a2是a1的直接后继。;例1.4 用上面的数学方法给出一周七天的数据逻辑结构。设a1、 a2、 a3、 a4、 a5、 a6、 a7分别表示星期一至星期日，这是线性结构。;例1.5 设一个数据结构的抽象描述为 S=｛D，R｝，其中: D=｛1，2，3，4，5，6，7，8｝ R=｛1，2，1，3，1，4，2，5，2，6，4，7，4，8｝ ;1.3 算法的描述;算法满足以下5个性质: 输入:一个算法可以有0个或多个输入量，在算法执行之前提供给算法。 输出:一个算法的执行结果要有一个或多个输出量，它是算法对输入数据处理的结果。 有穷性:一个算法必须在执行有穷步骤之后结束，并且每一步骤也都必须在有限的时间之内完成。 确定性:算法中的每一步骤都有明确的含义，没有二义性。 可行性:算法中描述的每一个操作，都可以通过已经实现的基本运算，执行有限次后来完成。;1.3.2 算法的设计要求;（2） 可读性 算法是对特定问题求解步骤的一种描述，它要转变成计算机可执行的程序，同时必须可以供他人使用。为了阅读与交流，所设计的算法要让他人能看懂，在算法或程序中可以增加一些注释来提高可读性。;（3） 健壮性 当输入的数据不符合要求时，算法应能判断出数据的非法性，并能进行适当的处理。 比如，暂停或终止程序的执行，显示错误信息等。不允许产生不可预料的结果。;（4） 高效性 算法的效率是指算法执行的时间和占用的存储空间。如果对于同一个问题有多个算法可供选择，应尽可能选择执行时间短、占用空间少的算法。;1.3.3 算法的评价;（1） 时间效率 时间效率就是考虑一个算法运行时所需时间的多少。 一个算法运行所需要的时间与算法中语句执行的次数成正比，如果算法中语句重复执行的次数越多，所需要的时间也就越多。 时间复杂度一般不是算法的精确执行次数，而是结算的数量级。它着重体现的是随着问题规模的增大，算法执行时间增长的变化趋势。;例1.6 求下列4个程序段的语句频度。;（a）是一个没有循环算法的基本操作，它的语句频度与问题规模没有关系，记作 T（n） =O（1）， 也称为常量阶。 （b）是一个一重循环的算法，它的语句频度随问题规模 n的增大而呈线性增大，这种线性关系记作 T（n）=O（n）， 也称线性阶。 （c）是一个二重循环的算法，它的语句频度为 n2，记作T（n）=O（n2）， 称为平方阶。 （d）是一个三重循环的算法，它的语句频度为 n3 ，记作T（n）=O（n3 ）， 称为立方阶。 ;（2） 空间效率 一个算法在执行过程中所占用的存储空间大小，称为空间效率或空间