1、数据结构数据结构-绪论绪论数据结构数据结构-绪论绪论1.1.了解数据结构研究的主要内容了解数据结构研究的主要内容2.2.掌握数据结构中涉及的基本概念掌握数据结构中涉及的基本概念3.3.掌握算法、算法的时间复杂度及其掌握算法、算法的时间复杂度及其分析的简易方法分析的简易方法 教学目标教学目标数据结构数据结构-绪论绪论1.1 1.1 数据结构的研究内容数据结构的研究内容1.2 1.2 基本概念和术语基本概念和术语1.3 1.3 算法与算法分析算法与算法分析教学内容教学内容数据结构数据结构-绪论绪论1.11.1 数据结构的研究内容数据结构的研究内容Niklaus Wirth：Algorithm+Da
2、ta Structures=Programs程序设计程序设计:算法算法:数据结构数据结构:为计算机处理问题编制一组指令集 处理问题的策略问题的数学模型数据结构数据结构-绪论绪论书目检索书目检索登录号：书名：作者名：分类号：出版单位：出版时间：价格：书目卡片001高等数学樊映川S01002理论力学罗远祥L01003高等数学华罗庚S01004线性代数栾汝书S02书目文件按书名按作者名按分类号高等数学001，003理论力学002，.线性代数004，.樊映川001,华罗庚002,.栾汝书004,.L002,S001,003,索引表线性表数据结构数据结构-绪论绪论树人机对奕问题人机对奕问题.数据结构数据
3、结构-绪论绪论/(root)binlibuseretcmathdsswyintaoxieStack.cppQueue.cppTree.cpp文件目录文件目录树数据结构数据结构-绪论绪论多叉路口交通灯管理问题CEDABABACADBABCBDDADBDCEAEBECED图顶点：顶点：一条通路连线：连线：不能同时通行染色：染色：有连线的两个顶点不能具有相同颜色数据结构数据结构-绪论绪论&求解非数值计算的问题求解非数值计算的问题：设计出合适的数据结构及相应的算法 即：首先要考虑对相关的各种信息如何表示、组织对相关的各种信息如何表示、组织和存储？和存储？数据结构的研究内容为：数据结构的研究内容为：研究
4、非数值计算的程序设计问题中计算机的操作操作对象对象以及它们之间的关系和操作关系和操作。数据结构数据结构-绪论绪论&数据结构课程的形成和发展：数据结构课程的形成和发展：形成阶段：形成阶段：6060年代初期，年代初期，“数据结构数据结构”有关内容散见于操作系统有关内容散见于操作系统、编译原理和表处理语言等课程。、编译原理和表处理语言等课程。19681968年，年，“数据结数据结构构”被列入美国一些大学计算机科学系的教学计划。被列入美国一些大学计算机科学系的教学计划。发展阶段：发展阶段：数据结构的概念不断扩充，包括了网络、集合代数论数据结构的概念不断扩充，包括了网络、集合代数论、关系等、关系等“离散
5、数学结构离散数学结构”的内容。的内容。7070年代后期，我国高校陆续开设该课程。年代后期，我国高校陆续开设该课程。数据结构数据结构-绪论绪论&数据结构数据结构所处的地位：所处的地位：介于数学、计算介于数学、计算机硬件和计算机机硬件和计算机软件三者之间的软件三者之间的一门核心课程一门核心课程数据结构数据结构-绪论绪论数据结构数据结构-绪论绪论 能够分析研究计算机加工的对象的特性，获能够分析研究计算机加工的对象的特性，获得其得其逻辑结构逻辑结构，根据需求，选择合适，根据需求，选择合适存贮结存贮结构及其相应的算法构及其相应的算法；学习一些学习一些常用的算法常用的算法；复杂程序设计的训练过程，要求编写
6、的程序复杂程序设计的训练过程，要求编写的程序结构清楚和正确易读结构清楚和正确易读；初步掌握算法的初步掌握算法的时间分析和空间分析时间分析和空间分析技术技术数据结构数据结构-绪论绪论1.2 1.2 基本概念和术语基本概念和术语一一数据、数据元素、数据项和数据对象数据、数据元素、数据项和数据对象二二数据结构数据结构三三数据类型和抽象数据类型数据类型和抽象数据类型四四抽象数据类型的表示与实现抽象数据类型的表示与实现数据结构数据结构-绪论绪论1 1、数据、数据（data)所有能输入到计算机中去的描述客观事物的符号u数值性数据数值性数据u非数值性数据（多媒体信息处理）非数值性数据（多媒体信息处理）2 2
7、、数据元素、数据元素（data element）数据的基本单位，也称结点（node）或记录（record）3 3、数据项、数据项（data item）有独立含义的数据最小单位，也称域(field)。也是数据结构中讨论的最小最小单位。三者之间的关系：数据 数据元素 数据项例：学生表 个人记录 学号、姓名一、数据、数据元素、数据项和数据对象一、数据、数据元素、数据项和数据对象数据结构数据结构-绪论绪论例如：描述一个学生的数据元素数据元素可以包括：学号、姓名、出生日期、班级、电话其中：出生日期出生日期还可以包括年、月、日，因此，这个数据项称之为组合项。组合项。数据结构数据结构-绪论绪论u整数数据对象
8、整数数据对象 N=0,N=0,1,1,2,2,u学生数据对象学生数据对象学生记录的集合学生记录的集合4 4、数据对象数据对象(Data Object)(Data Object)：相同特性的数据元素的集合，是数据的一个子集数据结构数据结构-绪论绪论数据结构（数据结构（Data StructureData Structure）是相互之间存是相互之间存在一种或多种特定关系的数据元素的集合。在一种或多种特定关系的数据元素的集合。数据结构是带数据结构是带“结构结构”的数据元素的集合，的数据元素的集合，“结构结构”就是指数据元素之间存在的关系。就是指数据元素之间存在的关系。二、数据结构二、数据结构数据结构
9、数据结构-绪论绪论数据结构的两个层次：数据结构的两个层次：逻辑结构：逻辑结构：数据元素间抽象化的相互关系，与数据的存储无关，独立于计算机，它是从具体问题抽象出来的数学模型。存储结构（物理结构）：存储结构（物理结构）：数据元素及其关系在计算机存储器中的存储方式。数据结构数据结构-绪论绪论数据的逻辑结构逻辑结构可归结为以下四类四类:线性线性结构树形树形结构图状图状结构集合集合结构数据结构数据结构-绪论绪论数据的存储结构存储结构：顺序存储结构借助元素在存储器中的相对位置 来表示数据元素间的逻辑关系链式存储结构借助指示元素存储地址的指针 来表示数据元素间的逻辑关系数据结构数据结构-绪论绪论元素元素n
10、n.元素元素i i.元素元素2 2元素元素1 1LoLo+mLo+(i-1)*mLo+（n-1)*m存储地址存储地址存储内容存储内容Location(元素元素i)=Lo+（i-1)*m顺序存储顺序存储数据结构数据结构-绪论绪论1536元素元素2 21400元素元素1 11346元素元素3 3 元素元素4 41345h存储地址存储地址 存储内容存储内容 指针指针 1345 1345 元素元素1 1 14001400 1346 1346 元素元素4 4 .14001400 元素元素2 2 1536 1536 .1536 1536 元素元素3 3 1346 1346 链式存储链式存储 h数据结构数据
11、结构-绪论绪论 在用高级程序语言编写的程序中，必须对程序中出现的每个变量、常量或表达式，明确说明明确说明它们所属的数据类型数据类型。例如，C+语言中的int,float,double,int,float,double,char,boolchar,bool等基本数据类型基本数据类型。不同类型的变量，其所能取的值的范围值的范围不同，所能进进行的运算行的运算不同。三、数据类型和抽象数据类型三、数据类型和抽象数据类型数据类型数据类型：是一组性质相同的值的集合值的集合,以及定义在这个集合上的一组运算一组运算的总称。数据结构数据结构-绪论绪论抽象数据类型抽象数据类型 (ADT:Abstract Data
12、Type)(ADT:Abstract Data Type)u更高层次的数据抽象更高层次的数据抽象u由用户定义，用以表示应用问题的由用户定义，用以表示应用问题的数据模型数据模型u由由基本的数据类型基本的数据类型组成组成,并包括并包括一组相关的一组相关的操作操作数据结构数据结构-绪论绪论抽象数据类型抽象数据类型可以用以下的三元组来表示：可以用以下的三元组来表示：ADT=（D，S，P）数据对象数据对象 D上的关系集上的关系集 D上的操作集上的操作集 ADTADT抽象数据类型名抽象数据类型名 数据数据对象对象：数据数据关系关系：基本基本操作操作 ：ADT ADT抽象数据类型抽象数据类型名名ADT常用常
13、用定义定义格式格式数据结构数据结构-绪论绪论赋值参数参数 只为操作提供输入值。引用参数参数 以&打头，除可提供输入值外，还将返回操作结果。初始条件初始条件 描述了操作执行之前数据结构和参数应满足的条件，若不满足，则操作失败，并返回相应出错信息。若无初始条件，则省略之。操作结果操作结果 说明了操作正常完成之后，数据结构的变化状况和应返回的结果。其中，基本操作基本操作的定义格式为:基本操作名基本操作名（参数表）初始条件：初始条件：初始条件描述 操作结果操作结果：操作结果描述 数据结构数据结构-绪论绪论例如，例如，抽象数据类型复数复数的定义：数据对象数据对象：De1,e2e1,e2RealSet 数
14、据关系数据关系：R1|e1是复数的实数部分|e2是复数的虚数部分 ADT Complex 基本操作：（见后页。）基本操作：（见后页。）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,&su
15、m)初始条件：z1,z2是复数。操作结果：用sum返回两个复数z1,z2 的和值。基本操作基本操作数据结构数据结构-绪论绪论假设:z1和z2是上述定义的复数则 Add(z1,z2,z3)操作的结果z3=z1+z2即为用户所求的结果ADT ADT 有两个重要特征:数据抽象数据抽象 用ADTADT描述程序处理的实体时，强调的是其本质的特征本质的特征、其所能完成的功能其所能完成的功能以及它和外部用户的接口外部用户的接口（即外界使用它的方法外界使用它的方法）。数据封装数据封装将实体的外部特性和其内部实现细节外部特性和其内部实现细节分离分离，并且对外部用户隐藏其内部实现细节。对外部用户隐藏其内部实现细节
16、。数据结构数据结构-绪论绪论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 的和/-基本操作的函数原型说明基本操作的函数原型说明数据结构数据结构-绪论绪论抽抽象象数数据据类类型型查找插入
17、查找插入 删除删除 修改修改 线性表线性表接口或用户界面数据类型的物理实现封装信息隐蔽信息隐蔽和和数据封装数据封装，使用与实现相分离，使用与实现相分离数据结构数据结构-绪论绪论 抽象数据类型需要通过固有数据类型固有数据类型(高级编程语言中已实现的数据类型)来实现。例如，对以上定义的复数。其存储结构的定义typedef struct float realpart；float imagpart；complex；struct complex float realpart；float imagpart；但我们跟倾向于这样使用但我们跟倾向于这样使用四、抽象数据类型的表示与实现四、抽象数据类型的表示与实现
18、数据结构数据结构-绪论绪论/-基本操作的实现基本操作的实现void add(complex z1,complex z2,complex&sum)/以 sum 返回两个复数 z1,z2 的和 sum.realpart=z1.realpart+z2.realpart;sum.imagpart=z1.imagpart+z2.imagpart;其它省略 数据结构数据结构-绪论绪论1.3 1.3 算法和算法分析算法和算法分析一算法的定义及特性二算法的评价三算法的效率度量数据结构数据结构-绪论绪论 算法算法是为了解决某类问题而规定的一个有限长的操作序列操作序列。一个算法必须满足以下五个重要特性五个重要特性
19、：1 1有穷性有穷性 2 2确定性确定性 3 3可行性可行性4 4有输入有输入 5 5有输出有输出一、算法的定义及特性一、算法的定义及特性数据结构数据结构-绪论绪论1 1有穷性有穷性 对于任意一组合法输入值，在执行有穷步有穷步骤骤之后一定能结束，即：算法中的每个步骤都能在有限时间有限时间内完成。2 2确定性确定性 对于每种情况每种情况下所应执行的操作，在算法中都有确切确切的规定，使算法的执行者或阅读者都能明确其含义及如何执行。并且并且在任何条件下，算法都只有在任何条件下，算法都只有一条执行路径。一条执行路径。3 3可行性可行性 算法中的所有操作都必须足够基本，都可以通过已经实现的基本操作运算有
20、限次实现之。数据结构数据结构-绪论绪论4 4有输入有输入 (0个或多个输入)作为算法加工对象的量值，通常体现为算法中的一组变量。有些输入量需要在算法执行过程中输入，而有的算法表面上可以没有输入，实际上已被嵌入算法之中。5 5有输出有输出 它是一组与“输入”有确定关系的量值，是算法进行信息加工后得到的结果，这种确定关系即为算法的功能。数据结构数据结构-绪论绪论二、算法的评价二、算法的评价设计算法时，通常应考虑达到以下目标：1正确性正确性2.2.可读性可读性3.3.健壮性健壮性4.4.高效性（时间代价和空间代价）高效性（时间代价和空间代价）数据结构数据结构-绪论绪论1 1正确性正确性 首先，首先，
21、算法应当满足满足以特定的“规格说明规格说明”方式给出的需求需求。其次，其次，对算法是否“正确正确”的的理解可以有以下四个层次四个层次：a程序中不含语法错误；b程序对于几组输入数据能够得出满足要求的结果；c c程序对于精心选择的、典型、苛刻且带有刁难性程序对于精心选择的、典型、苛刻且带有刁难性的几组输入数据能够得出满足要求的结果；的几组输入数据能够得出满足要求的结果；d d程序对于一切合法的输入数据都能得出满足要求的结果；通常以第c c层意义的正确性作为衡量一个算法是否合格的标准。数据结构数据结构-绪论绪论2.可读性可读性 算法主要是为了人的阅读与交流阅读与交流，其次才是为计算机执行，因此,算法
22、应该易于易于人的理解理解；另一方面，晦涩难读的程序易于晦涩难读的程序易于隐藏较多错误而难以调试隐藏较多错误而难以调试(这一点非常重要这一点非常重要)。3健壮性健壮性 当输入的数据非法非法时，算法应当恰当地作出反映或进行进行相应处理相应处理，而不是产生莫名奇妙的输出结果。并且，处理出处理出错的方法错的方法不应是中断程序的执行，而应是返回返回一个表示错误表示错误或错误性质的值或错误性质的值，以便在更高的抽象层次上进行处理。数据结构数据结构-绪论绪论4高效性高效性通常，效率指的是算法执行时间；存储量指的是算法执行过程中所需的最大存储空间，两者都与问题的规模有关。数据结构数据结构-绪论绪论三、算法的效
23、率度量三、算法的效率度量通常有两种两种衡量算法效率的方法:1 1 事后统计法事后统计法2 2 事前分析估算法事前分析估算法缺点：缺点：1必须执行程序 2其它因素掩盖算法本质数据结构数据结构-绪论绪论和算法执行时间时间相关的因素因素：1 1算法算法选用的策略的策略2 2问题的规模问题的规模3 3编写程序的语言语言4 4编译编译程序产生的机器代码的质量的质量5 5计算机计算机执行指令的速度的速度数据结构数据结构-绪论绪论 假如，随着问题规模 n 的增长，算法执行算法执行时间的增长率和时间的增长率和 f(n)的增长率相同的增长率相同，则可记作：T(n)=O(f(n)称称T(n)为算法的为算法的(渐近
24、)时间复杂度。时间复杂度。一个特定算法的算法的“运行工作量运行工作量”的大小，只依赖于问题的规模（通常用整数量n表示），或者说，它是问题规模的函数是问题规模的函数。数据结构数据结构-绪论绪论算法算法 =控制结构控制结构+原操作原操作（固有数据类型的操作）算法的执行时间算法的执行时间=原操作原操作(i)(i)的执行次数的执行次数原操作原操作(i)(i)的执行时间的执行时间算法的执行时间算法的执行时间 与与原操作执行次数之和原操作执行次数之和成正比成正比 如何估算算法的时间复杂度？如何估算算法的时间复杂度？数据结构数据结构-绪论绪论 从算法中选取一种对于所研究的问题来说是 基本操作基本操作 的原操
25、作，以该基本操作 在算法中重复执行的次数在算法中重复执行的次数 作为算法运行时间的衡量准则。数据结构数据结构-绪论绪论例例1两两个个矩矩阵阵相相乘乘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;/mult时间复杂度:O(n3)数据结构数据结构-绪论绪论例例2选选择择排排序序/对数组对数组a a从小到大排序从小到大排序void select_sort(int a,int n)for(i=0;i n-
26、1;+i)j=i;/选择第选择第 i 个最小元素个最小元素for(k=i+1;k n;+k)if(ak aj)j=k;swap(aj,ai);/select_sort时间复杂度:O(n2)数据结构数据结构-绪论绪论四、算法的存储空间需求四、算法的存储空间需求算法的空间复杂度定义为空间复杂度定义为:表示随着问题规模表示随着问题规模 n 的增大，算法运行所需存储的增大，算法运行所需存储量的增长率与量的增长率与 g(n)的增长率相同。的增长率相同。S(n)=O(g(n)算法的存储量算法的存储量包括:1输入数据输入数据所占空间2程序本身程序本身所占空间(相对有限，可忽略相对有限，可忽略)3辅助变量辅助
27、变量所占空间(关键关键)数据结构数据结构-绪论绪论 一般来说，输入数据输入数据所占空间只取决于问题本身，和算法无关和算法无关，则只需要分析除输入和程序之外的辅助变量辅助变量所占额外空额外空间间。若所需额外空间相对于输入数据量来说是常数，则称此算法为原地工作原地工作。若所需存储量依赖于特定的输入，则通常按最坏情况考虑。数据结构数据结构-绪论绪论本章小结本章小结1.数据、数据结构等基本概念2.对数据结构的两个层次的理解逻辑结构的四种形式存储结构的两种形式3.抽象数据类型的表示方法4.理解算法五个要素的确切含义5.掌握计算语句频度和估算算法时间复杂度的方法数据结构数据结构-绪论绪论复杂度分析练习HLoj 1015HLoj 1063HDoj 2374
