数据结构（第二版）课件

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,fgfh,精品课件,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,fgfh,精品课件,*,数据结构,（第二版）,严蔚敏 吴伟民,清华大学出版社,精品课件,数据结构 （第二版）严蔚敏 吴伟民精品课件,第一章 绪论,1.1,的主要内容,1.2 基本术语,1.3 算法描述及分析,精品课件,第一章 绪论 1.1 的主要内容精品课件,1.1 的主要内容,99080-3 班号,3202670 计算机学院办公室电话号码,610054 电子科技大学邮编,510102780618748 身份证号码,例1,：,99080-33202670610054510102780618748,结论1.,杂乱的数据不能表达和交流信息,精品课件,1.1 的主要内容99080-3 班号,1.1 的主要内容,例,2: 电话号码簿 (,a,1,，,b,1,) (a,2,，,b,2,)(a,n,，,b,n,),其中：,a,i,为某人姓名，,b,i,为该人的电话号码。,要求：设计一个算法，给定一个姓名时，,能查出此人的电话号码。,如果姓名和电话号码的排列次序无规律，,则只能逐一比较姓名进行查找,如果姓名按字典顺序组织，则查找就快捷多了,结论2.,数据之间是有联系的,这些联系常常影响算法的选择和效率。,DS,就是要研究数据之间的联系。,精品课件,1.1 的主要内容例2: 电话号码簿 (a1，,1.1 的主要内容,例3：大学学生管理机构,学校,一系八系,一年级二年级三年级四年级,班班,张三李四,结论,数据之间是有结构的,例中数据之间呈分层结构（树状结构）,DS,就是要研究,数据之间的各类结构,。,精品课件,1.1 的主要内容例3：大学学生管理机构结论,1.1 的主要内容,例：图书目录管理,设每个书目含：书名，作者，登录号，分类，出版年月,对图书目录常有如下操作：,查找：某书在书库中是否存在？,插入：购进新书时的登录；,删除：报废或丢失的书，需从目录中去掉；,结论,在某种数据结构上可定义一组运算,DS,就是要研究各类数据结构上的各种运算。,精品课件,1.1 的主要内容例：图书目录管理结论在,1.1 的主要内容,综上所述：,DS,主要研究内容：,数据的各种逻辑结构和物理结构，以及它们之间的相应关系；,对每种结构定义相适应的各种运算；,设计出相应的算法；,分析算法的效率。,常见的数据结构有：数组、栈、队列、表、串、树、图和文件等。,精品课件,1.1 的主要内容综上所述： DS主要研究内,数据结构与问题求解,1. 在计算机中建立一个与实际问题有比较密切对应关系的,模型,；,2. 计算机内部的,数据,表示了需要被处理的实际对象，包括其内在的性质和关系；,3. 处理这些数据的,程序,则模拟对象领域中的实际过程；,4. 将计算机程序的运行,结果,在实际领域中给予解释，便得到实际问题的解。,精品课件,数据结构与问题求解1. 在计算机中建立一个与实际问题有比较密,1.2 基本术语,数据,（,Data),：,所有能被,计算机处理,的,符号,的集合。,数据元素,（,Data Element,）：,是数据这个集合中的一个个体。,设给定数据集合为：,D=d,1,，,d,2,，,d,n,则,d,i,属于,D,，,并称,d,i,为,数据元素。,数据项,（,Data Item,）：,数据元素常常还可分为若干个数据项，数据项是数据具有意义的最小单位。,精品课件,1.2 基本术语数据（Data)：所有能被计算机处理的符号的,1.2 基本术语,数据对象,（,Data Object,）:,具有相同特性的数据元素的集合。,例如：数据集合,D=0,，,1,，,，A,，,B,，,，,Z,则：,数据对象正整数,N,0,，,1,，,数据对象字母,C,A,，,B,，,，,Z,数据元素是数据的一个个体，,数据对象是数据的一个子集。,精品课件,1.2 基本术语数据对象（Data Object）: 具有相,1.2 基本术语,数据结构,（,Data Structure,）：,是带有结构的数据元素的集合。,所谓结构就是数据元素之间的关系，即描述数据元素之间的运算及运算规则。,用集合的形式描述，数据结构是一个二元组：,DS=(D,，,R),其中：,D,是数据元素的集合，,R,是,D,上,关系的集合。,简言之，数据元素和其相互关系称为数据结构,精品课件,1.2 基本术语数据结构（Data Structure）：是,1.2 基本术语,逻辑结构,（,Logical Structure,）：,指数据元素之间的结构关系。,物理结构,（,Physical Structure,）：,指数据结构在机内的表示，也称为存储结构。,精品课件,1.2 基本术语逻辑结构（Logical Structure,1.3,算法,描述和算法分析,一,算法,（,Algorithm,）,算法概念：算法是一个有限的指令集，,遵循指令流可以完成特定的功能。,算法基本特性：,有穷性,：算法经有限步后结束；,确定性,：下一步必须是明确的；,可行性,：每一步是可执行的；,精品课件,1.3 算法描述和算法分析一算法（Algorithm）,1.3,算法,描述和算法分析,算法与程序的区别,算法,是解决问题的一种方法或一个过程，考虑如何将输入转换成输出，一个问题可以有多种算法。,程序,是用某种程序设计语言对算法的具体实现。,主要区别在：,有穷性,和,描述方法,程序可以是无穷的，例如,OS,，,算法是有穷的；,程序是用程序设计语言描述，在机器上可以执行；,算法还可以用框图、自然语言等方式描述。,精品课件,1.3 算法描述和算法分析算法与程序的区别主要区别在：有,1.3,算法描述,和算法分析,二算法描述语言类,Pascal,为了便于理解掌握算法的思想和实质，本课程采用类,Pascal,语言,来描述各种算法。,所有的算法均以过程或函数的形式表示；,PROC,过程,名 (,参数,表)；,算法说明,语句组,ENDP,；,过程,名,精品课件,1.3 算法描述和算法分析二算法描述语言类Pascal,1.3,算法描述,和算法分析,FUNC,函数名 (,参数,表)：类型；,函数说明,语句组,RETURN(f),ENDF,；,函数名,调用过程语句为：过程名（,参数,表）,调用函数语句为：变量名：函数名（,参数,表）,精品课件,1.3 算法描述和算法分析 FUNC 函数名 (参数表)：,1.3,算法描述,和算法分析,出错语句：,ERROR,（,出错信息）；,注释语句：注释内容,语句结束符号：；,语句组符号：,基本函数：,max(),、,min(),、,abs(),、eof 、eoln,布尔运算：,AND,、,OR,、,NOT,、,CAND,、,COR,精品课件,1.3 算法描述和算法分析出错语句：ERROR（出错信息,1.3,算法描述,和算法分析,赋值语句：变量名：表达式；,分支语句：,IF,条件,THEN,语句,ELSE,语句；,CASE,条件：语句；,条件,n,：,语句,n,；,(ELSE,语句,n+1),ENDC；,精品课件,1.3 算法描述和算法分析赋值语句：变量名：表达式；精品课,1.3,算法描述,和算法分析,循环语句：,FOR,变量名：初值,TO,终值,DO,循环体；,FOR,变量名：初值,DOWNTO,终值,DO,循环体；,WHILE,条件,DO,循环体；,REPEAT,循环体,UNTIL,条件；,标准输入输出过程：,read,（,变量表）；,write（,变量表）；,精品课件,1.3 算法描述和算法分析循环语句：精品课件,1.3 算法描述和,算法分析,三算法分析,如何衡量一个,正确算法,的好坏？,衡量的三个尺度：,运行所花费的时间（算法的时间特性）；,所占用存储空间的大小（算法的空间特性）；,其他（可读性、易调性、健壮性等）。,时间和空间特性的巨大改进源于更好的数据结构或算法。,精品课件,1.3 算法描述和算法分析三算法分析精品课件,1.3 算法描述和,算法分析,语句频度,（,Frequency Count,）：,语句可能重复执行的最大次数。,时间复杂度,（,Time Complexity,）：,设算法中所有语句的语句频度为,t(n),，,f(n),是当,n,趋向无穷大时与,t(n),为同阶无穷大，,则算法的时间复杂度,T(n)=O(f(n),其中：,n,为算法计算量或称为规模（,size,）；,f(n),是运算时间随,n,增大时,的增长率；,O(f(n),是,算法时间特性的量度。,精品课件,1.3 算法描述和算法分析语句频度（Frequency Co,第一章小结,数据结构概念,算法时间复杂度,精品课件,第一章小结数据结构概念精品课件,