l8_深入理解函数、二维数组

1、计算机程序设计基础第8讲深入理解函数/二维数组陈来军 清 华 大 学 电 机 系 2015.11.11主要内容CONTENTS计算机程序设计基础21. 函数的相关问题2. 数组3. 增量式开发4. 函数的递归调用C程序设计（第四版）第6、7章C语言程序设计: 现代方法(第2版)第8、9章前7讲回顾程序构成 main函数、头文件、return 语句数据类型 int、float、char表达式 算术、赋值、逗号表达式、scanf、printf 程序结构 顺序结构、选择结构、循环结构一维数组、函数 深入学习：函数、二维数组

2、计算机程序设计基础31 关于函数使用的两个问题 问题1：函数只有一个返回值 floatf_result = my_sin(0.1); 若需要返回多个值，如何处理？ 解决方案之一：改用全局变量 弊端：模块化效果不好计算机程序设计基础41 关于函数使用的两个问题 问题2：关于全局变量和局部变量 变量尽可能不要重名。否则，可读性差 如果重名，注意“屏蔽”原则！计算机程序设计基础51 关于函数使用的两个问题 推荐的编程习惯计算机程序设计基础61 关于函数使用的两个问题 不好的缩进习惯结构混乱可读性差计算机程序设计基础72 二维数组1. 复习一维数组#define N 10int aN= 0,1,2,3

3、,4, ;for( int i=0; i=N; i+)ai *= 2;int b10;b = a;左侧代码正确吗?/错误的代码1.2.i=N 越界b=a 赋值错误计算机程序设计基础82 二维数组使用数组时最严重、常见的错误“下标越界”计算机程序设计基础91. 二维数组2. 复习字符数组右侧代码运行结果是什么？计算机程序设计基础102 二维数组3.数组 数组可以有任意维数。下图为一二维数组，数学上称为“矩阵”计算机程序设计基础112 二维数组3.1数组定义 数据类型变量名维度1维度2；int m59;计算机程序设计基础122 二维数组第0行0001020304050607081011123.2数

4、组的存储 int m59第1行先存第0行，再存第1行，计算机程序设计基础132 二维数组问题 int m159,m25*9 需要的存储空间一样多吗？计算机程序设计基础142 二维数组012345678910000102030405060708101112m0第0行int m59;int m5*9;m9第1行11顺序存储先行后列，顺序存储计算机程序设计基础152 二维数组例1：数组的定义NOTICE!不要把mi j写成mi,j,否则C语言会把逗号看成逗号运算符，因此，mi,j 等同于m j.计算机程序设计基础162 二维数组3.2数组的初始化 嵌套初始化的方式 完全初始化 int a33 = 1

5、,2,3,2,3,1,1,3,2; 部分行初始化，不完全初始化 int b33 = 1,2,3,2,3,1,; 部分列初始化，不完全初始化 int c33 = 1,2,3,2,1,3,2; 无嵌套完全（不完全）初始化 int d33 = 1,2,3,2,3,1,1,3,2； int e33 = 1,2,3,2,3,1,；/后续元素初始化为0计算机程序设计基础172 二维数组例2：数组的初始化方法不推荐！可读性差。NOTICE!在定义数组的同时进行初始化计算机程序设计基础182 二维数组3.3数组的使用例3：矩阵元素赋值 数组元素引用 数组名下标1下标2 注意：数组下标从0开始程序实现了什么功能

6、？运行结果：计算机程序设计基础192 二维数组例4：矩阵相乘 求两个33矩阵的乘积nci, j = Ai, k* Bk, jk =1计算机程序设计基础202 二维数组计算机程序设计基础212 二维数组3.3 二维字符数组字符串数组 当构成数组的数据是字符串时，这个数组就称为字符串数组。 字符串数组实际上是字符型的二维数组，字符串数组的利用率比较高。 一维字符数组可以存放一个字符串，二维字符数组可以存放若干个字符串。二维字符数组的定义类似于二维数值数组，例如，charstr110;char str21080; 二维字符数组的初始化与二维数值数组不同。计算机程序设计基础222 二维数组3.3.1

7、二维字符数组的初始化 用字符常量为每一个字符数组元素赋初值，例如，char a36=S,u,n,E,a,r,t,h,M,o,o,n; 初始化后的结果为：a00= S，a01= u，a02= na10= E，a11= a，a12= r，a13= t， a14=ha20=M，a21=o，a22= o，a23= n。 其余没赋初始值的数组元素均为0。计算机程序设计基础232 二维数组3.3.1 二维字符数组的初始化(续) 二维数组初始化时，可以使用下列形式直接赋予它多个字符串，例如，char a36=“Sun”, ”Earth”, ”Moon”; 这里char型二维数组a可以分解成3个一维数组a0、

