江苏专转本计算机第3章剖析.ppt

* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * “系统文件”是操作系统本身所包含的文件，删除时系统会给出警告，资源管理器若不特别设置为“显示全部文件”（在“工具”菜单的“文件夹选项”对话框中设置）时不会在文件列表中显示； 若为隐藏文件，且资源管理器又设置为“不显示隐藏文件”时，它不会在文件列表中列出； 存档属性通常被当作文件的一种标识，“文件备份程序”通过该属性来决定文件是否需要进行备份，新建的文件或在备份后又被修改过的文件，系统自动地将其属性设置为存档，在执行了备份操作后所有被备份的文件均被清除存档属性； 只读文件表示该文件只能阅读，不允许进行修改，若需修改则操作系统给出警告。 文件还可以具有“压缩”、“加密”和“编制索引”属性，前两个属性分别用来指出该文件的数据在保存到磁盘存储器时是否需要进行数据压缩（为了节省磁盘空间）和数据加密（不让无关用户了解文件的内容），后一个属性可以帮助编制该文件的索引，以利于快速进行检索。 * * * * * * * * * * * * * addiu: 无符号立即数加法 * * * * * 算法是解决问题的方法与步骤 例：有三个硬币，其中一个是伪造的，另两个是真的，伪币与真币重量略有不同。现在提供一座天平，如何找出伪币呢？ 分析： 方法明确而有序 按提供的条件进行操作 任何人均可仿照进行(共享智能) 开始 C是伪币 B是伪币 A是伪币 A＝B？ A＝C？ 是 否 否 是 算法的表示方法 文字说明 流程图表示 用N-S盒图表示算法 用PAD图描述算法 伪代码（一种介于自然语言和程序设计语言之间的文字和符号表达工具） 自然语言描述 “比较Ａ与Ｂ的重量，若Ａ＝Ｂ，则Ｃ是伪造的；否则再比较Ａ与Ｃ的重量，若Ａ＝Ｃ，则Ｂ是伪造的；否则Ａ是伪造的。” 缺点： 容易产生歧义，很难 “精确”地进行表达 叙述冗长，很难清楚地表达算法的逻辑流程 算法的流程图表示 流程图由结点和有向边构成，它描述了算法所执行操作的顺序及执行操作的条件 流程图符号 ： 比文字描述简明，但当算法比较复杂时，理解困难，容易产生错误 端点符 处理 判断 预定义功能 原始数据放在 数组A中；令 i=1 确定A[i]到A[n]中最 小整数的位置,设为j A[i] 和A[j]交换位置 i = i + 1 i = n ? 结束 开始 3. 算法的分析 算法分析的基本内容 正确性：给定有效输入后，经过有限时间的计算，产生正确的输出结果 简单性 算法是否容易理解，是否容易验证其正确性，程序是否容易调试 简单的算法效率不一定高，要在保证一定效率的前提下力求算法简单 时间复杂性(Time Complexity) ： 当问题的规模n充分大时，运行该算法所需要的时间的数量级表示 空间复杂性(Space Complexity) ： 除原始数据之外，额外占用的存储空间的大小 计算机算法的4个特点 目的：完成某个特定的信息处理任务 必须满足的性质： （考点） ① 确定性：算法中每一步操作的含义必须清楚明确，无二义性 ② 能行性： 算法中有待实现的操作都是计算机可执行的，即必须在计算机的能力范围之内，且在有限时间内能够完成 ③ 有穷性： 算法在执行了有限步操作后必须结束 ④ 算法结束后至少产生一个输出（包括参量或状态的变化） 3.4.2 数据结构 什么是数据结构？ 数据结构 研究如何在计算机中表示被处理的对象及对象之间的关系，即如何组织数据。例如： 选择排序中，未排序整数和已排序整数如何表示？ 排序算法中，排序的对象若不是整数而是姓名如何表示？是文件夹中的文件名又如何表示？是表格中的“行”又如何表示？ Word文档中插入的表格和图片如何表示？ Windows操作系统中菜单如何表示？对话框如何表示？窗口如何表示？ 计算机下棋时，棋盘和棋局如何表示？ 精心设计的数据结构可使算法获得更高的时间效率或空间效率 数据结构的内容 1 数据的抽象(逻辑)结构，即数据结构中包括哪些元素，相互之间有什么关系等。例如： 2 数据的物理(存储)结构，即数据的抽象结构如何在实际的存储器中予以实现，数据元素如何表示，相互关系如何表示等 3 定义在数据结构上的一组运算(操作)及其实现方法 线性结构 网状结构 树形结构 集合结构 小 结 1 数据结构研究如何在计算机中描述操作对象和操作对象之间的关系： 所有操作对象在计算机中均表示为某种类型的数据(或数据结构) 操作对象之间的关系可以刻画为： 每一种数据结构均有3个方面的内容： 设计其概念结构（逻辑结构） 设计其存储结构（物理结构） 设计并实现其运算（操作） 集合结构 线性结构 树形结构 网状结构 小 结 2 数据结构