数据结构最全课件

《数据结构最全课件》由会员分享，可在线阅读，更多相关《数据结构最全课件（46页珍藏版）》请在金锄头文库上搜索。

1、数据结构与算法数据结构与算法Data Structures Data Structures 讲课学时：讲课学时：4242上机学时：上机学时：2020教学安排教学安排邮箱邮箱::教师教师: :黄俊恒黄俊恒11.1 什么是数据结构什么是数据结构 例例1.11.1、煤气管道的铺设问题。在城市的各小、煤气管道的铺设问题。在城市的各小区之间铺设煤气管道，共有区之间铺设煤气管道，共有4 4个小区，由于地理环个小区，由于地理环境不同等因素使各条管线所需投资不同，如何使境不同等因素使各条管线所需投资不同，如何使投资成本最低？投资成本最低？abdc181819152025abdc181815abdc181520

2、2数据结构数据结构: :数据结构是一门研究非数值计算的程数据结构是一门研究非数值计算的程序设计问题中计算机的序设计问题中计算机的操作对象操作对象以及它们以及它们之间的之间的关系和操作关系和操作等的学科。（等的学科。（P3P3）数据结构的三个层次：数据结构的三个层次：1 1、逻辑结构（问题的数学模型）、逻辑结构（问题的数学模型）2 2、存储结构、存储结构3 3、建立在二者之上的基本运算、建立在二者之上的基本运算1.1 什么是数据结构什么是数据结构3程序设计程序设计 = = 数据结构数据结构 + + 算法算法程序设计：为计算机处理问题编制的一组指令集程序设计：为计算机处理问题编制的一组指令集算法：

3、处理问题的策略算法：处理问题的策略*1.1 什么是数据结构什么是数据结构4教材情况教材情况1.1.数据结构数据结构严蔚敏等严蔚敏等 清华大学出版社清华大学出版社2.2.数据结构与算法数据结构与算法 廖明宏廖明宏 郭福顺等郭福顺等 高等教育出版社高等教育出版社前序课程前序课程后序课程后序课程5考试考核考试考核1.1.出勤与作业出勤与作业 每缺少一次扣每缺少一次扣3 3分分, ,满三次扣满三次扣1010分分, ,满四满四次取消考试资格。次取消考试资格。2.2.实验实验 占总成绩占总成绩30%30%3.3.期末闭卷考试期末闭卷考试 占总成绩占总成绩70%70%*6第一章第一章 绪论绪论1.1 1.1

4、 什么是数据结构什么是数据结构1.2 1.2 基本概念和术语基本概念和术语1.3 1.3 抽象数据类型的表示和实现抽象数据类型的表示和实现1.4 1.4 算法和算法分析算法和算法分析71.1.数据数据 数据是用于数据是用于描述客观事物描述客观事物的符号表示，在计的符号表示，在计算机科学中指一切可以输入到计算机中的并由计算机科学中指一切可以输入到计算机中的并由计算机程序算机程序处理处理的符号的集合。的符号的集合。1.2 1.2 基本概念和术语基本概念和术语2.2.数据元素数据元素 数据的基本单位是数据元素，数据的基本单位是数据元素， 通常作为一个通常作为一个整体进行考虑和处理。一般由若干整体进行

5、考虑和处理。一般由若干数据项数据项组成。组成。 数据元素有时又称为数据元素有时又称为结点结点、记录或表目。、记录或表目。83.3.数据项数据项 是数据的不可分割的最小单位，是数据的不可分割的最小单位， 一个数据元素一个数据元素可由若干个数据项组成。是对数据元素可由若干个数据项组成。是对数据元素属性的描述。属性的描述。 有时称有时称域或字段域或字段。 姓名姓名性别性别年龄年龄专业专业班级班级 数数 据据 项项 例如：学生例如：学生( ( 数据元素数据元素) )1.2 1.2 基本概念和术语基本概念和术语94. 4. 数据对象数据对象 性质相同的元素的集合叫做数据对象，性质相同的元素的集合叫做数据

