数据结构与算法概述幻灯片.ppt

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

1、数据结构与算法概述第1页，共63页，编辑于2022年，星期六为什么要学数据结构？数据结构研究什么？重新理解算法。如何分析算法的优劣？第一章第一章 概论概论第2页，共63页，编辑于2022年，星期六第一问题：为什么要学数据结构Data Structure？第3页，共63页，编辑于2022年，星期六n用计算机处理的实际问题可分为两大类问题：数值计算非数值计算n数值计算问题数值计算问题：在计算机发展初期，人们主要应用计算机来完成科学计算，即处理数值计算问题，对于这类问题，可以通过抽象出合适的数学模型，然后设计一个相应的算法来解决。在建筑设计时计算梁结构的应力要求解线性方程组预报人口增长情况时要求解微

2、分方程等。n非数值计算问题非数值计算问题：但是随着计算机应用领域的不断扩大，计算机更多地应用于处理非数值计算问题，这类问题涉及到数据元素间复杂的相互关系，一般无法用数学方程来描述。第4页，共63页，编辑于2022年，星期六现实中对象之间的关系关系n线性关系线性关系：如列车中各车箱之间的关系、排队买车票人之间的关系、一叠盘子中各盘子之间的关系等。n层次关系层次关系：如学校的组织结构、人的辈分关系等。n网状关系网状关系：如城市铁路交通网、电话网、计算机网络等。第5页，共63页，编辑于2022年，星期六实际问题中对象之间的关系例1：学生成绩管理学号姓名大学英语C语言数据结构A07001王萍90859

3、5A07002马玲808590A07003张兰959199A07004李建708486A07005黄勇827678:：A07001王萍908595学生成绩表A07002马玲808590A07003张兰959199A07004李建708486A07005黄勇827678n关系：线性线性n特征：一个直接前趋，一个直接后继第6页，共63页，编辑于2022年，星期六实际问题中对象之间的关系n例2：“井字棋”的人机对弈 OO OOO O OO O OO OO O O OO O OO OO O OO O OO O关系：树型树型特征：一个直接前趋，多个直接后继第7页，共63页，编辑于2022年，星期六实际问

4、题中对象之间的关系n例3：交通图的最短路径问题 A4A2A6A3A1A554798612关系：图型图型特征：多个直接前趋，多个直接后继第8页，共63页，编辑于2022年，星期六第一问题：什么要学数据结构？解决非数值问题的首要任务是选取一种合适的数据结构表示该问题，然后才考虑如何编写有效的算法。计算机处理的大多属于非数值计算问题。第9页，共63页，编辑于2022年，星期六第二问题数据结构研究什么？第10页，共63页，编辑于2022年，星期六几个基本概念几个基本概念1.1.数据数据2.2.数据元素数据元素3.3.数据项数据项第11页，共63页，编辑于2022年，星期六 所有能被输入被输入到计算机中

5、，且能被计算机处处理的符号理的符号(数值、字符等数值、字符等)的集合集合。1.1.数据数据:2.2.数据元素数据元素:如果把数据作为一个集合，则集合中的每一个独立“个体个体”称为数据元素。数据元素是数据结构中讨论的基本单位。基本单位。数据集合中的所有数据元素的属性相同。第12页，共63页，编辑于2022年，星期六例如：描述一个学生信息的数据元素称之为组合项称之为组合项年 月 日姓 名学 号班 号性别出生日期入学成绩原子项原子项3.3.数据项数据项数据元素也可以由若干数据元素也可以由若干数据项数据项构成。构成。第13页，共63页，编辑于2022年，星期六数据结构的研究内容数据结构的研究内容n研究

6、数据之间的相互关系，即数据的组织形式，包括：数据元素之间的逻辑关系，也称为数据的逻辑结构(Logical structure)。数据元素及其关系在计算机存储器内的表示，称为数据的存储结构(storage structure)。n数据的运算，即基于某种存储结构对数据施加的操作或运算。第14页，共63页，编辑于2022年，星期六4.4.数据数据结构结构：带结构结构的数据元素的集合对于一个有相同特性的数据元素的集合，如果在数据元素之间存在一种或多种特定的关系，则称为一个数据结构。指的是数据元素之间存在的关系不同的“关系关系”构成不同的“结构结构”第15页，共63页，编辑于2022年，星期六例如，例如

