DS数据结构概述

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,软件学院 李媛媛,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,DS数据结构概述,本章重点难点,重点:,数据构造的逻辑构造、存储构造以与根本操作的概念与相互关系；,抽象数据类型(ADT)的概念和实现方法，算法的时间复杂性和空间复杂性分析。,难点:,抽象数据类型(ADT)的概念和实现方法；,算法的时间复杂性和空间复杂性分析。,2,1.1 为什么要学习数据构造,算法+数据构造 = 程序设计,处理问题的策略,给出问题的数学模型,编制出用计算机,处理问题的指令,问题,构建数学模型,算法实现,3,计算机的开展,数据处理的种类,数据,数值数据,非数值数据,数,(,整数,实数,),字符 字符串 文字 图形 图象 声音,对客观对象的符号表示,程序,原始数据,结果数据,软件 硬件 应用领域,4,学习数据构造的原因：, 计算机处理的数据量越来越大。, 数据类型越来越多。, 数据的构造越来越复杂。,数据构造是一门研究“非数值计算程序设计问题中计算机的操作对象以与它们之间的关系和操作的学科。,1.1 为什么要学习数据构造,5,数据如下：,结论,1,：杂乱无章的数据不能表达和交流。,例,1,1985782335902261011,工号：1985070016,号码：,：233000,身份证号码：3461011,6,例,2,号码簿a1,b1 a2,b2 an,bn ,其中，ai为某人姓名，bi为该人的 号码。,结论,2,：数据之间是有联系的。,7,例,3,家族的族谱: 假设某家族有10个成员A, B,C,D,E,F,G,H,I,J，他们之间的血缘关系可以用如以下图表示。,J,I,A,C,B,D,H,G,F,E,结论3：数据之间是有构造的。,8,学号 姓名 性别 出生日期 入学成绩 所在班级,00201,杨润生 男,82/06/01 561 00,计算机,200102,石磊 男,83/12/21 512 00,计算机,100202,李梅 女,83/02/23 532 00,计算机,2,00301,马耀先 男,82/07/12 509 00,计算机,3,某级学生情况,要求分班按入学成绩排列顺序。,说明：在此类文档管理中,可以有查找、修改、插入、删除等操作。,例,4,结论4：在某种数据构造上可以定义一组运算。,9,1.2 数据构造的有关概念和术语,1、数据：对客观事物的符号表示，信息的载体，能被计算机识别、存储和加工处理。如整数，实数，字符串、图象、声音等都是数据。,2、数据元素：数据的根本单位，又可称为元素、结点、顶点、记录等。,3、数据项: 是数据不可分割的最小单位。如学号、姓名等。,一个数据元素可以由假设干个数据项构成。,4、数据对象：性质一样的数据元素的集合。如所有班名一样的记录集合。,5、数据类型：是指一个类型和定义在这个类型上的操作集合。,分为：原子类型和构造类型,6、抽象数据类型：是指一个逻辑概念上的类型和这个类型上的操作集合。优点：将数据和操作封装在一起实现了信息隐藏。,10,抽象数据类型的定义可以由元素、元素之间的关系与操作三局部构成。,抽象数据类型的定义格式,ADT 抽象数据类型名,数据对象：,数据关系：,根本操作：,ADT 抽象数据类型名,例如：P4 例1-4,1.2 数据构造的有关概念和术语,11,1.2 数据构造的有关概念和术语,数据构造：相互之间存在一种或多种特定关系的数据元素的集合。,形式定义为：,Data_Structure(D, R),例如：P5 例1-5,12,数据构造包括以下内容：,1数据的逻辑构造。从逻辑关系上描述数据，与数据存储无关，独立于计算机。它包括以下四类根本构造：,集合：同属一个集合,线性构造：一对一,树形构造：一对多,图状构造或网状构造：多对多,1.2 数据构造的有关概念和术语,13,数据构造类型,树,图,线性表,栈,队列,串,数组,广义表,数据结构,线性结构,非线性结构,14,2数据的物理构造，数据构造在计算机存储器中的表示，又称存储构造。它包括：,顺序存储构造：借助数据元素在存储器中相对位置表示逻辑关系,链式存储构造：依靠数据元素中的指针表示元素之间的逻辑关系,索引,散列,1.2 数据构造的有关概念和术语,15,对每种数据构造，主要讨论如下三方面的问题：,数据的逻辑构造,数据元素之间的逻辑关系，是具体关系的抽象。,数据的存储构造(物理构造)：,数据元素与其关系在计算机内存中的表示；,数据的运算或算法,即对数据施加的操作。定义在数据的逻辑构造上的抽象的操作。,16,1.3,算法和算法描述,1,、算法,算法是对特定问题求解步骤的一种描述，是指令的集合。,算法的特性：,有穷性、确定性、可行性、输入、输出,17,算法的根本特征,有穷性：算法中的操作步骤为有限个，且每个步骤都能在有限时间内完成。,确定性：组成算法的操作必须清晰无二义性。,可行性：算法中的所有操作都必须足够根本，都可以通过已经实现的根本操作运算有限次实现之。,输入：作为算法加工对象的量值，通常表达为算法中的一组变量。些算法的字面上可以没有输入，实际上已被嵌入算法之中。,输出：它是一组与输入有确定关系的量值，是算法进展信息加工后得到的结果，这种确定关系即为算法的功能。,18,2、算法设计的要求,正确性,可读性,强健性,高效性,1.3,算法和算法描述,19,算法必须是“正确的,所谓算法是正确的，除了应该满足算法说明中写明的“功能之外，应对各组典型的带有苛刻条件的输入数据得出正确的结果。,在算法是正确的前提下，算法的可读性是摆在第一位的，这在当今大型软件需要多人合作完成的环境下是换重要的，另一方面，晦涩难读的程序易于隐藏错误而难以调试。,应有很好的“可读性,一个算法应当思路清晰、层次清楚、简单明了、易读易懂。,算法的设计要求,20,必须具有“强健性,算法的强健性指的是，算法应对非法输入的数据作出恰当反映或进展相应处理，一般情况下，应向调用它的函数返回一个表示错误或错误性质的值。,算法的效率,应考虑所设计的算法具有“高效率与低存储量。高效率与低存储量是矛盾的，要视具体问题而定。,算法的设计要求,21,算法描述：,1.文字形式 :用中文或英文这样的文字来描述算法。,2.伪码形式 :用一种仿程序设计语言的语言来描述算法。比方类C语言。,3.程序设计语言形式 :用某种程序设计语言描述算法。其优点是算法不用修改，直接作为程序语句键入计算机，计算机能调用和运行。,1.3,算法和算法描述,22,算法描述：,类C语言,比,程序设计语言,更容易描述和被理解，比文字描述的自然语言更接近程序设计语言，容易转换成高级语言。,例如：P7 例1-6,1.3,算法和算法描述,23,1.,算法是对特定问题求解步骤的一种描述，是指令的集合。一个问题可以有多种算法。,2.,程序是用某种程序设计语言对算法的具体实现。,软件开发生命周期：,需求分析概要设计,算法,设计,程序编码,运行维护,算法和程序的区别,24,1.,程序可以是无穷的，例如：,OS,；,算法必须是有穷的。,2.,程序可以是错误的，算法必须是正确的。,3.,程序是用程序设计语言描述，在机器上可以运行；算法也可以用框图，自然语言等方式描述。,算法和程序的区别,25,1.4,算法时空效率分析方法,算法分析就是对算法质量优劣的评价，通常分为,事后统计,和,事前分析,两种方法。,算法分析应从两个角度：,依据算法编写的程序在计算机中运行时间的多少的度量，即,时间复杂度,。,依据算法编写的程序在计算机中占存储空间的多少的度量，即,空间复杂度,。,注：,时间复杂度和空间复杂度合称算法的,复杂度,。,26,1.4,算法时空效率分析方法,程序运行所需要的时间取决于以下因素：,(1)机器执行指令的速度,(2)书写算法的程序设计语言,(3)编译产生的机器语言代码质量,(4),算法所选用的策略,(,5,),问题的规模,，即算法的时间效率与算法所处理的数据个数n的函数关系。,27,算法的时间复杂度,是算法执行的时间消耗，是求解问题规模n的函数。记为：T(n)=O(f(n)。,(1)时间复杂度的计算方法频度统计法,例1：语句 x=x+1;执行频度为1，时间复杂度记为： T(n)=O(1),1.4,算法时空效率分析方法,28,(1)时间复杂度的计算方法频度统计法,例2： for(i=1; i=n; i+),x=x+1;,算法的频度=n+1,那么算法的时间复杂度为O(n),1.4,算法时空效率分析方法,29,(1)时间复杂度的计算方法频度统计法,例3： for(i=1; i=n; +i),for(j=1; j=n; +j),x=x+1;,算法的频度=n(n+1),那么算法的时间复杂度为O(n2),1.4,算法时空效率分析方法,30,(1)时间复杂度的计算方法频度统计法,例4： for(i=1; i=n; +i),for(j=1; j=n; +j) ,cij = 0;,for(k=1; k=n; +k),cij += aik * bkj;,算法的频度=n+1 + n(n+1) + n2 + n2(n+1) + n3,= 2n3 + 3n2 + 2n + 1,那么算法的时间复杂度为O(n3),1.4,算法时空效率分析方法,31,(2)有的情况下，算法中根本操作重复执行的次数还随问题的输入数据集不同而不同。此时，一种方法是讨论平均时间复杂度，一种方法是讨论最坏的情况下的时间复杂度。,(3)常见的时间复杂度按数量级递增排列依次为：,常数阶O(1)对数阶O(log2n)线性阶O(n)线性对数阶O(nlog2n)平方阶O(n2)立方阶O(n3)k次方阶O(nk)指数阶O(2n)。,1.4,算法时空效率分析方法,32,讨论：,“不必最求高效算法，低效算法可以在高速计算机上得到补偿。这一说法正确吗？,1.4,算法时空效率分析方法,33,设,A1,A2,A3,是求解同一问题的不同算法，其时间复杂度分别是：,O(n),O(nlgn), O(N!),。,C1,和,C2,为计算机，且,C2,的计算速度是,C1,的,10,倍。,复杂度,C1,可解规模,C2,可解规模 可解规模的关系,O(n) N11 N21 N21=10N11,O(nlgn) N12 N22 N22=10N12,O(N!) N13 N23 N23=N13+,小常数,1.4,算法时空效率分析方法,结论：“不必最求高效算法，低效算法可以在高速计算机上得到补偿。这一说法是错误的!,34,2.算法的空间复杂度,是算法的空间消耗，也是求解问题规模n的函数。记为：S(n)=O(f(n)。,算法执行期间所需要的存储量包括：,输入数据所占空间固定，与算法无关,程序本身所占空间固定，与算法无关,辅助变量所占空间,1.4,算法时空效率分析方法,35,本章小结,数据构造研究的是数据的逻辑构造和存储构造以与其算法；,本课程从抽象数据类型角度讨论各种类型的数据构造与其应用；,本课程使用类C语言作为算法的描述工具；,算法的五大特性：有穷性、确定性、可行性、输入、输出；,一个“好的算法应满足正确性、可读性、强健性以与效率与低存储量的需求；,算法的分析主要考察算法的时间复杂度和空间复杂度。,36,课堂练习,1. 算法的时间复杂度取决于 ,A问题的规模 B. 待处理数据的初态 C. A和B,2.计算机算法指的是1，它必须具备2 这三个特性。,(1) A计算方法 B. 排序方法,C. 解决问题的步骤序列 D. 调度方法,(2) A可执行性、可移植性、可扩大性 B. 可执行性、确定性、有穷性,C. 确定性、有穷性、稳定性 D. 易读性、稳定性、平安性,37,谢谢大家！,38,谢谢观赏,