数据结构简介课件.ppt

1、注：第注：第8章和带章和带*章节不作要求章节不作要求讨论讨论5个问题：个问题： 学生基本情况 学 号 姓 名 性 别 班级 . 9905001 李力 男 99101 . 9905002 杜军 男 99101 . 9905003 程霄寒 女 99101 . . .9905030 方勇. 男 99101 . 管理与经济学院管理与经济学院经济系经济系管理系管理系国际经济与贸易国际经济与贸易人力资源人力资源信息管理与信息信息管理与信息系统系统电子商务电子商务1.1 什么是数据结构什么是数据结构是相互之间存在一种或多种特定相互之间存在一种或多种特定关系关系的的数据元素数据元素的的集合，表示为：集合，表示

2、为： （数值或非数值数值或非数值） Data_Structure=（D, R）是指同一数据元素类型中各元素之间存在的关系。是指同一数据元素类型中各元素之间存在的关系。元素有限集元素有限集关系有限集关系有限集针对针对非数值计算非数值计算的程序设计问题，研究计算机的程序设计问题，研究计算机的的操作对象操作对象以及它们之间的以及它们之间的关系关系和和操作操作。 是介于是介于数学、计算机硬件和计算机软件数学、计算机硬件和计算机软件三者之三者之间的一门核心课程。间的一门核心课程。Data_Structure=( D, R )数学数学软件软件硬件硬件关系关系对象对象关系关系操作操作对象对象关系关系操作操作

3、Back1.2 学习数据结构的意义学习数据结构的意义计算机计算机内的数值运算依靠方程式，而内的数值运算依靠方程式，而非数值运算非数值运算（如表、树、图等）则要依靠数据结构。（如表、树、图等）则要依靠数据结构。数据结构是一门学科，针对数据结构是一门学科，针对非数值计算非数值计算的程序的程序设计问题，研究计算机的设计问题，研究计算机的操作对象操作对象以及它们之间的以及它们之间的关系和操作关系和操作等等。等等。同样的数据对象，用不同的数据结构来同样的数据对象，用不同的数据结构来表示，运算效率可能有明显的差异。表示，运算效率可能有明显的差异。 Back1.数据数据(data)所有能被计算机识别、存储和

4、处理的符号的集所有能被计算机识别、存储和处理的符号的集合（合（包括数字、字符、声音、图像等信息包括数字、字符、声音、图像等信息）。）。 2.数据元素数据元素(dataelement)是数据的是数据的基本基本单位，具有完整单位，具有完整确定的实际意义确定的实际意义(又称元素、结点，顶点、记录等又称元素、结点，顶点、记录等）。）。3.数据项数据项(Dataitem)构成数据元素的项目。是具有独立含构成数据元素的项目。是具有独立含义的义的最小最小标识单位（标识单位（又称字段、域、属性又称字段、域、属性等等）。）。三者之间的关系：三者之间的关系：数据数据 数据元素数据元素 数据项数据项例：例：班级通讯

5、录班级通讯录 个人记录个人记录 姓名、年龄姓名、年龄 1.3.1 基本概念和术语基本概念和术语5.数据结构数据结构(data structure)(data structure)-相互之间存在一种或多种特定关系的数据元素的集合。相互之间存在一种或多种特定关系的数据元素的集合。数据元素之间的关系称为数据元素之间的关系称为结构。结构。四类基本结构：四类基本结构： 集合集合 线性结构线性结构 树形结构树形结构 图状结构图状结构集合结构：集合结构： 仅同属一个集合仅同属一个集合 线性结构线性结构: 一对一（一对一（1:1) 树树 结结 构构: 一对多（一对多（1:n) 图图 结结 构构: 多对多多对多

