湖南农大-《数据结构》课件(C语言) 第01章.ppt

第1页,数据结构,主讲：戴小鹏,第2页,第3页,本章主要内容,一、数据结构教学计划二、第一章绪论1、什么是数据结构2、基本概念和术语3、抽象数据类型(ADT)4、类C语言语法规则5、算法的描述和算法分析,第4页,一、数据结构教学计划,英文名称DataStructure先修课程计算机高级语言后续课程数据库技术等授课学时56学时上机实践24机时教学对象,第5页,配套题集数据结构题集，严蔚敏等编清华大学出版社，1994.9参考教材1.数据结构，陆松年等编著上海交通大学出版社，1995.92.数据结构教程，唐发根等编著北京航空航天大学出版社，1996.103.数据结构与算法分析，张铭等译电子工业出版社，1998.84.数据结构，陈桂芬，戴小鹏编著,中国农业出版社，2013，2注：可参考数据结构的C+语言方面的书籍。,一、数据结构教学计划,第6页,一、数据结构教学计划,课程地位本课程不仅是一般的程序设计的基本训练，而且是设计和实现编译程序、数据库系统、人工智能系统和其它系统程序的重要基础，是一门核心课程，对培养计算机及有关专业人才具有重要意义。,第7页,课程任务讲授那些最重要、最常用的数据结构，阐明数据结构内在的逻辑关系，讨论它们在计算机中的存储表示，并结合各种典型应用说明它们在进行各种运算时的动态性质和实现操作的算法。,一、数据结构教学计划,第8页,课程要求1.熟悉各类典型的数据结构的逻辑特性、不同的存储方法与存储量、算法及效率的关系、定义于数据结构上的主要基本操作及其算法，了解它们的应用环境,为学习后续课程奠定基础；2.进一步提高软件设计和编程水平；3.增强根据求解问题性质,选择合适的数据结构及控制求解算法的时间与空间复杂性的能力。,一、数据结构教学计划,第9页,第10页,要求：、了解数据结构、算法的概念、基本的逻辑结构和存储结构、基本操作；、掌握类C语言体系和抽象数据类型的概念；、知道算法的时间复杂性和空间复杂性概念。重点：、数据结构与算法的概念；、类C语言体系；、抽象数据类型。,二、第一章绪论,第11页,1、什么是数据结构,二、第一章绪论,简义：数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等的学科。,数据结构是计算机科学专业的一门核心课程，它的研究对象为问题求解方法、程序设计方法及一些典型数据结构的算法。,第12页,数据结构,程序设计,算法,问题求解,程序编写,1、什么是数据结构,第13页,“好”数据结构“好”算法“好”程序,良好、合理的数据结构清晰、实用的算法简洁、高效的程序,1、什么是数据结构,第14页,数据结构在计算机科学技术中是一门综合性的专业基础课，计算机科学技术各个领域都要用到多种数据结构。在我国计算机及相关专业的教学计划中，它是核心课程之一。在我院教学计划中，数据结构已成为我院各专业一门公共必修课程。中国已列入93年计算机教程中。推荐学时为100学时。其基本内容包括：基本数据结构，抽象数据类型，递归算法，复杂性分析，排序和搜索，可计算性和不可判定性，问题求解策略，并行和分布式算法等。,数据结构在计算机科学中所处的地位：,1、什么是数据结构,第15页,客观事物的符号表示，是计算机程序加工的原料。它是信息的载体，能被计算机识别、存储和加工处理。随着计算机软、硬件的发展，计算机应用领域的不断扩大，数据的含义也随之拓广。文字、表格、图像、声音、光和电的输入等等均可列入数据的范畴。,数据(Data),2、基本概念和术语,二、第一章绪论,第16页,是数据的基本单位，即数据这个集合中的一个实体。通常作为整体进行考虑和处理。有些情况下，数据元素也称为元素、结点、顶点、记录等。一个数据元素可能仅含一个数据项，亦可包含若干个数据项。,数据元素(DataElement),2、基本概念和术语,数据项(DataItem),亦称字段、域,数据项是具有独立含义的不可分割的最小标识单位。,第17页,数据对象(DataObject),性质相同的数据元素的集合，是数据的一个子集。数据对象可以是有限的，也可以是无限的。如：整数对象是集合N=0,1,2,.；字母字符的集合等。,2、基本概念和术语,第18页,数据类型(DataType),简称类型，一个值的集合和定义在值集上的一组操作的总称。它显式地或隐含地规定了变量或表达式所有可能的取值范围以及在这些值上允许进行的操作。原子类型(AtomicType)：如C中的标量类型（整型、实型、字符型）以及指针类型等。结构类型(StructuredType）：亦称结构类型，如C中的数组、记录、文件类型等。抽象数据类型(AbstractDataType,ADT）：下面有专门介绍。,2、基本概念和术语,第19页,数据处理(DataProcessing),对数据进行诸如查找、插入、删除、合并、排序、统计、简单计算、输入、输出等的操作过程。,2、基本概念和术语,结构(Structure),相互关联的元素之间的构成关系。这种关系可以是物理上的，也可以是逻辑上的，或其它关系。,第20页,定义：是相互之间存在一种或多种特定关系的数据元素的集合。组成：由某一数据对象及该对象中所有数据成员之间的关系组成。DataStructure=（DataObject,Relationships）数据结构是指在程序中信息的逻辑组织方法，一般来说，这种方法也受到所选择的程序设计语言的限制。,数据结构(DataStructure),2、基本概念和术语,第21页,数据的逻辑结构：指各数据元素之间的逻辑关系，是用户按使用需要建立起来的，呈现在用户面前的结构形式。数据的物理结构：亦称数据的物理结构、存储结构，是指数据在计算机内的表示方法，即存储形式。,数据结构(DataStructure),2、基本概念和术语,第22页,1）数据元素之间的逻辑关系，亦称数据的逻辑结构；,数据结构的三个方面,2）数据元素及其关系在计算机存储器内的表示，亦称数据的存储结构；,3）数据的运算，即对数据施加的操作。,2、基本概念和术语,第23页,数据结构的三个方面,例1：一个线性表逻辑结构：哪个元素是表中第一个元素；哪个元素是表中最后一个元素；哪些元素在一个给定元素之前或之后；等等。存储结构：它的元素在存储器中是顺序地邻接存放，还是用指针连接在一起的；等等。运算：在表中查找一个元素；从表中删去一个元素；向表中插入一个元素；等等。,2、基本概念和术语,第24页,数据的四种基本逻辑结构与四种基本存储结构,1）从逻辑角度看，数据可归结为四种基本结构：集合、线性结构、树结构和图结构,2）从存储角度看，数据可归结为四种基本结构：顺序结构、链接结构、索引结构和散列结构,2、基本概念和术语,第25页,1）数据的四种基本逻辑结构,线性结构：结构中的数据元素之间存在一对一的关系,树结构：结构中的数据元素之间存在一对多的关系,图结构：结构中的数据元素之间存在多对多的关系。,集合：结构中的数据元素之间除“同属于一个集合”的关系，无其他关系,第26页,2）数据的四种基本存储结构,链接存储结构不要求逻辑上相邻的结点其物理位置上亦相邻，结点间的逻辑关系是由附加的指针字段表示的。,顺序存储结构把逻辑上相邻的结点存储在物理位置上相邻存储单元里，结点间的逻辑关系由存储单元的邻接关系来体现。,散列存储结构根据结点的关键字直接计算出该结点的存储地址。,索引存储结构通常在存储结点信息的同时，还建立附加的索引表，索引表中的每一项称为索引项，索引项的一般形式是：（关键字，地址），关键字是能唯一标识一个结点的那些数据项。,第27页,定义在数据结构上的基本操作,删除(Delete)删去数据结构中某个指定的数据元素。,插入(Insert)在数据结构中的指定位置上增添新的数据元素。,更新(Update)改变数据结构中某个数据元素的值，在概念上等价于删除和插入操作的组合。,查找(Find)在数据结构中寻找满足某个特定要求的数据元素(位置或值)。,2、基本概念和术语,第28页,定义在数据结构上的基本操作,排序(Sort)（在线性结构中）重新安排数据元素之间的逻辑顺序关系，使之按值由小到大或大到小（即递增、不降或递减、不增）的次序排列。注：一般将插入、删除与修改统称为更新；查找亦称搜索(Search)。,2、基本概念和术语,第29页,同一种逻辑结构采用不同的存储方法，可以得到不同的存储结构。选择何种存储结构来表示相应的逻辑结构，主要是使其运算方便及根据算法的时空要求来具体确定。常将同一逻辑结构的不同存储结构以不同的数据结构的命名。如线性表顺序表、链表、散列表。给定了数据的逻辑结构和存储结构，若定义的运算集合及其运算的性质不同，也可能导致完全不同的数据结构。如线性表中的栈、队列、顺序栈、链栈、链队列。,2、基本概念和术语,第30页,抽象数据类型(AbstractDataType,ADT)是指一个数学模型以及定义在这个模型上的一组操作。抽象数据类型仅取决于它的逻辑特性，与其在计算集中的表示无关。即无论其内部结构如何变化，只要它的数学特性没有变化，都不影响其外部使用。一个ADT的定义并不涉及它的实现细节，这些实现细节对于ADT的用户是隐蔽的封装性/信息隐蔽数据结构是ADT的物理实现。,3、抽象数据类型(ADT),二、第一章绪论,第31页,例2：整数的数学概念和施加于整数的运算构成一个ADT，不同计算机中实现可能不同，其数学特性是相同，因此对用户完全相同。,3、抽象数据类型(ADT),例3：一个整数线性表的ADT应包含下列操作：插入一个整数到线性表尾删除线性表中特定位置上的整数在线性表中查找特定整数,第32页,ADT包括以下三部分内容：ADT的规格说明(Specification)ADT的表示(Representation)ADT的实现(Implementation)用元组表示：ADT=(数据对象,关系集,处理集),3、抽象数据类型(ADT),3、抽象数据类型(ADT),第33页,本书的表示格式：ADT抽象数据类型名数据对象：数据关系：基本操作：ADT抽象数据类型名,3、抽象数据类型(ADT),3、抽象数据类型(ADT),用伪码表示,基本操作名(参数表)初始条件：操作结果：,第34页,在具体实现时，完成任务的算法、数据类型、数据结构、程序的逻辑组织，甚至采用哪种程序设计语言都是可以自由选择的与具体实现无关。ADT的主要目的之一是对用户隐蔽所有的表示方法，算法的详细细节、实现操作的具体代码以及其它所有对外界不必要的细节，都被局限于具体实现的模块内部，从而实现了信息的隐蔽。ADT的一个重要优点是其简单性。ADT的目的是将数据的本质特征、它们的结构及操作同它们的非本质的具体表示及实现细节相区分开来，从而得到了简化。,3、抽象数据类型(ADT),第35页,例4：在数据结构中，复数可定义为一种简单的抽象数据类型：Complex=(C,R)其中C是含有两个实数的集合C1,C2，R=P，P是定义在集合C上的一种关系，有序偶表示C1是复数的实部，C2是复数的虚部。,3、抽象数据类型(ADT),第36页,SpecificationComplex元素（Elements）元素的集合为两个实数的笛卡儿乘积Z=RR其中R表示实数集，Z表示复数集。结构（Structure）Complex的元素之间不存在任何结构，每一个元素表示定义在复数域Z中的一个孤立的值。,抽象数据类型Complex的规格说明：,3、抽象数据类型(ADT),第37页,ADTComplexDataObjects:D=C1,C2|C1,C2实数;DataRelationships:R=|C1,C2实数Operations:InitComplex(初始条件：复数T已知操作结果：E1,E2分别减C1,C2ADTComplex,抽象数据类型Complex的规格说明：,3、抽象数据类型(ADT),第38页,抽象数据类型Complex具体的表示和实现依赖于所采用的计算机语言。用户可以用某种高级语言的固有数据类型和自定义数据类型，并借助于过程和函数来表示和实现抽象数据类型Complex。C语言表示如下：,抽象数据类型Complex的表示：,3、抽象数据类型(ADT),structComplexrealRealPart;realImagPart;；,第39页,Operation在Complex上可定义下列操作1）函数InitComplex生成一个复数Z，Z=x+iyComplexInitComplex(realx,realy);2）函数Add求两个复数Z1与Z2之和。ComplexAdd(ComplexZ1,ComplexZ2);或ComplexAdd(ComplexZ,realR1,realR2);3）函数Sub，求两个复数Z1与Z2之差ComplexSub(ComplexZ1,ComplexZ2);或ComplexSub(ComplexZ,realR1,realR2);,3、抽象数据类型(ADT),继下页,第40页,Operation4）函数Multiply求两个复数之积ComplexMultiply(ComplexZ1,ComplexZ2);ComplexMultiply(ComplexZ,realR1,realR2);5）函数GetRealPart取复数Z的实部realGetRealPart(ComplexZ);6）函数GetImagPart取函数Z的虚部realGetImagPart(ComplexZ);,3、抽象数据类型(ADT),续上页,第41页,以上关于ADT的定义（规格说明、表示）没有涉及到实现。正象ADT的名字所暗示的那样，它是作为实现的公共特征的抽象。但是，从ADT的角度研究数据结构的最终目的仍在于应用，因此必须仔细考虑表示方法、算法、实现的技术及细节。而当ADT被实现时，ADT中的元素成了数据结构的一个实例,而那些操作就成了算法。由于在ADT的规格说明中，只指明了其功能而未指定要采用何种方法，因此，实现的独立性是显而易见的。,抽象数据类型Complex的实现：,3、抽象数据类型(ADT),第42页,ComplexCreate(realx,realy)ComplexZ;Z.RealPart=x;Z.ImagPart=y;returnZ;ComplexAdd(ComplexZ1,ComplexZ2)ComplexSum;Sum.RealPart=Z1.RealPart+Z2.RealPart;Sum.ImagPart=Z1.ImagPart+Z2.ImagPart;returnSum;(以下略),抽象数据类型Complex的C语言实现：,3、抽象数据类型(ADT),第43页,实现ADT,3、抽象数据类型(ADT),由于C语言是面向过程的语言，它能支持ADT的实现，但是不能很好的反映ADT的数据隐蔽原则。在Pascal语言中，库单元(Unit)是ADT的较好表示和实现。随着面向对象技术的成熟，用面向对象中的对象/类来描述和实现ADT是非常好的方法。这种方法在面向对象程序设计方面已经成熟，已经广泛应用于不同程序设计语言及开发环境当中（如：C+，ObjectPascal,VB,Java,PowerBuilder等等）。,第44页,下面是Complex采用C+的定义：classComplexprivate:realRealPart;realImagPart;public:Complex(realx,realy);/构造函数Complex(Complex/取虚部C+实现略,C+实现ADT,3、抽象数据类型(ADT),第45页,4、类C语言语法规则,二、第一章绪论,类C语言是介于伪码语言和高级语言之间的一种算法描述语言。使用类C语言描述算法的好处：1.保持C结构清晰、明确直观等特色；2.但又略去一些次要环节，抓住主干精华。,第46页,4、类C语言语法规则,函数类型过程名(参数表)/算法说明语句组;return结果；/过程名当返回状态结果时，函数定义为Status类型。,1）算法以过程或函数的形式表示,第47页,4、类C语言语法规则,2）赋值语句,简单赋值变量名=表达式；,串联赋值变量1=变量2=表达式；,成组赋值(变量名1,变量名k)=(表达式1,表达式k);,结构名=结构名;,结构名=(值1,值k)；,第48页,4、类C语言语法规则,2）赋值语句,变换赋值变量1变量2；,if(条件)语句1;if(条件)语句1;else语句2；/可以嵌套,3）IF语句,第49页,4、类C语言语法规则,switch(表达式)case条件1：语句1；break;case条件n：语句n;break;default:语句n+1,4）Switch语句,switchcase条件1：语句1；break;case条件n：语句n;break;default:语句n+1,第50页,4、类C语言语法规则,For语句：for(处置表达式序列;条件;修改表达式系列)语句；While语句：while(条件)语句；Do-While语句：do语句;while(条件);,5）循环语句,第51页,4、类C语言语法规则,6）基本函数,7）布尔运算符,8）标识符,具体参见P10页,9）常量和类型,第52页,算法的概念算法的描述算法设计的要求算法效率的度量算法的存储空间需求,5、算法的描述和算法分析,第53页,算法的概念,5、算法的描述和算法分析,算法(Algorithm)是对特定问题求解步骤的一种描述，是能在计算机上经过有限时间完成的、毫不含糊的指令的有限序列。其中每一条指令表示一个或多个操作。,问题（Problem）是一个函数，或是输入和输出的一种联系。程序（Program）是用计算机程序设计语言实现的完成一定功能的代码。算法的实现一定是程序，但程序不一定是算法的实现。,第54页,5、算法的描述和算法分析,算法的五个重要特性,1）有穷性：执行有限步，每步均在有穷时间内完成。,2）确定性：对相同的输入，必产生相同的输出，即无二义性。,3）可行性：计算机可使用已实现的基本运算执行有限次来完成。,4）输入：零个或多个输入。,5）输出：一个或多个输出。,第55页,5、算法的描述和算法分析,关于算法性质的另一种描述1、正确性(Correctness)它必须完成所期望的功能，把每一次输入转化为正确的输出。2、具体步骤(ConcreteSteps)一个算法应该由一系列具体步骤组成。3、确定性(NoAmbiguity)下一步（通常是指算法描述中的下一步）应执行的步骤必须明确。4、有限性(Finite)一个算法必须由有限步组成。5、可终止性(Terminable)算法必须可以终止，即不能进入死循环。,第56页,算法的描述,5、算法的描述和算法分析,一个算法可以用各种不同的方法来进行描述。比如可使用某种高级语言、汇编语言甚至机器语言来描述某个算法，亦可使用伪码语言或框图等其它形式来描述它。这里我们采用上讲介绍的类C语言来描述算法,第57页,在程序设计中，对算法进行分析是十分重要的。对于一个具体的应用实例，通常可能有若干个算法可供选用，应判断哪一个算法在现有的计算机环境中对解决某个问题是最优的。,例5：写一函数，用以计算1+2+n的值，其中n为已知。longSumWork(intn)intsum=0;for(inti=1;i+;i=n)sum+=i;returnsum;,算法设计的要求,5、算法的描述和算法分析,longBetterSum(intn)return(n+1)*n/2;,第58页,算法设计的要求,5、算法的描述和算法分析,在计算机科学中，通常使用算法的计算（执行）时间和所需的存储空间来评价算法或程序的优劣。在选择算法时，除了要考虑算法的运算时间和所需内存外，往往还要考虑其它一些重要的因素，即所谓设计一个“好”的算法应考虑达到的下列目标。,1）正确性2）可读性3）健壮性4）效率与低存储量需求,第59页,算法设计的要求,5、算法的描述和算法分析,1）正确性(Correctness)能满足具体问题的需求。正确性对于选择算法来说，是首要的问题。正确性的四个层次：a.程序不含语法错误；b.程序对于输入数据能够得出满足规格说明要求的结果(要算对)；c.程序对于精心选择的典型、苛刻而带有刁难性的输入数据能够得出满足规格说明要求的结果；d.程序对于一切合法的输入数据都能产生满足规格说明要求的结果。,第60页,算法设计的要求,5、算法的描述和算法分析,2）可读性(Readability)希望一个算法易于理解、易于编码，也易于调试。3）健壮性(Robustness)对于异常的处理能力。能作出判断，并给出适当的提示或警告信息，以等待操作员的干预或能自动进行适当处理。4）效率(Efficiency)与低存储需求效率指算法执行时间。同一问题，算法执行时间越短，效率越高。存储量需求指算法执行过程中所需的最大存储空间。此所谓时（执行时间）、空（运行空间）效应。,第61页,算法效率的度量,5、算法的描述和算法分析,算法执行时间的度量时间复杂度执行时间取决于下列因素：a.选用哪种算法b.问题的规模（输入的大小/复杂程度）；c.所选用的语言；d.编译程序所产生可执行代码的质量；e.机器执行指令的速度。1）事后统计对算法程序的执行进行计时。（有缺陷）2）事前估计事先估算的主要因素问题的规模。,第62页,算法效率的度量,5、算法的描述和算法分析,一个算法是由控制结构（顺序、分支和循环）和原操作（指固有数据类型的操作）构成的，算法时间取决于两者的综合效果。但是，为便于比较同一问题的不同算法，通常的做法是：从算法中选取一种对于所研究的问题（或算法类型）来说是基本运算的原操作，以该基本运算重复执行的次数作为算法的时间量度的依据。,2）事前估计,第63页,算法效率的度量,5、算法的描述和算法分析,例6：两个nn矩阵相乘，令乘法运算作为基本运算for(i=1;i=n;i+)for(j=1;jn0，恒有n2+4n2n2,第65页,5、算法的描述和算法分析,大O运算规则规则一对于任何的常数k和任何的函数f，恒有kf(n)=O(f(n)，即大O忽略常数因子。规则二若f(n)=O(g(n)且g(n)=O(h(n)，则f(n)=O(h(n)，即大O的概念是传递的。规则三若定义maxf(n)，