1、1/67n1主要内容主要内容n了解算法的基本概念了解算法的基本概念n掌握描述算法的三种基本结构掌握描述算法的三种基本结构n学会算法的流程图描述学会算法的流程图描述n介绍几种基本算法介绍几种基本算法2/67n21 算法的基本概念算法的基本概念n计算机只是一个计算工具，它本身不能主动计算机只是一个计算工具，它本身不能主动帮助我们做任何事情，需要我们告诉它如何帮助我们做任何事情，需要我们告诉它如何进行计算。进行计算。n程序设计程序设计就是要告诉计算机如何进行计算的。就是要告诉计算机如何进行计算的。这与我们中学时代的数学解题过程是一样的，这与我们中学时代的数学解题过程是一样的，只不过描述的手段有所变化
2、而已。只不过描述的手段有所变化而已。3/67n程序的开发程序的开发u 对所要处理的问题域进行正确的理解对所要处理的问题域进行正确的理解u 把这种正确的理解正确的描述出来把这种正确的理解正确的描述出来客观事物（问题域）客观事物（问题域）计算机软件计算机软件语言的鸿沟语言的鸿沟自然语言自然语言编程语言编程语言程序的理解和执行程序的理解和执行（计算机）（计算机）编程（人）编程（人）语言的过渡语言的过渡（人）（人）对问题域的认识对问题域的认识 （人）（人）4/67没有解决方案就没有程序！没有解决方案就没有程序！n现实世界中现实世界中的解决方案的解决方案u为解决一个问题而采取的方法和步骤为解决一个问题而
3、采取的方法和步骤n计算机系统中的算法计算机系统中的算法u适用于计算机系统的解决某个问题的方法和步骤适用于计算机系统的解决某个问题的方法和步骤n写程序写程序“三部曲三部曲”（1）先思考出现实世界）先思考出现实世界中问题的解决方案；中问题的解决方案；（2）再思考出相应的适用于计算机系统的算法；）再思考出相应的适用于计算机系统的算法；（3）用高级语言及其数据结构精确地描述算法）用高级语言及其数据结构精确地描述算法；5/67n5n1984年图灵奖获得者年图灵奖获得者瑞士科学家瑞士科学家尼克劳斯尼克劳斯沃斯沃斯（Niklaus Wirth，Pascal语言的发明者和结构化程序设计创始者）语言的发明者和结
4、构化程序设计创始者）1976年出版了年出版了算法算法+数据结构数据结构=程序设计程序设计一书，提出了一书，提出了著名的公式：著名的公式：“程序程序 数据结构数据结构 算法算法”。u程序：刻画现实世界，解决现实世界中的问题程序：刻画现实世界，解决现实世界中的问题u算法算法：问题的解的描述：问题的解的描述u数据结构：现实世界的数据模型数据结构：现实世界的数据模型n程序就是在程序就是在数据的某些特定的表示方式和结构数据的某些特定的表示方式和结构的基础上对的基础上对抽象算法抽象算法的具体表述的具体表述。n+程序设计方法程序设计方法+语言工具和环境语言工具和环境u程序设计语言：实现的工具程序设计语言：实
5、现的工具6/67n61 算法的基本概念算法的基本概念n算法的定义算法的定义u设计程序的目的是为了求解问题，为解决一个问题设计程序的目的是为了求解问题，为解决一个问题所采取的方法和步骤，就称为所采取的方法和步骤，就称为“算法算法”u算法是算法是一个由一组严格定义的指令组成的过程一个由一组严格定义的指令组成的过程，给，给定一个出始状态，这个过程能够结束在一个确定终定一个出始状态，这个过程能够结束在一个确定终止状态。止状态。u大多数算法都可以用程序实现。大多数算法都可以用程序实现。u常用算法一般都被实现为算法库，供程序员调用。常用算法一般都被实现为算法库，供程序员调用。7/67n71 算法的基本概念
6、算法的基本概念n一个实例：找出一组一个实例：找出一组正整数正整数中的最大的数中的最大的数8/67n81 算法的基本概念算法的基本概念n逐步求解，定义算法的动作逐步求解，定义算法的动作uS1:设设Largest为第一个数为第一个数uS2:若第二个数比若第二个数比Largest大，则设大，则设Largest为第二个数为第二个数uS3:若第三个数比若第三个数比Largest大，则设大，则设Largest为第三个数为第三个数uS4:若第四个数比若第四个数比Largest大，则设大，则设Largest为第四个数为第四个数uS5:若第五个数比若第五个数比Largest大，则设大，则设Largest为第五个
7、数为第五个数9/67n91 算法的基本概念算法的基本概念n算法动作精化算法动作精化uS0:设设Largest为为0uS1:若若当前数当前数比比Largest大，则设大，则设Largest为为当前数当前数uS2:若若当前数当前数比比Largest大，则设大，则设Largest为为当前数当前数uS3:若若当前数当前数比比Largest大，则设大，则设Largest为为当前数当前数uS4:若若当前数当前数比比Largest大，则设大，则设Largest为为当前数当前数uS5:若若当前数当前数比比Largest大，则设大，则设Largest为为当前数当前数10/67n101 算法的基本概念算法的基本概
8、念n算法范化算法范化从从N个正整数中找出最大数的通用算法个正整数中找出最大数的通用算法uS0:设设Largest为为0，当前位置，当前位置p为为0uS1:若当前数比若当前数比Largest大，则设大，则设Largest为当前数为当前数uS2:若若p比比N小，则小，则p增加增加1，返回，返回S1，否则返回，否则返回Largest11/67n111 算法的基本概念算法的基本概念算法的基本性质算法的基本性质n通用性通用性：即适用于某一类问题中的所有个体，而不只是用即适用于某一类问题中的所有个体，而不只是用来解决一个具体的问题。来解决一个具体的问题。n有效性有效性：即应有明确的步骤一步一步地引导计算的
9、进行。即应有明确的步骤一步一步地引导计算的进行。n确定性确定性：即每个步骤都是机械的、有明确定义的动作，不即每个步骤都是机械的、有明确定义的动作，不需要计算者临时动脑筋。需要计算者临时动脑筋。n有限性有限性：对满足算法要求的输入数据，算法应在有限多步对满足算法要求的输入数据，算法应在有限多步内结束，并给出明确的计算结果。内结束，并给出明确的计算结果。n离散性离散性：算法的输入数据及输出数据都应是离散的符号。算法的输入数据及输出数据都应是离散的符号。12/67n121 算法的基本概念算法的基本概念n算法的基本要求算法的基本要求u正确正确u易维护（可读，易修改）易维护（可读，易修改）u方便使用方便
10、使用u高效高效速度快速度快 运行时间少，时间复杂度低运行时间少，时间复杂度低占用内存少占用内存少 空间复杂度低空间复杂度低n算法的效率可以测试，用大量输入数据测量运行的时间和算法的效率可以测试，用大量输入数据测量运行的时间和占用的内存，通过比较判别和选择效率高的算法。占用的内存，通过比较判别和选择效率高的算法。n更重要的是编程前的分析和估计，即理论的计算，给出事更重要的是编程前的分析和估计，即理论的计算，给出事前的判断。前的判断。13/67n131 算法的基本概念算法的基本概念n不了解施加于数据上的算法就无法决定如何不了解施加于数据上的算法就无法决定如何构造数据；反之，算法的结构和选择却常常构
11、造数据；反之，算法的结构和选择却常常在很大程度上依赖于作为基础的数据结构。在很大程度上依赖于作为基础的数据结构。简而言之，简而言之，程序的构成（算法）与数据结构程序的构成（算法）与数据结构是两个不可分割地联系在一起的问题。是两个不可分割地联系在一起的问题。14/67n142 描述算法的三种基本结构描述算法的三种基本结构n已经证明，只使用如下三种结构，就可以描已经证明，只使用如下三种结构，就可以描述任何算法，且算法结构优良述任何算法，且算法结构优良u顺序结构（顺序结构（Sequence）u分支结构（分支结构（Decision）u循环结构（循环结构（Repetition）n每一种基本结构分别只有一
12、个入口和一个出每一种基本结构分别只有一个入口和一个出口口15/67n152.1 顺序结构顺序结构n顺序结构：顺序结构：动作（语句）动作（语句）序列，顺序列，顺序执行序执行u动作动作1 1u动作动作2 2u动作动作3 3uu动作动作n n动作动作1动作动作2动作动作3动作动作116/67n162.2 分支结构分支结构n分支结构：根据分支结构：根据条件条件判断执判断执行什么动作（语句）行什么动作（语句）u如果如果 条件成立条件成立 则则动作动作1 1u否则否则动作动作2 2u分支结束分支结束条件成立？条件成立？动作动作1动作动作2是是否否17/67n172.3 循环结构循环结构n循环结构：循环结构
13、：重复执行重复执行一一系列动作系列动作n当当 条件成立条件成立 做做u动作动作1 1u动作动作2 2uu动作动作n nn循环结束处循环结束处条件成立？条件成立？动作动作1动作动作n是是否否18/67n183 流程图表示算法流程图表示算法n算法是让人来理解的，因此需要有效的算算法是让人来理解的，因此需要有效的算法表示机制法表示机制u自然语言表示法自然语言表示法u伪代码表达法伪代码表达法u流程图表示法流程图表示法19/67n193 流程图表示算法流程图表示算法n流程图显示了程序的流程判断结构。通常流程图显示了程序的流程判断结构。通常包含如下符号：包含如下符号：u开始开始和和结束结束u流程线流程线u
14、输入输入和和输出输出u处理（动作）处理（动作）u条件判断条件判断开始开始/结束结束处理（动作）处理（动作）流程线流程线输入输入/输出输出条件判断条件判断20/67n203 流程图表示算法流程图表示算法n判断判断x0y=xy=-xYesNo21/67n213 流程图表示算法流程图表示算法n循环循环k10动作动作k=k+1YesNo动作动作k=022/67n223 流程图表示算法流程图表示算法n判断闰年判断闰年u能被能被4 4整除且不能被整除且不能被100100整除；整除；u能被能被400400整除整除23/67n233 流程图表示算法流程图表示算法判断闰年判断闰年能被能被4 4整除且不能被整除且
15、不能被100100整除；整除；能被能被400400整除整除n用用C+语言语言实现算法实现算法#include using namespace std;int main()int k;cink;if(k%4=0)if(k%100=0)if(k%400=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;24/67n243 流程图表示算法流程图表示算法n另一种表示：另一种表示：N-SN-S图图
16、（无线的流程图无线的流程图,又称盒图又称盒图）25/67n254 基本算法基本算法n数值算法数值算法u加减乘除、最大最小值、解方程、求微积分加减乘除、最大最小值、解方程、求微积分n非数值算法非数值算法u排序、查找、文本处理、流程处理排序、查找、文本处理、流程处理算法设计与分析需要坚实的数学基础算法设计与分析需要坚实的数学基础26/67n264.1基本算法基本算法-求平方根求平方根n求一个数的平方根：求一个数的平方根：x=u迭代迭代公式公式(牛顿迭代法牛顿迭代法)x1=1 xn+1=(xn+a/xn)/2 迭代计算，直到迭代计算，直到 xn+1 xn 的绝对的绝对值小于误差要求，例如小于值小于误
17、差要求，例如小于0.00001，即保留小数点后，即保留小数点后5位。位。输入数输入数a开始开始初始化：初始化：x2=1x1=x2x2=(x1+a/x1)/2x2-x1的绝对值的绝对值小于小于0.00001？N结束结束输出输出x2Ya27/67n27 求平方根求平方根(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
18、;x2=(x1+a/x1)/2;28/67n284.2基本算法基本算法 排序排序n排序（排序（Sort）是指对一些数据的重新组织，使得是指对一些数据的重新组织，使得数据由大到小（降序）或者由小到大（升序）存数据由大到小（降序）或者由小到大（升序）存储。排序是很一种基本的要求。我们所感兴趣的储。排序是很一种基本的要求。我们所感兴趣的是如何寻找到一个好（计算速度快或占用内存少）是如何寻找到一个好（计算速度快或占用内存少）的办法来进行排序的办法来进行排序。u选择排序选择排序u冒泡排序冒泡排序29/67n294.2排序排序选择排序选择排序n选择排序，选择排序，Selection sortu数据列表被分
19、为两个子列表：已排序和未排数据列表被分为两个子列表：已排序和未排序。找到未排序列表中值最小（或最大）的序。找到未排序列表中值最小（或最大）的元素，并把它和未排序列表中的第一个元素元素，并把它和未排序列表中的第一个元素进行交换。进行交换。30/67n304.2 选择排序选择排序示例（续）示例（续）31/67n314.2 选择排序选择排序示例示例32/67n324.2 选择排序选择排序算法、程序算法、程序初始化：初始化：wall=0开始开始找到未排序列表找到未排序列表中的最小元素中的最小元素与未排序列表中与未排序列表中第一个元素交换第一个元素交换是否还有是否还有未排序元素？未排序元素？N结束结束Y
20、wall=wall+133/67n334.2 排序排序冒泡排序冒泡排序n冒泡排序，冒泡排序，Bubble sortu数据列表被分为两个子列表：已排序和未排序。数据列表被分为两个子列表：已排序和未排序。未排序列表中最小（或最大）的元素通过冒泡的未排序列表中最小（或最大）的元素通过冒泡的形式（从后往前冒泡）从未排序列表中交换到已形式（从后往前冒泡）从未排序列表中交换到已排序列表中。排序列表中。34/67n344.2 冒泡排序冒泡排序示例示例比较比较比较并交换比较并交换冒泡的过程冒泡的过程35/67n354.2 冒泡排序冒泡排序示例（续）示例（续）36/67n364.2 冒泡排序冒泡排序示例（续）示
21、例（续）37/67n374.2 冒泡排序冒泡排序算法、程序算法、程序初始化：初始化：wall=0开始开始还有未排序的数？还有未排序的数？N结束结束Y交换相邻数交换相邻数还有未冒泡的数？还有未冒泡的数？比较相邻数比较相邻数YN38/67n384.2基本算法基本算法 排序排序n各种排序方法简介：各种排序方法简介：就地排序算法（不增加新的存储空间）就地排序算法（不增加新的存储空间）1、插入排序法（、插入排序法（Insert Sort）将一个数插入到序列中的合适位置。将一个数插入到序列中的合适位置。2、选择排序法（、选择排序法（Selection Sort）每次把最小（大）的元素交换到最前面。每次把最
22、小（大）的元素交换到最前面。3、冒泡排序法（、冒泡排序法（Bubble Sort比较并交换相邻的元素，直到所有元素都被放到合适的位置。比较并交换相邻的元素，直到所有元素都被放到合适的位置。4、堆排序（、堆排序（Heap Sort）一种效率非常高，但原理较复杂的排序方法。一种效率非常高，但原理较复杂的排序方法。5、快速排序算法（、快速排序算法（Quick Sort）一种通常情况下效率非常高，但原理较复杂的排序一种通常情况下效率非常高，但原理较复杂的排序39/67n394.2基本算法基本算法 搜索搜索n搜索（搜索（Search）是利用给出的关键值，在一个数据集合或是利用给出的关键值，在一个数据集合
23、或数据序列中找出与关键值匹配的一个或一组数据的过程。数据序列中找出与关键值匹配的一个或一组数据的过程。n顺序查找：顺序查找：最简单的查找算法。最简单的查找算法。u从数据序列的第一个数据开始，逐个与关键值比较，直到找到一个从数据序列的第一个数据开始，逐个与关键值比较，直到找到一个或所有的匹配数据为止（也可能找不到）。顺序查找不要求待查找或所有的匹配数据为止（也可能找不到）。顺序查找不要求待查找的数据序列已经排好序。但当待查找数据序列中数据比较多时，顺的数据序列已经排好序。但当待查找数据序列中数据比较多时，顺序查找的效率将十分低。序查找的效率将十分低。n二分查找：二分查找：二分查找可以提高查找效率
24、，但要求待查找的二分查找可以提高查找效率，但要求待查找的数据序列已经排好序。数据序列已经排好序。u以序列中间数据为界将待查找的数据序列分成两个子序列，比较匹以序列中间数据为界将待查找的数据序列分成两个子序列，比较匹配关键值与中间数据的大小，再确定去哪个子序列中继续查找。这配关键值与中间数据的大小，再确定去哪个子序列中继续查找。这样逐步缩小范围，直到找到所需数据。样逐步缩小范围，直到找到所需数据。40/67n404.2基本算法基本算法 二分法搜索二分法搜索n二分法搜索，二分法搜索，Binary search 找一个数在给定已找一个数在给定已排序列表中的位置。排序列表中的位置。例如在例如在A中查找
25、中查找45的位置。的位置。16312 24353241 43514553 568875091157(0+16)/2158(8+15)/211108(8+10)/2943514553 5688759143514516312 2435324116312 2435324153 56887591AAA16312 24353241 43514553 568875091157(0+16)/2158(8+15)/211108(8+10)/2943514553 5688759143514516312 2435324116312 2435324153 56887591AAAn(0+15)/24541455345
26、=4541/67n414.3 二分法搜索二分法搜索算法、程序算法、程序开始开始返回返回-1子序列为空？子序列为空？low=0,high=n-1mid=(low+high)/2返回返回midx=Amid？xAmid？high=mid-1low=mid+1YYYNNN42/67n424.4 基本算法基本算法 迭代与递归迭代与递归n迭代迭代(iterative，baike./view/649495.htm)与与递归递归(recursive，baike./view/96473.htm)43/67n43小结小结n算法的概念算法的概念n描述算法的三种基本结构描述算法的三种基本结构u顺序结构、分支结构、循环
27、结构顺序结构、分支结构、循环结构n算法的流程图表示与算法的程序实现算法的流程图表示与算法的程序实现u闰年判断闰年判断n基本算法介绍基本算法介绍u迭代计算：求平方根迭代计算：求平方根u排序：选择排序、冒泡排序排序：选择排序、冒泡排序u二分查找二分查找u迭代与递归迭代与递归44/67n44 程序开发程序开发n自顶向下、逐步求精自顶向下、逐步求精n结构化程序设计原则结构化程序设计原则n程序风格程序风格45/67n45n 编程序并不难，只要有算法，会程序设计语言，任何人编程序并不难，只要有算法，会程序设计语言，任何人都可以编出程序，但是不同人编出的程序却大不相同。针对同都可以编出程序，但是不同人编出的
28、程序却大不相同。针对同一个问题一个问题:有人编的程序风格好、易读、易维护、易重用、可靠性有人编的程序风格好、易读、易维护、易重用、可靠性高、运行得既快又节省存储空间；高、运行得既快又节省存储空间；有人编的程序风格差、晦涩难懂、难于维护、冗长、正有人编的程序风格差、晦涩难懂、难于维护、冗长、正确性和可靠性极低、运行起来既慢又占用空间。确性和可靠性极低、运行起来既慢又占用空间。n编程序易，编好程序难编程序易，编好程序难。n 要想编出一个风格优美、正确可靠、各方面均优秀的好要想编出一个风格优美、正确可靠、各方面均优秀的好程序，必须按照现代软件工程的规范进行。同时也必须遵循好程序，必须按照现代软件工程
29、的规范进行。同时也必须遵循好的程序设计原则和使用好的程序设计方法的程序设计原则和使用好的程序设计方法。46/67n46n “自顶向下、逐步求精自顶向下、逐步求精”过程中的每一步，分解某过程中的每一步，分解某一具体问题时，主要用到如下四种求精技术：一具体问题时，主要用到如下四种求精技术：1 1.顺序连接的求精顺序连接的求精2 2.分支、选择的求精分支、选择的求精3 3.循环的求精循环的求精4 4.递归的求精递归的求精47/67n47“自顶向下，逐步求精自顶向下，逐步求精”的分析技术实质上是上图所示过程的反复。的分析技术实质上是上图所示过程的反复。求解一个问题求解一个问题粗略的解决方案粗略的解决方
30、案细细 化化第一步子问题第一步子问题第二步子问题第二步子问题第第n步子问题步子问题.前处理前处理 结束结束条件条件后处理后处理进进展展一一步步前处理前处理后处理后处理条条件件处理处理1处理处理2处理处理n.条件条件2条件条件n 条件条件1前处理前处理后处理后处理递归递归条件条件递归递归顺序顺序 连接连接循环循环分支分支 选择选择递归递归 当问题的子解具有前后关系时，采用第一种顺序连接的求精技当问题的子解具有前后关系时，采用第一种顺序连接的求精技术，将问题分解成互不相交的几个子问题的顺序执行。术，将问题分解成互不相交的几个子问题的顺序执行。当问题是分别不同情况而应该进行不同处理时，采用分支、选择
31、当问题是分别不同情况而应该进行不同处理时，采用分支、选择的求精技术，构造分支。这时要注意分支的条件一定要正确。的求精技术，构造分支。这时要注意分支的条件一定要正确。当当问题的子解具有特性：如果有向解的方向前进一步的方法，且问题的子解具有特性：如果有向解的方向前进一步的方法，且不断重复该步骤，即能解决问题，最终达到完全解。则应该采用不断重复该步骤，即能解决问题，最终达到完全解。则应该采用循环的求精技术（构造循环）。这时一定要弄清循环的初始条件、循环的求精技术（构造循环）。这时一定要弄清循环的初始条件、结束条件和有限进展的一步都是什么。结束条件和有限进展的一步都是什么。当当问题的某步解法与前边高层
32、次的某步解法具有相同性质，只是某问题的某步解法与前边高层次的某步解法具有相同性质，只是某些参数不同时，可采用递归的求精技术。这时应注意递归的参数变些参数不同时，可采用递归的求精技术。这时应注意递归的参数变化规律以及递归出口。化规律以及递归出口。48/67n48n “自顶向下、逐步求精自顶向下、逐步求精”是一种思维方式，是一种思维方式，它不是计算机程序员独有的。事实上在日常生活、工它不是计算机程序员独有的。事实上在日常生活、工作中也经常的使用该技术，只不过不自觉或没意识到作中也经常的使用该技术，只不过不自觉或没意识到罢了。罢了。n 例如写一本书、或文章，总要作一个提纲，例如写一本书、或文章，总要
33、作一个提纲，全书分成几章；然后对每一章又列出本章分几节；对全书分成几章；然后对每一章又列出本章分几节；对每一节又分出几小节等等；最后再具体着手写每个小每一节又分出几小节等等；最后再具体着手写每个小节。节。n 这就是自顶向下、逐步求精。这就是自顶向下、逐步求精。49/67n49 采用自顶向下、逐步求精方法构造程序有如下优采用自顶向下、逐步求精方法构造程序有如下优点点:1.1.程序的层次分明、结构清晰程序的层次分明、结构清晰。2.2.便于集体开发程序。对于大型程序来讲，可以每便于集体开发程序。对于大型程序来讲，可以每组负责一个模块（一个子部分），在一个组内又可以每个人组负责一个模块（一个子部分），
34、在一个组内又可以每个人负责一个子模块（更小的子部分）等等。而各个模块之间以负责一个子模块（更小的子部分）等等。而各个模块之间以及各个子模块之间相对独立，互相之间没有制约，各个模块及各个子模块之间相对独立，互相之间没有制约，各个模块的负责人员可以独立的进行各自的程序设计。的负责人员可以独立的进行各自的程序设计。3.3.便于调试。若程序有错误，可以很容易的将错误便于调试。若程序有错误，可以很容易的将错误局部于某一子部分，找出错误，同时每一部分的错误是独立局部于某一子部分，找出错误，同时每一部分的错误是独立的，也不至于影响其它的部分。的，也不至于影响其它的部分。50/67n50n 从从2020世纪世
35、纪6060年代开始，计算机软件系统日益发展，作为年代开始，计算机软件系统日益发展，作为软件主要组成部分的程序系统越来越庞大，复杂度越来越高软件主要组成部分的程序系统越来越庞大，复杂度越来越高，同时同时出错率也不断增加，系统的可靠性越来越难以保证，维护出错率也不断增加，系统的可靠性越来越难以保证，维护也越来越困难也越来越困难。n比如比如，当年著名的，当年著名的IBM360IBM360操作系统出错率是操作系统出错率是3 3。经过几年。经过几年运行后，征集了广大用户的意见运行后，征集了广大用户的意见,集中进行一次修改，修改完集中进行一次修改，修改完成后，最后测试出错率仍是成后，最后测试出错率仍是3
36、3。例子很多，此种情况的不断。例子很多，此种情况的不断发展，最后终于导致一场所谓的软件危机发展，最后终于导致一场所谓的软件危机。n在在该背景下，该背景下，19681968年年Dijkstra Dijkstra 提出了结构化程序设计思想。提出了结构化程序设计思想。这种思想的基点是：这种思想的基点是：n“清晰，易懂地书写程序逻辑，使程序结构表现得简单、明快清晰，易懂地书写程序逻辑，使程序结构表现得简单、明快”结构化程序设计原则结构化程序设计原则51/67n51 从这点出发，人们经过艰苦实践，总结出了一套结构化程序设计原则。从这点出发，人们经过艰苦实践，总结出了一套结构化程序设计原则。这套原则要求程
37、序员写出的程序应该是结构良好的，即这套原则要求程序员写出的程序应该是结构良好的，即:1.1.易于保证和验证程序的正确性易于保证和验证程序的正确性 2.2.易于阅读、维护和调试。易于阅读、维护和调试。这种良好结构的程序具体体现在：对任意程序段来讲这种良好结构的程序具体体现在：对任意程序段来讲 1.1.仅有一个入口，一个出口仅有一个入口，一个出口 2.2.没有死循环没有死循环 3.3.没有死码区。没有死码区。为了达到上述目的，强调程序员在写程序时应该为了达到上述目的，强调程序员在写程序时应该:1.1.利用自顶向下、逐步求精的技术设计程序利用自顶向下、逐步求精的技术设计程序 2.2.具有良好的程序设
38、计风格具有良好的程序设计风格 3.3.尽量利用标准的顺序、分支、重复控制结构。保证程序仅有一尽量利用标准的顺序、分支、重复控制结构。保证程序仅有一个入口、一个出口。个入口、一个出口。4.4.限制使用限制使用 GOTO GOTO 语句。可能一个坏程序的缺点都是由语句。可能一个坏程序的缺点都是由 GOTO GOTO 语句引起的。语句引起的。52/67n52 结构化程序设计的发展，使程序设计从技艺走向工程，为软件工程学发展奠结构化程序设计的发展，使程序设计从技艺走向工程，为软件工程学发展奠定了有力基础。使软件生产由个体作坊式的艺术创作方式发展成为千千万万人参加的定了有力基础。使软件生产由个体作坊式的
39、艺术创作方式发展成为千千万万人参加的工程方式，达到了工程方式，达到了“系列化、产品化系列化、产品化 、工程化、工程化 、标准化、标准化”。“软件工程软件工程”也从这一也从这一时期开始逐步发展起来。时期开始逐步发展起来。能够反映结构化程序设计要求，便于书写结构化程序的程序设计语言，称结能够反映结构化程序设计要求，便于书写结构化程序的程序设计语言，称结构化程序设计语言。可以认为构化程序设计语言。可以认为C C是结构化程序设计语言。是结构化程序设计语言。目前程序设计领域的热点是目前程序设计领域的热点是“面向对象程序设计方法面向对象程序设计方法”和和“基于构件的程序基于构件的程序设计方法设计方法”等等
40、。主要。主要特长在于程序的组织、信息封装、软件重用等特长在于程序的组织、信息封装、软件重用等。结构化程序设计方法针对每个程序模块的设计起着不可缺少的十分关键的作用。结构化程序设计方法针对每个程序模块的设计起着不可缺少的十分关键的作用。可以说结构化程序设计是一切程序设计技术的基础，是任何软件工作者必须掌握的技可以说结构化程序设计是一切程序设计技术的基础，是任何软件工作者必须掌握的技术。术。53/67n53 程序风格是指程序的书写格式等与易读性、清晰性、互相交流有关的，程序风格是指程序的书写格式等与易读性、清晰性、互相交流有关的，而与程序执行无关或关系不大的一些的问题。而与程序执行无关或关系不大的
41、一些的问题。写程序不仅仅是为了与计算机进行交流，而且也是为了与人进行交流，进写程序不仅仅是为了与计算机进行交流，而且也是为了与人进行交流，进一步还为了给自己或别人阅读，同时程序员自己也需要不断地查阅自己编出一步还为了给自己或别人阅读，同时程序员自己也需要不断地查阅自己编出的程序，更何况程序的维护很可能由别人来做的程序，更何况程序的维护很可能由别人来做。在写程序时要考虑到：程序既是为了在计算机上运行，也是为了今后在写程序时要考虑到：程序既是为了在计算机上运行，也是为了今后的交流和阅读，同时还是为了留下有用的参考文件。的交流和阅读，同时还是为了留下有用的参考文件。程序设计程序设计风格是程序员必须的
42、修养。良好的程序设计风格是程序员在风格是程序员必须的修养。良好的程序设计风格是程序员在长期的编程实践中逐步发展，积累和提炼出来的。它是产生正确、高效、易长期的编程实践中逐步发展，积累和提炼出来的。它是产生正确、高效、易读、易维护程序的一种重要的手段。读、易维护程序的一种重要的手段。程序风格主要涉及程序的行文格式、注释和空白的合适用法、尽量使程序风格主要涉及程序的行文格式、注释和空白的合适用法、尽量使用合适的助记名来命名标识符、明白地表示出程序结构和数据结构等。用合适的助记名来命名标识符、明白地表示出程序结构和数据结构等。程序风格程序风格54/67n54 行文格式行文格式n程序的行文格式不好直接
43、影响程序的可读性、程序的行文格式不好直接影响程序的可读性、清晰性和外观。清晰性和外观。/*A*/#include int i;main()i=25+38;coutI;/*B*/#include int i;main()i=25+38;cout i;/*C*/#include int i;/*声明整型变量声明整型变量i*/int main(void)/*主函数主函数*/i=25+38;/*求和运算求和运算*/couti;/*打印打印*/55/67n55if(b)S1else S2switch(expr)case a1:S1.case an:sn /*switch*/图图1 函数定义函数定义 图图
44、2 IF语句语句 图图3 SWITCH语句语句int main()DS DS ./*main*/do S while(b)for(expr1;expr2;expe3)S/*for*/while(b)S /*while*/图图4 WHILE语句语句 图图5 FOR语句语句 图图6 DO语句语句56/67n56 标识符是程序员给自己引进的常量、类型、变量、函数标识符是程序员给自己引进的常量、类型、变量、函数等起的名字。程序设计语言对如何命名标识符没有限制，标识等起的名字。程序设计语言对如何命名标识符没有限制，标识符也没有固定的含义。但是从使用角度看，标识符表记的每个符也没有固定的含义。但是从使用角
45、度看，标识符表记的每个对象都有具体的含义对象都有具体的含义。为了为了提高可读性和有助于记忆，应该使标识符在拼写上尽提高可读性和有助于记忆，应该使标识符在拼写上尽量和它所标记对象的物理、数学等含义相一致，并且要避免与量和它所标记对象的物理、数学等含义相一致，并且要避免与系统预定义的标准标识符重名系统预定义的标准标识符重名。例如例如，表示圆周率，表示圆周率用用paipai就比用一个一般的就比用一个一般的a a要好；表示要好；表示面积用面积用areaarea就比用就比用s s要好；表示长度用要好；表示长度用lengthlength就比用就比用l l要要好；好；.。标识符标识符57/67n57 注释是
46、间隔符的一种，在程序中的作用相当于一个空格。注注释是间隔符的一种，在程序中的作用相当于一个空格。注释的存在不影响程序的意义，但是它有助于人们阅读和理解释的存在不影响程序的意义，但是它有助于人们阅读和理解程序。程序。因此因此，在程序中适当加入注释是一个好的程序设计习惯。但，在程序中适当加入注释是一个好的程序设计习惯。但是也不要在不需要加注释、意义十分明显的地方加注释。究竟应该是也不要在不需要加注释、意义十分明显的地方加注释。究竟应该在程序的什么地方加注释，以及注释应该如何来写，并没有一个统在程序的什么地方加注释，以及注释应该如何来写，并没有一个统一的标准，这里也只是提一些建议。通常一的标准，这里
47、也只是提一些建议。通常:1.1.所有程序都应该从注释开始所有程序都应该从注释开始 2.2.所有函数也都应该从注释开始所有函数也都应该从注释开始 3.3.也可以对一个程序段、一个语句、一个声明等加注释，以也可以对一个程序段、一个语句、一个声明等加注释，以注明某程序段的功能、一个语句的作用、一个常量或变量的意义等。注明某程序段的功能、一个语句的作用、一个常量或变量的意义等。4.4.当修改有注释的程序时，若程序内容被修改，则相应的注当修改有注释的程序时，若程序内容被修改，则相应的注释也必须作修改。错误的注释往往比没有注释效果更坏。释也必须作修改。错误的注释往往比没有注释效果更坏。注释注释58/67n
48、58 一般的，程序中使用的全部一般的，程序中使用的全部常量常量都要引进一个常量标识符，都要引进一个常量标识符，在程序中不应该出现除了在程序中不应该出现除了0 0、1 1等极其简单的常量以外的其它字面等极其简单的常量以外的其它字面常量。并且常量应该是全程的常量。并且常量应该是全程的。在在程序一开始用宏定义把本程序中用的全部常量定义，并加程序一开始用宏定义把本程序中用的全部常量定义，并加注释标明每个常量的意义、使用位置等。而在每个函数中一般不注释标明每个常量的意义、使用位置等。而在每个函数中一般不应该再包含常量定义。应该再包含常量定义。应该应该按照作用和用途来选择按照作用和用途来选择变量变量的说明
49、位置，并且应该尽量的说明位置，并且应该尽量把变量说明成局部的。把变量说明成局部的。函数函数一般应该只访问它的形式参数和局部量。如果必须访问一般应该只访问它的形式参数和局部量。如果必须访问全局量，应该加必要的注释。全局量，应该加必要的注释。对程序说明的建议对程序说明的建议59/67编程问题编程问题n编程网格是编程网格是如何判断一个程序是否如何判断一个程序是否能通过的能通过的。u服务器服务器上有很多测试数据文件，其中包括标准输入文上有很多测试数据文件，其中包括标准输入文件和标准输出文件。对每个提交的程序件和标准输出文件。对每个提交的程序，都会，都会把标准把标准输入文件作为输入交给它处理，结果保存在
50、另一个文输入文件作为输入交给它处理，结果保存在另一个文件中并与标准输出文件比较。件中并与标准输出文件比较。n常见错误提示信息：常见错误提示信息：u二者一致，则返回二者一致，则返回AcceptedAccepted；u不一致，根据情况返回不一致，根据情况返回Wrong AnswerWrong Answer或或Presentation Presentation ErrorError；u程序没有在规定时间内输出结果，中断程序的执行并程序没有在规定时间内输出结果，中断程序的执行并返回返回Time Limit ExceededTime Limit Exceeded；u编译错误；编译错误；u60/67输入输
