第二章基本数据结构及其运算.ppt

第二章基本数据结构及其运算,2.1数据结构的基本概念2.2线性表及顺序存储结构2.3线性表链表及其运算2.4数组2.5树与二叉树2.6图,本章主要介绍:数据结构、数据逻辑结构、数据存储结构的基本概念；几种常用的数据结构(线性表、栈、队列、数组、树与二叉树、图），阐明这些数据结构内在的逻辑关系，讨论它们在计算机中存储的常用方式：顺序存储和链式存储，以及在这些数据结构上进行各种运算的算法。重点：理解数据结构、数据逻辑结构和存储结构的概念，掌握常用的数据结构中各数据内在的逻辑关系，在计算机中的存储方式，以及在其上进行各种运算的算法。难点：正确区分数据逻辑结构和存储结构，掌握常用数据结构在计算机中的存储方式，及在其上进行各种运算的算法。,1、数据元素之间的固有逻辑关系，称为数据的逻辑结构,数据结构主要研究和讨论三方面问题：,2、数据元素及其关系在计算机中的存储方式，称为数据的物理结构或存储结构,3、施加在数据结构上的操作，称为数据结构的运算。数据处理的本质就是对数据结构施加各种运算，常见的运算有：查找、排序、插入、删除等。,2.1数据结构的基本概念,例1、无序表的顺序查找与有序表的对分查找。,2.1.1两个例子,2、尽量节省数据处理过程中所占用的存储空间,1、提高数据处理的速度,主要目的是提高数据处理的效率：,12345678910,12345678910,data0data1data2data3data4data5data6data7data8,13244277,2830,12132124,28304277,25,(a)无序表,data0data1data2data3data4data5data6data7data8,21,12,25,(b)有序表,图2.1数据元素存放顺序不同的两个表,表(a)只能采用顺序查找，将x与表中每一个元素进行比较，查找效率较低。,因表(b)中的元素是有序排列，可找到其中间元素data4，将x与它进行比较，有三种可能：x=data4xdata4xn,in)THENi=n+1IF(in或i1不能进行删除,其算法为：,PROCEDUREDESL(V,n,i)IF(n=0)THENUNDERFLOW;RETURNIF(in)THENprintf(“Notthiselementinthelist”;RETURNFORj=iTOn-1DOV(j)=V(j+1)n=n-1RETURN,例：C+语言编写顺序表基本操作：表初始化、输出、插入与删除（C+幻灯20）,顺序表操作的特点：,1顺序表中数据元素的个数需要预先确定；,2由于顺序表的随机存取特性，访问每个元素很方便；,3插入和删除操作需移动大量的元素，平均为个,4、需一片连续空间，线性表容量不易扩充,2.2.2栈及其应用,例：下列给出了具有嵌套调用的五个程序,1、什么是栈,返回地址：A、B、C、D,A、B、C、D组成一个线性表，计算机系统在处理时可用一个线性表来动态记忆调用过程中的路径，即建立一个空线性表，调用函数时将返回地址插入线性表，返回主程序时将返回地址从表中删除；但如何处理插入与删除的元素，才能让调用过程不出差错。,要让调用过程不出差错，这四个元素的插入顺序必须为A、B、C、D，而删除顺序刚好与这相反，为D、C、B、A，,如规定只能在一端进行插入与删除操作，可满足上述要求。这种只能在一端进行插入与删除操作的线性表称为栈。,允许插入和删除的一端称为栈顶，而不允许插入与删除的一端称为栈底。,入栈顺序：a1,a2,a3,an出栈顺序：an,an-1,a2,a1栈的操作原则：先进后出,栈底,栈顶,插入(入栈),删除(出栈),top,bottom,随着入栈与出栈操作的进行，栈顶的位置浮动变化，为反映这种变化，设置一个栈顶指针top，指向当前栈顶元素的存储位置，设一个栈底指针bottom，指向栈底元素的存储位置。,2、栈的基本运算（1）入栈：在栈顶端插入一个新元素（2）出栈(退栈)：从栈顶删除一个元素（3）取栈顶元素：在栈中读栈顶元素,3、栈的顺序存储结构及其运算,栈是一种特殊的线性表，与一般顺序存储结构的线性表一样，也可利用一片连续的存储单元依次存放自栈底到栈顶的数据元素，,可用一维数组S(1:m)模拟栈，m为栈的容量一般取：bottom=1,入栈：,top=top+1,S(top)=x,出栈：,top=top-1,y=S(top),栈空：,top=0,栈满：,top=m,初始状态：,top=0,算法2.3在容量为m的栈s中插入一个元素x,PROCEDUREPUSH(S,m,top,x)IF(top=m)THENstack-OVERFLOW;RETURNtop=top+1S(top)=xRETURN,异常情况为：,栈满时，不能插入,top=m,该算法涉及到的输入、输出数据：,算法2.4在容量为m的栈s中删除一个元素,PROCEDUREPOP(S,top,y)IF(top=0)THENstack-UNDERFLOW;RETURNy=S(top)top=top-1RETURN,异常情况为：,栈空时，不能删除,top=0,该算法涉及到的输入、输出数据：,算法2.5读栈顶元素,PROCEDURETOP(S,top,y)IF(top=0)THENstack-UNDERFLOW;RETURNy=S(top)RETURN,异常情况为：,栈空时，无元素可读,top=0,该算法涉及到的输入、输出数据：,栈是最广泛使用的数据结构之一，子程序的调用，递归过程的实现，表达式的计算都是栈应用的典型例子。自学P38表达式的计算,2.2.3队列及其应用,1、什么是队列,队列也是一种特殊的线性表，它只允许在一端进行插入，而在另一端进行删除，允许插入的一端称为队尾，用一个尾指针rear指示，允许删除的一端称为队（排）头，用一个排头指针(front)指示。,入队顺序：A,B,C,D,E,F出队顺序：A,B,C,D,E,F,队列的操作原则：先进先出,同栈类似，在顺序存储结构下，可用一维数组Q(1:m)模拟队列，m为队列的容量,入队：,rear=rear+1,Q(rear)=x,出队：,y=Q(front),队空：,front=rear,队满：,rear=m,初始状态：,front=rear=0,front=front+1,由于队列只能在一端插入，在另一端删除，随着入队与出队运算不断进行，队列中元素不断向队尾方向移动，而在排头产生一片不能用的空间，最后可能导致尾指针指向队列最后一个位置，而排头却有一片无法利用的空闲区，这种现象称为“假溢出”,front,rear,如何避免“假溢出”现象的发生：,最简单的办法，在进行入队与出队运算时，调整队列中元素在存储空间中的位置，即出队时将队列中所有元素依次向排头方向移动一个位置。但这种办法需移动大量的元素，在实际中一般不用，而是采取另一种办法。,2、循环队列,将队列存储空间的最后一个位置饶到第一个位置，形成逻辑上的环状空间，供队列循环使用,m,1,入队：,rear=rear+1,Q(rear)=x,出队：,y=Q(front),队空：,front=rear,队满：,rear=front,初始状态：,front=rear=m,front=front+1,循环队列的运算,Ifrear=m+1Thenrear=1,Iffront=m+1Thenfront=1,由此可见，循环队列结构虽然避免了“假溢出”现象，但却带来一个新问题，无法区别满足条件front=rear的队列是处于队空还是队满的状态，为解决这个问题，可采用两种方法：,（1）、另设一个标志以区别队空和队满,队满条件：,s=1andrear=front,队列初始状态：,s=0且front=rear=m,队空条件：,s=0,入队操作：,If(rear=front)and(s=1)Then“队满”；Returnrear=rear+1Ifrear=m+1Thenrear=1Q(rear)=xs=1,出队操作：,If(s=0)Then“队空”；Returnfront=front+1Iffront=m+1Thenfront=1y=Q(front)Ifrear=frontThens=0,完整的算法见P4344,（2）、用队尾指针追上排头指针这一特征作为队满的条件,入队时，将rear+1=front作为队满的条件,即：rear=rear+1Ifrear=m+1Thenrear=1Ifrear=frontThen“队满”,队空：rear=front,算法2.6a在容量为m的循环队列Q中插入一个元素x,PROCEDUREADDCQ(Q,m,rear,front,x)t=rear+1IF(t=m+1)THENt=1IF(t=front)THEN“OVERFLOW”;RETURNrear=tQ(rear)=xRETURN,异常情况为：,队满时，不能插入,(rear+1)modm=front,该算法涉及到的输入、输出数据：,算法2.7a在容量为m的循环队列Q中删除一个元素,PROCEDUREDELCQ(Q,m,rear,front,y)IF(rear=front)THEN“UNDERFLOW”;RETURNfront=front+1IF(front=m+1)THENfront=1y=Q(front)RETURN,异常情况为：,队空时，不能删除,rear=front,该算法涉及到的输入、输出数据：,队列在计算机中也有广泛的应用，凡可抽象为线性表并符合先到先服务的处理过程，均可用队列模拟。例VB中的事件队列；计算机中CPU与外设传递数据时，在内存中设置的缓冲区队列。P48介绍了队列在日常生活中应用，自学,线性表顺序存储结构具有结构简单，读取元素方便等优点，适合小线性表或长度固定的线性表，但它存在以下几方面的缺点：,需一片连续空间，不能利用存储器中的碎片，且线性表容量不易扩充,不能对存储空间进行动态分配；,插入和删除操作需移动大量的元素，平均为个,对于大的线性表或元素变化频繁的线性表不宜采用顺序结构，而是采用链式存储结构,1、线性链表,线性链表是线性表的链式存储结构，在链式存储结构中，数据元素可存储在不连续的空间中，各数据元素之间的关系不是由存储单元的邻接关系确定，而是由指针域确定。,2.3线性链表及其运算,2.3.1线性链表的基本概念,在链式存储结构中，每一个数据元素的表示由两部分信息组成：一是数据元素的值；二是各数据元素的前后件关系,存储数据元素值,存储与该结点逻辑上相邻的结点地址,即：线性链表中每一个元素的存储单元都由数据域和指针域两部分组成，称为存储结点（结点）,只有一个指针域时，其存储内容为该结点后件的地址，无后件结点，指针域为“0”、“NULL”或“”,例：已知数据结构B=(D,R)，D=a,b,c,d,e,f，R=(b,c),(c,d),(d,a),(a,f),(f,e)，其链式存储结构为：,注意：头指针Head是整个链表的唯一标识，通过它可找到链表中任意元素数据元素间的逻辑关系是通过指针来反映的链式结构既可存储线性结构，也可存储非线性结构（多个后件用多个指针域指向，前件也可用指针域指出,线性链表的物理状态,用链式结构存储线性表时，每个结点的存储空间可任意分配，它们可以不连续，它们之间的关系由指针域确定,在程序设计时，可用两个一维数组V(1:m)，Next(1:m)存储线性表，用V表示数据，Next表示指针域则第i个结点为,数据元素值,数据元素地址,上例用数组存储：R=(b,c),(c,d),(d,a),(a,f),(f,e),V(1)=a、V(2)=b、V(3)=c、V(4)=d、V(5)=e、V(6)=f,Next(1)=,6,Next(2)=,3,Next(3)=,4,Next(4)=,1,Next(5)=,0,Next(6)=,5,Head=,2,通过Head可找到链表中任意元素，例：,V(Head)=V(2)=bp=Next(Head)=Next(2)=3,V(p)=V(3)=c,一般而言，线性链表（a1,a2,a3,ai,an）可用如下逻辑状态图来表示：,上例可用下图表示线性链表的逻辑状态：V(1)=a、V(2)=b、V(3)=c、V(4)=d、V(5)=e、V(6)=fR=(b,c),(c,d),(d,a),(a,f),(f,e),Head,2,3,4,1,6,5,线性链表中的各结点在计算机中的存储位置分布是杂乱的，但只要抓住了链表的头指针Head，实际上就抓住了表中所有结点。当Head=0时为空表,算法2.9依次输出头指针为Head的线性表中各结点值,异常情况：,该算法涉及到的输入、输出数据：,空表时无输出,PROCEDUREPRTLL(V,Next,Head)j=HeadWhile(j0)DooutputV(j)j=Next(j)RETURN,P5556介绍了如何在C+语言中用动态分配内存的方法实现链表，并用一段程序介绍在C+语言中如何创建链表，如何输出链表中各元素，自学,前面讨论的链表每个结点只有一个指针域，指向其后件地址，由该指针能方便找到其后件，但不能找到前件，这种链表称为线性单链表(单链表)，在单链表中，只能顺指针向链尾方向扫描，当要寻找某个结点的前件时，只能从头指针开始重新寻找。为弥补单链表的不足，在应用中可设置两个指针域，一个指向前件，称为左指针；一个指向后件，称为右指针。这样的线性表称为双向链表,第i个结点：,逻辑状态图：,2、带链的栈,栈和队列是线性表，故栈和队列都可采用链式存储结构,Top,栈顶指针相当于链表头指针,0,在实际应用中，带栈的链可以用来收集计算机存储空间中具有相同结构的空闲存储空间，这种带链的栈称为可利用栈。由于可利用栈链接了计算机存储空间中具有相同结构的空闲结点，因此，当计算机系统或用户程序需要存储结点时，可从中取出栈顶结点，当计算机系统或用户程序释放一个存储结点时，则将该结点放回到可利用栈的栈顶。,p,从可利用栈中取得一个结点p,p,将结点p送回可利用栈,用链式存储结构解决实际问题时，首先分配一定的存储空间形成可利用栈，再构造与可利用栈中结点具有相同结构的链表(可能有多个)，这些链表中元素的插入结点取至可利用栈，删除的结点送回可利用栈。因此所有具有相同结构的链表可共用同一个可利用栈,算法2.10从栈顶为Top的可利用栈取得一个p,输入：输出：,异常情况：,栈为空，获得结点失败,返回值P=,0可利用栈无空间分配失败,0可利用栈有空间分配成功,PROCEDUREnew(p)p=TopIfp=0ThenReturnTop=Next(Top)Return,算法2.11将结点p送回栈顶为Top的可利用栈,输入：输出：,异常情况：,无,PROCEDUREdispose(p)Next(p)=TopTop=pReturn,可利用栈是一个空表，是为其它链表服务的。以下算法是带链的栈的入栈与出栈运算,算法2.12在栈顶为Top1的带链栈中插入一个元素x,输入：输出：,异常情况：,可利用栈为空分配新结点失败,p,x,new(p);ifp=0then“无空间”,PROCEDUREPushLL(Top1,x)new(p)Ifp=0Then“无空间”；ReturnV(p)=xNext(p)=Top1Top1=pReturn,算法2.13在栈顶为Top1的带链栈中删除栈顶元素,p,输入：输出：,异常情况：,栈空，不能删除,Top1=0,PROCEDUREPOPLL(Top1,y)IfTop1=0Then“栈空”；Returny=V(Top1)p=Top1Top1=Next(Top1)dispose(p)Return,在C语言中用函数malloc()分配空间，用free()释放空间在C+语言中用new分配空间，用delete释放空间,3、带链的队列,排头指针(front)相当于链表头指针，尾指针(rear)指向链表最后一个元素,front,rear,队空(front=rear=0)，改变头指针和尾指针的值,算法2.14在带链队列中插入一个元素x,输入：输出：,异常情况：,可利用栈为空，分配新结点失败,p,x,new(p);ifp=0then“无空间”,0,front=prear=p,PROCEDUREADDLL(rear,front,x)new(p)Ifp=0Then“无空间”；ReturnV(p)=xNext(p)=0Iffront0ThenNext(rear)=prear=pElserear=front=pReturn,算法2.15在带链队列中删除一个元素,输入：输出：,队中只有一个结点，删除该结点后，必须改变尾指针(rear)的值,front,p,异常情况：,队空，不能删除,front=0,rear=0,PROCEDUREDELLL(front,rear,y)Iffront=0Then“队空”；Returny=V(front)p=frontfront=Next(front)Iffront=0Thenrear=0dispose(p)Return,线性链表可进行的基本运算即为线性表的基本运算，主要介绍前两种运算，在线性链表中，结点之间的关系是由指针的链接关系关系来表示，在对线性链表进行插入与删除时，只需改变指针即可,线性表插入、线性表删除、线性表查找、线性表排序、线性表分解、线性表合并、线性表复制、线性表逆转,2.3.2线性链表的基本运算,一、在线性链表中包含x元素的结点之前插入一个新元素b,p,b,1、为插入的新元素分配一个新结点p，V(p)=b,2、在线性表中寻找包含元素x的前一个结点q,3、将结点p插入到结点q之后,b,p,单向链表,双向链表,单向链表Next(p)=Next(q)Next(q)=p,双向链表Llink(p)=qRlink(p)=Rlink(q)Llink(Rlink(q)=pRlink(q)=p,q,q,二、在线性链表中删除包含元素x的结点,p,1、在线性表中寻找包含元素x的前一个结点q,2、删除结点q的后一个结点,3、释放被删除的结点,p,单向链表,双向链表,单向链表Next(q)=Next(Next(q),双向链表Rlink(q)=Rlink(Rlink(q)Llink(Rlink(Rlink(q)=q,q,q,从上面分析可看出，线性表的插入与删除不涉及数据元素的移动，但也存在两个问题：、插入时，从何处得到空闲的结点作为新元素结点；删除时，被删除结点应释放到何处才能被以后使用，即如何管理空闲结点(用可利用栈)2、在非空链表中寻找包含指定元素的前一个结点,算法2.16在头指针为Head的非空链表中寻找包含元素x的前一个结点q,输入：输出：,2、x在表中第一个元素,异常情况：,1、空表,3、x不在表中,放入插入与删除算法中考虑,q,PROCEDURELookST(Head,x,q)q=HeadWhile(Next(q)0)and(V(next(q)x)Doq=Next(q)Return,如链表中未包含元素x，q指向,链表最后一个元素,即返回值Next(q)=0 x不在链表中Next(q)0q为x前件地址,三、线性表的插入与删除算法,算法2.1在头指针为Head的线性链表中包含元素x的结点前插入结点b，如链表中无元素x，则将b插入到链表的末尾。,、x在表中第一个元素，插在表头,异常情况：,、空表，插入结点为表中第一个结点,、x不在表中，插在表尾,输入：输出：,Head=0,V(Head)=x,LookST(Head,x,q)Next(q)=0,、无空间，不能插入,p,b,q,PROCEDUREInsLst(Head,x,b)new(p)Ifp=0Then“无空间”；ReturnV(p)=bIfHead=0ThenHead=p;Next(p)=0;ReturnIfV(Head)=xThenNext(p)=Head;Head=p;ReturnLookST(Head,x,q)Next(p)=Next(q)Next(q)=pReturn,算法2.1在头指针为Head的线性链表中删除包含元素x的结点,、删除元素为表中第一个结点,异常情况：,、空表，不能删除,、x不在表中，不能删除,Head=0,V(Head)=x,LookST(Head,x,q)Next(q)=0,PROCEDUREDelSt(Head,x)IfHead=0Then“空表”;ReturnIfV(Head)=xThenp=Next(Head);dispose(Head);Head=p;ReturnLookST(Head,x,q)IfNext(q)=0Then“无此结点”;Returnp=Next(q)Next(q)=Next(p)Dispose(p)Return,p,q,线性链表插入与删除示意图见书P68图2.26P70图2.27,输入：输出：,四、循环链表,增加一个表头结点，数据域任意或根据需要设置，指针域指向线性链表的第一个结点，Head指向表头结点,最后一个结点指针域不为空，而是指向表头结点,空循环链表,注意：,循环链表可以从任何一个结点出发去访问其他结点,循环链表和单链表判定表的结束标志的方法不同：循环单链表的结束标志：Next(P)=Head单链表的结束标志：Next(P)=0,循环链表的插入和删除算法和单链表类似。自学,循环链表和单链表判定空表的方法不同：循环单链表为空表标志：Head=Next(Head)单链表为空表标志：Head=0,1.顺序表占用的存储空间最少，而双链表占用的存储空间最多,2.顺序表是一种随机存储结构，访问表中的某一个元素方便；单链表元素的访问则必须从头指针开始按顺序依次去寻找待访问的元素。,3.一个顺序表一旦确定则其大小就不可以随意改变，因此操作中需要进行“判满”的工作，而链表的大小却可方便的改变，但链表占用的存储空间较多。,4.顺序表的操作主要消耗在元素的移动上，效率较低，单链表的操作消耗在指针的移动上，双链表的操作极为方便，但却是建立在存储空间的消耗上的。,总结:,五、线性表的应用一元多项式相加,任何一个一元多项式Pn(x)都可按升幂表示为：Pn(x)=p0+p1x+p2x2+pixi+pnxn,可见Pn(x)由n+1个系数（p0，p1，pi，pn）唯一确定，可用一个线性表P来表示系数的集合，其中Pi(x)项的指数隐含在系数pi中。该线性表可表示为：P=（p0，p1，pi，pn）表长为n+1。,同理，再设一个一元多项式Qm(x)，此多项式也可由一个线性表Q=（q0，q1，qi，qm）(表长为m+1)来表示。若要计算：Rn(x)=Pn(x)+Qm(x)，这里不失一般性，假定mn。Rn(x)也可用线性表R=(p0+q0，p1+q1，pm+qm，pm+1,，pn）来表示，显然可以对P、Q、R采用顺序结构存储，采用顺序表形式处理这种多项式的相加。,但是，若已知多项式为S(x）=1+3x10000+5x30000，此时再用将指数项隐含在系数中的方式，用系数顺序表来表示S（x），则其表长为30001，而表中只有3个非零元素，浪费了大量的存储空间。因此，一般情况下的一元n次多项式可写成：Pn(x)=P1xe1+P2xe2+Pixei+Pmxem，其中Pi是指数为ei的非零系数项，且满足0e1e2i),只需存储下三角元素即可,用B1:n(n+1)/2以行为主存储,访问时：,jiaij=Bi(i-1)/2+j,jiaij=aji=Bj(j-1)/2+i,即：,3对角矩阵若矩阵中所有非零元素都集中在以主对角线为中心的带状区域中，区域外的值全为0，则称为对角矩阵。常见的有三对角矩阵、五对角矩阵、七对角矩阵等。例如，77的三对角矩阵有三条对角线上元素非0。,aij=,B2(i-1)+j(i-1ji+1),0(ji+1),三对角矩阵压缩存储时，只需存三对角元素，共3(n-2)+4=3n-2个，用B1:3n-2以行为主存储，访问时，i-1ji+1时aij=Bk；其它aij=0,aij=,B2(j-1)+i(i-1ji+1),0(ji+1),同理，以列优先依次存放，要访问i行j列元素aij的公式为：,k=3(i-1)-1+(j-i+2)=2(i-1)+j,2.4.3一般稀疏矩阵的表示在特殊矩阵中，元素的分布呈现某种规律，故一定能找到一种合适的方法，将它们进行压缩存放。但是，在实际应用中，我们还经常会遇到一类矩阵：其矩阵阶数很大，非零元素个数较少，零元素很多，但非零元素的排列没有一定规律，我们称这一类矩阵为稀疏矩阵。,例：如下78矩阵，56个元素中只有8个非零元素，其余均为零元素，而非零元素分布是无规则的。这类矩阵也可采用压缩存储，只存储非零元素，但由于非零元素分布无规律，压缩时，除存放非零元素的值外，还必须存储适当的辅助信息，才能迅速确定一个非零元素是矩阵中的哪一个位置上的元素。,1、稀疏矩阵的顺序存储,为了使稀疏矩阵经过压缩后，能方便地访问其中每一个非零元素(访问不到的为零元素)，通常需给出三个信息：,非零元素所在行号,非零元素所在列号,非零元素值,即一个非零元素可用一个三元组(i,j,v)表示。上例三元组可表示为：,所对应的三元组为：,(1,3,3),(1,8,1),(3,1,9),(4,5,7),(5,7,6),(6,4,2),(6,6,3),(7,3,5),为表示唯一性，添加一个三元组:（总行数，总列数，非零元素个数），即(7,8,8)，表示稀疏矩阵的总体信息。所以，一个具有t个非零元素的稀疏矩阵可用t+1个三元组表示，其中第一个三元组用于表示稀疏矩阵的总体信息，其后各三元组依次表示各非零元素，且按以行为主的顺序存储。常用三列二维的表格或数组形式表示(三列二维数组)，如图。,2、稀疏矩阵的链式存储结构,当稀疏矩阵中非零元素的位置或个数经常变动时，三元组的顺序存储结构就不适合，此时，采用链表作为存储结构更为恰当。稀疏矩阵的链式存储结构方法有几种，如带行指针的单链表表示法和十字链表表示方法。,带行指针的链表把具有相同行号的非零元素用一个单链表连接起来，稀疏矩阵中的若干行组成若干个单链表，合起来称为带行指针的链表。例如，上例稀疏矩阵的带行指针的链表描述形式：,这种方法能方便找到同一行的所有非零元素，但不便寻找同一列的所有元素,十字链表十字链表是稀疏矩阵的的一种较好的存储方法，在该方法中，每一个非零元素用一个结点表示，结点中除了表示非零元素所在的行、列和值的三元组（i,j,v）外，还需增加两个链域：行指针域(rptr)，用来指向本行中下一个非零元素；列指针域(cptr)，用来指向本列中下一个非零元素。稀疏矩阵中同一行的非零元素通过向右的rptr指针链接成一个链表。同一列的非零元素也通过cptr指针链接成一个链表。因此，每个非零元素既是第i行链表中的一个结点，又是第j列链表中的一个结点，相当于处在一个十字交叉路口，故称这种链表为十字链表。,十字链表结点,指向本行下一个元素,指向本列下一个元素,另外，为了运算方便，我们规定行、列循环链表的表头结点和表示非零元素的结点一样，也定为五个域，且规定行、列、域值为0，并且将所有的行、列链表和头结点一起链成一个循环链表。在行（列）表头结点中，行、列域的值都为0，故两组表头结点可以共用，即第i行链表和第i列链表共用一个表头结点，在表头结点中，行、列域的值都为0或-1，故两组表头结点可以共用，即第i行链表和第i列链表共用一个表头结点，这些表头结点存放在一个顺序存储空间中。,例：如图稀疏矩阵的十字链表描述形式：,在表头结点中，行、列域的值都为0或-1，故两组表头结点可以共用，即第i行链表和第i列链表共用一个表头结点，这些表头结点存放在一个顺序存储空间中,H1,H2,H3,H4,H1,H5,H2,H3,H4,H5,2.5树与二叉树,树是一种简单的非线性结构，在树这种数据结构中，所有数据元素之间的关系具有明显的层次特性。如图，可用于描述具有层次关系的数据。如学校行政关系结构(P114图2.40),2.5.1树的基本概念,1、定义：树是由n个（n0）具有相同类型的结点元素组成的有限集合，且满足以下的条件：1)其中有一个结点无直接前驱，称为根（Root）；2)其余的结点元素可分为m个互不相交的子集T1,T2Tm，这m个子集本身又构成树，称为Root的子树。,上右图所示为一棵树，其中A为根，它有三棵子树：T1=B,E,F;T2=C,G,H,I,J;T3=D在子树T2中，C是该子树的根，它有三棵子树：T21=G；T22=H；T23=I，J；T22和T21仅有一个根结点，没有子树。,注意：（1）树的定义中n0，即没有空树的概念；（2）树的定义中采用了递归定义的方法，显示了树结构本身的这种递归的性质。,2、树的有关术语,根结点、父结点、子结点、叶子结点、内部结点或分支结点(度不为0的结点)兄弟结点(具有同一父结点的子结点称为兄弟结点)结点的度、树的度，树的深度、子树森林：是m(m0)棵树的集合有序树树中结点在同层中按从左到右有序排列，不能互换的树称有序树，反之称无序树,例:(a+(b+c/d)+(e*h-g*f(s,t,x+y)的表达式树,3、可用树型结构描述一个表达式：用操作数代表树叶，运算符代表非叶子结点，所构成的树称表达式树。编译系统中常用的表达式表示方法。表达式树是有序树,结点顺序不可更改。,+,b,+,a,-,c,d,/,+,*,e,h,+,x,y,*,g,f,t,s,树在计算机中可用多重链表表示，即每个结点有多个指针域，每个指针域指向它的一个子结点，每个结点的指针域数由该结点的度确定,4、树的存储,例：,1、定义：二叉树是由n个（n0）具有相同类型的结点元素组成的有限集合，且满足以下的条件：（1）由一个根结点和它的两棵左右子树组成；（2）其左右子树分别又构成一棵二叉树。,注意：二叉树的定义中n0，即表示有空二叉树的概念；二叉树的定义中也采用了递归定义的方法，显示了二叉树结构本身的这种递归的性质。二叉树的子树有左右之分，次序不能颠倒。,由定义知二叉树有五种基本形态，如下图所示：,2.5.2二叉树及其基本性质,空,性质1在二叉树的第K层上，最多有2k-1(1k)个结点。,性质2深度为m的二叉树最多有2m-1个结点。,2、二叉树的基本性质,性质3在任意一棵二叉树中，度为0的结点（即叶子结点）总是比度为2的结点多一个。,性质4具有n个结点的二叉树，其深度至少为log2n+1,由以上性质可以引入以下概念：,满二叉树：一棵深度为k而且有2k-1个结点的二叉树称为满二叉树。,特点：满二叉树中所有分支结点均存在左右子树；所有叶子结点均在同一层次上。,注：满二叉树必须是二叉树的每一层上的结点数都达到最大，否则就不是满二叉树。,完全二叉树：一棵深度为k且有n个结点的二叉树，当且仅当其每一个结点编号都与深度为k的满二叉树中编号为1至n的结点的编号完全一致时，该二叉树称为完全二叉树。,从满二叉树及完全二叉树定义还可以知道，满二叉树一定是一棵完全二叉树，反之完全二叉树不一定是一棵满二叉树。满二叉树的叶子结点全部在最底层，而完全二叉树的叶子结点可以分布在最下面两层。,性质5具有n个结点的完全二叉树深度为log2(n)+1或log2(n+1)。注意：x表示取不大于x的最大整数，也叫做对x下取整，x表示取不小于x的最小整数，也叫做对x上取整),性质6设完全二叉树共有n个结点。如果从根结点开始，按层序(每一层从左到右)用自然数1，2n给结点进行编号，则对于编号为k的结点有：若k=1，则该结点为根结点，若k1，则该结点的父结点编号为INT(k/2)。若2kn,则编号为k的结点的左子结点编号为2k；否则该结点无左子结点若2k+1n,则编号为k的结点的右子结点编号为2k+1;否则该结点无右子结点,由此可见，完全二叉树中各结点的编号可以唯一地反应出结点之间的逻辑关系。,2.5.3二叉树的存储结构,二叉树的顺序存储结构：对于下图中所示的完全二叉树，可以用内存空间中一组地址连续的存储单元来存放，并以一个一维数组的形式（BT12）来表示。,可见，完全二叉树中各结点间的的逻辑关系可以由其存储单元的物理地址来反映。,1,2,3,4,5,6,7,8,9,10,11,12,对于一般的二叉树，也可以按照完全二叉树的顺序结构来存储，仅需要添加一些空结点，使它变成为一棵完全二叉树。,这样做可能会带来存储空间的浪费，最坏的情况，一个深度为K,且只有K个结点的单支树，却至少需要2k-1个存储单元。,若K=4，2k-1=15K=11，2k-1=2047,1、二叉树的链式存储结构：,由二叉树的特性其链式存储结构中的每一个结点可如图所示：,指向左子结点的指针域,数据域,指向右子结点的指针域,（1）输入根节点；（2）若左子树不空，则输入左子树，否则输入一个结束符；（3）若右子树不空，则输入右子树，否则输入一个结束符；,2、二叉树链表的生成(构造二叉树)根据给定的结点在计算机内建立二叉树的链式存储结构。输入二叉树结点的方式不同，构造二叉树的算法也不同。按如下方式顺序输入给定二叉树及左右子树中各结点值；,例：,输入顺序应为：FCADBEGHP表示结束符,如输入序列为（自学）FCADBEGHP由它构造的二叉树及构造的过程为：第一个输入元素为根结点，将它作为当前结点随后输入元素为当前结点左结点，链入其左指针域，并将它作为当前结点，这个过程一直进行，直到遇结束标志(表示当前结点左子树已完)随后输入元素链入当前结点的右指针域，如此时遇结束标志，表示当前结点左右子树已链接完成，随后输入元素链入当前结点父结点右指针域，并将它作为当前结点，转。,将一个结点链入二叉树有三种情况：该结点为根结点该结点链人当前结点左指针域该结点链人当前结点右指针域如何确定输入的结点是根结点、左子树还是右子树？,用一个标志来区分：k=,例：输入序列为：FCADBEGHP用BT指向根结点，q指向当前结点，初始k=0其树构造过程如下：,(1)输入元素F,new(p),V(p)=F,L(p)=R(p)=0,因k=0,BT=p,q=p，k=1,(2)输入元素C，new(p),V(p)=C,L(p)=R(p)=0,因k=1，故L(q)=p,q=p,k=1,(3)输入元素A，new(p),V(p)=A,L(p)=R(p)=0,因k=1，故L(q)=p,q=p,k=1,(4)输入元素=当前结点A左子树完，k=2，输入下一个元素，当前A结点右子树完，退回当前结点A的父结点C，k=2，输入元素,new(p),V(p)=D,L(p)=R(p)=0,因k=2，故R(q)=p,q=p,k=1,(5)输入元素B，new(p),V(p)=B,L(p)=R(p)=0,因k=1，故L(q)=p,q=p,k=1,(6)输入元素=当前结点B左子树完，k=2，输入下一个元素，当前B结点右子树完，退回当前结点B的父结点D，k=2，输入元素，当前D结点右子树完，退回当前结点D的父结点C，C右子树已处理，退回C父结点F，k=2，输入元素Enew(p),V(p)=D,L(p)=R(p)=0,因k=2，故R(q)=p,q=p,k=1,(7)输入元素=当前结点E左子树完，k=2，输入下一个元素G，new(p),V(p)=D,L(p)=R(p)=0,因k=2，故R(q)=p,q=p,k=1,(8)输入元素H，new(p),V(p)=A,L(p)=R(p)=0,因k=1，故L(q)=p,q=p,k=1,(9)输入元素=当前结点H左子树完，k=2，输入下一个元素，当前H结点右子树完，退回当前结点H的父结点G，k=2，输入元素Pnew(p),V(p)=D,L(p)=R(p)=0,因k=2，故R(q)=p,q=p,k=1,(10)输入元素=当前结点P左子树完，k=2，输入下一个元素，当前P结点右子树完，退回当前结点P的父结点G，G右子树已处理，退回G父结点E，E右子树已处理，退回E父结点F，F右子树已处理，程序结束,FCADBEGHP,在上述二叉树的构造过程中，如何保存左子树已处理，但右子树还未处理的结点，,用栈存储右子树未处理的结点，上述二叉树构造过程为：,b=F,new(p),V(p)=b,L(p)=R(p)=0,因k=0,故BT=p,q=p,k=1,push(S,Top,p),Inputb,(2)b=C,new(p),V(p)=b,L(p)=R(p)=0,因k=1，故L(q)=p,q=p,k=1,push(S,Top,p),inputb,(3)b=A,new(p),V(p)=b,L(p)=R(p)=0,因k=1，故L(q)=p,q=p,k=1,push(S,Top,p),Inputb,(4)b=当前结点左子树完，k=2,pop(S,Top,q),Inputb(当前结点为A,即q=A)b=k=2,pop(S,Top,q),Inputb（当前结点为C）b=D,new(p),V(p)=D,L(p)=R(p)=0,因k=2，故R(q)=p,q=p,k=1,push(S,Top,p),inputb,输入FCADBEGHP初始k=0，Top=0，Inputb,(5)b=B，new(p),V(p)=b,L(p)=R(p)=0,因k=1，故L(q)=p,q=p,k=1,push(S,Top,p),Inputb,(6)b=k=2,pop(S,Top,q),Inputb(当前结点为B)b=k=2,pop(S,Top,q),Inputb（当前结点为D）b=k=2,pop(S,Top,q),Inputb（当前结点为F）b=E,new(p),V(p)=D,L(p)=R(p)=0,因k=2，故R(q)=p,q=p,k=1,push(S,Top,p),inputb这过程一直进行，直到输入为结束标志且栈为空，程序如下：,PROCEDURECreatBT(BT)Top=0Inputb;k=0;Whileb结束标志orTop0DoIfb结束标志Thennew(p);V(p)=b;L(p)=R(p)=0;Ifk=1ThenL(q)=p;q=p;k=1Ifk=2ThenR(q)=p;q=p;k=1Ifk=0ThenBT=p;q=p;k=1Push(S,Top,p)ElsePop(S,Top,q);k=2InputbRe