算法和数据结构.ppt

《算法和数据结构.ppt》由会员分享，可在线阅读，更多相关《算法和数据结构.ppt（28页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、3.4 算法和数据结构算法和数据结构3.4.1 算法算法3.4.2 数据结构数据结构23.4 算法和数据结构3.4.1 算法算法33.4 算法和数据结构计算机计算机求解问题的步骤求解问题的步骤(1)确定并理解问题；确定并理解问题；(2)寻找解决问题的方法与步骤，并将其表示成寻找解决问题的方法与步骤，并将其表示成算法算法(Algorithm)；(3)使用某种程序设计语言描述该算法使用某种程序设计语言描述该算法(编程编程),并进行调试；并进行调试；(4)运行程序，获得问题的解答；运行程序，获得问题的解答；(5)进行评估，改进算法和程序进行评估，改进算法和程序43.4 算法和数据结构1.什么是算法？

2、什么是算法？53.4 算法和数据结构算法是解决问题的方法与步骤算法是解决问题的方法与步骤n例：有三个硬币，其中一个是例：有三个硬币，其中一个是伪造的，另两个是真的，伪币伪造的，另两个是真的，伪币与真币重量略有不同。现在提与真币重量略有不同。现在提供一座天平，供一座天平，如何如何找出伪币呢找出伪币呢？n分析：分析：n方法明确而有序方法明确而有序n按提供的条件进行操作按提供的条件进行操作n任何人均可仿照进行任何人均可仿照进行(共享共享智能智能)开始开始C是伪币是伪币B是伪币是伪币A是伪币是伪币AB？AC？是是否否否否是是63.4 算法和数据结构2.算法设计举例算法设计举例73.4 算法和数据结构例

3、：对整数进行排序例：对整数进行排序n问题：任给一组问题：任给一组(n个个)整数，将它们从小到大进行排序整数，将它们从小到大进行排序n粗略的思路：粗略的思路：从所有整数中选一个最小的，作为已排序的第一个数从所有整数中选一个最小的，作为已排序的第一个数 从剩下未排序整数中选最小的数，添加到已排序整数的后面从剩下未排序整数中选最小的数，添加到已排序整数的后面 反复执行步骤反复执行步骤，直到所有整数都处理完毕，直到所有整数都处理完毕n进一步细化：进一步细化：n把待排序的整数放在一个数组把待排序的整数放在一个数组A中，每个整数是数组中，每个整数是数组A中的一中的一个元素：个元素：A1,A2,A3,An,

4、n排好序的元素在排好序的元素在A的前面部分，无序的元素留在后面，每的前面部分，无序的元素留在后面，每“循循环环”一次，有序部分增加一次，有序部分增加1个元素，无序部分减少个元素，无序部分减少1个元素个元素n每次每次“循环循环”只需在数组的无序元素部分选出最小的数只需在数组的无序元素部分选出最小的数n反复进行反复进行n-1次即可得到排序后的结果次即可得到排序后的结果83.4 算法和数据结构“直接选择排序直接选择排序”算法举例算法举例2345789第第6次循环后，排序结束次循环后，排序结束2937845与首元素交换，第与首元素交换，第1次循环结束次循环结束4937825数组的初态，全部是未排序元素

5、数组的初态，全部是未排序元素4937825在未排序元素中确定最小数位置在未排序元素中确定最小数位置2397845与首元素交换，第与首元素交换，第2次循环结束次循环结束2937845在未排序元素中确定最小数位置在未排序元素中确定最小数位置2347895与首元素交换，第与首元素交换，第3次循环结束次循环结束2397845在未排序元素中确定最小数位置在未排序元素中确定最小数位置93.4 算法和数据结构3.算法的表示算法的表示103.4 算法和数据结构算法的表示方法算法的表示方法n文字说明文字说明n流程图表示流程图表示n用用N-S盒图表示算法盒图表示算法n用用PAD图描述算法图描述算法n伪代码（一种介

6、于自然语言和程序设计语言之间伪代码（一种介于自然语言和程序设计语言之间的文字和符号表达工具）的文字和符号表达工具）113.4 算法和数据结构自然语言描述自然语言描述n“比较与的重量，若，则是伪造的；比较与的重量，若，则是伪造的；否则再比较与的重量，若，则是伪否则再比较与的重量，若，则是伪造的；否则是伪造的。造的；否则是伪造的。”n缺点：缺点：n容易产生歧义，容易产生歧义，很难很难“精确精确”地进行表达地进行表达n叙述冗长，很难清楚地表达算法的逻辑流程叙述冗长，很难清楚地表达算法的逻辑流程123.4 算法和数据结构算法的流程图表示算法的流程图表示n流程图由结点和有向边构成，它描述了算法所执行操流

