数据结构简介课件.ppt

《数据结构简介课件.ppt》由会员分享，可在线阅读，更多相关《数据结构简介课件.ppt（42页珍藏版）》请在三一办公上搜索。

1、学时数：72学 分：4教 材：严蔚敏等，数据结构（C语言版），清华大学出版社，1997年4月第1版参考书：1李春葆，数据结构（C语言篇）习题与解析（修订版），清华大学出版社，2002年4月。2 薛超英，数据结构（第二版），华中科技大学出版社，2002年8月。3殷人昆等，数据结构（用面向对象方法与C+描述），清华大学出版社，1999年7月（2002年配题集）,目录,第1章 绪论第2章 线性表第3章 栈和队列 第4章 串 第5章 数组和广义表 第6章 树和二叉树 第7章 图 第9章 查找 第10章 排序,注：第8章和带*章节不作要求,第1章 绪论,讨论5个问题：,1.1 什么是数据结构 1.2 学

2、习数据结构的意义 1.3 数据结构主要涵盖内容 1.4 什么是抽象数据类型 1.5 算法效率的度量,计算机解题的基本方法是：分析问题，确定数据模型；设计相应的算法；编写程序；反复调试程序直至得到正确的结果。有些问题的数据模型可以用具体代数方程、矩阵等表示。然而，更多的实际问题是无法用数学方程表示的。下面给出三个简单的例子加以说明。表1-1-1是一个学生基本情况表。表中有30个记录，按学号顺序排列，它们之间存在一对一的关系，这是一种线性结构，主要操作有查找、修改、插入或删除等。,举例1,表1-1-1 学生基本情况表,举例2,图1-1-1表示的是我院的专业设置情况。在图1-1-1中可以把一所学院名

3、称看成树根，把下设的若干个系名看成它的树枝中间结点，把每个系的若干个专业方向看成树叶，这就形成一个树形结构。树形结构通常用表示结点的分层组织，结点之间是一对多的关系。对于树形结构的主要操作是遍历、查找、插入或删除等。,管理与经济学院,经济系,管理系,国际经济与贸易,人力资源,图1-1-1 树型数据结构,信息管理与信息系统,电子商务,举例3,图1-1-2是一个描述若干个城镇之间的公路网。图中每个顶点代表一个城镇，边表示城镇之间的道路。显然在图1-1-2中各个顶点之间的关系更加复杂，它们是一种多对多的关系。具有这种关系的结构称之为图形结构。在实际就用中假设从某个原料产地把原料运往各加工地，需要制定

4、一个运输方案使得运输费用最省。,图1-1-2 图型结构示例,1.1 什么是数据结构,是相互之间存在一种或多种特定关系的数据元素的集合，表示为：,（数值或非数值）,Data_Structure=（D,R）,是指同一数据元素类型中各元素之间存在的关系。,元素有限集,关系有限集,数据结构课程的地位,针对非数值计算的程序设计问题，研究计算机的操作对象以及它们之间的关系和操作。是介于数学、计算机硬件和计算机软件三者之间的一门核心课程。,Data_Structure=(D,R),数学,软件,硬件,关系,对象关系操作,对象关系操作,Back,1.2 学习数据结构的意义,计算机内的数值运算依靠方程式，而非数值

5、运算（如表、树、图等）则要依靠数据结构。,数据结构是一门学科，针对非数值计算的程序设计问题，研究计算机的操作对象以及它们之间的关系和操作等等。,程序设计好算法好结构,同样的数据对象，用不同的数据结构来表示，运算效率可能有明显的差异。,Back,1.3 数据结构涵盖的内容,1.数据(data)所有能被计算机识别、存储和处理的符号的集合（包括数字、字符、声音、图像等信息）。2.数据元素(data element)是数据的基本单位，具有完整确定的实际意义(又称元素、结点，顶点、记录等）。3.数据项(Data item)构成数据元素的项目。是具有独立含义的最小标识单位（又称字段、域、属性 等）。,三者

6、之间的关系：数据 数据元素 数据项,例：班级通讯录 个人记录 姓名、年龄,1.3.1 基本概念和术语,4.数据对象(data object),由性质相同(类型相同)的数据元素组成的集合。数据对象是数据的一个子集。例1 由4个整数组成的数据对象 D1=20,-30,88,45 例2 由正整数组成的数据对象 D2=1,2,3,.例3 由26个字母组成的数据对象 D3=A,B,C,.,Z 其中：D1，D3是有穷集，D2是无穷集。,5.数据结构(data structure)-相互之间存在一种或多种特定关系的数据元素的集合。数据元素之间的关系称为结构。四类基本结构：,集合 线性结构 树形结构 图状结构

7、,集合结构：仅同属一个集合,线性结构:一对一（1:1),树 结 构:一对多（1:n),图 结 构:多对多(m:n),非线性,线 性,逻辑结构可细分为4类：,答：指数据元素之间的逻辑关系。即从逻辑关系上描述数据，它与数据的存储无关，是独立于计算机的。,解释1：什么是逻辑结构？,1.线性表 2.栈 线性结构 3.队列,双队列 4.数组数据结构 5.字符串 非 线 性 1.树,二叉树 结 构 2.图,数据结构(逻辑结构)分类,（1）S=(D,R)D=a,b,c,d,e,f R=(a,e),(b,c),(c,a),(e,f),(f,d),解：上述表达式可用图形表示为：,b c a e f d,此结构为

