《2程序构造的基本方法.ppt

信息科学与工程学院 程序构造的基本方法 程序设计与算法语言——大学计算机知识基础 程序构造的基本方法 上讲回顾 计算机中数据的表示 进位计数制 基数 位权 机器数—怎样用二进制表示负数并正确运算 原码、补码、反码、移码 小数点的表示 定点 浮点 非数值数据的编码 汉字编码 布尔代数 程序构造的基本方法 1. 数据组织 2. 数据处理 数据的组织与数据的处理相互影响 1. 数据组织 两大类型 内存数据组织：存放于内部存储器中的数据，数量相对较小 外存数据组织：存放于内部（一小部分）和外部（绝大部分）存储器中的数据，数量相对较大，需要专用数据管理系统来协调数据的交换 文件系统 数据库系统 1. 数据组织 逻辑组织：一种抽象的描述，只涉及数据之间的组织关系。其组织方法 1. 简单 2. 线性 3. 层次 4. 网状 5. 外存 物理组织：一种具体的组织形态 1. 数据组织 简单数据组织方法 用于相互之间没有太强关系的少量数据 对每一个数据都取一个名称，代表存放数据的空间 1. 数据组织 线性数据组织方法 用于同类的批量数据，即“向量”，例如 一时间段对内某一事物的观测数据{x1, x2, …, xn-1, xn} 一个班级全体学生学号 整批数据共享一个名称，而其中每一个具体数据通过赋予各自的一个序号给出 1. 数据组织 线性数据组织方法 具体实现（物理组织）方式 连续： 将这组数据存放在计算机内存中某个连续区域，因此可根据其对应的序号直接计算出每一个数据存储的具体区域，例如：数组 非连续：将这组数据分散存放在计算机内存中，需一个联系每一个数据存储位置的附加区域，将后面一个数据存储位置登记到前面一个数据的附加区域，例如：单向链表 1. 数据组织 线性数据组织——链表（linked table，空间换时间） 1. 数据组织 线性数据组织——在链表中插入元素 1. 数据组织 线性数据组织——在链表中删除元素 1. 数据组织 线性数据组织——栈（stack，先进后出） First In Last Out（FILO） 压栈（push） 出栈（pop） 数据操作特点 只能在同一端（栈顶）进行 每次涉及一个数据 1. 数据组织 线性数据组织——队列（queue，先进先出） First In First Out（FIFO） 进队（push） 出队（pop） 数据操作特点 在不同端进行插入和删除操作 每次涉及一个数据 1. 数据组织 层次数据组织方法——树（tree） 节点 根 枝 叶子 从根到叶子的一条路经上的所有节点构成一个线性关系 整个数型结构由多个线性关系叠加构成 1. 数据组织 网状数据组织方法——图（graph） 允许任意两个数据之间都可存在关系 使用一个矩阵定义数据之间的关系 使用线性复合的方式表达网状数据组织 可定义数据之间的顺序关系 可定义数据之间的关系代价 1. 数据组织 外存数据组织方法（大容量数据组织）——文件（file） 建立（create） 使用 打开（open） 读/写（read/write） 关闭（close） 删除（delete） 移动（move） 2. 数据处理方法——算法 定义：一个有穷的指令集，规定一个运算序列 特点 有零或多个输入（事先得到的） 有一或多个输出 确定性：每一步都应确切和无歧义定义 有穷性 有效性 算法与数据组织密切相关，是在某种数据组织结构上的一种解决问题的计算方法 2. 数据处理方法——算法 衡量算法的标准——用相对量级表示 时间 空间 2. 数据处理方法——算法 1. 算法描述 算法是抽象的，但必须通过具象的方式来展示。形式 语言：自然语言、类计算机语言、计算机语言 图形： 流程图、N-S图、PAD 图 表格 2. 常用算法 2. 数据处理方法——算法 用流程图表示基本逻辑控制规则 2. 数据处理方法——算法 用流程图表示基本逻辑控制规则 2. 数据处理方法——算法 算法描述的图形方式——N-S图 由Ike Nassi和Ben Shneiderman提出 一种结构化的流程图 通过一个矩形框表达一个对数据的基本处理 三种基本的元素框：顺序、分支、循环 通过三种元素框的任意逻辑组合（框的嵌套）来表达算法 2. 数据处理方法——算法 三种基本的元素框——顺序 2. 数据处理方法——算法 三种基本的元素框——分支 2. 数据处理方法——算法 三种基本的元素框——循环 2. 数据处理方法——算法 例3-2：判断一个正整数是否是素数 2. 数据处理方法——算法 常用算法 排序 查找 递归 回溯 2. 数据处理方法——算法 排序（sorting）：一组数据有序化的过程 由小到大排列称为升序（ascent sorting） 由大到小排列称为降序（descent sorting