《数据结构》课件(C语言)new精品.ppt

世界是平衡的 我们希望选用一个所占存储空间小、运行时间短、其它性能也好的算法。然而，实际上很难做到十全十美。原因是上述要求有时相互抵触，要节约算法的执行时间往往要以牺牲更多的空间为代价，而为了节省空间可能耗费更多的计算时间。因此我们只能根据具体情况有所侧重。 若该程序使用次数较少，则力求算法简明易懂； 对于反复多次使用的程序，应尽可能选用快速的算法； 若待解决的问题数据量极大，机器的存储空间较小，则相应算法主要考虑如何节省空间。 关于空间复杂度的分析 例: 数组的转置 关于时间复杂度的分析 一个算法所耗费的时间，应该是该算法中每条语句的执行时间之和，而每条语句的执行时间是该语句的执行次数(也称为频度(Frequency Count))与该语句执行一次所需时间的乘积。 常数阶O(1) 对数阶O(1og2n) 线性阶O(n) 线性对数阶O(nlog2n) O(n2)、O(n3)、…、O(nk)、 指数阶O(2n)。 第一章 小结 基本内容 *数据和数据结构等名词和术语的确定含义 *抽象数据类型（ADT） *描述算法的类C语言 *从时间和空间角度分析算法的方法 学习要点 *熟悉各名词、术语的含义，掌握基本概念，特别是数据的逻辑结构和存储结构之间的关系 *了解怎样以ADT的角度来描述数据结构 *熟悉类C语言的书写规范 *理解算法五要素 *掌握计算语句频度和估算算法时间复杂度的方法 第一章 小结 算法设计的基本步骤 明确需求 构造数学模型 设计算法 正确性验证 算法效率的分析 算法的实现 程序的测试与排错 编写文档资料 作业 ① 请在下次课前完成第1章自测卷全部内容4 复习C语言，重点是结构类型和递归概念 逻辑结构定义了数据的逻辑关系，物理结构是逻辑结构的具体实现。由于物理存储结构不同导致算法处理不同，但是仍然是实现逻辑结构中定义的内容。 讲述为什么。计算机处理和表示与人们自然理解和表述之间存在巨大差异。为缩小差距，易于理解、使用、构造，需要封装，这个过程就是抽象的过程。数据类型的抽象方法和表示以ADT来描述。 算法 == 程序 ？ 算法是为了描述解决某一问题的方法，而不涉及具体的实现细节。 算法存在的辨证关系数据结构与算法的辨证关系 给定了数据的逻辑结构后，对同一逻辑结构而言，由于存储结构的不同，定义的运算也是不同的。 如线性表是一种逻辑结构，若采用顺序存储方法表示，则称为顺序表；若采用链式存储方法表示，则称为链表。 相同的运算在顺序表和链表上的实现方法是不同的。 ● 算法的概念 4、算法的描述和算法分析 算法(Algorithm)是对特定问题求解步骤的一种描述，是能在计算机上经过有限时间完成的、毫不含糊的指令的有限序列。其中每一条指令表示一个或多个操作。 问题（Problem）是一个函数，或是输入和输出的一种联系。程序（Program）是用计算机程序设计语言实现的完成一定功能的代码。 算法的实现一定是程序，但程序不一定是算法的实现。 4、算法的描述和算法分析 算法的五个重要特性 1）有穷性：执行有限步，每步均在有穷时间内完成。 2）确定性：对相同的输入，必产生相同的输出，即无二义性。 3）可行性：计算机可使用已实现的基本运算执行有限次来完成。 4）输入：零个或多个输入。 5）输出：一个或多个输出。 4、算法的描述和算法分析 关于算法性质的另一种描述 1、正确性(Correctness) 它必须完成所期望的功能，把每一次输入转化为正确的输出。 2、具体步骤(Concrete Steps) 一个算法应该由一系列具体步骤组成。 3、确定性(No Ambiguity) 下一步（通常是指算法描述中的下一步）应执行的步骤必须明确。 4、有限性(Finite) 一个算法必须由有限步组成。 5、可终止性(Terminable) 算法必须可以终止，即不能进入死循环。 ●算法的描述 4、算法的描述和算法分析 一个算法可以用各种不同的方法来进行描述。比如可使用某种高级语言、汇编语言甚至机器语言来描述某个算法，亦可使用伪码语言或框图等其它形式来描述它。 ●算法的描述 4、算法的描述和算法分析 描述算法的语言形式 1.文字形式:用中文或英文这样的文字来描述算法。 2.伪码形式:用一种仿程序设计语言的语言来描述算法。 3.程序设计语言形式:用某种程序设计语言描述算法。其优点是算法不用修改，直接作为程序语句键入计算机，计算机能调用和运行。这里我们采用上讲介绍的类C语言来描述算法 4、算法的描述和算法分析 例:设计一个把存储在数组中