算法和数据结构幻灯片.ppt
《算法和数据结构幻灯片.ppt》由会员分享,可在线阅读,更多相关《算法和数据结构幻灯片.ppt(79页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、程序设计程序设计=计算机编程语言计算机编程语言+数据结构数据结构+算法算法数据结构是指数据的逻辑结构和存储结构,数据结构是指数据的逻辑结构和存储结构,而算法则是对数据运算的描述。而算法则是对数据运算的描述。程序设计的实质是对实际问题选择一种好的程序设计的实质是对实际问题选择一种好的数据结构,加之设计一个好的算法。数据结构,加之设计一个好的算法。第1页,共79页,编辑于2022年,星期一算法的定义算法的定义算法的要素算法的要素算法的表示算法的表示算法与计算机程序的关系算法与计算机程序的关系算法设计的基本方法算法设计的基本方法对算法的评价对算法的评价第2页,共79页,编辑于2022年,星期一算法的
2、定义算法的定义一组明确的可执行步骤的有序集合一组明确的可执行步骤的有序集合例:输入两个正整数例:输入两个正整数m m和和n(mn),n(mn),求它们的最大求它们的最大公约数公约数,记为记为god(m,n)god(m,n)。根据欧几里德算法:根据欧几里德算法:若若 r r 是是 m n m n 的余数的余数,则则 gcd(m,n)=gcd(n,r)gcd(m,n)=gcd(n,r)第3页,共79页,编辑于2022年,星期一适合计算机实现的算法适合计算机实现的算法(辗转相除法辗转相除法):如如 m=28,n=8,m=28,n=8,则则god(28,8)=god(8,4)=god(4,0)=4go
3、d(28,8)=god(8,4)=god(4,0)=4算法描述算法描述算法描述算法描述自然语言:自然语言:1.1.输入输入m,n(mn)m,n(mn);2.2.求求m/nm/n的余数的余数 r r;3.3.如果如果r0r0则将则将n n放入放入m m,r r放入放入n n,转第,转第2 2步继续;如果步继续;如果r=0r=0则转第则转第4 4步步4.4.输出最大公约数输出最大公约数n n。第4页,共79页,编辑于2022年,星期一开始开始开始开始m mod nrm mod nrm mod nrm mod nrnmnmnmnmrnrnrnrn是是是是否否否否结束结束结束结束打印打印打印打印n n
4、 n n输入输入输入输入m,nm,nm,nm,nr=0?r=0?r=0?r=0?流程图:第5页,共79页,编辑于2022年,星期一算法的特征算法的特征n有穷性(有穷性(finitenessfiniteness)-能在有限时间内做完;能在有限时间内做完;n确定性(确定性(definitenessdefiniteness)-每一步骤都有明确定义;每一步骤都有明确定义;n可行性(可行性(effectivenesseffectiveness)-能实现和达到预期目的;能实现和达到预期目的;n信息性(信息性(informationinformation)-能提供足够的情报,具有输能提供足够的情报,具有输入
5、、输出。入、输出。算法的要素算法的要素n精确精确,简单和抽象分级简单和抽象分级第6页,共79页,编辑于2022年,星期一算法的表示算法的表示n流程图流程图nN-SN-S图图n伪码伪码程序流程图 NS图 伪码第7页,共79页,编辑于2022年,星期一算法与计算机程序算法与计算机程序n算法是逻辑步骤算法是逻辑步骤n计算机程序是使用某种编程语言表达算法计算机程序是使用某种编程语言表达算法第8页,共79页,编辑于2022年,星期一算法设计的基本方法算法设计的基本方法n列举法列举法-根据提出的问题列举所有可能的情况,并用根据提出的问题列举所有可能的情况,并用问题中给定的条件检验哪些是需要的,而哪些是不需
6、要问题中给定的条件检验哪些是需要的,而哪些是不需要的;的;n递推法递推法-从已知的初始条件出发,逐次地推出所要求从已知的初始条件出发,逐次地推出所要求的各中间结果和最后结果;的各中间结果和最后结果;n减半递推法减半递推法-工程上常用的分治法,即将问题的规工程上常用的分治法,即将问题的规模减半来解,最后重复模减半来解,最后重复“减半减半”的过程;的过程;第9页,共79页,编辑于2022年,星期一n递归法递归法 -首先将问题逐层分解最后归结为一些首先将问题逐层分解最后归结为一些最简单的问题,解决这些最简单问题后再沿着原来最简单的问题,解决这些最简单问题后再沿着原来分解的逆过程逐步进行综合。分解的逆
7、过程逐步进行综合。n回溯法回溯法-在处理复杂数据结构时,通过对问题的在处理复杂数据结构时,通过对问题的分析找出一个解决问题的线索,然后沿着次线索逐步分析找出一个解决问题的线索,然后沿着次线索逐步试探,若失败就逐步回退并换别的路线再进行试探;试探,若失败就逐步回退并换别的路线再进行试探;n归纳法归纳法-通过列举足够多的特殊情况发现其中一通过列举足够多的特殊情况发现其中一些规律,经过分析最终找出一般的关系;些规律,经过分析最终找出一般的关系;第10页,共79页,编辑于2022年,星期一算法举例算法举例第11页,共79页,编辑于2022年,星期一输入一个数输入一个数 maxmaxn=2n=2当当n=
8、10nmaxxmaxy ymax=xmax=xn=n+1n=n+1输出其中的最大值输出其中的最大值 maxmax 输入十个数,找出最大数输出(输入十个数,找出最大数输出(递推法递推法 )第12页,共79页,编辑于2022年,星期一假定一对刚出生的小兔子,一个月后就能长成大兔子,再假定一对刚出生的小兔子,一个月后就能长成大兔子,再过一个月后就开始生小兔子,并且也正好生一对兔子。问过一个月后就开始生小兔子,并且也正好生一对兔子。问在没有兔子死亡的情况下,一对初生的兔子一年后可繁殖在没有兔子死亡的情况下,一对初生的兔子一年后可繁殖成多少对兔子。(成多少对兔子。(递推法递推法)解:用解:用 F F(n
9、 n)表示第表示第 n n 个月的兔子对数。个月的兔子对数。第一个月:第一个月:F F(1)=1(1)=1 第二个月:第二个月:F F(2)=(2)=F F(1)+0=1(1)+0=1 第三个月:第三个月:F F(3)=(3)=F F(2)+1=2(2)+1=2 第四个月:第四个月:F F(4)=(4)=F F(3)+1=3(3)+1=3 第五个月:第五个月:F F(5)=(5)=F F(4)+2=5(4)+2=5 第六个月:第六个月:F F(6)=(6)=F F(5)+3=8(5)+3=8 第七个月:第七个月:F F(7)=(7)=F F(6)+5=13(6)+5=13第13页,共79页,编
10、辑于2022年,星期一递推到一年后即第十三个月,得递推到一年后即第十三个月,得 Fibonacci Fibonacci数列:数列:1 1,1 1,2 2,3 3,5 5,8 8,1313,2121,3434,5555,8989,144144,233 233 分析可知:分析可知:第第 n n 个月的兔子对数由两部分组成:一是第个月的兔子对数由两部分组成:一是第 n n-1-1 个月的个月的兔子对数;兔子对数;二是第二是第 n n-2-2 个月的兔子对数个月的兔子对数 所以得递推关系为所以得递推关系为 F F(1)=1(1)=1 F F(2)=1(2)=1 F F(n n)=)=F F(n n-1
11、)+-1)+F F(n-n-2)2)n n=3,4,=3,4,第14页,共79页,编辑于2022年,星期一求求Fibonacci数列流程图数列流程图开始开始F1=1,F2=1,n=3n1i=i-1x=xixi=2(x+1)输出 i,xii=7,x=1结束NY开始第第7天:天:1第第6天:天:4第第5天:天:10第第4天:天:22第第3天:天:46第第2天:天:94第第1天:天:190第18页,共79页,编辑于2022年,星期一0 0f(x1)f(x1)f(x2)f(x2)f(x3)f(x3)f(x4)f(x4)x1x1x2x2x3x3x4x4减半递推(迭代)法减半递推(迭代)法设方程设方程 f
12、(x)=0 f(x)=0在区间在区间x1,x2x1,x2上有一个实根,且上有一个实根,且f(x1)f(x1)与与f(x2)f(x2)异号,用二分法求该异号,用二分法求该方程在区间方程在区间x1,x2x1,x2上的实根。上的实根。减半递推过程:减半递推过程:1.1.求中点:求中点:x3=1/2(x1+x2)x3=1/2(x1+x2)2.2.判判 f(x3)f(x3)是否接近是否接近0 0?若接近若接近0 0,x3x3即为所求根即为所求根 若不接近若不接近0 0,则将原区间减半,则将原区间减半 舍弃与舍弃与f(x3)同号者:同号者:x2=x3 再求中点:再求中点:x4=1/2(x1+x3)如此重复
13、得:如此重复得:x1,x2,xn-1,xn当当xn与与xn-1之差小于给定的误差之差小于给定的误差En时,时,xn即为近似解即为近似解迭代关系:迭代关系:迭代关系:迭代关系:x3=(x1+x2)/2 x3=(x1+x2)/2舍弃与舍弃与f(x3)同号者:同号者:f(x3)*f(x2)0:x2=x3;f(x3)*f(x2)0:x2=x3;/*/*为下一次迭代做准备为下一次迭代做准备为下一次迭代做准备为下一次迭代做准备*/*/f(x3)*f(x1)0:x1=x3;f(x3)*f(x1)0:x1=x3;第19页,共79页,编辑于2022年,星期一f(x3)*f(x1)10-4输出结果x3YN流程图流
14、程图第20页,共79页,编辑于2022年,星期一算法的评价算法的评价n时间复杂度:时间复杂度:指算法中包含简单操作的次数指算法中包含简单操作的次数假如,随着问题规模假如,随着问题规模 n n 的增长,算法执行时间的增长率的增长,算法执行时间的增长率和和 f(n)f(n)的增长率相同,则可记作:的增长率相同,则可记作:T(n)=O(f(n)T(n)=O(f(n)称称T(n)T(n)为算法的为算法的(渐近渐近)时间复杂度时间复杂度一般以数量级的形式给出一般以数量级的形式给出如如(1),(log(1),(log2 2n n),(n),(n),(n),(n2 2)其中其中(1)(1)表示算法的时间复杂
15、度为常量,它不随数据量表示算法的时间复杂度为常量,它不随数据量n n的的改变而改变,如访问一个数据表中第一个元素时,无论该改变而改变,如访问一个数据表中第一个元素时,无论该表的大小如何,其时间复杂度均为表的大小如何,其时间复杂度均为(1)(1)第21页,共79页,编辑于2022年,星期一For i=1 to nFor i=1 to n1 do1 do y=y+1;y=y+1;/*/*/For j=0 to 2n do For j=0 to 2n do x=x+1;x=x+1;/*/*/语句语句的执行次数为:的执行次数为:n n1 1,语句语句的执行次数为:(的执行次数为:(n n1 1)()(
16、2n2n1 1)2n2n2 2n n1 1该程序段的时间复杂度为:该程序段的时间复杂度为:T T(n n)O O(n n1 12n2n2 2n n1 1)O O(n n2 2)第22页,共79页,编辑于2022年,星期一空间复杂度空间复杂度空间复杂度主要考虑在算法运行过程中临时占用的存储空间复杂度主要考虑在算法运行过程中临时占用的存储空间的大小空间的大小假如,随着问题规模假如,随着问题规模 n n 的增大,算法运行所需存储量的的增大,算法运行所需存储量的增长率与增长率与 g(n)g(n)的增长率相同,则可记作:的增长率相同,则可记作:S(n)=O(g(n)S(n)=O(g(n)称称S(n)S(
17、n)为算法的空间复杂度为算法的空间复杂度第23页,共79页,编辑于2022年,星期一数据结构的基本术语数据结构的基本术语数据的逻辑结构数据的逻辑结构数据的存储结构数据的存储结构第24页,共79页,编辑于2022年,星期一基本术语基本术语n数据:信息的载体,它能够被计算机识别、存储和数据:信息的载体,它能够被计算机识别、存储和加工处理。加工处理。n数据元素:是数据的基本单位。数据元素:是数据的基本单位。n数据项:具有独立意义的最小数据单位,是对数据数据项:具有独立意义的最小数据单位,是对数据元素属性的描述,也称域或字段。元素属性的描述,也称域或字段。n数据对象:指具有相同性质的数据元素的集合,是
18、数数据对象:指具有相同性质的数据元素的集合,是数据的一个子集。据的一个子集。n数据处理:指对数据集合中的各元素,以各种方式进行处数据处理:指对数据集合中的各元素,以各种方式进行处理,包括对数据的插入、删除、查找、更新、排序等基本理,包括对数据的插入、删除、查找、更新、排序等基本运算,也包括对数据元素进行分析。运算,也包括对数据元素进行分析。第25页,共79页,编辑于2022年,星期一数据结构的定义:数据结构的定义:互相有关联的数据元素的集合互相有关联的数据元素的集合一个数据结构应包含两方面信息:一个数据结构应包含两方面信息:1.1.所有数据元素的信息所有数据元素的信息2.2.各数据元素之间的关
19、系各数据元素之间的关系 第26页,共79页,编辑于2022年,星期一数据结构研究的内容数据结构研究的内容1.1.数据集合中,各种数据元素之间所固有的逻辑关系,数据集合中,各种数据元素之间所固有的逻辑关系,即即数据的逻辑结构数据的逻辑结构。2.2.在对数据进行处理时,各数据元素在计算机在对数据进行处理时,各数据元素在计算机中的存储关系,即中的存储关系,即数据的存储结构数据的存储结构。3.3.对各种数据结构进行的运算,其中常用的有对各种数据结构进行的运算,其中常用的有检索、检索、插入、删除、排序插入、删除、排序等。等。第27页,共79页,编辑于2022年,星期一数据的逻辑结构数据的逻辑结构-反映数
20、据元素之间的逻辑关系反映数据元素之间的逻辑关系一个数据结构可以表示为一个二元组:一个数据结构可以表示为一个二元组:B=B=(D D,R R)D D是数据元素的集合,是数据元素的集合,R R是定义在是定义在D D上的二元关系的集合,反映了上的二元关系的集合,反映了D D中各元素中各元素之间的前驱与后继关系之间的前驱与后继关系二个要素二个要素1.1.数据元素的集合数据元素的集合D D2.2.D D上的二元关系上的二元关系R R举例举例第28页,共79页,编辑于2022年,星期一例例1.1.一年四季的数据结构。一年四季的数据结构。表示为:表示为:Season=Season=(D D,R R)D=D=
21、(春,夏,秋,冬)(春,夏,秋,冬)R=R=(春,夏),(夏,秋),(秋,冬)(春,夏),(夏,秋),(秋,冬)例例2.2.n n维向量维向量X=X=(x1x1,x2x2,xnxn)的数据结构。)的数据结构。表示为:表示为:X=X=(D D,R R)D=D=(x1x1,x2 x2,xnxn)R=R=(x1x1,x2x2),(),(x2x2,x3x3),(,(xn-1xn-1,xnxn)例例3.3.家庭成员的数据结构。家庭成员的数据结构。表示为:表示为:Family=Family=(D D,R R)D=D=(父亲,儿子,女儿)(父亲,儿子,女儿)R=R=(父亲,儿子),(父亲,女儿)(父亲,儿子
22、),(父亲,女儿)第29页,共79页,编辑于2022年,星期一根据数据结构中各数据元素之间的根据数据结构中各数据元素之间的前驱前驱与与后继后继关系的复关系的复杂程度,逻辑上可以把数据结构分为杂程度,逻辑上可以把数据结构分为线性结构线性结构和和非非线性结构线性结构。一个非空的线性数据结构应满足两个条件:一个非空的线性数据结构应满足两个条件:有且仅有一个根结点(没有前驱的结点);有且仅有一个根结点(没有前驱的结点);每一个结点最多只有一个前驱,一个后继;每一个结点最多只有一个前驱,一个后继;如果一个数据结构不是线性的,则称为非线性结构(树如果一个数据结构不是线性的,则称为非线性结构(树形结构、图形
23、结构或网状结构)。形结构、图形结构或网状结构)。例例1 1、例、例2 2属于线性结构,例属于线性结构,例3 3为非线性结构。为非线性结构。第30页,共79页,编辑于2022年,星期一n三种基本结构图示三种基本结构图示1.1.线性结构:元素之间是一对一的关系线性结构:元素之间是一对一的关系2.2.树形结构:元素之间是一对多的关系树形结构:元素之间是一对多的关系(非线性非线性)3.3.图形结构或网状结构:元素之间是多对多的关系图形结构或网状结构:元素之间是多对多的关系(非非线性线性)第31页,共79页,编辑于2022年,星期一数据的存储结构:数据的存储结构:即数据的逻辑结构在计算机存即数据的逻辑结
24、构在计算机存储空间中的存放形式储空间中的存放形式常见四种:常见四种:1.1.顺序存储结构顺序存储结构2.2.链式存储结构链式存储结构3.3.索引存储结构索引存储结构4.4.散列存储结构散列存储结构第32页,共79页,编辑于2022年,星期一线性表的基本概念线性表的基本概念线性表的顺序存储及其运算线性表的顺序存储及其运算线性表的链式存储及其运算线性表的链式存储及其运算第33页,共79页,编辑于2022年,星期一线性表的基本概念线性表的基本概念n线性表是由线性表是由n n(n=0)个元素个元素a1a1,a2a2,anan组组成的有限序列,记为:(成的有限序列,记为:(a1a1,a2a2,anan)
25、。)。数据元素(也称为结点)的个数数据元素(也称为结点)的个数 n n 称为线性表称为线性表的长度,的长度,n=0n=0时称此线性表为空表。时称此线性表为空表。n非空线性表(非空线性表(a a1 1,a,a2 2,a,an n)的结构特征:)的结构特征:若线性表非空,第一个元素无前驱;最后一个元素无若线性表非空,第一个元素无前驱;最后一个元素无后继;后继;其他元素仅有一个直接前驱和一个直接后继。其他元素仅有一个直接前驱和一个直接后继。第34页,共79页,编辑于2022年,星期一线性表的顺序存储及其运算线性表的顺序存储及其运算n线性表的顺序存储线性表的顺序存储1.1.所有元素所占的存储空间连续所
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 算法 数据结构 幻灯片
限制150内