数据结构基本概念.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第,1,章 数据结构,1.1,数据结构的基本概念与算法,1.2,线性表,1.3,栈和队列,1.4,树和二叉树,1.5,查找,1.6,内部排序,A,B,C,D,E,F,G,姓名 学号 成绩 班级,李红,9761059 95,机,97.6,10,65,865,计算机是一门研究用计算机进行信息表示和处理的科学。这里面涉及到两个问题：,信息的表示,信息的处理,而信息的表示和存储又直接关系到处理信息的程序的效率。随着计算机的普及，信息量的增加，信息范围的拓宽，使许多系统程序和应用程序的规模很大，结构又相当复杂。因此，为了编写出一个“好”的程序，必须分析待处理的,对象的特征,及各,对象之间存在的关系,，这就是数据结构这门课所要研究的问题。,什么是数据结构,下面文字的含义：,漆黑的头发没有麻子脚不大周正,演绎,漆黑的头发，没有麻子，脚不大，周正。,结论：,描述一个古代美人,！,演绎,漆黑的头发没有，麻子，脚不大周正。,结论：描述了一个,古代丑女人,，还是个瘸子。,结论,两个不同的演绎表现为不同的结果，一个是古代美人，一个确实古代丑女人，原因只是文字的不同组合造成！,也就是说：相同的文字（数据）经过不同的组合（结构）会得到不同的结果，这就是我们要介绍的数据结构：,数据及其之间的关系（结构）。,1.1,数据结构的基本概念与算法,1.,数据结构的定义,1).,数据：,信息载体，能够被计算机识别、存储和加工处理。可以是,数值数据,(,整数、实数,),，也可以是,非数值数据,(,声音、图像等,),。,2).,数据项,:,是数据的具有独立含义的不可分割的,最小标识单位,如成绩表中学号,姓名等,.,3).,数据元素：,一个数据元素由,若干数据项,组成,是数据的,基本单位,，通常作为一个整体进行考虑和处理,(,又称,结点、记录,),。,1.1.1,数据结构的基本概念,学号,姓名,系别,住址,电话,981111,李洪,机械,六舍,5371111,982111,王刚,电子,四舍,5372111,983211,王将,计算机,五舍,5373211,983212,张强,机械,六舎,5372221,4,个数据元素,5,个数据项,1,个数据项,1,个数据元素,4).,数据对象,:,具有,相同性质,的,数据元素的,集合,。,是数据的一个子集。,例,:,成绩表,学号,姓名,系别,住址,电话,981111,李洪,机械,六舍,5371111,982111,王刚,电子,四舍,5372111,983211,王将,计算机,五舍,5373211,983212,张强,机械,六舎,5372221,1,.,数据结构的定义,1).,数据：,2).,数据项,:,3).,数据元素：,关键码：,值唯一能区别不同的,数据元素的数据项,数据对象,-由,4,个记录组成,表中每行是一个记录,每个记录由,5,个数据项组成,.,1.1,数据结构的基本概念与算法,1.1.1,数据结构的基本概念,1.,数据结构的定义,1).,数据：,2).,数据项,:,3).,数据元素：,4).,数据对象,:,5).,数据结构,:,相互之间存在着一种或多种,关系,的,数据元素,的集合。,研究,内容,数据的逻辑结构,：,各数据元素之间的逻辑关系,数据的存储结构,：,各数据元素在计算机中的存储关系,对各种数据结构进行的运算,：,添加，删除，排序等。,1.1,数据结构的基本概念与算法,1.1.1,数据结构的基本概念,1.,数据结构的定义,1).,数据：,2).,数据项3).,数据元素：,4).,数据对象,:,5).,数据结构,:,相互之间存在着一种或多种,关系,的,数据元素,的集合。,研究,目的,一是提高数据处理的,速度,.,二是尽量节省在数据处理过程中所占用的计算机存储,空间,.,1.1,数据结构的基本概念与算法,1.1.1,数据结构的基本概念,1.,数据结构的定义,2.,数据的逻辑结构,集合,元素间为松散的关系,(,属于关系,),线性结构,元素间为一对一关系,树形结构,元素间为一对多关系,图状结构,元素间为多对多关系,1.1,数据结构的基本概念与算法,1.1.1,数据结构的基本概念,集合、树型、图形结构属于,非线性结构,学号,姓名,语文,数学,C语言,1001,张三,85,54,92,1002,李四,92,84,64,1003,王五,87,74,73,.,通迅录、成绩单、花名册,线性结构,电子字典、家谱、目录,树型结构,H,B,C,D,E,F,G,A,H,G,F,E,C,D,B,A,计算机中的目录结构问题,树,交通线路、通信网络,图状结构,图形结构特点,结点间的连结是任意的,A,E,B,C,D,树型结构特点,结点间具有分层次的连接关系,3.,数据结构的存储结构,数据的存储结构是指数据元素及其关系在计算机存储器内的表示（又称映象）。,存储结构研究的是,逻辑结构用计算机语言,实现，依赖于,计算机语言。,一种,数据结构可以根据需要采用,多种不同的存储结构,，常用的存储结构有,顺序、链接与索引,等存储方式。,数据的,存储结构不同,，解决问题的,方法就有所不同,，数据处理的,效率也是不同,的。,1.1,数据结构的基本概念与算法,1.1.1,数据结构的基本概念,3.,数据结构的存储结构,(1),顺序存储方,式,：,逻辑上,相邻的元素存储在,物理位置相邻,的存储单元中,。主要用于线性结构。,通常借助于数组来实现。,1.1,数据结构的基本概念与算法,1.1.1,数据结构的基本概念,顺序存储结构的线性表,线性表,(a0,a1,a2,a3),存储单元的地址即物理地址,如，,C,语言的数组,a,2,a,3,a,1,a,0,a,1,a,0,3.数据结构的存储结构,(1),顺序存储方,式,：,逻辑上,相邻的元素存储在,物理位置相邻,的存储单元中,。主要用于线性结构。,通常借助于数组来实现。,(2),链式,存储方,式,：,对逻辑上相邻的元素,不要求其物理地址相邻，,元素间逻辑关系通过附加的指针字段来表示。通常借助于,指针类型,实现。,1.1,数据结构的基本概念与算法,1.1.1,数据结构的基本概念,链式,存储结构的线性表,存储单元的地址即物理地址,指针域：存放下一个结点的地址,a0,a1,在逻辑上相邻,而在机内存储时,存储单元的地址,(100,108),并不相邻,.,链式,存储方,式特点,：,每个,结点,由两部分组成：一部分存放数据，另一部分,存储,指向前件或后件结点的指针域。,逻辑上相邻的结点物理上不必相连。,数据运算,(,插入和删除等,),灵活。,a,2,a,3,a,1,a,0,1.1,数据结构的基本概念与算法,1.1.1,数据结构的基本概念,6.,数据类型及其分类,数据类型（,Data Type,）是程序设计语言中所允许使用的变量类型。,一个变量类型不仅定义了相应变量可以设定的值的的,集合,，还规定了对变量允许进行的一组运算及其规则。,例：,C,语言中的整型变量，其值为某个区间上整数，定义在其上的操作为：加，减、乘、除和求余数等算术运算。,分类：（,1,）非结构的原子类型,（,2,）结构类型,（,2,）结构类型：,结构类型的值是由,若干成分按某种结构,组成的，因此是可分解的，并且它的成分可以是非结构的，也可以是结构的。,（,1,）非结构的原子类型：,原子类型的值是不可分解的。如：程序设计语言中的基本类型（整型，实型，字符型，指针类型和空类型）。,结构类型举例：,struct,stu,char nm8;/,学号,char name18;/,姓名,char sex;/,性别,;,struct,stu,s1;/,学生类型,1.,算法的定义：,算法,(A1gorithm),是对特定问题求解步骤的精确描述，它是指令或语句的有限序列,。,1.1,数据结构的基本概念与算法,1.1.2,算法及算法分析,有穷性：,一个算法应包含有限个操作步骤，而且每一步都应在有限时间内完成。,确定性,：,算法中每一条指令必须有确切的含义，确保不会产生二义性。,可行性：,算法中指定的操作都是可以通过基本运算执行有限次后实现,。,输入：,一个算法有零个或多个的输入，,这些输入取自于某个特定的对象集合。,输出,：一个算法有一个或多个的输出，,这些输出是同输入有着某些特定关系的量。,1.,算法概念,算法,(A1gorithm),是对特定问题求解步骤的精确描述，它是指令或语句的有限序列,。,1.1,数据结构的基本概念与算法,1.1.2,算法及算法分析,首先要从具体问题抽象出一个适当的数学模型；,然后设计一个解此数学模型的算法；,最后采用一种计算机语言编出程序，调试、修改,直至得到最终答案。,用计算机解决一个具体问题时，大致需要经过下列几个步骤：,1.1,数据结构的基本概念与算法,1.1.2,算法及算法分析,算法设计的要求,（,1,）正确性,（,2,）可读性,（,3,）,健壮性,（,4,）效率与低存储量,执行结果应满足预先的功能和性能要求,思路清晰、层次分明、简单明了、易读易懂,输入数据非法时，算法能作适当处理，不致于引起严重后果,有效使用存储空间和较高的时间效率,1.1,数据结构的基本概念与算法,评价算法标准,算法所占用计算机资源，即,时间代价,(,算法所需要的时间）,和,空间代价,（算法所需要的存储空间）。,算法所需要的时间包括：,程序运行时所需要的数据总量；,源程序进行编译所需要的时间；,计算机执行每条指令所需要的时间；,程序中指令,重复执行的次数,，而本条正是讨论算法中的重点内容（,常考,）,1.1.2,算法及算法分析,1.1,数据结构的基本概念与算法,1.1.3,算法分析技术初步,相关名词：,(1),问题规模：,不同种类问题，问题规模含义不同。如矩阵运算取决于矩阵阶数，多项式运算取决于项数。,(2),算法运行时间：,大致等于其所有语句,执行时间的总和,。,(3),语句频度：,该语句在算法中,重复执行的次数,。,1.1,数据结构的基本概念与算法,1.1.3,算法分析技术初步,1.,时间复杂度：,算法中基本操作重复执行的次数依据算法中,最大语句频度,来估算，它是问题规模,n,的某个函数,f(n,),，算法的时间量度记作,T(n,),O(f,（,n),表示随问题规模,n,的增大，算法执行时间的增长率和,f(n,),的增长率相同，称作算法的渐近时间复杂度，简称时间复杂度。,时间复杂度：,T(n)=O(f(n),T(n),：,算法中所有语句频度之和,n,：,问题规模。,T(n),是,n,的某个函数。,O,：,数量级。,当问题规模趋向无穷时，,T(n),的数量级称为时间复杂度。,x+=5;,单个语句的频度为,1,，则 程序段的时间复杂度为,for(i,=0;in;i+),for(j,=0;j,n;j,+)cij,=i*j;,最优算法：,随,n,的增大，,T(n),增长较慢的算法。,T(n,)=O(1),则：,T(n,)=O(n,2,),for(i,=1;i=,n;+i,),for(j,=1;j=,n;+j,),cij,=0;,for(k,=1;k=,n;+k,),cij,+=,aik,*,bkj,;,由于是一个三重循环，每个循环从,1,到,n,，则总次数为,:,nnn,=n,3,时间复杂度为,T(n,)=,O(n,3,),for(i,=1;i=,n;+i,),+x;,s+=x;,语句频度为：,2n,其时间复杂度为：,O(n,),for(i,=2;i=,n;+i,),for(j,=2;j=i-1;+j),+x;,aij,=x;,语句频度为：,1+2+3+n-2,=(1+n-2)(n-2)/2,=(n-1)(n-2)/2,=n,2,-3n+2,时间复杂度为,O(n,2,),时间复杂度：,平均时间复杂度：,所有可能的输入实例均以等概率出现的情况下，算法的期望运行时间。,最坏时间复杂度：,最坏情况下算法的时间复杂度。,算法的时间复杂度不仅与,问题规模,有关,而且与,输入数据,有关,即输入数据所有的可能取值范围及输入各种数据或数据集的概率有关,以下六种计算算法时间的多项式是最常用的。其关系为：,O(1),O(logn,),O(n,),O(nlogn,),O(n,2,)O(n,3,),1.1数据结构的基本概念与算法,2.,空间复杂度：,定义：,算法运行从开始到结束所需的存储空间量,包括 固定部分和可变部分。,固定部分：,此部分空间与所处理数据的大小和规模无关。通常用来保存本身所用的程序代码、常量、变量等,。,可变部分：,此部分空间与处理的数据的大小和规模有关，即,执行算法,时所需额外空间。,1.1.2,算法及算法分析,思考题,研究数据结构的目的是什么？,数据结构研究哪三方面的问题,?,关系如何,?,在数据结构中数据项、数据元素及数据对象的关系？,数据的逻辑结构分为哪两大类？各有何特点？,数据的存储结构中的顺序存储与链式存储各有什么特点？,什么是算法？有何特点？,算法设计的基本要求？,算法设计的方法？,如何评价算法？,什么是时间复杂度？时间复杂度与哪些因素有关？,什么是空间复杂度？包括哪两部分？,习题讲解,1.,数据处理的最小单位是,_,。,A.,数据,B.,数据元素,C.,数据项,D.,数据结构,2.,数据结构中，与所使用的计算机无关的是数据的,_,。,A.,存储结构,B.,物理结构,C.,逻辑结构,D.,物理和存储结构,3.,下面叙述正确的是,_,。,A.,算法的执行效率与数据的存储结构无关,B.,算法的空间复杂度是指算法程序中指令（或语句）的条数,C.,算法的有穷性是指算法必须能在执行有限个步骤之后终止,D.,以上三种描述都不对,4.,算法的时间复杂度是指,_,A.,执行算法程序所需要的时间,B.,算法程序的长度,C.,算法执行过程中所需要的基本运算次数,D.,算法程序中的指令条数,5.,算法的空间复杂度是指,_,。,A.,算法程序的长度,B.,算法程序中的指令条数,C.,算法程序所占的存储空间,D.,算法执行过程中所需要的存储空间,CCCCD,习题讲解,6.,算法一般都可以用哪几种控制结构组合而成,_,。,A.,循环、分支、递归,B.,顺序、循环、嵌套,C.,循环、递归、选择,D.,顺序、选择、循环,7.,数据的存储结构是指,_,。,(05.4,月）,A,）存储在外存中的数据,B,）数据所占的存储空间量,C,）数据在计算机中的顺序存储方式,D,数据的逻辑结构在计算机中的表示,8.,在下列选项中，哪个不是一个算法应该具有的基本特征,_,。,A.,确定性,B.,可行性,C.,无穷性,D.,拥有足够的情报,9.,在计算机中，算法是指,_,。,A.,查询方法,B.,加工方法,C.,解题方案的准确而完整的描述,D.,排序方法,10.,算法分析的目的是,_,。,A.,找出数据结构的合理性,B.,找出算法中输入和输出之间的关系,C.,分析算法的易懂性和可靠性,D.,分析算法的效率以求改进,DDCCD,习题讲解,11.,算法具有五个特性，以下选项中不属于算法特性的是,_,。,(05.4,月）,A,）有穷性,B,）简洁性,C,）可行性,D,）确定性12.,下列叙述中正确的是,A,）一个逻辑数据结构只能有一种存储结构,B,）数据的逻辑结构属于线性结构，存储结构属于非线性结构,C,）一个逻辑数据结构可以有多种存储结构，且各种存储结构不影响数据处理的效率,D,）一个逻辑数据结构可以有多种存储结构，且各种存储结构影响数据处理的效率,13.,算法复杂度主要包括时间复杂度和,【2】,复杂度。（,05.9,月）,14.,问题处理方案的正确而完整的描述称为,【5】,。,(05.4,月）,BD,空间复杂度、算法,15.,在线性结构和树型结构中，前驱结点和后继结点之间分别存在着,_,和,_,的联系。,一对一、一对多,16.,一个数据结构在计算机中的表示（映象）称为,_,。,数据的存储结构,