数据结构数据结构精.ppt

《数据结构数据结构精.ppt》由会员分享，可在线阅读，更多相关《数据结构数据结构精.ppt（26页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数据结构数据结构第1页，本讲稿共26页2 2第2页，本讲稿共26页数据结构课程的地位数据结构课程的地位 它是计算机专业及相关专业的它是计算机专业及相关专业的核心课程核心课程之一，是计算机及相关专业的之一，是计算机及相关专业的重要骨干基础课重要骨干基础课程程。它针对非数值计算的程序设计问题，研它针对非数值计算的程序设计问题，研究计算机的操作对象以及它们之间的关系和究计算机的操作对象以及它们之间的关系和操作。即其研究目的是研究有效地组织和处操作。即其研究目的是研究有效地组织和处理非数值类型数据的理论、技术和方法。理非数值类型数据的理论、技术和方法。3 3第3页，本讲稿共26页数据结构的核心研究内容

2、数据结构的核心研究内容数数据据的的逻逻辑辑结结构构、存存储储结结构构及及它它们们之之间间的关系和相应的基本操作运算的定义和实现。的关系和相应的基本操作运算的定义和实现。本本书书围围绕绕数数据据结结构构的的三三种种基基本本结结构构：线线性性结结构构、树树形形结结构构和和图图形形结结构构展展开开讨讨论论，研研究究解解决决如如下下问问题题：一一个个具具体体问问题题的的逻逻辑辑数数据据结结构构是是什什么么？适适宜宜选选用用什什么么样样的的存存储储结结构构？采采用用什什么么样的操作实现算法效率更高？样的操作实现算法效率更高？4 4第4页，本讲稿共26页1 1 1 1、上课认真听讲，适当做好笔记，按时交作

3、业。、上课认真听讲，适当做好笔记，按时交作业。、上课认真听讲，适当做好笔记，按时交作业。、上课认真听讲，适当做好笔记，按时交作业。2 2 2 2、考试成绩分两部分：平时成绩（包括出勤和上机实验）占、考试成绩分两部分：平时成绩（包括出勤和上机实验）占、考试成绩分两部分：平时成绩（包括出勤和上机实验）占、考试成绩分两部分：平时成绩（包括出勤和上机实验）占40%40%40%40%，期末成绩占，期末成绩占，期末成绩占，期末成绩占60%60%60%60%。3 3 3 3、课后需要多读课文和参考书，上网查看相关内容，在理解基本内、课后需要多读课文和参考书，上网查看相关内容，在理解基本内、课后需要多读课文和

4、参考书，上网查看相关内容，在理解基本内、课后需要多读课文和参考书，上网查看相关内容，在理解基本内容的基础上，多看、多做习题。容的基础上，多看、多做习题。容的基础上，多看、多做习题。容的基础上，多看、多做习题。4 4 4 4、上机实验十分重要，一定要在上机前做好充分准备，多采用不同的、上机实验十分重要，一定要在上机前做好充分准备，多采用不同的、上机实验十分重要，一定要在上机前做好充分准备，多采用不同的、上机实验十分重要，一定要在上机前做好充分准备，多采用不同的数据存储结构和不同的实现算法解决一个问题。数据存储结构和不同的实现算法解决一个问题。数据存储结构和不同的实现算法解决一个问题。数据存储结构

5、和不同的实现算法解决一个问题。对学生的几点要求对学生的几点要求5 5第5页，本讲稿共26页第第1章绪论章绪论讨论讨论5个问题：个问题：1.1 数据结构数据结构的基本概念的基本概念1.2 学习数据结构的意义学习数据结构的意义 1.3 数据结构涵盖的主要内容数据结构涵盖的主要内容 1.4 算法效率的度量算法效率的度量6 6第6页，本讲稿共26页1.1 数据结构的基本概念数据结构的基本概念1 1、举例、举例 建立一个学生档案。学生表包括学号、姓名、性别、籍建立一个学生档案。学生表包括学号、姓名、性别、籍建立一个学生档案。学生表包括学号、姓名、性别、籍建立一个学生档案。学生表包括学号、姓名、性别、籍贯

