大学数据结构ppt课件(清华版)

数据结构DataStructure长春大学软件工程系２０11．2学分：3教材：严蔚敏等，数据结构（C语言版），清华大学出版社，2011年参考书：[1]殷人昆等，数据结构（用面向对象方法与C++描述），清华大学出版社，1999年7月。￥26[2]殷人昆等，数据结构习题解析，清华大学出版社，2002年4月。[3]李春葆，数据结构习题与解析（C语言篇），清华大学出版社，2001年1月。[4]严蔚敏等，数据结构题集(C语言版)，清华大学出版社，1997年4月。内容安排章内容学时章内容学时1序论27图102线性表88动态存储管理略3栈和队列89查找104串010内部排序105数组和广义表411外部排序略6树和二叉树1212文件略注：本学期共64时。第1章序论1.1什么是数据结构1.2基本概念和术语1.3抽象数据类型的表示和实现1.4算法和算法分析作业5§1.1什么是数据结构Q1如何采用计算机解决问题？Q2数据结构解决什么样的问题？Q3《数据结构》课程介绍6Q1：如何采用计算机解决问题？答：寻求数学模型的实质：分析问题，从中提取操作的对象，并找出这些操作对象之间含有的关系，然后用数学的语言加以描述。(2)设计解此数学模型的算法；(1)从具体问题抽象出一个适当的数学模型；(3)编程，测试、调整直至得到最终解答。7Q2：数据结构解决什么样的问题？答：数据结构研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等的学科。8介于数学、计算机硬件和计算机软件三者之间的一门核心课程关系对象关系操作数学软件硬件对象关系操作Q3：《数据结构》课程介绍§1.2基本概念和术语Q1什么是数据结构？Q2学习数据结构有什么用？Q3数据结构涵盖的主要内容？讨论：Q1：什么是数据结构？答:(见教材P5)是相互之间存在一种或多种特定关系的数据元素的集合，表示为：（数值或非数值）Data_Structure=（D,S）或：是指同一数据元素类中各元素之间存在的关系。亦可表示为：S＝（D,R）或B=（K,R）元素有限集关系有限集术语：数据、数据元素和数据项数据(data)——所有能被计算机识别、存储和处理的符号的集合（包括数字、字符、声音、图像等信息）。数据元素(dataelement)——是数据的基本单位，具有完整确定的实际意义(又称元素、结点，顶点、记录等）。数据项(Dataitem)——构成数据元素的项目。是具有独立含义的最小标识单位（又称字段、域、属性等）。三者之间的关系：数据数据元素数据项例：班级通讯录个人记录姓名、年龄……Q2：学习数据结构有什么用？答：计算机内的数值运算依靠方程式，而非数值运算（如表、树、图等）则要依靠数据结构。这是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等等的学科。程序设计实质＝好算法＋好结构同样的数据对象，用不同的数据结构来表示，运算效率可能有明显的差异。Q3：数据结构涵盖的内容？解释1：什么叫数据的逻辑结构？答：指数据元素之间的逻辑关系。即从逻辑关系上描述数据，它与数据的存储无关，是独立于计算机的。逻辑结构可细分为4类：集合结构：仅同属一个集合线性结构:一对一（1:1)树结构:一对多（1:n)图结构:多对多(m:n)非线性线性例：用图形表示下列数据结构，并指出它们是属于线性结构还是非线性结构。（1）S=(D,R)D={a,b,c,d,e,f}R={(a,e),(b,c),(c,a),(e,f),(f,d)}解：上述表达式可用图形表示为：bcaefd此结构为线性的。（2）S=(D,R)D={di|1≤i≤5}R={(di,dj),ij}d1d5d2d4d3该结构是非线性的。解：上述表达式可用图形表示为：解释2：什么叫数据的物理结构？答：物理结构亦称存储结构，是数据的逻辑结构在计算机存储器内的表示（或映像）。它依赖于计算机。存储结构可分为4大类：例：（见教材P6）复数3.0－2.3i的两种存储方式：顺序、链式、索引、散列－2.303023.00300041503023.003000415－2.3法1：地址内容法2：地址内容2字节解释3：什么是数据的运算？答：在数据的逻辑结构上定义的操作算法。它在数据的存储结构上实现。最常用的数据运算有5种：插入、删除、修改、查找、排序§1.3抽象数据类型的表示和实现Q1数据类型与抽象数据类型的区别？Q2抽象数据类型如何定义？Q3抽象数据类型如何表示和实现？讨论：提示：教材中例1-6和例1-7分别给出了抽象数据类型“三元组”的定义、表示和实现，请试阅读。Q1数据类型与抽象数据类型的区别？数据类型：是一个值的集合和定义在该值上的一组操作的总称。抽象数据类型：由用户定义，用以表示应用问题的数据模型。它由基本的数据类型构成，并包括一组相关的服务（或称操作）它与数据类型实质上是一个概念，但其特征是使用与实现分离，实行封装和信息隐蔽（独立于计算机）。Q2抽象数据类型如何定义？抽象数据类型可以用以下的三元组来表示：ADT=（D，S，P）数据对象D上的关系集D上的操作集ADT抽象数据类型名{数据对象：数据对象的定义数据关系：数据关系的定义基本操作：基本操作的定义}ADT抽象数据类型名ADT常用定义格式例：给出自然数(NaturalNumber)的抽象数据类型定义。ADTNatural_Numberisobjects:一个整数的有序子集合，它开始于0，结束于机器能表示的最大整数(MAXINT)functions:对于所有的x,yNatural_Number；TRUE,FALSEBoolean；+,-,,==,=等都是可用的服务。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_NumberQ3抽象数据类型如何表示和实现？抽象数据类型可以通过固有的数据类型（如整型、实型、字符型等）来表示和实现。即利用处理器中已存在的数据类型来说明新的结构，用已经实现的操作来组合新的操作。注：教材中用的是类C语言（介于伪码和C语言之间）作为描述工具。其描述语法见P10-11。但上机时要用具体语言实现，如C或C++等§1.4算法和算法分析Q1.什么是算法？Q2.算法设计的要求？Q3.时间复杂度如何表示？Q4.空间复杂度如何表示？讨论：答：算法是解决某一特定类型问题的有限运算序列。是一系列输入转换为输出的计算步骤。Q1.什么是算法？算法有5个基本特性：有穷性、确定性、可行性、输入和输出26Q2.算法设计的要求？答：(1)正确性(2)可读性(3)健壮性(4)效率与低存储需求时间复杂度T(n)按数量级递增顺序为：注1O（）为渐近符号。注2空间复杂度S(n)按数量级递增顺序也与上表类同。复杂度高复杂度低Q3.时间复杂度如何表示？渐进符号（O）的定义：当且仅当存在一个正的常数C，使得对所有的nn0，有f(n)Cg(n)，则f(n)=O(g(n))3n+2=O(n)/*3n+24nforn2*/3n+3=O(n)/*3n+34nforn3*/100n+6=O(n)/*100n+6101nforn10*/10n2+4n+2=O(n2)/*10n2+4n+211n2forn5*/6*2n+n2=O(2n)/*6*2n+n27*2nforn4*/例：例：分析以下程序段的时间复杂度。i=1;①while(i=n)i=i*2;②该算法的运行时间由算法中所有语句的频度（即该语句重复执行的次数）之和构成。解：分析：显然，语句①的频度是1。设语句2的频度是f(n)，则有：nnf)(2即f(n)≤log2n，取最大值f(n)=log2n所以该程序段的时间复杂度T(n)=1+f(n)=1+log2n=O(log2n)算法的时间复杂度是由嵌套最深层语句的频度决定的。30Q4.空间复杂度如何表示？S(n)=O(f(n))一个上机执行的程序除了需要存储空间来寄存本身所用指令、常数、变量和输入数据外，也需要一些对数据进行操作的工作单元和存储一些为实现计算所需信息的辅助空间。原地工作：若额外空间相对于输入数据量来说是常数，则称此算法为原地工作。注：若额外空间所占空间量依赖于特定的输入，则除特别指明外，均按最坏情况来分析。作业：1.思考:数据结构、数据类型、抽象数据类型的区别算法与程序的区别2.请试做配套习题集(P10_16)。3.复习C++语言。32上堂课要点回顾数据结构课程——涉及数学、计算机硬件和计算机软件数据结构定义——指互相有关联的数据元素的集合，用D_S=(D,S)或S=(D,R)表示。数据结构内容——数据的逻辑结构、存储结构和运算算法效率指标——时间效率和空间效率33数据结构课程的内容逻辑结构唯一存储结构不唯一运算的实现依赖于存储结构34近3周上课内容第2章线性表第3章栈和队列第4章串第5章数组和广义表线性结构若结构是非空有限集，则有且仅有一个开始结点和一个终端结点，并且所有结点都最多只有一个直接前趋和一个直接后继。可表示为：（a1,a2,……,an）线性结构的定义：（逻辑、存储和运算）35线性结构的特点：①只有一个首结点和尾结点；②除首尾结点外，其他结点只有一个直接前驱和一个直接后继。线性结构表达式：（a1,a2,……,an）线性结构包括线性表、堆栈、队列、字符串、数组等等，其中，最典型、最常用的是------线性表简言之，线性结构反映结点间的逻辑关系是一对一的见第2章36第2章线性表2.1线性表的逻辑结构2.2线性表的顺序表示和实现2.3线性表的链式表示和实现2.4应用举例（一元多项式的表示及相加）作业37（a1,a2,…ai-1，ai,ai＋1，…,an）2.1线性表的类型定义一.线性表的定义：用数据元素的有限序列表示n=0时称为数据元素线性起点ai的直接前趋ai的直接后继下标，是元素的序号，表示元素在表中的位置n为元素总个数，即表长空表线性终点38例1分析26个英文字母组成的英文表（A,B,C,D,……,Z）学号姓名性别年龄班级2001011810205于春梅女182001级电信016班2001011810260何仕鹏男182001级电信017班2001011810284王爽女182001级通信011班2001011810360王亚武男182001级通信012班：：：：：例2分析学生情况登记表数据元素都是记录;元素间关系是线性数据元素都是字母;元素间关系是线性同一线性表中的元素必定具有相同特性39练：判断下列叙述的正误：1.数据的逻辑结构是指数据元素之间的逻辑关系，是用户按使用需要建立的。2.线性表的逻辑结构定义是唯一的，不依赖于计算机。3.线性结构反映结点间的逻辑关系是一对一的。4.一维向量是线性表，但二维或N维数组不是。5.“同一数据逻辑结构中的所有数据元素都具有相同的特性”是指数据元素所包含的数据项的个数都相等。×√√√×40二.线性表的类型定义（详见课本P19）对线性表的有关操作举例请大家看课本P20例2-1，例2-2412.2线性表的顺序表示和实现2.2.1顺序表的表示2.2.2顺序表的实现2.2.3顺序表的运算效率分析本节小结作业422.2.1顺序表的表示用一组地址连续的存储单元依次存储线性表的元素，可通过数组V[n]来实现。把逻辑上相邻的数据元素存储在物理上相邻的存储单元中的存储结构。线性表的顺序表示又称为顺序存储结构或顺序映像。顺序存储定义：顺序存储方法：简言之，逻辑上相邻，物理上也相邻1.顺序表示432.线性表顺序存储特点：1）逻辑上相邻的数据元素，