数据结构与数据库.pptx

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

1、教材教材数据结构（数据结构（c c语言版）语言版），严蔚敏，严蔚敏等编著等编著,清华大学出版社，清华大学出版社，19971997数据结构题集（数据结构题集（c c语言版）语言版），严，严蔚敏等编著蔚敏等编著,清华大学出版社，清华大学出版社，19991999第1页/共41页参考书参考书数据结构数据结构(第二版第二版)，唐策善、黄刘生，唐策善、黄刘生 编著，中国科大出版社，编著，中国科大出版社，20012001 Data Structures with C+,Williaw Ford et al.,Prentice Hall Inc.,1996.Data Structures&Program De

2、sign in C,2nd Ed.,Robert Kruse et al.,Prentice Hall Inc.,1997.第2页/共41页v什么是数据结构什么是数据结构v基本概念和术语基本概念和术语v抽象数据类型抽象数据类型v算法分析算法分析v性能分析与度量性能分析与度量第一章第一章 绪论绪论第3页/共41页学生成绩表格学生成绩表格学生成绩表格学生成绩表格第4页/共41页选课单选课单学号学号课程号课程号时间时间成绩成绩20001DS2000SX20002001,22000,9788720002ART2000DS20002002,22001,2689020003SX2000DS20002000

3、,92001,2877820004SX2000ART20002000,92002,28976第5页/共41页UNIX文件系统结构图文件系统结构图/rootbinlibuseretcmathdsswyintaoxieStack.cppQueue.cppTree.cpp第6页/共41页综上，综上，描述这类非数值计算问题的数学模型不是数学方程描述这类非数值计算问题的数学模型不是数学方程,而是树、表和图而是树、表和图之类的数据结构。之类的数据结构。因此从广义上讲，因此从广义上讲，数据结构描述现实世界实体的数学模型及其上的操作在计数据结构描述现实世界实体的数学模型及其上的操作在计算机中的表示和实现算机中

4、的表示和实现.第7页/共41页信息？数据？知识？第8页/共41页基本概念和术语基本概念和术语数据数据(Data)是信息的载体，是描述客观事物的数、字符、以及所有能输入到计算机是信息的载体，是描述客观事物的数、字符、以及所有能输入到计算机中，被计算机程序识别和处理的符号的集合。中，被计算机程序识别和处理的符号的集合。数值性数据数值性数据非数值性数据非数值性数据第9页/共41页数据元素（数据元素（Data Element）数据的数据的基本单位基本单位。在计算机程序。在计算机程序中常作为一个整体进行考虑和处中常作为一个整体进行考虑和处理。理。有时一个有时一个数据元素数据元素可以由若干可以由若干数数据

5、项据项(Data Item)组成。组成。数据项数据项是数据的不可分割的最小单位。是数据的不可分割的最小单位。数据元素又称为元素、结点、记数据元素又称为元素、结点、记录录第10页/共41页数据项数据项(Data Item)学学号号姓姓名名出生日期出生日期年年 月月 日日 籍籍贯贯年年级级系系别别宿宿舍舍号号第11页/共41页数据对象数据对象(Data Object)具有相同性质的数据元素的集合。具有相同性质的数据元素的集合。u整数数据对象整数数据对象 N=0,1,2,u字母字符数据对象字母字符数据对象C=C=A,B,C,F 第12页/共41页数据结构数据结构（Data Structure）形式定

6、义：形式定义：某一数据对象的所有数据成员某一数据对象的所有数据成员之间的关系。记为：之间的关系。记为：Data_Structure=D,SData_Structure=D,S 其中，其中，D D 是某一数据对象，是某一数据对象，S S 是该对象中所有数据成员之间的是该对象中所有数据成员之间的关关系系的有限集合。的有限集合。第13页/共41页序偶:一般来说，两个具有固定次序的客体组成一个序偶序偶，常常表示两个客体之间的关系。记作。其中的x和y分别称为第一元素和第二元素。如：“中国地处亚洲”表示为序偶具有确定的次序。=,iffx=u,y=v第一元素本身也可是一序偶。这样，序偶的概念可推广到n元组。

7、如:三元组可定义为一序偶,z第14页/共41页关系：任一序偶的集合确定了一个二元关系R，R中任一序偶可记做 xRy。例如，在实数中关系 可记作 =|x,y是实数且xy 数据结构的一个例子（例1.5)Group=(P,R)第15页/共41页四类基本结构四类基本结构集合线性结构树形结构 网状结构第16页/共41页数据的逻辑结构数据的逻辑结构从逻辑关系上描述数据，与数据的从逻辑关系上描述数据，与数据的存储无关；存储无关；从具体问题抽象出来的数据模型；从具体问题抽象出来的数据模型；与数据元素本身的形式、内容无关；与数据元素本身的形式、内容无关；与数据元素的相对位置无关。与数据元素的相对位置无关。第17