7、，IPIP地址（地址（IPv4IPv4）是一个用四个）是一个用四个 3 位的十位的十进制数表示一个数据结构。进制数表示一个数据结构。166,111,102,2 a1(166),a2(111),a3(102),a4(2)则在数据元素 a1、a2、a3 和a4之间存在着“次次序序”关系关系 a1,a2、a2,a3、a3,a4 166,111,102,2 a1 a2 a3 a4111,166,102,2 a2 a1 a3 a4第16页，共63页，编辑于2022年，星期六又例，在2行3列的二维数组a1,a2,a3,a4,a5,a6中六个元素之间存在什么关系？行的次序关系行的次序关系:列的次序关系列的次

8、序关系:row=,col=,a1 a3 a5 a2 a4 a6 a1 a2 a3a4 a5 a6 a1 a2 a3 a4 a5 a6第17页，共63页，编辑于2022年，星期六从关系关系或结构结构分，数据结构，数据结构可归结为以下四类四类:线性线性结构树形树形结构图状图状结构集合集合结构5.5.分类分类第18页，共63页，编辑于2022年，星期六数据结构包括“逻辑结构逻辑结构”和“物理结构物理结构”两个方面(层次):逻辑结构逻辑结构 是对数据元素之间的逻辑关系的描述。它对应一个数据元素的集合和定义在此集合上的若干关系;物理结构物理结构 是逻辑结构在计算机中的表示和实现，故又称“存储结构存储结构

9、”。6.6.逻辑结构和物理结构逻辑结构和物理结构第19页，共63页，编辑于2022年，星期六7.7.数据结构的数据结构的存储结构存储结构 逻辑结构在存储器中的映象逻辑结构在存储器中的映象“数据元素数据元素”的映象的映象 “关系关系”的映象的映象 所有数据元素都映象为二进制位串所有数据元素都映象为二进制位串(321)10 =(501)8 =(101000001)2 A =(101)8 =(001000001)2顺序映象顺序映象 和链式映象和链式映象第20页，共63页，编辑于2022年，星期六8.8.顺序映象顺序映象 逻辑上相邻的数据元素存储在物理位逻辑上相邻的数据元素存储在物理位置也相邻的存储单

10、元里置也相邻的存储单元里例如例如:令 y 的存储位置和 x 的存储位置之间差一个常量 C而 C 是一个隐含值，整个存储结构中只含整个存储结构中只含数据元素本身的信息数据元素本身的信息 x y第21页，共63页，编辑于2022年，星期六9.9.链式映象链式映象以附加信息以附加信息(指针指针)表示后继关系表示后继关系需要用一个和 x 在一起的附加信息附加信息指示 y 的存储位置y x第22页，共63页，编辑于2022年，星期六为方便起见，数据的逻辑结构简称为数据结构，物理结构称为存储结构第23页，共63页，编辑于2022年，星期六结构运算逻辑结构存储结构+数据结构数据结构算法+程序瑞士计算机科学家

11、沃思(N.Wirth)教授提出：数据结构在计算机科学中的地位 程序设计的实质是对实际问题选择一种好的数据结构，加之设计一个好的算法，而好的算法在很大程度上取决于描述实际问题的数据结构。数据结构是计算机软件和计算机应用专业的核心课程之一，由于在计算机系统软件和应用软件中都要用到各种数据结构，要想更有效地使用计算机，就必须学习数据结构的有关知识。第24页，共63页，编辑于2022年，星期六数据结构在软件从业人员的知识与技能结构中的地位 第25页，共63页，编辑于2022年，星期六数据结构在软件从业人员的知识与技能结构中的地位 编程语言解决问题的思想第26页，共63页，编辑于2022年，星期六推荐阅

12、读-程序员杂志n特别策划特别策划算法的力量算法的力量李开复.算法的力量百度首席架构师揭密：算法是百度工程师的利器影响算法世界的十位大师n特别策划特别策划程序员的七种武器程序员的七种武器左轻候左轻候.最基础的数据结构最基础的数据结构第27页，共63页，编辑于2022年，星期六 任何受过专业训练的程序员，对“数据结构”这门课程中涉及到的各种数据结构都不会陌生，但是在实际的编程工作中，大部分的数据结构都不会用到，而且也永远都不会用到。虽然如此，深入地理解基本数据结构的概念和实现细节，仍然是每个程序员的任务。这不仅仅是因为，掌握这些知识将有利于更加正确和灵活地应用它们，而且也是因为，对于语言背后的实现

