3 程序工作方式解析课件.ppt

第三讲 3.1 程序的工作方式解析;3．1 程序工作方式解析（与对话方式的区别和联系） ;3．2 程序的本质 ;3．2．2 递归思维的简单解析 ;3．2．3 基本逻辑控制规则及其组合 ;3．3 程序构造的基本方法（数据组织+数据处理） ;1）简单数据组织 ;2）线性数据组织 ;非连续组织 将这批数据分散存放到计算机内部存储器中，每个数据存放一个位置，一般而言，这些位置是不连续的。这种数据组织实现方法，也称为链表结构。 ;非连续组织方式中，每当插入一个数据时，可以将这个数据存放在任意一个允许存放的位置，然后通过修改位置信息完成插入。 ;图3.7 线性数据组织非连续实现中的插入与删除 ;尽管非连续组织方法中不涉及数据的频繁移动，节省了大量时间。但它为了保持数据在逻辑上的线性关系，每个数据存放区域都增加了用于记录下一个数据存放位置的空间，是牺牲空间而换取时??。 ;“栈”结构 ;“队列”结构 ;3）层次数据组织——树 ;对于树型数据组织，可以通过线性复合的方式在计算机中表达。从树根开始到达每个叶子结点的一条路径上的所有点构成一个线性关系，整个树型结构是多个线性关系的叠加。 ;遍历：依照某种顺序关系依次访问树中的所有结点的过程称为遍历。;4）网状数据组织——图 ;5）外存数据组织方式（大容量数据组织）——文件 ;针对文件方式的数据组织，数据的访问一般要经过文件建立（create）、文件使用、文件删除、文件移动等基本操作。其中，文件使用必须经过打开（open）、读/写（read/write）、关闭（close）三个基本步骤。 ;3．3．2 数据处理方法——算法 ;; 算法本身是抽象的，它只是反映一种解决问题的方法，但这种方法必须通过某种形式展示出来，这就是具体的算法表示和描述。;N-S图 ;【例3-2】输入10个整数，求它们的和。 采用简单数据组织方式，用S存放和，I记录输入数据的个数。初始时，S=0，I=0。每输入一个数，I增加1，并将该数加入到S中。N-S图描述如图3.18。 ;【例3-3】给定一个正整数N，判断它是否是素数。 ;图3.19 判断N是否是素数的N-S图 ;2）常用基本算法 ;（b） 冒泡排序算法思想的可视表示（冒第一个泡） 图3.20 冒泡排序算法 ;（a）冒泡排序算法的N-S图 ;【例3-5】线性数据组织，选择排序（由小到大：升序）。 基本思想及排序过程：首先确定当前需要选择第几个数据，然后从未排序的数据集中选择一个当前最小的数据，并将其按线性序列排在已排序数据的后面。对于n个数据，一共需要选择n-1个数据。;（b） 选择排序算法思想的可视表示 图3.21 选择排序算法 ;（2）查找;（a）直接查找算法的N-S图 ;（b） 直接查找算法思想的可视表示 图3.22 直接查找算法可视化表示 ;【例3-7】 树型数据组织，二叉树查找。 ;图3.23 二叉树查找算法可视化表示 ;（3）递归 递归算法是递归思想的直接应用，递归的基本思想是，针对某个概念，通过概念本身定义这个概念。也就是用自己说明自己。 ; 递归有两个显著的特征，即递归终止条件和递归策略。比如，上面有关阶乘的例子中，①是递归终止条件；②是递归策略。递归策略往往是向递归终止条件靠拢。;嵌套递归: 是指在递归策略中，某个递归的数据部分还包含一个递归，比如，Ackerman函数的定义，就是嵌套递归。 N+1 当M=0时； Akm（M，N）= Akm（M-1，1） 当M?0，N=0时； Akm（M-1，Akm（M，N-1）） 当M?0，N?0时。;图3.24 5！的求解过程 ;（4）回溯 ;图3.26 回溯法基本结构 ;【例3-8】 老鼠走迷宫 当老鼠从一个开始点出发进入迷宫，在迷宫中经过不断的探索，能够到达指定的出口，则说明迷宫存在一条通路；否则说明迷宫没有通路。 ;3．4 程序设计的三个要素 ;3．4．1程序设计语言 ; 在计算机程序设计语言中，数据类型的概念特别重要，不同的数据类型定义不同的词性，用于指明该类词汇所表达的数据的性质、数据的大小范围，以及在该类数据上可以施加的基本运算。 ;数据类型转换;语句 ;2）语言种类及实现 ;高级语言 是一种独立于具体计算机的语言，是面向人的语言，他采用近似于自然语言的结构 ;图3.35 高级语言基本分类 ;3．4．2 程序设计环境 ;图3.37 运行支撑环境的两种模型 ;3.4.3 模式及其建构实例解析 ;② 实例解析 [模式1] 循环模式及其建构 名称 循环三步 语境 用于重复处理 问题 处理方法的重用 解决方