数据结构简介课件

,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,学时数,：,72,学 分,：,4,教 材,：严蔚敏等，数据结构（,C,语言版），清华大学出版社，,1997,年,4,月第,1,版,参考书：,1,李春葆，数据结构（,C,语言篇）,习题与解析（修订版），清华大学出版社，,2002,年,4,月。,2,薛超英，数据结构（第二版），华中科技大学出版社，,2002,年,8,月。,3,殷人昆等，数据结构（用面向对象方法与,C+,描述），清华大学出版社，,1999,年,7,月（,2002,年配题集）,学时数：72,1,目录,第,1,章 绪论,第,2,章 线性表,第,3,章 栈和队列,第,4,章 串,第,5,章 数组和广义表,第,6,章 树和二叉树,第,7,章 图,第,9,章 查找,第,10,章 排序,注：第,8,章和带*章节不作要求,目录第1章 绪论注：第8章和带*章节不作要求,2,第,1,章 绪论,讨论,5,个问题：,1.1,什么是数据结构,1.2,学习数据结构的意义,1.3,数据结构主要涵盖内容,1.4,什么是抽象数据类型,1.5,算法效率的度量,第1章 绪论讨论5个问题：1.1 什么是数据结构,3,计算机解题的基本方法是：分析问题，确定数据模型；设计相应的算法；编写程序；反复调试程序直至得到正确的结果。有些问题的数据模型可以用具体代数方程、矩阵等表示。然而，更多的实际问题是无法用数学方程表示的。下面给出三个简单的例子加以说明。,表,1-1-1,是一个学生基本情况表。表中有,30,个记录，按学号顺序排列，它们之间存在一对一的关系，这是一种线性结构，主要操作有查找、修改、插入或删除等。,举例,1,计算机解题的基本方法是：分析问题，确定数据模型；设计相应的算,4,表1-1-1 学生基本情况表,表1-1-1 学生基本情况表,5,举例,2,图,1-1-1,表示的是我院的专业设置情况。在图,1-1-1,中可以把一所学院名称看成树根，把下设的若干个系名看成它的树枝中间结点，把每个系的若干个专业方向看成树叶，这就形成一个树形结构。树形结构通常用表示结点的分层组织，结点之间是一对多的关系。对于树形结构的主要操作是遍历、查找、插入或删除等。,举例2图1-1-1表示的是我院的专业设置情况。在图1-1-1,6,管理与经济学院,经济系,管理系,国际经济与贸易,人力资源,图,1-1-1,树型数据结构,信息管理与信息系统,电子商务,管理与经济学院经济系管理系国际经济与贸易人力资源图1-1-1,7,举例,3,图,1-1-2,是一个描述若干个城镇之间的公路网。图中每个顶点代表一个城镇，边表示城镇之间的道路。显然在图,1-1-2,中各个顶点之间的关系更加复杂，它们是一种多对多的关系。具有这种关系的结构称之为图形结构。在实际就用中假设从某个原料产地把原料运往各加工地，需要制定一个运输方案使得运输费用最省。,举例3图1-1-2是一个描述若干个城镇之间的公路网。图中每个,8,图1-1-2 图型结构示例,图1-1-2 图型结构示例,9,1.1,什么是数据结构,是,相互之间存在一种或多种特定,关系,的,数据元素,的集合，表示为：,（,数值或非数值,）,Data_Structure=,（,D,R,）,是指同一数据元素类型中各元素之间存在的关系。,元素有限集,关系有限集,1.1 什么是数据结构是相互之间存在一种或多种特定关系的数,10,数据结构课程的地位,针对,非数值计算,的程序设计问题，研究计算机的,操作对象,以及它们之间的,关系,和,操作,。,是介于,数学、计算机硬件和计算机软件,三者之间的一门核心课程。,Data_Structure=(D,R),数学,软件,硬件,关系,对象关系操作,对象关系操作,Back,数据结构课程的地位针对非数值计算的程序设计问题，研究计算,11,1.2,学习数据结构的意义,计算机,内的数值运算依靠方程式，而,非数值运算,（如表、树、图等）则要依靠数据结构。,数据结构是一门学科，针对,非数值计算,的程序设计问题，研究计算机的,操作对象,以及它们之间的,关系和操作,等等。,程序设计好算法好结构,同样的数据对象，用不同的数据结构来表示，运算效率可能有明显的差异。,Back,1.2 学习数据结构的意义计算机内的数值运算依靠方程式,12,1.3,数据结构涵盖的内容,1.3 数据结构涵盖的内容,13,1.,数据,(data),所有能被计算机识别、存储和处理的符号的集合（,包括数字、字符、声音、图像等信息,）。,2.,数据元素,(data element),是数据的,基本,单位，具有完整确定的实际意义,(,又称元素、结点，顶点、记录等,）。,3.,数据项,(Data item),构成数据元素的项目。是具有独立含义的,最小,标识单位（,又称字段、域、属性,等,）。,三者之间的关系：,数据,数据元素,数据项,例：,班级通讯录,个人记录,姓名、年龄,1.3.1,基本概念和术语,1.数据(data)所有能被计算机识别、存储和处理的符号,14,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,是无穷集。,4.数据对象(data object)由性质相同(类,15,5.,数据结构,(data structure),-,相互之间存在一种或多种特定关系的数据元素的集合。,数据元素之间的关系称为,结构。,四类基本结构：,集合 线性结构 树形结构 图状结构,5.数据结构(data structure)-集合,16,集合结构：,仅同属一个集合,线性结构,:,一对一（,1:1),树,结,构,:,一对多（,1:n),图,结,构,:,多对多,(m:n),非线性,线,性,逻辑结构可细分为,4,类：,答：指数据元素之间的逻辑关系。即从逻辑关系上描述数据，它,与数据的存储无关,，是,独立于计算机,的。,解释,1,：什么是逻辑结构？,集合结构：仅同属一个集合 线性结构:一对一（1:1,17,1.,线性表,2.,栈,线性结构,3.,队列,双队列,4.,数组,数据结构,5.,字符串,非 线 性,1.,树,二叉树,结 构,2.,图,数据结构,(,逻辑结构,),分类,1.线性,18,（,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,此结构为,线性,的。,例：,用图形表示下列数据结构，并指出它们是属于线性结构还是非线性结构。,（1）S=(D,R)解：上述表达式可用图形表示为：,19,d,1,d,5,d,2,d,4,d,3,该结构,是非线性,的。,解：,上述表达式可用图形表示为：,（,2,）,S=(D,R)D=di|1i5 R=(di,dj),ij,d1 该结构是非线性的。解：上,20,答：物理结构亦称,存储结构,，是数据的逻辑结构在计算机存储器内的表示（或映像）。它,依赖于计算机,。,存储结构可分为,4,大类：,例：,复数,3.0,2.3i,的两种存储方式：,顺序、链式、索引、散列,2.3,0302,3.0,0300,0415,0302,3.0,0300,0415,2.3,法,1,：,地址,内容,法,2,：,地址,内容,2,字节,解释,2,：什么叫数据的物理结构？,答：物理结构亦称存储结构，是数据的逻辑结构在计算机存储器内的,21,答：在数据的逻辑结构上定义的操作算法。,它,在数据的存储结构上实现,。,最常用的数据运算有,5,种：,插入、删除、修改、查找、排序,解释,3,：什么是数据的运算？,答：在数据的逻辑结构上定义的操作算法。最常用的数据运算有,22,算法的设计取决于选定的数据逻辑结构，而算法的实现依赖于采用的存储结构。,Back,算法的设计取决于选定的数据逻辑结构，而算法的实现依赖,23,1.4,什么是抽象数据类型,1.4.1,数据类型与抽象数据类型的区别？,1.4.2,抽象数据类型如何定义？,1.4.3,抽象数据类型如何表示和实现？,讨论：,抽象数据类型,和,伪码,是学习数据结构的工具,1.4 什么是抽象数据类型1.4.1 数据类型与抽象数据,24,1.4.1,数据类型与抽象数据类型的区别,数据类型：,是一个,值的集合,和定义在该值上的,一组操作,的总称。,抽象数据类型：,由,用户定义,，用以表示应用问题的数据模型。它由基本的数据类型构成，并包括一组相关的,服务,（或称操作）,它与数据类型实质上是一个概念，但其特征是,使用,与,实现分离,，实行,封装,和,信息隐蔽,（独立于计算机）,1.4.1 数据类型与抽象数据类型的区别数据类型：是一个值,25,1.4.2,抽象数据类型如何定义,抽象数据类型,可以用以下的三元组来表示：,ADT=,（,D,，,R,，,P,）,ADT,抽象数据类型名,数据,对象,：,数据,关系,：,基本,操作,：,ADT,抽象数据类型,名,ADT,常用定义格式,数据对象,D,上的关系集,D,上的操作集,1.4.2 抽象数据类型如何定义抽象数据类型可以用以下的三,26,1.4.3,抽象数据类型如何表示和实现,抽象数据类型可以通过,固有的,数据类型（如整型、实型、字符型等）来表示和实现。,注,1,：它有些类似,C,语言中的,结构（,struct),类型,，但增加了相关的,服务,。,注,2,：教材中用,类,C,语言（介于伪码和,C,语言之间）作为描述工具。其描述语法汇总在教材,P10-11,上。,1.4.3 抽象数据类型如何表示和实现 抽象数据类型可,27,提示：,教材中例,1-6,和例,1-7,分别给出了抽象数据类型“三元组”的定义、表示和实现，请自己先试读一遍。,当课程内容学习到,50%,以后，你再回头看这个例子，会发现自己已能完全看懂了！,Back,提示：Back,28,1.5,算法效率的度量,讨论：,1.5.1,什么是算法？如何评判算法的好坏？,1.5.2,时间复杂度和空间复杂度如何表示？,1.5.3,计算举例,1.5 算法效率的度量讨论：1.5.1 什么是算法？如,29,1.5.1,什么是算法？如何评判一个算法的好坏？,常用,时间复杂度,来衡量,算法的基本特性：,算法评价指标：,有穷性、确定性、可行性、,必有,输出,正确性、可读性、健壮性、,效率,与,低存储量,需求,常用,空间复杂度,来衡量,程序设计的实质：好算法好结构,算法,是对特定问题求解步骤的一种描述，它是指令的有限序列，是一系列输入转换为输出的计算步骤。,1.5.1 什么是算法？如何评判一个算法的好坏？常用时间复,30,注：,1,）,O,（）为渐近符号,。,2,）,空间复杂度,S(n),按数量级递增顺序也与上表类似。,复杂度高,复杂度低,时间复杂度,T(n),按数量级递增顺序为：,1.5.2,时间复杂度和空间复杂度如何表示？,多项,注：复杂度高复杂度低时间复杂度T(n)按数量级递增顺序为：,31,3n+2=,O,(n),因为,3n+2,4n,forn,2,6*2,n,+n,2,=,O,(2,n,),因为,6*2,n,+n,2,7*2,n,forn,4,例：,渐进符号,（,O,）的定义：当且仅当存在一个正的常数,C，使得对所有的,n,n,0，有,f(n),Cg(n)，则：f(n)=O(g(n),3n+2=O(n)因为3n+24n,32,算法的,时间复杂度,-,算法,(,或程序,),中基本操作,(,或语句,),重复执行的次数的总和。,设,n,为求解的,问题的规模,基本操作,(,或语句,),执行次数,总和称为,语句频度,记作,f(n),；,时间复杂度记作,T(n),有：,T(n)=O(f(n),例,1 int s,；,scanf(“%d”,&s)