《C算法设计》PPT课件.pptx

《《C算法设计》PPT课件.pptx》由会员分享，可在线阅读，更多相关《《C算法设计》PPT课件.pptx（67页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、计算概论计算概论 算法设计算法设计崔崔 斌斌2/67n2主要内容主要内容n了解算法的基本概念了解算法的基本概念n掌握描述算法的三种基本掌握描述算法的三种基本结构构n学会算法的流程学会算法的流程图描述描述n介介绍几种基本算法几种基本算法3/67n31 算法的基本概念算法的基本概念n计算机只是一个算机只是一个计算工具，它本身不能主算工具，它本身不能主动帮帮助我助我们做任何事情，需要我做任何事情，需要我们告告诉它如何它如何进行行计算。算。n程序程序设计就是要告就是要告诉计算机如何算机如何进行行计算的。算的。这与我与我们中学中学时代的数学解代的数学解题过程是一程是一样的，的，只不只不过描述的手段有所描

2、述的手段有所变化而已。化而已。4/67n程序的开程序的开发u 对所要处理的问题域进行正确的理解对所要处理的问题域进行正确的理解u 把这种正确的理解正确的描述出来把这种正确的理解正确的描述出来客观事物（问题域）客观事物（问题域）计算机软件计算机软件语言的鸿沟语言的鸿沟自然语言自然语言编程语言编程语言程序的理解和执行程序的理解和执行（计算机）（计算机）编程（人）编程（人）语言的过渡语言的过渡（人）（人）对问题域的认识对问题域的认识 （人）（人）5/67没有解决方案就没有程序！没有解决方案就没有程序！n现实世界中世界中的解决方案的解决方案u为解决一个问题而采取的方法和步骤为解决一个问题而采取的方法和

3、步骤n计算机系算机系统中的算法中的算法u适用于计算机系统的解决某个问题的方法和步骤适用于计算机系统的解决某个问题的方法和步骤n写程序写程序“三部曲三部曲”（1）先思考出现实世界）先思考出现实世界中问题的解决方案；中问题的解决方案；（2）再思考出相应的适用于计算机系统的算法；）再思考出相应的适用于计算机系统的算法；（3）用高级语言及其数据结构精确地描述算法）用高级语言及其数据结构精确地描述算法；6/67n6n1984年年图灵灵奖获得者得者瑞士科学家瑞士科学家尼克尼克劳斯斯沃斯沃斯（Niklaus Wirth，Pascal语言的言的发明者和明者和结构化程序构化程序设计创始者）始者）1976年出版了

4、年出版了算法算法+数据数据结构构=程序程序设计一一书，提出了，提出了著名的公式：著名的公式：“程序程序 数据数据结构构 算法算法”。u程序：刻画现实世界，解决现实世界中的问题程序：刻画现实世界，解决现实世界中的问题u算法算法：问题的解的描述：问题的解的描述u数据结构：现实世界的数据模型数据结构：现实世界的数据模型n程序就是在程序就是在数据的某些特定的表示方式和数据的某些特定的表示方式和结构构的基的基础上上对抽象算法抽象算法的具体表述的具体表述。n+程序程序设计方法方法+语言工具和言工具和环境境u程序设计语言：实现的工具程序设计语言：实现的工具7/67n71 算法的基本概念算法的基本概念n算法的

5、定算法的定义u设计程序的目的是为了求解问题，为解决一个问题设计程序的目的是为了求解问题，为解决一个问题所采取的方法和步骤，就称为所采取的方法和步骤，就称为“算法算法”u算法是算法是一个由一组严格定义的指令组成的过程一个由一组严格定义的指令组成的过程，给，给定一个出始状态，这个过程能够结束在一个确定终定一个出始状态，这个过程能够结束在一个确定终止状态。止状态。u大多数算法都可以用程序实现。大多数算法都可以用程序实现。u常用算法一般都被实现为算法库，供程序员调用。常用算法一般都被实现为算法库，供程序员调用。8/67n81 算法的基本概念算法的基本概念n一个实例：找出一组一个实例：找出一组正整数正整

6、数中的最大的数中的最大的数9/67n91 算法的基本概念算法的基本概念n逐步求解，定逐步求解，定义算法的算法的动作作uS1:设设Largest为第一个数为第一个数uS2:若第二个数比若第二个数比Largest大，则设大，则设Largest为第二个数为第二个数uS3:若第三个数比若第三个数比Largest大，则设大，则设Largest为第三个数为第三个数uS4:若第四个数比若第四个数比Largest大，则设大，则设Largest为第四个数为第四个数uS5:若第五个数比若第五个数比Largest大，则设大，则设Largest为第五个数为第五个数10/67n101 算法的基本概念算法的基本概念n算法

