程序构造的基本方法.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）：通过概念定义概念本身一种特殊的循环，在循环体内重复循环特征“自引用”规则终止条件本质分解：向终止条件逼近综合：从终止条件返回分解与综合互为逆过程形式：单递归、多递归、嵌套递归,信息科学与工程学院,程序构造的基本方法,36,2.数据处理方法算法,递归举例：求阶乘“自引用”规则：N!=N(N-1)!终止条件：N!=1当N=1或N=0时,信息科学与工程学院,程序构造的基本方法,37,2.数据处理方法算法,回溯（back-tracking）：对问题的候选解按某种顺序逐一枚举（enum）和检验本质：二维穷举扩展试探和回溯维当前点的穷举维,
