模块化程序设计.ppt

第5章模块化程序设计 C语言程序设计 2 解析C程序设计 第2版 第5章模块化程序设计 2020 1 3 讲授方法 解析法 解析法 是从实际问题入手 剖析求解问题的关键点 进行知识的发现 然后结合问题讲解需要的知识点 最后给出问题的求解办法和实现过程 并举一反三 各章节以问题入手 分析并讲述需要的知识点 然后再实现该问题 并通过思考题延伸知识点或引入新的问题 环环相扣 层层推进 充分体现解析法的精髓 达到通俗易懂 由浅入深的效果 举一反三 培养迁移知识的能力 3 解析C程序设计 第2版 第5章模块化程序设计 2020 1 3 本章内容 模块化程序设计思想模块分解的原则C程序的一般结构 函数的嵌套调用 函数的递归调用 4 解析C程序设计 第2版 第5章模块化程序设计 2020 1 3 复杂问题的求解 怎样来分析和完成 高校信息管理系统 呢 一个大系统 或子系统 不可能用一个主函数来完成 必须将大问题分解成小问题 再由若干人 若干函数 模块 来完成 5 解析C程序设计 第2版 第5章模块化程序设计 2020 1 3 高校信息管理系统功能分解 6 解析C程序设计 第2版 第5章模块化程序设计 2020 1 3 模块化程序设计思想 为了完成上述大型系统的开发 我们将软件开发看成是一项工程来做 其过程大致分为 系统定义 需求分析 系统设计 编写程序 系统测试 系统维护等阶段 软件工程的思想 将一个大的系统采取 分而治之 方法解决 7 解析C程序设计 第2版 第5章模块化程序设计 2020 1 3 模块化程序设计思想 开发一个软件系统时 最好的办法是从编写主程序开始 在主程序中 将问题作为一个整体考虑 然后找出完成整个任务的主要步骤 再沿着这条主线将整个问题继续分解为独立的模块 这种 自顶向下 逐步细化 的思想就是模块化程序设计的主要思想 8 解析C程序设计 第2版 第5章模块化程序设计 2020 1 3 为什么需要模块化程序设计 什么时候需要模块化 某一功能 如果重复实现2遍及其以上 即应考虑模块化 将它写成通用函数 并向小组成员发布 要尽可能利用其它人的现成模块 模块化程序设计方法就是按照 自顶向下 逐步求精 的思想 将系统功能逐步细分 使每个功能非常单一 一般不超过50行 9 解析C程序设计 第2版 第5章模块化程序设计 2020 1 3 模块化程序设计方法 功能分解自顶向下 逐步求精的过程模块分解的原则保证模块的相对独立性高聚合 低耦合模块的实现细节对外不可见外部 关心做什么内部 关心怎么做设计好模块接口接口是指罗列出一个模块的所有的与外部打交道的变量等定义好后不要轻易改动在模块开头 文件的开头 进行函数声明 10 解析C程序设计 第2版 第5章模块化程序设计 2020 1 3 模块分解的原则 模块分解的基本原则是 高聚合 低耦合及信息隐藏 高聚合是指一个模块只能完成单一的功能 不能 身兼数职 在描述功能时不能出现 和 与 等连词 低耦合是指模块之间参数传递尽量少 还不能通过全局变量来实现数据传递 信息隐藏是指把不需要调用者知道的信息都包装在模块内部隐藏起来 只有实现了高聚合 低耦合 才可能最大程度的实现信息隐藏 从而实现真正意义上的模块化程序设计 11 解析C程序设计 第2版 第5章模块化程序设计 2020 1 3 模块化程序设计的优点 每个模块都可以分配给不同的程序员完成 从而缩短开发周期 各个模块高聚合 模块之间低耦合 只要模块之间确定了参数传递的接口 不管哪个模块内部的改动 均不会影响其它模块 从而使软件产品的生产更加灵活 系统细化到模块 条理清楚 系统更加容易理解和实现 容易维护 系统可靠 模块化程序设计的特点是 各模块相对独立 功能单一 结构清晰 接口简单 避免程序开发的重复劳动 易于维护和功能扩充 程序设计的复杂性得到了有效控制等 12 解析C程序设计 第2版 第5章模块化程序设计 2020 1 3 C程序的一般结构 C语言是模块化程序设计语言 每个模块都是由函数完成的 C语言是函数式的语言 函数就是模块 使用顺序结构 分支结构 循环结构三种基本结构设计的程序必然就是结构化程序 13 解析C程序设计 第2版 第5章模块化程序设计 2020 1 3 函数设计的原则 函数的功能要单一 不要设计多用途的函数函数的规模要小 尽量控制在50行代码以内1986年IBM在OS 360的研究结果 大多数有错误的函数都大于500行1991年对148 000行代码的研究表明 小于143行的函数比更长的函数更容易维护参数和返回值的规则参数要书写完整 不要省略对函数的入口参数进行有效性检查没有参数和返回值时 用void填充每个函数只有一个入口和一个出口 尽量不使用全局变量尽量少用静态局部变量 以避免函数具有 记忆 功能 14 解析C程序设计 第2版 第5章模块化程序设计 2020 1 3 C语言中的函数与模块 在C语言中 每个模块都是由函数完成的 一个小模块就是一个函数 在程序设计中 常将一些常用的功能模块编写成函数 放在函数库中供公共选用 程序员要善于利用库函数 以减少重复编写程序段的工作量 在编写某个函数时 遇到具有相对独立的功能的程序段 都应独立成另一个函数 而在一个函数中调用另一个函数 当某一个函数拥有较多的代码时 一般函数代码50行左右 也应将函数中相对独立的代码分成另一个函数 C语言就是模块化程序设计语言 15 解析C程序设计 第2版 第5章模块化程序设计 2020 1 3 简化的模块化问题 实现前面 高校信息管理系统 需要用到模块化程序设计 函数的定义 声明 调用 嵌套调用 返回等 还需要用到数组 指针 结构体 文件等知识 这些知识将在后续章节逐一介绍 这里另外提出一个稍微简单一点的问题 以便在本节中实现 16 解析C程序设计 第2版 第5章模块化程序设计 2020 1 3 提出问题 例5 1 求一元二次方程ax2 bx c的根 并考虑判别式的各种情况 17 解析C程序设计 第2版 第5章模块化程序设计 2020 1 3 主函数可以调用其他函数 反之 不然 自定义函数之间能否调用呢 能 函数不能嵌套定义 但是函数能嵌套调用 即函数调用函数 前者称为调用函数 后者称为被调函数 在主函数main 中输入a b c 并调用求根函数root 在求根函数中再计算判别式disc 并判断3种情况 根据每种情况调用不同的根计算函数root1 root2 root3 分析问题 18 解析C程序设计 第2版 第5章模块化程序设计 2020 1 3 实现代码 LI5 1 C include include 自定义函数的声明 voidroot inta intb intc floatroot1 inta intb intc voidroot2 inta intb intc voidroot3 inta intb intc 主函数 intmain inta b c printf Inputa b c scanf d d d 19 解析C程序设计 第2版 第5章模块化程序设计 2020 1 3 求方程根函数 voidroot inta intb intc floatdisc r disc b b 4 a c 求判别式的值 if disc 0 r root1 a b c 调用求两个相等实根函数 printf x1 7 2f tx2 7 2f n r r elseif disc 0 root2 a b c 调用求两个不相等实根函数 elseroot3 a b c 调用求两个虚根函数 求方程两个相等实根函数 floatroot1 inta intb intc floatr r b 2 0 a 计算相等的实根 return r 20 解析C程序设计 第2版 第5章模块化程序设计 2020 1 3 求方程两个不相等实根函数 voidroot2 inta intb intc floatdisc x1 x2 disc b b 4 a c x1 b sqrt disc 2 0 a 计算实根x1 x2 b sqrt disc 2 0 a 计算实根x2 printf x1 7 2f tx2 7 2f n x1 x2 求方程两个虚根函数 voidroot3 inta intb intc floatdisc p q disc b b 4 a c p b 2 0 a 计算虚根实部p q sqrt disc 2 0 a 计算虚根虚部q printf x1 7 2f 7 2fi tx2 7 2f 7 2fi n p q p q 21 解析C程序设计 第2版 第5章模块化程序设计 2020 1 3 函数调用 22 解析C程序设计 第2版 第5章模块化程序设计 2020 1 3 函数的嵌套调用 23 解析C程序设计 第2版 第5章模块化程序设计 2020 1 3 课堂练习 用函数的嵌套调用方法计算 24 解析C程序设计 第2版 第5章模块化程序设计 2020 1 3 举一反三 LI5 2 c includeintdif intx inty intz intmax intx inty intz intmin intx inty intz voidmain inta b c d printf InputData scanf d d d 定义dif函数求三数的差值 intdif intx inty intz intm1 m2 m1 max x y z m2 min x y z returnm1 m2 定义max函数求三数的最大值 intmax intx inty intz intr1 r2 r1 x y x y r2 r1 z r1 z return r2 定义min函数求三数的最小值 intmin intx inty intz intr r x y x y return r z r z 25 解析C程序设计 第2版 第5章模块化程序设计 2020 1 3 举一反三 例5 3用弦截法求方程的根 分析 弦截法求方程的根的方法如下 取两个不同点x1 x2 如果f x1 与f x2 符号相反 则 x1 x2 区间内必有一个根 否则改变x1 x2的值使得f x1 与f x2 异号为止 注意 x1与x2的值不能相差太大 确保之间只有一个根 连接f x1 与f x2 两点 此线 即弦 交x轴于x点 计算见图 再求出f x 若f x 与f x1 同号 则将x作为新的x1 若f x 与f x2 同号 则将x作为新的x2 重复第 与第 步 直到 f x 其中 是一个很小的正数 如0 0001 此时可以认为 f x 0 26 解析C程序设计 第2版 第5章模块化程序设计 2020 1 3 弦截法N S图及程序 include includefloatf floatx floatxpoint floatx1 floatx2 floatroot floatx1 floatx2 voidmain floatx1 x2 f1 f2 x 输入x1和x2并保证其函数值反号 do printf Inputx1 x2 n scanf f f 27 解析C程序设计 第2版 第5章模块化程序设计 2020 1 3 弦截法求根程序 定义f函数 求f x 的值 floatf floatx floaty 计算f x 的值 y x 5 0 x 16 0 x 80 0 return y 定义xpoint函数 求弦与x轴的交点 floatxpoint floatx1 floatx2 floatx x x1 f x2 x2 f x1 f x2 f x1 return x 定义root函数 求近似根 floatroot floatx1 floatx2 floatx y y1 y1 f x1 do x xpoint x1 x2 y f x 新的f x 与f x1 同号时 用x替换x1 否则替换x2 if y y1 0 y1 y x1 x elsex2 x while fabs y 0 0001 当f x 约等于0时退出循环 return x 28 解析C程序设计 第2版 第5章模块化程序设计 2020 1 3 函数调用关系 29 解析C程序设计 第2版 第5章模块化程序设计 2020 1 3 例5 4 求 的值 分析 从表达式中可以看出 每项都是一样的 不同的是起止数不同 因此每项的计算可以由一个相同的函数来完成 而每项中还有一个阶乘 因此还需要一个求阶乘的函数 30 解析C程序设计 第2版 第5章模块化程序设计 2020 1 3 例5 4程序 include 求n的阶乘函数 doublefac intn doubles n if n 1 return1 小于1的数的阶乘都返回1 for n 先将n值减1 再判断n值是否为非0 真 s n 计算阶乘s s n 计算的是 s n n 1 2 1 returns 返回n 值 求项的值 n1和n2为起止数 doublesum intn1 intn2 inti doubles 0 for i n1 i n2 i s s 1 fac i returns voidmain doubles s sum 1 3 sum 6 9 sum 12 15 printf ns f s getch 暂停 按任意键继续 31 解析C程序设计 第2版 第5章模块化程序设计 2020 1 3 例5 4函数调用关系 32 解析C程序设计 第2版 第5章模块化程序设计 2020 1 3 思考题 求n 可以使用1 2 3 n形式 进一步思考 n 可以写成 n 1 n 其中用到了 n 1 的值 那么 能不能在求n 时调用自身函数求 n 1 只是改变参数值 以此类推 答 可以使用递归方式完成 33 解析C程序设计 第2版 第5章模块化程序设计 2020 1 3 例5 5用递归方法求n 分析 求n 除了可以使用例5 5递推方法外 即 1 2 3 n 还可以使用递归方法 递推是用一个值推出另一个值 递归是通过函数的自身调用来推导结果 如计算5 可以用5 5 4 4 4 3 3 3 2 2 2 1 1 1 其递归公式如下 34 解析C程序设计 第2版 第5章模块化程序设计 2020 1 3 递归算法的执行过程分回推和递推两个阶段 在回推阶段 把较复杂的问题 规模为n 的求解推到比原问题简单一些的问题 规模小于n 的求解 在递推阶段 当获得最简单情况的解后 逐级返回 依次得到稍复杂问题的解 计算5 其递归过程中的 回推 和 递推 如图5 9所示 35 解析C程序设计 第2版 第5章模块化程序设计 2020 1 3 回推 和 递推 36 解析C程序设计 第2版 第5章模块化程序设计 2020 1 3 求解过程 对使用递归方法计算4 的结果如下 调用递归调用返回第1步fac 4 fa 4 fac 4 1 4 fac 3 fa 4 3 2 1第2步fac 3 fa 3 fac 3 1 3 fac 2 fa 3 2 1第3步fac 2 fa 2 fac 2 1 2 fac 1 fa 2 1第4步fac 1 fa fac 1 1 回推 递推 回推过程 计算fac 4 时要知道fac 3 计算fac 3 时要知道fac 2 计算fac 2 时要知道fac 1 而fac 1 为1 递推过程 知道fac 1 后可算fac 2 从而可算fac 3 最后计算fac 4 37 解析C程序设计 第2版 第5章模块化程序设计 2020 1 3 例5 5程序 LI5 5 c includelongfac intn voidmain intn longr 定义长整型变量存放n的阶乘的值 printf Inputn scanf d 返回fac的函数值 38 解析C程序设计 第2版 第5章模块化程序设计 2020 1 3 函数的递归调用 在函数调用中 如果直接或间接地调用该函数本身 称为递归调用 递归有时也称为循环定义 递归又分为 直接递归调用 即函数直接调用自身 和间接调用 即函数互相调用对方 intf intx inty z z f y return 2 z 39 解析C程序设计 第2版 第5章模块化程序设计 2020 1 3 递归调用的说明 上述两种递归调用都是无终止的自身调用 程序中不应出现无终止调用 而只应出现有限次数的有终止的递归调用 可以使用if语句来控制 在递归程序中 由递归方式与递归终止条件两部分组成 即一个递归的问题可以分为 首先 回推 然后 递推 在递归过程中 必须具有一个结束递归过程的条件 40 解析C程序设计 第2版 第5章模块化程序设计 2020 1 3 递归调用的说明 C编译系统对递归函数的自调用次数没有限制 每调用函数一次 在内存堆栈区分配空间 用于存放函数变量 返回值等信息 所以递归次数过多 可能引起堆栈溢出 41 解析C程序设计 第2版 第5章模块化程序设计 2020 1 3 由于递归引起一系列的函数调用 并且可能会有一系列的重复计算 递归算法的执行效率相对较低 当某个递归算法能较方便地转换成递推算法时 通常按递推算法编写程序 42 解析C程序设计 第2版 第5章模块化程序设计 2020 1 3 递归形式 当有函数返回值时 通用的递归函数体表述如下 if 递归结束条件 return 递归公式的初值 elsereturn 递归函数调用返回的结果值 有时递归函数并不返回任何值 只是输出显示结果 有时递归子问题和原问题的形式并不完全相同 这时必须把问题作一个小的变化 使得递归子问题与原问题完全相同 43 解析C程序设计 第2版 第5章模块化程序设计 2020 1 3 例5 6 用递归方法求解斐波那契 Fibonacci 数列斐波那契数列 0 1 1 2 3 5 8 13 21 34 第n项的递归公式为 分析 由公式可以看出 第n项斐波那契数列值是前2项的和 这就是递归方式 而当n 0和1时 斐波那契数列就是n值本身 这就是递归结束条件 44 解析C程序设计 第2版 第5章模块化程序设计 2020 1 3 例5 6程序 LI5 6 c includevoidmain longfib intn 自定义函数声明 longs 第i项斐波那契数列的值 inti 0 斐波那契数列某项的序号 do s fib i 求斐波那契数列第i项 printf Fib d ld n i s 显示斐波那契数列第i项的值 printf InputFibonacciNumber scanf d 求斐波那契数列的递归方式 45 解析C程序设计 第2版 第5章模块化程序设计 2020 1 3 例5 6程序说明 本例中自定义函数的声明longfib intn 放在main函数中 因此 fib函数只能在main函数中使用 在其他函数中使用时还需要再次声明 Fibonacci数列递归调用的次数随项数的增多而呈指数级数的增长 每次递归调用fib函数时 都要调用该函数两次 即计算n个Fibonacci数列的值 递归调用的次数为2n 计算第20项的Fibonacci数需要递归调用的次数为220 大约100万次 计算第4项则只需要16次 这种现象称为指数复杂度 虽然程序的算法简单 但计算的复杂度会随着n的增加而呈指数级增长 46 解析C程序设计 第2版 第5章模块化程序设计 2020 1 3 Hanoi 汉诺 塔问题 例5 4编程求解Hanoi 汉诺 塔问题 古代有一个梵塔 塔内有三个柱子A B C 僧侣们想把A拄子上的一摞盘子移动到C柱子上 最初A拄子上有大小不等的64个盘子 且小的在上 大的在下 在移动过程中 大盘子只能在下 小盘子只能在上 并且每次只能移动一个盘子 可以借助于B柱子 47 解析C程序设计 第2版 第5章模块化程序设计 2020 1 3 问题的分析 Hanoi 汉诺 塔问题是一个古典的数学问题 任何一个人都不可能使用传统的方法直接写出移动盘子的每一个具体步骤 僧侣们也无法解决这个问题 解决Hanoi 汉诺 塔问题的方法可以表述如下 老和尚移动64个盘子的步骤第1步 请第2个和尚将前63个盘子从A柱子移到B柱子 第2步 自己将最下面的第64个盘子从A柱子移到C柱子 第3步 再请第2个和尚将63个盘子从B柱子移到C柱子 第2个和尚移动63个盘子的步骤第1步 请第3个和尚将前62个盘子从A柱子移到C柱子 第2步 自己将最下面的第63个盘子从A柱子移到B柱子 第3步 再请第3个和尚将62个盘子从C柱子移到B柱子 依此类推 直到第63个和尚完成了2个盘子的移动 最后由第64个和尚完成1个盘子的移动 这个过程称之为 回推 过程 48 解析C程序设计 第2版 第5章模块化程序设计 2020 1 3 问题的分析 当第64个和尚完成1个盘子的移动后 第63个和尚就可以完成2个盘子的移动 最后第1个和尚完成64个盘子的移动 这个过程称之为 递推 过程 回推 和 递推 两个过程构成了 递归 问题的两个阶段 如果要求递归过程在有限步骤内 就必须有一个结束递归过程的条件 Hanoi 汉诺 塔问题就是第64个和尚可以一次性的完成盘子的移动 Hanoi 汉诺 塔问题只有采用递归方法才能非常容易的 有效的得到解决 49 解析C程序设计 第2版 第5章模块化程序设计 2020 1 3 例5 4汉诺塔问题的实现 用A B C分别表示Hanoi 汉诺 塔中的三个柱子 1 n表示n个盘子 最上面的编号为1 最下面的编号为n 首先设计一个函数move完成将第k个盘子从A柱子移动到C柱子 即模拟和尚自己移动一个盘子 move intno charfrom charto 整型变量no表示盘子的编号 字符型变量from表示源柱子 字符型变量to表示目的柱子 再设计一个函数hanoi完成将n个盘子从A柱子移动到C柱子 即和尚请另外一个和尚移动盘子的过程 hanoi intn charA charB charC 表示借助B柱子将n个盘子从A柱子移动到C柱子 将n个盘子借助B柱子从A柱子移动到C柱子 可以使用三个步骤实现 步骤1 hanoi n 1 A C B 借助C柱子将n 1个盘子从A移到B 步骤2 move n A C 将第n个盘子从A柱子移动到C柱子 步骤3 hanoi n 1 B A C 借助A柱子将n 1个盘子从B移到C 50 解析C程序设计 第2版 第5章模块化程序设计 2020 1 3 例5 4程序 LI5 4 c include 包含头文件 voidmove intno charfrom charto 自定义函数的声明 voidhanoi intn charA charB charC 自定义函数的声明 voidmain 主函数 无参数 无返回值 intn 定义整型变量n 存放盘子总数 printf Inputthenumberofdiskes 提示输入n的值 scanf d 定义函数 借助B柱子将n个盘子从A柱子移动到C柱子intn 表示n个盘子charA 表示A柱子charB 表示B柱子charC 表示C柱子 voidhanoi intn charA charB charC if n 1 move n A C else hanoi n 1 A C B move n A C hanoi n 1 B A C 51 解析C程序设计 第2版 第5章模块化程序设计 2020 1 3 例5 4程序说明 本程序递归函数没有返回值 只是完成了三个步骤 并将结果输出显示在屏幕上 在本程序中 递归结束条件是当n 1时所执行的移动1个盘子的函数 递归方式是先将n 1个盘子移动到B柱子 再将第n个盘子移动到C柱子 最后将n 1个盘子移动到C柱子 本程序没有明确的递归公式 也没有初值和递归函数的返回值 本程序中move函数并未真正移动盘子 只是打印出移动盘子的方案 52 解析C程序设计 第2版 第5章模块化程序设计 2020 1 3 举一反三 例5 7用递归法编写一函数将一个整数n转换成若干字符显示在屏幕上 例如整数 258转换成4个字符 258 显示 分析 如果整数为正数 如258 显示时不需要符号 而为负数时 则需要负号 每位数字转换成字符时 只需要将数字加上字符 0 即可 而将数字字符转换成数字时 只需要将数字字符减去字符 0 即可 如 字符9要变成数字9 只需要作 9 0 运算 即 9 9 0 数字9要变成字符9 只需要作 0 9运算 即 9 0 9 n 10是将n缩小10倍 为求n的十位数作准备 n 10是求n的个位数 如此循环 递归 可以将n的每位数字求出 53 解析C程序设计 第2版 第5章模块化程序设计 2020 1 3 例5 7程序 LI5 7 c includevoidconvert intn voidmain intnumber printf Inputnumber scanf d 显示各位数字 54 解析C程序设计 第2版 第5章模块化程序设计 2020 1 3 思考题 例5 7在主函数main中定义了变量number表示输入的数 而在递归函数convert中定义变量i表示下次递归的新数 这里能不能在convert函数中再次定义number变量呢 而在递归函数convert中使用convert i 语句实现了递归调用 那么每次调用时都是使用的是变量i 它与上次的i值是否有冲突呢 答 这个问题在第3章中已经讲述 它属于变量的作用域问题 55 解析C程序设计 第2版 第5章模块化程序设计 2020 1 3 应用实例 例5 8 求两个数的最大公约数和最小公倍数 分析 最大公约数 或称最大公因子 是能够同时被两个数整除的最大数 其性质为 如果a b 则a和b的最大公约数与a b和b的最大公约数相同 如果b a 则a和b的最大公约数与a和b a的最大公约数相同 如果a b 则a和b的最大公约数与a值和b值相同 换句话说 最大公约数是最后能使余数为0的被除数 最小公倍数为 两数相乘 再除以最大公约数 56 解析C程序设计 第2版 第5章模块化程序设计 2020 1 3 解法一 穷举法 LI5 8 1 c include includeinthcf intu intv intlcd intu intv inth voidmain intn1 n2 h l clrscr 清屏 scanf d d 57 解析C程序设计 第2版 第5章模块化程序设计 2020 1 3 解法二 辗转相除法 58 解析C程序设计 第2版 第5章模块化程序设计 2020 1 3 解法二 辗转相除法 LI5 8 2 c include includeinthcf intu intv intlcd intu intv inth voidmain intn1 n2 h l clr