大学信息技术基础(第六章)概要.ppt

大学信息技术基础 ——软件设计基础 （第六章） 算法是处理问题的策略 数据结构是问题的数学模型 数据结构+算法=程序 6.1.1 算法的基本概念 算法是对问题解决步骤的描述 程序可以作为算法的一种描述，但通常程序的编制不可能优于算法的设计 可行性 确定性 有穷性 输入 输出（一个算法可以有一个或多个输出） 6.1.2 算法的表示 自然语言——歧义性 传统流程图 起止框—— 输入、输出框—— 处理框—— 连接点—— N-S图 顺序结构 选择结构 当型循环——注意：这种循环可能一次都不被执行 直到型循环——注意：这种循环至少被执行一次 6.1.2 算法的表示 伪代码——介于自然语言和计算机语言间的算法描述工具 计算机程序设计语言 算法可以与计算机无关 6.1.3 算法设计的基本方法 列举法（穷举法或枚举法） 扫描所有的可能性 归纳法—— 列举一些一般性的情况，经过分析，总 结出一般性的关系 递推法—— 从已知的初始条件出发，逐次推出各个 中间结果和最后结果 递归法—— 将问题逐渐分解到最后的简单问题，再 沿着分解的逆过程逐步综合，直到解决 原问题 递归法的程序举例 Public double factorial(int num) { switch(num) { case 1: return 1; default: return num*factorial (num-1); } } 6.1.3 算法设计的基本方法 分治法 对问题分而治之 回溯法—— 对解决问题的可能性的树形采用线路尝 试，如果不行再回溯尝试的方法，常见 的是下棋的算法 6.1.4 算法的评价 正确性 执行结果满足预先规定的功能和性能要求 可读性—— 易读易懂 健壮性—— 对非法输入数据做出恰当的反应或处理 复杂性—— 所需计算机资源的多少 时间复杂性：程序在计算机上运行所花费的时间 空间复杂性：指执行这个算法所需的内存空间 6.1.5 程序与程序设计语言 程序 程序包含两方面：对象间的关系（数据结构），对象进行处理的加工规则（算法） 程序设计语言 机器语言—— 由二进制代码组成，是唯一可以直接在 计算机上执行的语言 汇编语言—— 用助记符代替机器语言，是面向机器语 言，不同类型计算机，汇编语言不同 6.1.5 程序与程序设计语言 高级语言——与机器指令系统无关 第一种高级语言——FORTRAN 编译程序：一次性将源程序翻译成目标程序，经过链接后产生可执行程序 解释程序：指令逐条翻译，逐条执行 编译程序的执行效率高于解释程序 6.2 数据结构 数据集合中各数据元素之间所固有的逻辑关系，即数据的逻辑结构 各数据元素在计算机中的存储关系，即数据的存储结构 对各种数据结构的运算 6.2.1 数据结构的基本概念 数据 数据元素（作为一个整体考虑的数据） 数据对象（性质相同数据元素的集合） 数据类型（值的集合及集合上的操作的总称） 数据结构是指相互间存在一定关系的数据元素的集合以及定义在其上的操作 数据的逻辑结构是指反映数据元素间逻辑关系的数据结构 6.2.1 数据结构的基本概念 数据的逻辑结构中要掌握的概念： 前件、后件 根节点、终端节点 数据的存储结构 逻辑上相邻的数据并不一定存储在一起 存储结构上的基本操作 插入、删除、更新、查找、排序、遍历 6.2.2 线性结构 主要的数据结构： 线性表、栈、队列、链表 特定： 线性表——顺序存储结构 栈 —— 先进后出 队列 —— 先进先出 链表 —— 便于插入和删除数据 6.2.3 非线性结构 非线性结构主要包括： 二叉树的遍历： 先序遍历、中序遍历、后序遍历 先序遍历：根-左-右 中序遍历：左-根-右 后序遍历：左-右-根 6.3 程序设计方法 6.3.1 程序设计的一般过程 问题描述、算法设计、代码编制、调试运行编写程序文档 6.3.2 结构化程序设计 结构化程序的基本结构与设计思想 任何算法都可以由三种基本结构：顺序、选择、循环的组合来完成 结构化设计的思想是以模块化设计为中心 模块的基本特征：只有一个入口和一个出口 6.3.2 结构化程序设计 结构化程序的基本原则 自顶向下，逐步求精 单入口、单出口 限制使用goto语句 6.3.3 面向对象程序设计 面向对象的程序设计（OOP） 起源Smalltalk语言 常见的OOP语言：Visual Basic,Visual C++,Java,Dephi等 面向对象的一些基本概念 类、对象、属性、方法、事件、事件过程、事件驱动 6.3.3 面向对象程序设计 面向对象程序设计的特点 抽象 数据抽象——反应对象的静态特征 行为抽象——反应对象的动态特征 封装 继承 多态 6.4 软件工程 软件