13、细节的求知欲是一个优秀程序员的素质。-摘自最基础的数据结构第28页，共63页，编辑于2022年，星期六关于数据结构中的结构n数据的逻辑结构是从逻辑关系上描述数据，它与数据的存储无关，是独立于计算机的，可以看作是从具体问题抽象出来的数学模型。数据的逻辑结构有两大类：线性结构：线性表非线性结构：树和图n数据的存储结构是逻辑结构用计算机语言的实现，它是依赖于计算机语言的。数据的存储结构有以下四种基本的存储方法。顺序存储方法 链接存储方法索引存储方法 散列存储方法第29页，共63页，编辑于2022年，星期六关于数据结构中的算法 n数据的运算是定义在数据的逻辑结构上的，每种逻辑结构都有一个运算的集合。最

14、常用的运算有查找、插入、删除、更新、排序等。n重点研究的两类基本算法：查找排序第30页，共63页，编辑于2022年，星期六本课程的结构n线性表n栈n队列n串n多维数组n树n图n查找n排序线性结构非线性结构算法第31页，共63页，编辑于2022年，星期六第二问题数据结构研究什么？运算逻辑结构存储结构第32页，共63页，编辑于2022年，星期六第三问题重新理解算法Algorithm第33页，共63页，编辑于2022年，星期六算法和算法的分析算法和算法的分析一、算法一、算法二、算法设计的原则二、算法设计的原则三、算法效率的度量方法和准则三、算法效率的度量方法和准则四、算法的存储空间需求四、算法的存储

15、空间需求第34页，共63页，编辑于2022年，星期六 算法算法是为了解决某类问题而规定的一个有限长的操作序列操作序列。一个算法必须满足以下五五个重要特性特性：1 1有穷性有穷性 2 2确定性确定性 3 3可行性可行性4 4有输入有输入 5 5有输出有输出一、算法一、算法第35页，共63页，编辑于2022年，星期六1 1有穷性有穷性 对于任意一组合法输入值，在执行有穷步骤有穷步骤之后一定能结束，即：算法中的每个步骤都能在有限时间有限时间内完成；2 2确定性确定性 对于每种情况每种情况下所应执行的操作，在算法中都有确切确切的规定，使算法的执行者或阅读者都能明确其含义及如何执行。并且并且在在任何条件

16、下，算法都只有一条执行路径；任何条件下，算法都只有一条执行路径；第36页，共63页，编辑于2022年，星期六3 3可行性可行性 算法中的所有操作都必须足够基本，都可以通过已经实现的基本操作运算有限次实现之；4 4有输入有输入 作为算法加工对象的量值，通常体现为算法中的一组变量。有些输入量需要在算法执行过程中输入，而有的算法表面上可以没有输入，实际上已被嵌入算法之中；第37页，共63页，编辑于2022年，星期六 5 5有输出有输出 它是一组与“输入”与确定关系的量值，是算法进行信息加工后得到的结果，这种确定关系即为算法的功能。第38页，共63页，编辑于2022年，星期六二、算法设计的原则二、算法

17、设计的原则设计算法时，通常应考虑达到以下目标：1正确性正确性2.可读性可读性3健壮性健壮性4高效率与低存储量需求高效率与低存储量需求第39页，共63页，编辑于2022年，星期六1 1正确性正确性 首先，首先，算法应当满足满足以特定的“规格说规格说明明”方式给出的需求需求。其次，其次，对算法是否“正确正确”的的理解可以有以下四个层次四个层次：a a程序中不含语法错误；b b程序对于几组输入数据能够得出满足要求的结果；第40页，共63页，编辑于2022年，星期六 c c程序对于精心选择的、典型、苛刻且带程序对于精心选择的、典型、苛刻且带有刁难性的几组输入数据能够得出满足要求有刁难性的几组输入数据能

18、够得出满足要求的结果；的结果；通常以第 c c 层意义的正确性作为衡量一个算法是否合格的标准。d d程序对于一切合法的输入数据都能得出满足要求的结果；第41页，共63页，编辑于2022年，星期六2.可读性可读性 算法主要是为了人的阅读与交流阅读与交流，其次才是为计算机执行。因此算法应该易于易于人的理解理解；另一方面，晦涩难读的程序易于隐藏较多错误而难以调试；第42页，共63页，编辑于2022年，星期六3健壮性健壮性 当输入的数据非法非法时，算法应当恰当地作出反映或进行相应处理进行相应处理，而不是产生莫名奇妙的输出结果。并且，处理出错的方处理出错的方法法不应是中断程序的执行，而应是返回返回一个表