6、对象，是数据的子集。是数据的子集。1.2 1.2 基本概念和术语基本概念和术语5 5、数据结构、数据结构: : 数据结构指的是数据元素之间的抽数据结构指的是数据元素之间的抽象的相互关系，是数据元素及其相互间象的相互关系，是数据元素及其相互间的关系的数学描述。的关系的数学描述。数据结构的三个层次：数据结构的三个层次： (1)(1)、逻辑结构（问题的数学模型）、逻辑结构（问题的数学模型） (2)(2)、存储结构、存储结构 (3)(3)、建立在二者之上的基本运算、建立在二者之上的基本运算101. 1. 集合集合ABCD数据结构的四种基本结构数据结构的四种基本结构2. 2. 线性结构线性结构ABCD例

7、例1-1 1-1 图书检图书检索（索（P1P1）3. 3. 树型结构树型结构ABCD例例1-2 1-2 人机对弈人机对弈（P1P1）4. 4. 图状结构图状结构ABCD例例1-3 1-3 交通灯管理交通灯管理（P2P2）11数据结构的形式定义：数据结构的形式定义：Data Structure=(D,S)Data Structure=(D,S)其中其中D D是数据无素的集合，是数据无素的集合，S S是是D D上关系的上关系的集合。集合。1.2 1.2 基本概念和术语基本概念和术语12数据结构数据结构: :数据结构指的是数据元素之间数据结构指的是数据元素之间的抽象的相互关系，是数据元素及其相的抽象

8、的相互关系，是数据元素及其相互间的关系的数学描述。互间的关系的数学描述。数据结构的三个层次：数据结构的三个层次：1 1、逻辑结构（问题的数学模型）、逻辑结构（问题的数学模型）2 2、存储结构、存储结构3 3、建立在二者之上的基本运算、建立在二者之上的基本运算1.2 1.2 基本概念和术语基本概念和术语132、存储结构（物理结构）、存储结构（物理结构）数据结构包括结点的值及结点之间的关系。数据结构包括结点的值及结点之间的关系。(1).(1).顺序存储结构；顺序存储结构；(2).(2).链接存储结构；链接存储结构；(3).(3).索引存储结构；索引存储结构；(4).(4).散列存储结构。散列存储结

9、构。1.2 1.2 基本概念和术语基本概念和术语146.6.数据类型数据类型 是一个值的集合和定义在这个值的集合上是一个值的集合和定义在这个值的集合上的一组的一组操作的总称操作的总称。分为原子数据类型和结构数据类型。分为原子数据类型和结构数据类型。1.2 1.2 基本概念和术语基本概念和术语15抽象数据类型抽象数据类型Abstract Data Abstract Data Types(ADTTypes(ADT) ) ADTADT数据型是程序设计语言中数据类数据型是程序设计语言中数据类型概念的推广和抽象。型概念的推广和抽象。 例如：对一个线性表例如：对一个线性表L L，我们可以声明它的，我们可以

10、声明它的类型，数据元素的类型，定义它的有关操作：类型，数据元素的类型，定义它的有关操作：intint=(=(x xx xZ Z,+,-,*,/,%,+,-,*,/,%, ,=),=) 表类型表类型LISTLIST，位置，位置position,FIRST(),ENDposition,FIRST(),END(),(),NEXT(),SAME(),DELETE(),RETRIEVE(). NEXT(),SAME(),DELETE(),RETRIEVE(). 16 例例1.2 1.2 编一个函数编一个函数PURGEPURGE，删除线性表，删除线性表L L中所中所有重复出现的元素。有重复出现的元素。 表