8、页/共41页数据的逻辑结构分类数据的逻辑结构分类 线性结构线性结构 线性表线性表 非线性结构非线性结构 树树 图（或网络）图（或网络）第18页/共41页bindevetclibuser2114131211234678910315871011998745662313155线性结构线性结构树形结构树形结构 树树 二叉树二叉树 二叉排序树二叉排序树第19页/共41页堆结构堆结构123548711102916125643125436113318146651921图结构图结构 网络结构网络结构第20页/共41页数据的存储结构数据的存储结构v数据结构在计算机中的表示（又称映象）。数据结构在计算机中的表示（

9、又称映象）。v包括数据元素的表示和关系的包括数据元素的表示和关系的 表示。表示。q 数据元素的表示数据元素的表示:位串（元素、结点）位串（元素、结点）q关系的表示关系的表示 顺序映象顺序映象 非顺序映象非顺序映象第21页/共41页抽象数据类型抽象数据类型（Abstract Data Type）n数据类型数据类型 定义：定义：一个值的集合和定义在这个值集上的一组一个值的集合和定义在这个值集上的一组操作的总称。操作的总称。nC语言中的基本数据类型语言中的基本数据类型 int char float double void 整型整型 字符型字符型 浮点型浮点型 双精度型双精度型 无值无值第22页/共4

10、1页抽象数据类型抽象数据类型是指一个数学模型以及定义在此数学模型上的一组操作是指一个数学模型以及定义在此数学模型上的一组操作数据结构数据结构+定义在此数据结构上的一组操作定义在此数据结构上的一组操作=抽象数据类型抽象数据类型 例如：矩阵例如：矩阵+（求转置、加、乘、（求转置、加、乘、求逆、求特征值）求逆、求特征值）构成一个矩阵的抽象数据类型构成一个矩阵的抽象数据类型 第23页/共41页抽象数据类型的描述抽象数据类型的描述抽象数据类型可用（抽象数据类型可用（D，S，P）三元组表示）三元组表示其中，其中，D是数据对象，是数据对象，S是是D上的关系集，上的关系集，P是对是对D的基本操作集。的基本操作

11、集。ADT 抽象数据类型名抽象数据类型名 数据对象：数据对象：数据对象的定义数据对象的定义 数据关系：数据关系：数据关系的定义数据关系的定义 基本操作：基本操作：基本操作的定义基本操作的定义 ADT 抽象数据类型名抽象数据类型名第24页/共41页其其中中,数数据据对对象象、数数据据关关系系用用伪伪码码描描述述；基基本本操作定义格式为操作定义格式为基本操作名（参数表）基本操作名（参数表）初始条件：初始条件：初始条件描述初始条件描述操作结果：操作结果：操作结果描述操作结果描述基基本本操操作作有有两两种种参参数数：赋赋值值参参数数只只为为操操作作提提供供输输入入值值；引引用用参参数数以以&打打头头，

12、除除可可提提供供输输入值外，还将返回操作结果。入值外，还将返回操作结果。“初初始始条条件件”描描述述了了操操作作执执行行之之前前数数据据结结构构和和参参数数应应满满足足的的条条件件，若若不不满满足足，则则操操作作失败，并返回相应出错信息。失败，并返回相应出错信息。“操操作作结结果果”说说明明了了操操作作正正常常完完成成之之后后，数数据据结结构构的的变变化化状状况况和和应应返返回回的的结结果果。若若初初始条件为空，则省略之。始条件为空，则省略之。第25页/共41页抽象数据类型的表示和实现抽象数据类型的表示和实现抽抽象象数数据据类类型型可可以以通通过过固固有有数数据据类类型型(高高级级编编程语言中

13、已实现的数据类型程语言中已实现的数据类型)来实现来实现抽象数据类型抽象数据类型 类类 class数据对象数据对象 数据成员数据成员基本操作基本操作 成员函数成员函数(方法方法)在在C+中，类的成分中，类的成分(数据成员和成员函数数据成员和成员函数)可以有三种访问级别可以有三种访问级别Private 私私有有成成分分（只只允允许许类类的的成成员员函函数数进进行行访访问）问）protected 保保护护成成分分（只只允允许许类类的的成成员员函函数数及及其其子孙类进行访问）子孙类进行访问）public 公公有有成成分分（允允许许类类的的成成员员函函数数、类类的的实实例例及其子孙类、子孙类的实例进行访

14、问）及其子孙类、子孙类的实例进行访问）第26页/共41页算法和算法分析算法和算法分析n定义定义：为了解决某类问题而规定的为了解决某类问题而规定的一个有限长的操作序列一个有限长的操作序列。n特性：特性：u有穷性有穷性 算法在执行有穷步后能结算法在执行有穷步后能结束束u确定性确定性 每步定义都是确切、无歧每步定义都是确切、无歧义义u可行性可行性 每一条运算应足够基本每一条运算应足够基本u输入输入 有有0个或多个输入个或多个输入u 输出输出 有一个或多个输出有一个或多个输出第27页/共41页算法设计算法设计例子：例子：选择排序选择排序问题：问题：递增排序递增排序解决方案：解决方案：逐个选择最小数据逐