19、示错误或错误性质的值表示错误或错误性质的值，以便在更高的抽象层次上进行处理。第43页，共63页，编辑于2022年，星期六4高效率与低存储量需求高效率与低存储量需求 通常，效率指的是通常，效率指的是算法执行时算法执行时间间；存储量指的是算法执行过程中；存储量指的是算法执行过程中所需的最大存储空间所需的最大存储空间。两者都与问。两者都与问题的规模有关。在有些情况下，两题的规模有关。在有些情况下，两者相互矛盾者相互矛盾第44页，共63页，编辑于2022年，星期六算法=程序？算法是为了描述解决某一问题的方法，而不涉及具体的实现细节。第45页，共63页，编辑于2022年，星期六算法存在的辨证关系数据结构

20、与算法的辨证关系n给定了数据的逻辑结构后，对同一逻辑结构而言，由于存储结构的不同，定义的运算也是不同的。如线性表是一种逻辑结构，若采用顺序存储方法表示，则称为顺序表；若采用链式存储方法表示，则称为链表。相同的运算在顺序表和链表上的实现方法是不同的。第46页，共63页，编辑于2022年，星期六第四问题第四问题如何分析算法的优劣？如何分析算法的优劣？两个指标：时间复杂度 空间复杂度第47页，共63页，编辑于2022年，星期六三、算法的评价三、算法的评价通常有两种两种衡量算法效率的方法:事后统计法事后统计法事前分析估算法事前分析估算法缺点：缺点：1、必须执行程序 2、其它因素掩盖算法本质第48页，共

21、63页，编辑于2022年，星期六算法执行时间时间相关的因素因素：1 1算法算法选用的策略的策略2 2问题的规模问题的规模3 3编写程序的语言语言4 4编译编译程序产生的机器代码的质量的质量5 5计算机计算机执行指令的速度的速度第49页，共63页，编辑于2022年，星期六算法（程序）算法（程序）=控制结构控制结构 +原操作原操作 （固有数据类型的操作）算法的执行时间算法的执行时间=原操作原操作(i)(i)的的执行次数执行次数原操作原操作(i)(i)的执行时间的执行时间 算法的执行时间算法的执行时间 与与 原操作执行次数之和原操作执行次数之和 成正比成正比 算法的执行时间分析：算法的执行时间分析：

22、第50页，共63页，编辑于2022年，星期六例例一一两两个个矩矩阵阵相相乘乘void mult(int a,int b,int&c)/以二维数组存储矩阵元素，c 为 a 和 b 的乘积 for(i=1;i=n;+i)for(j=1;j=n;+j)ci,j=0;for(k=1;k=n;+k)ci,j+=ai,k*bk,j;/for/mult原操作执行次数之和：原操作执行次数之和：2 2n3 3n2 2n1 n+1n(n+1)n2 n2(n+1)n3 第51页，共63页，编辑于2022年，星期六时间复杂度的渐进表示法时间复杂度的渐进表示法n算法中所有语句的次数（频度）之和是算法中所有语句的次数（频

