程序构造的基本方法.ppt

程序设计与算法语言 大学计算机知识基础,程序构造的基本方法,信息科学与工程学院,程序构造的基本方法,2,上讲回顾,计算机中数据的表示 进位计数制 基数 位权 机器数怎样用二进制表示负数并正确运算 原码、补码、反码、移码 小数点的表示 定点 浮点 非数值数据的编码 汉字编码 布尔代数,信息科学与工程学院,程序构造的基本方法,3,程序构造的基本方法,1. 数据组织 2. 数据处理 数据的组织与数据的处理相互影响,信息科学与工程学院,程序构造的基本方法,4,1. 数据组织,两大类型 内存数据组织：存放于内部存储器中的数据，数量相对较小 外存数据组织：存放于内部（一小部分）和外部（绝大部分）存储器中的数据，数量相对较大，需要专用数据管理系统来协调数据的交换 文件系统 数据库系统,信息科学与工程学院,程序构造的基本方法,5,1. 数据组织,逻辑组织：一种抽象的描述，只涉及数据之间的组织关系。其组织方法 1. 简单 2. 线性 3. 层次 4. 网状 5. 外存 物理组织：一种具体的组织形态,信息科学与工程学院,程序构造的基本方法,6,1. 数据组织,简单数据组织方法 用于相互之间没有太强关系的少量数据 对每一个数据都取一个名称，代表存放数据的空间,x,y,k,l,z,信息科学与工程学院,程序构造的基本方法,7,1. 数据组织,线性数据组织方法 用于同类的批量数据，即“向量”，例如 一时间段对内某一事物的观测数据x1, x2, , xn-1, xn 一个班级全体学生学号 整批数据共享一个名称，而其中每一个具体数据通过赋予各自的一个序号给出,x1,x2,x3,x4,x5,x6,x7,x8,x9,信息科学与工程学院,程序构造的基本方法,8,1. 数据组织,线性数据组织方法 具体实现（物理组织）方式 连续： 将这组数据存放在计算机内存中某个连续区域，因此可根据其对应的序号直接计算出每一个数据存储的具体区域，例如：数组 非连续：将这组数据分散存放在计算机内存中，需一个联系每一个数据存储位置的附加区域，将后面一个数据存储位置登记到前面一个数据的附加区域，例如：单向链表,信息科学与工程学院,程序构造的基本方法,9,1. 数据组织,线性数据组织链表（linked table，空间换时间）,信息科学与工程学院,程序构造的基本方法,10,1. 数据组织,线性数据组织在链表中插入元素,2060,2030,X,信息科学与工程学院,程序构造的基本方法,11,1. 数据组织,线性数据组织在链表中删除元素,X,X,2030,信息科学与工程学院,程序构造的基本方法,12,1. 数据组织,线性数据组织栈（stack，先进后出） First In Last Out（FILO） 压栈（push） 出栈（pop） 数据操作特点 只能在同一端（栈顶）进行 每次涉及一个数据,栈底,栈顶,入栈,出栈,信息科学与工程学院,程序构造的基本方法,13,1. 数据组织,线性数据组织队列（queue，先进先出） First In First Out（FIFO） 进队（push） 出队（pop） 数据操作特点 在不同端进行插入和删除操作 每次涉及一个数据,队尾,队头,进队,出队,信息科学与工程学院,程序构造的基本方法,14,1. 数据组织,层次数据组织方法树（tree） 节点 根 枝 叶子 从根到叶子的一条 路经上的所有节点 构成一个线性关系 整个数型结构由多 个线性关系叠加构成,Root,L,R,LL,RL,RLL,RR,LRR,信息科学与工程学院,程序构造的基本方法,15,1. 数据组织,网状数据组织方法图（graph） 允许任意两个数据之间都可存在关系 使用一个矩阵定义数据之间的关系 使用线性复合的方式表达网状数据组织 可定义数据之间的顺序关系 可定义数据之间的关系代价,A,B,D,E,C,信息科学与工程学院,程序构造的基本方法,16,1. 数据组织,外存数据组织方法（大容量数据组织）文件（file） 建立（create） 使用 打开（open） 读/写（read/write） 关闭（close） 删除（delete） 移动（move）,信息科学与工程学院,程序构造的基本方法,17,2. 数据处理方法算法,定义：一个有穷的指令集，规定一个运算序列 特点 有零或多个输入（事先得到的） 有一或多个输出 确定性：每一步都应确切和无歧义定义 有穷性 有效性 算法与数据组织密切相关，是在某种数据组织结构上的一种解决问题的计算方法,信息科学与工程学院,程序构造的基本方法,18,2. 数据处理方法算法,衡量算法的标准用相对量级表示 时间 空间,信息科学与工程学院,程序构造的基本方法,19,2. 数据处理方法算法,1. 算法描述 算法是抽象的，但必须通过具象的方式来展示。形式 语言：自然语言、类计算机语言、计算机语言 图形： 流程图、N-S图、PAD 图 表格 2. 常用算法,信息科学与工程学院,程序构造的基本方法,20,2. 数据处理方法算法,用流程图表示基本逻辑控制规则,处理,顺序,单分支,双分支,信息科学与工程学院,程序构造的基本方法,21,2. 数据处理方法算法,用流程图表示基本逻辑控制规则,循环（先判断）,循环（后判断）,信息科学与工程学院,程序构造的基本方法,22,2. 数据处理方法算法,算法描述的图形方式N-S图 由Ike Nassi和Ben Shneiderman提出 一种结构化的流程图 通过一个矩形框表达一个对数据的基本处理 三种基本的元素框：顺序、分支、循环 通过三种元素框的任意逻辑组合（框的嵌套）来表达算法,信息科学与工程学院,程序构造的基本方法,23,2. 数据处理方法算法,三种基本的元素框顺序,A,B,信息科学与工程学院,程序构造的基本方法,24,2. 数据处理方法算法,三种基本的元素框分支,P成立？,是,否,A,B,信息科学与工程学院,程序构造的基本方法,25,2. 数据处理方法算法,三种基本的元素框循环,C,当P成立,C,当P成立,信息科学与工程学院,程序构造的基本方法,26,2. 数据处理方法算法,例3-2：判断一个正整数是否是素数,输入：正整数N,W0, I2,RN/I的余数,R=0?,II+1,W=0?,直到IN-1或W=1,W1,N是素数,N不是素数,T,F,T,F,信息科学与工程学院,程序构造的基本方法,27,2. 数据处理方法算法,常用算法 排序 查找 递归 回溯,信息科学与工程学院,程序构造的基本方法,28,2. 数据处理方法算法,排序（sorting）：一组数据有序化的过程 由小到大排列称为升序（ascent sorting） 由大到小排列称为降序（descent sorting） 类型（用于线性数据组织） 冒泡：将比较小的数据（泡泡）向前挤，升序；将比较大的数据（泡泡）向前挤，降序 选择：从未排序的数据集中选择最小的，升序；从未排序的数据集中选择最大的，降序,信息科学与工程学院,程序构造的基本方法,29,2. 数据处理方法算法,冒泡排序 每遍从最后一个数据开始进行两两比较并将小的排在大的前面（交换两数据），直到要冒出的位置 第一遍需要比较n - 1次冒出所有数据中的最小的，冒出位置是1 第二遍需要比较n - 2次冒出剩余数据中的最小的（第二小的） ，冒出位置是2 以此类推，共进行n - 1遍（最后第n遍不需要进行）,信息科学与工程学院,程序构造的基本方法,30,信息科学与工程学院,程序构造的基本方法,31,信息科学与工程学院,程序构造的基本方法,32,2. 数据处理方法算法,选择排序 每遍首先确定要选择的位置，再从未排序数据中找出最小的并与选择位置处的数据交换 第一遍需要比较n - 1次得到所有数据中的最小的，选择位置是1 第二遍需要比较n - 2次得到剩余数据中的最小的（第二小的），选择位置是2 以此类推，共进行n - 1遍（最后第n遍不需要进行）,信息科学与工程学院,程序构造的基本方法,33,信息科学与工程学院,程序构造的基本方法,34,2. 数据处理方法算法,查找（search）：从一组数据中找出所需数据的过程 直接（用于线性数据组织） ：逐一地与需查找的数据比较 二叉树（用于树型数据组织） 二叉搜索（排序）树：任意一结点的左子树的所有结点的数据都小于该结点数据，反之则大于 从树根开始与需查找的数据比较，大则向左，小则向右，直到树叶 动态查找需在查不到时将需查找数据插入,信息科学与工程学院,程序构造的基本方法,35,2. 数据处理方法算法,递归（recursion）：通过概念定义概念本身 一种特殊的循环，在循环体内重复循环 特征 “自引用”规则 终止条件 本质 分解：向终止条件逼近 综合：从终止条件返回 分解与综合互为逆过程 形式：单递归、多递归、嵌套递归,信息科学与工