8、a1和a2，它们各自有6个元素。3个一维数组分别由3个字符串予以初始化。 可以把ai当作一个字符串来处理。类似以前在一维数组中讲过的一维字符数组的字符串。计算机程序设计基础242 二维数组3.3.1 二维字符数组的初始化(续) 二维数组初始化时，可以使用下列形式直接赋予它多个字符串，例如，char a36=“Sun”, ”Earth”, ”Moon”;a00a0 ：a1 ：a2 ：NOTICE！0存储造成资源浪费!计算机程序设计基础25Sun0000Earth00Moon0002 二维数组3.3.2 二维字符数组的引用 用i引用i行的字符串,或用i j引用i行j列的字符 例：for(i=0;i

9、3;i+)printf(“%sn”,ai);for(i=0;i3;i+)/*输出i行字符串*/printf(“%cn”,aii); /*输出i行i列字符*/ for(i=0;i 0n!= 1n(n -1)!递归方程边界条件与递归方程是递归函数的二个要素，递归函数只有具备了这两个要素，才能在有限次计算后得出结果。计算机程序设计基础474* 函数递归调用第1类 数据本身，按递归进行定义n = 0n 0n!= 1n(n -1)!递归调用：自调用在函数的定义中直接或间接调用函数自身。计算机程序设计基础484* 函数递归调用阶 乘 函 数递归调用过程计算机程序设计基础494* 函数递归调用第1类 数据本

10、身，按递归进行定义阶乘函数的递归调用树5!Recursion tree4!3!2!1!0!计算机程序设计基础504* 函数递归调用第1类 数据本身，按递归进行定义 例2：Fibonacci数列 无穷数列1，1，2，3，5，8，13，21，34，55， 称为Fibonacci数列。它可以递归地定义为：边界条件n = 0n = 1n 11F (n) = 1F (n - 1) + F (n - 2)递归方程计算机程序设计基础514* 函数递归调用第1类 数据本身，按递归进行定义n = 0n = 1n 11F (n) = 1F (n -1) + F (n - 2)递归调用：自调用在函数的定义中直接或间

11、接调用函数自身。计算机程序设计基础524* 函数递归调用Fib(5) Fib(4) Fib(3) Fib(3) Fib(2) Fib(2)Fib(1) Fib(2)Fib(1) Fib(1) Fib(0) Fib(1)Fib(0) 斐波那契数列的递归调用树Recursion tree Fib(1) Fib(0) 调用次数NumofCall(k) = 2*Fib(k+1) - 1。O(2n )计算机程序设计基础534* 函数递归调用第1类 数据本身，按递归进行定义 例3（练习）：Ackerman函数 当一个函数及它的一个变量是由函数自身定义时，称这个函数是双递归函数。 Ackerman函数A(n

12、，m)定义如下：A(1,0) = 2A(0, m) =1A(n,0) = n + 2边界条件m 0n 2n,m 1A(n, m) = A( A(n - 1, m), m - 1)递归方程计算机程序设计基础544* 函数递归调用第2类 问题解法，按递归定义 我们有时会碰到一些题目，它们既不能通过建立数学模型解决，又没有现成算法可以套用， 或者必须遍历所有状况才可以得出正确结果。这时，我们就必须采用搜索算法来解决问题。 搜索算法按搜索的方式分有两类，一类是深度优先搜索，一类是广度优先搜索。 对于搜索来说，我们需要使用到的一个技术就是递归与回溯。计算机程序设计基础554* 函数递归调用第2类 问题解

13、法，按递归定义 问题：在数字7629中插入2个加号，找到和最小的划分7和6之间不添加加号7和6之间添加一个加号77+6767+6+27+6276+2762762+97+6+2+97+6+297+62+97+62976+2+976+297629NumofCall(n) =1+2+4+8,O(2n )调用次数计算机程序设计基础564* 函数递归调用第2类 问题解法，按递归定义 汉诺塔问题汉诺塔（又称河内塔）问题是源于一个古老的益智玩具。大梵天创造世界的时候做了三根石柱子，在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小

14、圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。计算机程序设计基础574* 函数递归调用第2类 问题解法，按递归定义 用递归思想解决汉诺塔问题是很方便的： 1. 先将n-1个盘子从a柱移动到b柱 2. 然后把最大的盘子从a柱移动到c柱 3. 再把n-1个盘子从b柱移动到c柱。 第1、3步均是n-1阶的汉诺塔问题。 第2步是递归的终止条件，是一个能直接求解的最小子问题。把1、3步进一步分解下去，最后n阶汉诺塔问题可以被分解成若干个只需要移动一个盘子的能直接求解的子问题，使得整个问题得到解决。计算机程序设计基础584* 函数递归调用void Hanoi(int n, char a, cha

15、r b, char c)if(n=1) /只有一个盘子，直接移动printf(move %c to %cn, a, c);elseHanoi(n-1, a, c, b); /n-1个盘子a柱-b柱printf(move %c to %cn, a, c); /最后一个盘子a柱-c柱Hanoi(n-1, b, a, c); /将n-1个盘子从b柱移动到c柱int main()int n; /盘子个数char a=1, b=2, c=3; /柱名printf(Enter the number of disks:); scanf(%d, &n);Hanoi(n, a, b, c); return 0;计算机程序设计基础594* 函数递归调用NOTICE！ 不能递归思想！以斐波那契数列为例，在计算F(n)时，需要计算F(n-1)和F(n-2)，而在计算F(n-1)时，也同时计算了F(n-2)。相比使用循环和数组，增加了额外的计算量！（指数增长）n = 0n = 1n 11F (n) = 1F (n -1) + F (n - 2)计