8、线性的。,例：用图形表示下列数据结构，并指出它们是属于线性结构还是非线性结构。,d1 d5 d2 d4 d3,该结构是非线性的。,解：上述表达式可用图形表示为：,（2）S=(D,R)D=di|1i5 R=(di,dj),ij,答：物理结构亦称存储结构，是数据的逻辑结构在计算机存储器内的表示（或映像）。它依赖于计算机。,存储结构可分为4大类：,例：复数3.02.3i的两种存储方式：,顺序、链式、索引、散列,法1：地址 内容,法2：地址 内容,2字节,解释2：什么叫数据的物理结构？,答：在数据的逻辑结构上定义的操作算法。它在数据的存储结构上实现。,最常用的数据运算有 5 种：,插入、删除、修改、查

9、找、排序,解释3：什么是数据的运算？,算法的设计取决于选定的数据逻辑结构，而算法的实现依赖于采用的存储结构。,Back,1.4 什么是抽象数据类型,1.4.1 数据类型与抽象数据类型的区别？1.4.2 抽象数据类型如何定义？1.4.3 抽象数据类型如何表示和实现？,讨论：,抽象数据类型和伪码是学习数据结构的工具,1.4.1 数据类型与抽象数据类型的区别,数据类型：是一个值的集合和定义在该值上的一组操作的总称。,抽象数据类型：由用户定义，用以表示应用问题的数据模型。它由基本的数据类型构成，并包括一组相关的服务（或称操作）,它与数据类型实质上是一个概念，但其特征是使用与实现分离，实行封装和信息隐蔽

10、（独立于计算机）,1.4.2 抽象数据类型如何定义,抽象数据类型可以用以下的三元组来表示：ADT=（D，R，P）,ADT抽象数据类型名 数据对象：数据关系：基本操作：ADT抽象数据类型名,ADT常用定义格式,数据对象,D上的关系集,D上的操作集,1.4.3 抽象数据类型如何表示和实现,抽象数据类型可以通过固有的数据类型（如整型、实型、字符型等）来表示和实现。,注1：它有些类似C语言中的结构（struct)类型，但增加了相关的服务。注2：教材中用类C语言（介于伪码和C语言之间）作为描述工具。其描述语法汇总在教材P10-11上。,提示：教材中例1-6和例1-7分别给出了抽象数据类型“三元组”的定义

11、、表示和实现，请自己先试读一遍。当课程内容学习到50%以后，你再回头看这个例子，会发现自己已能完全看懂了！,Back,1.5 算法效率的度量,讨论：,1.5.1 什么是算法？如何评判算法的好坏？1.5.2 时间复杂度和空间复杂度如何表示？1.5.3 计算举例,1.5.1 什么是算法？如何评判一个算法的好坏？,常用时间复杂度来衡量,算法的基本特性：,算法评价指标：,有穷性、确定性、可行性、必有输出,正确性、可读性、健壮性、效率与低存储量需求,常用空间复杂度来衡量,程序设计的实质：好算法好结构,算法是对特定问题求解步骤的一种描述，它是指令的有限序列，是一系列输入转换为输出的计算步骤。,注：1）O（

