计算机程序设计基础.pdf

计算机程序设计基础计算机程序设计基础计算机程序设计基础计算机程序设计基础教师：文迪教师：文迪教师：文迪教师：文迪Email: Email: wendi@wendi@清华大学电子工程系清华大学电子工程系清华大学电子工程系清华大学电子工程系清华大学电子工程系清华大学电子工程系清华大学电子工程系清华大学电子工程系智能图文信息处理实验室智能图文信息处理实验室智能图文信息处理实验室智能图文信息处理实验室第七章第七章 模块及函数设计（二）模块及函数设计（二）第七章第七章 模块及函数设计（二）模块及函数设计（二）1.1. 基于函数的模块化程序设计基于函数的模块化程序设计 2 2函数函数的递归调用的递归调用 函数的递归调用为我们带来什么样的编程灵活性？ 什么是内联函数？内联函2.2. 函数函数的递归调用的递归调用 3.3. 预处理命令预处理命令 什么是内联函数？内联函数与普通函数、宏定义的区别在哪里？ 什么是函数的重载？在什么情况下函数可以重载？ 如何规定函数的默认参数？ 如何规定函数的默认参数？基于函数的模块化程序设计基于函数的模块化程序设计基于函数的模块化程序设计基于函数的模块化程序设计• • 上节课，我们了解了程序模块的概上节课，我们了解了程序模块的概上节课，我们了解了程序模块的概上节课，我们了解了程序模块的概 念，及其在念，及其在C C语言中的实现手段语言中的实现手段———— 函数函数InOut .cppCalc .cppInOut hCalc h• • 有了函数的支持，我们就可以把软有了函数的支持，我们就可以把软 件程序设计分散为独立的件程序设计分散为独立的模块设计模块设计 在在们们.h.h• • 在在C C语言中，我们通常用不同语言中，我们通常用不同 的的. .cppcpp文件存放不同文件存放不同的的函数模块，函数模块， 然后用然后用 h h头文件存放它们的声明头文件存放它们的声明Calc .hInOut .hInOut .cppCalc .cpp然后用然后用.h.h头文件存放它们的声明，头文件存放它们的声明， 便于管理便于管理 Prog cpp.cpp main()Calc .hInOut .hInOut .cppCalc .cppProg .cpp main()基于函数的程序运行基于函数的程序运行基于函数的程序运行基于函数的程序运行• • 在运行时，程序每次都会调用在运行时，程序每次都会调用mainmain()()函数函数————所有所有在运行时，程序每次都会调用在运行时，程序每次都会调用()()函数函数所有所有 C/C++C/C++语言程序的入口，也是第一个被调用的函数语言程序的入口，也是第一个被调用的函数编译、链接编译、链接在通常情况下，在通常情况下， main()函数是函数是 C/C++程序的程序的int main (void) // 主函数 {exe可执行程序可执行程序C/C++程序的程序的 入口，从入口，从main 函数中函数中return 就就等于结束整等于结束整} // main可执行程序可执行程序就就等于结束整等于结束整 个程序。

个程序} // main} // main调入操作调入操作调入操作调入操作 系统运行系统运行函数的嵌套调用函数的嵌套调用函数的嵌套调用函数的嵌套调用• • 从从main()main()函数开始，整个函数开始，整个C/C++C/C++程序就是一部函数调程序就是一部函数调从从()()函数开始，整个函数开始，整个 / /程序就是部函数调程序就是部函数调 用的历史用的历史int main (void) // 主函数 { ...void func1(void) { ...bool func2(int n) {main()func2(n)func1();...if ( func2(a) ) { ... }...return true; ...函数调用函数调用 堆栈堆栈函数调用函数调用 堆栈堆栈func1()main()函数调用函数调用函数调用函数调用func1()main()函数调用函数调用函数调用函数调用 堆栈堆栈堆栈堆栈} ... } // func1} // func2函数调用函数调用函数调用函数调用 堆栈堆栈堆栈堆栈堆栈堆栈堆栈堆栈} // main函数调用的原理函数调用的原理函数调用的原理函数调用的原理• • C/C++C/C++语言编译器通过在函数语言编译器通过在函数调用调用和和返回返回时的固定操时的固定操 作来实现函数调用在函数调用时作来实现函数调用在函数调用时作来实现函数调用，在函数调用时：作来实现函数调用，在函数调用时： 1.1. 保存原执行函数的寄存器现场；保存原执行函数的寄存器现场； 2 2进行参数传递；进行参数传递；2.2. 进行参数传递；进行参数传递； 3.3. 指令控制转向调用函数的入口处；指令控制转向调用函数的入口处； 在函数返回时：在函数返回时：func()在函数返回时：在函数返回时： 1.1. 传递返回值；传递返回值； 2.2. 指令控制返回调用函数的下一条语句处；指令控制返回调用函数的下一条语句处；func()...函数调用函数调用函数调用函数调用3.3. 恢复原执行函数的寄存器现场。

