数据结构知识点总结,有工大老师多年经验编写（课堂PPT）

计算机系列课程之间的联系,1,数据结构涵盖的内容,2,二.基本概念和术语,1.数据数据是用于描述客观事物的数值、字符，以及一切可以输入到计算机中的并由计算机程序加以处理的符号的集合。其范围随着计算机技术的发展而不断发展。2.数据元素数据的基本单位是数据元素，在计算机程序中通常作为一个整体进行考虑和处理。3.数据项是数据的不可分割的最小单位，一个数据元素可由若干个数据项组成。4.数据对象性质相同的元素的集合叫做数据对象。,3,5.结点数据元素在机内的位串表示，即数据元素在计算机内的映象。6.域/字段当数据元素由若干个数据项组成时，位串中对应于各个数据项的子串称为域/字段，是数据元素中数据项在计算机中的映象。7.信息表计算机程序所作用的一组数据通常称为信息表，是数据对象在计算机中的映象。,4,8.数据结构数据结构指的是数据元素之间的相互关系，这种关系是抽象的，即并不涉及数据元素的具体内容。是数据元素及其相互间的关系的数学描述。9.逻辑结构和存储结构(1)逻辑结构数据结构中描述的是数据元素之间的抽象关系(逻辑关系)，称为逻辑结构。(2)存储结构/物理结构数据结构在计算机中的表示（映象）称为存储结构/物理结构。,1.1.1基本概念和术语,5,(3)数据元素之间的关系（逻辑结构）在计算机中有两种表示方法：顺序映象(表示)和非顺序映象(表示)，从而导致两种不同的存储结构：顺序结构和链式结构。顺序映象（表示）的特点是借助数据元素在存储器中的相对位置来表示数据元素之间的逻辑关系。非顺序映象（表示）的特点是借助指示数据元素存储地址的指针来表示数据元素之间的逻辑关系。,1.1.1基本概念和术语,返回,6,1.1.2四种基本的数据结构,1.集合结构,结构中的数据元素之间除了“属于同一个集合”的关系之外，别无其他关系。关系比较松散，可用其他结构来表示。,结构中的数据元素之间存在一个对一个的关系，即线性关系，每个元素至多有一个直接前导和后继。,2.线性结构,7,3.树型结构,结构中的数据元素之间存在一个对多个的关系，即层次关系，即每一层上的元素可能与下层的多个元素相关，而至多与上层的一个元素相关。,结构中的数据元素之间存在多个对多个的关系，即任意关系，任何元素之间都可能有关系。,4.网状/图型结构,返回,8,1.1.3数据结构的研究对象,数据结构的研究对象(研究内容),1.数据对象的结构形式,各种数据结构的性质(逻辑结构);2.数据对象和”关系”在计算机中的表示(物理结构/存储结构);3.数据结构上定义的基本操作(算法);4.算法的效率;5.数据结构的应用,如数据分类,检索.,返回,9,数据结构的作用图,数据结构,数据关系,数据表示,数据类型,数学离散数学应用数学,硬件存储设备总体结构,软件系统软件应用软件,算法设计数据运算,编码理论数据组合,系统设计数据存取,10,2.1算法及其性能评价准则,算法（Algorithm）：是对特定问题求解步骤的一种描述，它是指令（规则）的有限序列，其中每一条指令表示一个或多个操作。,算法的特征：有穷性、确定性、能行性、输入、输出,算法描述：自然语言；程序设计语言；类语言*；,一、算法、算法的特征和算法描述,常用的算法设计方法：递归法（Recursion）、分治法(Divide-andConquer)、贪心法(Greedy)、动态规划(DynamicProgramming)、搜索与遍历、回溯（Backtracking）、解空间局部搜索近似算法(Approximation)、在线算法（On-Line）等,11,2.2算法时间复杂性分析方法,定理2.1若A（n）=amnm+a1n+a0是关于n的m次多项式，则A（n）=（nm）*此定理说明，时间复杂性仅取决于多项式的最高次幂，而与最高次幂的系数和其他低次项无关（1）表示实践复杂性为常数常见的时间复杂性及其比较（1）（n）（n）（n）（nn）（n2）（n3）=(y+1)(y+1)y=y+1;时间复杂性为O（,s=0;f(n)=1;T2(n)=O(f(n)=O(1)常量阶,）,13,for(i=1;i=n;+i)for(j=1;j=n;+j)+x;s+=x;f(n)=3n2+2n+1;T3(n)=O(f(n)=O(n2)平方阶,for(i=1;i=n;+i)for(j=1;j=n;+j)cij=0;for(k=1;k=n;+k)cij+=aik*bkj;f(n)=2n3+3n2+2n+1;T4(n)=O(f(n)=O(n3)立方阶,for(i=1;i=n;+i)+x;s+=x;f(n)=3n+1;T1(n)=O(f(n)=O(n)线形阶,14,第三章线性表（LinerList）,15,知识点：线性表的逻辑结构和各种存储表示方法定义在逻辑结构上的各种基本运算（操作）在各种存储结构上如何实现这些基本运算各种基本运算的时间复杂性,重点：熟练掌握顺序表和单链表上实现的各种算法及相关的时间复杂性分析,难点：使用本章所学的基本知识设计有效算法解决与线性表相关的应用问题,16,3.1抽象数据型线性表,定义线性表是由n(n0)个相同类型的元素组成的有序集合。记为：(a1,a2,a3,ai-1,ai,ai+1,an),其中：n为线性表中元素个数，称为线性表的长度；当n=0时，为空表，记为（）。ai为线性表中的元素，类型定义为elementtypea1为表中第1个元素，无前驱元素；an为表中最后一个元素，无后继元素；对于ai-1,ai,ai+1(1in)，称ai-1为ai的直接前驱，ai+1为ai的直接后继。(位置概念！）线性表是有限的，也是有序的。,17,3.1抽象数据型线性表,线性表LIST=(D,R)D=ai|aiElementset,i=1,2,n,n0R=HH=|ai-1,aiD,i=2,n,操作：设L的型为LIST线性表实例，x的型为elementtype的元素实例，p为位置变量。所有操作描述为：Insert(x,p,L)Locate(x,L)Retrieve(p,L)Delete(p,L)Previous(p,L),Next(p,L)MakeNull(L)First(L)End(L),数学模型,18,3.1抽象数据型线性表,举例：设计函数Deleval（LIST,19,3.2线性表的实现,问题：确定数据结构（存储结构）实现型LIST，并在此基础上实现各个基本操作。,存储结构的三种方式：连续的存储空间（数组）静态存储非连续存储空间指针（链表）动态存储游标（连续存储空间+动态管理思想）静态链表,3.2.1指针和游标,指针：地址量，其值为另一存储空间的地址；游标：整型指示量，其值为数组的下标，用以表示指定元素的“地址”或“位置”（所在的数组下标）,20,3.2.2线性表的数组实现,顺序表：把线性表的元素逻辑顺序依次存放在数组的连续单元内，再用一个整型量表示最后一个元素所在单元的下标。,特点：元素之间的逻辑关系（相继/相邻关系）用物理上的相邻关系来表示（用物理上的连续性刻画逻辑上的相继性）；是一种随机存储结构，也就是可以随机存取表中的任意元素，其存储位置可由一个简单直观的公式来表示。,21,3.2.2线性表的数组实现,类型定义：#definemaxlength100structLISTelementtypeelementsmaxlength;intlast;位置类型：typedefintposition;线性表L:LISTL;表示：L.elementsp/L的第p个元素L.lastL的长度，最后元素的位置,22,3.2.2线性表的数组实现,操作：,voidInsert(elementtypex,positionp,LIST/时间复杂性：O(n),23,positionLocate(elementtypex,LISTL)positionq;for(q=1;qL.last)error(“指定元素不存在”);elsereturn(L.elementsp);/时间复杂性：O(1),24,voidDelete(positionp,LIST/时间复杂性：O(n),3.2.2线性表的数组实现,positionPrevious(positionp,LISTL)if(pL.last)error(“前驱元素不存在”);elsereturn(p1);/时间复杂性：O(1),25,positionEnd(LISTL)return(L.last+1);/O(1),positionFirst(LISTL)return(1);/复杂性：O(1),positionNext(positionp,LISTL)if(p=L.last)error(“前驱元素不存在”);elsereturn(p+1);/时间复杂性：O(1),positionMakeNull(LIST/时间复杂性：O(1),3.2.2线性表的数组实现,26,3.2.3线性表的指针实现,单链表：一个线性表由若干个结点组成，每个结点均含有两个域：存放元素的信息域和存放其后继结点的指针域，这样就形成一个单向链接式存储结构，简称单向链表或单向线性链表。,结构特点：逻辑次序和物理次序不一定相同；元素之间的逻辑关系用指针表示；需要额外空间存储元素之间的关系；非随机存储结构,27,3.2.3线性表的指针实现,28,操作讨论：,3.2.3线性表的指针实现,插入元素:,p,(a)表头插入元素,(b)中间插入元素,(c)表尾插入元素,q=newcelltype;qelement=x;qnext=pnext;pnext=q;,或:temp=pnext;pnext=newcelltype;pnextelement=x;pnextnext=temp;,讨论表头结点的作用,29,操作讨论：,3.2.3线性表的指针实现,删除元素:,q=pnext;pnext=qnext;deleteq;,或：q=pnext;pnext=pnextnext;deleteq;,讨论结点ai的位置p,30,操作：,3.2.3线性表的指针实现,positionEnd(LISTL)positionq;q=L;while(qnext!=NULL)q=qnext;return(q);/时间复杂性：O(n),voidInsert(elementtypex,positionp)positionq;q=newcelltype;qelement=x;qnext=pnext;pnext=q;/时间复杂性：O(1),31,操作：,3.2.3线性表的指针实现,positionLocate(elementtypex,LISTL)positionp;p=L;while(pnext!=NULL)if(pnextelement=x)returnp;elsep=pnext;returnp;/时间复杂性：O(n),elementtypeRetrieve(positionp)return(pnextelement);/时间复杂性：O(1),32,操作：,3.2.3线性表的指针实现,voidDelete(positionp)positionq;if(pnext!=NULL)q=pnext;pnext=qnext;deleteq;/时间复杂性：O(1),positionPrevious(positionp)positionq;if(p=Lnext)error(“不存在前驱元素”)；elseq=L;while(qnext!=p)q=qnext;returnq;/时间复杂性：O(n),33,操作：,3.2.3线性表的指针实现,positionNext(positionp)positionq;if(pnext=NULL)error(“不存在后继元素”)；elseq=pnext;returnq;/时间复杂性：O(1),positionMakeNull(LIST/时间复杂性：O(1),34,操作：,3.2.3线性表的指针实现,positionFirst(LISTL)returnL;/时间复杂性：O(1),静态链表与动态链表的比较,比较参数表的容量存取操作时间空间,链式存储灵活，易扩充顺序存取访问元素费时间实际长度，节省空间,顺序存储固定，不易扩充随机存取插入删除费时间估算表长度，浪费空间,举例：遍历线性链表，按照线性表中元素的顺序，依次访问表中的每一个元素，每个元素只能被访问一次。,voidTravel(LISTL)positionp;p=Lnext;while(p!=NULL)coutnext;q=p-next;L-next-next=NULL;while(p!=null)p-next=L-next;L-next=p;p=q;q=q-next;,方法二:线性表由q来表示p=null;w=q;while(w!=null)w=w-next;q-next=p;p=q;q=w;,36,3.2.5双向链表,双向连表：在单向链表中，对每个结点增加一个域，用一指向该结点的前驱结点。线性表的这种存储结构称为双向链表。,优点：实现双向查找（单链表不易做到）表中的位置i可以用指示含有第i个结点的指针表示。缺点：空间开销大。,37,3.2.5双向链表,操作：,删除位置p的元素：voidDelete(positionp,DLIST,voidInsert(elementtypex,positionp,DLIST,38,3.2.6环形链表,对线性链表的改进，解决“单向操作”的问题；改进后的链表，能够从任意位置元素开始，访问表中的每一个元素。,单向环形链表：在(不带表头结点)的单向链表中，使末尾结点的指针域指向头结点，得到一个环形结构；用指向末尾结点的指针标识这个表。,存储结构:与单向链表相同(略）,39,操作：在表左端插入结点Insert(x,FIRST(R),R);LInsert(x,R)voidLInsert(elementtypex,LIST,3.2.6环形链表,在表右端插入结点Insert(x,END(R),R);RInsert(x,R)voidRInsert(elementtypex,LISTR)LInsert(x,R);R=Rnext;,40,操作：从表左端删除结点Delete(First(R),R);LDelete(R)voidLDelete(LIST,3.2.6环形链表,41,3.2.6环形链表,双向环形链表的结构与双向连表结构相同，只是将表头元素的空previous域指向表尾，同时将表尾的空next域指向表头结点，从而形成向前和向后的两个环形链表，对链表的操作变得更加灵活。,举例：设计算法，将一个单向环形链表反向。头元素变成尾元素，尾元素变成新的头元素，依次类推。,42,3.2.6环形链表,43,3.3栈（Stack）,栈是线性表的一种特殊形式，是一种限定性数据结构，也就是在对线性表的操作加以限制后，形成的一种新的数据结构。,定义：是限定只在表尾进行插入和删除操作的线性表。栈又称为后进先出(LastInFirstOut)的线性表。简称LIFO结构。,栈举例,44,3.3栈,栈的基本MakeNull(S)操作Top(S)Pop(S)Push(x,S)Empty(S),举例：利用栈实现行编辑处理。设定符号“#”为擦讫符，用以删除“#”前的字符；符号“”为删行符，用以删除当前编辑行。原理：一般字符进栈；读字符擦讫符退栈；删行符则清栈,45,3.3.1栈的实现,3.3栈,1、顺序存储,顺序栈示意图,top,类型定义：enumBoolenTRUE,FALSEtypedefstructelementtypeelementsmaxlength;inttop;STACK;STACKS;,栈的容量：maxlength1;栈空：S.top=0;栈满：S.top=maxlength1;栈顶元素：S.elementsS.top;,46,3.3.1栈的实现,1、顺序存储,操作：,voidMakeNull(STACK,BooleanEmpty(STACKS)if(S.topnext)returnFALSE;elsereturnTRUE;,多个栈共用一个存储空间的讨论,52,3.4排队或队列（Queue）,队列是对线性表的插入和删除操作加以限定的另一种限定性数据结构。定义将线性表的插入和删除操作分别限制在表的两端进行，和栈相反，队列是一种先进先出（FirstInFirstOut，简称FIFO结构）的线性表。,操作：MakeNull(Q)、Front(Q)、EnQueue(x,Q)、DeQueue(Q)、Empty(Q),53,3.4队列（Queue）,3.4.1队列的指针实现,元素的“型”：structcelltypeelementtypeelement；celltype*next；,队列的“型”：structQUEUEcelltype*front；celltype*rear；;,54,3.4.1队列的指针实现,操作：voidMakeNull(QUEUE,BooleanEmpty(Q)QUEUE,elementtypeFront(Q)QUEUEQ;returnQ.frontnextelement;,55,3.4.1队列的指针实现,voidEnQueue(elementtypex,QUEUE,voidDelete(QUEUE,56,3.4.2队列的数组实现,队列的“型”：structQUEUEelementtypeelementmaxlength;intfront；intrear；;,随着不断有元素出队和进队（插入和删除），队列的状态由1变成2；此时an占据队列的最后一个位置；第n+1个元素无法进队,但实际上，前面部分位置空闲。,57,3.4.2队列的数组实现,解决假溢出的方法有多种；一是通过不断移动元素位置，每当有元素出队列时，后面的元素前移一个位置，使队头元素始终占据队列的第一个位置。第二种方法是采用循环队列。,插入元素：Q.rear=(Q.rear+1）%maxlength删除元素：Q.front=(Q.front+1）%maxlength,队空：(Q.rear+1）%maxlength=Q.front队满：(Q.rear+1)%maxlength=Q.front,?,58,3.4.2队列的数组实现,问题：如何解决循环队列中队空与队满状态相同？,方法一：约定队列头指针在队列尾指针的下一位置上；方法二：另设一个标志位用以区别队空与队满两种状态；,结论：两种方法的代价是相同的。,操作：intaddone(inti)return(i+1）%maxlength);voidMakeNull(QUEUE,booleanEmpty(Q)QUEUEQ;if(addone(Q.rear)=Q.front)returnTRUE;elsereturnFALSE;,59,3.4.2队列的数组实现,操作：elementtypeFront(QUEUEQ)if(Empty(Q)returnNULL;elsereturn(Q.elementsQ.front);voidEnQueue(elementtypex,QUEUEQ)if(addone(addone(Q.rear)=Q.front)error(“队列满”);elseQ.rear=addone(Q.rear);Q.elementsQ.rear=x;,60,3.4.2队列的数组实现,voidDeQueue(QUEUEQ);if(Empty(Q)error(“空队列”);elseQ.front=addone(Q.front);,61,3.6串(String),串是线性表的一种特殊形式，表中每个元素的类型为字符型，是一个有限的字符序列。串的基本形式可表示成：S=a1a2a3an；其中：charai；0in；n0；当n=0时，为空串。n为串的长度；,C语言中串有两种实现方法：1、字符数组，如：charstr110；2、字符指针，如：char*str2；,3.6.1抽象数据型串,62,3.6.2串的实现,1、串的顺序存储采用连续的存储空间（数组），自第一个元素开始，依次存储字符串中的每一个字符。charstr10=“China”；,操作：NULL，ISNULL，IN，LEN，CONCAT，SUBSTR，INDEX,2、串的链式存储构造线性链表，element类型为char，自第一个元素开始，依次存储字符串中的每一个字符。,63,3.7数组(ARRAY),3.7.1抽象数据型数组,数组是由下标（index）和值（value）组成的序对（index，value）的集合。也可以定义为是由相同类型的数据元素组成有限序列。数组在内存中是采用一组连续的地址空间存储的，正是由于此种原因，才可以实现下标运算。所有数组都是一个一维向量。,数组1：(a1,a2,a3,ai,an);,数组2：(a11,a1n,a21,a2n,aij,am1,amn);1im,1jn;,数组3:(a111,a11n,a121,a12n,aijk,amn1,amnp);1im,1jn,1kp;,64,3.7.2数组的实现,1、数组的顺序存储,数组的顺序表示，指的是在计算机中，用一组连续的存储单元来实现数组的存储。目前的高级程序设计语言都是这样实现的。两种存储方式：一是按行存储（C语言、PASCAL等）二是按列存储（FORTRAN等）,elementtypeA23；,65,1、数组的顺序存储,对二维数组有：LOC（Aij）=LOC（A00）+ni+j，0im-1，0jn-1对三维数组有：LOC（Ai1i2i3）=LOC（A000）+d2d3i1+d3i2+i3，0i1d1-1，0i2d2-1，0i3d3-1,66,2、数组的压缩存储,特殊矩阵若n阶矩阵A中的元素满足下述性质aij=aji1i,jn则称n阶对称阵。对于对称矩阵,为实现节约存储空间,我们可以为每一对对称元素分配一个存储空间,这样,原来需要的n2个元素压缩存储到n(n+1)/2个元素空间。,对称关系：设sa0.n(n+1)/2做为n阶对称阵A的存储结构,则Sak和aij的一一对应关系为:i(i+1)/2+j当ijk=j(j+1)/2+i当ij,67,（2）稀疏矩阵,稀疏矩阵中，零元素的个数远远多于非零元素的个数。为实现压缩存储，仍考虑只存储非零元素。,68,第4章树,69,70,1、一个结点x组成的集x是一株树，这个结点x也是这株树的根。2、假设x是一个结点，T1，T2，Tk是k株互不相交的树，我们可以构造一株新树：令x为根，并有k条边由x指向树T1，T2，Tk。这些边也叫做分支，T1，T2，Tk称作根x的树之子树（SubTree）。,树的构造性递归定义,递归定义，但不会产生循环定义。,一株树的每个结点都是这株树的某株子树的根。,注意！,71,树的逻辑结构特点,除根结点之外，每株子树的根结点有且仅有一个直接前驱，但可以有0个或多个直接后继。即一对多的关系，反映了结点之间的层次关系。,72,结点的度(元结点的度(元）和树的度叶结点（终端结点）非终端结点（分支结点）子结点（儿子、子女）父结点（双亲）兄弟（结点）和树的高,路（径）长祖先（结点）后代（子孙）结点层、结点的高路（路径）,有序树无序树森林,森林forest：是n0株互不相交的树的集合。,73,二叉树:一棵二叉树是结点的一个有限集合，该集合或者为空，或者是由一个根结点和两棵分别称为左子树和右子树的、互不相交的二叉树组成。,结构特点:每个结点最多只有两个孩子结点，即结点的度不大于2,子树有左右之别，子树的次序（位置）不能颠倒。,基本形态：,4.2.1二叉树的定义及遍历,74,高度为K且有2K-1个结点的二叉树称为满二叉树。,设二叉树高度为K，称满足下列性质的二叉树为完全二叉树（1）所有的叶都出现在K或K-1层；（2）K-1层的所有叶都在非终结结点的右边；（3）除了K-1层的最右非终结结点可能有一个（只能是左分支）或两个分支之外，其余非终结结点都有两个分支。,75,二叉树的遍历,根据某种策略，按照一定的顺序访问二叉树中的每一个结点，使每个结点被访问一次且只被访问一次。结果得到二叉树结点的线性序列。,根（D）、左孩子（L）和右孩子（R）三个结点可能出现的顺序有：DLRLDRLRDDRLRDLRLD,要讨论的三种操作分别为：,先根顺序DLR，中根顺序LDR，后根顺序LRD,策略：左孩子结点一定要在右孩子结点之前访问。,76,先根顺序遍历二叉树：若二叉树非空则：访问根结点；先根顺序遍历左子树；先根顺序遍历右子树；,中根顺序遍历二叉树：若二叉树非空则：中根顺序遍历左子树；访问根结点；中根顺序遍历右子树；,后根顺序遍历二叉树：若二叉树非空则：后根顺序遍历左子树；后根顺序遍历右子树；访问根结点；,所得到的线性序列分别称为先根（序）、中根（序）和后根（序）序列。,77,如图所示的二叉树，对其进行先序、中序和后序遍历都是从根结点A开始的，且在遍历过程中经过结点的路线是一样的，只是访问的时机不同而已。,78,性质1二叉树的第i层最多有2i-1个结点。(i1)证明用数学归纳法性质2高度为K的二叉树最多有2K-1个结点。(K1)证明用求等比级数前K项和的公式20+21+22+2K=2K-1性质3对任何一棵二叉树,如果其叶结点有n0个,度为2的非叶结点有n2个,则有n0n21证明：若设度为1的结点有n1个，结点总数为n，分支总数为B，则根据二叉树的定义，n=n0+n1+n2B=2n2+n1=n-1因此，有2n2+n1=n0+n1+n2-1n2=n0-1n0=n2+1,4.2.2二叉树的性质,79,性质4具有n(n0)个结点的完全二叉树的高度为log2(n+1)或log2n+1证明：设完全二叉树的高度为K，则有2K-1-1n2K-1变形2K-1n+12K2K-1n2K取对数K-1rchild指向其右孩子结点，否则令其指向其（先序、中序、后序）后继；同时在每个结点中增加两个标志位，以区分该结点的的两个链域是指向其左/右孩子还是指向某种遍历的前驱/后继。,structnodedatatypedata;structnode*lchild,*rchild;enumboollchild,rchild;,typdefstructnode*THTREE;,87,p-ltag=,TRUEp-lchild指向左孩子FALSEp-lchild指向（中序）前驱,88,算法：求$p（中序前驱）：,分析：(1)当p-ltag=FALSE时，p-lchild即为所求（线索）。(2)当p-ltag=TRUE时，$p为p的左子树的最右结点。,THTREEInPre(THTREEp)THTREEQ;Q=p-lchild;if(p-ltag=TRUE)while(Q-rtag=TRUE)Q=Q-rchild;return(Q);,89,voidPreOrder(BTREET)STACKS;Makenull(S);/递归工作栈structnode*p=T;while(p!=NULL)coutdatarchild!=NULL)Push(S,p-rchild);if(p-lchild!=NULL)p=p-lchild;/进左子树elsep=Top(S);Pop(S);/左子树空,访问右子树,例先序遍历的非递归算法栈顶保存当前结点的右子树,90,voidPreorder(BTREEbt)STACKS;BTREEt;t=bt;Makenull(S);while(t!=null|!Empty(S)whlie(t!=null)visit(t-data);push(t,S);t=t-lc;if(!Empty(S)t=top(S);pop(S);t=t-rc;,例先序遍历的非递归算法栈顶保存当前结点的左子树,91,4.3.1树的三种遍历,先根顺序访问根结点；先根顺序遍历T1;先根顺序遍历T2;先根顺序遍历Tk;,中根顺序中根顺序遍历T1;访问根结点；中根顺序遍历T2;中根顺序遍历Tk;,后根顺序后根顺序遍历T1;后根顺序遍历T2;后根顺序遍历Tk;访问根结点；,先根遍历序列:RADEBCFGHK中根遍历序列:DAERBGFHKC后根遍历序列:DEABGHKFCR,D,A,E,R,B,C,F,G,H,K,92,4.3.2树的存储结构,1、树的数组表示法（双亲表示、父链表示、单链表示）,首先，对树T的结点按下列规则依次编号：根结点编号为1；对于T中的每一个已编号的结点k，按从左到右的顺序对k的儿子结点编号。然后，令树T的结点编号与一个结构体数组的下标对应，结构体数组的每个单元包括两个域：parent和data域，且规定：,Ai.data=结点i的数据域的值,父链表示：,93,structnodeintparent;chardata;,typedefnodeTREE11;TREET;,存储结构：,基本操作的实现：,结构特点：每个结点均保存父结点所在的数组单元下标兄弟结点的编号连续。,易求父结点、祖先结点：如i的父结点的父结点TTi.parent.parent易求结点数据域的值：Ti.data不便于CREATEk操作,94,2、树的邻接表表示法（孩子表示法、孩子链表表示法）,typedefstructCTNodeintchild;structCTNode*next;*ChildPtr;typedefstructTelementtypedata;ChildPtrfirstchild;CTBox;typedefstructCTBoxnodesMAX_TREE_SIZE;intn,r;Ctree;,95,1、结点结构,2、存贮示例,因每个结点有且仅有两个指针域，所以也称为二叉树表示方法,3、树的（左）孩子（右）兄弟表示法（二叉树表示法）,96,类型：typedefstructCSNode/动态存储结构ElemTypedata;structCSNode*firstchild,*nextsibling;typedefstructCSNode*TREE;,97,森林（树）转换为二元树：,连线：把每株树的各兄弟结点连起来；把各株树的根结点连起来（视为兄弟）抹线：对于每个结点，只保留与其最左儿子的连线，抹去该结点与其它结点之间的连线旋转：按顺时针旋转45度角（左链竖画，右链横画）,98,4.5树的应用,没有度数为1的结点外结点数=内结点数+1(为什么?)有n个外结点的扩充二元树共有2n-1个结点。,4.5.3哈夫曼（Huffman）树及其应用,在二叉树中，对于每个结点，若出现空（左/右）子树，则为其加上一个特殊的结点（称为外结点），由此得到的新二叉树称为原二叉树的扩充二叉树。而原二叉树的结点称为内结点,一、哈夫曼树的由来及其构造,99,内路径长I=21+32+13=11外路径长E=12+53+24=25,2.扩充二元树的外路径长、内路径长及相互关系,外路径长E：从根结点到每个外结点的路径长之和，E=lj内路径长I：从根结点到每个内结点的路径长之和关系：E=I2n(n为内结点的个数）,4.5.3哈夫曼（Huffman）树及其应用,100,设：wi=2,3,4,11,求：wjlj（加权路长）,（a）111422333=34（b）213243113=53（c）221123242=40,3.扩充二元树的加权路径长,外结点的加权路径长：设每个外结点j对应一个实数wj（称为外结点的权值），lj是从根到外结点j的路长，则wjlj个称为外结点j的加权路长。扩充二元树的加权路长:WPL=wjlj称为扩充二元树的加权路长。,4.5.3哈夫曼（Huffman）树及其应用,101,哈夫曼树定义:在给定权值为w1，w2wn的n个叶结点所构成的所有扩充二叉树中，WPL=wjlj最小的称为huffman树。在哈夫曼树中，权值越小，离根越远；权值大的结点离根最近。,构造算法:(1)由给定的n个权值w0,w1,w2,wn-1，构造具有n棵扩充二叉树的森林F=T0,T1,T2,Tn-1，其中每棵扩充二叉树Ti只有一个带权值wi的根结点,其左、右子树均为空。(2)重复以下步骤,直到F中仅剩下一棵二叉树为止：在F中选取两棵根结点的权值最小的扩充二叉树,做为左、右子树构造一棵新的二叉树，且置新的二叉树的根结点的权值为其左、右子树上根结点的权值之和。在F中删去这两棵二叉树。把新的二叉树加入F。,哈夫曼树（最优二叉树）,102,F:7524,F:756,7,5,2,4,0-初始,1-合并24,F:711,7,5,2,4,7,5,2,4,6,6,11,2-合并56,F:18,5,3-合并711,2,7,4,6,11,18,举例,103,编码和译码：,哈夫曼（Huffman）树及其应用,是指将文件（字符集）中的每个字符转换为一个唯一的二进制串。,编码,（解码）是指将二进制串转换为对应的字符。,译码,对于给定的字符集，可能存在多种编码方案，但应选择最优的。,3.编码的前缀性：,对字符集进行编码时，如果任意一个字符的编码都不是其它任何字符编码的前缀，则称这种编码具有前缀性或前缀编码。,前缀编码,注意,等长编码具有前缀性；变长编码可能使译码产生二义性，即不具有前缀性。如,E(00),T(01),W(0001),则译码时无法确定信息串是ET还是W。,104,最优编码（Huffman编码）,Huffman编码问题和编码算法：,对于给定的字符集以及每个字符出现的概率（使用频度），求字符集的最优的前缀性编码Huffman编码问题。,用huffman算法求字符集最优编码的算法：,使字符集中的每个字符对应一株只有叶结点的二叉树，叶的权值为对应字符的使用频率；利用huffman算法来构造一株huffman树；对huffman树上的每个结点，左支附以0，右支附以1（或者相反），则从根到叶的路上的0、1序列就是相应字符的编码,105,Huffman编码问题和编码算法：,哈夫曼（Huffman）树及其应用,举例,106,第5章图及其相关算法,107,图是由顶点集合(vertex)及顶点间的关系集合组成的一种数据结构：Graph(V,E)其中V=x|x某个数据对象是顶点的有穷非空集合；E=(x,y)|x,yV或E=|x,yV是顶点之间关系的有穷集合，也叫做边(edge)集合。有向图若图G的每条边都有方向，则称G为有向图（Digraph)。在有向图中，有向边（也称弧）都是顶点的有序对。无向图若图G的每条边都是没有方向的，则称G为无向图（UnDigraph)。在无向图中，每条边都是顶点的无序对(x,y)。,定义图,5.1图的基本概念,108,无向图中顶点v的度（Degree）是关联于该顶点的边的数目，或与该顶点相邻的顶点数目，记为D（v）。若G是有向图，则把邻接到顶点v的顶点数目或边数目称为顶点v的入度（Indegree），记为ID（v）；把邻接于顶点v的顶点数目或边数目称为顶点v的出度（Outdegree），记为OD（v）；顶点v的度则定义为该顶点的入度和出度之和，即D（v）=ID（v）+OD（v）无论是有向图还是无向图，顶点数n、边数e和度数之间的关系为：,定义结点的度,109,在无向图G中，若存在一个顶点序列vp,vi1,vi2,vim,vq，使得（vp,vi1）,（vi1,vi2）,（vim,vq）E(G)，则称顶点vp路到vq有一条路径（Path）。在有向图G中，若存在一个顶点序列vp,vi1,vi2,vim,vq，使得有向边,E(G)，则称顶点vp路到vq有一条有向路径（Path）。非带权图的路径长度是指此路径上边的条数。带权图的路径长度是指路径上各边的权之和。简单路径若路径上各顶点v1,v2,.,vm均不互相同,则称这样的路径为简单路径。简单回路若路径上第一个顶点v1与最后一个顶点vm重合,则称这样的简单路径为回路或环。,定义路（径）、路径长、简单路、简单环路,110,连通图与连通分量在无向图中,若从顶点vi到顶点vj有路径,则称顶点vi与vj是连通的。如果图中任意一对顶点都是连通的,则称此图是连通图。非连通图的极大连通子图叫做连通分量。强连通图与强连通分量在有向图中,若对于每一对顶点vi和vj,都存在一条从vi到vj和从vj到vi的路径,则称此图是强连通图。非强连通图的极大强连通子图叫做强连通分量。,定义图的连通性,5.1图的基本概念,111,5.2.1邻接矩阵(AdjacencyMatrix),一、图的邻接矩阵表示,5.2图的存储表示,在图的邻接矩阵表示中，有一个记录各个顶点信息的顶点表，还有一个表示各个顶点之间关系的邻接矩阵。设图A=(V,E)是一个有n个顶点的图,图的邻接矩阵是一个二维数组A.edgenn，定义：,112,4,1,0,无向图的邻接矩阵是对称的;有向图的邻接矩阵可能是不对称的。在有向图中,统计第i行1的个数可得顶点i的出度，统计第j列1的个数可得顶点j的入度。在无向图中,统计第i行(列)1的个数可得顶点i的度。,二、网络的邻接矩阵,113,#defineMaxValueInt_Max/在中#defineNumEdges50;/边条数#defineNumVertices10;/顶点个数typedefcharVertexData;/顶点数据类型typedefintEdgeData;/边上权值类型typedefstructVertexDatavexlistNumVertices;/顶点表EdgeDataedgeNumVerticesNumVertices;/邻接矩阵边表,可视为边之间的关系intn,e;/图中当前的顶点个数与边数MTGraph;,114,voidCreateMGragh(MTGragh*G)/建立(无向)图的邻接矩阵inti,j,k,w;scanf(%d,%d,/空间复杂性：S=O(n+n2)/时间复杂性：T=O(n+n2+e)。当en,T=O(n2),115,5.2.2邻接表(AdjacencyList),一、图的邻接表表示,对于G中的每个顶点vi，把所有邻接（于）vi的顶点vj链成一个单链表（称为关于vi的邻接表）。邻接表中每个表结点都有两个域：其一是邻接点域adjvex，用以存放与vi相邻顶点的序号；其二是链域next，用来将邻接表的所有表点链在一起；另外若要表示边上的信息如（权值）,则在表结点中还应增加一个数据域cost.,无向图G1邻接表,116,G2的逆邻接表,有向图G2邻接表,在无向图的邻接表中，一条边（Vi，Vj）在邻接表中出现两次：一次在关于Vi的邻接表中；一次在关于Vj的邻接表中.关于顶点Vi的邻接表的结点数目为顶点Vi的度,在有向图的邻接表中，一条边在邻接表中出只现一次关于顶点Vi的邻接表中结点数目为顶点Vi的出度；在逆邻接表中关于顶点Vi的邻接表中结点数目为顶点Vi的入度。,117,#defineNumVertices10;/顶点个数typedefcharVertexData;/顶点数据类型typedefintEdgeData;/边上权值类型typedefstructnode/边表结点intadjvex;/邻接点域（下标）EdgeDatacost;/边上的权值structnode*next;/下一边链接指针EdgeNode;typedefstruct/顶点表结点VertexDatavertex;/顶点数据域EdgeNode*firstedge;/边链表头指针VertexNode;typedefstruct/图的邻接表VertexNodevexlistNumVertices;intn,e;/图中当前的顶点个数与边数AdjGraph;,118,在邻接矩阵中求边的数目e，必须检查整个矩阵，所耗时间是O(n2)，与边的个数e无关；而在邻接表中求边的数目e，只要对每个边表的结点个数进行计数即可求得e，所耗时间是O(e+n)。因此当e是否为图的一条边，只要判断矩阵中的第i行第j列是否为非零元素即可;但在邻接表中，须扫描第i个边表，最坏情况下消耗时间O(n).空间复杂度,两种存储结构的比较,图的搜索：从图的某个顶点出发，访遍图中所有的顶点，且使每个顶点被访问一次且仅被访问一次，称为图的搜索（遍历）（GraphTraversal）。“访问”有许多方法和策略，不同的“访问”方法和策略导致不同的搜索算法，因此图的搜索算法是有关图的算法的基础。,119,图中可能存在回路，且图的任一顶点都可能与其它顶点相通，在访问完某个顶点之后可能会沿着某些边又回到了曾经访问过的顶点。为了避免重复访问，可设置一个标志顶点是否被访问过的辅助数组visited初始状态为0,在图的遍历过程中,一旦某一个