第4章程序与算法

北理工珠海学院计算机学院2019/8/281第4章程序与算法北理工珠海学院计算机学院2019/8/2828/28/20192§2C语言程序的基本结构§2C语言程序的基本结构一.C语言程序结构main()程序首部{说明语句数据结构语句输入语句执行语句运算处理算法设计}输出语句北理工珠海学院计算机学院2019/8/2838/28/20193生成执行程序的四个过程编辑、编译、连接、运行北理工珠海学院计算机学院2019/8/2848/28/20194§4C语言编程环境编译方式用户目标程序源程序执行程序库文件连接程序编译程序编辑程序错误信息结果编译连接编辑.c.obj.exe运行北理工珠海学院计算机学院2019/8/2858/28/20195END课堂练习题[1.1]运行的程序的后缀是______。[1.2]C语言源程序文件的后缀是______，经过编译后,生成文件的后缀是______，经过连接后，生成文件的后缀是______。[1.3]结构化程序由____、____、____三种基本结构组成。.EXE.C.OBJ.EXE顺序分支循环完北理工珠海学院计算机学院2019/8/286几个知识要点程序=数据结构+算法“数据结构”就是要告诉程序要用到哪些数据、哪种类型的数据、数据间的关系以及数据存储方法。“算法”就是计算机解题所进行操作的步骤，是程序的逻辑抽象，是解决问题的数学过程，是对解题过程准确而完整的描述。编程是一种“把一件事情交给计算机去做”的行为，这个行为通过程序语言加以描述。算法设计是编程前必须要做的事，解决“做什么”和“如何做”的问题，然后程序再根据算法实现出来，因此算法是程序设计的灵魂。§1程序设计与算法概述北理工珠海学院计算机学院2019/8/287几个知识要点C语言本身的语法规则C语言从基本字符集到关键字、标识符、常量、变量、函数和表达式等基本“单词”，再到基本语句，结合具体的语言规则和要求就构成C语言的程序。C程序的组成要素和设计、调试步骤函数是构成程序的基本单位，语句是构成函数的基本单位。函数用于实现某一项功能，语句用于体现完成这个功能所进行操作的详细步骤。程序设计就是分析解决问题的方法步骤，并将其记录下来的过程。程序设计过程包括分析、设计、编码、测试、排错、文档编写等阶段。§1程序设计与算法概述北理工珠海学院计算机学院2019/8/2881.程序设计的步骤一个初级程序员对于一个简单的问题，若要用计算机解决，具体步骤大致为：①确定待解决问题的计算或处理方法；②将实际问题转变为一个数学问题，用数学模型(表达式)描述；③编制程序框图，确定程序结构；④选择计算机语言和它的工作模式；⑤编制程序；⑥上机编辑、调试（包括编译和连接），消除语法错误；⑦如果结果正确则生成最终的用户程序，否则返回①从头重来，找出逻辑或设计错误所在。§1程序设计与算法概述北理工珠海学院计算机学院2019/8/289如何表示算法？处理思路：公式？输入要求？错误处理方法？解决问题方法？2.算法举例【例4-1】输入三角形三个边的值，计算这个三角形的面积。如何输入？如何计算和输出？输入的是什么类型的值，输出类型、精度如何？输入值错误（不能构成三角形）如何解决？§1程序设计与算法概述北理工珠海学院计算机学院2019/8/2810算法描述图示开始计算面积并输出声明变量输入边值判断输入？结束错误处理错误#includestdio.h#includemath.hintmain(){inta,b,c;floats,area;scanf(“%d,%d,%d”,&a,&b,&c);if(“不能构成三角形”){printf(“inputerror!”);return0;}else{s=(a+b+c)/2.0;area=sqrt(s*(s-a)*(s-b)*(s-c));printf(“area=%.2f”,area);}return0;}北理工珠海学院计算机学院2019/8/2811目录§1程序设计与算法概述§2程序设计思想§3算法描述方法§4算法特性与评价方法§5本章小节第4章算法北理工珠海学院计算机学院2019/8/2812§2程序设计思想4.2.1结构化程序设计思想1.基本概念1966年C.Bobm提出任何程序都可以用顺序、选择、循环三种基本结构来组合，这样编写出来的程序易懂易读也易于修改，提高了程序可靠性。这样的程序称为结构化程序，编写这样的程序称为结构化程序设计。“分而治之”是一种解决复杂问题的常用方法，是结构化程序设计思想的具体体现。大问题可以分解为若干关联的小问题，小问题又可以分解为若干更小、更具体的问题。把小问题逐一求解，大问题就得到解决。2.结构化程序设计的方法（1）自顶向下、逐步细化。（2）模块化。（3）结构化编码。北理工珠海学院计算机学院2019/8/2813“自顶向下、逐步细化”方法“自顶向下、逐步细化”就是从一个大问题出发，往下逐步分解，由宏观到微观，由一般问题到具体细节实现等进行有序、有层次、有步骤的分析，最终在编写程序前，给出所有方法步骤的细节。例如：计算学院教师的平均工资。这个任务比较复杂，可分解为如下几点：（1）找出每个教师的收入；（2）计算共有多少教师；（3）计算工资总额；（4）计算平均工资。对于第（3）步又可再细分为：①找出一位教师档案；②读出工资数额；③累计求和；重复上述三步骤。对于①可再次进一步细分为：打开档案；找出正确记录；从磁盘读取数据。§2程序设计思想北理工珠海学院计算机学院2019/8/2814模块化设计结构化程序设计的另一个概念是模块化设计，把一个大的复杂的问题逐层分解为一系列小的简单的模块来进行处理，每个小模块只完成单一的具体任务。模块内部联系紧密，而与其他模块之间联系较弱，这样的模块称为独立性高的模块，实现“高内聚、低耦合”。模块化“功能分解”即按照问题的功能进行模块划分，把相近功能的任务放到一个模块中。§2程序设计思想北理工珠海学院计算机学院2019/8/28151)模块之间接口关系简单，每个模块完成独立的工作，易于被人理解，所编写出来的程序可读性和可理解性好；2)各个模块功能单一，要修改某一个模块时只涉及到要修改的模块而不涉及到其他模块，不会出现修改程序时牵一发动全身的现象；3)人们可以单独验证、测试一个个模块，保证其正确性；4)可以利用现有模块，像搭积木一样进行开发新的程序。独立性高的模块有以下优点：§2程序设计思想北理工珠海学院计算机学院2019/8/2816模块之间是一种层次结构，上层模块对下层模块进行调用，下图所示是报表生成程序的层次结构，以柜形框表示模块，框中的模块名称表明模块的功能，提出顶层的模块“做什么”而不涉及“怎样做”，最下层模块功能十分具体，涉及“怎样做”的精确描述，易于编程。报表生成程序数据输入数据计算求和求平均求方差打印报表§2程序设计思想北理工珠海学院计算机学院2019/8/2817结构化编码通过顺序、分支、循环三种基本结构通过函数方式实现功能通过多程序（.c文件）实现项目1.三种基本控制结构：顺序控制、选择控制、循环控制。2.模块化组织结构：按功能划分模块，每个模块易于理解且不可再分，用函数实现模块化组织结构。3.程序设计过程：自顶而下、逐步细化。结构化程序设计要点§2程序设计思想北理工珠海学院计算机学院2019/8/2818结构化程序有三种基本结构顺序结构选择结构循环结构语句执行的顺序与程序书写的顺序一致条件成立，执行A；否则，执行B重复执行某组动作条件成立时，反复执行A；条件不成立，停止重复执行动作A，当某一条件成立时，停止C程序的基本结构北理工珠海学院计算机学院2019/8/2819main(){inta,b,c;a=5;b=6;c=a+b;printf(“%d”,c);}程序执行的顺序和语句书写的顺序一致有一个数据入口一个数据出口AB顺序结构北理工珠海学院计算机学院2019/8/2820条件ABYN当条件满足时,执行语句A；否则,执行语句B有一个数据入口一个数据出口键盘输入一个整数,判断其正负inta;aa0if(a0)printf(“a为正数”);elseprintf(“a为负数”);语句A语句B打印a的值选择结构北理工珠海学院计算机学院2019/8/2821YN求1~100的自然数之和X=100x=1S=0语句若条件满足,重复执行语句内容；否则,退出循环条件一个数据入口一个数据出口s=s+x;x=x+1;条件不满足,不执行任何语句循环结构1.当型循环北理工珠海学院计算机学院2019/8/2822语句NY求1+2+3+~n=1000的最大的nn=1,s=0;s=s+nn=n+1……S1000n=1s=0不论条件是否满足,语句至少执行一次2.直到型循环s=1+2+3+……n=?(s1000)北理工珠海学院计算机学院2019/8/28233.结构化程序设计的特点1）以三种基本结构的组合进行程序的编写；2）程序的编写采用模块化结构；3）自顶向下，逐步求精；4）限制使用goto语句，不用或少用goto语句，通常只允许用它从一个循环中跳出而不允许从外部跳入一个循环；5）每一个结构只允许有一个入口和一个出口。各部分之间接口简单，逻辑清晰；6）采用结构化语言编写程序，程序结构清晰易于阅读和修改；7）采用良好的编程风格。§2程序设计思想北理工珠海学院计算机学院2019/8/28244.程序设计步骤1.分析问题，建立数学模型。2.确定数据结构。3.确定算法，描述算法。4.编制程序，调试程序。5.运行程序，得到结果。程序设计要求：书写正确，结果正确§2程序设计思想北理工珠海学院计算机学院2019/8/28254.2.2面向对象的程序设计基本概念1.基本概念面向对象程序设计的本质是把数据与处理数据的过程当成一个整体——对象。类（CLASS）：定义了一类事物的抽象特点，包括事物的属性和它具有的行为（称为方法）。父类、子类实例(Instance)对象(Object)：是类的实例，是某个类别的具体化的事物。方法（method）是一个类能做的事情，代表具体操作功能。消息（Message）继承（Inheritance）多态性（Polymorphism）§2程序设计思想北理工珠海学院计算机学院2019/8/28262.面向对象程序设计的优点1.稳定性好2.可重用性好3.与人类习惯的思维方法一致4.易于开发大型软件产品5.可维护性好§2程序设计思想北理工珠海学院计算机学院2019/8/2827目录§1程序设计与算法概述§2程序设计思想§3算法描述方法§4算法特性与评价方法§5本章小节第4章算法北理工珠海学院计算机学院2019/8/2828算法分类利用计算机解题，一般有两类算法：数值计算算法和非数值计算算法。数值计算是指求数值解的问题（如计算方程根，求最大公约数等），往往有现成的模型、计算方法和公式对应。非数值计算主要解决需要用分析推理、逻辑推导才能解决的问题。由于种类繁多、要求各异，只有一些典型的非数值计算方法（如排序、查找算法等），许多问题需要设计解决问题的专门算法。§3算法描述方法北理工珠海学院计算机学院2019/8/28292.算法的描述①自然语言②传统流程图③NS结构化流程图④伪代码⑤程序代码（最准确的描述）。§3算法描述方法北理工珠海学院计算机学院2019/8/2830§3算法描述方法2.算法的表示②传统流程图描述下图表示程序流程图的基本符号，建议初学者养成编写程序前先画图的习惯，通过流程图使你的算法思想和实现步骤得以体现，便于检查、修改和交流。程序流程图基本符号北理工珠海学院计算机学院2019/8/2831三种基本结构的流程图描述模块A模块BYesNo条件判断模块A模块B§3算法描述方法北理工珠海学院计算机学院2019/8/2832三种基本结构的流程图描述模块A模块BYesNo条件判断模块A模块B模块A条件？No条件？模块ANo§3算法描述方法北理工珠海学院计算机学院2019/8/2833②流程图人们普遍采用程序流程图是