《数据结构与数据库学习教案.pptx》由会员分享，可在线阅读，更多相关《数据结构与数据库学习教案.pptx（41页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、数据结构数据结构(sh j ji u)与数据库与数据库第一页，共41页。教材教材(jioci)数据结构（数据结构（c语言版），语言版），严蔚敏等编著严蔚敏等编著,清华大学出清华大学出版社，版社，1997数据结构题集（数据结构题集（c语言版）语言版），严蔚敏等编著，严蔚敏等编著,清华大清华大学出版社，学出版社，1999第1页/共41页第二页，共41页。参考书参考书数据结构数据结构(sh j ji u)(第第二版二版)，唐策善、黄刘生，唐策善、黄刘生 编编著，中国科大出版社，著，中国科大出版社，2001 Data Structures with C+,Williaw Ford et al.,Pre
2、ntice Hall Inc.,1996.Data Structures&Program Design in C,2nd Ed.,Robert Kruse et al.,Prentice Hall Inc.,1997.第2页/共41页第三页，共41页。vv什么是数据结构什么是数据结构什么是数据结构什么是数据结构vv基本概念和术语基本概念和术语基本概念和术语基本概念和术语vv抽象数据类型抽象数据类型抽象数据类型抽象数据类型vv算法算法算法算法(sun f)(sun f)(sun f)(sun f)分析分析分析分析vv性能分析与度量性能分析与度量性能分析与度量性能分析与度量第一章 绪论(xln)第
3、3页/共41页第四页，共41页。学生(xu sheng)成绩表格第4页/共41页第五页，共41页。选课单学号学号课程号课程号时间时间成绩成绩20001DS2000SX20002001,22000,9788720002ART2000DS20002002,22001,2689020003SX2000DS20002000,92001,2877820004SX2000ART20002000,92002,28976第5页/共41页第六页，共41页。UNIXUNIX文件系统结构图文件系统结构图文件系统结构图文件系统结构图/rootbinlibuseretcmathdsswyintaoxieStack.cp
4、pQueue.cppTree.cpp第6页/共41页第七页，共41页。综上，描述这类非数值计算问综上，描述这类非数值计算问题的数学模型不是数学方程题的数学模型不是数学方程,而是树、表和图之类的数据结而是树、表和图之类的数据结构构(sh j ji u)。因此从广义上讲，数据结构因此从广义上讲，数据结构(sh j ji u)描述现实世描述现实世界实体的数学模型及其上的操界实体的数学模型及其上的操作在计算机中的表示和实现作在计算机中的表示和实现.第7页/共41页第八页，共41页。信息(xnx)？数据？知识？第8页/共41页第九页，共41页。基本概念和术语基本概念和术语(shy)(shy)数据数据数据
5、数据(Data)(Data)是信息是信息是信息是信息(xnx)(xnx)的载体，是描述客观事物的载体，是描述客观事物的载体，是描述客观事物的载体，是描述客观事物的数、字符、以及所有能输入到计算的数、字符、以及所有能输入到计算的数、字符、以及所有能输入到计算的数、字符、以及所有能输入到计算机中，被计算机程序识别和处理的符机中，被计算机程序识别和处理的符机中，被计算机程序识别和处理的符机中，被计算机程序识别和处理的符号的集合。号的集合。号的集合。号的集合。数值性数据数值性数据数值性数据数值性数据非数值性数据非数值性数据非数值性数据非数值性数据第9页/共41页第十页，共41页。数据元素（数据元素（D
6、ata ElementData Element）数据的基本单位。在计算机程序数据的基本单位。在计算机程序中常作为一个中常作为一个(y)(y)整体进整体进行考虑和处理。行考虑和处理。有时一个有时一个(y)(y)数据元素可以由数据元素可以由若干数据项若干数据项(Data Item)(Data Item)组成。组成。数据项是数据的不可分割的最数据项是数据的不可分割的最小单位。小单位。数据元素又称为元素、结点、记数据元素又称为元素、结点、记录录第10页/共41页第十一页，共41页。数据项数据项(Data Item)学学号号姓姓名名出生日期出生日期年年 月月 日日 籍籍贯贯年年级级系系别别宿宿舍舍号号第
7、11页/共41页第十二页，共41页。数据对象数据对象(Data Object)具有相同性质的数据元素的集合。具有相同性质的数据元素的集合。整数数据对象整数数据对象 N=0,1,2,字母字母(zm)字符数据对象字符数据对象C=A,B,C,F 第12页/共41页第十三页，共41页。数据结构（数据结构（Data Structure）形式定义：形式定义：某一数据对象的所有数据成员之某一数据对象的所有数据成员之间的关系。记为：间的关系。记为：Data_Structure=D,S 其中，其中，D 是某一数据对象，是某一数据对象，S 是是该对象中所有数据成员之间的关系该对象中所有数据成员之间的关系的有限的有
8、限(yuxin)集合。集合。第13页/共41页第十四页，共41页。序偶:一般来说，两个具有固定次序的客体组成一个序偶，常常表示两个客体之间的关系。记作。其中的x和y分别称为第一元素和第二元素。如：“中国地处亚洲”表示为序偶具有确定(qudng)的次序。=,iffx=u,y=v第一元素本身也可是一序偶。这样，序偶的概念可推广到n元组。如:三元组可定义为一序偶,z第14页/共41页第十五页，共41页。关系：任一序偶的集合确定了一个(y)二元关系R，R中任一序偶可记做 xRy。例如，在实数中关系 可记作 =|x,y是实数且xy 数据结构的一个(y)例子（例1.5)Group=(P,R)第15页/共4
9、1页第十六页，共41页。四类基本结构四类基本结构(jigu)集合集合线性结构线性结构(jigu)树形结构树形结构(jigu)网状结构网状结构(jigu)第16页/共41页第十七页，共41页。数据的逻辑结构数据的逻辑结构从逻辑关系上描述数据，与数据的从逻辑关系上描述数据，与数据的存储无关；存储无关；从具体问题抽象出来从具体问题抽象出来(ch li)的数的数据模型；据模型；与数据元素本身的形式、内容无关；与数据元素本身的形式、内容无关；与数据元素的相对位置无关。与数据元素的相对位置无关。第17页/共41页第十八页，共41页。数据的逻辑数据的逻辑(lu j)结构分类结构分类线性结构线性结构 线性表线
10、性表非线性结构非线性结构 树树 图（或网络）图（或网络）第18页/共41页第十九页，共41页。bindevetclibuser2114131211234678910315871011998745662313155线性结构线性结构(jigu)树形结构树形结构(jigu)树树 二叉树二叉树 二叉排序树二叉排序树第19页/共41页第二十页，共41页。堆结构堆结构(jigu)123548711102916125643125436113318146651921图结构图结构(jigu)(jigu)网络结构网络结构(jigu)(jigu)第20页/共41页第二十一页，共41页。数据的存储结构数据的存储结构数
11、据的存储结构数据的存储结构数据结构在计算机中的表示（又称映象）数据结构在计算机中的表示（又称映象）数据结构在计算机中的表示（又称映象）数据结构在计算机中的表示（又称映象）。包括包括包括包括(boku)(boku)数据元素的表示和关系的数据元素的表示和关系的数据元素的表示和关系的数据元素的表示和关系的 表示。表示。表示。表示。数据元素的表示数据元素的表示数据元素的表示数据元素的表示:位串（元素、结点）位串（元素、结点）位串（元素、结点）位串（元素、结点）关系的表示关系的表示关系的表示关系的表示 顺序映象顺序映象顺序映象顺序映象 非顺序映象非顺序映象非顺序映象非顺序映象第21页/共41页第二十二页
12、，共41页。抽象数据类型（抽象数据类型（Abstract Data Type）n n数据类型数据类型数据类型数据类型 定义：一个值的集合定义：一个值的集合定义：一个值的集合定义：一个值的集合(jh)(jh)和定义在这个值集上的一组操和定义在这个值集上的一组操和定义在这个值集上的一组操和定义在这个值集上的一组操作的总称。作的总称。作的总称。作的总称。n nC C语言中的基本数据类型语言中的基本数据类型语言中的基本数据类型语言中的基本数据类型n n int char float double void int char float double voidn n 整型整型整型整型 字符型字符型字符型
13、字符型 浮点型浮点型浮点型浮点型 双精度型双精度型双精度型双精度型 无值无值无值无值第22页/共41页第二十三页，共41页。抽象数据类型抽象数据类型抽象数据类型抽象数据类型是是是是指指指指一一一一个个个个数数数数学学学学模模模模型型型型以以以以及及及及定定定定义义义义在在在在此此此此数数数数学学学学模模模模型上的一组操作型上的一组操作型上的一组操作型上的一组操作数数数数据据据据结结结结构构构构+定定定定义义义义在在在在此此此此数数数数据据据据结结结结构构构构上上上上的的的的一一一一组组组组操作操作操作操作=抽象数据类型抽象数据类型抽象数据类型抽象数据类型 例例例例如如如如(lr)(lr)：矩矩
14、矩矩阵阵阵阵 +（求求求求转转转转置置置置、加加加加、乘、乘、乘、乘、求求求求逆逆逆逆、求求求求特特特特征征征征值）值）值）值）构成一个矩阵的抽象数据类型构成一个矩阵的抽象数据类型构成一个矩阵的抽象数据类型构成一个矩阵的抽象数据类型 第23页/共41页第二十四页，共41页。抽象数据类型的描述抽象数据类型的描述抽象数据类型可用（抽象数据类型可用（D，S，P）三元）三元组表示组表示其中其中(qzhng)，D是数据对象，是数据对象，S是是D上的关系集，上的关系集，P是对是对D的基本的基本操作集。操作集。ADT 抽象数据类型名抽象数据类型名 数据对象：数据对象的定义数据对象：数据对象的定义 数据关系：
15、数据关系的定义数据关系：数据关系的定义 基本操作：基本操作的定义基本操作：基本操作的定义 ADT 抽象数据类型名抽象数据类型名第24页/共41页第二十五页，共41页。其其其其中中中中,数数数数据据据据对对对对象象象象、数数数数据据据据关关关关系系系系用用用用伪伪伪伪码码码码描描描描述述述述；基基基基本本本本操操操操作定义格式为作定义格式为作定义格式为作定义格式为基本操作名（参数表）基本操作名（参数表）基本操作名（参数表）基本操作名（参数表）初始条件：初始条件描述初始条件：初始条件描述初始条件：初始条件描述初始条件：初始条件描述操作结果：操作结果描述操作结果：操作结果描述操作结果：操作结果描述操
16、作结果：操作结果描述基基基基本本本本操操操操作作作作有有有有两两两两种种种种参参参参数数数数：赋赋赋赋值值值值参参参参数数数数只只只只为为为为操操操操作作作作提提提提供供供供输输输输入入入入(shr)(shr)值值值值；引引引引用用用用参参参参数数数数以以以以&打打打打头头头头，除除除除可可可可提提提提供供供供输入输入输入输入(shr)(shr)值外，还将返回操作结果。值外，还将返回操作结果。值外，还将返回操作结果。值外，还将返回操作结果。“初初初初始始始始条条条条件件件件”描描描描述述述述了了了了操操操操作作作作执执执执行行行行之之之之前前前前数数数数据据据据结结结结构构构构和和和和参参参参
17、数数数数应应应应满满满满足足足足的的的的条条条条件件件件，若若若若不不不不满满满满足足足足，则则则则操操操操作作作作失失失失败败败败，并返回相应出错信息。并返回相应出错信息。并返回相应出错信息。并返回相应出错信息。“操操操操作作作作结结结结果果果果”说说说说明明明明了了了了操操操操作作作作正正正正常常常常完完完完成成成成之之之之后后后后，数数数数据据据据结结结结构构构构的的的的变变变变化化化化状状状状况况况况和和和和应应应应返返返返回回回回的的的的结结结结果果果果。若若若若初初初初始始始始条条条条件件件件为空，则省略之。为空，则省略之。为空，则省略之。为空，则省略之。第25页/共41页第二十六
18、页，共41页。抽象数据类型的表示和实现抽象数据类型的表示和实现(shxin)抽象数据类型可以通过固有数据抽象数据类型可以通过固有数据类型类型(高级编程语言中已实现高级编程语言中已实现(shxin)的数据类型的数据类型)来实现来实现(shxin)抽象数据类型抽象数据类型 类类 class数据对象数据对象 数据成员数据成员基本操作基本操作 成员函数成员函数(方法方法)在在C+中，类的成分中，类的成分(数据成员数据成员和成员函数和成员函数)可以有三种访问级可以有三种访问级别别Private 私有成分（只允许类的私有成分（只允许类的成员函数进行访问）成员函数进行访问）protected 保护成分（只允
19、许类保护成分（只允许类的成员函数及其子孙类进行访的成员函数及其子孙类进行访问）问）public 公有成分（允许类的成员公有成分（允许类的成员函数、类的实例及其子孙类、函数、类的实例及其子孙类、子孙类的实例进行访问）子孙类的实例进行访问）第26页/共41页第二十七页，共41页。算法算法(sun f)(sun f)和算法和算法(sun(sun f)f)分析分析n n定义：为了解决某类问题而规定的定义：为了解决某类问题而规定的一个有限长的操作序列一个有限长的操作序列。n n特性：特性：n n有穷性有穷性 算法在执行有穷步后能结算法在执行有穷步后能结束束n n确定性确定性 每步定义都是确切、无歧每步定
20、义都是确切、无歧义义n n可行性可行性 每一条运算应足够基本每一条运算应足够基本(jbn)n n输入输入 有有0个或多个输入个或多个输入n n 输出输出 有一个或多个输出有一个或多个输出第27页/共41页第二十八页，共41页。算法设计算法设计(shj)(shj)例子：例子：选择排序选择排序问题：递增排序问题：递增排序解决方案：逐个选择最小数据解决方案：逐个选择最小数据算法框架：算法框架：for(int i=0;i n-1;for(int i=0;i n-1;i+)/n-1i+)/n-1趟趟 从从aiai检查到检查到an-1;an-1;若最小整数在若最小整数在ak,ak,交换交换aiai与与ak
21、;ak;细化：细化：Select Sort Select Sort 第28页/共41页第二十九页，共41页。void selectSort(int a,int n)void selectSort(int a,int n)/对对对对n n个整数个整数个整数个整数a0,a1,an-1a0,a1,an-1按递增按递增按递增按递增(dzng)(dzng)顺顺顺顺序排序序排序序排序序排序 for(int i=0;i n-1;i+)for(int i=0;i n-1;i+)int k=i;int k=i;for(int j=i+1;j n;j+)for(int j=i+1;j n;j+)if(aj ak)
22、k=j;/if(aj ak)k=j;/从从从从aiai查到查到查到查到an-1,an-1,找最小整数找最小整数找最小整数找最小整数,在在在在akak int temp=ai;ai=ak;ak=int temp=ai;ai=ak;ak=temp;temp;第29页/共41页第三十页，共41页。性能性能(xngnng)分析与度量分析与度量算法的性能标准算法的性能标准正确性正确性可读性可读性健壮性健壮性效率（时间效率（时间(shjin)、空间）、空间）第30页/共41页第三十一页，共41页。算法的事后统计（后期测试）算法的事后统计（后期测试）算法的事后统计（后期测试）算法的事后统计（后期测试）在算法
23、中的某些部位插装时间在算法中的某些部位插装时间在算法中的某些部位插装时间在算法中的某些部位插装时间(shjin)(shjin)函数函数函数函数time(),time(),测定算法完成某一功能所花费时间测定算法完成某一功能所花费时间测定算法完成某一功能所花费时间测定算法完成某一功能所花费时间(shjin)(shjin)double start,stop;double start,stop;time(&start);time(&start);int k=seqsearch(a,n,x);int k=seqsearch(a,n,x);time(&stop);time(&stop);double ru
24、nTime=stop-start;double runTime=stop-start;printf(”%d%dn ,n,runTime printf(”%d%dn ,n,runTime););第31页/共41页第三十二页，共41页。int seqsearch(int a,int n,int x)/在在a0,an-1中搜索中搜索(su su)x int i=0;while(i n&ai!=x)i+;if(i=n)return-1;return i;第32页/共41页第三十三页，共41页。算法的事前估计算法的事前估计算法的事前估计算法的事前估计时间复杂度度量时间复杂度度量时间复杂度度量时间复杂度度
25、量运行时间运行时间运行时间运行时间=算法中每条语句执行时间之算法中每条语句执行时间之算法中每条语句执行时间之算法中每条语句执行时间之和。和。和。和。每条语句执行时间每条语句执行时间每条语句执行时间每条语句执行时间=该语句的执行次数该语句的执行次数该语句的执行次数该语句的执行次数(csh)(csh)（频度）（频度）（频度）（频度）*语句执行一次所需语句执行一次所需语句执行一次所需语句执行一次所需时间。时间。时间。时间。语句执行一次所需时间取决于机器的指语句执行一次所需时间取决于机器的指语句执行一次所需时间取决于机器的指语句执行一次所需时间取决于机器的指令性能和速度和编译所产生的代码质令性能和速度
26、和编译所产生的代码质令性能和速度和编译所产生的代码质令性能和速度和编译所产生的代码质量，很难确定。量，很难确定。量，很难确定。量，很难确定。设每条语句执行一次所需时间为单位时设每条语句执行一次所需时间为单位时设每条语句执行一次所需时间为单位时设每条语句执行一次所需时间为单位时间，则一个算法的运行时间就是该算间，则一个算法的运行时间就是该算间，则一个算法的运行时间就是该算间，则一个算法的运行时间就是该算法中所有语句的频度之和。法中所有语句的频度之和。法中所有语句的频度之和。法中所有语句的频度之和。第33页/共41页第三十四页，共41页。举例(jl)1矩阵相乘算法矩阵相乘算法 for(i=1;i=
27、n;+i)for(i=1;i=n;+i)/n+1/n+1 for(j=1;j=n;+j)for(j=1;j=n;+j)/n(n+1)/n(n+1)c i j =0;c i j =0;/n2/n2 for(k=1;k=n;+k)for(k=1;k=n;+k)/n2(n+1)/n2(n+1)c i j +=a i c i j +=a i k*b k j;/n3k*b k j;/n3 则则 算法执行算法执行(zhxng)(zhxng)时间时间T(n)T(n)为为所有语句的频度之和。所有语句的频度之和。T(n)=n+1+n(n+1)+n3 T(n)=n+1+n(n+1)+n3 =2n3+3n2+2n+
28、1 =2n3+3n2+2n+1第34页/共41页第三十五页，共41页。vv渐进时间复杂度 vv 引入“O”记号，以体现随问题规模n的增长率。vv T(n)=n+1+n(n+1)+n3 =2n3+3n2+2n+1 O(n3)，其中n3 为增长最快的项。vv最坏时间复杂度 vs.平均时间复杂度vv 有时算法基本操作重复执行次数还随问题的输入(shr)数据集不同而不同（如一些排序算法）。vv 这时可分析最坏时间复杂度（最坏情况下的时间复杂度）和平均时间复杂度（平均情况下的时间复杂度）第35页/共41页第三十六页，共41页。估计算法时间的通常做法：估计算法时间的通常做法：根据问题（或算法类型），从根据
29、问题（或算法类型），从算法中选取一种原操作（指固算法中选取一种原操作（指固有数据类型的操作）作为基本有数据类型的操作）作为基本操作。操作。其重复执行次数应与算法执行其重复执行次数应与算法执行时间成正比；时间成正比；一般为最深层循环内的语句中一般为最深层循环内的语句中的原操作；的原操作；用该基本操作重复执行的次数用该基本操作重复执行的次数作为算法的时间度量。即统计作为算法的时间度量。即统计包含该操作的所有语句的频度包含该操作的所有语句的频度(pn d)之和。之和。如：上例中选取乘法为基本如：上例中选取乘法为基本操作；算法执行时间操作；算法执行时间 T(n)则则正比于乘法所在语句的频度正比于乘法所
30、在语句的频度(pn d)n3,记为记为T(n)=O(n3)第36页/共41页第三十七页，共41页。试估计以下(yxi)程序段 的时间复杂度 for(i=1;i=n;+i)for(j=1;j=i;+j)for(k=1;k=j;+k)x+基本操作执行次数为 因此 T(n)=O(n3)举例(jl)2第37页/共41页第三十八页，共41页。uu空间复杂度度量空间复杂度度量空间复杂度度量空间复杂度度量uu存储空间的固定部分存储空间的固定部分存储空间的固定部分存储空间的固定部分程序指令代码的空间，常数、简单变量、程序指令代码的空间，常数、简单变量、程序指令代码的空间，常数、简单变量、程序指令代码的空间，常
31、数、简单变量、定长成分定长成分定长成分定长成分(chng fn)(chng fn)(如数组元素、结构如数组元素、结构如数组元素、结构如数组元素、结构成分成分成分成分(chng fn)(chng fn)、对象的数据成员等、对象的数据成员等、对象的数据成员等、对象的数据成员等)变变变变量所占空间量所占空间量所占空间量所占空间uu可变部分可变部分可变部分可变部分尺寸与实例特性有关的成分尺寸与实例特性有关的成分尺寸与实例特性有关的成分尺寸与实例特性有关的成分(chng fn)(chng fn)变量所占空间、引用变量所占空间、递归变量所占空间、引用变量所占空间、递归变量所占空间、引用变量所占空间、递归变
32、量所占空间、引用变量所占空间、递归栈所用空间、通过栈所用空间、通过栈所用空间、通过栈所用空间、通过newnew和和和和deletedelete命令动态命令动态命令动态命令动态使用空间使用空间使用空间使用空间uu空间复杂度空间复杂度空间复杂度空间复杂度 uu 原地工作（额外空间相对输入数据量原地工作（额外空间相对输入数据量原地工作（额外空间相对输入数据量原地工作（额外空间相对输入数据量来说是常数）来说是常数）来说是常数）来说是常数）第38页/共41页第三十九页，共41页。常见(chnjin)时间复杂度O(1)O(1)常数阶常数阶O(n)O(n)线性阶线性阶O(n2)O(n2)平方平方(pngfng)(pngfng)阶阶O(nb)O(nb)多项式阶多项式阶O(lnn)O(lnn)对数阶对数阶O(2n)O(2n)指数阶指数阶常见函数的增长率（图常见函数的增长率（图1.71.7）第39页/共41页第四十页，共41页。作业(zuy)课后阅读(yud)：习题集第1-6页。习题:习题集page 9 1.8(8)第40页/共41页第四十一页，共41页。