15、个选择最小数据算法框架：算法框架：for(int i=0;i n-1;i+)/n-1趟趟 从从ai检查到检查到an-1;若最小整数在若最小整数在ak,交换交换ai与与ak;细化：细化：Select Sort 第28页/共41页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;第29页/共41页性能分析与度量性能分析与度量算法的性能标准算法的性能

16、标准u正确性正确性u可读性可读性u健壮性健壮性u效率（时间、空间）效率（时间、空间）第30页/共41页算法的事后统计（后期测试）算法的事后统计（后期测试）在算法中的某些部位插装时间函数在算法中的某些部位插装时间函数time(),测定算法完成某一功能所花费时间测定算法完成某一功能所花费时间doublestart,stop;time(&start);intk=seqsearch(a,n,x);time(&stop);double runTime=stop-start;printf(”%d%dn,n,runTime);第31页/共41页intseqsearch(inta,intn,intx)/在在a

17、0,an-1中搜索中搜索xint i=0;while(in&ai!=x)i+;if(i=n)return-1;returni;第32页/共41页算法的事前估计算法的事前估计时间复杂度度量时间复杂度度量n运行时间运行时间=算法中每条语句执行时间之和。算法中每条语句执行时间之和。n每条语句执行时间每条语句执行时间=该语句的执行次数（该语句的执行次数（频频度度）*语句执行一次所需时间。语句执行一次所需时间。n语句执行一次所需时间取决于机器的指令性能语句执行一次所需时间取决于机器的指令性能和速度和编译所产生的代码质量，很难确定。和速度和编译所产生的代码质量，很难确定。n设每条语句执行一次所需时间为单位

18、时间，则设每条语句执行一次所需时间为单位时间，则一个算法的运行时间就是该算法中一个算法的运行时间就是该算法中所有语句的所有语句的频度之和频度之和。第33页/共41页举例举例 1矩阵相乘算法for(i=1;i=n;+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第34页/共41页v渐进时间复杂度 引入“O”记号，以体现随问题规模n的增长率。

19、T(n)=n+1+n(n+1)+n3 =2n3+3n2+2n+1 O(n3)，其中n3 为增长最快的项。v最坏时间复杂度最坏时间复杂度 vs.vs.平均时间复杂度平均时间复杂度有时算法基本操作重复执行次数还随问题的输入数据集不同而不同（如一些排序算法）。这时可分析最坏时间复杂度（最坏情况下的时间复杂度）和平均时间复杂度（平均情况下的时间复杂度）第35页/共41页 估计算法时间的通常做法：估计算法时间的通常做法：根据问题（或算法类型），从算法中选取一种原操作（指固有数据类型的操作）作为基本操作。其重复执行次数应与算法执行时间成正比；一般为最深层循环内的语句中的原操作；用该基本操作重复执行的次数作

20、为算法的时间度量。即统计包含该操作的所有语句的频度之和。如：上例中选取乘法为基本操作；算法执行时间 T(n)则正比于乘法所在语句的频度n3,记为T(n)=O(n3)第36页/共41页试估计以下程序段 的时间复杂度 for(i=1;i=n;+i)for(j=1;j=i;+j)for(k=1;k=j;+k)x+基本操作执行次数为 因此 T(n)=O(n3)举例举例 2第37页/共41页u空间复杂度度量空间复杂度度量n n存储空间的固定部分存储空间的固定部分程序指令代码的空间，常数、简单变量、定长成分程序指令代码的空间，常数、简单变量、定长成分(如数组元素、结构成分、对象的数据成员等如数组元素、结构

21、成分、对象的数据成员等)变量变量所占空间所占空间n n可变部分可变部分尺寸与实例特性有关的成分变量所占空间、引用变尺寸与实例特性有关的成分变量所占空间、引用变量所占空间、递归栈所用空间、通过量所占空间、递归栈所用空间、通过new和和delete命令动态使用空间命令动态使用空间空间复杂度空间复杂度 原地工作原地工作（额外空间相对输入数据量来说是常（额外空间相对输入数据量来说是常数）数）第38页/共41页常见时间复杂度常见时间复杂度常见时间复杂度常见时间复杂度O(1)常数阶O(n)线性阶O(n2)平方阶O(nb)多项式阶O(lnn)对数阶O(2n)指数阶常见函数的增长率（图1.7）第39页/共41页作业作业课后阅读：习题集第1-6页。习题:习题集page 9 1.8(8)第40页/共41页感谢您的观看。第41页/共41页