《数据结构绪论》PPT课件.ppt

平时成绩：40%出勤、课堂、上机,考试成绩：60%,关于成绩,通过本课程的学习，运用本课程讨论的知识更好地进行算法设计与算法分析，掌握计算机进行数据处理的基本原理、基本方法和技巧，进一步提高程序设计的水平和能力。,本课程的特点：,1.计算机专业重要的专业基础课之一.,2.需要有关“程序设计语言”和“离散数学”的知识作为课程的基础.,3.实践性较强.,4.难学而且重要.,5.乐趣.,数据结构的研究对象,计算机应用,如何组织？,如何处理？,程序,算法,存储结构,逻辑结构,数据,谁来处理？,1.1 数据结构讨论的范畴,1.2 基本概念,1.3 算法和算法的量度,本章内容,1.1 数据结构讨论的范畴,Niklaus Wirth:算法+数据结构=程序,程序设计：为计算机处理问题编制一组指 令集算法（怎么样处理）：处理问题的策略数据结构（被处理的信息如何表示）：问 题的数学模型,用计算机解决一具体问题时，大致需要经过下列几个步骤:,如何寻求数据模型？1、分析问题；2、提取操作的对象；3、找出操作对象之间的关系；4、用数学的语言加以描述；,模型：？取决于整数值的范围,例1：求一组（n个）整数中的最大值,算法：？基本操作是“比较两个数的大小”,模型：？棋盘和棋子如何表示,例 2：计算机对弈,算法：？对弈的规则和策略,数据结构是一门讨论“描述现实世界实体的数学模型及其上的操作在计算机中如何表示和实现”的学科。,概括的说，,数据结构主要研究数据之间有哪些结构关系，如何表示，如何存储，如何处理。,具体的说，,一、数据与数据结构二、数据类型三、抽象数据类型,1.2 基本概念,一、数据与数据结构,描述客观事物的数字、字符以及一切能够输入到计算机中，并且能够被计算机程序处理的符号的集合。,数据：,数据元素：,是数据中的一个个体是数据结构中讨论的基本单位。例一中的整数例二中的棋盘格局（状态）,数据项：数据结构中讨论的最小单位 数据元素可以是数据项的集合,例如：描述一个运动员的数据元素可以是,1、数据元素之间的联系称之为结构。2、数据结构就是具有结构的数据元素 的集合。,3214，6587，9345 6587，3214，9345 a1 a2 a3 a2 a1 a3,例如：一个含12位数的十进制数可以用三个四位十进制数表示,3214，6587，9345 a1(3214),a2(6587),a3(9345)在a1,a2和a3之间存在次序关系,数据结构就是具有结构的数据元素的集合。,2行3列的二维数组 a1,a2,a3,a4,a5,a6,行的次序关系：row=,列的次序关系：col=,数据结构就是具有结构的数据元素的集合。,可见不同的“关系”构成不同的“结构”或者说，数据结构是相互之间存在着某种逻辑关系的数据元素的集合。,数据结构是一个二元组,Data-Structure=(D,S),其中，D是数据元素的有限集合,S是D上的关系的有限集合。,数据结构的形式定义为：,集合结构：数据元素间除“同属于一个集合”外，无其它关系线性结构：一个对一个，如:线性表、栈、队列树形结构：一个对多个，如:树图状结构：多个对多个，如:图,逻辑结构可归结为如下四类：,“数据元素”的映象,“关系”的映象,1.顺序存储映象,以相对的存储位置表示数据关系。,例如：令Y的存储位置和X的存储位置之间差一个常量C,而C是一个隐含值，整个存储结构中只含数据元素本身的信息,X,Y,以附加信息（指针）来表示数据关系,2.链式存储映象,需要用一个和x在一起的附加信息指示y的存储位置,Y,X,1536,元素2,1400,元素1,1346,元素3,元素4,1345,h,数据的逻辑结构与存储结构的关系,任何一个算法的设计取决于选定的数据（逻辑）结构算法的实现依赖于采用的存储结构,在不同的编程环境中，存储结构可有不同的描述方法,当用高级程序设计语言进行编程时，通常可用高级程序设计语言中提供的数据类型描述之,例如：,以三个带有次序关系的整数表示一个长整数时，可利用c语言中提供的整数数组类型。定义长整数为：,二、数据类型,在用高级语言编写的程序中，必须对程序中出现的每个变量、常量或表达式明确说明他们所属的数据类型。,C语言中提供的基本数据类型有:,整型：int浮点型：float双精度型：double字符型：char逻辑型：bool(c+),C语言中提供的复合数据类型有：,数组：结构：struct,一个值的集合+定义在此集合上的一组操作=数据类型,三、抽象数据类型(Abstract Data Type简称ADT),是指一个数学模型以及定义在此数学模型上的一组操作,数据结构+定义在此数据结构上的一组操作=抽象数据类型,抽象数据类型的定义与其在计算机内部如何表示和实现无关（类/class）,抽象数据类型和数据类型实际上是一个概念,ADT Complex 数据对象：De1,e2e1,e2RealSet 数据关系：R1|e1是复数的实数部分,|e2 是复数的虚数部分,例如：抽象数据类型复数的定义,基本操作：InitComplex(&Z,v1,v2)操作结果：构造复数Z,其实部和虚部 分别被赋以参数v1和v2的值。DestroyComplex(&Z)操作结果：复数Z被销毁。GetReal(Z,&realPart)初始条件：复数已存在。操作结果：用realPart返回复数Z的实部 值。,GetImag(Z,&ImagPart)初始条件：复数已存在。操作结果：用ImagPart返回复数Z的 虚部值。Add(z1,z2,&sum)初始条件：z1,z2是复数。操作结果：用sum返回两个复数 z1,z2的和值。ADT Complex,抽象数据类型可用（D，S，P）三元组表示 其中，D是数据对象集，S是D上的关系集，P是对D的基本操作集。,抽象数据类型的描述方法,ADT 抽象数据类型名 数据对象：数据对象的定义 数据关系：数据关系的定义 基本操作：基本操作的定义 ADT 抽象数据类型名,其中基本操作的定义格式为：,基本操作名（参数表）初始条件：操作结果：,赋值参数:只为操作提供输入值。引用参数：以&打头，除可提供输入 值之外，还将返回操作结果。,初始条件：描述了操作执行之前数据结构和参数应满足的条件，若不满足，则操作失败，并返回相应出错信息。,操作结果：说明了操作正常完成之后，数据结构的变化状况和应返回的结果。,内容回顾,数据结构与算法讨论的内容课程的重要性，如何学好？数据、数据元素、数据项、数据结构、逻辑结构、存储结构数据类型、抽象数据类型,ADT 抽象数据类型名 数据对象：数据对象的定义 数据关系：数据关系的定义 基本操作：基本操作的定义 ADT 抽象数据类型名,抽象数据类型的表示和实现,抽象数据类型需要通过固有数据类型（高级编程语言中已实现的数据类型）来实现。例如，以上所定义的复数。,/-存储结构的定义typedef struct float realpart;float imagpart;complex;/-基本操作的函数原型说明,1.3 算法和算法的衡量,一、算法,二、算法设计的原则,三、算法效率的衡量方法和准则,四、算法的存储空间需求,一.算法,算法是为了解决某类问题而规定的一个有限长的操作序列。,一个完整的算法应该满足下面五个基本标准：,1有穷性 对于任意一组合法输入值，在执行有穷步骤(语句条数有限）之后一定能结束，即：算法中的每个步骤都能在有限时间（合理)内完成；,2确定性 对于每种情况下所应执行的操作，在算法中都有确切的规定，使算法的执行者或阅读者都能明确其含义及如何执行。并且在任何条件下，算法都只有一条执行路径；（同一个输入，无论在任何情况下，同一输出）;,3可行性 算法中的所有操作都必须足够基本，都可以通过已经实现的基本操作，运算有限次实现之；,4有输入 作为算法加工对象的量值，通常体现为算法中的一组变量。有些输入量需要在算法执行过程中输入，而有的算法表面上可以没有输入，实际上已被嵌入算法之中；,5有输出 它是一组与“输入”有确定关系的量值，是算法进行信息加工后得到的结果，这种确定关系即为算法的功能;,算法的表示,类C语言(参见书p 10-11)介于伪码和c语言之间的一种语言,1正确性 2.可读性 3健壮性 4高效率与低存储量需求,二、算法设计的原则,设计算法时，通常要考虑达到如下目标,1正确性,首先，算法应当满足以特定的“规格说明”方式给出的需求（用户的需求）。,a程序中不含语法错误；,其次，对算法是否“正确”的理解可以有以下四个层次：,b程序对于几组输入数据能够得出 满足要求的结果；,通常以第c层意义的正确性作为衡量一个算法是否合格的标准。,d程序对于一切合法的输入数据都能得出满足要求的结果；,c程序对于精心选择的、典型、苛刻切带有刁难性的几组输入数据能够得出满足要求的结果；,2.可读性,算法主要是为了人的阅读与交流，其次才是为计算机执行。因此算法应该易于人的理解；另一方面，晦涩难读的程序易于隐藏较多错误而难以调试；(teamwork),当输入的数据非法时，算法应当恰当地作出反映或进行相应处理，而不是产生莫名奇妙的输出结果。并且，处理出错的方法不应是中断程序的执行，而应是返回一个表示错误或错误性质的值，以便在更高的抽象层次上进行处理。（死机）,3健壮性,通常，效率指的是算法执行时间；存储量指的是算法执行过程中所需的最大存储空间。两者都与问题的规模有关。,4高效率与低存储量需求,通常有两种衡量算法效率的方法:,三、算法效率的衡量方法和准则,事前分析估算法,事后统计法 缺点：1必须执行程序 2其它因素掩盖算法本质,和算法执行时间相关的因素：,1、算法选用的策略2、问题的规模（如：求100以内还是1000以内的素数).3、编写程序的语言4、编译程序产生的机器代码的质量5、计算机执行指令的速度,一个特定算法的运行工作量的大小，只依赖于问题的规模（通常用整数量n表示），或者说，它是问题规模n的函数。,假如，随着问题规模n的增长，算法执行时间的增长率T(n)和问题规模n的的函数f(n)的增长率相同，则可记作：T(n)=O(f(n)称T(n)为算法的(渐近)时间复杂度,如何估算 算法的时间复杂度呢？,算法的频度:f(n)=n+n*n+n2+n2*n+n3=2n3+2n2+n,-n-n*n-n2-n2*n-n3,void s_s(int a,int n)for(i=0;i n-1;+i)j=i;/选择第I个最小元素 for(k=i+1;k n;+k)if(ak aj)j=k;if(j!=i)aj ai/s_s,常见的时间复杂度：O(1)：常量阶 O(n)：线性阶 O(n2)：平方阶 O(logn)：对数阶 O(2n)：指数阶,算法的空间复杂度 S(n)=O(g(n)表示随着问题规模n的增大，算法运行所需存储量的增长率S(n)与g(n)的增长率相同。,空间复杂度,2.程序本身所占空间；,3.辅助变量所占空间；,1.输入数据所占空间;,算法的存储量包括：,本章学习要点,1、熟悉各名词、术语的含义，掌握基本概念。2、理解ADT的意义。3、理解算法五个要素的确切含义。4、掌握计算语句频度和估算算法时间复杂度的方法。5、算法的表示与实现。,练习题：,1、简述下列术语：数据结构、逻辑结构、存储结构、抽象数据类型。2、简述抽象数据类型的两个重要特征以及这两个重要特征的意义。3、简述四种逻辑结构、两种主要的数据关系映象。4、分析一下冒泡排序的时间复杂度,1、数据结构在计算机内存中的表示是指 A.数据的存储结构 B.数据元素的结构 C.数据的逻辑结构 D.数据元素之间的关系答案：A2、在数据结构中，与所使用的计算机无关的是 A.数据的存储结构 B.逻辑和物理结构 C.数据的逻辑结构 D.数据的物理结构答案：C,3、对于给定的n个元素，可以构造出的逻辑结构有、四种。答案：集合 线性结构 树结构 图结构,