7、算法动作精化作精化uS0:设设Largest为为0uS1:若若当前数当前数比比Largest大，则设大，则设Largest为为当前数当前数uS2:若若当前数当前数比比Largest大，则设大，则设Largest为为当前数当前数uS3:若若当前数当前数比比Largest大，则设大，则设Largest为为当前数当前数uS4:若若当前数当前数比比Largest大，则设大，则设Largest为为当前数当前数uS5:若若当前数当前数比比Largest大，则设大，则设Largest为为当前数当前数11/67n111 算法的基本概念算法的基本概念n算法范化算法范化从从N个正整数中找出最大数的通用算法个正整数

8、中找出最大数的通用算法uS0:设设Largest为为0，当前位置，当前位置p为为0uS1:若当前数比若当前数比Largest大，则设大，则设Largest为当前数为当前数uS2:若若p比比N小，则小，则p增加增加1，返回，返回S1，否则返回，否则返回Largest12/67n121 算法的基本概念算法的基本概念算法的基本性质算法的基本性质n通用性通用性：即适用于某一即适用于某一类问题中的所有个体，而不只是用中的所有个体，而不只是用来解决一个具体的来解决一个具体的问题。n有效性有效性：即即应有明确的步有明确的步骤一步一步地引一步一步地引导计算的算的进行。行。n确定性确定性：即每个步即每个步骤都是

9、机械的、有明确定都是机械的、有明确定义的的动作，不作，不需要需要计算者算者临时动脑筋。筋。n有限性有限性：对满足算法要求的足算法要求的输入数据，算法入数据，算法应在有限多步在有限多步内内结束，并束，并给出明确的出明确的计算算结果。果。n离散性离散性：算法的算法的输入数据及入数据及输出数据都出数据都应是离散的符号。是离散的符号。13/67n131 算法的基本概念算法的基本概念n算法的基本要求算法的基本要求u正确正确u易维护（可读，易修改）易维护（可读，易修改）u方便使用方便使用u高效高效速度快速度快 运行运行时间少，少，时间复复杂度低度低占用内存少占用内存少 空空间复复杂度低度低n算法的效率可以

10、算法的效率可以测试，用大量，用大量输入数据入数据测量运行的量运行的时间和和占用的内存，通占用的内存，通过比比较判判别和和选择效率高的算法。效率高的算法。n更重要的是更重要的是编程前的分析和估程前的分析和估计，即理，即理论的的计算，算，给出事出事前的判断。前的判断。14/67n141 算法的基本概念算法的基本概念n不了解施加于数据上的算法就无法决定如何不了解施加于数据上的算法就无法决定如何构造数据；反之，算法的构造数据；反之，算法的结构和构和选择却常常却常常在很大程度上依在很大程度上依赖于作于作为基基础的数据的数据结构。构。简而言之，而言之，程序的构成（算法）与数据程序的构成（算法）与数据结构构

11、是两个不可分割地是两个不可分割地联系在一起的系在一起的问题。15/67n152 描述算法的三种基本结构描述算法的三种基本结构n已已经证明，只使用如下三种明，只使用如下三种结构，就可以描述构，就可以描述任何算法，且算法任何算法，且算法结构构优良良u顺序结构（顺序结构（Sequence）u分支结构（分支结构（Decision）u循环结构（循环结构（Repetition）n每一种基本每一种基本结构分构分别只有一个入口和一个出口只有一个入口和一个出口16/67n162.1 顺序结构顺序结构n顺序序结构：构：动作（作（语句）句）序列，序列，顺序序执行行u动作动作1 1u动作动作2 2u动作动作3 3uu

12、动作动作n n动作动作1动作动作2动作动作3动作动作117/67n172.2 分支结构分支结构n分支分支结构：根据构：根据条件条件判断判断执行什么行什么动作（作（语句）句）u如果如果 条件成立条件成立 则则动作动作1 1u否则否则动作动作2 2u分支结束分支结束条件成立？条件成立？动作动作1动作动作2是是否否18/67n182.3 循环结构循环结构n循循环结构：构：重复重复执行行一一系列系列动作作n当当 条件成立条件成立 做做u动作动作1 1u动作动作2 2uu动作动作n nn循环结束处循环结束处条件成立？条件成立？动作动作1动作动作n是是否否19/67n193 流程图表示算法流程图表示算法n

