7.1 7.1 程序设计概述程序设计概述 7.2.2 7.2.2 算法的复杂度算法的复杂度7.2.1 7.2.1 算法的基本概念算法的基本概念 7.1.3 7.1.3 面向对象程序设计面向对象程序设计 7.1.2 7.1.2 结构化程序设计结构化程序设计7.1.1 7.1.1 程序设计的风格程序设计的风格7.2 7.2 算法概述算法概述掌握逐步求精的结构化程序设计方法，初步掌握良好的程序设计风格的内涵，掌握算法的基本概念，理解面向对象程序设计的基本概念。教学目标及基本要求教学目标及基本要求教学重点教学重点逐步求精的结构化程序设计方法，算法的基本概念。 第第2727讲讲 程序设计与软件开发基础程序设计与软件开发基础( (一一) )教学难点教学难点面向对象程序设计的基本概念，算法的复杂度。 程序设计的风格结构化程序设计面向对象程序设计算法的基本概念算法的复杂度教学内容教学内容第第2727讲讲 程序设计与软件开发基础程序设计与软件开发基础( (一一) )1学时 教学时间教学时间第第2727讲讲 程序设计与软件开发基础程序设计与软件开发基础( (一一) )7.1 程序设计概述7.1.1 程序设计的风格1 1程序设计风格程序设计风格程序设计风格程序设计风格 程序设计风格是指编写程序时所表现出的特点、习惯和逻辑思路。 程序设计的风格总体而言应该强调简单和清晰，程序必须是可以理解的。 主导的程序设计风格： “清晰第一，效率第二” 。2 2 2 2良好程序设计风格良好程序设计风格良好程序设计风格良好程序设计风格（1）源程序文档化 符号名的命名见名知意名字不宜太长不要使用相似的名字不要使用关键字做标识符 同一个名字不要有多种含义7.1.1 程序设计的风格 功能性注释：通常位于每个程序的开头部分，它给出程序的整体说明。主要描述内容包括：程序标题、程序功能说明、主要算法、接口说明、程序位置、开发简历、程序设计者、复审者、复审日期、修改日期等。一般嵌在源程序体之中，主要描述其后的语句或程序做什么。 程序注释序言性注释： 源程序文档化 视觉组织 在程序中利用空格、空行、缩进等技巧使程序层次清晰。源程序文档化（2）数据说明的方法 数据说明的次序规范化：数据说明次序固定，便程序理解、阅读和维护，可以使数据的属性容易查找，也有利于测试、排错和维护。良好程序设计风格 说明语句中变量安排有序化：当一个说明语句说明多个变量时，变量按照字母顺序排序为好。 使用注释来说明复杂数据的结构。 显式地说明一切变量。（3）语句的结构 在一行内只写一条语句。 程序编写应优先考虑清晰性，除非对效率有特殊要求，即清晰第一，效率第二。 首先要保证程序正确，然后才要求提高速度。 良好程序设计风格 避免使用临时变量而使程序的可读性下降。 避免采用复杂的条件语句和不必要的转移，尽量使用库函数。 数据结构要有利于程序的简化，程序要模块化，且要尽量使模块功能单一化，利用信息隐蔽，确保每一个模块的独立性。 尽量只采用3种基本控制结构来编写程序。语句的结构（4）输入和输出 对所有的输入数据都要检验数据的合法性以及检查输入项的各种重要组合的合理性。 输入格式要简单，以使输入的步骤和操作尽可能简单。 输入数据时，应允许使用自由格式和缺省值。 输入一批数据时，最好使用输入结束标志。 良好程序设计风格 以交互式方式输入、输出数据时，要在屏幕上有明确的提示符，数据输入结束时，应在屏幕上给出状态信息。 当程序设计语言对输入格式有严格要求时，应保持输入格式与输入语句的一致性；给所有的输出加注释，并设计良好的输出报表格式。输入和输出7.1.2 结构化程序设计1 1 1 1结构化程序设计的原则结构化程序设计的原则结构化程序设计的原则结构化程序设计的原则自顶向下、逐步求精、模块化、限制使用自顶向下、逐步求精、模块化、限制使用GOTO语句。语句。（1）自顶向下 先总体，后细节；先全局目标，后局部目标。（2）逐步求精 设计一些子目标作为过渡，逐步细化。结构化程序设计的原则（3）模块化 把程序要解决的总目标分解为分目标，再进一步分解为具体的小目标，把每个小目标称为一个模块。（4）限制使用GOTO语句 使用GOTO语句有时会使程序执行效率较高，但也容易造成程序混乱，程序不易理解、不易排错、不易维护，因而要尽量限制使用GOTO语句。结构化程序设计的原则2 2 2 2结构化程序的基本结构与特点结构化程序的基本结构与特点结构化程序的基本结构与特点结构化程序的基本结构与特点结构化程序的基本结构只有结构化程序的基本结构只有3 3种种: :顺序、选择和循环顺序、选择和循环（1）顺序结构 如图7-1所示,顺序结构是顺序执行结构。所谓顺序执行，就是按照程序语句行的自然顺序，一条语句一条语句（ABC）地执行程序。7.1.2 结构化程序设计ABC图7-1 顺序结构顺序结构（2）选择结构 选择结构又称为分支结构，它包括简单选择和多分支选择结构，这种结构可以根据设定的条件，判断应该选择哪一条分支来执行相应的语句序列。图7-2列出了包含2个分支的简单选择结构。结构化程序设计的基本结构与特点 条件 T F A B图7-2 选择结构选择结构（3）循环结构 循环结构又称为重复结构，它根据给定的条件，判断是否需要重复执行某一相同的或类似的程序段。分为两类:直到型循环结构：先判断后执行循环体（图7-3）先执行循环体后判断（图7-4）当型循环结构： 结构化程序设计的基本结构与特点图7-3 当型循环结构图7-4 直到型循环结构判断条件 循环体 循环体判断条件循环结构3 3 3 3结构化程序设计原则和方法的运用结构化程序设计原则和方法的运用结构化程序设计原则和方法的运用结构化程序设计原则和方法的运用（1）使用顺序、选择、循环三种结构表示程序的控制逻辑。（2）选用的控制结构只准许有一个入口和一个出口。7.1.2 结构化程序设计（3）复杂结构应用嵌套的基本控制结构进行组合嵌套来实现，语言中所没有的控制结构，应该采用前后一致的方法来模拟。（4）严格控制GOTO语句的使用。结构化程序设计原则和方法的运用7.1.3 面向对象程序设计1 1 1 1面向对象程序设计方法的产生面向对象程序设计方法的产生面向对象程序设计方法的产生面向对象程序设计方法的产生系统的需求总是处于不断变化之中，因此，需要设计对变化有弹性的系统 。面向对象程序设计方法学的产生传统的结构化程序设计方法主要是面向过程的，也就是在分析设计时更多地从过程处理的角度进行，系统框架结构，系统模块的划分、设计都是基于系统所实现的功能，而功能是系统中最易变的部分，这样，如果系统需求发生一些变化（如系统某些功能的改进或扩充新功能），系统的结构就会受到破坏。 利用传统的结构化程序设计方法设计的系统不易扩充。在实际系统中，最稳定的部分是系统对象，它直接描述问题域。面向对象的系统能够有效提高系统结构的稳定性。较复杂的系统将为每个对象类定义一些更复杂的功能（如“飞机”对象类中增加自动跟踪功能）或者增加一些新的对象类（如“雷达”），但是系统的核心部分（问题域中的对象）即使在系统功能范围发生变化的情况下，仍保持不变。面向对象程序设计方法学的产生在分析阶段采用DFD表示，而在设计阶段采用结构图的表示方法。在面向对象方法中，从分析（OOA）、设计（OOD）到编程实现（OOP）采用的都是同样的表示方法。 传统的结构化分析和设计方法中存在迥然不同的表示方法。面向对象程序设计方法学的产生2 2 2 2面向对象程序设计方法学的优点面向对象程序设计方法学的优点面向对象程序设计方法学的优点面向对象程序设计方法学的优点可重用性继承是面向对象方法的一个重要机制，用面向对象方法设计的系统的基本对象类可以被其他新系统重用，通常这是通过一个包含类和子类层次结构的类库来实现的，面向对象方法通过从一个项目向另一个项目提供一些重用类而能显著提高生产率。 7.1.3 面向对象程序设计可维护性表示方法的一致性面向对象程序设计方法学的优点3 3 3 3面向对象程序设计方法学的基本概念面向对象程序设计方法学的基本概念面向对象程序设计方法学的基本概念面向对象程序设计方法学的基本概念（1 1）对象对象概念：在现实世界中，对象指的是任何一个实概念：在现实世界中，对象指的是任何一个实体。它可能是一个人、一部车。体。它可能是一个人、一部车。对象的组成：对象的组成：7.1.3 面向对象程序设计对象的属性对象的属性对象名对象名对象的方法对象的方法用来标识对象用来标识对象是实体所具有的性质（外形与是实体所具有的性质（外形与状态）。状态）。是实体所拥有的行为。是实体所拥有的行为。 （2 2）消息消息概念：概念：对象之间进行通信的一种构成叫做消息。对象之间进行通信的一种构成叫做消息。 消息传递消息传递 ：当一个消息发送给某个对象时，包含当一个消息发送给某个对象时，包含要求接收对象去执行某些活动的信息。接收到信息要求接收对象去执行某些活动的信息。接收到信息的对象经过解释，然后予以响应。这种通信机制叫的对象经过解释，然后予以响应。这种通信机制叫做消息传递。发送消息的对象不需要知道接收消息做消息传递。发送消息的对象不需要知道接收消息的对象如何响应该请求。的对象如何响应该请求。面向对象程序设计方法学的基本概念（3 3）类类概念：类是对象的抽象概念：类是对象的抽象。 （4 4）继承继承概念：概念：继承是父类和子类之间共享数据和方法继承是父类和子类之间共享数据和方法的机制的机制 。可以在一个已经存在的类的基础上来进。可以在一个已经存在的类的基础上来进行，把这个已经存在的类所定义的内容作为自己行，把这个已经存在的类所定义的内容作为自己的内容，并加入若干新的内容的内容，并加入若干新的内容 。面向对象程序设计方法学的基本概念继承的分类继承的分类单重继承：单重继承：多重继承：多重继承：子类只从一个父类得到继承子类只从一个父类得到继承 子类从多个父类得到继承子类从多个父类得到继承 面向对象程序设计方法学的基本概念（5 5）多态性多态性概念：概念：同样的消息被不同的对象接受时可导致完全同样的消息被不同的对象接受时可导致完全不同的行动，该现象称为多态性。不同的行动，该现象称为多态性。 多态性的作用：多态性机制不仅增加了面向对象软多态性的作用：多态性机制不仅增加了面向对象软件系统的灵活性，进一步减少了信息冗余，而且显件系统的灵活性，进一步减少了信息冗余，而且显著地提高了软件的可重用性和可扩充性。著地提高了软件的可重用性和可扩充性。面向对象程序设计方法学的基本概念7.2 算法概述7.2.1 7.2.1 7.2.1 7.2.1 算法的基本概念算法的基本概念算法的基本概念算法的基本概念1 1算法的基本概念算法的基本概念算法的基本概念算法的基本概念 算法是指解题方案的准确而完整的描述，并且具有下列特性： （1）有穷性：一个算法必须在执行有穷步骤之后结束，且每一步都可在有穷时间内完成。 算法的特性（2）确定性：算法的每一步必须是确切定义的，不能有歧义。（3）可行性：算法应该是可行的。（4）输入：一个算法有零个或多个输入。（5）输出：一个算法有一个或多个输出。7.2.1 算法的基本概念2 2算法的基本要素算法的基本要素算法的基本要素算法的基本要素对数据对象的运算和操作 算法的控制结构 算术运算、 逻辑运算、 关系运算、 数据传输算法中各操作之间的执行顺序7.2.1 算法的基本概念3 3算法设计的要求算法设计的要求算法设计的要求算法设计的要求正确性可读性健壮性效率评价一个算法优劣的主要标准是算法的执行效率和存储需求。算法的执行效率指的是时间复杂度（Time Complexity），存储需求指的是空间复杂度（Space Complexity）。 7.2.1 算法的复杂度7.2.2 算法的复杂度1 1算法的时间复杂度算法的时间复杂度算法的时间复杂度算法的时间复杂度v概念算法的时间复杂度是指执行算法所需要的计算工作量。因为基本运算反映了算法运算的主要特征，因而可以用算法在执行过程中所需基本运算的执行次数来度量算法的工作量。算法的时间复杂度v算法的工作量计算公式算法的工作量=f(n) 其中n是问题的规模两个n阶矩阵相乘所需的基本运算（即两个实数的乘法）次数为n3，即计算工作量为n3，也就是时间复杂度为n3。 算法的时间复杂度v注意事项在同一个问题规模下，如果算法执行所需的基本运算次数取决于某一特定输入时，可以用平均性态和最坏情况复杂性方法来分析算法的工作量。算法的时间复杂度平均性态平均性态分析是指用各种特定输入下的基本运算次数的加权平均值来度量算法的工作量。 在长度为n的一维数组中查找值为x的元素，若采用顺序搜索法，在平均情况下需要检查数组中一半的元素。 算法的时间复杂度最坏情况分析 最坏情况分析是指在规模为n时，算法所执行的基本运算的最大次数。 在长度为n的一维数组中查找值为x的元素，若采用顺序搜索法，在最坏情况下最坏情况需查找n次。 7.2.2 算法的复杂度2 2算法的空间复杂度算法的空间复杂度算法的空间复杂度算法的空间复杂度一个算法的空间复杂度一般是指执行这个算法所需要的内存空间。包括算法程序所占的空间、输入的初始数据所占的存储空间以及算法执行过程中所需要的额外空间。其中额外空间包括算法程序执行过程中的工作单元以及某种数据结构所需要的附加存储空间。 例 题【例7.1】讨论用选择法对数组中n个整数按由小到大排序的时间复杂度。1.选择法: 先将n个数中最小的数与a0对换，再将a1到an-1中最小的数与a1对换每比较一轮，找出一个未经排序的数中最小的一个，共比较n1轮。 2.算法:（1）从键盘输入n个数，并将其存储在一个有n个元素的整型数组a中。（2）进行选择排序： int i=0；/每一轮比较起始元素的下标 int k=0；/每一轮比较得到的最小元素的下标 通过循环求出aian中最小数的下标k 如果i不等于k，将ai与ak对换 i=i+1，转到（3）输出排序的结果。3.C+程序代码void void select_sort(intselect_sort(int array, array, intint n) / n) /第第1 1行行 intint i,j,k,ti,j,k,t; /; /第第2 2行行 for(ifor(i=0;in-1;i+) /=0;in-1;i+) /第第3 3行行 k=i; / k=i; /第第4 4行行 for(jfor(j=i+1;j=i+1;jn;jn;j+) /+) /第第5 5行行 if(arrayjif(arrayjarraykarrayk) /) /第第6 6行行 k=j; /k=j; /第第7 7行行if(kif(k!=i) /!=i) /第第8 8行行 /第第9 9行行 t=t=arrayk;arraykarrayk;arrayk=arrayi;arrayiarrayi;arrayi=t; /=t; /第第1010行行 / /第第1111行行 / /第第1212行行 / /第第1313行行4.时间复杂度算法中第3行的for循环的循环体要执行n1次，而第5行的for循环的循环体每次分别执行n1，n2，n3，2，1次，该算法的时间复杂度为：n1+n2+2+1=n(n1)/2。小 结程序设计语言经历了程序设计语言经历了机器语言、汇编语言、高级语言机器语言、汇编语言、高级语言等等多个阶段多个阶段 ，程序设计方法也经历了早期手工作坊式的程序，程序设计方法也经历了早期手工作坊式的程序设计、设计、结构化程序设计、面向对象程序设计结构化程序设计、面向对象程序设计等发展阶段。等发展阶段。结构化程序设计方法的主要原则可以概括为结构化程序设计方法的主要原则可以概括为自顶向下、逐自顶向下、逐步求精、模块化、限制使用步求精、模块化、限制使用GOTOGOTO语句语句。结构化程序设计方。结构化程序设计方法是仅仅使用法是仅仅使用顺序、选择和循环顺序、选择和循环3 3种基本控制结构，它虽然种基本控制结构，它虽然成功但是它并不总是有效的。面向对象程序设计方法涉及成功但是它并不总是有效的。面向对象程序设计方法涉及 小 结到到类、对象、消息、继承、多态性类、对象、消息、继承、多态性等相关概念。应用系等相关概念。应用系统开发的程序设计的程序设计风格会深刻地影响软件的统开发的程序设计的程序设计风格会深刻地影响软件的质量和可维护性，质量和可维护性，良好的程序设计风格良好的程序设计风格可以使程序结构可以使程序结构清晰合理，使程序代码便于维护。清晰合理，使程序代码便于维护。算法是为解决某一特算法是为解决某一特定类型的问题规定了一个运算过程，评价一个算法优劣定类型的问题规定了一个运算过程，评价一个算法优劣的主要标准是算法的执行效率和存储需求的主要标准是算法的执行效率和存储需求 ，设计高效的，设计高效的算法对程序设计有着十分重要的意义。算法对程序设计有着十分重要的意义。作 业1什么是程序设计的风格？如何才能养成良好的程序设计的风格？2简述结构化程序设计的主要原则及基本结构。3什么是算法？它有哪些特点？