公共基础课件(二).ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,全国计算机等级考试,二级公共基础,计算机科学与技术系,董 再 秀,witsdong,1数据的逻辑结构,2、数据的存储结构,3、,数据的运算,：检索、排序、插入、删除、修改等。,A,线性结构,B,非线性结构,A,顺序存储,B,链式存储,线性表,栈,队,树形结构,图形结构,数据结构的三个方面,(亦称物理结构),栈,栈是一种特殊的线性表。其特殊性在于限定插入和删除数据元素的操作只能在线性表的表尾端进行。如下所示：,进行插入和删除的表尾端是浮动端，通常被称为,栈顶,，,a,n,为栈顶元素，并用一个“栈顶指针”指示；而表头端是固定端，通常被称为,栈底，,a,1,为栈底元素。我们经常将栈用下图的形式描述：,a,1,a,2,a,3,.,a,n,插入和删除端,栈的特征,结论：后进先出（,Last In First Out），,简称为,LIFO,线性表。,举例1：家里吃饭的碗，通常在洗干净后一个一个地落在一起存放，在使用时，若一个一个地拿，一定最先拿走最上面的那只碗，而最后拿出最下面的那只碗。,举例2：在建筑工地上，使用的砖块从底往上一层一层地码放，在使用时，将从最上面一层一层地拿取。,举例,3,：子弹夹。,栈的基本运算,（1）插入元素称为,入栈,运算；,（2）删除元素称为,退栈,运算；,（3）,读栈顶元素,是将栈顶元素赋给一个指定的变量，此时指针无变化,bottom,A,B,C,D,E,top,top=0,栈空,Top=m,栈满 （,m,为栈的最大容量）,bottom,top,B,A,1,2,3,4,5,1,2,3,4,5,bottom,top,B,A,1,2,3,4,5,C,D,1.4.2 队列及其基本运算,队列(,Queue),也是一种运算受限的,线性表,。它只允许在表的一端进行插入，而在另一端进行删除。允许删除的一端称为,队头,(,front)，,允许插入的一端称为,队尾,(,rear)。,例如：排队购物。操作系统中的作业排队。先进入队列的成员总是先离开队列。因此队列亦称作先进先出(,First In First Out),的线性表，简称,FIFO,表。,当队列中没有元素时称为,空队列,。在空队列中依次加入元素,a,1,a,2,a,n,之后，,a,1,是,队头元素,，,a,n,是,队尾元素,。显然退出队列的次序也只能是,a,1,a,2,a,n,，,也就是说队列的修改是依先进先出的原则进行的。,下图是队列的示意图：,a,1,a,2,a,n,出队,入队,队列的顺序存储结构,front=-1,rear=-1,1,2,3,4,5,0,队空,1,2,3,4,5,0,front,J1,J1,J3,入队,J1,J2,J3,rear,rear,1,2,3,4,5,0,J4,J5,J6,入队,J4,J5,J6,front,设两个指针,front,rear,约定：,rear,指示队尾元素；,front,指示队头元素前一位置,初值,front=rear=-1,空队列条件：,front=rear,入队列：,sq+rear=x;,出队列：,x=sq+front;,rear,rear,front,rear,1,2,3,4,5,0,J1,J2,J3,出队,J1,J2,J3,front,front,front,实现：用一维数组实现,sqM,存在问题,设数组维数为,M，,则：,当,front=-1,rear=M-1,时，再有元素入队发生溢出真溢出,当,front,-1,rear=M-1,时，再有元素入队发生溢出假溢出,解决方案,队首固定，每次出队剩余元素向下移动浪费时间,循环队列,基本思想：把队列设想成环形，让,sq0,接在,sqM-1,之后，若,rear+1=M,则令,rear=0;,1,M,2,front,rear,.,.,入队,运算是指在循环队列的队尾加入一个新元素,(1),首先将队尾指针进一,即,rear=rear+1,并当,rear=m+1,时置,rear=1,。,(2),然后将新元素插入到队尾指针指向的位置。,出,队,运算是指在循环队列的排头位置退出一个元素并赋给指定变量。,(1),首先将排头指针进一，即,front=front+1,并且当,front=m+1,时置,front=1,(2),然后将排头指针指向的元素赋值给指定变量,1,2,3,4,5,6,rear,front,J4,J5,J6,1,2,3,4,5,6,rear,front,J9,J8,J7,J4,J5,J6,1,2,3,4,5,6,rear,front,初始状态,J4,J5,J6,出队,J7,J8,J9,入队,队空：,front=rear,队满：,front=rear,解决方案：,另外,设一个标志,以区别队空、队满,S=0 (,队空,),S=1 (,队满,),队列是指允许在一端（队尾）进入插入，而在另一端（队头）进行删除的线性表。,Rear,指针指向队尾，,front,指针指向队头。,队列是“先进先出”（,FIFO）,或“后进后出”（,LILO）,的线性表。,队列运算包括,（1）入队运算：从队尾插入一个元素；,（2）退队运算：从队头删除一个元素。,循环队列：,s=0,表示队列空,s=1,且,front=rear,表示队列满,队列特征总结,1.5.1 线性链表的基本概念,线性表顺序存储结构的特点：是一种简单、方便的存储方式。它要求线性表的数据元素依次存放在连续的存储单元中，从而利用数据元素的存储顺序表示相应的逻辑顺序，这种存储方式属于静态存储形式。,线性表顺序存储结构暴露的问题,在做插入或删除元素的操作时，会产生大量的数据元素移动；,对于长度变化较大的线性表，要一次性地分配足够的存储空间，但这些空间常常又得不到充分的利用；,线性表的容量难以扩充。,1.5 线性链表,线性表的链式存储结构,线性表的链式存储结构：,指用一组任意的存储单元（可以连续，也可以不连续）存储线性表中的数据元素。,链表中结点的逻辑次序和物理次序不一定相同,为了存储线性表中的每一个元素，一方面要存储数据元素的值，另一方面要存储各数据元素之间的前后件关系,数据结构中的每一个元素对应于一个存储单元，这种存储单元称为存储结点，简称结点。,存储空间中的每一个结点分两部分：一部分用于存储元素的值，称数据域；另一部分用于存放下一个数据元素的 存储序号（存储结点的地址），即指向后件结点，称为指针域。,data,Next/link,指针域，用来存放结点的直接后继的地址,数据域，用来存放结点的值,例如：线性表（,a,b,c,d),在链式存储结构中，存储数据结构的存储空间可以不连续，各数据结点的存储顺序与数据元素之间的逻辑关系可以不一致，而数据元素之间的逻辑关系是由指针域来确定的。,链式存储方式即可用于表示线性结构，也可用于表示非线性结构。,head,d,c,b,a,线性（单）链表的逻辑结构,null,其中，,head,是头指针，它指向单链表中的第一个结点，这是单链表操作的入口点。由于最后一个结点没有直接后继结点，所以，它的指针域放入一个特殊的值,NULL。NULL,值在图示中常用（）符号表示。,L,双向链表：,R,110,hat 200,130,cat 135,135,eat 170,160,mat NULL,165,bat 130,170,fat 110,200,jat,205,205,lat 160,165,head,头指针,数据域,指针域,例如：线性表,（,bat,cat,eat,fat,hat,jat,lat,mat,）,bat,cat,eat,mat,head,链式存储结构的特点,（1）线性表中的数据元素在存储单元中的存放顺序与逻辑顺序不一定一致；,（2）在对线性表操作时，只能通过头指针进入链表，并通过每个结点的指针域向后扫描其余结点，这样就会造成寻找第一个结点和寻找最后一个结点所花费的时间不等，具有这种特点的存取方式被称为顺序存取方式。,1.5.2 线性链表的基本运算,1、在线性链表中查找指定元素,在对线性链表进行插入或删除的运算中，总是首先需要找到插入或删除的位置，这就需要对线性链表进行扫描查找，要找到线性链表中指定值的前一个结点。,查找：查找单链表中是否存在结点,X，,若有则返回指向,X,结点的指针；否则返回,NULL,算法评价,p,a,b,x,s,插入：在线性表两个数据元素,a,和,b,间插入,x，,已知,p,指向,a,s-link=p-link;,p-link=s;,算法评价,p,a,b,c,删除：删除链表中,b,结点，已知,p,指向,a,结点,p-link=p-link-link,算法评价,若是栈中元素的数目变化范围较大或不清楚栈元素的数目，就应该考虑使用链式存储结构。,人们将用链式存储结构表示的栈称作“链栈”。链栈通常用一个无头结点的单链表表示。如图所示。,由于栈的插入删除操作只能在一端进行，而对于单链表来说，在首端插入删除结点要比尾端相对地容易一些，所以，我们将单链表的首端作为栈顶端，即将单链表的头指针作为栈顶指针。,栈的链式存储,top,队列的链式存储结构简称为链队列，它是限制仅在表头删除和表尾插入的单链表。,front,rear,队列的链式存储,循环链表是表中最后一个结点的指针指向头结点，使链表构成环状,特点：从表中任一结点出发均可找到表中其他结点，提高查找效率,操作与单链表基本一致,，它可以使空表和非空表的运算统一,单链表,p,或,p-link=NULL,循环链表,p,或,p-link=H,h,h,空表,1.5.2 循环链表的基本运算,例题讲解,线性表的顺序存储结构和线性表的链式存储结构分别是,A),顺序存取的存储结构、顺序存取的存储结构,B),随机存取的存储结构、顺序存取的存储结构,C),随机存取的存储结构、随机存取的存储结构,D),任意存取的存储结构、任意存取的存储结构,链表不具有的特点是,A),不必事先估计存储空间,B),可随机访问任一元素,C),插入删除不需要移动元素,D),所需空间与线性表长度成正比,线性表若采用链式存储结构时，要求内存中可用存储单元的地址,A),必须是连续的,B),部分地址必须是连续的,C),一定是不连续的,D),连续不连续都可以,栈和队列的共同特点是,A),都是先进先出,B),都是先进后出,C),只允许在端点处插入和删除元素,D),没有共同点,如果进栈序列为,e1,e2,e3,e4，,则可能的出栈序列是,A)e3,e1,e4,e2 B)e2,e4,e3,e1,C)e3,e4,e1,e2D),任意顺序,一些重要的程序语言(如,C,语言和,Pascal,语言)允许过程的递归调用。而实现递归调用中的存储分配通常用,A),栈,B),堆,C),数组,D),链表,当循环队列非空且队尾指针等于队头指针时，说明循环队列已满，不能进行入队运算。这种情况称为,【2】,。,栈底至栈顶依次存放元素,A、B、C、D，,在第五个元素,E,入栈前，栈中元素可以出栈，则出栈序列可能是,A)ABCED B)DCBEA C)DBCEA D)CDABE,栈通常采用的两种存储结构是,A),顺序存储结构和链表存储结构,B),散列方式和索引方式,C),链表存储结构和数组,D),线性存储结构和非线性存储结构,栈和队列通常采用的存储结构是,【1】,。,下列数据结构中，按先进后出原则组织数据的是,A),线性链表,B),栈,C),循环链表,D),顺序表,由两个栈共享一个存储空间的好处是,A),减少存取时间，降低下溢发生的机率,B),节省存储空间，降低上溢发生的机率,C),减少存取时间，降低上溢发生的机率,D),节省存储空间，降低下溢发生的机率,下列关于栈的叙述中正确的是,）在栈中只能插入数据,B）,在栈中只能删除数据,C）,栈是先进先出的线性表,D）,栈是后进先出的线性表,下列关于队列的叙述中正确的是,）在队列中只能插入数据,B）,在队列中只能删除数据,C）,队列是先进先出的线性表,D）,队列是后进先出的线性表,1.6 树与二叉树,树是一种简单的非线性结构，所有元素之间具有明显的层次特性。,例如家谱、行政组织机构都可用树形象地表示,在树结构中，每一个结点只有一个前件，称为,父结点,，没有前件的结点只有一个，称为树的,根结点,，简称树的根。每一个结点可以有多个后件，称为该结点的,子结点,。没有后件的结点称为,叶子结点,。,一棵非空树是由若干棵子树构成的，而子树又可由若干棵更小的子树构成。,本例是有13个结点的树，其中,A,是根，其余结点分成3个子集：,T,1,、,T,2,、,T,3。,都是根,A,的子树，且本身也是一棵树。例如：,T,1,其根为,B，,两棵子树为,T,11,=F,，,T,12,=E,K,L，,T,12,又是一棵子树，树根为,F，K,和,L,是,E,的两个互不相交的子集。,结点：,数据元素的内容及其指向其子树根的分支统称为结点。,结点的度,（,Degree):,结点的分支数，即结点拥有的子树数。,终端结点,（叶子,leaf）:,度为0的结点。,非终端结点,:度不为0的结点。,结点的层次,:树中根结点的层次为1，根结点子树的根为第2 层，以此类推。,树的度,:树中所有结点度的最大值。,树的深度,:树中所有结点层次的最大值。,有序树、无序树,:如果树中每棵子树从左向右的排列拥有一定的顺序，不得互换，则称为有序树，否则称为无序树。,术语,1.6.2 二叉树及其基本性质,二叉树是树形结构的一个重要类型,。特征：,（1）,每个结点最多有两棵子树；,（2）,子树有左右之分。,G H,D E F,B C,A,(,a),(,b),(,c),(,d),(,e),(,a),空树 (,b),只有根结点的二叉树 (,c),右子树为空的二叉树 (,d),左子树为空的二叉树 (,e),左、右子树均非空的二叉树,二叉树的5种形态,二叉树具有下列5个重要的性质。,【性质1】,在二叉树的第,i,层上最多有2,i-1,个结点（,i1）。,二叉树的第1层只有一个根结点，所以，,i=1,时，,2,i-1,=2,1-1,=2,0,=1,成立。,假设,对所有的,j，1ji,成立，即第,j,层上最多有2,j-1,个结点成立。,若,j=i-1,，,则第,j,层上最多有2,j-1,=2,i-2,个结点。由于在二叉树中，每个结点的度最大为2，所以可以推导出第,i,层最多的结点个数就是第,i-1,层最多结点个数的,2倍,，即2,i-2,*2=2,i-1,。,二叉树的性质,【性质2】,深度为,K,的二叉树最多有2,K,-1,个结点(,K1）。,由性质1可以得出，1至,K,层各层最多的结点个数分别为：2,0,2,1,2,2,2,3,.,2,K-1,。,这是一个以2为比值的等比数列，前,n,项之和的计算公式为：,二叉树的性质,其中,a,1,为第一项，,a,n,为第,k,项，,q,为比值。可以得到，该数列前,K,项之和为：,【性质3】,对于任意一棵二叉树,BT，,如果度为0的结点（叶子）个数为,n,0,，,度为2的结点个数为,n,2,，,则,n,0,=n,2,+1。,证明：,1.假设度为1的结点个数为,n,1,，,结点总数为,n。,因为在二叉树中，所有结点的度均小于或等于2，所以结点总数为：,n=n,0,+n,1,+n,2,（1）,二叉树的性质,2.,设,B,为二叉树中的分支数,从,入支,的角度看，即,前驱结点,的角度看，二叉树中，除根结点之外，其余每个结点都有一个且只有一个前驱结点，即有一个从上向下的分支指向(即占有一个分支)，所以，总的结点个数,n,与分支数,B,之间的关系为：,n=B+1。（2）,从,出支,的角度看，即,后继结点,的角度看，因为在二叉树中，度为0的结点没有后继结点，即不占分支，度为1的结点有一个后继结点，产生1个分支，度为2的结点产生2个分支，所以分支数,B,可以表示为：,B=n,1,+2n,2,。（3）,将此式代入上式，得：,n=n,1,+2n,2,+1 （4）,用（1）式减去（4）式，并经过调整后得到：,n,0,=n,2,+1。,满二叉树,如果一个深度为,K,的二叉树拥有2,K,-1,个结点，则将它称为满二叉树。,特点：每一层上的结点数都是最大结点数,8 9,10 11 12 13 14 15,4 5 6 7,2 3,1,完全二叉树,有一棵深度为,h，,具有,n,个结点的二叉树，若将它与一棵同深度的满二叉树中的所有结点按从上到下，从左到右的顺序分别进行编号，且该二叉树中的每个结点分别与满二叉树中编号为1,n,的结点位置一一对应，则称这棵二叉树为完全二叉树。,就说从满二叉树里，最下一层的叶子，如果是从右往左拿掉叶子，不论多少，都是完全的。,从完全二叉树的定义可见，其叶子结点只能在最下面两层上，且从左到右的排满,8 9 10 11 12,4 5 6 7,2 3,1,7 8 9,4 5 6,2 3,1,4 5 6,2 3,1,完全二叉树的特点：,（1）叶子结点只可能在层次最大的两层上出现,（2）对任意结点，若其右分支下的子孙的最大层次是,p，,则其左分支下的子孙的最大层次必是,p,或,p+1,【性质4】,具有,n,个结点的,完全二叉树,的深度为,log,2,n,+1。,其中，,log,2,n,的结果是不大于,log,2,n,的最大整数。,证明：假设具有,n,个结点的完全二叉树的深度为,K，,第,k-1,层一定是满二叉树，则根据性质2可以得出：,2,K-1,-1n2,K,-1,将不等式两端加1得到：2,K-1,n2,K,将不等式中的三项同取以2为底的对数，并经过化简后得到：,K-1log,2,n 1,其双亲结点的编号为,i/2,。,（2）,如果2,in，,则结点,i,没有左孩子（结点,i,为叶子结点）；否则其左孩子结点的编号为2,i。,（3）,如果2,i+1n，,则结点,i,没有右孩子；否则其右孩子结点的编号为2,i+1。,2,i+2,2,i 2i+1 2i+2 2i+3 i+1 2i 2i+1,i,i i+1,1.6.3 二叉树的存储结构,二叉树通常使用链式存储结构。,常见的二叉树结点结构如下所示：,G H,D E F,B C,A,G H ,D E F ,B C,A,BT,1.6.4 二叉树的遍历,二叉树是一种非线性的数据结构，在对它进行操作时，总是需要逐一对每个数据元素实施操作，这样就存在一个操作顺序问题，由此提出了二叉树的遍历操作。所谓遍历二叉树就是按某种顺序访问二叉树中的每个结点一次且仅一次的过程。这里的访问可以是输出、比较、更新、查看元素内容等等各种操作。,二叉树的遍历方式为：按根、左子树和右子树三个部分进行访问；,遍历二叉树的顺序存在下面三种顺序,DLR、LDR,和,LRD，,根据根访问的位置不同分别被称为,先序,遍历、,中序,遍历和,后序,遍历。,下面我们将分别进行讨论。,（1）先序遍历,若二叉树为空，则结束遍历操作；否则,访问根结点；,先序遍历左子树；,先序遍历右子树。,（2）中序遍历,若二叉树为空，则结束遍历操作；否则,中序遍历左子树；,访问根结点；,中序遍历右子树。,（3）后序遍历,若二叉树为空，则结束遍历操作；否则,后序遍历左子树；,后序遍历右子树；,访问根结点。,G H,B C,A,D E F,先序序列：,ABDGCEFH,中序序列：,DGBAECHF,后序序列：,GDBEHFCA,下面是一棵二叉树及其经过三种遍历得到的相应序列。,例题讲解,具有3个结点的二叉树有,A)2,种形态,B)4,种形态,C)7,种形态,D)5,种形态,设有下列二叉树：,对此二叉树前序遍历的结果为,A)ZBTTCPXA B)ATBZXCTP C)ZBTACTXP D)ATBZXCPT,设一棵二叉树中有3个叶子结点，有8个度为1的结点，则该二叉树中总的结点数为,A)12 B)13 C)14D)15,设有下列二叉树：,对此二叉树的中序遍历的结果为,A)ABCDEF B)DBEAFC C)ABDECF D)DEBFCA,已知二叉树后序遍历序列是,dabec,，,中序遍历序列是,debac,，,它的前序遍历序列是,cedba,A),acbed,B),decab,C),deabc,D),cedba,已知一棵二叉树前序遍历和中序遍历分别为,ABDEGCFH,和,DBGEACHF，,则该二叉树的后序遍历为,DGEBHFCA,A)GEDHFBCA B)DGEBHFCA,C)ABCDEFGH D)ACBFEDHG,树是结点的集合，它的根结点数目是,A),有且只有1,B)1,或多于1,C)0,或1,D),至少2,在深度为5的满二叉树中，叶子结点的个数为,A)32B)31 C)16 D)15,若某二叉树的前序遍历访问顺序是,abdgcefh,，,中序遍历访问顺序是,dgbaechf,，,则其后序遍历的结点访问顺序是,A),bdgcefha,B),gdbecfha,C),bdgaechf,D),gdbehfca,在树结构中，树根结点没有【1】。,下列叙述中正确的是,A),线性表是线性结构,B),栈与队列是非线性结构,C),线性链表是非线性结构,D),二叉树是线性结构,设树,T,的深度为4,其中度为1、2、3、4的结点个数分别为4、2、1、1。则,T,中的叶子结点数为,A）8 B）7 C）6 D）5,补充树的性质：结点数为所有结点的度数之和加,1,设一棵完全二叉树共有700个结点，则该二叉树中有（,350,）个叶子结点。,可以算出，这棵二叉树共十层，,1-9,层的节点个数为,29-1=511,个,所以最后一层的节点个数为,700-511=189,个,189div2=95,那么倒数第二层的叶结点个数即是,2(9-1)-95=161,个 所以所有的叶结点个数即为,:189+161=350,个,在一个容量为15的循环队列中，若头指针,front=6，,尾指针,rear=9，,则该循环队列中共有（）个元素。,设一棵二叉树的中序遍历结果为,DBEAFC，,前序遍历结果为,ABDECF，,则后序遍历结果为（,DEBFCA,）。,