第4章程序设计基础

第4章程序设计基础2019/8/292计算机科学导论学习目标了解程序设计的基础知识、程序设计风格的重要性、基本的查找和排序方法。掌握结构化程序设计方法和面向对象程序设计方法的思想、几种基本的数据结构。学习计算机首先要学习程序设计，良好的程序设计技能和风格有助于加深对计算机的理解和进一步学习。第4章程序设计基础2019/8/293计算机科学导论4.1程序设计基础程序设计是指用计算机语言对所要解决的问题中的数据以及处理问题的方法和步骤所做的完整而准确的描述的过程。程序设计步骤如下：(1)确定要解决的问题。(2)分析问题。在着手解决问题之前，应该通过分析，充分理解问题，明确原始数据、解题要求、需要输出的数据及形式等。(3)选择计算方法。(4)确定数据结构和算法。算法是解题的过程。首先集中精力于算法的总体规划，然后逐层降低问题的抽象性，逐步充实细节，直到最终把抽象的问题具体化成可用程序语句表达的算法。这是一个自上而下、逐步细化的过程。2019/8/294计算机科学导论4.1程序设计基础(5)绘制流程图。(6)编写程序。利用程序设计语言表示算法，编写代码。(7)调试并测试程序。调试程序包括编译和连接等操作。程序员还要对程序执行的结果进行分析，只有能够得到正确结果的程序才是所需的程序。(8)整理资料，交付使用。高质量程序设计目标是结构化程度高、可读性好、效率高、可靠性高、便于维护。2019/8/295计算机科学导论4.2程序设计方法程序设计初期，由于计算机硬件条件的限制，运算速度与存储空间都迫使程序员追求高效率，编写程序成为一种技巧与艺术，而程序的可理解性、可扩充性等要素则次之。随着计算机硬件与通信技术的发展，计算机应用领域越来越广泛，应用规模也越来越大，程序设计不再是一两个程序员就可以完成的任务。在这种情况下，编写程序不再片面追求高效率，而是综合考虑程序的可靠性、可扩充性、可重用性和可理解性等要素。2019/8/296计算机科学导论4.2.1结构化程序设计方法结构化程序设计思想:采用自顶向下、逐步求精的设计方法和单入口单出口的控制结构。2019/8/297计算机科学导论1．自上而下与自下而上先将一个大问题分解成若干个子问题，把比较复杂的子问题继续分解成更加简单的二级子问题，直至每个子问题都有显而易见的解决办法，然后在实现时采用自下而上的方法，逐一编写解决各个子问题的程序。设计程序时采用自上而下的方法比采用自下而上的方法效率要高得多。4.2.1结构化程序设计方法2019/8/298计算机科学导论采用自上而下解决问题的思路如图:......…二级子问题二级子问题二级子问题需要解决的复杂问题…三级子问题三级子问题三级子问题.........…最小问题最小问题最小问题4.2.1结构化程序设计方法2019/8/299计算机科学导论2．结构化方法结构化方法有助于在正式编写程序之前充分理解问题的实质和实现方法，并且可以在具体编码过程中提供指导。4.2.1结构化程序设计方法2019/8/2910计算机科学导论结构化方法通常遵循以下原则:(1)用户参与的原则(3)自上而下的原则(4)阶段成果文档化4.2.1结构化程序设计方法2019/8/2911计算机科学导论3．结构化程序设计方法结构化程序设计的原则是：(1)使用顺序、选择、循环3种基本控制结构表示程序逻辑。(2)程序语句组织成容易识别的语句模块，每个模块都是单入口、单出口。(3)严格控制GOTO语句的使用。4.2.1结构化程序设计方法2019/8/2912计算机科学导论(a)顺序结构(b)选择结构(c)while循环(d)do-while循环AB出口假真入口ABS假真入口SA出口假真入口AS4.2.1结构化程序设计方法2019/8/2913计算机科学导论4．模块化方法一个复杂的问题可以划分为多个简单问题的组合。在自顶向下、逐步细化的过程中，把复杂问题分解成一个个简单问题的最基本方法就是模块化。模块化便于问题的分析，模块体现了信息隐藏的概念。模块常用子程序加以实现。4.2.1结构化程序设计方法2019/8/2914计算机科学导论4.2.2面向对象的程序设计方法1．面向对象的思想OO(ObjectOriented，面向对象)的程序设计把客观事物看作具有属性和行为的对象，通过抽象找出同一类对象的共同属性(静态特征)和行为(动态特征)，形成类。2019/8/2915计算机科学导论2．对象、消息传递和类对象:是对现实问题的高度概括、分类和抽象。每个对象都只有自己的数据和相应的处理函数，整个程序是由一系列相互作用的对象来构成，不同对象之间是通过发送消息来实现相互联系、相互作用。4.2.2面向对象的程序设计方法2019/8/2916计算机科学导论消息传递:消息是对象之间进行通信的一种机制。发送给某个对象的一个消息包含着要求接收对象完成某些活动的信息。接收到消息的对象经过解释，然后予以响应。这个通信机制叫做消息传递。发送消息的对象并不需要知道接收消息的对象如何对请求予以响应。4.2.2面向对象的程序设计方法2019/8/2917计算机科学导论类:定义了一组大体上相似的对象。一个类所包含的方法和数据描述一组对象的共同行为和属性。对象则是类的具体化，是类的实例。类通过派生可以有子类，同样也可以有父类，形成层次结构。4.2.2面向对象的程序设计方法2019/8/2918计算机科学导论3．抽象是对具体事物(即对象)进行概括，即忽略事物的非本质特征，只注意那些与当前目标有关的本质特征，从而抽象出一类对象的共性并加以描述。对一个问题的抽象一般来讲应该包括两个方面：数据抽象和代码抽象(或称为行为抽象)。4.2.2面向对象的程序设计方法2019/8/2919计算机科学导论4．封装性封装的两个含义：第一是，将抽象得到的数据成员和代码成员相结合，形成一个不可分割的整体，即对象，这种数据及行为的有机结合也就是封装。第二个含义称为信息隐蔽，即尽可能隐蔽对象的内部细节。在隐蔽对象内部细节的同时，对象需要提供与外部世界进行交流的接口，并实现对数据访问权限的合理控制，把整个程序中不同部分的相互影响减少到最低限度。4.2.2面向对象的程序设计方法2019/8/2920计算机科学导论5．继承性是父类和子类之间共享数据和方法的机制。在定义一个类的时候，可以以一个已经存在的类为基础，并把这个已经存在的类所包含的属性和方法作为自身的一部分，然后加入新的属性和方法以区别于原来的类。原有的类称为基类或父类，产生的新类称为派生类。4.2.2面向对象的程序设计方法2019/8/2921计算机科学导论6.多态性在收到外部消息时，对象通常要予以响应。不同的对象收到同一消息可能产生完全不同的结果。4.2.2面向对象的程序设计方法2019/8/2922计算机科学导论4.2.3函数程序设计函数程序设计语言使用非常简单的计算模型或者程序观点，一个程序是输入集合到输出集合的数学函数，执行一个程序便是计算一个函数在给定输入的输出值。函数程序的特点是清晰、简洁和易读等，这些特点使得大型程序的开发更高效，维护更容易。函数程序设计语言因其简单的基本理论，使现代程序设计的基本思想，如抽象、数据抽象、多态和重载等都得到了最清楚的体现。因此，函数程序设计不仅是学习现代程序设计思想的理想语言，而且为传统的命令式和面向对象的程序设计语言提供了很有意义的视角。2019/8/2923计算机科学导论4.2.4程序设计风格程序设计风格指一个人编制程序时所表现出来的特点、习惯、逻辑思路等。2019/8/2924计算机科学导论1．源程序文档化(1)标识符应按意取名。(2)程序应加注释。注释是程序员与读者之间通信的重要工具，用自然语言或伪码描述。它说明了程序的功能，特别是在维护阶段，对理解程序提供了明确指导。注释分序言性注释和功能性注释。序言性注释应置于每个模块的起始部分。4.2.4程序设计风格2019/8/2925计算机科学导论2．数据说明为了使数据定义更易于理解和维护，有以下原则。(1)数据说明顺序应规范，使数据的属性更易于查找，从而有利于测试、纠错与维护。如常量说明、类型说明、全局变量说明、局部变量说明等。(2)一个语句说明多个变量时，各变量名按字典顺序排列。(3)对于复杂的数据结构，要加注释，说明在程序实现时的特点。4.2.4程序设计风格2019/8/2926计算机科学导论①说明每个模块的用途、功能。②说明模块的接口：调用形式、参数描述及从属模块的清单。③数据描述：重要数据的名称、用途、限制、约束及其他信息。④开发历史：设计者、审阅者姓名及日期，修改说明及日期。功能性注释嵌入在源程序内部，说明程序段或语句的功能以及数据的状态。注意以下几点：①注释用来说明程序段，而不是每一行程序都要加注释。②使用空行、缩格或括号，以便于区分注释和程序。③修改程序也应修改注释。4.2.4程序设计风格2019/8/2927计算机科学导论3．语句构造语句构造的原则是简单、直接，不能为了追求效率而使代码复杂化。为了便于阅读和理解，一行只写一条语句；不同层次的语句采用缩进形式，使程序的逻辑结构和功能特征更加清晰。要避免复杂的判定条件，避免多重的循环嵌套；表达式中使用括号以提高运算次序的清晰度等。4.2.4程序设计风格2019/8/2928计算机科学导论4．在编写输入和输出语句时应考虑原则(1)输入操作步骤和输入格式尽量简单。(2)应检查输入数据的合法性、有效性，报告必要的输入状态信息及错误信息。(3)输入一批数据时，使用数据或文件结束标志，而不要用计数来控制。(4)交互式输入时，提供可用的选择和边界值。(5)当程序设计语言有严格的格式要求时，应保持输入格式的一致性。(6)输出数据表格化、图形化。输入、输出风格还受其他因素的影响，如输入/输出设备、用户经验及通信环境等。4.2.4程序设计风格2019/8/2929计算机科学导论5．效率效率是指处理机时间和存储空间的使用。(1)效率是一个性能要求，目标在需求分析时给出。(2)追求效率要建立在不损害程序可读性和可靠性基础上，要在确保程序正确、清晰的情况下提高效率。(3)提高程序效率的根本途径在于选择良好的设计方法、良好的数据结构，而不是靠编程时对程序语句做调整。4.2.4程序设计风格2019/8/2930计算机科学导论4.2.5程序设计举例例4.1输入三角形的3个边长a，b和c，求三角形面积。则计算该三角形的面积的C语言源程序如下：#includemath.hmain(){floata,b,c,s,area;scanf(“%f,%f,%f”,&a,&b,&c);s=1.0/2*(a+b+c);area=sqrt(s*(s-a)*(s-b)*(s-c));printf(“a=%7.2f,b=%7.2f,c=%7.2f,s=%7.2f\n”,a,b,c,s);printf(“area=%7.2f\n”,area);}))()((csbsassarea2/)(cbas2019/8/2931计算机科学导论例4.2求方程的根，a，b，c由键盘输入，设，根据数学知识，可以求得方程的根为：设:，则方程的根可以改写为：02cbxax042acb2421acbbx2422acbbxabp2aacbq242qpx1qpx24.2.5程序设计举例2019/8/2932计算机科学导论计算该方程的根的源程序如下：#includemath.hmain(){floata,b,c,disc,x1,x2,p,q;scanf(“a=%f,b=%f,c=%f”,&a,&b,&c);disc=b*b-4*a*c;p=-b/(2*a);q=sqrt(disc)/(2*a);x1=p+q;x2=p-q;printf(“\nx1=%5.2f\nx2=%5.2f\n”,x1,x2