资源描述
单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,数据结构,数据结构,是计算机专业的一门重要的专业基础课。它主要研究计算机加工对象的逻辑结构、在计算机中的表示形式以及实现各种基本操作的算法。它是学习操作系统、编译原理、数据库原理等计算机专业核心课程的基础,掌握好这门课程的内容,是学习计算机其他相关课程的必备条件。,开设本课程的背景,上课认真听讲;,仔细阅读教材中的大量例题,从而体会并最终,掌握数据结构中的基本概念;,独立完成每个章节后面的练习题。,本课程讲述的主要内容,本课程将分别讲述数据结构的基本概念、线性表、栈和队列、串和数组、树形结构、图结构、查找、排序等内容。,学习本课程的基本方法,第,1,章 绪论,1.1,什么是数据结构,1.2,基本概念和术语,1.3,抽象数据类型的表示和实现,1.4,算法和算法分析,一般来说,用计算机解决一个具体,问题时,大致需要经过下列几个步骤,:,1.,首先抽象出一个适当的数学模型,;,2.,设计一个算法,编出程序,;,3.,测试,调试程序,.,然而,更多的非数值计算问题无法,用数学方程加以描述,.,计算机的实质是,:,数据,处理机,数据处理机,输出结果数据,输入原始数据,1.1,什么是数据结构,数据结构,是一门研究,数据,组织,、,存储,和,运算,的一般方法的学科。,数据结构是一门研究,数据,组织,、,存储,和,运算,的一般方法的学科。,能输入到计算机中,并能被计算机程序处理的,符号的集合。,整数,(1,2),、,实数,(1.1,1.2),字符串,(Beijing),、,图形、声音。,数据结构是一门研究,数据,组织,、,存储,和,运算,的一般方法的学科。,计算机管理图书问题,在图书馆里有各种卡片:有按书名编排的、,有按作者编排的、有按分类编排,如何将查询图书的这些信息存入计算机中,既要考虑查询时间短,又要考虑节省空间,数据结构是一门研究,数据,组织,、,存储,和,运算,的一般方法的学科。,最简单的办法之一是建立一张表,,每一本书的信息在表中占一行,如,数据结构是一门研究,数据,组织,、,存储,和,运算,的一般方法的学科。,如何将,0,1,2,3,4,5,6,7,8,9,这,10,个数存放在,计算机中能最快地达到你所需要的目的?,目的不同,,最佳,的存储方法就不同,。,从大到小排列:,9,8,7,6,5,4,3,2,1,0,输出偶数:,0,2,4,6,8,数据元素在,计算机中的表示,数据结构是一门研究,数据,组织,、,存储,和,运算,的一般方法的学科。,对数据结构中的结点进行,操作处理,(,插入、删除、修改、查找、排序,),当今计算机应用的特点,:,所处理的数据量大且具有一定的关系;,对其操作不再是单纯的数值计算,而更多地是需要对其进行组织、管理和检索。,应用举例,1,学籍档案管理,假设一个学籍档案管理系统应包含如下表所示的学生信息。,“,学生,”,表格,特点:,每个学生的信息占据一行,所有学生的信息按学号顺序依次排列构成一张表格;,表中每个学生的信息依据学号的大小存在着一种前后关系,这就是我们所说的线性结构;,对它的操作通常是插入某个学生的信息,删除某个学生的信息,更新某个学生的信息,按条件检索某个学生的信息等等。,应用举例,2,输出,n,个对象的全排列,输出,n,个对象的全排列可以使用下图,1-1,所示的形式描述。,图,1-1 3,个对象的全排列过程,特点:,在求解过程中,所处理的数据之间具有层次关系,这是我们所说的树形结构;,对它的操作有:建立树形结构,输出最低层结点内容等等。,应用举例,3,制定教学计划,在制定教学计划时,需要考虑各门课程的开设顺序。有些课程需要先修课程,有些课程则不需要,而有些课程又是其他课程的先修课程。比如,计算机专业课程的开设情况如下表所示:,课程先后关系的图形描形式:,图,1-2,计算机专业必修课程开设先后关系,c1,c9,c4,c2,c12,c10,c11,c3,c6,c7,c8,c5,特点,课程之间的先后关系用图结构描述;,通过实施创建图结构,按要求将图结构中的顶点进行拓朴排序。,结论,计算机的操作对象的关系更加复杂,操作形式不再是单纯的数值计算,而更多地是对这些具有一定关系的数据进行组织管理,我们将此称为,非数值性,处理。要使计算机能够更有效地进行这些非数值性处理,就必须弄清楚这些操作对象的特点,在计算机中的表示方式以及各个操作的具体实现手段。这些就是,数据结构,这门课程研究的主要内容。,RETURN,1.2,基本概念和术语,数据,(,data,),是描述客观事物的数字、字符、以及所有能输入到计算机中,被计算机,识别,和,处理,的符号的集合。是计算机操作的对象的总称。,数值性数据,非数值性数据,是数据结构中讨论的基本单位,在计算机中通常作为一个整体进行考虑和处理。,数据元素,:,有时一个数据元素可由若干个数据项组成,如,:,记录,/,结构。,(data element),数据的不可分割的最小单位,如结构中的域。,数据项,:,如,:,学籍记录中的每一项,(,学号、姓名等,),。,(data item),数据对象,(data object),数据的子集。具有相同性质的数据成员(数据元素)的集合。,整数数据对象,N,=0,1,2,数据结构,(data,strucure,),定义,:,是相互之间存在一种或多种特定关系的数据元素的集合,它包括数据元素的逻辑关系,(,逻辑结构,),、数据元素在计算机中的存储表示,(,存储结构,),、数据元素的,运算,三个方面。,常见的数据结构有:,集合,、,线性结构,、,树形 结构,和,图结构(网状结构),。,逻辑结构,数据结构中所说的“关系”实际上是指数据元素之间的,逻辑关系,,是对数据元素之间的逻辑关系的描述,它可以用一个数据元素的集合和定义在此集合上的若干关系来表示。,线性结构,树形结构,图结构,集合结构,四种基本结构,(逻辑结构),集合,:元素仅属于同一个集合,没有其他关系。,线性结构,:,存在一对一 关系,序列相邻,次序关系。,树形结构,:,存在一对多关系,层次关系。,图状结构(网状结构),:,存在多对多关系,任意性。,数据结构的形式定义描述,为,:,数据结构,是一个二元组,Data_Structures=(D,R),其中,:D,是数据元素的有限集,,R,是,D,上关系的有限集,即是该对象中所有数据成员之间的关系的有限集合。,1,4,2,3,G1=D,R,D=1,2,3,4,R=(1,2),(1,3),(1,4),(2,3),(3,4),(2,4),2,1,3,G2=D,R,D=1,2,3,R=,图结构,结点间的连结是任意的,存储结构(物理结构),是指数据结构在计算机存储器中的具体实现。与孤立的数据元素表示形式不同,数据结构中的数据元素不但要表示其本身的实际内容,还要表示清楚数据元素之间的逻辑结构。,常见的存储结构,顺序存储结构,:特点是借助于数据元素的相对存储位置来表示数据元素之间的逻辑结构;,链式存储结构,:,特点是借助于指示数据元素地址的指针表示数据元素之间的逻辑结构。,关系的映象方法:,(,表示,x,y,的方法,),顺序存储,以相对的存储位置表示后继关系,例如,:,令,y,的存储位置和,x,的存储位置之间差一个常量,m,而,m,是一个隐含值,,整个存储结构中只含数据元素本身的信息,x y,元素,n,.,元素,i,.,元素,2,元素,1,L,o,Lo+m,Lo+(i-1)*m,Lo+(n-1)*m,存储地址,存储内容,Loc(a)=Lo+(i-1)*m,顺序存储,m,是每个元素所,占用的存储单元,个数,元素,n,.,元素,i,.,元素,2,元素,1,存储内容,顺序存储结构常用于线性结构,将逻辑上相邻的数据元素存储在物理上相邻的存储单元里。,顺序存储结构的三个弱点:,1.,作插入或删除操作时,需移动大量元数。,2.,长度变化较大时,需按最大空间分配。,3.,表的容量难以扩充。,链式存储,以附加信息,(,指针,),表示后继关系,需要用一个和,x,在一起的,附加信息,指示,y,的存储位置,y x,h,1536,元素,2,1400,元素,1,1346,元素,3,元素,4,1345,链式存储,每个结点都由两部分组成:,数据域,和,指针域,。,数据域,存放元素本身的数据,,指针域,存放指针。,数据元素之间逻辑上的联系由指针来体现,。,1346,元素,3,1536,.,.,.,1536,元素,2,1400,.,.,.,元素,4,1346,1400,元素,1,1345,指针,存储内容,存储地址,1536,元素,2,1400,元素,1,1346,元素,3,元素,4,head,链式存储,1345,1536,元素,2,1400,元素,1,1346,元素,3,元素,4,1345,h,链式存储,1.,比顺序存储结构的存储密度小,(,每个结点都由数据域和指针域组成,),。,2.,逻辑上相邻的结点物理上不必相邻。,3.,插入、删除灵活,(,不必移动结点,只要改变结点中的指针,),。,链接存储结构特点:,1,数据的逻辑结构,2,、数据的存储结构,3,、数据的运算:检索、排序、插入、删除、修改等。,B.,线性结构,A,顺序存储,B,链式存储,线性表,栈,队列,C.,树形结构,D.,图结构,数据结构的三个方面,A.,集合,树,二叉树,C,索引存储,D,散列存储,数据类型,在用高级程序语言编写的程序中,必须对程序中出现的每个变量、常量或表达式,明确说明它们所属的数据类型。,定义:,一组性质相同的值的集合,以及定义于这个值集合上的一组操作的总称,.,例如,,C,语言中提供的基本数据类型有,:,整型,int,浮点型,float,字符型,char,逻辑型,bool,(,C+,语言),双精度型,double,数据类型,:,是一个,值的集合,和定义在此集合上的,一组操作,的总称。,不同类型的变量,其所能取的值的范围不同,所能进行的操作不同。,例如:整型,值的范围是:,-32768,32767,操作是:,+,,,-,,*,,/,,,%,各种高级程序设计语言中都拥有“整数”类型,尽管它们在不同处理器上实现的方法不同,但对程序员而言是“相同的”,因为它们的数学特性相同。,从“数学抽象”的角度看,可称它为一个,“,抽象数据类型,”,。,抽象数据类型,(ADT:Abstract Data Types),由用户定义,用以表示应用问题的,数据模型,由基本的,数据类型,组成,并包括,一组相关的操作,(或称服务),信息隐蔽,和,数据封装,,使用与实现相分离,例如,:,“,整数,”,是一个抽象数据类型。,其数学特性和具体的计算机或语言无关。,“,抽象,”,的意义在于强调数据类型的数学特性。,抽象数据类型还包括用户在设计软件系统时自己定义的数据类型。,在,构造软件系统的各个相对独立的模块时,定义,一组数据,和施与这些数据之上的,一组操作,,并在模块,内部,给出它们的,表示和实现细节,,在模块,外部,使用的只是,抽象的数据和抽象的操作,。,例如,,定义抽象数据类型,“,复数,”,数据对象:,D,e1,e2,e1,e2RealSet ,数据关系:,R1,|e1,是复数的实数部分,|e2,是复数的虚数部分,ADT Complex,基本操作:,AssignComplex,(&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,ADT,有两个重要特征,:,数据抽象,用,ADT,描述程序处理的实体时,强调的是其,本质的特征,、,其所能完成的功能,以及它和,外部用户的接口,(即,外界使用它的方法,),数据封装,将实体的,外部特性和其内部实现细节分离,,并且,对外部用户隐藏,其内部实现细节,抽象数据类型的描述方法,抽象数据类型可用,(,D,,,S,,,P,),三元组,表示,其中,,D,是数据对象,,S,是,D,上的关系集,,P,是对,D,的基本操作集。,ADT,抽象数据类型名,数据对象:,数据对象的定义,数据关系:,数据关系的定义,基本操作:,基本操作的定义,ADT,抽象数据类型名,其中基本操作的定义格式为,:,基本操作名,(参数表),初始条件:,初始条件描述,操作结果,:,操作结果描述,赋值参数,只为操作提供输入值;,引用参数,以,&,打头,除可提供输入值外,,还将返回操作结果。,初始条件,描述了操作执行之前数据结构和参数应满足的条件,若不满足,则操作失败,并返回相应出错信息。,操作结果,说明了操作正常完成之后,数据结构的变化状况和应返回的结果。若初始条件为空,则省略之。,1.3,抽象数据类型的表示和实现,抽象数据类型需要通过,固有数据类型,(,高级编程语言中已实现的数据类型,),来实现。,例如,对以上定义的复数,typedef,struct,float,realpart,;,float,imagpart,;,complex,;,/-,存储结构的定义,-,/-,基本操作的函数原型说明,void,Assign(complex,&,Z,float,realval,float,imagval,),;,/,构造复数,Z,其实部和虚部分别被赋以参数,/,realval,和,imagval,的值,float,GetReal,(complex Z),;,/,返回复数,Z,的实部值,float,Getimag,(,complex,Z),;,/,返回复数,Z,的虚部值,void,add(complex z1,complex z2,complex&sum),;,/,以,sum,返回两个复数,z1,z2,的和,/-,基本操作的实现,-,void,add(complex z1,complex z2,complex,&,sum),/,以,sum,返回两个复数,z1,z2,的和,sum.realpart,=z1.realpart+z2.realpart;,sum.imagpart,=z1.imagpart+z2.imagpart;,其它省略,算法的描述,选择算法描述语言的准则,(,1,)该语言应该具有描述数据结构和算法的基本功能;,(,2,)该语言应该尽可能地简捷,以便于掌握、理解;,(,3,)使用该语言描述的算法应该能够比较容易地转换成任何一种程序设计语言。,“类,C”,描述语言,是通过对,C,语言进行精心筛选保留的一个核心子集,并为了便于描述,又做了若干扩展修改,它介于伪码和,C,语言之间,从而,增强了语言的描述功能。,1.,预定义常量及类型,#define TRUE 1,#define FALSE 0,#define OK 1,#define ERROR 0,#define INFEASIBLE -1,#define OVERFLOW -2,/,Status,是函数的类型,其值函数结果状态代码,typedef,int,Status,数据结构的表示(存储结构),用类型定义,typedef,描述。数据元素类型约定为,ElemType,,,由用户在使用该数据类型时自行定义。,3.,基本操作的算法都用以下形式的函数描述:,函数类型 函数名(函数参数表),/,算法说明,语句序列;,/,函数名,为了简化函数的书写,提高算法描述的清晰度,我们规定除函数参数表中的参数需要说明数据类型外,函数中使用的局部变量可以不做变量说明,必要时给出相应的注释即可。另外,在书写算法时,应该养成对重点语句段落添加注解的良好习惯。在形参表中,以,&,打头的为引用参数。,4.,赋值语句有:,简单赋值,变量名,=,表达式,;,串联赋值,变量名,1=,变量名,2=.=,变量名,n=,表达式;,成组赋值,(变量名,1,,,.,,变量名,n,),=,(,表达式,1,,,.,,表达式,n,);,结构赋值,结构名,1=,结构名,2,;,结构名,=,(值,1,,值,2,,,.,,值,n,);,变量名,=,表达式,;,变量名,起始下标,.,终止下标,=,变量名,起始,下标,.,终止下标,交换赋值,变量名,1,变量名,2,;,条件赋值,变量名,=,条件表达式,?,表达式,T,:,表达式,F,;,5.,选择语句有:,条件语句,1,if,(,表达式)语句;,条件语句,2,if,(,表达式)语句;,else,语句;,开关语句,1,switch,(,表达式,),case,值,1,:语句序列,1,;,break,;,case,值,2,:语句序列,2,;,break,;,.,case,值,n,:,语句序列,n,;,break,;,default,:,语句序列,n+1,;,开关语句,2,switch ,case,条件,1,:语句序列,1,;,break,;,case,条件,2,:语句序列,2,;,break,;,.,case,条件,n,:,语句序列,n,;,break,;,default,:,语句序列,n+1,;,6.,循环语句有:,for,语句,for,(,表达式,1,;条件;表达式,2,)语句;,while,语句,while,(,条件)语句;,do-while,语句,do,语句序列;,while,(,条件);,7.,结束语句有:,函数结束语句,return,表达式;,return;,case,结束语句,break;,异常结束语句,exit,(,异常代码);,8.,输入和输出语句有:,输入语句,scanf,(,格式串,,变量名,1,,,.,,变量名,n),;,输出语句,printf,(,格式串,,表达式,1,,,.,,表达式,n);,通常省略格式串。,9.,注释格式为:,单行注释,/,文字序列,10.,基本函数有:,求最大值,max,(,表达式,1,,,.,,表达式,n,);,函数返回参数表中,n,个表达式结果中的最大值。,求最小值,min,(,表达式,1,,,.,,表达式,n,);,函数返回参数表中,n,个表达式结果中的最小值。,求绝对值,abs,(,表达式);,函数返回表达式的绝对值。,求不足整数值,floor,(,表达式);,函数返回不大于表达式的最大整数值。,求进位整数值,ceil,(,表达式);,函数返回不小于表达式的最小整数值。,判定文件结束,eof,(,文件变量)或,eof,;,判定行结束,eoln,(,文件变量)或,eoln,;,11.,逻辑运算约定:,与运算,&:,对于,A&B,,,当的值为时,不再对求值。,或运算,|:,对于,A|B,,,当的值为非时,不再对求值。,return,1.4,算法和算法分析,1,算法的概念,定义:,是对特定问题求解步骤的一种描述。,设计算法的基本过程,通过对问题进行详细地分析,抽象出相应的数学模型;,确定使用的数据结构,并在此基础上设计对此数据结构实施各种操作的算法;,选用某种语言将算法转换成程序;,调试并运行这些程序。,算法应该具有下列五个特性,(,1,)有穷性:,一个算法必须在执行有穷步之后结束。,(,2,)确定性:,算法中的每一步,必须有确切的含义,在他人理解时不会产生二义性。,(,3,)可行性:,算法中描述的每一步操作都可以通过已有的基本操作执行有限次实现。,(,4,)输入:,一个算法应该有零个或多个输入。,(,5,)输出:,一个算法应该有一个或多个输出。,2,算法设计的要求,正确性,可读性,健壮性(容错性),效率与低存储量,设计算法时,通常应考虑达到以下目标:,正确性,首先,,算法应当,满足,以特定的,“,规格说明,”,方式给出的,需求,。,其次,,对算法是否,“,正确,”,的,理解可以有以下,四个层次,:,a,程序中不含语法错误;,b,程序对于几组输入数据能够得出满足要求的结果;,c,程序对于精心选择的、典型、苛刻且带有刁难性的几组输入数据能够得出满足要求的结果;,d,程序对于一切合法的输入数据都能得出满足要求的结果;,可读性,算法主要是为了人的,阅读与交流,,,其次才是为计算机执行。因此算法应该,易于,人的,理解,;另一方面,晦涩难读的程序易于隐藏较多错误而难以调试;,健壮性,当,输入的数据,非法,时,算法应当恰当地作出反映或,进行相应处理,,而不是产生莫名奇妙的输出结果。并且,,处理出错的方法,不应是中断程序的执行,而应是,返回,一个,表示错误或错误性质的值,,以便在更高的抽象层次上进行处理。,高效率与低存储量需求,通常,效率指的是,算法执行,时间,;存储量指的是算法执行过程,中,所需的最大存储空间,。两者都与,问题的规模有关。,3,算法效率的度量,通常有,两种,衡量算法效率的方法,:,事后统计法,缺点:,1,。必须执行程序,2,。其它因素掩盖算法本质,事前分析估算法,和算法执行,时间,相关的,因素,:,1,算法选用的策略,2,问题的规模,3,编写程序的,语言,4,编译,程序产生的机器代码,的质量,5,计算机,执行指令,的速度,一个特定,算法的,“,运行工作量,”,的大小,只依赖于,问题的规模,(通常用整数量,n,表示),或者说,,它,是问题规模的函数,。,假如,随着问题规模,n,的增长,,算法执行时间的增长率和,f(n),的增长率相同,,则可记作:,T(n)=O(f(n),称,T(n),为算法的,(,渐近,),时间复杂度,如何估算,算法的时间复杂度?,时间特性的分析,如果我们将一个算法所花费的时间设计成一个以数据量,n,为自变量的函数,T(n),,,这个函数在正整数定义域范围内一定是单调递增的。好的算法应该能够在数据量,n,增长的同时,函数,T(n),的增长速度比较缓慢。,从算法中选取一种对于所研究的问题来说是,基本操作,的原操作,以该基本操作,在算法中重复执行的次数,作为算法运行时间的衡量准则。,(,a,),+x;s=0,;,+x,的频度为,1,(,b,),for(i=1;i=n;+i),+x;s+=x;,+x,的频度为,n,(,c,),for(j=1;j=n;+j),for(k=1;k=n;+k),+x;s+=x;,+x,的频度为,n,2,时间复杂度,:,O(1),时间复杂度,:,O(n),时间复杂度,:,O(n,2,),两,个,矩,阵,相,乘,void,mult(,int,a,int,b,int,&,c),/,以二维数组存储矩阵元素,,c,为,a,和,b,的乘积,for,(i=1;i=n;+i),for,(j=1;j=n;+j),ci,j=0;,for,(k=1;k=n;,+,k),ci,j+=,ai,k,*,bk,j;,/for,/,mult,基本操作,:,乘法,操作,时间复杂度,:,O(n,3,),例,二,选,择,排,序,void,select_sort(,int,&,a,int,n),/,将,a,中整数序列重新排列成自小至大有序的整数序列,。,/select_sort,基本操作,:,比较,(,数据元素,),操作,时间复杂度,:,O(n,2,),j=i;,/,选择第,i,个最小元素,for,(k=i+1;k n;,+,k),if,(ak,aj),j=k;,for,(i=0;i1,&,change,;-i),/bubble_sort,基本操作,:,赋值,操作,时间复杂度,:,O(n,2,),change=FALSE;,/change,为元素进行交换标志,for,(j=0;j aj+1),aj,aj+1;,change=TRUE,;,/,一趟起泡,算法的存储空间需求,算法的,空间复杂度定义为,:,表示随着问题规模,n,的增大,,算法运行所需存储量的增长率,与,g(n),的增长率相同。,S(n)=O(g(n),算法的存储量,包括,:,1,输入数据,所占空间,2,程序本身,所占空间,;,3,辅助变量,所占空间,。,1.,熟悉各名词、术语的含义,掌握基本概念。,2.,理解算法五个要素的确切含义。,本章学习要点,3.,掌握计算语句频度和估算算法时间复杂度的方法。,1.1 1.5 1.6,本章作业,(P72),
展开阅读全文