6、。要求：查找贯。要求：查找贯。要求：查找贯。要求：查找“王红王红王红王红”是否存在。是否存在。是否存在。是否存在。解决的方法步骤：解决的方法步骤：解决的方法步骤：解决的方法步骤：1)1)1)1)如如如如何何何何记记记记录录录录所所所所有有有有学学学学生生生生记记记记录录录录（及及及及选选选选择择择择何何何何种种种种逻逻逻逻辑辑辑辑数数数数据据据据结结结结构构构构）？2)2)2)2)选择何种存储结构？选择何种存储结构？选择何种存储结构？选择何种存储结构？vv若把所有记录依次存储在一个数组中若把所有记录依次存储在一个数组中若把所有记录依次存储在一个数组中若把所有记录依次存储在一个数组中采用采用采用

7、采用顺序存储结构顺序存储结构顺序存储结构顺序存储结构vv若采用指针链表若采用指针链表若采用指针链表若采用指针链表采用链式存储结构采用链式存储结构采用链式存储结构采用链式存储结构7 7第7页，本讲稿共26页2 2、基本术语、基本术语(1)(1)(1)(1)数据：所有能被计算机识别、存储和处理的符号的集合（包括数数据：所有能被计算机识别、存储和处理的符号的集合（包括数数据：所有能被计算机识别、存储和处理的符号的集合（包括数数据：所有能被计算机识别、存储和处理的符号的集合（包括数字、字符、声音、图像等信息字、字符、声音、图像等信息字、字符、声音、图像等信息字、字符、声音、图像等信息 ）。）。）。）。

8、(2)(2)(2)(2)数数数数据据据据元元元元素素素素:是是是是数数数数据据据据的的的的基基基基本本本本单单单单位位位位，具具具具有有有有完完完完整整整整确确确确定定定定的的的的实实实实际际际际意意意意义义义义。在在在在计计计计算算算算机机机机程程程程序序序序中中中中通通通通常常常常作作作作为为为为一一一一个个个个整整整整体体体体进进进进行行行行考考考考虑虑虑虑和和和和处处处处理理理理。一一一一个个个个数数数数据据据据元元元元素素素素可可可可由由由由若若若若干干干干个个个个数数数数据项组成。据项组成。据项组成。据项组成。(3)(3)(3)(3)数据项数据项数据项数据项:构成数据元素的项目。它

9、是数据不可分割的最小单位。构成数据元素的项目。它是数据不可分割的最小单位。构成数据元素的项目。它是数据不可分割的最小单位。构成数据元素的项目。它是数据不可分割的最小单位。(4)(4)(4)(4)数数数数据据据据类类类类型型型型：指指指指一一一一个个个个类类类类型型型型和和和和定定定定义义义义在在在在这这这这个个个个类类类类型型型型上上上上的的的的操操操操作作作作集集集集合合合合。例例例例：C C C C语语语语言言言言（基基基基本本本本类类类类型型型型：整整整整型型型型、浮浮浮浮点点点点型型型型、字字字字符符符符型型型型等等等等构构构构造造造造类类类类型型型型：数数数数组组组组、结构、联合、指

10、针、枚举等）结构、联合、指针、枚举等）结构、联合、指针、枚举等）结构、联合、指针、枚举等）(5)(5)(5)(5)抽象数据元素：抽象定义的、没有实际含义的数据元素。抽象数据元素：抽象定义的、没有实际含义的数据元素。抽象数据元素：抽象定义的、没有实际含义的数据元素。抽象数据元素：抽象定义的、没有实际含义的数据元素。(6)(6)(6)(6)抽象数据类型：用户自己定义的数据类型。抽象数据类型：用户自己定义的数据类型。抽象数据类型：用户自己定义的数据类型。抽象数据类型：用户自己定义的数据类型。8 8第8页，本讲稿共26页2 2、基本术语、基本术语(续）续）(7)(7)(7)(7)数据结构数据结构数据结

11、构数据结构：是相互之间存在一种或多种特定关系的数据元素的：是相互之间存在一种或多种特定关系的数据元素的：是相互之间存在一种或多种特定关系的数据元素的：是相互之间存在一种或多种特定关系的数据元素的集合。或按照一定逻辑关系组织，并按一定存储方法存储的数集合。或按照一定逻辑关系组织，并按一定存储方法存储的数集合。或按照一定逻辑关系组织，并按一定存储方法存储的数集合。或按照一定逻辑关系组织，并按一定存储方法存储的数据的集合，且需要定义一系列运算。逻辑结构、存储结构和运据的集合，且需要定义一系列运算。逻辑结构、存储结构和运据的集合，且需要定义一系列运算。逻辑结构、存储结构和运据的集合，且需要定义一系列运

12、算。逻辑结构、存储结构和运算合称为三要素。表示为：算合称为三要素。表示为：算合称为三要素。表示为：算合称为三要素。表示为：Data_Structure=Data_Structure=Data_Structure=Data_Structure=（D,RD,RD,RD,R）其中，其中，其中，其中，D D D D元素有限集，元素有限集，元素有限集，元素有限集，R R R R关系有限集关系有限集关系有限集关系有限集 9 9第9页，本讲稿共26页程序设计好算法好结构程序设计好算法好结构同样的数据对象，用不同的数据结构来表示，同样的数据对象，用不同的数据结构来表示，运算效率可能有明显的差异。运算效率可能有

13、明显的差异。1.2学习数据结构的意义学习数据结构的意义计计算算机机内内的的数数值值运运算算依依靠靠方方程程式式，而而非非数数值值运运算算（如如表表、树树、图等）则要依靠数据结构。图等）则要依靠数据结构。数数据据结结构构是是一一门门学学科科，针针对对非非数数值值计计算算的的程程序序设设计计问问题题，研研究究计算机的操作对象以及它们之间的关系和操作等等。计算机的操作对象以及它们之间的关系和操作等等。1010第10页，本讲稿共26页1.3数据结构涵盖的内容数据结构涵盖的内容1111第11页，本讲稿共26页集合结构：集合结构：仅同属一个集合仅同属一个集合线性结构线性结构:一对一（一对一（1:1)树树结

