11 为什么学习数据结构 12 数据结构的有关概念和术语 13

第一章数据结构概述2020年2月10日11.1为什么学习数据结构1.2数据结构的有关概念和术语1.3算法和算法描述1.4算法的时空效率分析方法1.5小结与习题第一章数据结构概述2020年2月10日2主要介绍课程中常用术语、常用数据结构及用类C语言实现算法描述的一般规则，算法的时间复杂度和空间复杂度分析与评价。本章主要内容通过本章学习，应掌握如下内容：数据结构中的基本概念及常用术语。线性结构、树型结构和图型结构等的逻辑特点。算法的定义、特性及用类C语言描述算法的规则。评价算法优劣的标准：时间复杂度、空间复杂度的定义及表示。第一章数据结构概述2020年2月10日31.1为什么要学习数据结构研究数据的特性、数据间的相互关系及其对应的存储表示，并利用这些特性、关系和存储表示设计出相应的算法和程序。为什么要学习数据结构？计算机处理的数据量越来越大；数据的类型越来越多；数据的结构越来越复杂。解决一个问题时几个步骤：抽象出一个适当的数学模型，设计或选择一个解决此类数学模型的算法，编写程序进行调试、测试，直至得到最终的解答。第一章数据结构概述2020年2月10日4【例1-1】学生信息检索问题。学生信息包括学号、姓名、性别和成绩等，一行为一个记录，表示一个学生的信息（也称为一个数据元素），一列为一个属性。学号姓名性别成绩20050601张三男51820050602李一宁女49620050603吴磊女581.5……………20050636梁磊男529线性关系:对线性表的主要操作有查找、修改、插入和删除等。第一章数据结构概述2020年2月10日5【例1-2】某大学专业设置问题。显然这种关系用“树”型结构来表示更形象。通常用来表示结点的分层组织，结点之间是一对多的关系。对树型结构主要操作有查找、修改、插入和删除等。**大学机械工程系电子工程系计算机与信息工程系机械制造材料科学电子应用电气自动化计算机应用与维护计算机应用与维护第一章数据结构概述2020年2月10日6【例1-3】通信网络问题。带圆圈的顶点表示城市，顶点和顶点之间的连线和数据表示城市之间的通信线路及其长度。，各顶点之间是多对多的关系，是网状结构，也称为图型结构，操作有：求从一个顶点到另一个顶点的最短路径等。由以上三个例子可见，描述这类非数值计算问题的数学模型有线性表、树、图等。所有的计算机系统软件和应用软件都要用到各种类型的数据结构。BCDFEA60454042304080653226第一章数据结构概述2020年2月10日71.2数据结构的有关概念和术语1.2.1基本概念和术语1．数据（Data）是描述客观事物的数值、字符以及所有能被输入到计算机并能被计算机识别、存储和处理的符号的集合。客观事物包括数值数据和非数值数据。数值数据：整数、实数或复数；非数值数据：字符、文字、图形、图像和声音等。2．数据元素（DataElement）是数据的基本单位。在不同的条件下，数据元素又可称为元素、结点、顶点、记录等。数据项：数据结构中讨论的最小单位。一个数据元素可由若干个数据项（DataItem）组成。例如，学生信息表的每一个数据元素就是一个学生记录，它包括学生的学号、姓名、性别、成绩等数据项。第一章数据结构概述2020年2月10日83．数据对象（DataObject）是具有相同性质数据元素的集合。4．数据类型(DataType)在用高级语言编写的程序中，每个变量、常量或表达式都有一个它所属的确定的数据类型。5．抽象数据类型（AbstractDataType，简称ADT）是指基于逻辑关系的数据类型以及定义在该类型之上的一组操作。ADT抽象数据类型名{数据对象：（数据对象的定义）数据关系：（数据关系的定义）基本操作：（基本操作的定义）}第一章数据结构概述2020年2月10日9【例1-4】线性表的抽象数据类型可描述如下：ADTLinear_list{数据元素所有ai属于同一数据对象，i=1，2，…，n（n≥1）逻辑结构所有数据元素ai存在次序关系（ai，ai+1），a1无前驱，an无后继。操作/*设L为Linear_list类型的线性表*/InitList（L）；/*建立一个空的线性表L*/Length（L）；/*求线性表L的长度*/GetElement（L，i）；/*取线性表L中的第i个元素*/Locate（L，x）；/*确定元素x在线性表L中的位置*/Insert（L，i，x）；/*在线性表L中的第i个位置处插入数据元素x*/Delete（L，i）；/*删除表L中第i个位置的元素*/……}；/*ADTLinear_list*/第一章数据结构概述2020年2月10日101.2.2数据结构定义数据结构（DataStructure）是指互相之间存在着一种或多种关系的数据元素的集合。数据元素之间的关系称为结构。数据的结构包括逻辑结构和物理结构。（1）逻辑结构：是数据元素之间的相互逻辑关系，它与数据的存储无关，是独立于计算机而存在。数据结构是由两个集合构成的一个二元组：Data_Structure(D，R))Data_Structure是一种数据结构，它由同属一个数据对象的数据元素的有限集合D和D上二元关系的有限集合R组成。其中：D={di|1≦i≦n,n≧1}R={rj|1≦j≦m,m≧1}第一章数据结构概述2020年2月10日11di表示第i个数据元素，rj表示第j个关系。D上二元关系R是序偶的集合。对于R中的任一序偶x,y(x,y∈D)，x称为序偶的第一元素，y称为序偶的第二元素，又称序偶的第一元素是第二元素的直接前驱；第二元素为第一个元素的直接后继。【例1-5】树型结构中的圆圈代表数据元素，带箭头的连线表示元素之间的关系，试用二元组表示法表示其逻辑结构。解：二元组为(D,R)其中，D={A,B,C,E,F,G,H,I,J};R={A,B,A,C,A,E,B,F,B,G,E,H,E,I,E,J}ABCEFGHIJ第一章数据结构概述2020年2月10日12通常有下列四种基本的结构：a.集合结构。集合是元素关系极为松散的一种结构。b.线性结构。线性结构的逻辑特征是：若结构是非空集，则有且仅有一个开始结点和一个终端结点，并且所有结点都最多只有一个直接前驱和一个直接后继。c.树型结构。该结构的数据元素之间存在着一对多的关系。d.图型结构。该结构的数据元素之间存在着多对多的关系，图型结构也称作网状结构。（2）物理结构（或存储结构）是数据结构在计算机中的表示（又称映像），它包括数据元素的机内表示和关系的机内表示。具体实现的方法有顺序、链接、索引、散列等多种，数据的具体操作与存储结构有很密切的联系。数据结构作为一门学科主要研究数据的各种逻辑结构和存储结构，以及对数据的各种操作。同时还要考虑执行算法时的时间和空间效率。第一章数据结构概述2020年2月10日131.3算法和算法描述⑴有穷性。一个算法必须在有穷步之后结束，即必须在有限时间内完成。⑵确定性。算法的每一步必须有确切的定义，无二义性。⑶可行性。算法中的每一步都可以通过已经实现的基本运算的有限次执行得以实现。⑷输入。一个算法具有零个或多个输入，这些输入取自特定的数据对象集合。⑸输出。一个算法具有一个或多个输出，这些输出同输入之间存在某种特定的关系。1.3.1算法与算法特性算法（Algorithm）是对特定问题求解步骤的一种描述，是指令的有限序列。一个算法应该具有下列特性：第一章数据结构概述2020年2月10日14一个好的算法通常要达到以下的要求：正确。执行结果应当满足预先规定的功能和性能要求。可读。应当思路清晰、层次分明、简单明了、易读易懂。健壮。当输入不合法数据时，应能作适当处理，不至引起严重后果。高效。有效使用存储空间和有较高的时间效率。1.3.2算法描述最简单的方法是使用自然语言，其优点是简单且便于人们对算法的阅读；缺点是转换成高级语言困难。类C语言忽略高级程序设计语言中一些严格的语法规则与描述细节，因此它比程序设计语言更容易描述和被人理解，比自然语言更接近程序设计语言，很容易被转换成高级语言。第一章数据结构概述2020年2月10日15本书对所用类C语言作如下约定：1．问题的规模用MAXSIZE#defineMAXSIZE602．预定义常量和类型：#defineTRUE1#defineFALSE0#defineOK1#defineERROR0#defineOVERFLOW-1typedefintStatus;3．数据结构（存储结构）的表示用类型定义（typedef）描述。数据元素类型约定为ElemType，由用户在使用该数据类型时自行定义。例1.学生信息检索系统中，用一维数组作存储n个学生的信息，数组中的数据元素有4个域：学号、姓名、性别和成绩：typedefstructstd_info{longintNum;/*学号域*/charName[8];/*姓名域*/charSex;/*性别域*/floatScore;/*成绩域*/}ElemType;第一章数据结构概述2020年2月10日164．基本操作的算法都用以下形式的函数描述函数类型函数名(函数参数表){/*算法说明*/语句序列；}/*函数名*/5．C语言中的常用语句赋值（=）、选择（if、if…else、switch…case…default）、循环（for、while、do…while）、结束（return、break、continue、exit）、输入和输出等语句。6．基本运算和基本函数基本运算有+、-、*、/、%、-、&&和||等。基本函数有max、min、abs、fabs、eof等。第一章数据结构概述2020年2月10日17例设某班级有n个学生，编写算法，查找班级中成绩最高的学生，并输出该学生的所有信息。分析：，算法依次查看数组中的元素，并保存当前最高成绩及其下标。使用类C语言编写：intlargest（ElemTypeS[MAXSIZE]，intn）{floatcurrlarge=0.0;inti,j=0;/*赋初值*/for（i=0;in;i++）/*进入循环*/if(S[i].Scorecurrlarge){j=i;currlarge=S[i].Score;}printf(“%10ld%10s%10c%10f\n”,S[j].Num,S[j].name,S[j].Sex,S[j].Score);}/*largest*/typedefstructstd_info{longintNum;charName[8];charSex;floatScore;}ElemType;第一章数据结构概述2020年2月10日181.4算法时空效率分析方法评价算法的性能用时间复杂度与空间复杂度来度量。1、算法的时间复杂度算法的时间复杂度（Timecomplexity）是指算法转换为程序后(这里仍称为算法)在计算机上从开始运行到结束所需要的时间。运行所需要的时间取决于下列因素：⑴硬件的速度。与硬件的配置高低有关。⑵书写程序的语言。语言的级别越高，其执行效率就越低。⑶编译程序所生成目标代码的质量。⑷依据算法所选用的策略。⑸问题的规模。一般情况下，处理的数据量越大，执行的时间相对也越长。第一章数据结构概述2020年2月10日19通常的做法是：不考虑不确定的情况，而以算法中简单操作重复执行的次数作为算法的时间度量。为此，一个特定算法的运行时间长短就只依赖于问题的规模n，或者说它是问题规模n的函数f(n)。【例1-7】求累加求和intsum(intb[]，intn）｛intsum=0;/*第1条定义并赋初值语句执行1次*/for（inti=0；in；i++）/*3n+2次*/sum+=b[i];/*n次*/returnsum;｝/*返回语句执行1次*/第一章数据结构概述2020年2月10日20要精确地计算f(n)是困难的，引入渐进时间复杂度在数量上估计一个算法的执行时间。算法时间的度量记作T(n)=Ο(f(n))它表示随问题的规模n的增大，算法执行