数据子目录

2014/4/71数据结构1计算机学院肖明军Email:xiaomj@ustc.
edu.
cnhttp://staff.
ustc.
edu.
cn/~xiaomj课程简介先修课程及条件程序设计的经验、C、离散数学、概率分析教材:数据结构,黄刘生,经济科学出版社数据结构(C语言版)严蔚敏清华大学出版社2数据结构(C语言版),严蔚敏,清华大学出版社考核:考试+作业+上机参考书C++数据结构,WilliamFord清华影印版数据结构和程序设计,Robert,Kruse.
2nd版§Ch.
1绪论重要性人类社会已步入信息社会计算机不再仅仅局限于科学计算,已深入到社会生活的各个领域3"给我一根杠杆,我就能撬动地球""给我一个接口,我就能驱动地球"4§Ch.
1绪论重要性计算机:硬件+软件算法+数据结构=程序设计(N.
Wirth,84年图灵奖得主)两个问题信息的表示和处理5两个问题:信息的表示和处理信息的表示和组织又直接关系到处理信息的程序的效率.
随着应用问题的不断复杂,导致信息量剧增与信息范围的拓宽,使许多系统程序和应用程序的规模很大,结构又相当复杂.
因此,必须分析待处理问题中的对象的特征及各对象之间存在的关系,这就是数据结构这门课所要研究的问题.
编写解决实际问题的程序的一般过程:如何用数据形式描述问题—即由问题抽象出一个适当的数学模型;问题所涉及的数据量大小及数据之间的关系;§Ch.
1绪论6问题所涉及的数据量大小及数据之间的关系;如何在计算机中存储数据及体现数据之间的关系处理问题时需要对数据作何种运算所编写的程序的性能是否良好上面所列举的问题基本上由数据结构这门课程来回答.
2014/4/72例1:电话号码查询系统设有一个电话号码薄,它记录了N个人的名字和其相应的电话号码,假定按如下形式安排:(a1,b1),(a2,b2),…(an,bn),其中ai,bi(i=1,2…n)分别表示某人的名字和电话号码.
本问题是一种典型的表格问题.
如表所示,数据与数据成简单的一对一的7姓名电话号码陈海13612345588李四锋13056112345.
.
.
.
.
.
线性关系.
线性表结构例2:磁盘目录文件系统磁盘根目录下有很多子目录及文件,每个子目录里又可以包含多个子目录及文件,但每个子目录只有一个父目录,依此类推:本问题是一种典型的树型结8本问题是种典型的树型结构问题,如图所示,数据与数据成一对多的关系,是一种典型的非线性关系结构—树形结构.
树形结构结构例3:交通网络图从一个地方到另外一个地方可以有多条路径.
本问题是一种典型的网状结构问题,数据与数据成多对多的关系,是一种非线性关系结构.
佛山广州9惠州中山东莞深圳珠海网状结构§1.
1基本概念和术语数据:信息载体客观事物的符号表示,能由计算机程序识别、存储和加工处理的符号集合所有能够数字化的信息均可认为是数据10数据元素:数据的基本单位,在程序中通常作为一个整体来进行考虑和处理同义词:元素、结点、顶点、记录、对象、元组等数据项:具有独立含义的最小标识单位,客观事物某一方面特性的数据描述同义词:字段、域、属性等§1.
1基本概念和术语数据结构:相互之间存在一种或多种特定关系的数据元素的集合,即数据的组织形式数据的逻辑结构:数据元素之间的逻辑关系数据的存储结构:数据元素及其关系在计算机存储11数据的存储结构:数据元素及其关系在计算机存储器内的表示数据的运算:对数据施加的操作§1.
1基本概念和术语数据结构举例系别姓名职称SCIEI经费1张明教授51201王华教授6315…23李立教授166012行:结点(对象、记录、元组等);列:数据项(属性、域、字段等)逻辑结构:开始结点终端结点内部结点结点之间的逻辑关系:有且仅有1个开始结点和1个终端结点,表中任1结点最多只有1个直接前驱和1个直接后继-----线性关系存储结构:用数组实现,还是用指针实现运算:创建、插入、删除、查找等2014/4/73§1.
1基本概念和术语逻辑结构线性结构:任一结点最多只有1个直接前驱和1个直接后继非线性结构:一结点可有多个直接前驱和多个直接后继集合结构:元素间无关系,只有元素是否属于集合的关系13存储结构(1)顺序存储方法逻辑上相邻的结点存储在物理位置上相邻的存储单元里结点间的逻辑关系由存储单元的邻接关系来体现借助于数组描述应用于线性的数据结构,非线性的数据结构的线性化§1.
1基本概念和术语存储结构(2)链接存储方法该方法不要求逻辑上相邻的结点在物理位置上亦相邻借助于指针来表示结点间的逻辑关系(3)索引存储方法14在存储结点信息的同时,建立附加的索引表.
表中每项称为索引项(关键字,地址)稠密索引:每个结点对应1个索引项稀疏索引:一组结点对应1个索引项(4)散列存储方法根据结点的Key直接计算出该结点的存储地址.
数据结构的主要运算⑴建立(Create)一个数据结构;⑵消除(Destroy)一个数据结构;⑶从一个数据结构中删除(Delete)一个数据元素;⑷把一个数据元素插入(Insert)到一个数据结构中;§1.
1基本概念和术语15⑸对一个数据结构进行访问(Access);⑹对一个数据结构(中的数据元素)进行修改(Modify);⑺对一个数据结构进行排序(Sort);⑻对一个数据结构进行查找(Search).
§1.
1基本概念和术语数据结构3方面之联系同一逻辑结构的不同存储结构,则用不同名称称谓例如,线性表顺序表,链表,散列表运算不同称谓也不同16运算不同,称谓也不同线性表栈、队列顺序栈、顺序队列数据的逻辑结构和物理结构是密不可分的两个方面,一个算法的设计取决于所选定的逻辑结构,而算法的实现依赖于所采用的存储结构.
在C语言中,用一维数组表示顺序存储结构;用结构体类型表示链式存储结构.
逻辑结构与所采用的存储结构线性表树图顺序存储结构链式存储结构复合存储结构逻辑结构物理结构17数据的逻辑结构非线性结构集合图状结构有向图无向图树形结构一般树二叉树线性结构一般线性表线性表推广广义表数组串受限线性表栈和队列数据逻辑结构层次关系图§1.
1基本概念和术语数据类型:是一个值的集合以及定义在这些值上的一组操作的总称,可看作是高级语言提供的数据结构原子类型:值不可分,一般是基本的预定义类型int,char等,定义了"+","-"等18int,char等,定义了,等结构类型:可供用户定义的新类型,构造类型、导出类型、派生类型等由基本类型组织而成,如数组、struct等2014/4/74§1.
1基本概念和术语抽象数据类型(AbstractDataType)抽象的数据组织和与之相关的操作,可看作是数据的逻辑结构及其在逻辑结构上定义的抽象操作特点①封装与隐藏:将数据和操作封装在一起,内部结构和实现细节对外屏蔽实现信息隐藏19实现细节对外屏蔽,实现信息隐藏②抽象:用户只能通过ADT里定义的接口和说明来访问和操作数据.
他反映了程序设计的两层抽象:概念层(抽象)---ADT、类说明实现层---类实现,相当于普通类型应用层----如main(){…},通过操作对象解决实际问题§1.
1基本概念和术语抽象数据类型(AbstractDataType)ADTADT_Name{Data:数据结构(数据对象和数据关系)说明Operations:Constructor://构造函数,创建对象实例Operation1://用C++或C函数原型描述20input:Preconditions://初始条件,执行本操作前系统//需满足的状态process://对数据执行的操作output://对返回数据的说明Postconditions://执行本操作后系统的状态Operation2:}例:抽象数据类型复数的定义ADTComplex{数据对象:D={e1,e2|e1,e2∈RealSet}数据关系:R1={|e1是复数的实数部分,e2是复数的虚数部分}基本操作:InitComplex(&Z,v1,v2)操作结果:构造复数Z,其实部和虚部分别被赋以参数v1和v2的值.
DestroyComplex(&Z)操作结果复数Z被销毁§1.
1基本概念和术语21操作结果:复数Z被销毁.
GetReal(Z,&realPart)初始条件:复数已存在.
操作结果:用realPart返回复数Z的实部值.
GetImag(Z,&ImagPart)初始条件:复数已存在.
操作结果:用ImagPart返回复数Z的虚部值.
Add(z1,z2,&sum)初始条件:z1,z2是复数.
操作结果:用sum返回两个复数z1、z2的和值.
}ADTComplex抽象数据类型的表示与实现通过程序设计语言中的类型来实现C抽象数据类型数据对象结构体§1.
1基本概念和术语22数据对象结构体基本操作函数C++,Java抽象数据类型类class数据对象数据成员基本操作成员函数(方法)ADT复数的C描述typedefstruct{doublerealpart;doubleimagpart;}Complex;booleanassign(Complex*pSrc,Complex*pDes){if(pSrc==NULL||pDes==NULL)returnERROR;pDes->realpart=pSrc->realpart;pDes>imagpart=pSrc>imagpart;23pDes->imagpart=pSrc->imagpart;returnTRUE;}Complex*add(Complex*pZ1,Complex*pZ2){Complex*pSum=(Complex*)malloc(sizeof(Complex));if(pSum==NULL)returnNULL;pSum->realpart=pZ1->realpart+pZ2->realpart;pSum->imagpart=pZ1->imagpart+pZ2->imagpart;returnpSum;}ADT复数的C++描述classComplex{//类的声明protected:doublerealpart;doublemagpart;public:Complex();24Complex(doublerealVal,doubleimagVal);Complex(Complex&z){assign(z);}~Complex();voidassign(Complex&z);doublegetReal(void)const{returnrealpart;}doublegetImag(void)const{returnimagpart;}friendComplexadd(Complex&z1,Complex&z2);};2014/4/75//类的实现部分Complex::Complex(doublerealVal,doubleimagVal){realpart=realVal;imagpart=imagVal;}voidComplex::assign(Complex&z){realpart=z.
realpart;imagpart=zimagpart;25imagpart=z.
imagpart;}Complexadd(Complex&z1,Complex&z2){Complexsum(z1);sum.
realpart+=z2.
realpart;sum.
imagpart+=z2.
imagpart;returnsum;}§1.
2算法描述分析算法重要性:数据的运算是通过算法描述的定义:非形式地说,算法是任意一个良定义的计算过程,它以一个或多个值作为输入,并产生一个或多个值作为输出.
因此,一个算法就是一系列将输入转换为输出的计算步骤26列将输入转换为输出的计算步骤.
5要素输入、输出、有穷性(有穷步骤,每步时间有限)确定性(算法只有唯一执行路径)、可行性(所有操作可通过已经实现的基本运算有限次实现之)算法与程序的联系与区别§1.
2算法描述分析输入实例一个问题的输入实例是由满足问题陈述中的限制、并能计算出该问题解的所有输入构成的.
算法描述自然语言、数学语言、伪语言、程序语言等均可27自然语言、数学语言、伪语言、程序语言等均可本课程以C为主,但不拘泥于细节算法评价正确性、可读性、健壮性、时空性能算法分析算法效率的度量事后统计:利用计算机内部的计时功能缺陷必须先运行依据算法编制的程序§1.
2算法描述分析28必须先运行依据算法编制的程序时间统计量依赖于计算机的软硬件环境doublestart,stop;time(&start);mainprocess(n,…);time(&stop);doublerunTime=stop-start;printf("%d%d\n",n,runTime);事前分析估算(时间)求出该算法的一个时间界限函数一些影响因素:算法的策略§1.
2算法描述分析29算法的策略问题的规模书写程序的语言编译器产生的机器代码的质量机器执行指令的速度§1.
2算法描述与分析算法分析算法的时间是每语句执行时间的总和每语句的执行时间=该语句执行次数(频度)X该语句执行1次的时间假定:每语句执行1次的时间为1个时间单位30假定每语句执行次的时间为个时间单位则:算法的执行时间=∑各语句频度问题的规模(Size)n输入量的大小,如…时间复杂度:算法的运行时间,是问题规模的函数2014/4/76§1.
2算法描述与分析时间复杂度例1:矩阵乘法for(i=0;isqrt(n))printf("&d是一个素数\n",n);37elseprintf("&d不是一个素数\n",n);}嵌套的最深层语句是i++;其频度由条件((n%i)!
=0&&i*1.
01&&change;--i)change=false;for(j=0;ja[j+1])38if(a[j]>a[j+1]){a[j]←→a[j+1];change=TURE;}}最好情况:0次最坏情况:1+2+3++n-1=n(n-1)/2平均时间复杂度为:O(n2)空间复杂度(Spacecomplexity):是指算法编写成程序后,在计算机中运行时所需存储空间大小的度量.
记作:S(n)=O(f(n))其中:n为问题的规模(或大小)该存储空间一般包括三个方面:指令常数变量所占用的存储空间;§1.
2算法描述与分析39指令常数变量所占用的存储空间;输入数据所占用的存储空间;辅助(存储)空间.
一般地,算法的空间复杂度指的是辅助空间.
一维数组a[n]:空间复杂度O(n)二维数组a[n][m]:空间复杂度O(n*m)作业1数据的逻辑结构数据的物理结构逻辑结构与物理结构的区别和联系是什么2分析以下程序段的时间复杂度,请说明分析的理由或原因.
40⑴Sum1(intn){intp=1,sum=0,m;for(m=1;m<=n;m++){p*=m;sum+=p;}return(sum);}⑵Sum2(intn){intsum=0,m,t;for(m=1;m<=n;m++){p=1;for(t=1;t<=m;t++)p*=t;sum+=p;}return(sum);41return(sum);}⑶递归函数fact(intn){if(n<=1)return(1);elsereturn(n*fact(n-1));}3.
按增长率由小至大的顺序排列下列各函数:4.
有时为了比较两个同数量级算法的优劣,须突出主项的常数因子,而将降低次项用大"O"记号表示.
例如,设T1(n)=1.
39nlgn+100n+256=1.
39nlgn+O(n),T2(n)3/2lgnnnnn100n,nlgn,,2,n!
,n,n,(2/3),(3/2),24212=2.
0nlgn-2n=2.
0nlgn+O(n),这两个式子表示,当n足够大时T1(n)优于T2(n),因为前者的常数因子小于后者.
请用此方法表示下列函数,并指出当n足够大时,哪一个较优,哪一个较劣⑴T1(n)=5n2-3n+60lgn⑵T2(n)=3n2+1000n+3lgn⑶T3(n)=8n2+3lgn⑷T4(n)=1.
5n2+6000nlgn