14、结构构:一对多（一对多（1:n)图图结结构构:多对多多对多(m:n)非线性非线性线线性性逻辑结构可细分为逻辑结构可细分为4类：类：指数据元素之间的逻辑关系。即从逻辑关系上描述数据，它指数据元素之间的逻辑关系。即从逻辑关系上描述数据，它与数据的存储无关，是独立于计算机的。与数据的存储无关，是独立于计算机的。解释解释1：什么叫数据的逻辑结构？什么叫数据的逻辑结构？1212第12页，本讲稿共26页（1 1）S=(D,R)S=(D,R)D=D=a,b,c,d,e,f a,b,c,d,e,f R=(R=(a,e),(b,c),(c,a),(e,f),(f,d)a,e),(b,c),(c,a),(e,f)

15、,(f,d)解：解：上述表达式可用图形表示为：上述表达式可用图形表示为：bcaefd此结构为此结构为线性线性的。的。例：例：用图形表示下列数据结构，并指出它们是属于线性用图形表示下列数据结构，并指出它们是属于线性结构还是非线性结构。结构还是非线性结构。1313第13页，本讲稿共26页 d1 d5 d2 d4 d3该结构该结构是非线性是非线性的。的。解：解：上述表达式可用图形表示为：上述表达式可用图形表示为：（2）S=(D,R)D=di|1i5 R=(di,dj),ij1414第14页，本讲稿共26页物物物物理理理理结结结结构构构构亦亦亦亦称称称称存存存存储储储储结结结结构构构构，是是是是数数数

16、数据据据据的的的的逻逻逻逻辑辑辑辑结结结结构构构构在在在在计计计计算算算算机机机机存存存存储储储储器器器器内内内内的的的的表示（或映像）。它依赖于计算机。表示（或映像）。它依赖于计算机。表示（或映像）。它依赖于计算机。表示（或映像）。它依赖于计算机。存储结构可分为存储结构可分为4大类：大类：例：例：复数复数3.02.3i的两种存储方式：的两种存储方式：顺序、链式、索引、散列顺序、链式、索引、散列2.303023.00300041503023.0030004152.3法法1：地址地址内容内容法法2：地址地址内容内容2字节字节解释解释2：什么叫数据的物理结构？：什么叫数据的物理结构？1515第15

17、页，本讲稿共26页在数据的逻辑结构上定义的操作算法。在数据的逻辑结构上定义的操作算法。在数据的逻辑结构上定义的操作算法。在数据的逻辑结构上定义的操作算法。它它它它在数据的存储结构上实现在数据的存储结构上实现在数据的存储结构上实现在数据的存储结构上实现。最常用的数据运算有最常用的数据运算有5种：种：插入、删除、修改、查找、排序插入、删除、修改、查找、排序解释解释3：什么是数据的运算？：什么是数据的运算？1616第16页，本讲稿共26页1.4 算法效率的度量算法效率的度量1 1 什么是算法？如何评判算法的好坏？什么是算法？如何评判算法的好坏？什么是算法？如何评判算法的好坏？什么是算法？如何评判算法

