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

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