数据结构讲义.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,数据结构,第一章 绪论,本章主要内容,学习,数据结构,的意义,基本概念和术语,算法的描述和分析,1.1,什么是数据结构,图书的基本信息,登记号，书名，作者，分类编号，出版单位，出版时间,作者简介，内容简介，等等。,操作,检索，排序，等等,数据之间的关系,线性关系,数据表示和算法操作的设计,与需求有关,数据的逻辑结构，存储结构，算法操作,逻辑结构是客观事物特性的一种抽象,存储结构是逻辑结构的计算机实现,算法操作是基于存储结构的操作，反映客观事物的变化,问题,1,：图书检索自动化,问题,2,：井子棋,问题,2,：井子棋（续）,如何表示一个棋局,数据之间的逻辑结构,表示棋局之间的演化关系,树型结构,算法如何设计,基于数据表示的基础上算法设计,拼盘游戏：空盘,拼盘游戏：拼件,拼盘游戏：拼出的一种方案,拼盘游戏：指定动作的习题,问题,3,：,铺设通信管线，投资最少,逻辑结构：图状结构,数据结构课程的主要任务,研究和解决非数值数据的组织和处理,描述非数值计算问题的数学模型，不再是数学方程,例如：前述的三个例子：数据的线性结构，树型结构，图,算法,+,数据结构,=,程序,算法和数据结构之间的关系,软件系统的框架应当建立在数据之上，而不是建立在操作之上,数据结构的作用范畴,抽象数据对象的数学模型（逻辑结构）例：图状结构,明确操作（运算的定义）例：查找、插入、,在存储结构上映射数据（存储结构）例：顺序存储,实现操作,数据结构课程的发展,1968,年斯坦福的,Knuth,教授开创了数据结构的最初体系，在他所著的,计算机程序设计技巧,第一卷,基本算法,中第一次较系统地阐述了数据的逻辑结构和存储结构及其操作。,Donald Ervin Knuth,The Art of Computer Programming,Art Evans,数据结构在计算机科学中是一门综合性的专业基础课，也是计算机专业的必修课，是其它许多课程的先修课程，是设计编译程序、操作系统、数据库系统等系统程序和大型应用程序的重要基础。,1.2,基本概念和术语,基本术语,数据,被计算机加工处理的对象。,数据元素,（,记录,、,表目,）数据的基本单位，是数据集合中的一个有意义的个体。,数据项,一个数据元素可由若干个,数据项,组成。,组合项,年 月 日,学 号姓 名班 号性别出生日期入学成绩,原子项,基本术语,2,数据对象,是性质相同的数据元素的集合，是数据的一个子集。,学号 姓名 班号 性别 出生日期 入学成绩,001,刘影,01,女,19840417 623,002,李恒,01,男,19831211 679,003,陈诚,02,男,19840910 638,数据结构,具有结构的数据元素的集合。它包括数据元素的,逻辑结构,、,存储结构,和相适应的,运算,。,数据元素,数据元素之间的逻辑关系，与计算机无关。,可用一个二元组表示：,Data_Structure=(D,R),D,：数据元素的有穷集合，,R,：集合,D,上关系的有穷集合。,例,设有数据结构,B=(D,R),，,其中,D=d1,d2,d3,d4,d5,d6,，,R=r,，,r=,，,试画出其逻辑结构图。,d1,d2 d3 d4,d5 d6,逻辑结构,（以班级学生关系为例）,(1),集合结构,数据元素除了,“,属于同一集合,”,的联系之外，没有其它的关系。,(2),线性结构,数据元素之间存在一对一的关系。,(3),树型结构,数据元素之间存在一对多的关系。,(4),图状结构,或,网状结构,数据元素之间存在多对多的关系。,成员关系,长幼关系,管理关系,朋友关系,四种基本的逻辑结构,数据的逻辑结构,THANK YOU,SUCCESS,2025/5/13 周二,21,可编辑,存储结构,：数据的逻辑结构在计算机中如何表示。,数据元素的映象,用二进制位,(bit),的位串表示数据元素。,每个数据元素的映象称为,结点,每个数据项的映象称为,数据域,关系的映象,两种基本方法及其组合使用。,顺序映象：以相对的存储位置表示关系,链式映象：以附加信息,(,指针,),表示关系,在不同的编程环境下，存储结构有不同的描述方式。,用高级程序语言编程时，直接用其提供的数据类型描述。,存储结构,(1),顺序存储,：数据元素依次放在连续的存储单元中,。,a1 a2 .a,i,.a,n,(2),链式存储,：在存储结点中增加若干指针域，记录后继或者相关结点的地址（指针）。,a1,1220,.a3,1342,.a2,1072,.,1000 1004,1000 1004 1072 1076 1220 1224,指针,结点,结点,顺序存储和链式存储,运算,（,操作,）,：在数据逻辑结构上定义的一组数据被使用的方式，其具体实现要在存储结构上进行。,几种常用的运算有：,(1),建立数据结构,(6),检索*,(2),清除数据结构,(7),更新,(3),插入数据元素,(8),判空和判满*,(4)删除数据元素,(9),求长*,(5),排序,*操作为,引用型操作,，即数据值不发生变化；,其它为,加工型操作,。,数据运算,抽象数据类型,ADT,（,Abstract Data Type,）,：,数据类型概念的引伸。指一个,数学模型,以及在其上定义的,操作集合,，与计算机无关。,数据类型,：一组值的集合和定义在其上的一组操作的总称。,ADT,的特点,：将它的使用和实现分离，提高软件复用程度。,原子类型,固定聚合类型：值由确定数目的成分构成,结构类型,可变聚合类型：值的成分数目不确定,抽象数据类型,数据的逻辑结构,+,运算的定义,-,面向用户，需求分析,（抽象数据类型）,概念层,数据的存储结构运算的实现,-,面向计算机,实现层,数据的逻辑结构与存储结构,其中基本操作的定义格式为,:,ADT,抽象数据类型名,数据对象：,数据对象的定义,数据关系：,数据关系的定义,基本操作：,基本操作的定义,ADT,抽象数据类型名,基本操作名,（参数表）,初始条件：,初始条件描述,操作结果,：,操作结果描述,抽象数据类型的描述方法,参数,赋值参数,只为操作提供输入值。,引用参数,除可提供输入值外，还将返回该参数值在操作后的变化结果,初始条件,描述了操作执行之前数据结构和参数应满足的条件，若不满足，则操作失败，并返回相应出错信息。,操作结果,说明了操作正常完成之后，数据结构的变化状况和应返回的结果抽象数据类型的描述方法（续）,1.3,抽象数据类型的表示与实现,1.4,算法和算法分析,算法的概念,建立在数据结构基础上的、求解问题的一系列确切的步骤。,一个算法必须满足以下五个重要特性,有穷性：,对任何合法输入执行有穷步后能结束。,确定性：,每条指令必须有确切的含义。,可行性：,算法的每一条指令均能执行。,输入：,有零个或多个输入。,输出：,有一个或多个输出。,算法的概念,和特性,正确性,(Correctness),算法应满足具体问题的需求,对于典型的、苛刻而带有刁难性的一组有效输入得到正确的结果,可读性,(Readability),算法应该好读。以有利于阅读者对程序的理解。,健壮性,(Robustness),算法应具有容错处理。当输入非法数据时，算法应对其作出反应，而不是产生莫名其妙或随机的输出结果。,高效性,(Efficiency),算法效率的度量,时间复杂度,空间复杂度,评价算法优劣的基本标准,算法效率的度量,时间复杂度,空间复杂度,算法执行的时间,事后统计的方法,先运行依据算法的程序,所得时间的统计量依赖于计算机的硬件、软件等环境因素,收集此算法的执行时间和实际占用空间的统计资料,事前分析估算的方法,求出该算法的一个时间界限函数；,时间复杂度,n,问题规模，一般为数据的输入量,f(n),算法中基本操作重复执行的次数,频度,是问题规模,n,的某个函数,算法的,时间量度、时间复杂度,算法中各语句的频度之和,T(n),T(n)=O(f(n),随问题规模的增大，算法执行时间的增长率和,f(n),的增长率相同,O,的含义,存在正的常数,c,和,n,0,，使得,当,n,n,0,时，,0,T(n),c*,f(n),时间复杂度计算,例,1,：,x+;s=0;,将,x+,看成是基本操作，语句频度为,T(n)=2,算法的时间复杂度：,O(1)-,常量阶,例,2:for(i=0;in;i+),/,执行,n+1,次,x+;,/,语句频度为：,n,s+=x;,/,语句频度为：,n,T(n)=2n+n+1=3n+1,算法的时间复杂度为：,O(n)-,线性阶,时间复杂度计算,2,例,3:,矩阵相乘,C=AxB,for(i=0;i n;i+),/n+1,for(j=0;j n;j+),/n*(n+1),cij=0;,/n,2,for(k=0;k n;k+),/n,2,*(n+1),cij+=aik*bkj;,/n,3,T(n)=,2n,3,+3n,2,+2n+1,算法的时间复杂度：,O(n,3,),时间复杂度计算,3,在难以精确计算基本操作执行次数的情况下，只求出关于,n,的增长率即可。,例,4:for (i=2;i=n;+i),for(j=2;j=,0&Ai!=K),(3)i=i-1;,(4)RETURN(i);,最好情况的时间复杂度,T(n)=O(1),最坏情况的时间复杂度,T(n)=O(n),平均时间复杂度：,所有可能的输入实例以等概率出现的情况,T(n)=(1+2+.+n)/n,算法的时间复杂度：,O(n),时间复杂度曲线,常见的时间复杂度,：,O(1),O(log,2,n),O(n),O(n log,2,n),O(n,2,),O(n,3,),O(2,n,),O(1)O(,log,2,n,),O(n),O(n,log,2,n,),(n,2,),O(n,3,),O(2,n,),空间复杂度,算法所需存储空间的度量,记作：,S(n)=O(f(n),其中,n,为问题的规模,(,或大小,),存储密度,d=,数据本身存储量/实际所占存储量,THANK YOU,SUCCESS,2025/5/13 周二,42,可编辑,