6、 (m:n)非线性非线性线线 性性逻辑结构可细分为逻辑结构可细分为4类：类：答：指数据元素之间的逻辑关系。即从逻辑关系上描述答：指数据元素之间的逻辑关系。即从逻辑关系上描述数据，它数据，它与数据的存储无关与数据的存储无关，是，是独立于计算机独立于计算机的。的。解释解释1：什么是逻辑结构？：什么是逻辑结构？（1）S=(D,R)D=a,b,c,d,e,fR=(a,e),(b,c),(c,a),(e,f),(f,d)解：解： 上述表达式可用图形表示为：上述表达式可用图形表示为：b c a e f d此结构为此结构为线性线性的。的。例：例：用图形表示下列数据结构，并指出它们是属于线用图形表示下列数据结

7、构，并指出它们是属于线性结构还是非线性结构。性结构还是非线性结构。 d1d5d2d4d3该结构该结构是非线性是非线性的。的。解：解：上述表达式可用图形表示为：上述表达式可用图形表示为：（2） S=(D, R) D=di | 1i5 R=(di , dj ), ij 答：物理结构亦称答：物理结构亦称存储结构存储结构，是数据的逻辑结构在计算机，是数据的逻辑结构在计算机存储器内的表示（或映像）。它存储器内的表示（或映像）。它依赖于计算机依赖于计算机。存储结构可分为存储结构可分为4大类：大类：例：例：复数复数3.02.3i 的两种存储方式：的两种存储方式：顺序、链式、索引、散列顺序、链式、索引、散列2

8、.303023.00300041503023.0030004152.3法法1：地址地址 内容内容法法2：地址地址 内容内容2字节字节解释解释2：什么叫数据的物理结构？：什么叫数据的物理结构？ 答：在数据的逻辑结构上定义的操作算法。答：在数据的逻辑结构上定义的操作算法。它它在数据的存储结构上实现在数据的存储结构上实现。最常用的数据运算有最常用的数据运算有 5 种：种：插入、删除、修改、查找、排序插入、删除、修改、查找、排序解释解释3：什么是数据的运算？：什么是数据的运算？Back1.4.1 数据类型与抽象数据类型的区别？数据类型与抽象数据类型的区别？ 1.4.2 抽象数据类型如何定义？抽象数据类

9、型如何定义？ 1.4.3 抽象数据类型如何表示和实现？抽象数据类型如何表示和实现？ 讨论：讨论：抽象数据类型抽象数据类型和和伪码伪码是学习数据结构的工具是学习数据结构的工具1.4.1 数据类型与抽象数据类型的区别数据类型与抽象数据类型的区别数据类型：数据类型：是一个是一个值的集合值的集合和定义在该值上的和定义在该值上的一组操作一组操作的总称。的总称。抽象数据类型：抽象数据类型：由由用户定义用户定义，用以表示应用问题的数，用以表示应用问题的数据模型。它由基本的数据类型构成，并包括一组相关据模型。它由基本的数据类型构成，并包括一组相关的的服务服务（或称操作）（或称操作） 它与数据类型实质上是一个概

10、念，但其特征是它与数据类型实质上是一个概念，但其特征是使用使用与与实现分离实现分离，实行，实行封装封装和和信息隐蔽信息隐蔽（独立于计算机）（独立于计算机）1.4.2 抽象数据类型如何定义抽象数据类型如何定义抽象数据类型抽象数据类型可以用以下的三元组来表示：可以用以下的三元组来表示： ADT = ADT = （D D，R R，P P） ADTADT抽象数据类型名抽象数据类型名 数据数据对象对象： 数据数据关系关系： 基本基本操作操作 ： ADT ADT抽象数据类型抽象数据类型名名ADT常用常用定义定义格式格式数据对象数据对象D D上的关系集上的关系集D D上的操作集上的操作集 1.4.3 抽象数

