国二复习必备数据结构.pptx

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,*,数据元素集合,元素间关系集合,数据结构（,data structure),数据元素和数据元素关系集合,Data_Structure=D,R,数据,逻辑结构,抽象反应数据元素,逻辑关系,从逻辑关系上描述数据，与数据存放无关,从详细问题抽象出来数据模型,；,与数据元素本身形式、内容无关,；,与数据元素相对位置无关,。,第1页,数据结构（,data structure),数据元素和数据元素关系集合,Data_Structure=D,R,数据,逻辑结构,抽象反应数据元素,逻辑关系,数据逻辑结构分为：,（集合）数据元素间除“同属于一个集合”外，无其它关系,线性结构,一个对一个，如线性表、栈、队列,树形结构,一个对多个，如树,图状结构,多个对多个，如图,第2页,数据,存放结构,（物理结构）数据逻辑结构在计算机,存放器中实现,存放结构分为：,次序,存放结构借助元素在存放器中,相对位置,来表示,数据元素间逻辑关系,链式,存放结构借助指示元素存放地址,指针,表示数据,元素间逻辑关系,第3页,时间复杂度,：,同一问题可用不一样算法处理，各种算法中，语句执行次数越多，则该算法花费时间越长。,一个算法中语句执行次数称为,语句频度,或,时间频度,，记为,T(n),。,T(n),=,语句执行次数,该语句执行时间,语句执行次数,该方法可独立于机器软件、硬件系统来分析算法在效率方面优劣,第4页,例 x=0;,y=0;,for(k=0;k 2*n;k+),x+;,for(i=0;i n;i+),for(j=0;j n;j+),y+;,1,1,2n,n,2,时间花费,T(n)=4+6n+2n,2,当n充分大时，T(n)与n,2,在数量级上相同，,记T(n)=,O,(n,2,),2n+1,n+1,n*(n+1),执行次数,第5页,时间复杂度,：算法耗用时间相对问题规模,n,增加率,，普通指,基本操作重复执行次数阶数,大,O,表示法：,T,(,n,)=O(,f,(,n,),加法规则与乘法规则,1、,O(,f(n),)+O(,g(n),)=maxO(,f(n),),O(,g(n),),2、,O(,f(,c,n),)=O(,f(n),),c,是正整数,3、,O(,f(n),)*O(,g(n),)=O(,f(n),*,g(n),),第6页,T1(n)=O(1),T2(n)=O(n),T3(n)=O(n,2,),T(n)=T1(n)+T2(n)+T3(n)=O(,max,(1,2n,n,2,)=O(n,2,),例 x=0;y=0;,for(k=0;k 2n;k+),x+;,for(i=0;i n;i+),for(j=0;j n;j+),y+;,频度最大,语句重复执行次数,阶数,第7页,例：n,n,矩阵相乘,for(i=1;i=n;i+),for(j=1;j=n;j+),cij=0;,for(k=1;k=n;k+),cij=cij+aik*bkj;,第8页,时间复杂度,：,基本操作重复执行次数阶数,（算法耗用时间增加率）,（渐近）空间复杂度,：,S(n)=O(f(n),辅助,存放空间增加率,或者说是算法所需存放空间量度,惯用时间复杂度：,O(1)-常量型,O(n)、O(n,2,)、O(n,3,)-多项式型,O(log,2,n)、O(nlog,2,n)-对数型,O(2,n,)、O(e,n,)-指数型,O(1),O(log,2,n),O(n),O(nlog,2,n),O(n,2,),O(n,3,),O(n,k,),O(2,n,),第9页,线性结构,特点,：在数据元素非空有限集中,存在,唯一,一个被称作“,第一个,”数据元素,存在,唯一,一个被称作“,最终一个,”数据元素,除第一个外，集合中每个数据元素均,只有一个前驱,除最终一个外，集合中每个数据元素均,只有一个后继,第10页,2.1 线性表,逻辑结构,定义：一个线性表是n,个数据元素有限序列,例 英文字母表（A,B,C,.Z),是一个线性表,例,数据元素,特征：,有限、序列、同构,元素个数n,表长度，,n=0,空表,1,i=stacksize,top,top,top,top,top,1,2,3,4,5,0,A,B,C,D,E,F,top,top,top,top,top,top,栈空,top,1,2,3,4,5,0,栈空,base,base,base,t,o,p,栈空,top=base,第24页,ABCDE,操作序列：,出栈序列：,元素A入栈,A,A,元素B入栈,B,B,元素C入栈,C,C,能否由入栈序列A、B、C、D、E,得到出栈序列CBDAE？,第25页,DE,操作序列：,出栈序列：,元素A入栈,A,元素B入栈,B,元素C入栈,元素C出栈,C,C,元素B出栈,B,能否由入栈序列A、B、C、D、E,得到出栈序列CBDAE？,第26页,DE,操作序列：,出栈序列：,元素A入栈,A,元素B入栈,元素C入栈,元素C出栈,C,元素B出栈,B,元素D入栈,D,D,元素D出栈,D,元素A出栈,A,能否由入栈序列A、B、C、D、E,得到出栈序列CBDAE？,第27页,E,操作序列：,出栈序列：,元素A入栈,元素B入栈,元素C入栈,元素C出栈,C,元素B出栈,B,元素D入栈,元素D出栈,D,元素A出栈,A元素E入栈,E,E,元素E出栈,E,能否由入栈序列A、B、C、D、E,得到出栈序列CBDAE？,能够得到,按1,2,3,4次序进栈，有几个出栈序列？,第28页,链栈,栈顶,.,top,data,link,栈底,typedef,struct Snode,SElemType data;,/数据域,struct Snode *link;,/指针域,LinkStack,;,链栈操作是线性表特例，比较易于实现,链栈结点结构,data link,第29页,队列定义及特点,定义：队列是限定只能在表一端进行插入，在表另一端进行删除线性表,a1 a2 a3.an,入队,出队,front,rear,队列,Q=(a1,a2,an),队列,逻辑结构,队尾(,rear,)允许插入一端,队头(,front,)允许删除一端,队列特点：先进先出(,FIFO,),第30页,a,1,a,2,a,n,a,i,a,1,a,2,a,i,a,n,队头,front,队尾,rear,出队,入队,front,队头,队尾,设队首、队尾指针,front,和,rear,front,指向头结点，,rear,指向队尾,rear,链队列,队列,链式存放结构,front,rear,第31页,Q.,rear,1,2,3,4,5,0,Q.,front,入队,J1,溢出,J2,J3,J4,J5,J6,Q.,rear,Q.,rear,Q.,rear,Q.,rear,Q.,rear,Q.,rear,真,队列,次序存放结构,SqQueue,Q;,#define,MAXQSIZE 100,/,最大队列长度,typedef,struct,QElemType *,base,;,/存放空间基址,int,front,;,/头指针，指向队头元素,int,rear,;,/尾指针，指向队尾元素,下一个位置,SqQueue,;,次序队列存放结构,初值：,Q.,front,=Q,.rear,=0;,队空：,Q.,front,=Q.,rear,;,入队：,真,溢出,条件：,Q.,base,Q.,rear,+=,e,;,Q.,front,=0;,Q.,rear,=MAXQSIZE;,第32页,SqQueue,Q;,#define,MAXQSIZE 100,/,最大队列长度,typedef,struct,QElemType *,base,;,/存放空间基址,int,front,;,/头指针，指向队头元素,int,rear,;,/尾指针，指向队尾元素,下一个位置,SqQueue,;,次序队列存放结构,出队：,假,溢出,条件：,e,=Q.,base,Q.,front,+;,1,2,3,4,5,0,Q.,front,出队,J1,J2,J3,J4,J5,J6,Q.,rear,Q.,front,Q.,front,Q.,front,溢出,假,队列,次序存放结构,Q.,front,0;,Q.,rear,=MAXQSIZE;,第33页,方案一,：,队首固定,，每次出队，剩下元素,下移,1,2,3,4,5,0,Q.,front,J1,出队,J1,J2,J3,J4,Q.,rear,真,溢出,条件,：,Q.,front,=0;,Q.,rear,=MAXQSIZE;,假,溢出,条件,：,Q.,front,0;,Q.,rear,=MAXQSIZE;,队列,次序存放结构,假溢出,问题处理方案,Q.,rear,第34页,1,2,3,4,5,0,Q.,front,J2,出队,J2,J3,J4,Q.,rear,Q.,rear,缺点：浪费时间,方案一,：,队首固定,，每次出队，剩下元素,下移,队列,次序存放结构,假溢出,问题处理方案,真,溢出,条件,：,Q.,front,=0;,Q.,rear,=MAXQSIZE;,假,溢出,条件,：,Q.,front,0;,Q.,rear,=MAXQSIZE;,第35页,J4,J5,J6,1,2,3,4,5,0,Q.,front,Q.,rear,方案二：,循环队列,，把队列,构想成,环形,，首尾相接,若Q.,rear,=,MAXSIZE,，则令Q.,rear,=0,J4,J5,J6,4,5,0,1,2,3,Q.rear,Q.front,实现,：,利用,模,运算,队列,次序存放结构,假溢出,问题处理方案,真,溢出,条件,：,Q.,front,=0;,Q.,rear,=MAXQSIZE;,假,溢出,条件,：,Q.,front,0;,Q.,rear,=MAXQSIZE;,第36页,J4,J5,J6,1,2,3,4,5,0,Q.,front,Q.,rear,方案二：,循环队列,，把队列,构想成,环形,，首尾相接，,若Q.,rear,=,MAXSIZE,，则令Q.,rear,=0,J4,J5,J6,4,5,0,1,2,3,Q.rear,Q.front,实现,：,利用,模,运算,队列,次序存放结构,假溢出,问题处理方案,“模”,运算,x%,MAXSIZE,结果范围为0(,MAXSIZE-1,),则，(,x+1)%,MAXSIZE,可实现,x,加1,满足范围要求,第37页,利用,模,运算实现循环队列,J8,J9,Q.rear,Q.front,J7,Q.rear,J4,J5,J6,4,5,0,1,2,3,Q.rear,初始状态,J7,J8,J9相继入队,Q.front,J4,J5,J6,4,5,0,1,2,3,Q.rear,循环,队列入,队,：,队满,队列,次序存放结构,循环队列,Q,.,base,Q,.,rear,=,e,;,Q,.,rear,=(,Q,.,rear,+1),%,MAXQSIZE,;,Q.rear,第38页,利用,模,运算实现循环队列,J8,J9,Q.front,J7,J4,J5,J6,4,5,0,1,2,3,初始状态,J7,J8,J9相继入队,Q.front,J4,J5,J6,4,5,0,1,2,3,Q.rear,Q.rear,队满,J4,J5,J6相继出队,Q.front,J4,J5,J6,4,5,0,1,2,3,Q.rear,Q.front,Q.front,Q.front,队空,循环,队列,出队,：,队列,次序存放结构,循环队列,e,=,Q,.,base,Q,.,front,;,Q,.,front,=(,Q,.,front,+1),%,MAXQSIZE,;,第39页,利用,模,运算实现循环队列,J8,J9,Q.front,J7,J4,J5,J6,4,5,0,1,2,3,初始状态,J7,J8J9相继入队,Q.front,J4,J5,J6,4,5,0,1,2,3,Q.rear,Q.rear,队满,J4,J5,J6相继出队,4,5,0,1,2,3,Q.rear,Q.front,队空,队列,次序存放结构,循环队列,循环,队列,中,：,队空,条件：,Q,.,front,=,Q,.,rear,队满,条件：,Q,.,front,=,Q,.,rear,?,处理方案：,1.,设一个标志,区分队空、队满,2.,少用一个元素空间,：,第40页,利用,模,运算实现循环队列,J8,Q.front,J7,J4,J5,J6,4,5,0,1,2,3,初始状态,J7,J8,J9相继入队,Q.front,J4,J5,J6,4,5,0,1,2,3,Q.rear,Q.rear,队满,J4,J5,J6相继出队,4,5,0,1,2,3,Q.rear,Q.front,队空,队列,次序存放结构,循环队列,处理方案：,1.,设一个标志,区分队空、队满,2.,少用一个元素空间,：,队空,：,Q,.,front,=,Q,.,rear,队满,：(,Q,.,rear,+1)%,MAXQSIZE,=,Q,.,front,第41页,五子棋游戏,.,.,.,.,.,.,树实例,第42页,树,是一类主要,非线性,数据结构，是以,分支,关系定义,层次,结构,定义：树(,tree,)是,n(n=0),个结点有限集,T,，,其中：,有且仅有一个特定结点，称为树,根,(,root,),当,n1,时，其余结点可分为,m(m0),个,互不相交,有限集,T1,T2,Tm,，,其中每一个集合本身又是一棵树，称为根,子树,(,subtree,),特点：,非空树中存在唯一一个称为,根,结点,非空树中各子树是,互不相交,集合,树定义,第43页,A,只有根结点树,A,B,C,D,E,F,G,H,I,J,K,L,M,有子树树,根,子树,第44页,结点,(,node,)表示树中元素，包含数据项及若干指向其子树分支,结点度,(,degree,)结点拥有子树数,叶子,(,leaf,)度为0结点,孩子,(,child,)结点子树根称为该结点孩子,双亲parents,)孩子结点上层结点叫该结点,弟兄,(,sibling,)同一双亲孩子,树度,一棵树中最大结点度数,结点层次,(,level,)从根结点算起，根为第一层，它孩子为第二层,深度,(,depth,)树中结点最大层次数,森林,(,forest,)m(m,0),棵互不相交树集合,树基本术语,第45页,结点,A,度：,结点,B,度：,结点,M,度,：,叶子：,结点,A,孩子：,结点,B,孩子：,结点,I,双亲：,结点,L,双亲,：,结点,B，C，D,为,结点,K，L,为,树度：,结点,A,层次：,结点,M,层次,：,树深度：,结点,F，G,为,结点,A,是结点,F，G,3,2,0,BC,D,E,F,3,1,4,4,K,L,F,G,M,I,J,D,E,弟兄,弟兄,堂弟兄,祖先,A,B,C,D,E,F,G,H,I,J,K,L,M,树基本术语,第46页,定义：二叉树是,n(n,0),个结点有限集，它或为空树,(,n=0),，,或由一个根结点和两棵分别称为,左子树,和,右子树,互不相交二叉树组成,特点,每个结点,至多,有二棵子树(即不存在度大于,2,结点),二叉树子树有,左、右之分,，且其次序不能任意颠倒,基本形态,二叉树定义,空二叉树,左、右子树均非空,D,R,L,只有根结点二叉树,D,右子树为空,D,L,左子树为空,D,R,第47页,二叉树性质,性质,1,：,在二叉树第,i层上至多有,2,i-1,个结点(i1),用归纳法证实,：,归纳基,：,归纳假设：,归纳证实：,i,=,1,层时，只有一个根结点：,2,i-1,=,2,0,=,1,；,假设对全部,j,，,1,j,i,，,命题成立，即第,j,层上至多有,2,j-1,个结点，则第,i,-,1,层上至多有,2,i-1,个结点,；,因为二叉树上每个结点至多有两棵子树，,则第,i,层结点数=,2,i-2,2,=,2,i-1,。,第48页,证实：,由性质1，可得深度为k,二叉树最大结点数是,等比数列求和：,二叉树性质,性质2：,深度为,k,二叉树上至多含,2,k,-1,个结点（k1）,第49页,性质3：,对任何一棵二叉树T,，,假如其叶子结点数为,n,0,，,度为,2,结点数为,n,2,，,则,n,0,=n,2,+1,证实：设,n1,为二叉树,T,中度为,1,结点数,因为：二叉树中全部结点度均小于或等于,2,所以：其结点总数,n=n0+n1+n2,又二叉树中，除根结点外，其余结点都只有一个,分支进入,设,B,为分支总数，则,n=B+1,又：分支由度为,1,和度为,2,结点射出，,B=n1+2*n2,于是，,n=B+1=n1+2*n2+1=n0+n1+n2,n0=n2+1,二叉树性质,第50页,满二叉树,定义：,特点：每一层上结点数都是最大结点数,，除最下层叶子结点外，每个结点度都为,2,。,1,2,3,114,5,8,9,12,13,6,7,10,14,15,满二叉树及其编号,特殊形式二叉树,第51页,完全二叉树,定义：深度为,k,，,有,n,个结点二叉树当且仅当其每一个结点都与深度为,k,满二叉树中编号从,1,至,n,结点一一对应时，称为,1,2,3,11,4,5,8,9,12,6,7,10,完全二叉树及其编号示例,特点,度小于,2,结点只可能在,层次最大两层,上,出现,，假如某个结点没有左孩子，那么它一定没有右孩子，该结点为叶子结点,除最终一层外，每层都充满了结点，最下面一层结点都集中在该层,最左边,特殊形式二叉树,第52页,1,2,3,11,4,5,8,9,12,13,6,7,10,1415,1,2,3,11,4,5,8,9,12,6,7,10,1,2,3,4,5,6,7,1,2,3,4,5,6,第53页,性质,4：,证实：设深度为k，依据二叉树性质2知：,2,k-1,-1 n,2,k,-1,2,k-1,n 2,k,，,于是有：,完全二叉树性质,含有,n,个结点完全二叉树,深度,为,log,2,n,+1,1,2,3,11,4,5,8,9,12,6,7,10,完全二叉树及其编号示例,第54页,性质,5：,完全二叉树性质,1,2,3,11,4,5,8,9,12,6,7,10,假如对一棵有,n,个结点完全二叉树结点按层序编号，则对任一结点,i(1,in),，,有：,(1)假如,i1,，,则结点,i,是二叉树根，无双亲；假如,i1,，,则其双亲是,i/2,(2),假如,2,in,，,则结点,i,无左孩子；假如,2,in,，,则其左,孩子是,2,i,(3),假如,2,i+1n,，,则结点,i,无右孩子；假如,2,i+1n,，,则其右孩子是,2,i+1,第55页,性质,5：,完全二叉树性质,假如对一棵有,n,个结点完全二叉树结点按层序编号，则对任一结点,i(1,in),，,有：,(1)假如,i=1,，,则结点,i,是二叉树根，无双亲；假如,i1,，,则其双亲是,i/2,(2),假如,2,in,，,则结点,i,无左孩子；假如,2,in,，,则其左,孩子是,2,i,(3),假如,2,i+1n,，,则结点,i,无右孩子；假如,2,i+1n,，,则其右孩子是,2,i+1,i/2,i,i+1,2i,2i+1,2i+2,完全二叉树中结点i与双亲和左、右孩子关系,二叉树次序存放,第56页,祝大家顺利经过2级,谢谢!,第57页,