11、类型表类型LISTLIST，位置，位置position,FIRST(),ENDposition,FIRST(),END(),(),NEXT(),SAME(),DELETE(),RETRIEVE(). NEXT(),SAME(),DELETE(),RETRIEVE(). 抽象数据类型抽象数据类型Abstract Data Abstract Data Types(ADTTypes(ADT) )17void PURGE(LIST L)void PURGE(LIST L)position position p,qp,q; ; p=FIRST(L); p=FIRST(L); while(pwhile(p

12、!=END(L)!=END(L) q= q=NEXT(p,LNEXT(p,L);); while(qwhile(q!=END(L)!=END(L) if ( if (same(RETRIEVE(p,L),RETRIEVE(q,Lsame(RETRIEVE(p,L),RETRIEVE(q,L) DELETE(q,LDELETE(q,L);); else else q= q=NEXT(q,LNEXT(q,L);); p= p=NEXT(p,LNEXT(p,L););抽象数据类型抽象数据类型Abstract Data Abstract Data Types(ADTTypes(ADT) )181 1、

13、抽象数据型的定义、抽象数据型的定义 定义定义 ：抽象数据类型是指一个数学抽象数据类型是指一个数学模型和定义在该模型上的一组操作。模型和定义在该模型上的一组操作。 ADTADT特点：特点：使用者只要知道这些操作使用者只要知道这些操作的用途就可以编程序了；至于这些操作是的用途就可以编程序了；至于这些操作是怎样实现的，以及内存中是如何表示的，怎样实现的，以及内存中是如何表示的，并不影响使用者所编程序的编码形式。并不影响使用者所编程序的编码形式。192 2、抽象数据类型的形式定义、抽象数据类型的形式定义 抽象数据类型的形式定义可用三元组抽象数据类型的形式定义可用三元组表示：表示： （D,S,PD,S,

14、P） D D是数据对象，是数据对象，S S是是D D上的关系集，上的关系集，P P是是对对D D的基本操作集。的基本操作集。 数据结构与抽象数据型的关系？数据结构与抽象数据型的关系？ 数据结构是抽象数据型中的数学模型，数据结构是抽象数据型中的数学模型，抽象数据型是数据结构加上一组操作。抽象数据型是数据结构加上一组操作。202 2、抽象数据类型的形式定义、抽象数据类型的形式定义 该书对抽象数据型的抽述方式该书对抽象数据型的抽述方式 ADT ADT 抽象数据类型名抽象数据类型名 数据对象：数据对象： 数据关系：数据关系： 基本操作：基本操作： ADTADT抽象数据类型名抽象数据类型名21(1) (

15、1) 预定义常量和类型预定义常量和类型 #define TRUE 1#define TRUE 1 #define FALSE 0 #define FALSE 0 #define Ok 1 #define Ok 1 #define ERROR 0 #define ERROR 0 #define INFEASIBLE -1 #define INFEASIBLE -1 #define OVERFLOW -2 #define OVERFLOW -2 typedeftypedef intint Status; Status;1.3 1.3 抽象数据类型的表示与实现抽象数据类型的表示与实现22(2) (2

16、) 数据结构的表示（存储结构）用类数据结构的表示（存储结构）用类型定义（型定义（typedeftypedef）描述，数据元素类）描述，数据元素类型约定为型约定为ElemTypeElemType, ,由用户使用该数据由用户使用该数据类型时自行定义。类型时自行定义。1.3 1.3 抽象数据类型的表示与实现抽象数据类型的表示与实现23(3) (3) 基本操作的算法都用以下形式的函数基本操作的算法都用以下形式的函数描述：描述： 函数类型函数类型 函数名（参数表）函数名（参数表） /算法说明算法说明 语句序列语句序列 /函数名函数名1.3 1.3 抽象数据类型的表示与实现抽象数据类型的表示与实现241.

17、3 1.3 抽象数据类型的表示与实现抽象数据类型的表示与实现(4) (4) 赋值语句有：赋值语句有： 简单赋值简单赋值 变量名变量名= =表达式；表达式； 串联赋值串联赋值 变量变量1=1=变量变量2=2=变量变量k=k=表达式；表达式； 成组赋值成组赋值 ( (变量名变量名1,1,变量名变量名k)=(k)=(表达式表达式1 1，,表达式表达式k k）; ; 结构名结构名= =结构名；结构名； 结构名结构名= =（值（值1 1，,值值k k）; ; 变量名变量名= =表达式；表达式； 变量名变量名 起始下标起始下标.终止下标终止下标=变量名变量名 起始下标起始下标.终止下标终止下标 交换赋值交

18、换赋值 变量名变量名变量名变量名 条件赋值条件赋值 变量名变量名= =条件表达式？表达式条件表达式？表达式T T：表达式：表达式F;F;251.3 1.3 抽象数据类型的表示与实现抽象数据类型的表示与实现(5) (5) 选择语句有：选择语句有： ifelseifelse switch switch(6) (6) 循环语句有：循环语句有： forfor while while do while do while261.3 1.3 抽象数据类型的表示与实现抽象数据类型的表示与实现(7) (7) 结束语句有：结束语句有： returnreturn break break exit exit(8) (

19、8) 输入输出输入输出 scanfscanf printfprintf271.3 1.3 抽象数据类型的表示与实现抽象数据类型的表示与实现(9) (9) 基本函数有基本函数有 max(max(表达式表达式1,1,表达式表达式n)n) min( min(表达式表达式1,1,表达式表达式n)n) abs( abs(表达式表达式) ) floor floor(表达式表达式) ceil( ceil(表达式表达式) ) eofeof( (表达式表达式) ) eolneoln( (表达式表达式) )281.3 1.3 抽象数据类型的表示与实现抽象数据类型的表示与实现(10) (10) 逻辑运算逻辑运算*

20、抽象数据型的表示和实现包括数据抽象数据型的表示和实现包括数据模型的表示和在其上定义的各种操作的模型的表示和在其上定义的各种操作的实现。实现。291.4 算法和算法分析算法和算法分析1.4.1 算法算法算法（算法（Algorithm）：是对特定问题求解步骤的）：是对特定问题求解步骤的一种描述，它是指令（规则）的有限序列，其中一种描述，它是指令（规则）的有限序列，其中每一条指令表示一个或多个操作。每一条指令表示一个或多个操作。算法的特征：算法的特征：输入、输入、输出、输出、确定性、确定性、有穷性、有穷性、可行性。可行性。算法与程序的区别？算法与程序的区别？程序不一定满足有穷性。程序不一定满足有穷性

21、。301.4.2、算法设计的要求、算法设计的要求 1、正确性、正确性(Correctness) 2、可读性、可读性(readability) 3、健壮性、健壮性(robustness) 4、效率与低存储量的要求。、效率与低存储量的要求。 （时间复杂性与空间复杂性）（时间复杂性与空间复杂性） 1.4 算法和算法分析算法和算法分析31 算法的时间复杂性算法的时间复杂性 (Time Complexity) （1）事后统计的方法）事后统计的方法 （2）事前分析估算的方法）事前分析估算的方法 一个用高级程序语言编写的程序在计算机上一个用高级程序语言编写的程序在计算机上运行时所消耗的时间取决于下列因素。运

22、行时所消耗的时间取决于下列因素。 依据算法选用的何种策略依据算法选用的何种策略; 问题的规模问题的规模 所用语言所用语言 编译程序产生的机器代码的质量编译程序产生的机器代码的质量 机器执行指令的速度机器执行指令的速度1.4.3 算法效率的度量算法效率的度量32 1、算法的时间复杂性算法的时间复杂性 (Time Complexity) 把算法的基本操作的重复执行的次数作为算把算法的基本操作的重复执行的次数作为算法的时间度量。法的时间度量。1.4.3 算法效率的度量算法效率的度量33 2.空间复杂性空间复杂性(Space Complexity) 算法的空间复杂性是指算法在执行过程中的算法的空间复杂

23、性是指算法在执行过程中的存储量需求存储量需求； 一个算法的存储量需求除了一个算法的存储量需求除了存放算法本身所存放算法本身所有的指令、常数、变量和输入数据外，有的指令、常数、变量和输入数据外，还包括对还包括对数据进行操作的工作单元和存储实现计算所需信数据进行操作的工作单元和存储实现计算所需信息的辅助空间息的辅助空间； 一般指辅助空间所占的存储空间。一般指辅助空间所占的存储空间。1.4 算法及其性能评价准则算法及其性能评价准则34 例例1.3 1.3 两个两个n nn n的矩阵相乘。其中矩阵的的矩阵相乘。其中矩阵的“阶阶”n n为问题的规模。为问题的规模。 void void MATRIXMLT

24、(intMATRIXMLT(int AnAn, intint Bn,intBn,int CnCn) intint i,j,ki,j,k; ; for (i=0; in; i+) (1)for (i=0; in; i+) (1)for (j=0; jn; j+) (2)for (j=0; jn; j+) (2) CijCij=0; (3)=0; (3) for (k=0;kfor (k=0;kn;kn;k+) (4)+) (4) CijCij+=+=AikAik*BkjBkj; (5); (5) 1.4 算法时间复杂性分析方法算法时间复杂性分析方法35 T(nT(n)=2n)=2n3 3+3n+

25、3n2 2+2n+1+2n+1 当当n n趋于无穷大时，趋于无穷大时，T(nT(n) )与与n n3 3 是是同阶的，我们称为同阶的，我们称为T(nT(n) )与与n n3 3 的数量级的数量级相同，可记作：相同，可记作：T(nT(n)=O(n)=O(n3 3 ) )。1.4 算法时间复杂性分析方法算法时间复杂性分析方法36 渐近时间复杂度表示法渐近时间复杂度表示法 (1) (1) O( )( )表示法：表示法： 若若T(nT(n) )和和f(nf(n) )是定义在正整数集合上的是定义在正整数集合上的两个函数，当存在两个正常数两个函数，当存在两个正常数c c和和n n0 0时，使时，使得对所有

26、的得对所有的nnnn0 0, ,都有都有T(n)cf(nT(n)cf(n) )成立，成立，则则T(nT(n)=)=O(f(nO(f(n) 渐近紧密上限渐近紧密上限 1.4 算法时间复杂性分析方法算法时间复杂性分析方法37 (2) (2) ( )( )表示法：表示法： 若若T(nT(n) )和和f(nf(n) )是定义在正整数集合上的是定义在正整数集合上的两个函数，当存在两个正常数两个函数，当存在两个正常数c c和和n n0 0时，使时，使得对所有的得对所有的nnnn0 0, ,都有都有T(nT(n) )cf(ncf(n) )成立，成立，则则T(nT(n)=)= ( (f(nf(n) 渐近紧密下

27、限渐近紧密下限 1.4 算法时间复杂性分析方法算法时间复杂性分析方法38 (3) (3) ( )( )表示法：表示法： 若若T(nT(n) )和和f(nf(n) )是定义在正整数集合上的两是定义在正整数集合上的两个函数，当存在正常数个函数，当存在正常数c c、d d和和n n0 0时，使得对时，使得对所有的所有的nnnn0 0, ,都有都有cf(n)T(n)cf(n)T(n)df(ndf(n) )成成立，则立，则T(nT(n)=)= ( (f(nf(n) 渐近紧密限度渐近紧密限度 1.4 算法时间复杂性分析方法算法时间复杂性分析方法39常数阶常数阶对数阶对数阶线性阶线性阶线性对数阶线性对数阶平

28、方阶平方阶立方阶立方阶K次方阶次方阶指数阶指数阶指数时间的关系为：指数时间的关系为：指数时间的关系为：指数时间的关系为： O(2O(2n n)O(nO(n!)!)O(nO(nn n) )1.4 算法时间复杂性分析方法算法时间复杂性分析方法40最坏时间复杂度最坏时间复杂度平均时间复杂度平均时间复杂度序号姓名电话号码1张一.2.3李一.4张三.5.6.n王五.查找成功的平均时间复杂度为查找成功的平均时间复杂度为O(nO(n););查找不成功的时间复杂度为查找不成功的时间复杂度为O(nO(n) )。1.4 算法时间复杂性分析方法算法时间复杂性分析方法最好时间复杂度最好时间复杂度41 例例1.4 1.

29、4 下面程序段的时间复杂度是：下面程序段的时间复杂度是： i=s=0;i=s=0; while (sn) while (s=n1+2+m=nm(m+1)/2=nm(m+1)/2=n42例例1.5 s=0; for(i=0;in;i+) for(j=i;jn;j+) s+=bij;例例 题题解：最内层语句共运行了：解：最内层语句共运行了：n+(n-1)+1=n(n+1)/243 例例1.6 下面程序段的时间复杂度为：下面程序段的时间复杂度为： i=1; while (i=n) i=i*3; 解：设循环了解：设循环了m次次 3m=n例例 题题44本本 课课 程程 内内 容容 结结 构构数数据据结结

30、构构线线性性结结构构非非线线性性结结构构第第2章章 线性表线性表第第3章章 栈和队列栈和队列第第4章章 串串第第5章章 数组和广义表数组和广义表第第6章章 树和二叉树树和二叉树第第7章章 图图第第8章章 动态存储管理动态存储管理第第9章章 查找查找第第10章章 内部排序内部排序第第11章章 外部排序外部排序第第12章章 文件文件*45总总 结结1 1 什么是数据结构什么是数据结构? ? 数据结构有哪几个层次数据结构有哪几个层次? ? 数据结构的分类数据结构的分类? ? 2 2 什么是抽象数据类型什么是抽象数据类型? ? 抽象数据型的实现是什么意思抽象数据型的实现是什么意思? ?3 3 如何求算法的时间复杂性如何求算法的时间复杂性? ?46