资源描述
单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,1,数据结构,Data,Structure,2,第,1,章 绪论,1.1,什么是数据结构,1.2,基本概念和术语,1.3,抽象数据类型的表示和实现,1.4,算法和算法分析,3,计算机的,功能,:,处理信息,(,数据,包括数字、字符、声音、图形、图像等等,),4,计算机是一门研究用计算机进行信息表示和处理的科学。,信息的表示,信息的处理,而信息的表示和组成又直接关系到处理信息的程序的效率。,随着计算机的普及,信息量的增加,信息范围的拓宽,使许多系统程序和应用程序的规模很大,结构又相当复杂。,因此,为了编写出一个“好”的程序,必须分析待处理的对象的特征及各对象之间存在的关系,这就是数据结构这门课所要研究的问题。,5,计算机的,应用,:科学计算,非数值计算的处理工作,处理对象,:数值数据,数值数据数据 非数值数据学习目的:合理组织数据、高效处理数据,计算机的应用由进行各种各样的,科学计算,发展为,文档处理、数据处理、图像处理、硬件设计、软件设计,等等。,6,1.1,什么是数据结构,对于一个课题,在计算机领域,一般遵循下面的解决原则:,需求分析,总体设计,模块分割,建立数学模型,解数学模型的算法,程序编制,调试,结果,数据结构涉及到:数学模型的建立和对该模型具体实现的对应的算法。,7,Niklaus Wirth,:,Algorithm+Data Structures=Programs,程序设计,:,为计算机处理问题编制一组指令集,算法,:,处理问题的策略,数据结构,:,问题的数学模型,例,:,求一组,(n,个,),整数中的最大值,算法,:,基本操作是“比较两个数的大小”,模型:?,8,在应用程序中涉及到各种各样的数据,如何在计算机中组织、存储、传递数据,需要讨论它们的归类及它们之间的关系,从而建立相应的数据结构,依此实现软件功能。,描述这类非数值计算问题的数学模型不是数学方程,而是树、表和图之类的数据结构。,eg.,数学模型,:,数学方程、表格、树、图,9,地位,:,“,数据结构”在计算机科学中是一门综合性的专业基础课。,数据结构是介于数学、计算机硬件和计算机软件三者之间的一门核心课程。,数据结构这一门课的内容不仅是一般程序设计,(,特别是非数值性程序设计,),的基础,而且是设计和实现编译程序、操作系统、数据库系统及其他系统程序的重要基础。,10,1.2,基本概念和术语,数据,Data,:,是对客观事物的符号表示,在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称,(,数字、字符、声音、图形、图像等等,),。,11,eg.,一个个人书库管理程序所要处理的数据为如下所示的表格:,书号,书名,作者,购书日期,价格,TP105,数据结构题集,严蔚敏,2002.4,21.00,TP42,软件工程,冯玉林,2003.6,28.00,TP51,数据结构,严蔚敏,2003.1,27.00,12,数据元素,Data Elememt,:,数据的基本单位,在计算机程序中常常作为一个整体进行考虑和处理。,eg.,每一行代表一本书,作为一个,基本单位,,即每一行为一个数据元素,上述表格数据由,n,个数据元素组成。,数据项,Data Item,:,一个数据元素由若干个数据项组成。,数据项是数据的不可分割的,最小单位,。,eg.,上述一个数据元素由,5,个数据项组成。,13,数据对象,Data Object,:,性质相同的数据元素的集合,是数据的一个子集。,eg.,整数的数据对象是,,,-3,,,-2,,,-1,,,0,,,1,,,2,,,3,,,英文字符类型的数据对象是,A,,,B,,,C,,,D,,,E,,,F,,,14,数据结构,Data Structure,:是相互之间存在一种或多种特定关系的数据元素的集合。数据元素之间不是相互独立的,他们之间有某种特定的关系,这种数据元素之间的关系,称为“,结构,”,Structure,。,15,四种基本结构,(,逻辑结构,)p5,集合,:,元素仅属于同一个集体,没有其他关系。,eg.,同班关系,线性结构,:,存在一对一 关系,序列相邻,次序关系。,eg.,大小关系,树型结构,:,存在一对多关系,层次关系。,eg.,家族关系,图状结构,(,网状结构,),:,存在多对多关系,任意性,eg.,交通图,16,数据结构的形式定义:,数据结构是一个二元组:,Data-Structure=(D,,,S),其中:,D,是数据元素的有限集,,S,是,D,上关系的有限集。,数学描述,即数学模型,eg.,复数的数据结构定义如下:,Complex=(C,,,R),其中:,C,是含两个实数的集合,C1,,,C2,,分别表示复数的实部和虚部。,R=P,,,P,是定义在集合上的一种关系,。,17,结构中描述的关系是数据元素之间的逻辑关系,因此又称为数据的,逻辑结构,.,数据的逻辑结构又分为线型结构和非线性结构两大类,.,线性结构数据的逻辑结构 非线性结构,18,对于任意一个逻辑结构,S=(D,,,R),,若,aD,,,bD,,,(a,,,b)R,,则称,a,是,b,的,前驱,,,b,是,a,的,后继,;若某结点没有前驱,则称该结点为,开始结点,;若某结点没有后继,则称该结点为,终端结点,。,序偶,(),19,1,2,3,4,5,在,线性结构,中,除了开始结点和终端结点外,其余结点有且仅有一个前驱,有且仅有一个后继,.,eg.,图示法,20,非线性结构分为树形结构和图状结构,.,树形结构非线性结构 图状结构,在,树形结构,中,每个结点最多只有一个前驱,但可以有多个后继,可以有多个终端结点,.,在,图状结构,中,每个结点的前驱和后继的数目可以是任意的,因此,可能没有开始结点和终端结点,也可能有多个开始结点和终端结点。,21,a,b,c,d,e,a,b,c,d,e,eg.,树形结构 图状结构,22,bin,dev,etc,lib,user,2,1,14,13,12,11,2,3,4,6,7,8,9,10,3,1,5,8,7,10,11,9,9,8,7,4,5,6,6,2,3,13,1,5,5,线性结构,树形结构,树 二叉树 二叉排序树,Eg.,23,堆结构,12,3,5,4,8,7,11,10,2,9,1,6,1,2,5,6,4,3,1,2,5,4,3,6,11,33,18,14,6,6,5,19,21,图结构 网络结构,24,数据的逻辑结构,从逻辑关系上描述数据,与数据的存储无关;,从具体问题抽象出来的数据模型;,与数据元素本身的形式、内容无关;,与数据元素的相对位置无关。,25,讨论数据结构的目的是为了在计算机中实现对它的操作,因此还需研究如何在计算机中表示它。,数据结构在计算机中的表示称为数据的,物理结构,(,又称,映像,或,存储结构,),,即逻辑结构到存储器的一个映射。它包括数据元素的表示和关系的表示。,数据元素的表示,物理结构,关系的表示,26,计算机使用,0,和,1,两个二进制数字,表示信息的最小单位是二进制的一位,叫做,位,Bit,。计算机的信息单位还有字节和字。一个,字节,由,8,位二进制信息组成,一个,字,至少由一个以上的字节组成。,位 信息单位 字节 字,27,在计算机中,用一个若干位组合起来形成的一个位串表示一个数据元素,通常称这个位串为,元素,Element,或,结点,Node,。当数据元素由若干数据项组成时,位串中对于各个数据项的子位串成为,数据域,Data Field,。,逻辑结构,:,数据元素 数据项,|,物理结构,:,元素,/,结点 数据域,28,数据元素之间的关系在计算机中有两种不同的表示方法,:,顺序映像和非顺序映像,|,顺序存储结构 链式存储结构,数据元素的表示物理结构 关系的表示,29,1.,顺序映像,特点,:,借助元素在存储器中的,相对位置,来表示元素之间的逻辑关系。,以,x,和,y,存储位置的相对关系表示有序对,最简单的方法就是使,y,和,x,的存储位置之间差一个常量,C,,,而,C,是一个隐含值,整个存储结构中只含数据元素本身的信息。,30,Eg.,线性结构,list:,设每个结点占用一个存储单元,数据从,200,号单元开始从低地址向高地址存放,.,存储结构如图所示,:,1,2,3,4,5,1,2,3,4,5,200,201,202,203,204,31,设每个结点占用,两,个存储单元,数据从,200,号单元开始从低地址向高地址存放,.,存储结构如图所示,:,200,201,202,203,204,206,207,208,209,210,1,2,3,4,5,32,2.,非顺序映像,特点,:,借助指示元素存储地址的,指针,Pointer,表示元素之间的逻辑关系,.,x,和,y,的存储位置随意,则需要用一个和,x,在一起的附加信息指示,y,的存储位置,这个附加信息和,x,绑定在一起,此时,两者合在一起作为,x,的存储映象。,33,Eg.,每个结点占用两个单元,一个存放结点的数值,另一个存放后继结点的地址,.,存储结构如图所示,:,1 236,3 308,5 ,2 202,4 214,209,202,214,236,308,结点的数值,后继结点的地址,34,存储密度,紧凑结构:所有的空间都存储数据元素,非紧凑结构:有附加的信息,附加的信息会带来其他的优势,选择数据的存储结构,数据操作花费的时间少,占用的存储空间小,一般情况,时间优于空间,35,数据类型,Data Type,是一个值的集合和定义在这个值集上的一组操作的总称。原子类型数据类型 结构类型,36,数据类型,基本类型,构造类型,整型,字符型,实型,(,浮点型,),枚举类型,指针类型,空类型,单精度型,双精度型,数组类型,结构体类型,共用体类型,C,语言中的数据类型,:,37,抽象数据类型,Abstract Data Type,,简称,ADT,,是指一个数据模型和定义在该模型上的一组操作。,每一个操作由它的输入和输出定义。抽象的与具体的相对应。,eg.int a,b;,则,a,和,b,可以进行,+,、,-,、*、,/,的运算,,,-2,,,-1,,,0,,,1,,,2,,,则是具体的,int,型数据,例如:,矩阵,+,(求转置、加、乘、求逆、求特征值),构成一个矩阵的抽象数据类型,数据结构,+,定义在此数据结构上的一组操作,=,抽象数据类型,38,原子类型抽象数据类型 固定聚合类型 结构类型 可变聚合类型,39,抽象数据类型可用(,D,,,S,,,P,)三元组表示,其中,,D,是数据对象,,S,是,D,上的关系集,,P,是对,D,的基本操作集。,ADT,抽象数据类型名,数据对象:,数据对象的定义,数据关系:,数据关系的定义,基本操作:,基本操作的定义,ADT,抽象数据类型名,其中,数据对象和数据关系的定义用伪码描述,40,基本操作的定义格式为,基本操作名(参数表),初始条件:,初始条件描述,操作结果:,操作结果描述,基本操作有两种参数:赋值参数只为操作提供输入值;引用参数以,&,打头,除可提供输入值外,还将返回操作结果。,“初始条件”描述了操作执行之前数据结构和参数应满足的条件,若不满足,则操作失败,并返回相应出错信息。,“操作结果”说明了操作正常完成之后,数据结构的变化状况和应返回的结果。若初始条件为空,则省略之。,41,数据结构的划分,(1),按数据结构的性质划分,数据的逻辑结构,数据元素之间的逻辑关系,(,设计算法,数学模型,),数据的物理结构,数据结构在计算机中的,映像,(,存储结构,算法的实现,),42,(2),按数据结构在计算机内的存储方式来划分,顺序存储结构,借助元素在存储器的相对位置来表示数据元素之间的逻辑关系。,链式存储结构,借助指示元素存储地址的指针表示数据元素之间的逻辑关系。,索引存储方法:在存储结点的同时,还建立附加 的索引表,索引表中的每一项称为索引项,形式为:关键字,地址。,散列存储方法:根据结点的关键字直接计算出该结点的存储地址。,说明:四种存储方法可结合起来对数据结构进行存储映像。,43,(3),按数据结构的操作来划分,静态结构,经过操作后,数据的结构特征保持不变,(,如数组,),。,半静态结构,经过操作后,数据的结构特性只允许很小变迁,(,如栈、队列,),。,动态结构,经过操作后,数据的结构特性变化比较灵活,可随机地重新组织结构,(,如指针,),。,44,1.3,抽象数据类型的表示与实现,用来写算法的方式有好几种:,1.,条例式的步骤,2.,流程图,Flow Char,3.,伪码,Pseudo Code,学习数据结构必须与实际应用相结合,使用伪代码讲授可能增加了学生上机实践的难度。,4.,程序语句,本书讨论的数据结构及其算法采用介于伪码和,C,语言之间的类,C,语言作为描述工具。,45,例、求两个整数,m,、,n(mn),的最大公因子,46,开始,输入,m,、,n,整除,m/n,,求余数,r,r=0?,打印,n,结束,mn,nr,是,否,流程图,47,【,求余数,】,以,n,除,m,,并令,r,为余数,(0rn),;,余数是否为,0,若,r=O,则结束算法,,n,就是最大公因子;,替换并返回,a,若,r0,则,mn,,,nr,返回,a,。,条例式的步骤,48,程序语句,int max common factor(int m,,,int n)int r,;,r=m%n,;,while(r!=O),m=n,;,n=r,;,r=m,n,;,return n,;,49,P16,P23,50,1,预定义常量和类型:,#define TRUE 1,;,#define FALSE -1,;,#define ERROR NULL,;,51,2,函数的形式,数据类型,函数名,(,形式参数,),形式参数说明;,内部数据说明;,执行语句组;,/*,函数名*,/,函数的定义主要由函数名和函数体组成,函数体用花括号“,”,和“,”,括起来。,函数中用方括号括起来的部分为可选项,函数名之间的圆括号不可省略。,函数的结果可由指针或别的方式传递到函数之外。,执行语句可由各种类型的语句所组成,两个语句之间用“;”号分隔。,可将函数中的表达式的值通过,return,语句返回给调用它的函数。,最后的花括号“,”,之后的,/*,函数名*,/,为注释部分,可舍。,52,3,赋值语句,简单赋值,:,=,,它表示将表达式的值赋给左边的变量;,+,,它表示变量加,1,后赋值给变量;,-,,它表示变量减,1,后赋值给变量;,53,成组赋值,:,1.(,,,,,),=(,,,,,,,),;,2.,下标,1,下标,2=,下标,1,下标,2,54,串联赋值,:,=,;,条件赋值,:,=,?,:,;,交换赋值,:,,表示变量,1,和变量,2,互换;,55,4,条件选择语句,if (),语句;,if (),语句,1,;,else,语句,2,;情况语句,switch (),case,判断值,1;,语句组,1,;,break;,case,判断值,2;,语句组,2,;,break;,case,判断值,n;,语句组,n,;,break,;,default,:语句组;,break,;,注意:,switch case,语句是先计算表达式的值,然后用其值与判断值相比较,若它们相一致时,就执行相应的,case,下的语句组;若不一致,则执行,default,下的语句组;其中的方括号代表可选项。,56,5,循环语句,for,语句,for(,;,;,),循环体语句;,首先计算表达式,1,的值,然后求表达式,2,的值,若结果非零则执行循环体语句,最后对表达式,3,运算,如此循环,直到表达式,2,的值为零时止。,57,while,语句,while(),循环体语句;,while,循环首先计算条件表达式的值,若条件表达式的值非零,则执行循环体语句,然后再次计算条件表达式,重复执行,直到条件表达式的值为假时退出循环,执行该循环之后的语句。,58,do-while,语句,do,循环体语句,while(),该循环语句首先执行循环体语句。然后再计算条件表达式的值,若条件表达式成立,则再次执行循环体,再计算条件表达式的值,直到条件表达式的值为零,即条件不成立时结束循环。,59,6,输入、输出语句,输入语句:用函数,scanf,实现,特别当数据为字符时,用,getchar,函数实现。,输出语句:用,printf,函数实现,当要输出字符数据时,用,putchar,函数实现。,60,7,其他一些语句,(1)return,表达式或,return,:用于函数结束。,(2)break,语句:可用在循环语句或,case,语句中结束循环过程或跳出情况语句。,(3)exit,语句:表示出现异常情况时,控制退出语句。,8,注释形式,可用,/*,字符串*,/,或者 单行注释 或,/,文字序列。,61,9,一些基本的函数,如:,max,函数,用于求一个或几个表达式中的最大值;,min,函数,用于求一个或几个表达式中的最小值;,abs,函数,用于求表达式的绝对值;,eof,函数,用于判定文件是否结束;,eoln,函数,用于判断文本行是否结束。,62,例,.,计算,f=1!+2!+3!+n!,,,用,C,语言描述。,void factorsum(int n),int i,,,j,;,int f,,,w,;,f=0,;,for(i=1,;,i=n,;,i+),w=1,;,for(j=1;,;,j=i,;,j+),w=w*j,;,f=f+w,;,return,;,上述算法所用到的运算有乘法、加法、赋值和比较,其基本运算为乘法操作。在上述算法的执行过程中,对外循环变量,i,的每次取值,内循环变量,j,循环,i,次。因为内循环每执行一次,内循环体语句,w=w*j,只作一次乘法操作,即当内循环变量,j,循环,i,次时,内循环体的语句,w=w*j,作,i,次乘法。所以,整个算法所作的乘法操作总数是:,f(n)=1+2+3+n=n(n+1)/2,。,63,1.4,算法和算法分析,1.4.1,算法,Algorithm,p13,算法,指一系列确定的而且是在有限步骤内能完成的操作。,算法的重要特性,P13,(1),有穷性,Finiteness,:,能执行结束,,对于任意一组合法输入值,在执行有穷步骤之后一定能结束,即:算法中的每个步骤都能在,有限,时间内完成;,64,(2),确定性,Definiteness,:,对于每种情况下所应执行的操作,在算法中都有确切的规定,使算法的执行者或阅读者都能明确其含义及如何执行。并且在任何条件下,算法都只有一条执行路径;,每一条指令不会产生二义性,对于相同的输入执行相同的路径,(3),可行性,(,有效性,),Effectiveness,:,算法中的所有操作都必须足够基本,都可以通过已经实现的基本操作运算有限次实现之;,65,(4),输入,Input,:,0,至多个输入,作为算法加工对象的量值,通常体现为算法中的一组变量。有些输入量需要在算法执行过程中输入,而有的算法表面上可以没有输入,实际上已被嵌入算法之中;,(5),输出,Output,:,1,至多个输出,它是一组与“输入”与确定关系的量值,是算法进行信息加工后得到的结果,这种确定关系即为算法的功能,66,问题:操作系统程序是不是算法?,如操作系统,只要系统不遭破坏,它就永远不会停止,即使没有作业要处理,仍处于一个等待循环中,等待新作业的进入。因此操作系统程序不是一个算法。,67,1.4.2,算法设计的要求,p13p14,(1),正确性,Correctness,算法应满足具体问题的需求。,首先,算法应当满足以特定的“规格说明”方式给出的需求。,68,其次,对算法是否“正确”的理解可以有以下四个层次:,a,程序中不含语法错误;,b,程序对于几组输入数据能够得出满足要求的结果;,c,程序对于精心选择的、典型、苛刻切带有刁难性的几组输入数据能够得出满足要求的结果;,d,程序对于一切合法的输入数据都能得出满足要求的结果;,通常以第,c,层意义的正确性作为衡量一个算法是否合格的标准。,69,(2),可读性,Readability,算法首先是给人读,然后才是机器执行。算法应该好读,以有利于阅读者对程序的理解。,(3),健壮性,Robustness,/,容错性,算法应具有容错处理。当输入非法数据时,算法应对其作出反应,而不是产年莫名其妙的输出结果。并且,处理出错的方法不应是中断程序的执行,而应是返回一个表示错误或错误性质的值,以便在更高的抽象层次上进行处理。,70,(,1,),71,(4),效率与低存储量需求,效率,指的是算法的执行时间。,计算机的资源,最重要的是运算所需的时间和存储程序和数据所需的空间资源。,一个“好”的算法,运行时间较短,占用较少的存储空间。一般,这两者与,问题的规模,有关。,72,1.4.3,算法效率的度量,一个算法如果能在所要求的资源限制内将问题解决好,则称这个算法是有效率的。,对一个算法要作出全面的分析可分成两个阶段进行,即,事先分析,和,事后测试,p14,1),事前分析估算法,(,事先分析,),2),事后统计法,(,事后测试,),73,1),事前分析估算法,(,事先分析,),和算法执行时间相关的因素:,1,算法选用的策略,2,问题的规模,3,编写程序的语言,4,编译程序产生的机器代码的质量,5,计算机执行指令的速度,2),事后统计法,(,事后测试,),缺点:,1.,必须执行程序,2.,其它因素掩盖算法本质收集此算法的执行时间和实际占用空间的统计资料。,74,算法的执行时间等于算法中各个语句执行时间的总和。,运行时间,=,算法中每条语句执行时间之和,某个语句的执行时间等于该语句执行一次所需时间与执行次数的乘积。,每条语句执行时间,=,该语句的执行次数(频度)*语句执行一次所需时间,语句的,频度,:该语句重复执行的次数。,75,语句执行一次所需时间取决于机器的指令性能和速度和编译所产生的代码质量,很难确定,在大多数情况下,精确统计算法中每个语句的执行次数与执行一次所需的时间都是非常困难的。,设每条语句执行一次所需时间为单位时间,则一个算法的运行时间就是该算法中所有语句的频度之和。,为了分析的方便,只选取一个,基本操作,(,或,原操作,),的频度作为算法执行时间的度量。基本操作一般指最深层循环内的语句。,例,:,(a)+x;s=0,;,+x,的频度为,(b)for(i=1;i=n;+i),+x;s+=x;,+x,的频度为,(c)for(j=1;j=n;+j),for(k=1;k=n;+k),f(n)=an,2,+bn+c,+x;s+=x;,+x,的频度为,1,n,n,2,n+1,n,n(n+1),n,2,n,2,1,n,n,2,77,for(i=2;i=n;i+),for(j=2;j=i-1;j+),+x;,aij=x;,i=2;i=3,,,j=2;i=4,,,j=2,,,3;i=n,,,j=2,,,3,,,,,n-1,频度之和:,an,2,+bn+c a,n,2,n,2,1,次,n,次,n-1,次,1+2+(n-2)=(n-1)(n-2)/2,次,1+2+(n-2)=(n-1)(n-2)/2,次,78,时间复杂度定义:,一般情况下,算法中,基本操作,重复执行的时间是问题规模,n,的某个函数,f(n),,算法的时间量度记作,T(n)=O(f(n),它表示随问题规模,n,的增大,算法执行时间的增长率和,f(n),的增长率相同,称作算法的,渐进时间复杂度,,简称,时间复杂度,。,79,main()int i,j,temp;int a10;for(i=0;i10;i+)scanf(%d,j+),for(i=0;iai+1),temp=ai;ai=ai+1;ai+1=temp;,for(i=1;i11;i+)printf(%5d,ai);printf(n);,80,有的情况下,算法中基本操作重复执行的次数还随问题的输入数据集不同而不同。例如:,void bubble-sort(int a,,,int n),for(i=n-1;change=TURE;i1-i),change=false;,for(j=0;jaj+1),aj aj+1;,change=TURE;,最好情况:,0,次,最坏情况:,1+2+3+n-1=n(n-1)/2,平均时间复杂度为,:O(n,2,),81,结论,(1),当,f(n),为对数函数、幂函数、或它们的乘积时,算法的运行时间是可以接受的,称这些算法是,有效算法,;当,f(n),为指数函数或阶乘函数时,算法的运行时间是不可接受的,称这些算法是,无效的算法,。,(2),随着,n,值的增大,增长速度各不相同,,n,足够大时,存在下列关系:,对数函数,幂函数,指数函数,82,常见函数的增长率,O(1),常量阶,与,n,无关,O(logn)log n,阶,O(n)n,阶,O(nlogn)n log n,阶,O(n,2,),平方阶,O(n,3,),立方阶,O(2,n,),指数阶,增长率由慢到快 图示见,p16,图,1-7,尽量少用指数阶的算法,说明:教材,p17,第,2,行 除特别指明外,均指最坏情况下的时间复杂度,83,1.4.4,空间复杂度,(1),存储算法本身所占用的空间,(2),算法的输入,/,输出数据占用的空间,(3),算法在运行过程中临时占用的辅助空间,原地工作:若辅助空间相对于输入数据量是常数,则称此算法是原地工作。,若所占空间量依赖于特定的输入,按最坏情况来分析。,
展开阅读全文