13、算法是算法是让人来理解的，因此需要有效的算人来理解的，因此需要有效的算法表示机制法表示机制u自然语言表示法自然语言表示法u伪代码表达法伪代码表达法u流程图表示法流程图表示法20/67n203 流程图表示算法流程图表示算法n流程流程图显示了程序的流程判断示了程序的流程判断结构。通常构。通常包含如下符号：包含如下符号：u开始开始和和结束结束u流程线流程线u输入输入和和输出输出u处理（动作）处理（动作）u条件判断条件判断开始开始/结束结束处理（动作）处理（动作）流程线流程线输入输入/输出输出条件判断条件判断21/67n213 流程图表示算法流程图表示算法n判断判断x0y=xy=-xYesNo22/6

14、7n223 流程图表示算法流程图表示算法n循循环k10动作动作k=k+1YesNo动作动作k=023/67n233 流程图表示算法流程图表示算法n判断判断闰年年u能被能被4 4整除且不能被整除且不能被100100整除；整除；u能被能被400400整除整除24/67n243 流程图表示算法流程图表示算法判断闰年判断闰年能被能被4 4整除且不能被整除且不能被100100整除；整除；能被能被400400整除整除n用用C+语言语言实现算法实现算法#include using namespace std;int main()int k;cink;if(k%4=0)if(k%100=0)if(k%400=

15、0)cout k is a leap year n;else cout k is not a leap year n;else cout k is a leap year n;else cout k is not a leap year n;return 0;25/67n253 流程图表示算法流程图表示算法n另一种表示：另一种表示：N-SN-S图图（无线的流程图无线的流程图,又称盒图又称盒图）26/67n264 基本算法基本算法n数数值算法算法u加减乘除、最大最小值、解方程、求微积分加减乘除、最大最小值、解方程、求微积分n非数非数值算法算法u排序、查找、文本处理、流程处理排序、查找、文本处理、

16、流程处理算法算法设计与分析需要与分析需要坚实的数学基的数学基础27/67n274.1基本算法基本算法-求平方根求平方根n求一个数的平方根：求一个数的平方根：x=u迭代迭代公式公式(牛顿迭代法牛顿迭代法)x1=1 xn+1=(xn+a/xn)/2 迭代计算，直到迭代计算，直到 xn+1 xn 的绝对的绝对值小于误差要求，例如小于值小于误差要求，例如小于0.00001，即保留小数点后，即保留小数点后5位。位。输入数输入数a开始开始初始化：初始化：x2=1x1=x2x2=(x1+a/x1)/2x2-x1的绝对值的绝对值小于小于0.00001？N结束结束输出输出x2Y28/67n28 求平方根求平方根

17、(C+语言语言实现实现)#include using namespace std;int main()double a,x1,x2;cin a;x2=1;dox1=x2;x2=(x1+a/x1)/2;while(x1-x20.00001|x2-x10.00001);cout x2 0.00001|x2-x10.00001)x1=x2;x2=(x1+a/x1)/2;29/67n294.2基本算法基本算法 排序排序n排序（排序（Sort）是指是指对一些数据的重新一些数据的重新组织，使得数，使得数据由大到小（降序）或者由小到大（升序）存据由大到小（降序）或者由小到大（升序）存储。排序是很一种基本的要

18、求。我排序是很一种基本的要求。我们所感所感兴趣的是如趣的是如何何寻找到一个好（找到一个好（计算速度快或占用内存少）的算速度快或占用内存少）的办法来法来进行排序行排序。u选择排序选择排序u冒泡排序冒泡排序30/67n304.2排序排序选择排序选择排序n选择排序，排序，Selection sortu数据列表被分为两个子列表：已排序和未排数据列表被分为两个子列表：已排序和未排序。找到未排序列表中值最小（或最大）的元序。找到未排序列表中值最小（或最大）的元素，并把它和未排序列表中的第一个元素进行素，并把它和未排序列表中的第一个元素进行交换。交换。31/67n314.2 选择排序选择排序示例（续）示例（

19、续）32/67n324.2 选择排序选择排序示例示例33/67n334.2 选择排序选择排序算法、程序算法、程序初始化：初始化：wall=0开始开始找到未排序列表找到未排序列表中的最小元素中的最小元素与未排序列表中与未排序列表中第一个元素交换第一个元素交换是否还有是否还有未排序元素？未排序元素？N结束结束Ywall=wall+134/67n344.2 排序排序冒泡排序冒泡排序n冒泡排序，冒泡排序，Bubble sortu数据列表被分为两个子列表：已排序和未排序。数据列表被分为两个子列表：已排序和未排序。未排序列表中最小（或最大）的元素通过冒泡的未排序列表中最小（或最大）的元素通过冒泡的形式（从