7、程图由结点和有向边构成，它描述了算法所执行操作的顺序及执行操作的条件作的顺序及执行操作的条件n流程图符号流程图符号：n比文字描述简明，但当算法比文字描述简明，但当算法比较复杂时，理解困难，容比较复杂时，理解困难，容易产生错误易产生错误 端点符端点符处理处理判断判断预定义功能预定义功能原始数据放在原始数据放在数组数组A中；令中；令 i=1确定确定Ai到到An中最中最小整数的位置小整数的位置,设为设为jAi 和和Aj交换位置交换位置i=i+1i=n?结束结束开始开始133.4 算法和数据结构求最大公约数的伪代码表示求最大公约数的伪代码表示算法算法3：辗转相除法求最大公约数：辗转相除法求最大公约数B

8、EGIN input m,n;/*输入正整数输入正整数m和和n*/do rm mod n;m n;n r;while r0;print m；/*输出最大公约数输出最大公约数*/ENDYNr不等于不等于0?输出输出m的值的值输入正整数输入正整数m和和n开始开始结束结束rm被被n除的余数除的余数m n;n r143.4 算法和数据结构4.算法的分析算法的分析153.4 算法和数据结构算法分析的基本内容算法分析的基本内容n正确性：给定有效输入后，经过有限时间的计算，正确性：给定有效输入后，经过有限时间的计算，产生正确的输出结果产生正确的输出结果n简单性简单性n 算法是否容易理解，是否容易验证其正确性

9、，程算法是否容易理解，是否容易验证其正确性，程序是否容易调试序是否容易调试n简单的算法效率不一定高，要在保证一定效率的前简单的算法效率不一定高，要在保证一定效率的前提下力求算法简单提下力求算法简单n时间复杂性时间复杂性(Time Complexity)：n当问题的规模当问题的规模n充分大时，运行该算法所需要的时充分大时，运行该算法所需要的时间的数量级表示间的数量级表示 n空间复杂性空间复杂性(Space Complexity)：n除原始数据之外，额外占用的存储空间的大小除原始数据之外，额外占用的存储空间的大小163.4 算法和数据结构选择排序算法的时间复杂性选择排序算法的时间复杂性假设参加排序

10、的整数有假设参加排序的整数有n个个（1）比较操作的次数：）比较操作的次数：在第在第i趟排序中选出最小整数时，需做趟排序中选出最小整数时，需做n-i次比较操作，次比较操作，因此，总的比较操作次数为：因此，总的比较操作次数为：n(n-1)/2=(n2-n)/2（2）移动操作的次数：）移动操作的次数：最好情况最好情况(原始数据已经排序原始数据已经排序)时，移动次数为时，移动次数为0最坏情况最坏情况(原始数据逆序排列原始数据逆序排列)时，每趟均要执行交换操时，每趟均要执行交换操作作(3次传送次传送)，总的移动次数取最大值为：，总的移动次数取最大值为：3(n-1)所以，直接选择排序的时间复杂性所以，直接

11、选择排序的时间复杂性 为为 O(n2)设置设置i的初值为的初值为1，循环执行下列操作，直到，循环执行下列操作，直到I=n：确定确定Ai 到到An中最小的整数元素的位置，设为中最小的整数元素的位置，设为j；交换交换Ai和和j；i=i+1 173.4 算法和数据结构4.小结小结183.4 算法和数据结构计算机算法的计算机算法的4个特点个特点n目的：完成某个特定的信息处理任务目的：完成某个特定的信息处理任务n必须满足的性质：必须满足的性质：确定性：算法中每一步操作的含义必须清楚明确，确定性：算法中每一步操作的含义必须清楚明确，无二义性无二义性 能行性：能行性：算法中有待实现的操作都是计算机可执算法中

12、有待实现的操作都是计算机可执行的，即必须在计算机的能力范围之内，且在有限行的，即必须在计算机的能力范围之内，且在有限时间内能够完成时间内能够完成 有穷性：有穷性：算法在执行了有限步操作后必须结束算法在执行了有限步操作后必须结束 算法结束后至少产生一个输出（包括参量或状态算法结束后至少产生一个输出（包括参量或状态的变化）的变化）19第12讲 数据结构3.4.2 数据结构数据结构20第12讲 数据结构什么是数据结构？什么是数据结构？n数据结构数据结构 研究如何在计算机中表示被处理的对象及对研究如何在计算机中表示被处理的对象及对象之间的关系，即如何组织数据。例如：象之间的关系，即如何组织数据。例如：

