数据结构课程简介课件.ppt

-电子课件电子课件 数据结构是一门研究数据结构是一门研究非数值计算非数值计算的程序设计问题中计算机的程序设计问题中计算机的的操作对象操作对象及其之间及其之间关系与操作关系与操作的学科，是介于的学科，是介于数学、计算机数学、计算机硬件和计算机软件硬件和计算机软件三者之间的一门核心课程，属于计算机学科三者之间的一门核心课程，属于计算机学科中的一门综合性专业基础课程，它不仅是一般程序设计的基础，中的一门综合性专业基础课程，它不仅是一般程序设计的基础，也是设计和实现编译程序、操作系统、数据库系统及其他系统也是设计和实现编译程序、操作系统、数据库系统及其他系统程序和大型应用程序的重要基础。是计算机专业专升本、考研程序和大型应用程序的重要基础。是计算机专业专升本、考研必考课程。必考课程。数据结构课程简介 学业基础学业基础先修课程：先修课程：离散数学、高级语言程序设计离散数学、高级语言程序设计 (如如C C语言语言)后续课程：后续课程：操作系统、数据库原理、人工智能等。操作系统、数据库原理、人工智能等。数据结构数据结构(C(C语言版语言版)教材：教材：数据结构数据结构(C(C语言版语言版)参考书：参考书：1数据结构题集数据结构题集严蔚敏严蔚敏2数据结构数据结构与算法分析与算法分析C语言描述语言描述（英文版（英文版.第第2版）人邮社陈越改编版）人邮社陈越改编3数据结构数据结构使用使用C语言（第语言（第3版）版），西，西安交大出版社，安交大出版社，2003年朱战立编著年朱战立编著 内内 容容 安安 排排章章内内 容容 学时学时 章章 内内 容容 学时学时 1绪绪 论论2+22+27图图10+210+22线性表线性表8+28+28动态存储管理动态存储管理2 23栈和队列栈和队列10+410+49查找查找12+212+24串串4+24+210内部排序内部排序8+28+25数组和广义表数组和广义表 4 411外部排序外部排序1 16树和二叉树树和二叉树 12+412+412文件文件1 1学习要求1 1、上课认真听讲，适当做好笔记，按时交作业。、上课认真听讲，适当做好笔记，按时交作业。2 2、复习和预习。、复习和预习。3 3、课后需要多读课本和参考书，上网查看相关内容，、课后需要多读课本和参考书，上网查看相关内容，在理解基本内容的基础上，多看、多做习题。在理解基本内容的基础上，多看、多做习题。4 4、上机实践。、上机实践。1.1数据结构讨论的范畴数据结构讨论的范畴1.2基本概念基本概念1.3算法和算法的量度算法和算法的量度第一章 绪论1.11.1 数据结构讨论的范畴数据结构讨论的范畴Niklaus Wirth：Algorithm+DataStructures=Programs程序设计程序设计:算法算法:数据结构数据结构:为计算机处理问题编制 一组指令集 处理问题的策略处理问题的策略问题的数学模型问题的数学模型 f(x)=ax2+bx+c 例如例如:数值计算的程序设计问题数值计算的程序设计问题 一元二次方程求解 一元线性回归分析经济预测 例一：例一：计算机对弈算法：?模型：?对弈的规则和策略棋盘及棋盘的格局非数值计算的程序设计问题非数值计算的程序设计问题例二：例二：学生的数据库管理算法：?模型：?需要管理的项目？如何管理？用户界面？各种表格概括地说：概括地说：数据结构是一门讨论数据结构是一门讨论“描述现实世描述现实世界实体的数学模型界实体的数学模型(非数值计算非数值计算)及其及其上的操作在计算机中如何表示和实现上的操作在计算机中如何表示和实现”的学科。的学科。数据结构数据结构=逻辑结构逻辑结构+存储结构存储结构+运算运算1.2 基本概念基本概念一、数据与数据结构一、数据与数据结构二、数据类型二、数据类型三、抽象数据类型三、抽象数据类型一、数据与数据结构一、数据与数据结构所有能被输入被输入到计算机中，且能被计算机处理的符号处理的符号的集合。数据数据:是数据（集合）中的一个“个体个体”数据元素数据元素:是数据结构中讨论的基本基本单位 数据项：数据项：是数据结构中讨论的最小最小单位数据元素可以是数据项的集合数据元素可以是数据项的集合例如：描述一个学生的数据元素可以是称之为组合项称之为组合项姓名姓名 性别性别 出生日期出生日期 入学日期入学日期系科系科成绩成绩 数据结构：数据结构：带结构结构的数据元素的集合假设用三个三个4位的十进制数位的十进制数表示一个含 12位位数的十进制数。数的十进制数。3214,6587,9345 a1(3214),a2(6587),a3(9345)则在数据元素 a1、a2 和 a3 之间存在着“次序次序”关系关系 a1,a2、a2,a3 3214，6587，9345 a1 a2 a3 6587，3214，9345 a2 a1 a3例如例如:再例，在一维数组 a1,a2,a3,a4,a5,a6 的数据元素之间存在如下的次序关系次序关系:|i=1,2,3,4,5 或者说，数据结构数据结构是相互之间存在着某相互之间存在着某种种逻辑逻辑关系的数据元素的集合关系的数据元素的集合。数据结构：数据结构：带结构结构的数据元素的集合可见，不同的“关系关系”构成不同的“结构结构”数据的逻辑结构逻辑结构可归结为以下四类四类:线性线性结构树形树形结构图状图状结构集合集合结构1 1对对1 11 1对多对多多对多多对多松散松散非非线线性性例：例：UNIX文件系统的系统结构图文件系统的系统结构图例：例：n个网站之间的连通关系个网站之间的连通关系树形关系树形关系树形关系树形关系网状关系网状关系网状关系网状关系数据结构的形式定义数据结构的形式定义为:数据结构数据结构是一个二元组 Data_Structures=(D,S)其中:D 是数据元素的有限集数据元素的有限集，S 是 D上关系的有限集关系的有限集。逻辑结构示例：逻辑结构示例：S=(D,R)D=a,b,c,d,e,fR=(a,e),(b,c),(c,a),(e,f),(f,d)解：解：上述表达式可用图形表示为：上述表达式可用图形表示为：bcaefd此结构为此结构为线性线性的。的。例例1：用图形表示下列数据结构，并指出它们是属于线性：用图形表示下列数据结构，并指出它们是属于线性结构还是非线性结构。结构还是非线性结构。d1d5d2d4d3该结构该结构是非线性是非线性的。的。解：上述表达式可用图形表示为：解：上述表达式可用图形表示为：（2）S=(D,R)D=di|1i5 R=(di,dj),ij课堂练习课堂练习数据的存储结构存储结构 逻辑结构在存储器中的映象逻辑结构在存储器中的映象“数据元素数据元素”的映象的映象？“关系关系”的映象的映象？数据元素的映象方法：数据元素的映象方法：用二进制位(bit)的位串表示数据元素(321)10 =(501)8 =(101000001)2关系的映象方法：关系的映象方法：（表示（表示 x,y 的方法的方法）顺序映象顺序映象以相对的存储位置表示后继关系以相对的存储位置表示后继关系链式映象链式映象以附加信息以附加信息(指针指针)表示后继关系表示后继关系对于一个数据结构对于一个数据结构B=（K，R）其中其中K=k1,k2,k3,k4,k5,k6,k7,k8,k9R=rr=,它的顺序存储方式如图所示它的顺序存储方式如图所示例例2-（1）对于一个数据结构对于一个数据结构B=B=（K K，R R）其）其中中K=k1,k2,k3,k4,k5K=k1,k2,k3,k4,k5R=rR=rr=,kr=,4,k5它的链式存储方式如图所示它的链式存储方式如图所示例例2-（2）在不同的编程环境中，在不同的编程环境中，存储结构可有不同的描述方法。存储结构可有不同的描述方法。通常可用高级编程语言中提供的通常可用高级编程语言中提供的数据类型数据类型描述之描述之。二、数据类型二、数据类型 在用高级语言的源程序中，对程序中出现的每个变量、常量或表达式，需要说明说明它们所属的数据类型数据类型。数据类型数据类型 是一个是一个 值的集合值的集合和定义在此集合上的和定义在此集合上的 一组操作一组操作的总称。的总称。三、抽象数据类型三、抽象数据类型 (AbstractDataType简称简称ADT)是指一个数学模型以及是指一个数学模型以及定义在此数学模型上的一定义在此数学模型上的一组操作。组操作。ADT有两个重要特征:数据抽象数据抽象 用ADT描述程序处理的实体时，强调的是其本质的特征本质的特征、其所能完成的其所能完成的功能功能以及它和外部用户的接口外部用户的接口。数据封装数据封装 将实体的外部特性和其内部外部特性和其内部实现细节分离实现细节分离，并且对外部用户隐藏对外部用户隐藏其内部实现细节。其内部实现细节。抽象数据类型的描述方法抽象数据类型的描述方法抽象数据类型可用抽象数据类型可用（D，S，P）三元组表示。三元组表示。其中：其中：D是数据对象；是数据对象；S是是 D上的关系集；上的关系集；P是对是对 D的基本操作集。的基本操作集。ADT 抽象数据类型名抽象数据类型名 数据对象：数据对象：数据对象的定义 数据关系：数据关系：数据关系的定义 基本操作：基本操作：基本操作的定义ADT 抽象数据类型名其中基本操作的定义格式为:基本操作名基本操作名（参数表）初始条件：初始条件：初始条件描述 操作结果操作结果：操作结果描述 赋值参数赋值参数 只为操作提供输入值。引用参数引用参数 以&打头，除可提供输入值外，还将返回操作结果。初始条件初始条件 描述了操作执行之前数据结构和参数应满足的条件，若不满足，则操作失败，并返回相应出错信息。操作结果操作结果 说明了操作正常完成之后，数据结构的变化状况和应返回的结果。若初始条件为空，则省略之。例如，例如，抽象数据类型复数复数的定义：数据对象：数据对象：De1,e2e1,e2RealSet 数据关系：数据关系：R1|e1是复数的实数部分|e2 是复数的虚数部分 ADTComplex基本操作：基本操作：AssignComplex(&Z,v1,v2)操作结果：构造复数 Z,其实部和虚部 分别被赋以参数 v1 和 v2 的值。DestroyComplex(&Z)操作结果：复数Z被销毁。GetReal(Z,&realPart)初始条件：复数已存在。操作结果：用realPart返回复数Z的实部值。GetImag(Z,&ImagPart)初始条件：复数已存在。操作结果：用ImagPart返回复数Z的虚部值。Add(z1,z2,&sum)初始条件：z1,z2是复数。操作结果：用sum返回两个复数z1,z2 的 和值。ADTComplex抽象数据类型的表示和实现抽象数据类型的表示和实现 抽象数据类型需要通过固有数据固有数据类型类型(高级编程语言中已实现的数据类型)来实现。例如，对以上定义的复数。例如，对以上定义的复数。typedefstruct float realpart；float imagpart；complex；/-存储结构的定义存储结构的定义/-基本操作的函数原型说明基本操作的函数原型说明void Assign(complex&Z,float realval,float imagval)；/构造复数 Z,其实部和虚部分别被赋以参数/realval 和 imagval 的值float GetReal(complex Z)；/返回复数 Z 的实部值float Getimag(complex Z)；/返回复数 Z 的虚部值voidadd(complex z1,complex z2,complex&sum)；/以 sum 返回两个复数 z1,z2 的和 /-基本操作的实现基本操作的实现voidadd(complex z1,complex z2,complex&sum)/以 sum 返回两个复数 z1,z2 的和 sum.realpart=z1.realpart+z2.realpart;sum.imagpart=z1.imagpart+z2.imagpart;其它省略 三、抽象数据类型三、抽象数据类型 (AbstractDataType简称简称ADT)是指一个数学模型以及是指一个数学模型以及定义在此数学模型上的一定义在此数学模型上的一组操作。组操作。ADT有两个重要特征:数据抽象数据抽象 用ADT描述程序处理的实体时，强调的是其本质的特征本质的特征、其所能完成的其所能完成的功能功能以及它和外部用户的接口外部用户的接口。数据封装数据封装 将实体的外部特性和其内部外部特性和其内部实现细节分离实现细节分离，并且对外部用户隐藏对外部用户隐藏其内部实现细节。其内部实现细节。抽象数据类型的描述方法抽象数据类型的描述方法抽象数据类型可用抽象数据类型可用（D，S，P）三元组表示。三元组表示。其中：其中：D是数据对象；是数据对象；S是是 D上的关系集；上的关系集；P是对是对 D的基本操作集。的基本操作集。ADT 抽象数据类型名抽象数据类型名 数据对象：数据对象：数据对象的定义 数据关系：数据关系：数据关系的定义 基本操作：基本操作：基本操作的定义ADT 抽象数据类型名其中基本操作的定义格式为:基本操作名基本操作名（参数表）初始条件：初始条件：初始条件描述 操作结果操作结果：操作结果描述 赋值参数赋值参数 只为操作提供输入值。引用参数引用参数 以&打头，除可提供输入值外，还将返回操作结果。初始条件初始条件 操作结果操作结果抽象数据类型的表示和实现抽象数据类型的表示和实现 抽象数据类型需要通过固有数据固有数据类型类型(高级编程语言中已实现的数据类型)来实现。例如，对于一个三元组的实现例如，对于一个三元组的实现(类类C语言语言)。typedefElemType*Triplet;StatusInitTriplet(Triplet&T,ElemTypev1,ElemTypev1,ElemTypev1);StatusDestroyTriplet(Triplet&T);StatusGet(TripletT,inti,ElemType&e);StatusIsAscending(TripletT);StatusMax(TripletT,Element&e);StatusInitTriplet(Triplet&T,ElemTypev1,ElemTypev1,ElemTypev1)T=(ElemType*)malloc(3*sizeof(ElemType);if(!T)exit(OVERFLOW);T0=v1;T1=v2;T2=v3;returnOK;类C语言描述三元组StatusDestroyTriplet(Triplet&T)free(T);T=NULL;returnOK;StatusGet(TripletT,inti,ElemType&e)if(i3)returnERROR;e=Ti-1;returnOK;StatusIsAscending(TripletT)return(T0=T1&T1=T2);StatusMax(TripletT,Element&e)e=(T0=T1)?(T0=T2)?T0:T2):(T1=T2)?T1:T2);returnOK;小结数据结构数据结构l逻辑结构逻辑结构+存储结构存储结构+运算运算逻辑结构：线性，树，图，集合逻辑结构：线性，树，图，集合存储结构：顺序存储和非顺序存储存储结构：顺序存储和非顺序存储数据类型和抽象数据类型数据类型和抽象数据类型作业：教学主页上：作业：教学主页上：（1）练习练习1（2）用用C语言实现教材语言实现教材12页的三元组的页的三元组的ADT描描述述 1.3 1.3 算法和算法的衡量算法和算法的衡量一、算法一、算法二、算法设计的原则二、算法设计的原则三、算法效率的衡量方法和准则三、算法效率的衡量方法和准则四、算法的存储空间需求四、算法的存储空间需求 算法算法是为了解决某类问题而规定的一个有限长的操作序列操作序列。一个算法必须满足以下五五个重要特性重要特性：1 1有穷性有穷性 2 2确定性确定性 3 3可行性可行性4 4有输入有输入 5 5有输出有输出一、算法一、算法二、算法设计的原则二、算法设计的原则设计算法时，通常应考虑达到以下目标：1正确性正确性2.可读性可读性3健壮性健壮性4高效率与低存储量需求高效率与低存储量需求算法执行时间算法执行时间所需的最大存储空间所需的最大存储空间三三、算法效率的、算法效率的 衡量方法和准则衡量方法和准则通常有两种两种衡量算法效率的方法:事后统计法事后统计法缺点：缺点：1必须执行程序 2其它因素掩盖算法本质事前分析估算法事前分析估算法#include#include#include#defineN1000intseqsearch(inta,constintn,constintx)/*n是数组的长度是数组的长度*/inti;for(i=1;i=n;i+)if(ai=x)break;return1;一个事后统计运行一个事后统计运行时间的程序时间的程序voidtimesearch()inti,aN+1;longintj;doublerunTime;clock_tstart,end;for(i=1;i=N;i+)/*给数组赋值给数组赋值*/ai=i;start=clock();for(j=0;j=60000;j+)seqsearch(a,N,0);end=clock();runTime=(double)(end-start);printf(Thisprogramruntime:%6.3fn,runTime);voidmain()timesearch();一个特定一个特定算法的算法的“运行工作量运行工作量”的大小，只依赖于的大小，只依赖于问题的规模问题的规模（通常用整数量（通常用整数量n表示），或者说，表示），或者说，它是问题规模的函数。它是问题规模的函数。假如，随着问题规模 n 的增长，算法执行时间的增长率和算法执行时间的增长率和f(n)的增长的增长率相同率相同，则可记作：T(n)=O(f(n)称称T(n)为算法的为算法的(渐近)时间复杂度。时间复杂度。3n+2=O(n)因为因为3n+2 4n当当n 2时时6*2n+n2=O(2n)因为因为6*2n+n2 7*2n当当n 4例：例：渐进符号渐进符号（O）的定义的定义：当且仅当存在当且仅当存在一个正的常数一个正的常数 C C，使得对所有的使得对所有的 n n n n0 0 ，有，有 f(n)f(n)Cg(n)Cg(n)，则：则：f(nf(n)=)=O(g(n)(g(n)时间复杂度时间复杂度T(n)按数量级递增按数量级递增顺序为：顺序为：多项式阶多项式阶如何估算如何估算 算法的时间复杂度？算法的时间复杂度？从算法中选取一种对于所研究的问题来说是 基本操作基本操作 的原操作，以该基本操作 在算法中重复执行的次在算法中重复执行的次数数 作为算法运行时间的衡量准则。算法的时间复杂度由嵌套最深层语句的频度决定算法的时间复杂度由嵌套最深层语句的频度决定例例一一两两个个矩矩阵阵相相乘乘voidmult(inta,intb,int&c)/以二维数组存储矩阵元素，以二维数组存储矩阵元素，c为为 a和和 b的乘积的乘积for(i=1;i=n;+i)for(j=1;j=n;+j)ci,j=0;for(k=1;k1&change;-i)/bubble_sortchange=FALSE;/change为元素进行交换标志为元素进行交换标志for(j=0;jaj+1)ajaj+1;change=TRUE;/一趟起泡一趟起泡基本操作基本操作:交换赋值操作交换赋值操作例例二二起起泡泡排排序序voidbubble_sort(int&a,intn)for(i=n-1,change=TRUE;i1&change;-i)/bubble_sort最好的情况最好的情况:交换交换0 0次次.最坏的情况最坏的情况:交换交换(n-1)+(n-2)+1=n(n-1)/2(n-1)+(n-2)+1=n(n-1)/2次次平均情况平均情况:略略change=FALSE;for(j=0;jaj+1)ajaj+1;change=TRUE;/一趟起泡一趟起泡时间复杂度最好时间复杂度最好时间复杂度最坏时间复杂度最坏时间复杂度平均时间复杂度平均时间复杂度思考思考:查找成功时查找成功时,顺序搜索的最好顺序搜索的最好,最坏最坏,平均时间复杂度平均时间复杂度?intseqsearch(inta,constintn,constintx)/*n是数组的长度是数组的长度*/inti;for(i=1;i=n;i+)if(ai=x)break;return1;课堂练习课堂练习:计算时间复杂度计算时间复杂度(1)i=1;j=0;while(i+jj)j+;elsei+;基本操作基本操作:if;语句执行次数语句执行次数:n时间复杂度时间复杂度:O(n)课堂练习课堂练习:计算时间复杂度计算时间复杂度(2)x=n;/n1y=0;while(x=(y+1)*(y+1)y+;基本操作基本操作:y+;语句执行次数语句执行次数:向下取整向下取整(n0.5-1)时间复杂度时间复杂度:O(n)四、算法的存储空间需求四、算法的存储空间需求算法的空间复杂度定义为空间复杂度定义为:表示随着问题规模表示随着问题规模n的增大，的增大，算法运行所需存储量的增长率算法运行所需存储量的增长率与与g(n)的增长率相同。的增长率相同。S(n)=O(g(n)算法的存储量算法的存储量包括:1输入数据输入数据所占空间2程序本身程序本身所占空间3辅助变量辅助变量所占空间 若输入数据输入数据所占空间只取决于问题 本身，和算法无关和算法无关，则只需要分析除 输入和程序之外的辅助变量辅助变量所占额外额外空间空间。若所需额外空间相对于输入数据量 来说是常数，则称此算法为原地工作原地工作。若所需存储量依赖于特定的输入，则通常按最坏情况考虑。1.熟悉各名词、术语的含义，掌握熟悉各名词、术语的含义，掌握基本概念。基本概念。2.理解算法五个要素的确切含义。理解算法五个要素的确切含义。本章学习要点本章学习要点3.掌握计算语句频度和估算算法时掌握计算语句频度和估算算法时间复杂度的方法。间复杂度的方法。