第5章_c语言程序的组织结构.ppt

1、5.3 自定义函数,5.2 标准函数,5.1 函数概述,5.4 函数与数组的应用实例,5.5 递归算法与递归函数,第5章 程序的组织结构,5.1 函数概述,结构化程序设计方法的核心是自顶向下，逐步求精，具体的实现策略是将复杂的问题逐步分解成相对简单的子问题，这样将有利于降低解决问题的难度，提高程序开发的效率。将一个问题分解成若干个子问题的过程称为模块化。 在C程序中，模块用函数实现。函数是构成C程序的基本单位。它由函数首部和函数体两个部分组成，函数首部包含函数的返回类型、函数名称和参数表的声明，函数体包含实现特定功能所需要执行的语句序列。,5.2 标准函数,C语言提供了很多标准函数，它们被放置

2、在一起，形成了一个标准函数库。 函数原型 函数原型是指不包含函数体的函数声明。 C语言规定，所有的函数必须先定义后调用。对于标准函数而言，由于它们的定义已经在C语言提供的标准函数库中，所以，人们在调用它们的时候，只需要在程序的前面利用编译预处理命令include将相应的函数原型加入到程序中就可以了。,例1：根据给定的两个坐标点（x1,y1）和（x2，y2），计算两点之间的距离。,问题分析 计算两点之间距离的公式为 d=,在这个公式中含有平方和开平方的运算，可以直接利用C语言提供的标准函数实现这两个运算。,算法描述,#include #include main( ) int x1, y1, x2

