数据结构（第二版）课件

《数据结构（第二版）课件》由会员分享，可在线阅读，更多相关《数据结构（第二版）课件（22页珍藏版）》请在装配图网上搜索。

1、,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,,,,fgfh,精品课件,*,,,,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,,fgfh,精品课件,*,数据结构,（第二版）,严蔚敏 吴伟民,,,,,,,,,清华大学出版社,精品课件,数据结构 （第二版）严蔚敏 吴伟民精品课件,第一章 绪论,,1.1,,的主要内容,1.2 基本术语,1.3 算法描述及分析,精品课件,第一章 绪论 1.1 的主要内容精品课件,1.1 的主要内容,99080-3 班号,3202670 计算机学院办公室电话号码,

2、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,为该人的电话号码。,要求：设计一个算法，给定一个姓名时，,能查出此人的电话号码。,,如果姓名和电话号码的排列次序无规律，,则只能逐一比较姓名进行查找,如果姓名按字典顺序组织，

3、则查找就快捷多了,结论2.,数据之间是有联系的,这些联系常常影响算法的选择和效率。,《,DS,》,就是要研究数据之间的联系。,精品课件,1.1 的主要内容例2: 电话号码簿 (a1，,1.1 的主要内容,例3：大学学生管理机构,,,学校,,一系　　．．．八系　．．．,,一年级　二年级　三年级　四年级,,,１班　．．．８班,张三．．．李四,结论３．,数据之间是有结构的,例３中数据之间呈分层结构（树状结构）,《,DS,》,就是要研究,数据之间的各类结构,。,精品课件,1.1 的主要内容例3：大学学生管理机构结论３．,1.1 的主要内容,例４：图书目录管理,设每个书目含：书名，作者，登录号，分类，

4、出版年月,对图书目录常有如下操作：,查找：某书在书库中是否存在？,插入：购进新书时的登录；,删除：报废或丢失的书，需从目录中去掉；,结论４．,在某种数据结构上可定义一组运算,《,DS,》,就是要研究各类数据结构上的各种运算。,精品课件,1.1 的主要内容例４：图书目录管理结论４． 在,1.1 的主要内容,综上所述：,《,DS,》,主要研究内容：,数据的各种逻辑结构和物理结构，以及它们之间的相应关系；,对每种结构定义相适应的各种运算；,设计出相应的算法；,分析算法的效率。,,常见的数据结构有：数组、栈、队列、表、串、树、图和文件等。,精品课件,1.1 的主要内容综上所述： 《DS》主要研究内,数

5、据结构与问题求解,1. 在计算机中建立一个与实际问题有比较密切对应关系的,模型,；,2. 计算机内部的,数据,表示了需要被处理的实际对象，包括其内在的性质和关系；,3. 处理这些数据的,程序,则模拟对象领域中的实际过程；,4. 将计算机程序的运行,结果,在实际领域中给予解释，便得到实际问题的解。,精品课件,数据结构与问题求解1. 在计算机中建立一个与实际问题有比较密,1.2 基本术语,数据,（,Data),：,所有能被,计算机处理,的,符号,的集合。,数据元素,（,Data Element,）：,是数据这个集合中的一个个体。,设给定数据集合为：,,D={d,1,，,d,2,，．．．，,d,n,

6、},,则,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 基本术

7、语数据对象（Data Object）: 具有相,1.2 基本术语,数据结构,（,Data Structure,）：,是带有结构的数据元素的集合。,,所谓结构就是数据元素之间的关系，即描述数据元素之间的运算及运算规则。,用集合的形式描述，数据结构是一个二元组：,,DS=(D,，,R),,,其中：,D,是数据元素的集合，,R,是,D,上,关系的集合。,简言之，数据元素和其相互关系称为数据结构,精品课件,1.2 基本术语数据结构（Data Structure）：是,1.2 基本术语,逻辑结构,（,Logical Structure,）：,指数据元素之间的结构关系。,物理结构,（,Physical S

8、tructure,）：,指数据结构在机内的表示，也称为存储结构。,精品课件,1.2 基本术语逻辑结构（Logical Structure,1.3,算法,描述和算法分析,一．,算法,（,Algorithm,）,１．,算法概念：算法是一个有限的指令集，,遵循指令流可以完成特定的功能。,２．算法基本特性：,,有穷性,：算法经有限步后结束；,,确定性,：下一步必须是明确的；,,可行性,：每一步是可执行的；,精品课件,1.3 算法描述和算法分析一．算法（Algorithm）２．,1.3,算法,描述和算法分析,３．算法与程序的区别,算法,是解决问题的一种方法或一个过程，考虑如何将输入转换成输出，一个问题可

9、以有多种算法。,程序,是用某种程序设计语言对算法的具体实现。,主要区别在：,有穷性,和,描述方法,程序可以是无穷的，例如,OS,，,算法是有穷的；,程序是用程序设计语言描述，在机器上可以执行；,算法还可以用框图、自然语言等方式描述。,精品课件,1.3 算法描述和算法分析３．算法与程序的区别主要区别在：有,1.3,算法描述,和算法分析,二．算法描述语言——类,Pascal,,为了便于理解掌握算法的思想和实质，本课程采用类,Pascal,语言,来描述各种算法。,所有的算法均以过程或函数的形式表示；,,PROC,,过程,名 (,参数,表)；,｛算法说明｝,语句组,,ENDP,；,{,过程,名},精品

10、课件,1.3 算法描述和算法分析二．算法描述语言——类Pascal,1.3,算法描述,和算法分析,,FUNC,函数名 (,参数,表)：类型；,｛函数说明｝,语句组,,RETURN(f),,ENDF,；,{,函数名},,调用过程语句为：过程名（,参数,表）,调用函数语句为：变量名：＝函数名（,参数,表）,精品课件,1.3 算法描述和算法分析 FUNC 函数名 (参数表)：,1.3,算法描述,和算法分析,出错语句：,ERROR,（‘,出错信息’）；,注释语句：｛注释内容｝,语句结束符号：；,语句组符号：［　］,基本函数：,max(),、,min(),、,,abs(),、eof 、eoln,布尔运

11、算：,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,循环体；,

12、,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,第一章 小结,数据结构概念,算法时间复杂度,精品课件,第一章 小结数据结构概念精品课件,