23、度）之和是矩阵阶矩阵阶数数n n的函数的函数 f(n)=f(n)=2n2n3 3+3n+3n2 2+2n+1+2n+1n一般地，称一般地，称n n是问题的规模。执行次数是问题的规模。执行次数f(n)f(n)是是关于关于n n的多项式函数的多项式函数,f(n),f(n)与执行时间成正比。与执行时间成正比。n当当n n趋于无穷大时，把执行次数函数趋于无穷大时，把执行次数函数f(n)f(n)的数的数量级（阶）称为算法的渐进时间复杂度量级（阶）称为算法的渐进时间复杂度 T(n)=O(f(n)-T(n)=O(f(n)-大大O O表示表示渐进渐进T(n)=O(nT(n)=O(n3 3)随着问题规模随着问题

24、规模 n n 的增长，算法执行时间的的增长，算法执行时间的增长增长率率和和 f(n)f(n)的的增长率增长率相同，相同，第52页，共63页，编辑于2022年，星期六 void select_sort(int&a,int n)/将将 a 中整数序列重新排列成自小至大有序的整数序列中整数序列重新排列成自小至大有序的整数序列。/select_sortfor(i=0;i n;+i)if(j!=i)aj ai例例二二选选择择排排序序时间复杂度:O(nO(n2 2)j=i;/选择第选择第 i i 个最小元素个最小元素for(k=i+1;k n;+k)if(ak aj)j=k;n+1 nn(n-1)/2 n

25、n(n+1)/2第53页，共63页，编辑于2022年，星期六X1；y1；For（k1，k=n，k）Xx1；L1 For（i1；i=n，i）For（j1；j=1&Ai!=k)i-;return return i;最坏的执行次数：最坏的执行次数：f(n)=nf(n)=n平均时间复杂度平均时间复杂度(等概率等概率)：T(n)=O(n)平均执行次数平均执行次数(等概率等概率):):f(n)=f(n)=(n+1)/2 第55页，共63页，编辑于2022年，星期六例：设有两个算法在同一机器上运行，其执行时例：设有两个算法在同一机器上运行，其执行时 间分间分别为别为 100n2 和和 2n.问：要使前者快于

26、后者，问：要使前者快于后者，n 至少要取多大？至少要取多大？解答：解答：问题是找出满足问题是找出满足 100n2 2n=8192 n=14时，时，100n2=19600 2n=16384 n=15时，时，100n2=22500 2n=32764 取取 n=15 满足要求。满足要求。各种函数的增长趋势各种函数的增长趋势 c log2n n nlog2n n2 n3 2n 3n=1&Ai!=k)i-;return return i;只用i,k两个辅助空间，因为和问题的尺寸n无关，故空间复杂度s（n）O（1）。T T（n n）与）与s s（n n）是一对矛盾，要想空间比较节约，往往）是一对矛盾，要想

27、空间比较节约，往往时间消耗就大；反之，时间开销小，常常得以空间资源时间消耗就大；反之，时间开销小，常常得以空间资源的消耗来换取。也有以时时空复杂度为的消耗来换取。也有以时时空复杂度为T T（n n）ss（n n）为衡量算法的标准。我们着重考虑时间效率，而假设为衡量算法的标准。我们着重考虑时间效率，而假设内存足够内存足够大。大。第58页，共63页，编辑于2022年，星期六2.1.3 2.1.3 算法描述算法描述1 1、数据结构表示、数据结构表示数据存储结构均用类型定义（typedeftypedef）的方式描述2 2、实现算法、实现算法用函数描述函数类型 函数名（函数参数表）内部数据说明；语句序列

28、；第59页，共63页，编辑于2022年，星期六指针指针*：存放对象的存储地址存放对象的存储地址int i=5;int i=5;int*p;int*p;p=p=&i;i;int k=*p;int k=*p;引用引用&：给对象提供一个替代的名字给对象提供一个替代的名字int i=5;int i=5;int int&j=i;j=i;i=7;i=7;int k=j;int k=j;3 3、函数难点回顾、函数难点回顾第60页，共63页，编辑于2022年，星期六函数调用时的参数传递函数调用时的参数传递值传递值传递把实参的值传给被调用函数的副本中。被调用把实参的值传给被调用函数的副本中。被调用函数修改的是副

29、本的值，实参不变。函数修改的是副本的值，实参不变。引用传递引用传递&:&:被传递的不是实参的值，而是实参的地址。被调被传递的不是实参的值，而是实参的地址。被调用函数通过地址存取被引用的实参，函数执行后实参用函数通过地址存取被引用的实参，函数执行后实参的值将发生改变。的值将发生改变。int a=1;b=2;int a=1;b=2;swap(a,b);swap(a,b);void swap(int&i,int&j)void swap(int&i,int&j)int t=j;int t=j;j=i;j=i;i=t;i=t;Assign(&Z,v1,v2)第61页，共63页，编辑于2022年，星期六1.熟悉各名词、术语的含义，掌握基本概念。2.理解算法五个要素的确切含义。本节学习要点本节学习要点3.掌握计算语句频度和估算算法时间复杂度的方法。第62页，共63页，编辑于2022年，星期六本节作业本节作业补充：补充：1、简述下列概念：数据、逻辑结构、存储结构、线性结构。2、设n为正整数，利用大“O”记号，将下列程序段的执行时间表示为n的函数。(1)i=1;k=0 while(in)k=k+10*i;i+;(2)i=0;k=0;dok=k+10*i;i+;while(i0)if(x100)x=x-10;y-;else x+;第63页，共63页，编辑于2022年，星期六