《数据结构概论》PPT课件.ppt

数数 据据 结结 构构蒋洪波蒋洪波华中科技大学电信系华中科技大学电信系()http:/12数据结构课程的地位数据结构课程的地位针对针对非数值计算非数值计算的程序设计问题，研究计算机的的程序设计问题，研究计算机的操作对象操作对象以及它们之间的以及它们之间的关系关系和和操作操作。是介于是介于数学、计算机硬件和计算机软件数学、计算机硬件和计算机软件三者之三者之间的一门核心课程。间的一门核心课程。关系对象关系操作数学软件硬件对象关系操作Data_Structure=（D,R）3学时数：学时数：56（4412）教教 材：材：严蔚敏严蔚敏等等，数据结构（，数据结构（C语言版），清华大学出版社，语言版），清华大学出版社，1997年年4月第月第1版版（配题集配题集）参考书：参考书：1 高一凡，高一凡，数据结构算法实现及解析（第二版），西电数据结构算法实现及解析（第二版），西电出版社，出版社，2004年年10月月2 李春葆，李春葆，数据结构（数据结构（C语言篇）语言篇）-习题与解析（修订版），习题与解析（修订版），清华大学出版社，清华大学出版社，2002年年4月月2 殷人昆等，殷人昆等，数据结构（用面向对象方法与数据结构（用面向对象方法与C+描述），清描述），清华大学出版社，华大学出版社，1999年年7月（月（2002年配题集年配题集）4内内 容容 安安 排排章章内内 容容 学时学时 章章 内内 容容 学时学时 1绪绪 论论27图图62线性表线性表68动态存储管理动态存储管理略略3栈和队列栈和队列49查找查找44串串410内部排序内部排序65数组和广义表数组和广义表 411外部排序外部排序略略6树和二叉树树和二叉树 812文件文件略略第第1-12周，周二周，周二9-10节节第第1-12周，周四周，周四1-2节节5目目 录录第第1章章 绪论绪论第第2章章 线性表线性表第第3章章 栈和队列栈和队列 第第4章章 串串第第5章章 数组和广义表数组和广义表第第6 6章章 树和二叉树树和二叉树 第第7章章 图图第第9章章 查找查找第第10章章 排序排序6第第1章绪论章绪论讨论讨论5个问题：个问题：1.1 什么是数据结构什么是数据结构1.2 学习数据结构的意义学习数据结构的意义 1.3 数据结构涵盖的主要内容数据结构涵盖的主要内容 1.4 什么是抽象数据类型什么是抽象数据类型1.5 算法效率的度量算法效率的度量71.1 什么是数据结构什么是数据结构是是相相互互之之间间存存在在一一种种或或多多种种特特定定关关系系的的数数据据元元素素的的集合，表示为：集合，表示为：（数值或非数值数值或非数值）Data_Structure=（D,R）是指是指同一数据元素类型同一数据元素类型中各元素之间存在的关系中各元素之间存在的关系元素有限集元素有限集关系有限集关系有限集8数数据据(data)所所有有能能被被计计算算机机识识别别、存存储储和和处处理理的的符符号号的的集集合合（包括数字、字符、声音、图像等信息包括数字、字符、声音、图像等信息）。）。数数据据元元素素(data element)是是数数据据的的基基本本单单位位，具具有有完完整整确确定的实际意义定的实际意义(又称元素、结点，顶点、记录等又称元素、结点，顶点、记录等）。）。数数据据项项(Data item)构构成成数数据据元元素素的的项项目目。是是具具有有独独立立含含义义的的最小最小标识单位（标识单位（又称字段、域、属性又称字段、域、属性 等等）。）。三者之间的关系：三者之间的关系：数据数据 数据元素数据元素 数据项数据项例：例：班级通讯录班级通讯录 个人记录个人记录 姓名、年龄姓名、年龄数据、数据元素和数据项数据、数据元素和数据项术语简介：术语简介：91.2 学习数据结构的意义学习数据结构的意义计计算算机机内内的的数数值值运运算算依依靠靠方方程程式式，而而非非数数值值运运算算（如（如表、树、图表、树、图等）则要依靠数据结构。等）则要依靠数据结构。数数据据结结构构是是一一门门学学科科，针针对对非非数数值值计计算算的的程程序序设设计计问问题题，研研究究计计算算机机的的操操作作对对象象以以及及它它们们之之间间的的关关系系和操作和操作等等。等等。程序设计好算法好结构程序设计好算法好结构同样的数据对象，用不同的数据结构来表同样的数据对象，用不同的数据结构来表示，运算效率可能有明显的差异。示，运算效率可能有明显的差异。101.3 数据结构涵盖的内容数据结构涵盖的内容11集合结构：集合结构：仅同属一个集合仅同属一个集合线性结构线性结构:一对一（一对一（1:1)树树 结结 构构:一对多（一对多（1:n)图图 结结 构构:多对多多对多 (m:n)非线性非线性线线 性性逻辑结构可细分为逻辑结构可细分为4类：类：答：指数据元素之间的逻辑关系。即从逻辑关系上描述答：指数据元素之间的逻辑关系。即从逻辑关系上描述数据，它数据，它与数据的存储无关与数据的存储无关，是，是独立于计算机独立于计算机的。的。解释解释1：什么叫数据的逻辑结构？什么叫数据的逻辑结构？12（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此结构为此结构为线性线性的。的。例：例：用图形表示下列数据结构，并指出它们是属于线用图形表示下列数据结构，并指出它们是属于线性结构还是非线性结构。性结构还是非线性结构。13 d1 d5 d2 d4 d3该结构是该结构是非线性非线性的。的。解：解：上述表达式可用图形表示为：上述表达式可用图形表示为：（2）S=(D,R)D=di|1i5 R=(di,dj),ij14答答：物物理理结结构构亦亦称称存存储储结结构构，是是数数据据的的逻逻辑辑结结构构在在计计算机存储器内的表示（或映像）。它算机存储器内的表示（或映像）。它依赖于计算机依赖于计算机。存储结构可分为存储结构可分为4大类：大类：例：例：复数复数2.3i 的两种存储方式：的两种存储方式：顺序、链式、索引、散列顺序、链式、索引、散列2.303023.00300041503023.0030004152.3法法1：地址地址 内容内容法法2：地址地址 内容内容2字节字节解释解释2：什么叫数据的物理结构？：什么叫数据的物理结构？15答：在数据的逻辑结构上定义的操作算法。答：在数据的逻辑结构上定义的操作算法。它它在数据的存储结构上实现在数据的存储结构上实现。最常用的数据运算有最常用的数据运算有 5 种：种：插入、删除、修改、查找、排序插入、删除、修改、查找、排序解释解释3：什么是数据的运算？：什么是数据的运算？161.4 什么是抽象数据类型什么是抽象数据类型1.4.1 数据类型与抽象数据类型的区别？数据类型与抽象数据类型的区别？1.4.2 抽象数据类型如何定义？抽象数据类型如何定义？1.4.3 抽象数据类型如何表示和实现？抽象数据类型如何表示和实现？讨论：讨论：抽象数据类型抽象数据类型和和伪码伪码是学习数据结构的工具是学习数据结构的工具17ADT=Abstract Data Type 1.4.1 数据类型与抽象数据类型的区别数据类型与抽象数据类型的区别数据类型：数据类型：是一个是一个值的集合值的集合和定义在该值上的和定义在该值上的一组操作一组操作的总称。的总称。抽象数据类型：抽象数据类型：由由用户定义用户定义的的一个数学模型与定义在一个数学模型与定义在该模型上的一组操作，该模型上的一组操作，它由基本的数据类型构成。它由基本的数据类型构成。ADTADT与数据类型实质上是一个概念，但其特征是与数据类型实质上是一个概念，但其特征是使用使用与与实现分离实现分离，实行，实行封装封装和和信息隐蔽信息隐蔽（独立于计算机）（独立于计算机）“抽象抽象”的意义在于数据类型的数学抽象特性的意义在于数据类型的数学抽象特性181.4.2 抽象数据类型如何定义抽象数据类型如何定义抽象数据类型抽象数据类型可以用以下的三元组来表示：可以用以下的三元组来表示：ADT=ADT=（D D，R R，P P）ADTADT抽象数据类型名抽象数据类型名 数据数据对象对象：数据数据关系关系：基本基本操作操作 ：ADT ADT抽象数据类型抽象数据类型名名ADT常用常用定义定义格式格式数据对象数据对象D D上的关系集上的关系集D D上的操作集上的操作集19例例1：给出自然数给出自然数(Natural Number)的的抽象数据类型抽象数据类型定义。定义。ADT Natural_Number objects:一个整数的有序子集合，它开始于0，结束于机器能表示的最大整数(MAX INT)functions:对于所有的 x,y Natural_Number；TRUE,FALSE Boolean；+,-,=,=等都是可用的服务。Zero()Zero()：Natural Number Natural Number 返回返回 0 0IsZero(x)IsZero(x)：Boolean if(x=0)Boolean if(x=0)返回返回TRUETRUE else else 返回返回 FALSEFALSEAdd(x,y)Add(x,y)：Natural Number Natural Number if(x+y=MAX INT)if(x+y=MAX INT)返回返回 x+yx+y else else 返回返回 MAX INTMAX INTSubtract(x,y):Natural NumberNatural Number if(xy)返回返回0 else 返回返回x-yEqual(x,y):Boolean Equal(x,y):Boolean if(x=y)if(x=y)返回返回TRUE else TRUE else 返回返回FALSEFALSESuccessor(x):Natural NumberNatural Number if(x=MAX INT)返回返回x else 返回返回x+1 Natural_Number“抽象抽象”的意义在于数据类型的数学抽象特的意义在于数据类型的数学抽象特性性201.4.3 抽象数据类型如何表示和实现抽象数据类型如何表示和实现 抽象数据类型可以通过抽象数据类型可以通过固有的固有的数据类型（如整型、数据类型（如整型、实型、字符型等）来表示和实现。实型、字符型等）来表示和实现。注注1 1 ：它有些类似：它有些类似C C语言中的语言中的结构（结构（struct)struct)类型类型，但，但增加了相关的增加了相关的服务服务(或操作或操作)。注注2 2 ：教材中用：教材中用类类C C语言（介于伪码和语言（介于伪码和C C语言之间）作语言之间）作为描述工具。其描述语法汇总在教材为描述工具。其描述语法汇总在教材P10-11P10-11上。上。但上机时要用具体语言实现，如但上机时要用具体语言实现，如C C或或C+C+等等21提示：提示：教材中教材中例例1-61-6和例和例1-71-7分别给出了抽象数据类型分别给出了抽象数据类型“三元组三元组”的定义、表示和实现，请自己先试的定义、表示和实现，请自己先试读一遍。读一遍。当课程学到当课程学到50%50%以后，你再回头看这个例子，会以后，你再回头看这个例子，会发现自己已能完全看懂了！发现自己已能完全看懂了！例例2：给出给出抽象数据类型抽象数据类型三元组（三元组（Triplet）的定义。）的定义。22例例2：给出给出抽象数据类型抽象数据类型三元组（三元组（Triplet）的定义。）的定义。ADT Triplet 数据数据对象对象：D=e1,e2,e3|e1,e2,e3 ElemSet,（定义了关系运（定义了关系运算的某个集合）算的某个集合）数据数据关系关系：R1=,基本基本操作操作：InitTriplet(&T,v1,v2,v3)/建三元组，给建三元组，给e1,e2,e3赋初值赋初值DestroyTriplet(&T)/销毁三元组销毁三元组Get(T,i,&e)/读取第读取第i元的值输出给元的值输出给ePut(T,i,e)/修改第修改第i元的值元的值=eIsAscending(T)/三元素单调增则返回三元素单调增则返回1,否则返回否则返回0IsDscending(T)/三元素单调减，则返回三元素单调减，则返回1,否则返回否则返回0Max(T,&e)/求三元素中的最大值并输出给求三元素中的最大值并输出给eMin(T,&e)/求三元素中的最小值并输出给求三元素中的最小值并输出给e ADT Triplet“抽象抽象”的意义在于数据类型的数学抽象特的意义在于数据类型的数学抽象特性性231.5 算法效率的度量算法效率的度量1.5.1 什么是算法？如何评判算法的好坏？什么是算法？如何评判算法的好坏？1.5.2 时间复杂度和空间复杂度如何表示？时间复杂度和空间复杂度如何表示？1.5.3 计算举例计算举例讨论：讨论：241.5.1 什么是算法？如何评判一个算法的好坏？什么是算法？如何评判一个算法的好坏？常用常用时间复杂度时间复杂度来衡量来衡量算法的基本特性：算法的基本特性：算法评价指标：算法评价指标：有穷性、确定性、可行性、有穷性、确定性、可行性、必有必有输出输出正确性、可读性、健壮性、正确性、可读性、健壮性、效率效率与与低存储量低存储量需求需求常用常用空间复杂度空间复杂度来衡量来衡量程序设计的实质：好算法好结构程序设计的实质：好算法好结构算法算法是对特定问题求解步骤的一种描述，它是指令的是对特定问题求解步骤的一种描述，它是指令的有限序列，是一系列输入转换为输出的计算步骤。有限序列，是一系列输入转换为输出的计算步骤。25注：注：1）O（）为渐近符号（）为渐近符号。2）空间复杂度空间复杂度S(n)按数量级递增顺序也与上表类似。按数量级递增顺序也与上表类似。复杂度高复杂度高复杂度低复杂度低时间复杂度时间复杂度T(n)按数量级递增顺序为：按数量级递增顺序为：1.5.2 时间复杂度和空间复杂度如何表示？时间复杂度和空间复杂度如何表示？多项式阶多项式阶263n+2=O(n)因为因为 3n+2 4n for n 26*2n+n2=O(2n)因为因为6*2n+n2 7*2n for n 4例：例：渐进符号渐进符号（O）的定义：）的定义：当且仅当存在一个正的常数当且仅当存在一个正的常数 C C，使得对所有的，使得对所有的 n n n n0 0 ，有，有 f(n)f(n)Cg(n)Cg(n)，则：，则：f(n)=f(n)=O O(g(n)(g(n)271.5.3 计算举例计算举例该算法的运行时间由程序中所有语句的该算法的运行时间由程序中所有语句的频度频度（即该语（即该语句重复执行的次数）句重复执行的次数）之和之和构成。构成。解：解：分析：分析：显然，语句显然，语句的频度是的频度是1。设语句。设语句2的频度是的频度是f(n)，则有：，则有：算法的时间复杂度由算法的时间复杂度由嵌套最深层语句的频度嵌套最深层语句的频度决定决定例：例：分析以下程序段的时间复杂度。分析以下程序段的时间复杂度。i=1;while(i=n)i=i*2;即即f(n)log2n，取最大值取最大值f(n)=log2n所以该程序段的时间复杂度所以该程序段的时间复杂度T(n)=1+f(n)=1+log2n=O(log2n)28本章小结本章小结数据结构课程数据结构课程 数据结构算法程序，涉及数学、数据结构算法程序，涉及数学、计算机硬件和软件。计算机硬件和软件。数据结构定义数据结构定义指互相有关联的数据元素的集合，指互相有关联的数据元素的集合，可用可用data_Structure=(D,R)data_Structure=(D,R)表示。表示。数据结构内容数据结构内容数据的逻辑结构、存储结构和基本数据的逻辑结构、存储结构和基本运算运算(计算机处理非数值对象计算机处理非数值对象)数据结构学习工具数据结构学习工具抽象数据类型和伪码（类抽象数据类型和伪码（类C）算法效率指标算法效率指标时间效率和空间效率时间效率和空间效率 第第1章结束章结束29作业：作业：见见http:/:8001/classroom/配套习题集的配套习题集的 题。题。复习复习C语言，重点是语言，重点是结构类型结构类型和和递归递归概念。概念。30