12、）为渐近符号。2）空间复杂度S(n)按数量级递增顺序也与上表类似。,复杂度高,复杂度低,时间复杂度T(n)按数量级递增顺序为：,1.5.2 时间复杂度和空间复杂度如何表示？,多项,3n+2=O(n)因为3n+24n forn2,6*2n+n2=O(2n)因为6*2n+n27*2n forn4,例：,渐进符号（O）的定义：当且仅当存在一个正的常数C，使得对所有的nn0，有f(n)Cg(n)，则：f(n)=O(g(n),算法的时间复杂度-,算法(或程序)中基本操作(或语句)重复执行的次数的总和。设n为求解的问题的规模,基本操作(或语句)执行次数总和称为语句频度,记作f(n)；时间复杂度记作T(n)

13、,有：T(n)=O(f(n)例1 int s；scanf(“%d”,&s)；s+；printf(“%d”,s)；其中：语句频度为：f(n)=f(1)=3 时间复杂度为：T(n)=O(f(n)=O(3)=O(1）O(1)称成为常量阶/常量数量级,例2 分析下面的算法,void sum(int a,int n)int s=0,i；/1次 for(i=0；in；i+)/n次 s=s+ai；/n次 printf(“%d”,s)；/1次 其中：语句频度为：f(n)=1+n+n+1 时间复杂度为：T(n)=O(f(n)=O(2n+2)=O(n）O(n)称成为线性阶/线性数量级,例3 分析下面的算法,1.v

14、oid sum(int m,int n)2.int i,j,s=0；/1次 3.for(i=1；i=m；i+)/m次 4.for(j=1；j=n；j+)/m*n次 5.s+；/m*n次 6.printf(“%d”,s)；/m次 7.8.其中:f(m,n)=1+m+2*m*n+m=2mn+2m+1 当m=n时,f(n)=2n2+2n+1 T(n)=O(f(n)=O(2n2+2n+1)=O(n2)O(n2)称成为平方阶/平方数量级,例4 分析下面的算法,1.void sum(int n)2.int i,j,s=0；/1次 3.for(i=1；i=n；i+)/n次 4.for(j=1；j=i；j+)

15、/?次 5.s+；/?次 6.printf(“%d”,s)；/n次 7.8.,例4 分析下面的算法,其中：第4行的次数为 1+2+.+n=n(1+n)/2 第5行的次数为 1+2+.+n=n(1+n)/2 f(n)=1+n+n(n+1)+n=n2+3n+1 T(n)=O(f(n)=O(n2）O(n2）称成为平方阶/平方数量级,例5 冒泡排序的C语言算法/对数组a中n个数按递增次序作冒泡排序 1.Void bubble1(int a,int n)2.int i,j,temp；3.for(i=0；iaj+1)/？次 6.temp=aj；/？次 7.aj=aj+1；/？次 8.aj+1=temp；/

16、？次 9.10.for(i=0；in；i+)/n 次 11.printf(“%d”,ai)；/n 次 12.思考：在最好情况下，f(n)=?T(n)=O(f(n)=?在最坏情况下，f(n)=?T(n)=O(f(n)=?,例6 冒泡排序的“类C语言”算法/对数组a中n个数按递增次序作冒泡排序 1.void bubble2(int a,int n)2.for(i=n-1,change=TRUE；i1&change；i-)3.change=FALSE；/change为交换标志 4.for(j=0；jaj+1)6.aj aj+1；/交换元素 7.change=TRUE；/修改交换标志 8.9.10.思

17、考：在最好情况下，f(n)=?T(n)=O(f(n)=?在最坏情况下，f(n)=?T(n)=O(f(n)=?,5.算法的空间复杂度-执行算法所需存储空间的大小。,1.5.3 计算举例,该算法的运行时间由程序中所有语句的频度（即该语句重复执行的次数）之和构成。,解：,分析：显然，语句的频度是1。设语句2的频度是f(n)，则有：,算法的时间复杂度由嵌套最深层语句的频度决定,即f(n)log2n，取最大值f(n)=log2n,所以该程序段的时间复杂度T(n)=1+f(n)=1+log2n=O(log2n),2f(n)n,本章小结,数据结构课程 数据结构算法程序，涉及数学、计算机硬件和软件。数据结构定义指互相有关联的数据元素的集合，可用data_Structure=(D,R)表示。数据结构内容数据的逻辑结构、存储结构和基本运算(计算机处理非数值对象)数据结构学习工具抽象数据类型和伪码（类C）算法效率指标时间效率和空间效率,