单击此处编辑母版标题样式,*,*,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,书山有路勤为径,学海无涯苦作舟,讲解人：杨文贤,数据结构,第一章 概述,前期课程,数据结构,计算机基础,C,语言,离散数学,后期课程,操作系统,编译原理,数据库原理,软件工程,承上启下,计算机科学课程体系（偏软）,C/C+,语言,数据结构 软件工程,掌握基本编程方法,掌握数据组织和数据处理的方法,掌握大型软件开发方法,学习识字,学习写作文,学习写小说,基本要求,课程关系,与语文学习过程类比,动手能力（上机）,1.1,什么是数据结构？,随着计算机技术的发展，计算机应用的范围更广，所处理的数据更复杂。如果要提高数据处理的效率，就必须研究数据,本身的特性,、,数据之间的关系,，以及如何有效地将数据组织,存储,在计算机内。,通过对数据结构的学习,你将掌握,非数值计算程序设计中,用的基本方法和技巧。,问题,1,：图书检索自动化,数据：各类书籍，更确切地说是每本书的信息，如：书 名，作者，分类号，出版单位，出 版时间，作者简介，内容简介等等。,操作：检索，排序，等等,数据之间的关系：线性关系,操作：书目入库，借书，还书等,1.1,什么是数据结构？,1.1,什么是数据结构？,L003,006,清华大学出版社,1979,刘永年,运筹学,K005,005,清华大学出版社,1958,栾汝书,线性代数,L002,004,清华大学出版社,1982,张之,化学,M003,003,高教出版社,1965,罗远祥,理论力学,S002,002,高教出版社,1964,樊映川,高等数学,L001,001,出版社,出版时间,作 者,书 名,书 号,书目文件,004,线性代数,003,化学,002,理论力学,001,高等数学,索引表,按书名,004,栾汝书,003,张之,002,罗远祥,001,樊映川,按作者名,002,S,003,M,005,K,001,004,006,L,按分类,线性表,1.1,什么是数据结构？,问题,2,：人机对弈,数据：,各种棋局状态，确切地说是描述棋盘格局的信息,操作：,走棋，即选择一种策略使棋局状态发生变化（由一个格局派生出另一个格局）,数据的逻辑结构：,表示棋局之间的演化关系：树型结构,棋盘的,当前,格局,#,子棋的对弈树局部,树,问题：多叉路口交通灯的管理,（即在多叉路口应设置几种颜色的交通灯，以保证交通流畅,）,数据：,路口各条路的信息,操作：,设置信号灯（求出各个可同时通行的路的集合）,C,B,A,E,D,1.1,什么是数据结构？,共,13,条路：,A-B,B-A,A-C,B-C,A-D,B-D,D-A,E-A,D-B,E-B,D-C,E-C,E-D,图,AB,AC,AD,BA,DC,ED,BC,BD,DA,DB,EA,EB,EC,可以用四种颜色着色，因此需要设置四种信号灯,数据结构课程的主要任务,研究和解决非数值数据的组织和处理,描述非数值计算问题的数学模型，不再是数学方程,例如：前述的三个例子：数据的线性结构，树型结构，图,主要研究,：,数据元素之间固有的逻辑关系数据逻辑结构,数据元素及关系在计算机内的表示数据存储结构,对数据结构的操作算法,基本术语,数据：被计算机加工处理的对象。,数据元素：,是数据的,基本单位,。在计算机程序中通常作为,一个整体,考虑和处理,。,数据项：,是数据,不可分割的最小单位,。,一个数据元素可由若干个数据项组成。,组合项,年 月 日,学号 姓名 班号 性别 出生日期 入学成绩,原子项,1.2,基本概念和术语,1.2 基本概念和术语,数据对象,:,是性质相同的数据元素的集合。,学号,姓名,班号,性别,出生日期,入学成绩,001,刘影,01,女,19840417,623,002,李恒,01,男,19831211,679,003,陈诚,02,男,19840910,638,004,数据元素,整个表是学生成绩数据对象,数据项,数据结构,:,相互之间存在一种或多种特定,关系,的数据元素的,集合,它包括数据元素的逻辑结构、存储结构和相适应的运算。,特点是,：,数据元素集合相同，而其上的关系不同，则构成的数据结构不同。,数据结构的形式定义：,数据结构是一个二元组,DS=(D,R),其中：,D,是数据元素的有限集，,R,是,D,上关系的有限集。,关系的表示,序偶：,有序对。例如：,前驱：,序偶中第一元素为第二元素的前驱,后继：,序偶中第二元素为第一元素的后继,例,：设有数据结构,B=(D,R),其中：,D=d1,d2,d3,d4,d5,d6,R=r,，,r=,，,试画出其逻辑结构图。,(1),集合结构,数据元素除了“属于同一集合”的联系之外，没有其它的关系。,(2),线性结构,数据元素之间存在一对一的关系。,(3),树型结构,数据元素之间存在一对多的关系。,(4),图状结构,或,网状结构,数据元素之间存在多对多的关系。,集合结构,线性结构,树型结构,图状结构,数据的逻辑结构,是对数据元素之间存在的逻辑关系的描述，它可以用一个数据元素的集合和定义在此集合上的若干关系表示。数据的逻辑结构可看作是从具体问题抽象出来的数学模型,。,线性结构：,各个数据成员依次排列在一个线性序列中。,非线形结构：,各个数据成员不再保持在一个线性序列中，每个数据成员可能与零个或多个其他数据成员发生关系。,数据的存储结构,数据元素及其关系在计算机内的表示。,数据元素的映象,用二进制位,(bit),的位串表示数据元素。,每个数据元素的映象称为,结点,每个数据项的映象称为,数据域,逻辑结构可以映射为以下四种存储结构：,顺序存储结构,：把逻辑上相邻的数据元素存储在物理位置也相邻的存储单元中，借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系。,链式存储结构,：借助指针表达数据元素间的逻辑关系。不要求逻辑上相邻的数据元素在物理位置上也相邻。,索引存储结构,：在存储数据元素的同时，还建立附加的索引表。通过索引表，可以找到存储数据元素的节点。,散列存储结构,：根据散列函数和处理冲突的方法确定数据元素的存储位置。,用高级程序语言编程时，直接用其提供的数据类型描述！,数据的操作,在数据逻辑结构上定义的一组数据被使用的方式，其具体实现要在存储结构上进行。,这三个方面的关系：,数据的逻辑结构独立于计算机，是数据本身所固有的。,存贮结构是逻辑结构在计算机存贮器中的映像，必须依赖于计算机。,运算是指所施加的一组操作总称。运算的定义直接依赖于逻辑结构，但运算的实现必须依赖于存贮结构。,数据结构的三个方面,数据结构的三个方面,1,数据的逻辑结构,3,数据的运算：检索、排序、插入、删除、修改等,2,数据的存储结构,(,亦称物理结构,),非线性结构,线性结构,线性表,栈,队列,串,树形结构,图形结构,集合结构,顺序存储,链式存储,1.3,抽象数据类型,抽象数据类型,ADT,（,Abstract Data Type,）：,数据元素集合,以及定义在该集合上的一组,操作,“抽象”指与具体实现无关，仅考虑能做什么，而不考虑如何做。,形式描述：,ADT=(D，R，P),标准定义格式？,其中：,D,是数据对象，,R,是,D,上的关系集，,P,是,D,的基本操作集。,作用：,抽象数据类型可以使我们更容易描述实际问题。,例：用线性表描述学生成绩表，用树或图描述遗传关系。,好处：,可提高软件的复用程度。使用它的人可以只关心它的逻辑特征，不需要了解它的存储方式。定义它的人同样不必要关心它如何存储。,数据类型：,是一个,值的集合,和定义在这个值集上,一组操作,总称。,分类：,(,按值的不同特性,),原子类型：每一个对象仅由单值构成的类型；,结构类型：每一个对象可由若干成分按某种结构构成的类型。,抽象数据类型重要特性,数据抽象,用,ADT,描述程序处理的实体时，强调的是其本质的特征、其所能完成的功能以及它和外部用户的接口（即外界使用它的方法）。,数据封装,将实体的外部特性和其内部实现细节分离，并且对外部用户隐藏其内部实现细节。,抽象数据类型的实现,面向对象,类,面向过程,结构体,例：复数数据类型的抽象描述,分析,：定义,实部,i,虚部,实部和虚部的取值范围,实数,复数的操作,、,、,ADT,复数的数据类型抽象,数据对象,：,D=e1,e2|,实数,数据关系,：,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),操作结果：用,sum,返回两个复数,z1，z2,的和值。,End ADT Complex,思考如何进行复数相加,Complex r1,r2,sum;,Add(r1,r2,例：,矩形数据类型抽象描述,分析,：,定义,长、宽,长和宽的取值范围,实数,矩形的操作,初始化,(,构造,),矩形、计算矩形的,周长和面积,ADTRECtangle is,数据对象,：,D=e1,e2|,实数,数据关系,：,R1=|e1,是长，,e2,是宽,基本操作,:,InitRectangle(r,len,width);,操作结果：初始化矩形长和宽,Circumference(r);,操作结果：计算矩形周长,Area(r);,操作结果：计算矩形面积,End RECtangle,1.4,算法分析,算法就是求解问题的一系列步骤的集合。,通常把具体存储结构上的操作实现步骤或过程称为,算法,使用最适当的,【,数据结构,】,，才能够设计出最有效率的,【,算法,】,，进而转换成为有效率的,【,程序,】,。,例：求,n,个整数中的最大值。,1.,将第,1,个数赋值给,max,；,2.,初始化计数器变量,i,为,1,；,3.,当,imax,，则将,ai,赋值,max,；,(2)i,自增,1,；,4.,返回,max,的值。,程序数据结构算法,算法的,5,个特性（性质）,有穷性：,对于任意一组合法的输入值，在执行有穷步骤之后一定能结束。,确定性：,每条指令必须有确切的含义，不能有二义性。,可行性：,算法中描述的操作都是用已经实现的基本运算组成。,输入：,可以有0、1、或多个输入量。,输出：,它是一组与输入有确定关系的量值，是算法进行信息加工后得到的结果，这种确定关系即为算法的功能。,算法和程序的关系,两者相似而又有区别。程序不一定满足有穷性（死循环）；程序中的指令必须是机器可执行的，而算法中的指令则无此限制。一个算法若用计算机语言来书写，则它就可以是一个程序。,考虑下列两段描述：,(1),描述一,void exam1(),n,2;,while(n%2,0),n,n+2;,coutnendl;,华中科大考研题,(2),描述二,void exam2(),y=0;,x=5/y;,coutx,yendl;,这两段描述均不能满足算法的特征,试问它们违反了哪些特征？,解：,(1),算法是一个死循环,违反了算法的有穷性特征。,(2),算法包含除零错误,违反了算法的可行性特征。,算法的评价（设计准则）,正确性,除了应该满足算法说明中写明的,“,功能,”,之外，应对各组典型的带有苛刻条件的输入数据得出正确的结果。,健壮性,算法应对非法输入的数据作出恰当反映或进行相应处理，一般情况下，应向调用它的函数返回一个表示错误或错误性质的值。,可读性,易于理解、实现和调试。,高效性,执行时间短（,时间效率,）、占用存储空间少（空间效率）,时间复杂度,一般用算法中基本语句被执行的次数来表示算法的时间效率（,算法的时间复杂度,）。,例：分析下面程序段的时