13、n选择排序中，未排序整数和已排序整数如何表示？选择排序中，未排序整数和已排序整数如何表示？n排序算法中，排序的对象若不是整数而是姓名如何表示排序算法中，排序的对象若不是整数而是姓名如何表示？是文件夹中的文件名又如何表示？是表格中的？是文件夹中的文件名又如何表示？是表格中的“行行”又如何表示？又如何表示？nWord文档中插入的表格和图片如何表示？文档中插入的表格和图片如何表示？nWindows操作系统中菜单如何表示？对话框如何表示？操作系统中菜单如何表示？对话框如何表示？窗口如何表示？窗口如何表示？n计算机下棋时，棋盘和棋局如何表示？计算机下棋时，棋盘和棋局如何表示？n精心设计的数据结构可使精心

14、设计的数据结构可使算法算法获得更高的时间效率或获得更高的时间效率或空间效率空间效率21第12讲 数据结构数据结构的内容数据结构的内容1 数据的数据的抽象抽象(逻辑逻辑)结构结构，即数据结构中包括哪些元素，相互，即数据结构中包括哪些元素，相互之间有什么关系等。例如：之间有什么关系等。例如：2 数据的数据的物理物理(存储存储)结构结构，即数据的抽象结构如何在实际的存，即数据的抽象结构如何在实际的存储器中予以实现，数据元素如何表示，相互关系如何表示等储器中予以实现，数据元素如何表示，相互关系如何表示等3 定义在数据结构上的一组定义在数据结构上的一组运算运算(操作操作)及其实现方法及其实现方法线性结构

15、线性结构网状结构网状结构树形结构树形结构集合结构集合结构22第12讲 数据结构2.线性数据结构线性数据结构 23第12讲 数据结构3.非线性数据结构非线性数据结构 24第12讲 数据结构树树(Tree)n“树树”是一种与线性表不同的数据结构，在树中各数是一种与线性表不同的数据结构，在树中各数据元素之间的逻辑关系具有层次性据元素之间的逻辑关系具有层次性(树的一般形式树的一般形式)层次层次1层次层次2层次层次3层次层次4根结点根结点叶结点叶结点叶结点叶结点叶结点叶结点叶结点叶结点(二叉树二叉树)根结点根结点叶结点叶结点叶结点叶结点叶结点叶结点25第12讲 数据结构树的数组实现树的数组实现01234

16、5数组数组下标下标2A1Y1L0D0S-1H说明：说明：每个数组元素有每个数组元素有2个数据项：一项是树的节点的数据元素，另一个数据项：一项是树的节点的数据元素，另一项是该节点的父节点所在的数组元素下标项是该节点的父节点所在的数组元素下标26第12讲 数据结构树的链表实现树的链表实现（二叉树的结点）（二叉树的结点）数据元素数据元素右子结点右子结点指针指针左子结点左子结点指针指针27第12讲 数据结构小小 结结 1n数据结构研究如何在计算机中描述操作对象和操作对数据结构研究如何在计算机中描述操作对象和操作对象之间的关系：象之间的关系：n所有操作对象在计算机中均表示为某种类型的数据所有操作对象在计

17、算机中均表示为某种类型的数据(或数或数据结构据结构)n操作对象之间的关系可以刻画为：操作对象之间的关系可以刻画为：n每一种数据结构均有每一种数据结构均有3个方面的内容：个方面的内容：n设计其概念结构（逻辑结构）设计其概念结构（逻辑结构）n设计其存储结构（物理结构）设计其存储结构（物理结构）n设计并实现其运算（操作）设计并实现其运算（操作）集合结构集合结构线性结构线性结构树形结构树形结构网状结构网状结构28第12讲 数据结构小小 结结 2n数据结构与高级程序设计语言的关系：数据结构与高级程序设计语言的关系：n初级初级(基本基本)数据类型数据类型 n语言本身定义语言本身定义(扩充扩充)的数据类型的数据类型n程序员定制的新的数据类型程序员定制的新的数据类型n瑞士计算机科学家尼瑞士计算机科学家尼沃思（沃思（N.Wirth）在）在20世纪世纪70年年代曾经提出过一个著名公式：代曾经提出过一个著名公式：n“数据结构数据结构+算法算法=程序程序”n之后他又提出：之后他又提出：n“计算机科学就是研究算法的学问计算机科学就是研究算法的学问”数据结构数据结构