18、的好坏？2 2 时间复杂度和空间复杂度如何表示？时间复杂度和空间复杂度如何表示？时间复杂度和空间复杂度如何表示？时间复杂度和空间复杂度如何表示？3 3 计算举例计算举例计算举例计算举例讨论：讨论：1717第17页，本讲稿共26页1 什么是算法？如何评判一个算法的好坏？什么是算法？如何评判一个算法的好坏？常用常用时间复杂度时间复杂度来衡量来衡量算法的基本特性：算法的基本特性：算法评价指标：算法评价指标：有穷性、确定性、可行性、必有输出有穷性、确定性、可行性、必有输出正确性、可读性、健壮性、高效率与低存储量需求正确性、可读性、健壮性、高效率与低存储量需求常用常用空间复杂度空间复杂度来衡量来衡量好的

19、程序设计：好算法好结构好的程序设计：好算法好结构算法：算法：是对特定问题求解步骤的一种描述，它是指令的有限是对特定问题求解步骤的一种描述，它是指令的有限序列，是一系列输入转换为输出的计算步骤。序列，是一系列输入转换为输出的计算步骤。1818第18页，本讲稿共26页注：注：1）O（）为渐近符号。（）为渐近符号。2）空间复杂度空间复杂度S(n)按数量级递增顺序也与上表类似。按数量级递增顺序也与上表类似。复杂度高复杂度高复杂度低复杂度低时间复杂度时间复杂度T(n)按数量级递增顺序为：按数量级递增顺序为：2 时间复杂度和空间复杂度如何表示？时间复杂度和空间复杂度如何表示？多项式阶多项式阶1919第19

20、页，本讲稿共26页3n+2=O(n)(n)因为因为因为因为 3n+2 4n for n 26*26*2n n+n2=O(2n n)因为因为因为因为6*26*2n+n+n2 7*2n n for n for n 4 4例：例：渐进符号渐进符号（O）的定义：）的定义：当且仅当存在一个正的常数当且仅当存在一个正的常数 C C，使得对所有的，使得对所有的 n n n n0 0 ，有，有 f(n)f(n)Cg(n)Cg(n)，则：，则：f(n)=f(n)=O(g(n)(g(n)2020第20页，本讲稿共26页该算法的运行时间由程序中所有语句的频度（即该语句重该算法的运行时间由程序中所有语句的频度（即该语

21、句重复执行的次数）之和构成。复执行的次数）之和构成。解：解：分析：显然，语句分析：显然，语句的频度是的频度是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)3 计算举例计算举例2121第21页，本讲稿共26页该算法的运行时间由程序中所

22、有语句的该算法的运行时间由程序中所有语句的频度频度（即该语句重复执（即该语句重复执行的次数）行的次数）之和之和构成。构成。解：解：例：例：分析以下程序段的时间复杂度。分析以下程序段的时间复杂度。i=1;k=0;while(in)k=k+10*i;i+;k=k+10*i;i+;即即f(n)log2n，取最大值取最大值f(n)=log2n所以该程序段的时间复杂度所以该程序段的时间复杂度T(n)=1+f(n)=1+log2n=O(log2n)3 计算举例计算举例2222第22页，本讲稿共26页T(n)=1+1+n+(n-1)+(n-1)=3nT(n)=1+1+n+(n-1)+(n-1)=3n可表示为

23、可表示为T(n)=O(n)3 分析分析 i=1;/1k=0;/1 while(in)/n k=k+10*i;/n-1i+;/n-12323第23页，本讲稿共26页本章小结本章小结数据结构课程数据结构课程 数据结构算法程序，涉及数学、数据结构算法程序，涉及数学、计算机硬件和软件。计算机硬件和软件。数据结构定义数据结构定义数据结构定义数据结构定义指互相有关联的数据元素的集合，可用指互相有关联的数据元素的集合，可用data_Structure=(D,R)data_Structure=(D,R)表示。表示。表示。表示。数据结构内容数据结构内容数据的逻辑结构、存储结构和基本运数据的逻辑结构、存储结构和基本运算算 。数据结构描述工具数据结构描述工具数据结构描述工具数据结构描述工具抽象数据类型和抽象数据类型和抽象数据类型和抽象数据类型和C C语言。语言。语言。语言。算法效率算法效率时间效率和空间效率时间效率和空间效率时间效率和空间效率时间效率和空间效率 。2424第24页，本讲稿共26页习习 题题 P7 1.1 1.2 1.3 1.4 1.5P7 1.1 1.2 1.3 1.4 1.52525第25页，本讲稿共26页CLASS IS OVER2626第26页，本讲稿共26页