算法与数据结构-算法与流程算法与数据结构-算法与流程图算法与数据结构-算法与流程图算法与数据结构-算法与流程图.ppt

算法与流程图 第章 目标 数据结构与算法 C程序的基本结构 用流程图描述算法 用C语言描述算法 算法设计要求 正确性 程序对于典型、苛刻而带有刁难性的几组输入数据能够得出满足规格说明要求的结果 可读性 健壮性 当输入数据非法时，能够适当地做出反应或者进行处理，而不会产生莫名其妙的结果 效率与低存储量需求 算法实现 文档 伪代码 N-S图 流程图 代码 自然语言 算法例子 从键盘中输入100个整数，对其中的正整数进行累加，最后输出结果。 算法描述（自然语言） 1、输入一个数； 2、如果该数0,累加它； 3、如果100个数没有输入完，转步骤1; 4、输入完100个数后，输出累加和。 算法描述（流程图） 算法描述（N-S流程图） 算法的C语句实现 流程图符号 C程序的基本结构 顺序结构 选择结构 循环结构 顺序结构3-1 顺序结构3-2 顺序结构3-3 选择结构2-1 选择结构2-2 循环结构2-1 循环结构2-2 从键盘输入9 个数，找出最大值 流程图的画法 演示使用visio画流程图…… 结构化程序设计基本要求 自顶向下，模块化设计 使用三种基本结构构造程序 程序书写规范，切勿随心所欲 清晰第一，效率第二 思路清晰 书写清晰（变量名、函数、注解等） 书写注意缩进 总结 算法和数据结构 用流程图描述算法 用C语言描术算法 (4) 关于数据存储结构的类型定义以及全局变量的说明等均应在写算法之前进行说明。 下面的例子给出了书写算法的一般步骤。 例1.1 有n个整数，将它们按由大到小的顺序排序，并且输出。 分析：n个数据的逻辑结构是线性表(a1,a2,a3,…,an)；选用一维数组作存储结构。 用C语言实现算法5-4 用C语言实现算法5-5 /*数组a的数据由主函数提供*/ 著名的计算机科学家N.沃思提出了一个有名的公式：算法+数据结构=程序。由此可见，数据结构和算法是程序的两大要素，二者相辅相成，缺一不可。一种数据结构的优劣是在实现其各种运算的算法中体现的。对数据结构的分析实质上也就是对实现其多种运算的算法的分析。评价一个算法应从四个方面进行：正确性、简单性、运行时间、占用空间。但主要看这个算法所要占用机器资源的多少。而在这些资源中时间和空间是两个最主要的方面，因此算法分析中最关心的也就是算法所需的时间代价和空间代价。 算法分析4-1 1. 空间 所谓算法的空间代价(或称空间复杂性)，是指当问题的规模以某种单位由1增至n时，解决该问题的算法实现所占用的空间也以某种单位由1增至f(n)，并称该算法的空间代价是f(n)。 算法分析4-2 2. 时间 (1) 语句频度(Frequency Count)：指的是在一个算法中该语句重复执行的次数。 (2) 算法的渐近时间复杂度(Asymptotic Time Complexity)：算法中基本操作重复执行的次数依据算法中最大语句频度来估算，它是问题规模n的某个函数f(n)，算法的时间量度记作T(n)=O(f(n))，表示随着问题规模n的增大，算法执行时间的增长率和f(n)的增长率相同，称作算法的渐近时间复杂度，简称时间复杂度。时间复杂度往往不是精确的执行次数，而是估算的数量级。它着重体现的是随着问题规模的增大，算法执行时间增长的变化趋势。 算法分析4-3 例如，在下列三个程序段中： (a) x=x+1; (b) for(i=1;i=n;i++) x=x+1; (c) for(j=1;j=n;j++) for(k=1;k=n;k++) x=x+1; 语句x=x+1的频度分别为1、n和 ，则(a)、(b)、(c)的时间复杂度分别是O(1)、O(n)、O( )。由此可见，随着问题规模的增大，其时间消耗也在增大。 算法分析4-4：常用算法实现与分析 图与网的定义和术语 图与网的定义和术语 引例： 首先分析学籍档案类问题。设一个班级有50个学生，这个班级的学籍表如表所示。 我们可以把表中每个学生的信息看成一个记录，表中的每个记录又由7个数据项组成。该学籍表由50个记录组成，记录之间是一种顺序关系。这种表通常称为线性表，数据之间的逻辑结构称为线性结构，其主要操作有检索、查找、插入或删除等。 学 籍 表 序号 学号 姓名 性别 英语 数学 物理 01李明 男 86 91 80 02马琳 男 76 83 85 50刘薇薇 女 88 93 90 数据结构的基本概念和术语6-1 图与网的定义和术语 又如，