c语言概述算法

1、c c语言概述算法语言概述算法 c c语言概述算法语言概述算法 c c语言概述算法语言概述算法 第第4 4页页 共共5353页页c c语言概述算法语言概述算法 C C语言是国际上广泛流行的高级语言。语言是国际上广泛流行的高级语言。 19631963年年, ,剑桥剑桥,CPL,CPL语言语言, ,更近硬件更近硬件, ,但规模大但规模大, ,难以实现难以实现. . 19671967年年, ,剑桥剑桥,Martin Richards,Martin Richards,简化简化,BCPL,BCPL语言语言. . 19701970年年, ,美国贝尔实验室美国贝尔实验室,Ken Thompson,Ken T

2、hompson,简化简化,B,B语言语言, ,写写 第一个第一个UNIXUNIX系统系统. . 1972197219731973年年, ,贝尔实验室贝尔实验室,D.M.Ritchie,B,D.M.Ritchie,B语言基础上语言基础上, , 设计出设计出C C语言语言, ,克服克服B B语言的过于简单、功能有限的不足语言的过于简单、功能有限的不足. . 19731973年，年，K.ThompsonK.Thompson和和D.M.RitchieD.M.Ritchie合作将合作将UNIXUNIX的的90%90%以以 上用上用C C改写改写. . 19781978年以后年以后,C,C语言已先后移植到

3、大、中、小、微型机上语言已先后移植到大、中、小、微型机上 已独立于已独立于UNIXUNIX和和PDPPDP，得以广泛应用。，得以广泛应用。 第第5 5页页 共共5353页页c c语言概述算法语言概述算法 Dennis MDennis MRitchieRitchie：19671967年加入贝年加入贝 尔实验室。他和尔实验室。他和Ken LKen LThompsonThompson两两 人共同设计并实现了人共同设计并实现了C C语言语言, , 改变了改变了 程序设计语言发展的轨迹，是程序设程序设计语言发展的轨迹，是程序设 计语言发展过程中的一个重要里程碑。计语言发展过程中的一个重要里程碑。 与此同

4、时，他们两人还设计并实现了与此同时，他们两人还设计并实现了 UNIXUNIX操作系统。正是由于这两项巨大操作系统。正是由于这两项巨大 贡献，贡献，Dennis MDennis MRitchieRitchie于于19831983年年 获得了计算机界的最高奖获得了计算机界的最高奖图灵奖。图灵奖。 此外，他还获得了此外，他还获得了ACMACM、IEEEIEEE、贝尔、贝尔 实验室等授予的多种奖项。实验室等授予的多种奖项。 第第6 6页页 共共5353页页c c语言概述算法语言概述算法 Brian WBrian WKernighanKernighan：是贝尔实：是贝尔实 验室计算科学研究中心高级研究验

5、室计算科学研究中心高级研究 人员，著名的计算机科学家。他人员，著名的计算机科学家。他 参加了参加了UNIXUNIX系统、系统、C C语言、语言、AWKAWK语语 言和许多其他系统的开发，同时言和许多其他系统的开发，同时 出版了许多在计算机领域具有影出版了许多在计算机领域具有影 响的著作。响的著作。 第第7 7页页 共共5353页页c c语言概述算法语言概述算法 C C语言的产生和地位语言的产生和地位 原书名：原书名： The C Programming Language 作者：作者： （美）（美）Brian W.Kernighan, Dennis M.Ritchie 本书原著即为本书原著即为C

6、 C语言的设计者之一语言的设计者之一Dennis MDennis MRitchieRitchie和著名和著名 的计算机科学家的计算机科学家Brian WBrian WKernighanKernighan合著的合著的 一本介绍一本介绍C C语言语言 的权威经典著作。的权威经典著作。 C语言已经成为全球程序员的公 共语言，并由此诞生了两个新的主流 语言C+与Java，它们都建立在C语言 的语法和基本结构的基础上。现在世 界上的许多软件都是在C语及其衍生 的各种语言的基础上开发出来的。 第第8 8页页 共共5353页页c c语言概述算法语言概述算法 l 可进行内存物理地址访问，具有汇编语言的特点可进

7、行内存物理地址访问，具有汇编语言的特点 l 控制流程结构化，以函数为基本结构进行流程控制控制流程结构化，以函数为基本结构进行流程控制 l l 具有构造数据类型的能力，数据结构系统化具有构造数据类型的能力，数据结构系统化 l 第第9 9页页 共共5353页页c c语言概述算法语言概述算法 例例1:/* 显示显示 “ How are you!” */ #include main( ) printf(How are you!); 程序运行结果是输出程序运行结果是输出: : HowHow are you!are you! 第第1010页页 共共5353页页c c语言概述算法语言概述算法 /*/表示注释

