C语言程序设计（谭浩强）_02.pptVIP

程序=数据结构+算法 §2.1算法的概念 算法是解决一个问题而采取的方法和步骤。这里仅限于计算机算法，用计算机解决某一问题而用的方法和步骤。 2.1.1计算机算法分类 1. 数值运算算法 （《数值分析》《数值方法》） ①例如 数值积分： ②线性方程组的求解： 如果|A|≠0。 2. 非数值算法 包括排序，查找，图形操作等问题。 例如排序问题，N个整数排序。 §2.2 算法举例 1 简单算法 求和：1+2+3……+100 1：S=0 2：i=1 3：S+i的值给S 4：i+1的值给i 5： 判断i=100，如果i=100执行3，4，5，否则算法结束。 6：打印S的值 这就是一个简单的算法，i，S各占用一个存储单元。 §2.3 算法的性质 1.有穷性 操作步骤是有限的，不能无限。 2.确定性 算法中每一个步骤都是明确的,不能是模糊的 3.有零个或多个输入 可以从外界输入必要的信息. 4.有一个或多个输出 输出解或结果，没有输出的算法是没有意义的。 5.有效性 每一步能有效执行，并得到确定的结果。 §2.4 算法的表示 2.4.1用自然语言表示算法 2.4.2用流程图表示 1.ANSI表示 2.三种基本结构 1966年 Bohra Jacopini 提出三种结构： （1）顺序结构 （2）选择结构（选取结构，分支结构） （3）循环结构 2.4.3 N-S流程图 1973年，美国 I，Nassi.B.Shneiderman 提出了一种新的流程图形式。 1.N-S流程图的流程图符号 ①顺序结构 ②选择结构 ③循环结构 §2.5结构化程序设计方法 “自顶向下，逐步细化”是一种系统分解的方法。根据需要解决的问题，对问题根据功能进行系统的分类。将一个大的复杂的系统解成若干子系统，每一个子系统完成原系统的某一项或多项功能。同时每一子系统又可划分若干子系统，就像树根，逐步细化，进入第二层，第三层……设计。 程序按功能模块划分为若干基本模块（子过程），每个子过程具有一定的功能，这些过程通过参数传递数据。数据和过程分离为相对独立的实体。 如下图： 结构化方法 2.分解模块的原则 （1）简明性（单功能度） 每一模块应简单易懂，易于实现，且模块仅执行一种功能。 （2）独立性 要求各模块相对独立，修改其中某一模块而不影响其它模块，减少各模块间数据联系。 (3)完整性 每一个模块独立完整，不要求一个模块完成多种功能，也不要求多个模块完成一个功能。 （4）一进一出原则 单个入口和单个出口。 （5）模块大小 100行左右（2页），分解基本功能即可。 例：将1到1000之间的素数打印出来。 （1）问题分析。 算法采用 Eratosthenes（埃拉托色尼）筛法.就将1-1000间的非素数挖掉。其余是素数。 （2）因此，选择数据结构，可以用数组，或不用数组，未挖掉数立即打印出来； （3）C 语言开发平台 （4）采用结构化编程； 算法：进行细化 * * 烟台大学 机电汽车工程学院 刘 鹏 第2章 算 法 数据结构是指数据的类型和数据的组成形式：诸如线性表，集合，树，图。 算法是用计算机解决某一问题的方法步骤。 梯形法 抛物线法 2 排序问题 将1 4 7 3 9 5从小到大排序 （1）冒泡排序 ：从左向右，相邻两个数进行比较，如果逆序则交换位置 1次扫描 ：1 4 3 7 5 9 2次扫描 ：1 3 4 5 7 9 （2）选择排序 ：从左向右，依次取数与后面的数进行比较，如果逆序则交换位置 1次扫描 ：1 4 7 3 9 5 4次扫描 ：1 3 4 5 9 7 3次扫描 ：1 3 4 7 9 5 2次扫描 ：1 3 7 4 9 5 5次扫描 ：1 3 4 5 7 9 起止框 输入输出框 判断框 处理框 ↓或 → 流程线 ○ 连接点 ----[ 注释框 特点：直观形象，清晰易懂，易于找错，但必须限制 箭头的滥用 A B 顺序结构 选择结构 p A B Y N p A p A “当型”循环 While “直到型”循环 Until 只有一个入口 只有一个出口 结构的每一部分都可能被执行到 结构不存在“死”循环 Y N Y N 开 始 0=s，1= i I=100? i+1=i 结束 s+i=s Y N s=1+2+……+100 算法流程图 输出s A B Y P N A B 当P成立 A 直到P成立 A 0=s 1=i 当P成立 s=s+i i=1+i 输出s 2.4.4用伪代码表示 伪代码与自然语言和计算机语言间的文字和符号来描述算法。其符号可为汉字或定义计算机语言的关键字。 例s=1+2+……+100 begin