数据结构 笔记

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,2011-5-30,#,1.4,数据类型和抽象数据类型,抽象数据类型三元组的定义：,ADT Triplet,数据对象,:D=e1,e2,e3|e1,e2,e3,ElemSet,数据关系,:R1=,InitTriplet(&T,v1,v2,v3),操作结果：构造了三元组,T,，元素,e1,e2,e3,分别被赋以参数,v1,v2,v3,Get(T,i,&e),初始条件：三元组,T,已存在，,1i3,操作结果：用,e,返回三元组,T,的第,i,个元素,Min(T,&e),初始条件：三元组,T,已存在,操作结果：用,e,返回,T,的三个元素中的最小值,ADT Triplet,1.5.2,算法的描述,1.,预定义常量和类型,常量说明采用,C+,语言的规范。,/,函数结果主要状态,constTRUE=1;,constFALSE=0;,constOK=1;,constERROR=0;,constINFEASIBLE=1;,constOVERFLOW=-2;,/status,是函数的返回值类型，其值是函数结果状态码,typedef int status;,/,布尔型类型,enum bool TRUE,FALSE,1.5.2,算法的描述,一般而言：,a,、,b,、,c,、,d,等用作,数据元素名称,。,i,、,j,、,k,、,l,、,m,、,n,等用作,整型变量名,。,p,、,q,、,r,等用作,指针变量名,。,通常每个操作函数均返回一个状态码，此时函数类型定义为,status,类型,参数表中某个参数允许预先用表达式的形式赋值，作为默认值使用，可以简化参数表，例如：,函数类型 函数名（类型,1,参数,1,，类型,2,参数,2=,算术表达式）,调用时可以是：,函数名（实参数,1,）,;/,实参数,2,使用默认值。,或,函数名（实参数,1,，实参数,2,）,;/,实参数,2,不使用默认值。,1.5.2,算法的描述,4.,内存的动态分配与释放,操作符,new,C+,操作符,new,可用来动态存储分配，该操作符返回一个指向所分配空间的指针。,例如：下面语句为一个整数动态分配存储空间,int*y;/,宣告指针,y=,new,int;/,分配存储空间,*,y=10;/,赋值,我们可以将上面三步适当合并,int*y=,new,int;*y=10;,或,int*y;y=,new,int(10);,或,int*y=,new,int(10);,操作符,delete,动态分配的存储空间不再需要时应该被释放，所释放的空间可重新用来动态创建新的结构。我们可以使用,C+,操作符,delete,来释放由操作符,new,所分配的空间。,delete y;/,释放分配给*,y,的空间,1.5.2,算法的描述,5.,赋值语句,简单赋值,:,变量名,=,表达式,;,条件赋值,:,变量名,=,条件表达式,?,表达式,T,:,表达式,F,;,串联赋值,:,变量名,1,=,变量名,2,=,=,变量名,k,=,表达式,；,成组赋值,:,(,变量名,1,变量名,2,变量名,k,)=(,表达式,1,表达式,2,表达式,k,);,结构名,=,结构名,;,结构名,=,值,1,值,2,值,k,;,变量名,=,表达式,;,变量名,起始下标,.,终止下标,=,变量名,起始下标,.,终止下标,;,1.5.2,算法的描述,6.,选择语句,条件语句,1:,if(,条件表达式,),语句,;,条件语句,2:,if(,条件表达式,),语句,;,else,语句,;,开关语句,1:,switch(,表达式,),case,值,1,:,语句,1,;break;,case,值,n,:,语句,n,;break;,default:,语句,n+1,;,开关语句,2:,switch,case,条件,1,:,语句,1,;break;,case,条件,n,:,语句,n,;break;,default:,语句,n+1,;,1.5.2,算法的描述,7.,循环语句,for,语句,:,for(,赋初值表达式序列,;,条件表达式,;,修改表达式序列,),语句,;,while,语句,:,while(,条件表达式,),语句,;,do-while,语句,:,do,语句序列,;,while(,条件表达式,);,8.,结束语句,函数结束语句,:,return,(,表达式,);,return;,case,结束语句,:,break;,1.5.2,算法的描述,9.,输入输出语句使用流式输入输出的形式,输入语句,:,cin,变量,1,变量,2,变量,n,;,输入语句,:,cout,变量,1,变量,2,0,则,f(n)=O(n,m,),证明,:f(n),i=0,m,|a,i,|n,i,n,m,0,m,|a,i,|n,i-m,n,m,0,m,|a,i,|,附录,3,：,渐进式表示方法,定理,2,大,O,比率定理,:,对于函数,f(n),和,g(n),若,lim,n,f(n)/g(n),存在,则,f(n)=O(g(n),当且仅当存在确定的常数,c,有,lim,n,f(n)/g(n)c,证明,:,如果,f(n)=O(g(n),则存在,c0,及某个,n,0,使得对所有的,nn,0,有,f(n)/g(n)c,因此,lim,n,f(n)/g(n)c,。接下来假定,lim,n,f(n)/g(n)c,它表明存在一个,n,0,，使得对所有的,nn,0,有,f(n)max1,c*g(n),。,附录,3,：,渐进式表示方法,3.,符号,(,渐进紧密下限,),符号，用来估算函数,f,的下限值,定义,:,符号,f(n)=,(g(n),当且仅当存在正的常数,c,和,n,0,使得对所有的,nn,0,有,f(n)cg(n),定理,1:,如果,f(n)=a,m,n,m,+a,1,n+a,0,且,a,m,0,则,f(n)=,(n,m,),定理,2,比率定理,:,对于函数,f(n),和,g(n),若,lim,n,g(n)/f(n),存在,则,f(n)=,(g(n),对于确定的常数,c,有,lim,n,g(n)/f(n)c,附录,3,：,渐进式表示方法,4.,符号,(,渐进紧密限度,),符号适用于同一个函数既可作为函数,f,的上限也可以作为,f,的下限的情形,定义,:,符号,f(n)=,(g(n),当且仅当存在正的常数,c,1,，,c,2,和某个,n,0,使得对所有的,nn,0,有,c,2,g(n)f(n)c,1,g(n),定理,1:,如果,f(n)=a,m,n,m,+a,1,n+a,0,且,a,m,0,则,f(n)=,(n,m,),定理,2,比率定理,:,对于函数,f(n),和,g(n),若,lim,n,f(n)/g(n),及,lim,n,g(n)/f(n),存在,f(n)=,(g(n),当且仅当对于确定的常数,c,有,lim,n,g(n)/f(n)c,及,lim,n,f(n)/g(n)c,附录,3,：,渐进式表示方法,5.,关于渐进符号的其它定理,定理：对于,任一个实数,x0,和任一个实数,0,下面的结论都是正确的：,1),存在某个,n,0,使得对于任何,nn,0,有,(logn),x,(logn),x+,。,2),存在某个,n,0,使得对于任何,nn,0,有,(logn),x,n,3),存在某个,n,0,使得对于任何,nn,0,有,n,x,n,x+,。,4),对于任意实数,y,，存在某个,n,0,使得对于任何,nn,0,有,n,x,(logn),y,n,x+,。,5),存在某个,n,0,使得对于任何,nn,0,有,n,x,1),E7:n!,E8:,n,i=1,1/i,是,O,、,、,之一,(1),(n,k,),(n,2,),(n,3,),(n,k+1,),(r,n,),(n/e),n,),(log n),