数据结构第二版.ppt

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