20、后往前冒泡）从未排序列表中交换到已形式（从后往前冒泡）从未排序列表中交换到已排序列表中。排序列表中。35/67n354.2 冒泡排序冒泡排序示例示例比较比较比较并交换比较并交换冒冒泡泡的的过过程程36/67n364.2 冒泡排序冒泡排序示例（续）示例（续）37/67n374.2 冒泡排序冒泡排序示例（续）示例（续）38/67n384.2 冒泡排序冒泡排序算法、程序算法、程序初始化：初始化：wall=0开始开始还有未排序的数？还有未排序的数？N结束结束Y交换相邻数交换相邻数还有未冒泡的数？还有未冒泡的数？比较相邻数比较相邻数YN39/67n394.2基本算法基本算法 排序排序n各种排序方法各种排

21、序方法简介：介：就地排序算法（不增加新的存就地排序算法（不增加新的存储空空间）1、插入排序法（、插入排序法（Insert Sort）将一个数插入到序列中的合适位置。将一个数插入到序列中的合适位置。2、选择排序法（、选择排序法（Selection Sort）每次把最小（大）的元素交每次把最小（大）的元素交换到最前面。到最前面。3、冒泡排序法（、冒泡排序法（Bubble Sort比比较并交并交换相相邻的元素，直到所有元素都被放到合适的位置。的元素，直到所有元素都被放到合适的位置。4、堆排序（、堆排序（Heap Sort）一种效率非常高，但原理一种效率非常高，但原理较复复杂的排序方法。的排序方法。5

22、、快速排序算法（、快速排序算法（Quick Sort）一种通常情况下效率非常高，但原理一种通常情况下效率非常高，但原理较复复杂的排序的排序40/67n404.2基本算法基本算法 搜索搜索n搜索（搜索（Search）是利用是利用给出的关出的关键值，在一个数据集合或数，在一个数据集合或数据序列中找出与关据序列中找出与关键值匹配的一个或一匹配的一个或一组数据的数据的过程。程。n顺序序查找：找：最最简单的的查找算法。找算法。u从数据序列的第一个数据开始，逐个与关键值比较，直到找到一个从数据序列的第一个数据开始，逐个与关键值比较，直到找到一个或所有的匹配数据为止（也可能找不到）。顺序查找不要求待查找或所

23、有的匹配数据为止（也可能找不到）。顺序查找不要求待查找的数据序列已经排好序。但当待查找数据序列中数据比较多时，顺的数据序列已经排好序。但当待查找数据序列中数据比较多时，顺序查找的效率将十分低。序查找的效率将十分低。n二分二分查找：找：二分二分查找可以提高找可以提高查找效率，但要求待找效率，但要求待查找的找的数据序列已数据序列已经排好序。排好序。u以序列中间数据为界将待查找的数据序列分成两个子序列，比较匹以序列中间数据为界将待查找的数据序列分成两个子序列，比较匹配关键值与中间数据的大小，再确定去哪个子序列中继续查找。这配关键值与中间数据的大小，再确定去哪个子序列中继续查找。这样逐步缩小范围，直到

24、找到所需数据。样逐步缩小范围，直到找到所需数据。41/67n414.2基本算法基本算法 二分法搜索二分法搜索n二分法搜索，二分法搜索，Binary search 找一个数在找一个数在给定已定已排序列表中的位置。排序列表中的位置。例如在例如在A中中查找找45的位置。的位置。n(0+15)/24541455345=4542/67n424.3 二分法搜索二分法搜索算法、程序算法、程序开始开始返回返回-1子序列为空？子序列为空？low=0,high=n-1mid=(low+high)/2返回返回midx=Amid？xAmid？high=mid-1low=mid+1YYYNNN43/67n434.4 基