恢复原执行函数的寄存器现场每当一个函数被调用时，编译器都会为其分配一个堆每当一个函数被调用时，编译器都会为其分配一个堆函数调用函数调用函数调用函数调用 堆栈堆栈堆栈堆栈栈空间置于栈顶，用来保存该函数所有参数、局部栈空间置于栈顶，用来保存该函数所有参数、局部 变量和寄存器现场函数堆栈随函数的嵌套调用而变量和寄存器现场函数堆栈随函数的嵌套调用而 逐层增加函数退出时则从栈顶开始逐层弹出逐层增加函数退出时则从栈顶开始逐层弹出逐层增加，函数退出时则从栈顶开始逐层弹出逐层增加，函数退出时则从栈顶开始逐层弹出函数的递归调用函数的递归调用函数的递归调用函数的递归调用• • 基于上述原理，基于上述原理，C/C++C/C++语言支持函数的递归调用语言支持函数的递归调用————即即基于上述原理，基于上述原理， / /语言支持函数的递归调用语言支持函数的递归调用即即 在某个函数的函数体中出现调用自己的语句在某个函数的函数体中出现调用自己的语句func(int a) {func(a/2) { ... func(a/2);func()...数数数数func(a)...函数调用函数调用函数调用函数调用 堆栈堆栈堆栈堆栈... }函函数数调用函调用函数数调用 堆栈堆栈调用 堆栈堆栈堆栈堆栈堆栈堆栈直接的递归调用直接的递归调用函数的递归调用函数的递归调用函数的递归调用函数的递归调用• • 另一种类似于递归调用的情况另一种类似于递归调用的情况————函数的循环调用函数的循环调用另种类似于递归调用的情况另种类似于递归调用的情况函数的循环调用函数的循环调用f1(a/2-3)f2(a/2)f1(a)f1(int a) { f1(a)...函数调用函数调用 堆栈堆栈函数调用函数调用 堆栈堆栈f2(int a) {f2(a/2)f1(a) ... f2(a/2); ... }f1(a)...函数调用函数调用函数调用函数调用 堆栈堆栈堆栈堆栈... f1(a-3); ... }...函数调用函数调用 堆栈堆栈函数调用函数调用 堆栈堆栈}堆栈堆栈堆栈堆栈}间接的递归调用间接的递归调用间接的递归调用间接的递归调用有限次数有终止的递归调用有限次数有终止的递归调用有限次数、有终止的递归调用有限次数、有终止的递归调用• • 如果没有退出机制，函数的递归调用将导致无终止的如果没有退出机制，函数的递归调用将导致无终止的如果没有退出机制，函数的递归调用将导致无终止的如果没有退出机制，函数的递归调用将导致无终止的 自身调用，最终导致函数调用堆栈溢出错误。