8、。注释只是给人看的,对编译和运 行不起作用。所以可以用汉字或英文字符表示，可以出现在 一行中的最右侧，也可以单独成为一行。 输出一行信息：输出一行信息：sum is 579sum is 579 第第1111页页 共共5353页页c c语言概述算法语言概述算法 例例3: 从键盘输入两个整数，并显示这两个整数之和。从键盘输入两个整数，并显示这两个整数之和。 int ADDxy(int a,int b) int c; c=a+b; return(c); main( ) int x,y,z; scanf(“%d%d”, z=ADDxy(x,y); printf(“sum=%dn”, z); 主函数 子

9、函数 程序运行情况如下程序运行情况如下： 8 5 8 5 sum=13 sum=13 第第1212页页 共共5353页页c c语言概述算法语言概述算法 (1) C(1) C程序是由函数构成的程序是由函数构成的, ,程序容易实现模块化。程序容易实现模块化。 main( ) /* 主函数说明主函数说明 */ 变量定义变量定义 /* 主函数体主函数体 */ 执行语句组执行语句组 子函数名子函数名1(参数参数) /* 子子函数函数说明说明 */ 变量定义变量定义 /* 子函数体子函数体 */ 执行语句组执行语句组 子函数名子函数名2(参数参数) /* 子函数说明子函数说明 */ 变量定义变量定义 /*

10、 子函数体子函数体 */ 执行语句组执行语句组 第第1313页页 共共5353页页c c语言概述算法语言概述算法 (2) (2) 一个函数由两部分组成一个函数由两部分组成: : 函数的首部：函数的首部：例例3 3中的中的AddxyAddxy函数首部函数首部 int Addxy(int x,int y ) 函数体：函数体：花括号内的部分。若一个函数有多个花花括号内的部分。若一个函数有多个花 括号括号, ,则最外层的一对花括号为函数体的范围。则最外层的一对花括号为函数体的范围。 (3) C(3) C程序总是从程序总是从mainmain函数开始执行的函数开始执行的, ,与与mainmain函数函数

11、的位置无关。的位置无关。 (4) C(4) C程序书写格式自由程序书写格式自由, ,一行内可以写几个语句一行内可以写几个语句, , 一个语句可以分写在多行上，一个语句可以分写在多行上，C C程序没有行号。程序没有行号。 第第1414页页 共共5353页页c c语言概述算法语言概述算法 (5) (5) 每个语句和数据声明的最后必须有一个分号。每个语句和数据声明的最后必须有一个分号。 (6) C(6) C语言本身没有输入输出语句。输入和输出的操作语言本身没有输入输出语句。输入和输出的操作 是由库函数是由库函数scanfscanf和和printfprintf等函数来完成的等函数来完成的 (7) (7

12、) 在在C C语言中，大小写字母是有区别的。（语言中，大小写字母是有区别的。（C C语言习语言习 惯用小写字母）惯用小写字母） (8) (8) 书写程序时，最好使用规范的缩进格式的形式。书写程序时，最好使用规范的缩进格式的形式。 (9) C(9) C程序注释程序注释/ /* * */ /可以写在程序的任何位置上可以写在程序的任何位置上 第第1515页页 共共5353页页c c语言概述算法语言概述算法 1.1. 上机输入、编辑源程序上机输入、编辑源程序 对源程序进行编译对源程序进行编译 与库函数连接与库函数连接 运行目标程序运行目标程序 第第1616页页 共共5353页页c c语言概述算法语言概

13、述算法 l 目前使用的大多数目前使用的大多数C C编译系统编译系统都是集成环境的。都是集成环境的。 可以用不同的编译系统对可以用不同的编译系统对C C程序进行操作程序进行操作 l 常用的有常用的有Turbo C 2.0Turbo C 2.0、Turbo C+ 3.0Turbo C+ 3.0、 Visual C+Visual C+等等 l Turbo C+ 3.0Turbo C+ 3.0：是一个集成环境，它具有方便、是一个集成环境，它具有方便、 直观和易用的界面，虽然它也是直观和易用的界面，虽然它也是DOSDOS环境下的集成环境下的集成 环境，但是可以把执行文件环境，但是可以把执行文件tc.ex

14、etc.exe生成快捷方式生成快捷方式 放在放在WindowsWindows桌面上，可以支持鼠标操作。桌面上，可以支持鼠标操作。 l Visual C+ 6.0Visual C+ 6.0：可视化面向对象开发环境，可视化面向对象开发环境， 可以用可以用Visual C+Visual C+对对C C程序进行编译。程序进行编译。 第第1717页页 共共5353页页c c语言概述算法语言概述算法 1.1.学习学习C C语言的语法语言的语法 数据表达：数据表达： 变量定义、正确书写表达式变量定义、正确书写表达式 流程控制：流程控制： if(ab) x=a; else x=b; sum=0;i=1; wh

15、ile(i=5) sum=sum+i; i=i+1; for(i=1;sum=0;i=80 输出输出gi i+1 i i50 结束结束 成立成立 不成立不成立 不成立不成立 成立成立 传统流程图用流传统流程图用流 程线指出各框的程线指出各框的 执行顺序，对流执行顺序，对流 程线的使用没有程线的使用没有 严格限制。严格限制。 第第4040页页 共共5353页页c c语言概述算法语言概述算法 传统流程图的流程可以是： 缺点：缺点：使用者可以毫不受限制地使流程随意地转向，使用者可以毫不受限制地使流程随意地转向， 使流程图变得毫无规律，难以阅读、修改，使算法的使流程图变得毫无规律，难以阅读、修改，使算

16、法的 可靠性和可维护性难以保证。可靠性和可维护性难以保证。 解决办法：解决办法：必须限制箭头的滥用，即不允许无规律地必须限制箭头的滥用，即不允许无规律地 使流程随意转向，只能顺序的进行下去。使流程随意转向，只能顺序的进行下去。 第第4141页页 共共5353页页c c语言概述算法语言概述算法 （3 3）N NS S流程图流程图 N-SN-S流程图流程图 由美国学者由美国学者I.NassiI.Nassi和和B.ShneidermanB.Shneiderman提出表提出表 示算法的图形工具。基本单元是矩形框示算法的图形工具。基本单元是矩形框, ,用不同用不同 的形状线分割的形状线分割, ,表示三种

17、结构。只有一个入口表示三种结构。只有一个入口, ,一一 个出口个出口, ,没有流程线。没有流程线。 N-SN-S图的优点图的优点 比文字描述直观、形象、比文字描述直观、形象、 易于理解；比传易于理解；比传 统流程图紧凑易画。尤其是它废除了流程线，整统流程图紧凑易画。尤其是它废除了流程线，整 个算法结构是由各个基本结构按顺序组成的，个算法结构是由各个基本结构按顺序组成的，N-N- -S-S流程图中的上下顺序就是执行时的顺序。流程图中的上下顺序就是执行时的顺序。 第第4242页页 共共5353页页c c语言概述算法语言概述算法 三种基本程序结构的三种基本程序结构的NSNS流程图流程图 条件条件 T

18、F 语句1 语句2 2.2.选择结构选择结构 语句1 语句2 1.1.顺序结构顺序结构 3.3.循环结构循环结构 循环体循环体 循环体循环体 当满足条件时当满足条件时 直到条件成立直到条件成立 循环结构一循环结构一 循环结构二循环结构二 第第4343页页 共共5353页页c c语言概述算法语言概述算法 0t,0i i+1i t+it 直到直到 i 100 输出输出 t 的值的值 传统流程图与传统流程图与N-SN-S流程图的比较流程图的比较 i 100 N Y 开始开始 0t,0i i+1i t+it 输出输出 t 的值的值 结束结束 例例1 1：1+2+3+1+2+3+ + 加到加到10010

19、0为止为止 第第4444页页 共共5353页页c c语言概述算法语言概述算法 例：例：打印打印5050名学名学 生中成绩高于生中成绩高于 8080分的学号和分的学号和 成绩用成绩用N-SN-S图表图表 示。示。 第第4545页页 共共5353页页c c语言概述算法语言概述算法 1. 1. 枚举法（穷举法）枚举法（穷举法） 特点特点: :算法简单，容易理解，运算量大。算法简单，容易理解，运算量大。 基本思想：基本思想： 根据题目的部分条件确定答案的大致范根据题目的部分条件确定答案的大致范 围，然后在此范围内对所有可能的情况逐围，然后在此范围内对所有可能的情况逐 一验证，直到所有情况均通过验证。若

20、某一验证，直到所有情况均通过验证。若某 个情况符合题目条件，则为本题的一个答个情况符合题目条件，则为本题的一个答 案；若全部情况验证完后均不符合题目的案；若全部情况验证完后均不符合题目的 条件，则问题无解。条件，则问题无解。 2.3 2.3 几种常用算法介绍几种常用算法介绍 第第4646页页 共共5353页页c c语言概述算法语言概述算法 如：如： 百元买百鸡问题。假定小鸡每只百元买百鸡问题。假定小鸡每只0.50.5元，公鸡元，公鸡 每只每只2 2元，母鸡每只元，母鸡每只3 3元。现在有元。现在有100100元钱要求元钱要求 买买100100只鸡，问共有几种购鸡方案？只鸡，问共有几种购鸡方案？

21、 根据题目设母鸡、公鸡、小鸡各为根据题目设母鸡、公鸡、小鸡各为x,y,zx,y,z只，只， 列出方程为：列出方程为：x+y+z=100 x+y+z=100，3x+2y+0.5z=1003x+2y+0.5z=100 利用穷举法，将各种可能的组合一一测试，利用穷举法，将各种可能的组合一一测试， 输出符合条件的组合。即在各个变量的取值范输出符合条件的组合。即在各个变量的取值范 围内不断变化围内不断变化x,y,zx,y,z的值，穷举的值，穷举x,y,zx,y,z全部可能全部可能 的组合，若满足方程组则是一组解。的组合，若满足方程组则是一组解。 第第4747页页 共共5353页页c c语言概述算法语言概述算法 #include stdio.h main() int x,y,z; printf(