计算机软件开发(第8、9讲).ppt

20 49 1 第4章计算机软件系统 回顾 4 1软件概述4 2操作系统概述4 3操作系统的功能4 4常见操作系统4 5应用软件 20 49 2 第5章计算机软件开发 第8 9讲 讲授 黄瑞兴 20 49 3 第5章计算机软件开发 5 1算法与数据结构5 2程序设计的基本概念5 3结构化程序设计5 4面向对象程序设计5 5软件工程5 6数据库系统概述 20 49 4 5 1算法与数据结构 算法与数据结构是计算机程序的两个最基本的概念 瑞士著名计算机科学家尼可莱沃思在1976年曾提出算法与数据结构二者的关系 算法 数据结构 程序准确地说 一个程序规定了某个数据结构上的一个算法 失算 起床 穿衣 冲凉 吃饭 上课 20 49 5 5 1 1算法的基本概念 算法 algorithms 是什么 韦氏新世界词典将 算法 定义为 解决某种问题的任何专门的方法 如公元前300年欧几里得在其著作 几何原本 中关于求两个数的最大公约数的辗转相除法就是著名的欧几里德算法 20 49 6 欧几里德算法 给定两个正整数m和n求它们的最大公因子 即能同时整除m和n的最大正整数 步骤 以n除m并令所得余数为r r必小于n 若r 0算法结束 输出结果n 否则继续步骤3 将n置换为m r置换为n并返回步骤1 欧几里德算法既表述了一个数的求解过程 同时又表述了一个判定过程 20 49 7 汉诺塔问题 每次只能移动一个盘子只能在三根柱子上移动 不能放在其他地方移动时必须始终保持大盘在下 小盘在上当这64个盘子全部移到第三根柱子上 世界末日就要到了 汉诺塔问题只能用递归方法而不能用其他方法来求解 所谓递归就是将一个较大的问题归结为一个或多个比原问题简单 且在结构上与原问题相同的子问题的求解方法 20 49 8 5 1 1算法的基本概念 著名计算机科学家克努特把算法的性质归纳为有穷性 算法必须在执行有限步之后结束 即必须在有限时间内完成 确定性 算法中的每个步骤都必须有明确的定义 不允许存在多义性和模棱两可 能行性 算法中描述的每步操作都应是可执行的 例如 当B 0时A B就无法执行 不符合能行性的要求 输入 一个算法必须有0个 自动生成初始数据 或多个输入 输出 一个算法必须产生一个或多个输出 20 49 9 自然语言是人们日常所用的语言 如英语 汉语等优点 自然语言所描述的算法通俗易懂 灵活自由 缺点 歧义性 容易导致算法执行的不确定性 串行性 一个算法中循环和分支较多时就很难清晰地表示出来 不便转换成用计算机程序设计语言表示 5 1 2算法的表示 自然语言 20 49 10 流程图是采用一些的图框符号来描述算法的逻辑结构 每个图框符号表示不同性质的操作 ANSI在上世纪60年代颁布流程图的标准 规定用来表示程序中各种操作的流程图符号 5 1 2算法的表示 流程图 起止框 输入 输出框 判断框 处理框 20 49 11 5 1 2算法的表示 例3 2求5 步骤1 令p 1步骤2 令i 2步骤3 使pXi 成绩依然存入p中 可表示为p pxi步骤4 使i的值加1 可表示为i i 1步骤5 如果i 5 则返回步骤3的位置 从步骤3开始再次执行本算法 如果i 5 则算法结束 流程图 开始 i 5 p 1 i 2 p pxi i i 1 结束 F T 20 49 12 伪代码是一种非正式的语言 它是用介于自然语言和计算机语言之间的文字和符号来描述算法比真正的程序代码更简明 更贴近自然语言书写方便 格式紧凑 易于理解 便于转化为计算机语言算法 即程序 5 1 2算法的表示 伪代码 20 49 13 5 1 2算法的表示 用伪代码表示例3 2求5 的算法Begin置p的初值为1置i的初值为2whilei 5p pxii i 1endwhile打印p的值End 20 49 14 5 1 3数据结构的基本概念 数据 是描述客观事物的数字 字符及所有能输入到计算机中并被计算机程序处理的符号的集合 数据元素 组成数据的基本单位称为数据元素 通常将数据元素作为一个整体进行处理 数据元素由若干个数据项组成 称数据元素为记录 数据项是数据的不可分割的最小单位 最简单的数据元素仅含有一个数据项 20 49 15 5 1 3数据结构的基本概念 数据结构 是指数据之间的相互关系 即数据的组织形式 数据结构的研究内容 程序设计中计算机所操作的对象及相互间的关系和运算 即数据的逻辑结构 存储结构以及数据结构的运算 数据的逻辑结构是指数据元素之间的逻辑关系 逻辑结构有 线性结构 树形结构和图状结构 或称网状结构 20 49 16 5 1 3数据结构的基本概念 数据的存储结构是指数据在存储器中的存储方式 顺序存储结构借助元素在存储器中的相对位置来表示数据元素的逻辑关系链式存储结构借助指针来表示数据元素之间的逻辑关系 通常在数据元素上增加一个或多个指针类型的属性来实现这种表示方式 20 49 17 数据结构的基本运算 操作 建立数据结构 撤消数据结构 插入数据元素 在一个给定的数据结构中 在指定位置上增添一个新的元素 删除数据元素 对一个给定的数据结构 删除某个指定节点 更新数据元素 在一个给定的数据结构中 改变某个元素的值 它等于插入和删除两个操作的组合 20 49 18 数据结构的基本运算 操作 查找数据元素 在一个给定的数据结构中 找出满足指定条件的元素 排序 对给定的数据结构中的所有的元素按照一定的条件将它们重新排列顺序 遍历 在一个给定的数据结构中 从第一个结点开始 依次访问各个结点 每个结点只能被访问一次 判定某个数据结构是否为空或是否已达到最大允许的容量 统计数据元素的个数 20 49 19 5 1 3数据结构的基本概念 学习数据结构的目的 可简化算法 节省空间 提高效率 程序设计中选择适当的数据结构 20 49 20 5 1 4线性表 定义 线性表的逻辑结构是n个数据元素的有限序列 a1 a2 a3 an 逻辑结构特征 数据元素之间呈线性关系第1个 无前驱 有1个后继 最后一个 有1个前驱 无后继 其它 有1个前驱 有1个后继 存储结构 一类是顺序 静态存储结构 另一类是链式 动态存储结构 除书上所列举的26个英文字母 0 9数字字符组成线性表 还能举出其他的线性表吗 20 49 21 5 1 4线性表 顺序存储结构线性表的插入 删除过程 15 18 22 25 26 29 11 12 20 49 22 5 1 4线性表 顺序存储结构线性表的插入 删除过程 15 18 22 25 26 29 11 12 20 20 49 23 5 1 4线性表 顺序存储结构线性表的插入 删除过程 11 20 49 24 5 1 4线性表 链式存储线性表的插入 删除 插入c 删除d 20 49 25 5 1 5栈与队列 栈是限定仅在表尾进行插入和删除操作的线性表 因此 对栈来说 表尾端有其特殊的含义 称为栈顶 相应的表头端称为栈底 不含元素的空表称为空栈栈又称后进先出 LastInFirstOut 的线性表 简称LIFO 20 49 26 5 1 5栈与队列 栈的示意图 栈底 栈顶 进栈 出栈 a1 a2 an 1 an 20 49 27 5 1 5栈与队列 栈顶指针和数据元素间的关系 A B C D E 20 49 28 5 1 5栈与队列 栈的链式存储结构 链栈示意图 栈顶指针 栈顶 栈底 20 49 29 5 1 5栈与队列 队列是一种先进先出 FirstInFirstOut 的线性表 简称为FIFO 队列只允许在表的一端进行插入操作 而在表的另一端进行删除操作 允许插入元素的表端称为队尾 允许删除元素的表端称为队头 类似于日常生活中的排队 删除元素从队头进行 插入元素从队尾进行 最早进入队列的元素最早离开 20 49 30 5 1 5栈与队列 队列示意图 a1 a2 an 队头 队尾 入队列 出队列 20 49 31 5 1 6树与图 树 非线性结构 有树和二叉树 非空树有且仅有一个根结点 结点拥有子结点的个数称结点的度 A B F L K E D G H I J M C 层次 1 2 3 4 ABC的度是多少 20 49 32 5 1 6树与图 图 数据元素之间的关系可以是任意的 1 3 2 1 4 5 2 6 有向图 无向图 4 20 49 33 5 1 7算法的设计 算法的设计目标正确性 能无误地处理合法输入数据 得到满足要求的结果 可读性 便于人们阅读和交流 健壮性 对非法输入的数据能作出适当的反应和处理 效率与存储量 衡量算法的执行时间及所需的最大存储空间 20 49 34 5 1 7算法的设计 算法设计的基本策略思想分割求解法 把一个大问题划分为原问题的较小子问题 先求出各子问题的解答 然后把各子问题的解答合并成整个问题的解 动态规划法 对所有的子问题都进行解答 每个子问题的解决依赖于一系列子问题的结果 如何找出后面的子问题 要依赖于前面一系列子问题的递推关系式 这就是动态规划策略的核心 20 49 35 5 1 7算法的设计 算法设计的基本策略思想子目标法 倒推法 从某个已知的特定解出发 反过来求这个解与已知条件之间存在的关系 以得到一般解的方法图的搜索法 把问题的求解过程用图或树这种结构来描述 回溯法 先试一试某一操作 如果以后发现这个操作不适合 则允许退回去 另选一个操作来进行 本质是一种搜索算法 20 49 36 习题 p69 1 什么是算法 算法应具备哪些特性 为什么 p70 3 几种常用的算法表示方法是什么 各有什么特点 10 试比较线性表 栈和队列三种数据结构 14 好的算法应满足哪些主要的设计目标 20 49 37 5 2程序设计的基本概念 什么是程序设计Programming 程序设计是给出解决特定问题程序的过程 是指设计 编制 调试程序的方法和过程 是软件构造活动中的重要组成部分 程序设计往往以某种程序设计语言为工具 给出这种语言下的程序 程序设计过程应当包括分析 设计 编码 测试 排错等不同阶段 专业的程序设计人员常被称为程序员 20 49 38 5 2程序设计的基本概念 5 2 1程序设计语言的分类机器语言 1GL 优点 可以被计算机直接理解和执行 执行速度快 且占用内存少 缺点 通用性差 程序可读性很差 不易于调试和维护 20 49 39 5 2 1程序设计语言的分类 汇编语言 2GL 用助记符表示机器指令操作码和地址码 助记符是一些有意义的英文单词的缩写和符号 如用ADD表示加法addition 用MOV表示数据的传送move等优点 可用汇编语言写出语句少 质量高 执行速度快的程序缺点 汇编语言仍是一种面向机器的语言 通用性差 20 49 40 5 2 1程序设计语言的分类 高级语言 3GL 按照一定的 语法规则 构建程序 用英语单词表示的关键字和数学符号组成 简化开发应用程序的过程 高级语言是面向算法过程的语言 即不但要告诉计算机 做什么 还要告诉计算机 怎么做 优点 程序表达直观 可读性好 与具体机器无关 便于移植 通用性好 20 49 41 高级语言与翻译系统 通常把用高级语言编写的程序称为源程序 把用二进制代码表示的程序称为机器代码程序或者目标程序 计算机只能识别和执行由二进制代码组成的机器语言 因此源程序必须经过语言处理程序翻译成目标程序才能被计算机执行 具有翻译功能的语言处理程序 编译程序 又称编译器 和解释程序 又称解释器 20 49 42 第四代语言4GL 是一种非过程化的语言 只需说明所要完成的加工和条件 给出输入数据并指明输出形式 就能得到所需结果 优点 简单易学 编程省时省力 无需很多程序设计知识就能开发应用程序应用 目前流行的关系型数据库管理系统结构化查询语言SQL 具有数据的查询 定义 操纵和控制功能 如Oracle Sybase MSSQLServer Access等 5 2 1程序设计语言的分类 20 49 43 非过程化语言 高级语言 过程化语言 解决问题时 必须详细描述解决问题的每一步 既要解决 做什么 又要解决 怎么做 非过程化语言不必描述繁琐的解决问题过程 只需告诉计算机 做什么 而不必指明 怎么做 特点 只指定哪些数据被操纵 至于对这些数据要执行哪些操作 以及这些操作是如何执行的 则未被指定 5 2 1程序设计语言的分类 20 49 44 5 2 1程序设计语言的分类 第五代语言5GL也是非过程化的语言 它们提供了可视化的图形界面来生成源代码 通常第五代语言使用第三代语言或第四代语言的编译程序来转换得到相应的机器语言程序 有些面向对象的开发工具和网页开发工具 如VisualBasic VisualC Java等就属于第五代语言 20 49 45 程序设计分类 按照结构性质分 有结构化程序设计与非结构化程序设计 前者是指具有结构性的程序设计方法与过程 它具有由基本结构构成复杂结构的层次性 后者反之 按照用户要求分 有过程式程序设计与非过程式程序设计 前者是指使用过程式程序设计语言的程序设计 后者指非过程式程序设计语言的程序设计 按照设计的成分性质分 有顺序程序设计 并发程序设计 并行程序设计 分布式程序设计 按照程序设计风格分 有逻辑式程序设计 函数式程序设计 对象式程序设计 20 49 46 Java Delphi VisualBASIC C C C C PASCAL 5 2 2几种常见的高级语言 COBOL FORTRAN BASIC 20 49 47 5 3结构化程序设计 结构化程序设计的思想 任何程序都只依靠三种基本结构的组合实现 顺序结构 选择结构和循环结构 选择结构又称分支结构 由这三种基本结构组成的程序称为结构化程序强调程序的结构和可读性 为缓解软件危机作出了重要的贡献 20 49 48 5 3结构化程序设计 控制结构 表达式 语句1 If语句 单分支结构 表达式 语句1 If else语句 双分支结构 语句2 F T F T 一位老学者曾经说过 顺续执行的程序都是简单的 程序的复杂性往往都体现在条件判断与循环控制上 20 49 49 5 3结构化程序设计 控制结构 表达式 语句 while语句的执行流程 表达式2 计算表达式3 for语句的执行流程 语句 F T F T 计算表达式1 For语句的下一条语句 比较while for与do while 20 49 50 5 3结构化程序设计 函数是C语言程序的基本组成单位 它不仅可以实现程序的模块化 使程序设计变得简单和直观 提高易读性和可维护性 而且还可以把程序中普通用到的一些计算或操作编成通用的函数 以供随时调用 这样可以大大地减轻程序员的代码工作量 C语言 主函数main 若干个函数组成函数可被任意调用 函数调用自己则产生递归 20 49 51 5 3结构化程序设计 指针point学习C语言 如不能用指针编写有效 正确和灵活的程序 可以认为没有学好C语言指针 地址 数组及其相互关系是C语言中最有特色的部分 规范地使用指针 可使程序达到简单明了不但要学会如何正确地使用指针 而且要学会在各种情况下正确地使用指针变量 20 49 52 5 3结构化程序设计 数组数组是有序数据的集合 数组中的元素具有相同的数据类型和名字 以不同的下标相区分 称为数组元素 使用数组时 先要进行定义 然后才能使用 a 0 a 1 a 2 a 3 a 4 数组a的示意图 20 49 53 5 4面向对象程序设计 面向对象具有如下优势 抽象性 能很好地表达任何复杂的数据类型 亦允许用户灵活地定义自己所需的数据类型 封装性 对象作为编程中的单元 满足模块独立性高的要求 再加上继承性和多态性 更有助于简化大型软件重复定义的模块 可重用性 大大提高了大型软件的可靠性和开发效率 20 49 54 什么是面向对象 Coad和Yourdon给出了一个定义 面向对象 对象 类 继承 消息 如果一个软件系统是使用这样4个概念设计和实现的 则认为这个软件系统是面向对象的 一个面向对象的程序的每一成份应是对象 计算是通过新的对象的建立和对象之间的消息传送来执行的 20 49 55 对象object 对象是面向对象开发模式的基本成份每个对象可用它本身的一组属性和它可以执行的一组操作来定义 属性一般只能通过执行对象的操作来改变 操作又称为方法或服务 它描述了对象执行的功能 若通过消息传递 还可以为其它对象使用 20 49 56 类class 类是一组具有相同数据结构和相同操作的对象的集合 类的定义包括一组数据属性和在数据上的一组合法操作 类定义可以视为一个具有类似特性与共同行为的对象的模板 可用来产生对象在一个类中 每个对象都是类的实例Instance 它们都可使用类中的函数 20 49 57 对象实现了数据与操作的结合 行为Behavior 说明这个对象能做什么 就是对象能进行什么操作 由方法或函数描述 状态State 当对象施加方法时对象的反映 通常用数据描述 标识Identity 区别于其它对象标志 每一个对象有唯一的ID 20 49 58 对象实现了数据与操作的结合 续 改变传统方法中将数据与操作 亦称函数或过程 相分离的做法 实现了将数据与操作封装在对象的统一体中 对象具有独立性和自治性 其内部状态不受或很少受外界的影响 20 49 59 每架飞机都是一个具体的对象 如飞豹 对象与类de示例 20 49 60 抽取飞机共同的特性 形成类 凡是飞机都能在空中飞行 具有改变飞行方向 控制飞行高度和速度的操作特性 凡是飞机都有机名 机型 飞行高度 飞行速度等数据 用以描述飞机的结构性能飞机还有严格的飞行安全约束规则 如飞行条件 起飞与降落条件等 20 49 61 封装 面向对象编程中模块的基本单元是类 类将数据和处理数据的过程封装为一个有机的整体 相比之下 面向过程编程中模块的基本单元是过程 数据处理在过程中进行 通过给函数传递参数然后获得一个函数返回值 20 49 62 概念封装和信息隐蔽 概念封装和信息隐蔽 使得类具有更大的独立性 在任一时刻都可以在类的界面上增加新的操作 并能够修改实现 以改进性能 或引入原来设计中没有的新服务为便于类的调整 应尽量做到定义与实现分离 对一个类的共有界面的实现所做的多次修改不应影响利用它的那些类 20 49 63 5 4面向对象程序设计 继承Inheritance一个类可以有父类superclass 也可以有子类subclass 每个 子类 都可以继承 类 的属性和方法 这种低层类继承高层类的属性和方法就叫做继承继承是指在类中 基于层次的关系共享属性和操作 一个类可以被细化为子类 每个子类继承父类的所有属性 也可以增加它独有的属性 20 49 64 类层次的结构继承 20 49 65 5 4面向对象程序设计 继承 20 49 66 5 5软件工程softwareengineering 弗里兹 鲍尔定义 软件工程是为了经济地获得能够在实际机器上有效运行的可靠软件而建立和使用的一系列完善的工程化原则 1983年IEEE定义 软件工程是开发 运行 维护和修复软件的系统方法 软件 定义 计算机程序 方法 规则 相关的文档资料以及在计算机上运行时所必需的数据 强调工程化重要性 20 49 67 软件工程三要素 方法 工具和过程 方法强调 如何做 包括诸如项目计划与估算 需求分析 数据结构 系统总体结构的设计 算法过程的设计 编码 测试以及维护等 工具为方法提供自动的或半自动的软件支撑环境 计算机辅助软件工程CASE将各种软件工具 开发机器和一个存放开发过程信息的工程数据库组合成一个软件开发支撑系统 即软件工程环境 20 49 68 软件工程三要素 方法 工具和过程 过程则是将软件工程的方法和工具综合起来以达到合理 及时地进行计算机软件开发的目的 过程定义了方法使用的顺序 要求交付的文档资料 为保证质量和协调变化所需要的管理 及软件开发各个阶段完成的里程碑 20 49 69 5 5软件工程 软件的生命周期的瀑布模型 计划 需求分析 设计 编码 测试 运行维护 20 49 70 演化模型 由于在项目开发的初始阶段人们对软件的需求认识常常不够清晰 因而使得开发项目难于做到一次开发成功 出现返工再开发在所难免 做两次 第一次只是试验开发 其目标只是在于探索可行性 弄清软件需求 第二次则在此基础上获得较为满意的软件产品 20 49 71 螺旋模型 螺旋模型沿着螺线旋转 在四个象限上分别表达四个方面的活动 制定计划 确定软件目标 选定实施方案 弄清项目开发的限制风险分析 分析所选方案 考虑如何识