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