25、本算法基本算法 迭代与递归迭代与递归n迭代迭代(iterative，http:/ 程序开发程序开发n自自顶向下、逐步求精向下、逐步求精n结构化程序构化程序设计原原则n程序程序风格格46/67n46n 编程序并不难，只要有算法，会程序设计语言，任何人编程序并不难，只要有算法，会程序设计语言，任何人都可以编出程序，但是不同人编出的程序却大不相同。针对同都可以编出程序，但是不同人编出的程序却大不相同。针对同一个问题一个问题:有人编的程序风格好、易读、易维护、易重用、可靠性有人编的程序风格好、易读、易维护、易重用、可靠性高、运行得既快又节省存储空间；高、运行得既快又节省存储空间；有人编的程序风格差、晦

26、涩难懂、难于维护、冗长、正有人编的程序风格差、晦涩难懂、难于维护、冗长、正确性和可靠性极低、运行起来既慢又占用空间。确性和可靠性极低、运行起来既慢又占用空间。n编程序易，编好程序难编程序易，编好程序难。n 要想编出一个风格优美、正确可靠、各方面均优秀的好要想编出一个风格优美、正确可靠、各方面均优秀的好程序，必须按照现代软件工程的规范进行。同时也必须遵循好程序，必须按照现代软件工程的规范进行。同时也必须遵循好的程序设计原则和使用好的程序设计方法的程序设计原则和使用好的程序设计方法。47/67n47n “自顶向下、逐步求精自顶向下、逐步求精”过程中的每一步，分解某过程中的每一步，分解某一具体问题时

27、，主要用到如下四种求精技术：一具体问题时，主要用到如下四种求精技术：1 1.顺序连接的求精顺序连接的求精2 2.分支、选择的求精分支、选择的求精3 3.循环的求精循环的求精4 4.递归的求精递归的求精48/67n48“自顶向下，逐步求精自顶向下，逐步求精”的分析技术实质上是上图所示过程的反复。的分析技术实质上是上图所示过程的反复。求解一个问题求解一个问题粗略的解决方案粗略的解决方案细细 化化第一步子问题第一步子问题第二步子问题第二步子问题第第n步子问题步子问题.前处理前处理 结束结束条件条件后处理后处理进进展展一一步步前处理前处理后处理后处理条条件件处理处理1处理处理2处理处理n.条件条件2条

28、件条件n 条件条件1前处理前处理后处理后处理递归递归条件条件递归递归顺序顺序 连接连接循环循环分支分支 选择选择递归递归 当问题的子解具有前后关系时，采用第一种顺序连接的求精技当问题的子解具有前后关系时，采用第一种顺序连接的求精技术，将问题分解成互不相交的几个子问题的顺序执行。术，将问题分解成互不相交的几个子问题的顺序执行。当问题是分别不同情况而应该进行不同处理时，采用分支、选择的当问题是分别不同情况而应该进行不同处理时，采用分支、选择的求精技术，构造分支。这时要注意分支的条件一定要正确。求精技术，构造分支。这时要注意分支的条件一定要正确。当当问题的子解具有特性：如果有向解的方向前进一步的方法

29、，且问题的子解具有特性：如果有向解的方向前进一步的方法，且不断重复该步骤，即能解决问题，最终达到完全解。则应该采用不断重复该步骤，即能解决问题，最终达到完全解。则应该采用循环的求精技术（构造循环）。这时一定要弄清循环的初始条件、循环的求精技术（构造循环）。这时一定要弄清循环的初始条件、结束条件和有限进展的一步都是什么。结束条件和有限进展的一步都是什么。当当问题的某步解法与前边高层次的某步解法具有相同性质，只是某问题的某步解法与前边高层次的某步解法具有相同性质，只是某些参数不同时，可采用递归的求精技术。这时应注意递归的参数变些参数不同时，可采用递归的求精技术。这时应注意递归的参数变化规律以及递归

30、出口。化规律以及递归出口。49/67n49n “自顶向下、逐步求精自顶向下、逐步求精”是一种思维方式，是一种思维方式，它不是计算机程序员独有的。事实上在日常生活、工作它不是计算机程序员独有的。事实上在日常生活、工作中也经常的使用该技术，只不过不自觉或没意识到罢了。中也经常的使用该技术，只不过不自觉或没意识到罢了。n 例如写一本书、或文章，总要作一个提纲，例如写一本书、或文章，总要作一个提纲，全书分成几章；然后对每一章又列出本章分几节；对每全书分成几章；然后对每一章又列出本章分几节；对每一节又分出几小节等等；最后再具体着手写每个小节。一节又分出几小节等等；最后再具体着手写每个小节。n 这就是自顶

31、向下、逐步求精。这就是自顶向下、逐步求精。50/67n50 采用自顶向下、逐步求精方法构造程序有如下优采用自顶向下、逐步求精方法构造程序有如下优点点:1.1.程序的层次分明、结构清晰程序的层次分明、结构清晰。2.2.便于集体开发程序。对于大型程序来讲，可以每便于集体开发程序。对于大型程序来讲，可以每组负责一个模块（一个子部分），在一个组内又可以每个人组负责一个模块（一个子部分），在一个组内又可以每个人负责一个子模块（更小的子部分）等等。而各个模块之间以负责一个子模块（更小的子部分）等等。而各个模块之间以及各个子模块之间相对独立，互相之间没有制约，各个模块及各个子模块之间相对独立，互相之间没有制

32、约，各个模块的负责人员可以独立的进行各自的程序设计。的负责人员可以独立的进行各自的程序设计。3.3.便于调试。若程序有错误，可以很容易的将错误便于调试。若程序有错误，可以很容易的将错误局部于某一子部分，找出错误，同时每一部分的错误是独立局部于某一子部分，找出错误，同时每一部分的错误是独立的，也不至于影响其它的部分。的，也不至于影响其它的部分。51/67n51n 从从2020世纪世纪6060年代开始，计算机软件系统日益发展，作为软年代开始，计算机软件系统日益发展，作为软件主要组成部分的程序系统越来越庞大，复杂度越来越高件主要组成部分的程序系统越来越庞大，复杂度越来越高，同，同时时出错率也不断增加

33、，系统的可靠性越来越难以保证，维护也出错率也不断增加，系统的可靠性越来越难以保证，维护也越来越困难越来越困难。n比如比如，当年著名的，当年著名的IBM360IBM360操作系统出错率是操作系统出错率是3 3。经过几年运。经过几年运行后，征集了广大用户的意见行后，征集了广大用户的意见,集中进行一次修改，修改完成集中进行一次修改，修改完成后，最后测试出错率仍是后，最后测试出错率仍是3 3。例子很多，此种情况的不断发。例子很多，此种情况的不断发展，最后终于导致一场所谓的软件危机展，最后终于导致一场所谓的软件危机。n在在该背景下，该背景下，19681968年年Dijkstra Dijkstra 提出了

34、结构化程序设计思想。提出了结构化程序设计思想。这种思想的基点是：这种思想的基点是：n“清晰，易懂地书写程序逻辑，使程序结构表现得简单、明快清晰，易懂地书写程序逻辑，使程序结构表现得简单、明快”结构化程序设计原则结构化程序设计原则52/67n52 从这点出发，人们经过艰苦实践，总结出了一套结构化程序设计原则。从这点出发，人们经过艰苦实践，总结出了一套结构化程序设计原则。这套原则要求程序员写出的程序应该是结构良好的，即这套原则要求程序员写出的程序应该是结构良好的，即:1.1.易于保证和验证程序的正确性易于保证和验证程序的正确性 2.2.易于阅读、维护和调试。易于阅读、维护和调试。这种良好结构的程序

35、具体体现在：对任意程序段来讲这种良好结构的程序具体体现在：对任意程序段来讲 1.1.仅有一个入口，一个出口仅有一个入口，一个出口 2.2.没有死循环没有死循环 3.3.没有死码区。没有死码区。为了达到上述目的，强调程序员在写程序时应该为了达到上述目的，强调程序员在写程序时应该:1.1.利用自顶向下、逐步求精的技术设计程序利用自顶向下、逐步求精的技术设计程序 2.2.具有良好的程序设计风格具有良好的程序设计风格 3.3.尽量利用标准的顺序、分支、重复控制结构。保证程序仅有一尽量利用标准的顺序、分支、重复控制结构。保证程序仅有一个入口、一个出口。个入口、一个出口。4.4.限制使用限制使用 GOTO

36、 GOTO 语句。可能一个坏程序的缺点都是由语句。可能一个坏程序的缺点都是由 GOTO GOTO 语语句引起的。句引起的。53/67n53 结构化程序设计的发展，使程序设计从技艺走向工程，为软件工程学发展奠结构化程序设计的发展，使程序设计从技艺走向工程，为软件工程学发展奠定了有力基础。使软件生产由个体作坊式的艺术创作方式发展成为千千万万人参加的定了有力基础。使软件生产由个体作坊式的艺术创作方式发展成为千千万万人参加的工程方式，达到了工程方式，达到了“系列化、产品化系列化、产品化 、工程化、工程化 、标准化、标准化”。“软件工程软件工程”也从这一也从这一时期开始逐步发展起来。时期开始逐步发展起来

37、。能够反映结构化程序设计要求，便于书写结构化程序的程序设计语言，称结能够反映结构化程序设计要求，便于书写结构化程序的程序设计语言，称结构化程序设计语言。可以认为构化程序设计语言。可以认为C C是结构化程序设计语言。是结构化程序设计语言。目目前前程程序序设设计计领领域域的的热热点点是是“面面向向对对象象程程序序设设计计方方法法”和和“基基于于构构件件的的程程序序设计方法设计方法”等等。主要。主要特长在于程序的组织、信息封装、软件重用等特长在于程序的组织、信息封装、软件重用等。结结构构化化程程序序设设计计方方法法针针对对每每个个程程序序模模块块的的设设计计起起着着不不可可缺缺少少的的十十分分关关键

38、键的的作作用用。可可以以说说结结构构化化程程序序设设计计是是一一切切程程序序设设计计技技术术的的基基础础，是是任任何何软软件件工工作作者者必必须须掌掌握握的的技技术。术。54/67n54 程序风格是指程序的书写格式等与易读性、清晰性、互相交流有关的，程序风格是指程序的书写格式等与易读性、清晰性、互相交流有关的，而与程序执行无关或关系不大的一些的问题。而与程序执行无关或关系不大的一些的问题。写程序不仅仅是为了与计算机进行交流，而且也是为了与人进行交流，进写程序不仅仅是为了与计算机进行交流，而且也是为了与人进行交流，进一步还为了给自己或别人阅读，同时程序员自己也需要不断地查阅自己编出一步还为了给自

39、己或别人阅读，同时程序员自己也需要不断地查阅自己编出的程序，更何况程序的维护很可能由别人来做的程序，更何况程序的维护很可能由别人来做。在写程序时要考虑到：程序既是为了在计算机上运行，也是为了今后在写程序时要考虑到：程序既是为了在计算机上运行，也是为了今后的交流和阅读，同时还是为了留下有用的参考文件。的交流和阅读，同时还是为了留下有用的参考文件。程序设计程序设计风格是程序员必须的修养。良好的程序设计风格是程序员在长风格是程序员必须的修养。良好的程序设计风格是程序员在长期的编程实践中逐步发展，积累和提炼出来的。它是产生正确、高效、易读、期的编程实践中逐步发展，积累和提炼出来的。它是产生正确、高效、

40、易读、易维护程序的一种重要的手段。易维护程序的一种重要的手段。程序风格主要涉及程序的行文格式、注释和空白的合适用法、尽量使用程序风格主要涉及程序的行文格式、注释和空白的合适用法、尽量使用合适的助记名来命名标识符、明白地表示出程序结构和数据结构等。合适的助记名来命名标识符、明白地表示出程序结构和数据结构等。程序风格程序风格55/67n55 行文格式行文格式n程序的行文格式不好直接影响程序的可程序的行文格式不好直接影响程序的可读性、性、清晰性和外清晰性和外观。/*A*/#include int i;main()i=25+38;coutI;/*B*/#include int i;main()i=25

41、+38;cout i;/*C*/#include int i;/*声明整型变量声明整型变量i*/int main(void)/*主函数主函数*/i=25+38;/*求和运算求和运算*/couti;/*打印打印*/56/67n56if(b)S1else S2switch(expr)case a1:S1.case an:sn /*switch*/图图1 函函数数定定义义 图图2 IF语语句句 图图3 SWITCH语句语句int main()DS DS ./*main*/do S while(b)for(expr1;expr2;expe3)S/*for*/while(b)S /*while*/图图

42、4 WHILE语语 句句 图图 5 FOR语语 句句 图图6 DO语句语句57/67n57 标识符是程序员给自己引进的常量、类型、变量、函数标识符是程序员给自己引进的常量、类型、变量、函数等起的名字。程序设计语言对如何命名标识符没有限制，标识等起的名字。程序设计语言对如何命名标识符没有限制，标识符也没有固定的含义。但是从使用角度看，标识符表记的每个符也没有固定的含义。但是从使用角度看，标识符表记的每个对象都有具体的含义对象都有具体的含义。为了为了提高可读性和有助于记忆，应该使标识符在拼写上尽提高可读性和有助于记忆，应该使标识符在拼写上尽量和它所标记对象的物理、数学等含义相一致，并且要避免与量和

43、它所标记对象的物理、数学等含义相一致，并且要避免与系统预定义的标准标识符重名系统预定义的标准标识符重名。例如例如，表示圆周率，表示圆周率用用paipai就比用一个一般的就比用一个一般的a a要好；表示要好；表示面积用面积用areaarea就比用就比用s s要好；表示长度用要好；表示长度用lengthlength就比用就比用l l要好；要好；.。标识符标识符58/67n58 注释是间隔符的一种，在程序中的作用相当于一个空格。注注释是间隔符的一种，在程序中的作用相当于一个空格。注释的存在不影响程序的意义，但是它有助于人们阅读和理解释的存在不影响程序的意义，但是它有助于人们阅读和理解程序。程序。因此

44、因此，在程序中适当加入注释是一个好的程序设计习惯。但，在程序中适当加入注释是一个好的程序设计习惯。但是也不要在不需要加注释、意义十分明显的地方加注释。究竟应该是也不要在不需要加注释、意义十分明显的地方加注释。究竟应该在程序的什么地方加注释，以及注释应该如何来写，并没有一个统在程序的什么地方加注释，以及注释应该如何来写，并没有一个统一的标准，这里也只是提一些建议。通常一的标准，这里也只是提一些建议。通常:1.1.所有程序都应该从注释开始所有程序都应该从注释开始 2.2.所有函数也都应该从注释开始所有函数也都应该从注释开始 3.3.也可以对一个程序段、一个语句、一个声明等加注释，以也可以对一个程序

45、段、一个语句、一个声明等加注释，以注明某程序段的功能、一个语句的作用、一个常量或变量的意义等。注明某程序段的功能、一个语句的作用、一个常量或变量的意义等。4.4.当修改有注释的程序时，若程序内容被修改，则相应的注当修改有注释的程序时，若程序内容被修改，则相应的注释也必须作修改。错误的注释往往比没有注释效果更坏。释也必须作修改。错误的注释往往比没有注释效果更坏。注释注释59/67n59 一般的，程序中使用的全部一般的，程序中使用的全部常量常量都要引进一个常量标识符，都要引进一个常量标识符，在程序中不应该出现除了在程序中不应该出现除了0 0、1 1等极其简单的常量以外的其它字面等极其简单的常量以外

46、的其它字面常量。并且常量应该是全程的常量。并且常量应该是全程的。在在程序一开始用宏定义把本程序中用的全部常量定义，并加程序一开始用宏定义把本程序中用的全部常量定义，并加注释标明每个常量的意义、使用位置等。而在每个函数中一般不注释标明每个常量的意义、使用位置等。而在每个函数中一般不应该再包含常量定义。应该再包含常量定义。应该应该按照作用和用途来选择按照作用和用途来选择变量变量的说明位置，并且应该尽量的说明位置，并且应该尽量把变量说明成局部的。把变量说明成局部的。函数函数一般应该只访问它的形式参数和局部量。如果必须访问一般应该只访问它的形式参数和局部量。如果必须访问全局量，应该加必要的注释。全局量

47、，应该加必要的注释。对程序说明的建议对程序说明的建议60/67编程问题编程问题n编程网格是编程网格是如何判断一个程序是否如何判断一个程序是否能通过的能通过的。u服务器服务器上有很多测试数据文件，其中包括标准输入文上有很多测试数据文件，其中包括标准输入文件和标准输出文件。对每个提交的程序件和标准输出文件。对每个提交的程序，都会，都会把标准把标准输入文件作为输入交给它处理，结果保存在另一个文输入文件作为输入交给它处理，结果保存在另一个文件中并与标准输出文件比较。件中并与标准输出文件比较。n常见错误提示信息：常见错误提示信息：u二者一致，则返回二者一致，则返回AcceptedAccepted；u不一

48、致，根据情况返回不一致，根据情况返回Wrong AnswerWrong Answer或或Presentation Presentation ErrorError；u程序没有在规定时间内输出结果，中断程序的执行并程序没有在规定时间内输出结果，中断程序的执行并返回返回Time Limit ExceededTime Limit Exceeded；u编译错误；编译错误；u61/67输入输出型错误输入输出型错误n1、多余的、多余的输入入输出出u出现的最多，比如出现的最多，比如POJ1000计算计算a+b，若多写个，若多写个 cout x)或或while(cin.getline(buff,len)来判断输

49、入是否结束。来判断输入是否结束。62/67输入输出型错误输入输出型错误n3、输入数据入数据读取取错误。u如字符串读成了整数或字符，输入字符串中如字符串读成了整数或字符，输入字符串中含有空格却没有用含有空格却没有用cin.getline输入等，仔细读题输入等，仔细读题可以避免。可以避免。n4、输出格式出格式错误。u常见错误，比如输出要求有常见错误，比如输出要求有Case 1:Case 2:这这样的内容，结果你却只输出了答案，或者输出样的内容，结果你却只输出了答案，或者输出时间格式是时间格式是YYYY-MM-DD，结果写成，结果写成YYYY/MM/DD，如此等等。，如此等等。63/67边界处理型错

50、误边界处理型错误n5、数、数组越界。越界。u常见错误。比如输入字符串最长常见错误。比如输入字符串最长100，结果数组只开到，结果数组只开到了了100，或者输入数据有，或者输入数据有1000个元素，却只开了个大小个元素，却只开了个大小500的数组。大家在开数组的时候，要仔细考虑是否会的数组。大家在开数组的时候，要仔细考虑是否会越界的问题，注意题目描述中说明的数据范围。越界的问题，注意题目描述中说明的数据范围。n6、边界情况考界情况考虑不足不足u常见错误。你可能考虑了一般的情况，却漏掉了一些常见错误。你可能考虑了一般的情况，却漏掉了一些极端的情况极端的情况(一般在数据取最小或者最大的时候出现一般在