《第3章3.4 算法和数据结构【专业教育】.ppt》由会员分享，可在线阅读，更多相关《第3章3.4 算法和数据结构【专业教育】.ppt（40页珍藏版）》请在三一文库上搜索。
1、3.4 算法和数据结构,3.4.1 算法 3.4.2 数据结构,3.4.1 算法,计算机求解问题的步骤,(1) 确定并理解问题； (2) 寻找解决问题的方法与步骤，并将其表示成算法(Algorithm) ； (3) 使用某种程序设计语言描述该算法(编程), 并进行调试； (4) 运行程序，获得问题的解答； (5) 进行评估，改进算法和程序,1. 什么是算法？,算法是解决问题的方法与步骤,例：有三个硬币，其中一个是伪造的，另两个是真的，伪币与真币重量略有不同。现在提供一座天平，如何找出伪币呢？ 分析： 方法明确而有序 按提供的条件进行操作 任何人均可仿照进行(共享智能),关于算法的三方面问题,如
2、何确定算法（算法设计）？ 如何表示算法（算法表示）？ 如何使算法更有效（算法分析）？,2. 算法设计举例,例：对整数进行排序,问题：任给一组(n个)整数，将它们从小到大进行排序 粗略的思路： 从所有整数中选一个最小的，作为已排序的第一个数 从剩下未排序整数中选最小的数，添加到已排序整数的后面 反复执行步骤，直到所有整数都处理完毕 进一步细化： 把待排序的整数放在一个数组A中，每个整数是数组A中的一个元素：A1, A2, A3, , An, 排好序的元素在A的前面部分，无序的元素留在后面，每“循环”一次，有序部分增加1个元素，无序部分减少1个元素 每次“循环”只需在数组的无序元素部分选出最小的数
3、 反复进行n-1次即可得到排序后的结果,“直接选择排序”算法举例,“直接选择排序”算法的描述,将原始数据放在数组A中； 设置i的初值为1，循环执行下列操作，直到i = n ： 确定Ai 到An中最小整数的位置，设为j ； 交换Ai和j ； i = i +1 ,用伪代码表示算法,用流程图表示算法,直接选择排序的c语言程序,void sort ( int A , int n) /* sort函数有2个参数:整型数组A和数组元素个数n */ int i, j, t, k ; /* 定义4个整型变量*/ for( i=0 ; in-1;i+) /* 重复执行n-1次，每次增加1个已排序的数 */ j
4、= i; for (k=i+1;kn ;k+) if (AkAj) j = k; /*在未排序整数中确定最小数的位置 */ t=Ai;Ai=Aj; Aj=t; /* 把未排序数中的最小数交换到未排序数的首位*/ ,3. 算法的表示,算法的表示方法,文字说明 流程图表示 用N-S盒图表示算法 用PAD图描述算法 伪代码（一种介于自然语言和程序设计语言之间的文字和符号表达工具）,自然语言描述,“比较与的重量，若，则是伪造的；否则再比较与的重量，若，则是伪造的；否则是伪造的。” 缺点： 容易产生歧义，很难 “精确”地进行表达 叙述冗长，很难清楚地表达算法的逻辑流程,算法的流程图表示,流程图由结点和有
5、向边构成，它描述了算法所执行操作的顺序及执行操作的条件 流程图符号 ：,比文字描述简明，但当算法比较复杂时，理解困难，容易产生错误,求最大公约数的伪代码表示,算法3：辗转相除法求最大公约数 BEGIN input m,n; /*输入正整数m和n*/ do rm mod n; m n; n r; while r0; print m； /*输出最大公约数*/ END,4. 算法的分析,算法分析的基本内容,正确性：给定有效输入后，经过有限时间的计算，产生正确的输出结果 简单性 算法是否容易理解，是否容易验证其正确性，程序是否容易调试 简单的算法效率不一定高，要在保证一定效率的前提下力求算法简单 时间
6、复杂性(Time Complexity) ： 当问题的规模n充分大时，运行该算法所需要的时间的数量级表示 空间复杂性(Space Complexity) ： 除原始数据之外，额外占用的存储空间的大小,选择排序算法的时间复杂性,假设参加排序的整数有n个 （1）比较操作的次数： 在第i趟排序中选出最小整数时，需做n-i次比较操作， 因此，总的比较操作次数为：n(n-1)/2 = (n2 -n)/2 （2）移动操作的次数： 最好情况(原始数据已经排序)时，移动次数为0最坏情况(原始数据逆序排列)时，每趟均要执行交换操作(3次传送)，总的移动次数取最大值为：3(n-1) 所以，直接选择排序的时间复杂性
7、 为 O(n2),设置i的初值为1，循环执行下列操作，直到I = n ： 确定Ai 到An中最小的整数元素的位置，设为j ； 交换Ai和j ； i = i +1 ,4. 小结,计算机中处处是算法！,例1：Word程序如何在文档中查找用户指定的词语？ 例2：在Word文档的表格中如何将表格内容排序？ 例3：如何把一幅彩色图片转换为灰度(黑白)图片？ 例4： Windows如何在硬盘中找到用户指定的文件？ 例5：媒体播放器如何把MP3文件转换成动听的音乐？ 例6：搜索引擎如何在WWW网中找到用户需要的网页？,算法是计算机软件的灵魂,计算机的通用性是因为它能运行各种各样的程序，而程序之所以能解决问题
8、，是因为它所体现了正确的算法 算法所解决的是一类问题而不是一个特定的问题，例如 排序(sort) 可以是表格内容的排序，也可以是文件夹中文件的排序，可以按数字或文字排序，也可以按日期排序，等等 查找(search)， 可以在文档中查找某个单词或在硬盘中查找某个文件，也可在Web上查找某个网页，等等 开发计算机应用的核心是：根据实际问题给出解题的算法，然后再将该算法在计算机上实现(即开发成为软件),计算机算法的4个特点,目的：完成某个特定的信息处理任务 必须满足的性质： 确定性：算法中每一步操作的含义必须清楚明确，无二义性 能行性： 算法中有待实现的操作都是计算机可执行的，即必须在计算机的能力范
9、围之内，且在有限时间内能够完成 有穷性： 算法在执行了有限步操作后必须结束 算法结束后至少产生一个输出（包括参量或状态的变化）,3.4.2 数据结构,算法(程序)的组成,算法(程序) 由2个部分组成： 进行的操作 所涉及的操作对象(数据),什么是数据结构？,数据结构 研究如何在计算机中表示被处理的对象及对象之间的关系，即如何组织数据。例如： 选择排序中，未排序整数和已排序整数如何表示？ 排序算法中，排序的对象若不是整数而是姓名如何表示？是文件夹中的文件名又如何表示？是表格中的“行”又如何表示？ Word文档中插入的表格和图片如何表示？ Windows操作系统中菜单如何表示？对话框如何表示？窗口
10、如何表示？ 计算机下棋时，棋盘和棋局如何表示？ 精心设计的数据结构可使算法获得更高的时间效率或空间效率,数据结构的内容,1 数据的抽象(逻辑)结构，即数据结构中包括哪些元素，相互之间有什么关系等。例如：,2 数据的物理(存储)结构，即数据的抽象结构如何在实际的存储器中予以实现，数据元素如何表示，相互关系如何表示等,3 定义在数据结构上的一组运算(操作)及其实现方法,2. 线性数据结构,举例：线性表(Liner-List),定义：若干个相同类型的数据元素组成的一个有限序列，其中每个数据元素可由多个数据项组成。表中有且仅有一个开始元素和一个结束元素，且所有元素都最多只有一个直接前趋和一个直接后继
11、例：考生成绩登记表(table),数据元素已经排了序的线性表称为有序线性表，简称有序表,每个数据元素包含3个数据项：准考证号、姓名、总分,线性表的运算(操作),增加1个新的数据元素 删除1个指定数据元素 查找指定的数据元素 最高分考生 最低分考生 将表中的数据元素排序 对表中的数据进行计算 计算平均分 ,数据结构的实现存储结构,顺序存储结构： 借助数据元素在存储器中的相对位置来表示数据元素之间的逻辑关系 链接表存储结构： 利用地址指针来表示元素之间的逻辑关系,例：线性表的实现方法之1,使用数组实现，在内存中顺序存放元素：,如果要在表中加一个姓名:马 明，结果为：,分析： 寻找指定的数据元素很容
12、易 插入元素或删除元素很不方便,内存地址,线性表的实现方法之2,使用链接表(linked list)实现： 数据元素在内存中可不按顺序存放，它们之间的顺序用“指针”来表示 指针实际上就是后继数据元素的地址,演示,2种实现方法的对比： 数组实现的空间开销少；存取指定元素的速度比较块 链表实现时插入/删除指定元素的速度快，表的长度不受限制,3. 非线性数据结构,树(Tree),“树”是一种与线性表不同的数据结构，在树中各数据元素之间的逻辑关系具有层次性,树的数组实现,说明： 每个数组元素有2个数据项：一项是树的节点的数据元素，另一项是该节点的父节点所在的数组元素下标,树的链表实现,树的应用举例：
13、人-机对弈时棋局变化的数据结构,X,X,小 结 1,数据结构研究如何在计算机中描述操作对象和操作对象之间的关系： 所有操作对象在计算机中均表示为某种类型的数据(或数据结构) 操作对象之间的关系可以刻画为： 每一种数据结构均有3个方面的内容： 设计其概念结构（逻辑结构） 设计其存储结构（物理结构） 设计并实现其运算（操作）,小 结 2,数据结构与高级程序设计语言的关系： 初级(基本)数据类型 语言本身定义(扩充)的数据类型 程序员定制的新的数据类型 瑞士计算机科学家尼沃思（N.Wirth）在20世纪70年代曾经提出过一个著名公式： “数据结构+算法 = 程序” 之后他又提出： “计算机科学就是研究算法的学问”,