第一章数据结构与算法概述.ppt

写在前面的话,本课程学习的是什么？,学习在思考问题时， 不仅按人的逻辑方式思考，也按计算机的逻辑思维方式思考,学习在解决问题时， 不仅考虑人的处理方式，也要考虑计算机的处理方式,为什么要学数据结构？ 数据结构研究什么？ 重新理解算法。 如何分析算法的优劣？,第一章 概论,第一问题： 为什么要学数据结构,Data Structure,？,用计算机处理的实际问题可分为两大类问题： 数值计算 非数值计算 数值计算问题： 在计算机发展初期，人们主要应用计算机来完成科学计算，即处理数值计算问题，对于这类问题，可以通过抽象出合适的数学模型，然后设计一个相应的算法来解决。 在建筑设计时计算梁结构的应力要求解线性方程组 预报人口增长情况时要求解微分方程等。 非数值计算问题： 但是随着计算机应用领域的不断扩大，计算机更多地应用于处理非数值计算问题，这类问题涉及到数据元素间复杂的相互关系，一般无法用数学方程来描述。,现实中对象之间的关系,线性关系：如列车中各车箱之间的关系、排队买车票人之间的关系、一叠盘子中各盘子之间的关系等。 层次关系：如学校的组织结构、人的辈分关系等。 网状关系：如城市铁路交通网、电话网、计算机网络等。,实际问题中对象之间的关系 例1：学生成绩管理,学生成绩表,关系：线性 特征：一个直接前趋， 一个直接后继,实际问题中对象之间的关系,例2：“井字棋”的人机对弈,关系：树型 特征：一个直接前趋， 多个直接后继,实际问题中对象之间的关系,例3：交通图的最短路径问题,A4,A2,A6,A3,A1,A5,5,4,7,9,8,6,1,2,关系：图型 特征：多个直接前趋， 多个直接后继,第一问题： 什么要学数据结构,？,解决非数值问题的首要任务是选取一种合适的数据结构表示该问题，然后才考虑如何编写有效的算法。,计算机处理的大多属于非数值计算问题。,第二问题 数据结构研究什么,？,几个基本概念,1. 数据 2. 数据元素 3. 数据项,所有能被输入到计算机中，且能被计算机处理的符号(数值、字符等)的集合。,1.数据:,2.数据元素:,如果把数据作为一个集合，则集合中的每一个独立“个体”称为数据元素。数据元素是数据结构中讨论的基本单位。,数据集合中的所有数据元素的属性相同。,例如：,描述一个学生信息的数据元素,称之为组合项,原子项,3.数据项,数据元素也可以由若干数据项构成。,数据结构的研究内容,研究数据之间的相互关系，即数据的组织形式，包括： 数据元素之间的逻辑关系，也称为数据的逻辑结构(Logical structure)。 数据元素及其关系在计算机存储器内的表示，称为数据的存储结构(storage structure)。 数据的运算，即基于某种存储结构对数据施加的操作或运算。,4. 数据结构：,带结构的数据元素的集合,对于一个有相同特性的数据元素的集合，如果在数据元素之间存在一种或多种特定的关系，则称为一个数据结构。,指的是数据元素之间存在的关系,不同的“关系”构成不同的“结构”,例如，IP地址（IPv4）是一个用四个 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 a4,111,166,102, 2 a2 a1 a3 a4,又例，在2行3列的二维数组 a1, a2, a3, a4, a5, a6中六个 元素之间存在什么关系？,行的次序关系: 列的次序关系:,row = ,col = ,a1 a3 a5 a2 a4 a6,a1 a2 a3 a4 a5 a6,从关系或结构分，数据结构可归结为以下四类:,线性结构,树形结构,图状结构,集合结构,5.分类,数据结构包括“逻辑结构” 和“物理结构”两个方面(层次):,逻辑结构 是对数据元素之间的逻辑关系的描述。它对应一个数据元素的集合和定义在此集合上的若干关系;,物理结构 是逻辑结构在计算机中的表示和实现，故又称“存储结构” 。,6. 逻辑结构和物理结构,7. 数据结构的存储结构, 逻辑结构在存储器中的映象,“数据元素”的映象,“关系”的映象,所有数据元素都映象为二进制位串,(321)10 = (501)8 = (101000001)2,A = (101)8 = (001000001)2,顺序映象 和链式映象,8. 顺序映象,逻辑上相邻的数据元素存储在物理位置也相邻的存储单元里,例如:令 y 的存储位置和 x 的存储位置之间差一个常量 C,而 C 是一个隐含值，整个存储结构中只含数据元素本身的信息,9. 链式映象,以附加信息(指针)表示后继关系,需要用一个和 x 在一起的附加信息指示 y 的存储位置,y x,为方便起见，数据的逻辑结构简称为数据结构，物理结构称为存储结构,结构,运算,逻辑结构,存储结构,+,数据结构,瑞士计算机科学家沃思(N.Wirth)教授提出：,数据结构在计算机科学中的地位,程序设计的实质是对实际问题选择一种好的数据结构，加之设计一个好的算法，而好的算法在很大程度上取决于描述实际问题的数据结构。 数据结构是计算机软件和计算机应用专业的核心课程之一，由于在计算机系统软件和应用软件中都要用到各种数据结构，要想更有效地使用计算机，就必须学习数据结构的有关知识。,数据结构在软件从业人员的知识与技能结构中的地位,数据结构在软件从业人员的知识与技能结构中的地位,编程语言,解决问题的思想,推荐阅读- 程序员杂志,特别策划算法的力量 李开复.算法的力量 百度首席架构师揭密：算法是百度工程师的利器 影响算法世界的十位大师 特别策划程序员的七种武器 左轻候.最基础的数据结构,任何受过专业训练的程序员，对“数据结构”这门课程中涉及到的各种数据结构都不会陌生，但是在实际的编程工作中，大部分的数据结构都不会用到，而且也永远都不会用到。虽然如此，深入地理解基本数据结构的概念和实现细节，仍然是每个程序员的任务。这不仅仅是因为，掌握这些知识将有利于更加正确和灵活地应用它们，而且也是因为，对于语言背后的实现细节的求知欲是一个优秀程序员的素质。 -摘自最基础的数据结构,关于数据结构中的结构,数据的逻辑结构是从逻辑关系上描述数据，它与数据的存储无关，是独立于计算机的，可以看作是从具体问题抽象出来的数学模型。数据的逻辑结构有两大类： 线性结构：线性表 非线性结构：树和图 数据的存储结构是逻辑结构用计算机语言的实现，它是依赖于计算机语言的。数据的存储结构有以下四种基本的存储方法。 顺序存储方法 链接存储方法 索引存储方法 散列存储方法,关于数据结构中的算法,数据的运算是定义在数据的逻辑结构上的，每种逻辑结构都有一个运算的集合。 最常用的运算有查找、插入、删除、更新、排序等。 重点研究的两类基本算法： 查找 排序,本课程的结构,线性表 栈 队列 串 多维数组 树 图 查找 排序,线性结构,非线性结构,算法,第二问题 数据结构研究什么,？,运算,逻辑结构,存储结构,第三问题 重新理解算法Algorithm,算法和算法的分析,一、算法,二、算法设计的原则,三、算法效率的度量方法和准则,四、算法的存储空间需求,算法是为了解决某类问题而规定的一个有限长的操作序列。一个算法必须满足以下五个重要特性：,1有穷性 2确定性 3可行性 4有输入 5有输出,一、算法,1有穷性 对于任意一组合法输入值，在执行有穷步骤之后一定能结束，即：算法中的每个步骤都能在有限时间内完成；,2确定性 对于每种情况下所应执行的操作，在算法中都有确切的规定，使算法的执行者或阅读者都能明确其含义及如何执行。并且在任何条件下，算法都只有一条执行路径；,3可行性 算法中的所有操作都必须足够基本，都可以通过已经实现的基本操作运算有限次实现之；,4有输入 作为算法加工对象的量值，通常体现为算法中的一组变量。有些输入量需要在算法执行过程中输入，而有的算法表面上可以没有输入，实际上已被嵌入算法之中；,5有输出 它是一组与“输入”与确 定关系的量值，是算法进行信息加工后得到的结果，这种确定关系即为算法的功能。,二、算法设计的原则,设计算法时，通常应考虑达到以下目标：,1正确性,2. 可读性,3健壮性,4高效率与低存储量需求,1正确性,首先，算法应当满足以特定的“规格说明”方式给出的需求。,其次，对算法是否“正确”的理解可以有以下四个层次：,a程序中不含语法错误；,b程序对于几组输入数据能够得出满足要求的结果；,c程序对于精心选择的、典型、苛刻且带有刁难性的几组输入数据能够得出满足要求的结果；,通常以第 c 层意义的正确性作为衡量一个算法是否合格的标准。,d程序对于一切合法的输入数据都能得出满足要求的结果；,2. 可读性,算法主要是为了人的阅读与交流， 其次才是为计算机执行。因此算法应该易于人的理解；另一方面，晦涩难读的程序易于隐藏较多错误而难以调试；,3健壮性,当输入的数据非法时，算法应当恰当地作出反映或进行相应处理，而不是产生莫名奇妙的输出结果。并且，处理出错的方法不应是中断程序的执行，而应是返回一个表示错误或错误性质的值，以便在更高的抽象层次上进行处理。,4高效率与低存储量需求,通常，效率指的是算法执行时间；存储量指的是算法执行过程中所需的最大存储空间。两者都与问题的规模有关。在有些情况下，两者相互矛盾,算法,=,程序,？,算法是为了描述解决某一问题的方法，而不涉及具体的实现细节。,算法存在的辨证关系 数据结构与算法的辨证关系,给定了数据的逻辑结构后，对同一逻辑结构而言，由于存储结构的不同，定义的运算也是不同的。 如线性表是一种逻辑结构，若采用顺序存储方法表示，则称为顺序表；若采用链式存储方法表示，则称为链表。 相同的运算在顺序表和链表上的实现方法是不同的。,第四问题 如何分析算法的优劣？,两个指标： 时间复杂度 空间复杂度,三、算法的评价,通常有两种衡量算法效率的方法:,事后统计法,事前分析估算法,缺点：1、必须执行程序 2、其它因素掩盖算法本质,算法执行时间相关的因素：,1算法选用的策略,2问题的规模,3编写程序的语言,4编译程序产生的机器代码的质量,5计算机执行指令的速度,算法（程序）= 控制结构 + 原操作 （固有数据类型的操作）,算法的执行时间 = 原操作(i)的执行次数×原操作(i)的执行时间,算法的执行时间 与 原操作执行次数之和 成正比,算法的执行时间分析：,例 一 两 个 矩 阵 相 乘,void mult(int a, int b, int /for /mult,原操作执行次数之和： 2n3 3n2 2n1,n+1,n(n+1),n2,n2 (n+1),n3,时间复杂度的渐进表示法,算法中所有语句的次数（频度）之和是矩阵阶数n的函数 f(n) = 2n3 + 3n2 + 2n +1 一般地，称n是问题的规模。执行次数f(n)是关于n的多项式函数,f(n)与执行时间成正比。 当n趋于无穷大时，把执行次数函数f(n)的数量级（阶）称为算法的渐进时间复杂度 T(n) = O(f(n) -大O表示渐进 T(n) = O(n3),随着问题规模 n 的增长，算法执行时间的增长率和 f(n) 的增长率相同，,void select_sort(int& a , int n) / 将 a 中整数序列重新排列成自小至大有序的整数序列。 / select_sort,for ( i = 0; i n; +i ) if ( j != i ) aj ai ,例 二 选 择 排 序,时间复杂度: O(n2),j = i; / 选择第 i 个最小元素 for ( k = i+1; k n; +k ) if (ak aj ) j = k;,n+1,n,n(n-1)/2,n,n(n+1)/2,X1 ；y1； For（k1，k=n，k） Xx1； L1 For（i1；i=n，i） For （j1；j=n，j） y=y+1； L2 F（L1）n；F（L2）n2； T（n）0(n2) 可见，当有多个串行的循环语句时，算法的时间复杂度由嵌套层次最多的循环语句中最里层语句的频度决定。,有时, 算法的时间复杂度不仅依赖于问题规模n，还与输入实例的初始状态有关。 例：在数组 An 中查找给定值 k 的算法： int i = n; while ( i = 1 ,最坏的执行次数： f(n) = n,平均时间复杂度(等概率)： T(n) = O(n),平均执行次数(等概率): f(n)= (n+1)/2,例：设有两个算法在同一机器上运行，其执行时 间分别为 100n2 和 2n. 问：要使前者快于后者，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 n!,四、算法的存储空间需求,算法的空间复杂度定义为:,表示随着问题规模 n 的增大， 算法运行所需存储量的增长率 与 g(n) 的增长率相同。,S(n) = O(g(n),int i = n; while ( i = 1 ,只用i,k两个辅助空间，因为和问题的尺寸n无关，故空间复杂度s（n）O（1）。,T（n）与s（n）是一对矛盾，要想空间比较节约，往往时间消耗就大；反之，时间开销小，常常得以空间资源的消耗来换取。也有以时时空复杂度为T（n）×s（n）为衡量算法的标准。我们着重考虑时间效率，而假设内存足够大。,2.1.3 算法描述,1、数据结构表示 数据存储结构均用类型定义（typedef）的方式描述 2、实现算法 用函数描述 函数类型 函数名（函数参数表） 内部数据说明； 语句序列； ,指针*：存放对象的存储地址 int i = 5; int *p; p = ,引用,3、函数难点回顾,函数调用时的参数传递,值传递 把实参的值传给被调用函数的副本中。被调用函数修改的是副本的值，实参不变。,引用传递 & : 被传递的不是实参的值，而是实参的地址。被调用函数通过地址存取被引用的实参，函数执行后实参的值将发生改变。,int a=1;b=2; swap(a,b);,void swap(int ,Assign( &Z, v1, v2 ),1. 熟悉各名词、术语的含义，掌握基本概念。,2. 理解算法五个要素的确切含义。,本节学习要点,3. 掌握计算语句频度和估算算法时间复杂度的方法。,本节作业,补充： 1、简述下列概念：数据、逻辑结构、存储结构、线性结构。 2、设n为正整数，利用大“O”记号，将下列程序段的执行时间表示为n的函数。,(1) i=1; k=0 while(in) k=k+10*i;i+;,(2) i=0; k=0; do k=k+10*i; i+; while(in);,(3) x=91; y=100; while(y0) if(x100) x=x-10;y-; else x+;,