11、据类型如何表示和实现抽象数据类型如何表示和实现 抽象数据类型可以通过抽象数据类型可以通过固有的固有的数据类型（如整型、数据类型（如整型、实型、字符型等）来表示和实现。实型、字符型等）来表示和实现。注注1 1 ：它有些类似：它有些类似C C语言中的语言中的结构（结构（struct)struct)类型类型，但，但增加了相关的增加了相关的服务服务。 注注2 2 ：教材中用：教材中用类类C C语言（介于伪码和语言（介于伪码和C C语言之间）作语言之间）作为描述工具。其描述语法汇总在教材为描述工具。其描述语法汇总在教材P10-11P10-11上。上。 Back1.5.1什么是算法？如何评判算法的好坏？什

12、么是算法？如何评判算法的好坏？1.5.2时间复杂度和空间复杂度如何表示？时间复杂度和空间复杂度如何表示？1.5.3计算举例计算举例1.5.1 什么是算法？如何评判一个算法的好坏？什么是算法？如何评判一个算法的好坏？常用常用时间复杂度时间复杂度来衡量来衡量算法的基本特性：算法的基本特性：算法评价指标：算法评价指标：有穷性、确定性、可行性、有穷性、确定性、可行性、必有必有输出输出正确性、可读性、健壮性、正确性、可读性、健壮性、效率效率与与低存储量低存储量需求需求常用常用空间复杂度空间复杂度来衡量来衡量程序设计的实质：好算法好结构程序设计的实质：好算法好结构算法算法是对特定问题求解步骤的一种描述，它

13、是指令的是对特定问题求解步骤的一种描述，它是指令的有限序列，是一系列输入转换为输出的计算步骤。有限序列，是一系列输入转换为输出的计算步骤。注：注： 1） O（）为渐近符号（）为渐近符号。 2） 空间复杂度空间复杂度S(n)按数量级递增顺序也与上表类似。按数量级递增顺序也与上表类似。复杂度高复杂度高复杂度低复杂度低时间复杂度时间复杂度T(n)按数量级递增顺序为：按数量级递增顺序为：1.5.2 时间复杂度和空间复杂度如何表示？时间复杂度和空间复杂度如何表示？多项多项3n+2=O(n)因为因为3n+2 4nforn 26*2n+n2=O(2n)因为因为6*2n+n2 7*2nforn 4例：例： 渐

14、进符号渐进符号（O）的定义：当且仅当存在一个正的常）的定义：当且仅当存在一个正的常数数C，使得对所有的，使得对所有的n n0 ，有，有f(n) Cg(n)，则：，则： f(n)=O(g(n)1.5.3 计算举例计算举例 该算法的运行时间由程序中所有语句的该算法的运行时间由程序中所有语句的频度频度（即该语（即该语句重复执行的次数）句重复执行的次数）之和之和构成。构成。 解：解：分析：分析：显然，语句的频度是显然，语句的频度是1。设语句。设语句2的频度是的频度是f(n)，则有：，则有：算法的时间复杂度由算法的时间复杂度由嵌套最深层语句的频度嵌套最深层语句的频度决定决定例：分析以下程序段的时间复杂度

15、。例：分析以下程序段的时间复杂度。i=1;while(i=n)i=i*2;即即f(n)log2n，取最大值取最大值f(n)=log2n所以该程序段的时间复杂度所以该程序段的时间复杂度T(n)=1+f(n)=1+ log2n= O( log2n)2f(n)n本章小结本章小结数据结构课程数据结构课程数据结构算法程序，涉及数学、数据结构算法程序，涉及数学、计算机硬件和软件。计算机硬件和软件。数据结构定义数据结构定义指互相有关联的数据元素的集合，指互相有关联的数据元素的集合，可用可用data_Structure=(D,R)data_Structure=(D,R)表示。表示。 数据结构内容数据结构内容数据的逻辑结构、存储结构和基本数据的逻辑结构、存储结构和基本运算运算(计算机处理非数值对象计算机处理非数值对象)数据结构学习工具数据结构学习工具抽象数据类型和伪码（类抽象数据类型和伪码（类C）算法效率指标算法效率指标时间效率和空间效率时间效率和空间效率