C语言概述、算法介绍.ppt

第一章 C概述、算法描述,主要内容,C语言概述 算法,（一）C语言概述,内容,C语言出现的历史背景 C语言的特点 简单的C程序介绍 运行C程序的步骤,历史背景,C语言出现的历史背景,C语言是国际上广泛流行的计算机高级语言,既可用来写系统软件，也可用来写应用软件。 C语言是在B语言的基础上发展起来的，它的根源可以追溯到ALGOL 60。,特点,C语言特点,语言简洁、紧凑，使用方便、灵活。 运算符丰富。 数据结构丰富，具有现代化语言的各种数据结构。 具有结构化的控制语句。 语法限制不太严格，程序设计自由度大。 语言能进行位(bit)操作，能实现汇编语言的大部分功能，可以直接对硬件进行操作。 生成目标代码质量高，程序执行效率高。 用C语言编写的程序可移植性好（与汇编语言比）。,C语言在编程语言中的位置,有人把C称为“高级语言中的低级语言” 或“中级语言”，意为兼有高级和低级语言的特点。按此观点可将各语言分类如下： 高级: BASIC,FORTRAN,COBOL,PASCAL,Ada,Modula-2； 中级: C,FORTH,宏汇编； 低级: 汇编语言 一般仍习惯将C语言称为高级语言，因为C程序也要通过编译、链接才能得到可执行的目标程序，这是和其他高级语言相同的。,程序示例,C程序 (例1.2),例 1.2 求两数和 #include int main() int a; int b; int sum; a = 123; b = 456; sum = a+b; printf (“sum is %d/n“， sum); return 1； ,C程序（例1.3）,例1.3 求两个数中的较大者 #include int max(int x，int y); / 前向声明 int main ( )/* 主函数*/ int a， b， c; /*声明部分，定义变量*/ scanf (“%d，%d“， ,C程序介绍(例1.3续1),/ 定义max函数，函数值为整型， 形式参数x，y为整型 int max(int x，int y) int z; if (x y) z=x; else z=y; return z; ,C程序（例1.3续2）,max()函数的另两种写法： 一种： int max(int x，int y) return x = y ? x : y; 另一种：用宏实现 #define MAX(x, y) (x) = (y) ? (x) : (y),运行C程序步骤,预备知识,程序：一组计算机能识别和执行的指令。 源程序：用高级语言编写的程序。 计算机只能识别和执行由0和1组成的二进制指令，而不能识别和执行用高级语言写的指令。 编译：为了使计算机能执行高级语言源程序，必须先用一种称为“编译程序”的软件，把源程序翻译成二进制形式的“目标程序”。 链接：把目标程序与系统的函数库以及其他目标程序链接起来，形成可执行程序。,运行C程序流程图,（二）算法,总述,程序包含以下两方面： 数据 数据的类型和数据的组织形式，即数据结构。 操作 即操作步骤，也就是算法。 它们的关系： 数据是操作的对象，操作的目的是对数据进行加工处理，以得到期望的结果。 数据结构 算法 程序,总述,程序除了上述两个要素之外，还包括程序设计方法和计算机语言。 因此，一个程序员应具备如下知识： 算法 数据结构 程序设计方法 语言,内容,算法的概念 算法举例 算法特性 算法表示方法 结构化的程序设计方法,算法的概念,算法的概念,为解决一个问题而采取的方法和步骤，就称为算法。 生活中同样存在算法：吃饭、上学、跳舞 算法分类： 数值运算算法 非数值运算算法：常见的是用于事务管理。,算法举例,例2.1,问题描述：求1*2*3*4*5。 方法一：用最原始的方法进行： 步骤1：先求1*2，得到结果2。 步骤2：将步骤2得到的结果再乘以3，得到结 果6。 步骤3：将6乘以4，得到24。 步骤4：将24乘以5，得到120。,例2.1（方法二）,设两个变量分别代表被乘数和乘数，不另外设变量存放结果，而直接将每一步的乘积放在被乘数变量中。 p：被乘数，i：乘数。用循环算法求结果。 步骤： S1：使p = 1 S2：使i = 2 S3：使p*i，乘积仍放在变量p中：p*i p S4：使i的值加1，即：i+1 i S5：如果i不大于5，返回S3重新执行；否则，算法结束。,例2.1（问题变化）,问题改为：求1*3*5*7*9*11。 算法只需作很少的改动： S1：1 p S2：3 i S3：p*i p S4：i+2 i S5：若i = 11，返回S3；否则，结束。 思考：仔细分析循环结束的条件，即S5步骤，如果将S5修改为：i 11，返回S3。 会有什么问题？,例2.1（总结）,方法二具有通用性，灵活性。,例2.2,问题描述：有50个学生，要求将他们之中成绩在80分以上的学号和成绩输出。 解决方法：用数组n表示学生学号，n0代表代表第一个学生，ni代表第i+1个学生学号。用数组g代表学生成绩，gi代表第i+1个学生成绩。算法如下： S1：0 i S2：如果gi = 80，则输出ni和gi；否则，不输出 S3：i+1 i S4：如果 i 50，返回S2继续执行；否则，算法结束。,例2.3,问题描述：判断20002500年中的每一年是否闰年，将结果输出。 闰年的条件： 1）能被4整除，但不能被100整除的年份都是闰年，如1996年。 2）能被100整除，又能被400整除的年份是闰年。如2000年。 3）不符合上述条件的年份都不是闰年。,例2.3（算法）,算法如下（设y为被检测的年份）： S1：2000 y； S2：若y不能被4整除，则输出y“不是闰年”。然后转到S6； S3：若y能被4整除，不能被100整除，则输出y“是闰年”。然后转到S6； S4：若y能被100整除，又能被400整除，输出y“是闰年”，然后转到S6； S5：输出y“不是闰年”； S6：y+1 y； S7：当 y = 2500时，继续执行，否则，算法结束。,算法特性,算法特性,有穷性 一个算法应包含有限的操作步骤，而不能时无限的。 注意：“有穷性”往往指“在合理的范围之内”。 确定性 算法中的每一步都是确定的，不能是含糊的、模棱两可的。 有零个或者多个输入。 所谓输入是指执行算法时需要从外界取得必要的信息。 有一个或者多个输出。 注意，一个算法的输出不一定是打印输出，一个算法得到的结果就是算法输出。 没有输出的算法是没有意义的。 有效性。 算法中的每一步都应能有效地执行，并得到结果。,算法表示方法,常用的算法表示方法,用自然语言表示 用传统流程图表示 用结构流程图表示 用伪代码表示 用计算机语言表示,用自然语言表示,前面介绍的算法就是用自然语言表示的。 优点： 通俗易懂 缺点： 1）文字冗长，容易出现歧义。 2）表示分支和循环算法不方便。,用传统流程图表示,处理框,起始框,输入输出框,判断框,流程线,用传统流程图表示例2.1算法,用传统流程图表示例2.2算法,流程图内容,一个流程图包括以下几部分： 1）表示相应操作的框。 2）带箭头的流程线。 3）框内外必要的文字说明。 特别提醒：流程线不要忘记画箭头，因为它是反映流程执行先后次序。,传统流程图优缺点,优点： 1）表示算法清楚、直观，能比较清楚地显示出各个框之间的逻辑关系。 缺点 1)流程图占用篇幅较多，尤其当算法比较复杂时，画流程图既费时又不方便。 2）对流程的使用没有严格限制，使用者可用毫不受限制地使用流程随意转来转去，使流程变得毫无规律，如果出现这这情况，就使人难以理解。 解决办法： 限制箭头的滥用，不允许无规律地使流程随意转向。,结构化程序设计方法,结构化的程序设计方法,结构化的程序设计方法强调程序设计风格和程序结构的规范化，提倡清晰的结构。 基本思路： 把一个复杂问题的求解过程分阶段进行，每个阶段处理的问题都控制在人们容易理解和处理的范围内。 方法： 1）自顶向下； 2）逐步细化； 3）模块化设计； 4）结构化编码。