c语言(概述,算法) (课堂PPT)

,第一堂课,C语言概述,算法概述,C语言程序设计,第1页共53页,第一章,C语言程序设计,C语言概述,第2页共53页,本章要点,C语言的特点C语言的发展历史C程序的结构在计算机上运行C程序的方法,C语言程序设计,第3页共53页,1.1语言的发展历史,C语言是国际上广泛流行的高级语言。1963年,剑桥,CPL语言,更近硬件,但规模大,难以实现.1967年,剑桥,MartinRichards,简化,BCPL语言.1970年,美国贝尔实验室,KenThompson,简化,B语言,写第一个UNIX系统.19721973年,贝尔实验室,D.M.Ritchie,B语言基础上,设计出C语言,克服B语言的过于简单、功能有限的不足.1973年，K.Thompson和D.M.Ritchie合作将UNIX的90%以上用C改写.1978年以后,C语言已先后移植到大、中、小、微型机上已独立于UNIX和PDP，得以广泛应用。,第4页共53页,DennisMRitchie：1967年加入贝尔实验室。他和KenLThompson两人共同设计并实现了C语言,改变了程序设计语言发展的轨迹，是程序设计语言发展过程中的一个重要里程碑。与此同时，他们两人还设计并实现了UNIX操作系统。正是由于这两项巨大贡献，DennisMRitchie于1983年获得了计算机界的最高奖图灵奖。此外，他还获得了ACM、IEEE、贝尔实验室等授予的多种奖项。,第5页共53页,BrianWKernighan：是贝尔实验室计算科学研究中心高级研究人员，著名的计算机科学家。他参加了UNIX系统、C语言、AWK语言和许多其他系统的开发，同时出版了许多在计算机领域具有影响的著作。,第6页共53页,C语言的产生和地位,原书名：TheCProgrammingLanguage作者：（美）BrianW.Kernighan,DennisM.Ritchie,本书原著即为C语言的设计者之一DennisMRitchie和著名的计算机科学家BrianWKernighan合著的一本介绍C语言的权威经典著作。,C语言已经成为全球程序员的公共语言，并由此诞生了两个新的主流语言C+与Java，它们都建立在C语言的语法和基本结构的基础上。现在世界上的许多软件都是在C语及其衍生的各种语言的基础上开发出来的。,第7页共53页,1.2语言的特点,为什么学习C语言？,可进行内存物理地址访问，具有汇编语言的特点,控制流程结构化，以函数为基本结构进行流程控制,语言简洁灵活，有32个关键字和9种控制语句,具有构造数据类型的能力，数据结构系统化,语言表达能力强：34种运算符,程序运行效率高，易读性、可移植性好,语法检查不够严格，对数组下标越界不做检查,第8页共53页,1.3C语言程序的组成结构,例1:/*显示“Howareyou!”*/#includemain()printf(Howareyou!);,程序运行结果是输出:Howareyou!,第9页共53页,例2求两数之和#includemain()/*求两数之和*/inta,b,sum;/*定义变量为整型*/a=123;/*变量赋值*/b=456;sum=a+b;/*求和*/printf(sumis%dn,sum);,说明：/*/表示注释。注释只是给人看的,对编译和运行不起作用。所以可以用汉字或英文字符表示，可以出现在一行中的最右侧，也可以单独成为一行。,输出一行信息：sumis579,第10页共53页,例3:从键盘输入两个整数，并显示这两个整数之和。,intADDxy(inta,intb)intc;c=a+b;return(c);,main()intx,y,z;scanf(“%d%d”,主函数,子函数,程序运行情况如下：85sum=13,第11页共53页,C程序的基本结构小结：,(1)C程序是由函数构成的,程序容易实现模块化。,main()/*主函数说明*/变量定义/*主函数体*/执行语句组子函数名1(参数)/*子函数说明*/变量定义/*子函数体*/执行语句组子函数名2(参数)/*子函数说明*/变量定义/*子函数体*/执行语句组,第12页共53页,(2)一个函数由两部分组成:函数的首部：例3中的Addxy函数首部intAddxy(intx,inty)函数体：花括号内的部分。若一个函数有多个花括号,则最外层的一对花括号为函数体的范围。(3)C程序总是从main函数开始执行的,与main函数的位置无关。(4)C程序书写格式自由,一行内可以写几个语句,一个语句可以分写在多行上，C程序没有行号。,第13页共53页,(5)每个语句和数据声明的最后必须有一个分号。(6)C语言本身没有输入输出语句。输入和输出的操作是由库函数scanf和printf等函数来完成的(7)在C语言中，大小写字母是有区别的。（C语言习惯用小写字母）(8)书写程序时，最好使用规范的缩进格式的形式。(9)C程序注释/*/可以写在程序的任何位置上,第14页共53页,1.4运行程序的步骤和方法,1.运行程序的步骤上机输入、编辑源程序对源程序进行编译与库函数连接运行目标程序,第15页共53页,2.程序的开发环境,目前使用的大多数C编译系统都是集成环境的。可以用不同的编译系统对C程序进行操作常用的有TurboC2.0、TurboC+3.0、VisualC+等TurboC+3.0：是一个集成环境，它具有方便、直观和易用的界面，虽然它也是DOS环境下的集成环境，但是可以把执行文件tc.exe生成快捷方式放在Windows桌面上，可以支持鼠标操作。VisualC+6.0：可视化面向对象开发环境，可以用VisualC+对C程序进行编译。,第16页共53页,1.5从三个方面学习语言,1.学习C语言的语法数据表达：变量定义、正确书写表达式流程控制：if(ab)x=a;elsex=b;sum=0;i=1;while(i=5)sum=sum+i;i=i+1;for(i=1;sum=0;i=5;i+)sum=sum+i;设计函数输入和输出,第17页共53页,2.学习解决问题的方法(算法),如何求级数12+22+32+前100项之和？,矩阵转置,如何打印乘法表？,数据如何按从小到大的顺序排序？,第18页共53页,3.学习在C语言编程环境下，编辑、编译、调试和运行程序开发环境：VisualC+6.0,上机作业1：使用VisualC+6.0编写简单的C程序,第19页共53页,第二章,C语言程序设计,算法与程序设计基础,第20页共53页,本章要点,什么是程序设计什么是算法，如何设计和表示算法结构化程序设计的思想和方法,第21页共53页,计算机语言：是规则和符号的集合，是与计算机交流的工具。必须具有数据表达和数据处理（流程控制）的能力。程序：求解问题的指令序列软件：程序的集合,学习语言设计程序制作软件,概念：,学软件：学思想、学功能、学操作。熟练工种学语言：学规则、学方法、学设计、学应用。规范学习，灵活应用,第22页共53页,计算机语言分类,面向过程语言面向对象语言,FORTRANBASICCPASCALCOBOLLISP,C+C#VisualBASICJAVA,第23页共53页,2.1程序设计的基本概念,数据元素：数据的最小单位数据结构：数据元素的组织形式,程序设计数据结构算法方法工具,数据结构的优劣决定了软件或程序的复杂程度和面貌,一个程序应包括两个方面的内容:,对数据的描述：数据结构对操作的描述：算法,完整的程序设计应该包括四部分:,第24页共53页,程序设计的步骤,分析问题，建立数学模型确定数据结构确定算法，描述算法编制程序，调试程序运行结果,一个正确的程序通常包含两方面的含义：一是书写正确，二是结果正确。书写正确是指程序语法正确，符合程序语言的规则；结果正确是指对应于正确的输入，程序能够得到所期望的输出。,第25页共53页,程序的三种基本结构,1.顺序结构程序按照语句的书写次序顺序执行。,先执行A操作，再执行B操作，两者是顺序执行关系。,第26页共53页,2.选择结构通过判断特定条件，选择一个分支执行。,当P条件成立时，执行A操作，否则执行B操作,当P条件成立时，执行语句操作，否则跳过语句操作,第27页共53页,3.循环结构在给定条件下，反复执行循环体，直到条件不满足为止.,(1)形式a（当型循环结构）,当P条件成立时，反复执行A,直到P为零为止。,第28页共53页,(2)形式b（直到型循环结构）,先执行A操作，再判断P是否成立，若P成立，再执行A，直到P不成立为止。,第29页共53页,算法：完成一项任务的具体步骤计算机语言的别名：算法语言,1.算法的概念,2.2算法概述,“一个算法，就是一个有穷规则的集合，其中之规则规定了一个解决某一特定类型的问题的运算序列。”任何解决问题的过程都是由一定的步骤组成的，把解决问题确定的方法和有限的步骤称作为算法。,第30页共53页,例1：计算函数M(x)的值。函数M(x)为：,算法分析：这是一个数值运算问题。其中M代表要计算的函数值，有两个不同的表达式，根据x的取值决定采用哪一个算式。根据计算机具有逻辑判断的基本功能，用计算机解题的算法如下：,第31页共53页,将a、b、c和x的值输入到计算机；判断xa?如果条件成立，执行第步，否则执行第步；按表达式bx+a2计算出结果存放到M中，然后执行第步；按表达式a(c-x)+c2计算出结果存放到M中，然后执行第步；输出M的值；算法结束。,这是用自然语言描述的算法,第32页共53页,例2：有黑和蓝两个墨水瓶，但却错把黑墨水装在了蓝墨水瓶子里，而蓝墨水错装在了黑墨水瓶子里，要求将其互换。,算法分析：这是一个非数值运算问题。因为两个瓶子的墨水不能直接交换，所以，解决这一问题的关键是需要引入第三个墨水瓶。设第三个墨水瓶为白色，其交换步骤如下：,第33页共53页,将蓝瓶中的黑墨水装入白瓶中将黑瓶中的蓝墨水装入蓝瓶中将白瓶中的黑墨水装入黑瓶中交换结束,第34页共53页,2.算法的基本特征,算法是一个有穷规则的集合，这些规则确定了解决某类问题的一个运算序列。算法的基本特征：,有穷性：算法必须在执行有限个操作后终止；确定性：算法中每一步的含义必须是确切的，不能出现任何二义性；有效性：算法中的每一步操作都应该能有效执行，一个不可执行的操作是无效的；有零个或多个输入：执行算法时，从外界获得必要的信息；有一个或多个输出：算法的解就是输出。,第35页共53页,3.算法的常用表示方法,可以用不同的方法表示算法，常用方法有：自然语言传统流程图结构化流程图,第36页共53页,（1）自然语言,自然语言即是使用汉语、英语或其他语言去描述算法。例有50名学生的成绩，要求将他们之中80分以上的成绩打印出来。设用g代表学生成绩，gi代表第i个学生成绩。1）使i=1；2）如果gi80，则打印gi，否则不打印；3）使i的值加1；4）如果i50,返回S2，继续执行；否则，算法结束。特点：描述算法通俗易懂，容易产生歧义。对复杂问题，语句繁琐、冗长，并且很难清楚地表达算法的逻辑流程，往往需要根据上下文判别其含义，尤其对描述含有选择、循环结构的算法，不太方便和直观，一般不常使用。,第37页共53页,(2)传统流程图,美国国家标准化协会ANSI(AmericanNationalStandardInstitute)规定了一些常用的流程图符号：,第38页共53页,程序流程图表示,传统流程图用流程线指出各框的执行顺序，对流程线的使用没有严格限制。,第39页共53页,传统流程图的流程可以是：,缺点：使用者可以毫不受限制地使流程随意地转向，使流程图变得毫无规律，难以阅读、修改，使算法的可靠性和可维护性难以保证。解决办法：必须限制箭头的滥用，即不允许无规律地使流程随意转向，只能顺序的进行下去。,第40页共53页,（3）NS流程图,N-S流程图由美国学者I.Nassi和B.Shneiderman提出表示算法的图形工具。基本单元是矩形框,用不同的形状线分割,表示三种结构。只有一个入口,一个出口,没有流程线。N-S图的优点比文字描述直观、形象、易于理解；比传统流程图紧凑易画。尤其是它废除了流程线，整个算法结构是由各个基本结构按顺序组成的，N-S流程图中的上下顺序就是执行时的顺序。,第41页共53页,三种基本程序结构的NS流程图,3.循环结构,第42页共53页,传统流程图与N-S流程图的比较,例1：1+2+3+加到100为止,第43页共53页,例：打印50名学生中成绩高于80分的学号和成绩用N-S图表示。,第44页共53页,1.枚举法（穷举法）特点:算法简单，容易理解，运算量大。基本思想：根据题目的部分条件确定答案的大致范围，然后在此范围内对所有可能的情况逐一验证，直到所有情况均通过验证。若某个情况符合题目条件，则为本题的一个答案；若全部情况验证完后均不符合题目的条件，则问题无解。,2.3几种常用算法介绍,第45页共53页,如：百元买百鸡问题。假定小鸡每只0.5元，公鸡每只2元，母鸡每只3元。现在有100元钱要求买100只鸡，问共有几种购鸡方案？根据题目设母鸡、公鸡、小鸡各为x,y,z只，列出方程为：x+y+z=100，3x+2y+0.5z=100利用穷举法，将各种可能的组合一一测试，输出符合条件的组合。即在各个变量的取值范围内不断变化x,y,z的值，穷举x,y,z全部可能的组合，若满足方程组则是一组解。,第46页共53页,#includestdio.hmain()intx,y,z;printf(母鸡公鸡小鸡);for(x=0;x=33;x+)for(y=0;y=1;i-)x=(x+1)*2;printf(第%d天的桃子数为：%d只,i,x);printf(n);,小猴吃桃子源程序：,第50页共53