3、, y2; double distance; printf(nEnter 2 coordinates(x1,y1,x2,y2)n); scanf(%d%d%d%d, ,程序代码,例2：掷骰子游戏。 骰子是一个有六个面的正方体，每个面分别印有16之间的小圆点代表点数。假设这个游戏的规则是：两个人轮流掷骰子6次，并将每次投掷的点数累加起来。点数多者获胜；点数相同平局。 请编写程序，模拟这个游戏的过程，并给出玩100盘之后,谁是最终的获胜者。,随机数的产生及应用实例,问题分析 由于每个人掷骰子所得到的点数是随机的，所以需要借助随机数发生器，每次产生一个16之间的整数，以此模拟玩者掷骰子的点数。 为了

4、计算在每盘中，甲、乙两人所掷的点数，需要定义两个int型变量d1，d2，用于作为记录每个人投掷点数的累加器。 为了记录每个人的获胜盘数，需要再定义两个int型变量c1，c2，用于记录每个人获胜的盘数。,算法描述,#include #include main() int d1, d2, c1, c2, i, j; c1 = c2 = 0; /* 初始化 */ randomize( ); /* 初始化随机数产生器 */ for (i=1; id2) c1+; /* 累加获胜盘数 */ else if (d1c2) /* 输出最终获胜者信息 */ printf(nThe first win.); e

5、lse if (c1c2) printf(nThe second win.); else printf(They tie.); ,程序代码,5.3 自定义函数,函数的定义 基本格式 （） ； 例: double distance(int x, int y) double d; d = sqrt(x*x+y*y); return d; ,C语言规定，一个函数可以有返回值，也可以没有返回值。如果有返回值，返回值的类型在函数名前声明，并在函数体中利用return 语句将返回值返回；如果没有返回值，在函数名前声明void。默认的返回类型是int。 函数名不但应该符合C语言的自定义标识符命名规范，还应该

6、“见名知意”。 参数表是函数之间交换信息的接口。既可以通过它将外界的数据传递给函数，也可以通过它将函数的操作结果带出函数。如果形式参数属于一维数组类型，无须指出一维数组的元素个数。 函数体是函数的核心部分，在这里列出了需要执行的语句序列。,函数的调用 函数调用语句的基本格式为： （）； 实在参数与形式参数的数据类型和个数一一对应。,函数的返回值 在声明函数的时候，函数名前使用了保留字void，说明这个函数没有返回值；否则，这个函数执行完毕后，应该返回一个相应类型的数值。 return 表达式；,参数的传递 定义函数时所给的参数被称为形式参数，这是由于当函数没有处于执行状态时，系统并不为这些参数

7、分配存储空间，换言之，这些参数此时并不存在，只是用来说明在调用这个函数时需要在这个位置向函数提供的数据类型，因此，在调用函数之后，参数传递需要经历两个基本步骤：首先，根据形式参数的声明格式，为每一个形式参数分配存储空间；然后再将实在参数的值赋给对应的形式参数。,例3：输出乘法口诀表。 乘法口诀表又被称为“九九表”，是一种小学生在学习乘法运算时需要熟背的一个口诀表。它是一个9行9列的二维表格，加上一个行标题和一个列标题，显示出来应该是10行10列。,自定义函数的应用实例,问题分析 行与行之间可以采用若干个“=”或“-”字符表示表格之间的线段，为此，可以定义一个函数，专门用来连续地显示若干个字符，

8、以避免在每次需要显示线段的时候，都重复地书写相应的语句序列。,#include void drawLine(int n,char ch); /* 连续显示n个ch字符 */ main() int i,j; printf(n 9.9 tablen); /* 显示表名 */ drawLine(30, =); /* 显示每列的标题 */ printf(n 1 2 3 4 5 6 7 8 9); drawLine(30, =); for (i=1; i=9; i+) /* 显示每行的内容 */ printf(n%3d, i); for (j=1; j=9; j+) printf(%3d, i*j);

9、if (i0); ,程序代码,冒泡排序 为了便于查找、统计，排序是一种经常需要进行的操作。排序的方法有很多种，上一章中介绍的简单选择排序是一种基于选择手段实现的排序方法。 冒泡排序的基本思路是不断地将所有相邻数据进行比效，如果前面的数据大于后面的数据（ajaj+1），就将两个位置的数据进行交换，最终实现将所有的数据按照非递减的顺序重新排列的目的。,问题分析 将整个待排序的数据序列划分成有序区域和无序区域。初始状态有序区域为空，无序区域包括所有待排序的数据。 对无序区域从前向后依次对相邻的两个数据进行比较，若逆序则将其交换，从而使得较小的数据像泡沫一样“飘浮”（向前），较大的数据“下沉”（向后）

10、。 每经过一趟冒泡排序，都会使无序区域中的最大数据进入有序区域。如果有n个数据等待排序，则最多经过n-1趟冒泡排序就可以将所有的数据排列好。,例6：冒泡排序。,算法描述,#include #include #define NUM 10 void input(int value ); void output(int value ); void sort(int value ); main( ) int valueNUM; /* 存储待排序的数据数列 */ input(value); output(value); sort(value); output(value); void input(int

11、 value ) /* 输入待排序数据 */ int i; printf(nEnter %d integers:,NUM); for (i=0; iNUM; i+) scanf(%d, ,程序代码,void output(int value ) /* 输出显示数据数列 */ int i; printf(n); for (i=0; i=1; i-) /* 控制排序趟数 */ for (j=0; jvaluej+1) /* 如果两个相邻数据逆序，交换 */ temp = valuej; valuej = valuej+1; valuej+1 = temp; ,程序代码,5.5 递归算法与递归函数,

12、概述 n!其含义为1234(n-1) n。从这个数学公式中可以发现， n!等于n与（n-1）！的乘积。即将计算n! 的过程分解成n与（n-1）！的乘积；这样分解的子问题除了n的值以外，与原问题具有相同的特征，所以求解子问题的基本方法与求解整个问题所采用的方法一样。具有这种特征的求解算法被称为递归算法，,实现阶乘递归算法的递归函数 long fact(int n) if (n=0) return 1; else return n* fact(n-1); ,y=fact(3),递归函数的调用过程,问题分析 解决这个问题似乎有些复杂，但采用递归方式就简单多了。3个数的全排列是每个数轮流充当一次第一个

13、数，再加上后面n-1个数的全排列，而求解n-1个数的全排列方法与求解n个数的全排列方法完全一样，因此，可以设计一个递归函数，实现求n个数全排列的操作。考虑到每次递归过程中，将针对n个数据进行排列，而这些数据来自同一数据序列，故设置数组保存数据序列，以数组名和数据个数作为函数的参数。,例7：求解n个数据的全排列。,#include #define NUM 3 void anagram(int , int); void print(int ); main( ) int dNUM; int i; for (i=0; i=0; i-) printf(%d ,di); ,程序代码,void anagra

14、m(int d , int n) /* 求解n的全排列 */ int i, j, temp; if (n=1) /* n=1直接输出 */ print(d); return; for (i=0; in; i+) anagram(d, n-1); /* 对后面n-1个数全排列 */ temp = d0; /* 轮换第一个位置的数 */ for (j=1; j=n-1; j+) dj-1 = dj; /* 将每个数据向前移 */ dn-1 = temp; ,程序代码,用递归函数实现二分查找 二分查找的问题，它是对有序数列进行查找操作的一种有效方法。实际上，这种查找方法是一个递归的过程。,问题分析

15、二分查找也是信息处理中常用的一个算法。为了提高这个算法的重用性，单独设置一个函数来实现该算法是适当的。二分查找算法可以描述为：针对一个已经从小到大排序的数据序列，用给定数据key与查找区间中央位置的数据比较，如果相等则表明查找成功；否则，如果key比中央位置的数据小，则在前半个区间用同样的方法继续查找；否则在后半个区间用同样的方法继续查找。因此，这是一个递归的过程。当查找区间的长度为0时，说明查找不成功。,例8：采用递归方式实现二分查找。,#include #include #define NUM 10 void input(int value ); void output(int value

16、 ); int search(int value , int key, int low, int high); main( ) int valueNUM, result, key; input(value); /* 输入有序序列 */ output(value); /* 输出有序数列 */ printf(nEnter a key:); /* 输入待查找的数值 */ scanf(%d, ,程序代码,void input(int value ) /* 创建有序数列 */ int i; for (i=0; ihigh) return -1; /* 查找区间为空 */ mid = (low+high)

17、/2; /* 求中间位置 */ if (valuemid=key) return mid; /* 得到查找的数据位置 */ if (keyvaluemid) return search(value, key, low, mid-1); /* 在下半区查找 */ else return search(value, key, mid+1, high); /* 在上半区查找 */ ,程序代码,变量的生存期与作用域 变量是存储空间在程序中的一种表示，它承担着存储操作数据和结果的重任，是程序中不可缺少的主要元素。C语言规定，每个变量必须先定义后引用。 人们将变量占据存储空间的时间称为变量的生存期，将变量

18、可以引用的区域称为变量的作用域。 从作用域角度划分 全局变量：在函数外部定义的变量被称为全局变量。 局部变量：在函数内部定义的变量，包括参数表中定义的形式参数被称为局部变量。 在复合语句中定义的变量被称为块变量。,生存期 在复合语句中定义的变量，其生存期为所在的复合语句块中。 在函数内部和形式参数表中定义的变量都属于局部变量。作用域是定义这些变量的函数。 全局变量的生存期是定义这个变量的程序文件，作用域是从定义处开始到程序文件的结束处为止。如果程序文件中的某些局部变量与之同名，则全局变量的作用域应该去除这部分区域。,自动变量和静态变量 变量的生存期是由存储类别控制的。常见的存储类别有两种，一个是静态的；另一个是自动的。具有静态存储类别的变量在程序开始运行时系统就为之分配存储空间，等到程序结束时才将为其分配的所有存储空间回收，这种变量被简称为静态变量；具有自动存储类别的变量在函数开始执行时为之分配存储空间，函数执行完毕后，立即回收这些存储空间，这种变量被简称为自动变量。在默认情况下，局部变量都属于自动变量。,说明： 在默认情况下，函数内部定义的变量属于自动变量；当使用static存储类别说明符将其指定为静态变量时，只有首次调用这个函数时，系统为之分配空间并初始化，随后的调用不再进行初始化。当程序结束时，系统才回收存储空间。这样就可以达