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