所以，自身调用，最终导致函数调用堆栈溢出错误所以， 必须加上条件判断，必须加上条件判断，只有满足条件才进行递归调用，只有满足条件才进行递归调用， 否则将终止否则将终止，让函数逐层退出，让函数逐层退出，才能保证，才能保证递归调用是递归调用是 有限次数、有终止的有限次数、有终止的f2()f()f()f2()f1()f2()f1()...函数调用函数调用 堆栈堆栈函数调用函数调用 堆栈堆栈f1()函数调用函数调用 堆栈堆栈函数调用函数调用 堆栈堆栈递归的基本思想及其用途递归的基本思想及其用途递归的基本思想及其用途递归的基本思想及其用途• • 人们在解决一些复杂的问题时，为了降低问题的复杂人们在解决一些复杂的问题时，为了降低问题的复杂人们在解决些复杂的问题时，为了降低问题的复杂人们在解决些复杂的问题时，为了降低问题的复杂 度，度，有时有时会采用会采用逆向思维过程逆向思维过程（又称（又称分析法分析法）：即将）：即将 问题逐层分解，最后归结为一些最简单的问题逐层分解，最后归结为一些最简单的问题，当这问题，当这 些些最简单的最简单的问题得到解决后问题得到解决后，再沿着原来分解，再沿着原来分解的路径的路径 逐步逐步回朔回朔。

这与这与通常的正向通常的正向思维思维————综合法综合法相反）相反）• • 在程序设计中，递归思想同样是一种很在程序设计中，递归思想同样是一种很有用的工具有用的工具，， 可以通过函数递归调用实现可以通过函数递归调用实现对于一些比较复杂的问对于一些比较复杂的问 题，若将算法设计成递归结构，代码量少，思路清晰，题，若将算法设计成递归结构，代码量少，思路清晰， 可读性强可读性强约瑟夫问题约瑟夫问题约瑟夫问题约瑟夫问题• • 39 39 个犹太人与约瑟夫及他的朋个犹太人与约瑟夫及他的朋个犹太人与约瑟夫及他的朋个犹太人与约瑟夫及他的朋 友躲到一个洞中，友躲到一个洞中，3939个犹太人个犹太人 决定宁死也不要被敌人抓到，决定宁死也不要被敌人抓到， 于是决定了个自杀方式于是决定了个自杀方式1 241于是决定了一个自杀方式，于是决定了一个自杀方式，4141 个人排成一个圆圈，由第个人排成一个圆圈，由第1 1个人个人 开始报数每报到第开始报数每报到第3 3人该人就人该人就2340 开始报数，每报到第开始报数，每报到第3 3人该人就人该人就 必须自杀，然后再由下一个重必须自杀，然后再由下一个重 新报数，直到所有人都自杀身新报数，直到所有人都自杀身439新报数，直到所有人都自杀身新报数，直到所有人都自杀身 亡为止。

然而约瑟夫和他的朋亡为止然而约瑟夫和他的朋 友并不想遵从，他将朋友与自友并不想遵从，他将朋友与自385 37己安排在两个位置上，最终逃己安排在两个位置上，最终逃 过了这场死亡游戏试问：这过了这场死亡游戏试问：这 两个位置是哪两个？两个位置是哪两个？37两个位置是哪两个？两个位置是哪两个？思路思路2 2思路思路2 2• • 如果只需要求解如果只需要求解最后一个幸存者最后一个幸存者原来所站的位置，那原来所站的位置，那如果只需要求解如果只需要求解最后个幸存者最后个幸存者原来所站的位置，那原来所站的位置，那 么不需要把整个游戏过程都模拟出来因为，假设我么不需要把整个游戏过程都模拟出来因为，假设我 们已经知道们已经知道4040人游戏最后一个幸存者的位置人游戏最后一个幸存者的位置J(40,3)J(40,3) 为为那么那么 在在人游戏时对应的位置人游戏时对应的位置和和 之间存在之间存在为为X X，那么，那么X X在在4141人游戏时对应的位置人游戏时对应的位置X’X’和和X X之间存在之间存在 着简单的对应关系着简单的对应关系 1 123414039401383734403941人游戏人游戏12373640人游戏人游戏5 X’?3 XX’=f(X)? X=J(40,3)X思路思路2 2思路思路2 2• • 因为因为4141人游戏的第一个出局者是人游戏的第一个出局者是3 3，，3 3号出局后从号出局后从4 4号号因为因为人游戏的第个出局者是人游戏的第个出局者是 ，， 号出局后从号出。