数据结构课程介绍

数据结构DataStructure,教材：严蔚敏等，数据结构（C语言版），清华大学出版社参考书：1殷人昆等，数据结构（用面向对象方法与C+描述），清华大学出版社，1999年7月。2殷人昆等，数据结构习题解析，清华大学出版社，2002年4月。3李春葆，数据结构习题与解析（C语言篇），清华大学出版社，2001年1月。4严蔚敏等，数据结构题集(C语言版)，清华大学出版社，1997年4月。,内容安排,注：本学期共64学时。,考核方式,闭卷考试，卷面70%+平时30%；平时成绩包含：实验（20分）、作业+考勤（10分）；平时成绩采用倒扣分方式：（1）缺一次实验扣3（2）缺一次作业扣1分；（3）缺勤（含请假）一次扣2分，缺6次（含实验）取消考试资格；加分项：每章的总结，交1次+2分；平时成绩最多30分！,第1章序论,1.1什么是数据结构1.2基本概念和术语1.3抽象数据类型的表示和实现1.4算法和算法分析,作业,1.1什么是数据结构,Q1如何采用计算机解决问题？Q2数据结构解决什么样的问题？Q3数据结构课程介绍,Q1：如何采用计算机解决问题？,答：编写解决实际问题的程序的一般过程：,(2)问题所涉及的数据量大小及数据间的关系；,如何用数据形式描述问题？从具体问题抽象出一个适当的数学模型；,(3)如何在计算机中存储数据和体现数据间的关系？,(4)处理问题时需要对数据做何种运算？,(5)所编写的程序的性能是否良好？,这些问题基本上是由数据结构这门课程来回答。,8,寻求数学模型的实质：分析问题，从中提取操作的对象，并找出这些操作对象之间含有的关系，然后用数学的语言加以描述。,Q2：数据结构解决什么样的问题？,答：,9,数据结构研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等的学科。,图书检索系统、电话号码查询系统人机对弈、家谱交通灯管理系统,10,11,12,13,深蓝是美国IBM公司生产的一台超级国际象棋电脑。“深蓝”和卡斯帕罗夫曾于1996年交过手，结果卡斯帕罗夫以4：2战胜了“深蓝”。“更深的蓝”是美国IBM公司生产的一台超级国际象棋电脑，重1270公斤，有32个大脑(微处理器)，每秒钟可以计算2亿步。“更深的蓝”输入了一百多年来优秀棋手的对局两百多万局。1997年5月11日，加里卡斯帕罗夫以2.5:3.5输给“更深的蓝”,14,15,16,Q3：数据结构课程介绍,介于数学、计算机硬件和计算机软件三者之间的一门核心课程，不仅是一般程序设计的基础，也是设计和实现编译程序、操作系统、数据库系统及其他系统软件和大型应用软件的重要基础。,关系,对象关系操作,对象关系操作,1.2基本概念和术语,Q1什么是数据结构？Q2学习数据结构有什么用？Q3数据结构涵盖的主要内容？,讨论：,数据(Data)：是客观事物的符号表示。在计算机科学中指的是所有能输入到计算机中并被计算机程序处理的符号总称。数据元素（DataElement）：是数据的基本单位，在程序中通常作为一个整体来进行考虑和处理。一个数据元素可由若干个数据项(DataItem)组成。数据项是数据的不可分割的最新单位。数据项是对客观事物某一方面特性的数据描述。数据对象（DataObject）：是性质相同的数据元素的集合，是数据的一个子集。如字符集合Char=A,B,C,数据包括数字、字符、声音、图像等信息。数据元素又称元素、结点，顶点、记录等。数据项又称字段、域、属性等。,三者之间的关系：数据数据元素数据项,例：班级通讯录个人记录姓名、年龄,Q1：什么是数据结构？,答:(见教材P5)是相互之间存在一种或多种特定关系的数据元素的集合，表示为：,（数值或非数值）,Data_Structure=（D,S）,或：是指同一数据元素类中各元素之间存在的关系。,亦可表示为：S（D,R）或B=（K,R）,元素有限集,关系有限集,Q2：学习数据结构有什么用？,答：计算机内的数值运算依靠方程式，而非数值运算（如表、树、图等）则要依靠数据结构。这是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等等的学科。,程序设计实质好算法好结构,同样的数据对象，用不同的数据结构来表示，运算效率可能有明显的差异。,解释1：什么叫数据的逻辑结构？,答：指数据元素之间的逻辑关系。即从逻辑关系上描述数据，它与数据的存储无关，是独立于计算机的。数据元素之间的关系可以是元素之间代表某种含义的自然关系，也可以是为处理问题方便而人为定义的关系，这种自然或人为定义的“关系”称为数据元素之间的逻辑关系。,解释1：什么叫数据的逻辑结构？,逻辑结构可细分为4类：,集合结构：仅同属一个集合线性结构:一对一（1:1)树结构:一对多（1:n)图结构:多对多(m:n),非线性,线性,例：用图形表示下列数据结构，并指出它们是属于线性结构还是非线性结构。,（1）S=(D,R)D=a,b,c,d,e,fR=(a,e),(b,c),(c,a),(e,f),(f,d),解：上述表达式可用图形表示为：,bcaefd,此结构为线性的。,（2）S=(D,R)D=di|1i5R=(di,dj),ij,d1d5d2d4d3,该结构是非线性的。,解：上述表达式可用图形表示为：,解释2：什么叫数据的物理结构？,答：物理结构亦称存储结构，是数据的逻辑结构在计算机存储器内的表示（或映像）。它依赖于计算机。数据结构在计算机内存中的存储包括数据元素的存储和元素之间的关系的表示。,解释2：什么叫数据的物理结构？,存储结构可分为4大类：顺序、链式、索引、散列顺序存储结构：用数据元素在存储器中的相对位置来表示数据元素之间的逻辑结构（关系）。链式存储结构：在每一个数据元素中增加一个存储另一个元素地址的指针，用该指针来表示数据元素之间的逻辑结构（关系）。,例：设有数据集合A=3，4，0，8顺序结构：数据元素存放的地址是连续的；链式结构：数据元素存放的地址是否连续不做要求。,例：（见教材P6）复数3.02.3i的两种存储方式：,法1：地址内容,法2：地址内容,2字节,数据的逻辑结构和物理结构是密不可分的两个方面，一个算法的设计取决于所选定的逻辑结构，而算法的实现依赖于所采用的存储结构。,解释3：什么是数据的运算？,答：在数据的逻辑结构上定义的操作算法。它在数据的存储结构上实现。,最常用的数据运算有5种：,插入、删除、修改、查找、排序,Q3：数据结构涵盖的内容？,1.3抽象数据类型的表示和实现,Q1数据类型与抽象数据类型的区别？Q2抽象数据类型如何定义？Q3抽象数据类型如何表示和实现？,讨论：,提示：教材中例1-6和例1-7分别给出了抽象数据类型“三元组”的定义、表示和实现，请试阅读。,Q1数据类型与抽象数据类型的区别？,数据类型：是一个值的集合和定义在该值上的一组操作的总称。,数据结构不同于数据类型，也不同于数据对象，它不仅要描述数据类型的数据对象，而且要描述数据对象各元素之间的相互关系。,Q1数据类型与抽象数据类型的区别？,抽象数据类型：由用户定义，用以表示应用问题的数据模型。它由基本的数据类型构成，并包括一组相关的服务（或称操作）。,它与数据类型实质上是一个概念，但其特征是使用与实现分离，实行封装和信息隐蔽（独立于计算机）。,抽象数据类型的定义仅是一组逻辑特性描述，与其在计算机内的表示和实现无关。因此，不论ADT的内部结构如何变化，只要其数学特性不变，都不影响其外部使用。,Q2抽象数据类型如何定义？,抽象数据类型可以用以下的三元组来表示：ADT=（D，S，P）数据对象D上的关系集D上的操作集,ADT抽象数据类型名数据对象：数据关系：基本操作：ADT抽象数据类型名,ADT常用定义格式,例：给出自然数(NaturalNumber)的抽象数据类型定义。,ADTNatural_Numberisobjects:一个整数的有序子集合，它开始于0，结束于机器能表示的最大整数(MAXINT)functions:对于所有的x,yNatural_Number；TRUE,FALSEBoolean；+,-,=,=等都是可用的服务。Zero()：NaturalNumber返回0IsZero(x)：Booleanif(x=0)返回TRUEelse返回FALSEAdd(x,y)：NaturalNumberif(x+y=MAXINT)返回x+yelse返回MAXINTSubtract(x,y):NaturalNumberif(xy)返回0else返回x-yEqual(x,y):Booleanif(x=y)返回TRUEelse返回FALSESuccessor(x):NaturalNumberif(x=MAXINT)返回xelse返回x+1endNatural_Number,Q3抽象数据类型如何表示和实现？,抽象数据类型可以通过固有的数据类型（如整型、实型、字符型等）来表示和实现。即利用处理器中已存在的数据类型来说明新的结构，用已经实现的操作来组合新的操作。,注：教材中用的是类C语言（介于伪码和C语言之间）作为描述工具。其描述语法见P10-11。,但上机时要用具体语言实现，如C或C+等,1.4算法和算法分析,Q1.什么是算法？Q2.算法设计的要求？Q3.时间复杂度如何表示？Q4.空间复杂度如何表示？,讨论：,答：算法是对特定问题求解方法(步骤)的一种描述，是指令的有限序列，其中每一条指令表示一个或多个操作。一个算法可以用多种方法描述，主要有：使用自然语言描述；使用形式语言描述；使用计算机程序设计语言描述。算法和程序是两个不同的概念。一个计算机程序是对一个算法使用某种程序设计语言的具体实现。算法必须可终止意味着不是所有的计算机程序都是算法。,Q1.什么是算法？,Q1.什么是算法？,算法有5个基本特性：,有穷性确定性可行性输入输出,一个好的算法有以下几个标