《公共基础课件二.ppt》由会员分享，可在线阅读，更多相关《公共基础课件二.ppt（72页珍藏版）》请在三一办公上搜索。
1、全国计算机等级考试二级公共基础,计算机科学与技术系董 再 秀,1数据的逻辑结构,2、数据的存储结构,3、数据的运算：检索、排序、插入、删除、修改等。,A线性结构,B非线性结构,A 顺序存储,B 链式存储,线性表,栈,队,树形结构,图形结构,数据结构的三个方面,(亦称物理结构),栈,栈是一种特殊的线性表。其特殊性在于限定插入和删除数据元素的操作只能在线性表的表尾端进行。如下所示：进行插入和删除的表尾端是浮动端，通常被称为栈顶，an 为栈顶元素，并用一个“栈顶指针”指示；而表头端是固定端，通常被称为栈底，a1为栈底元素。我们经常将栈用下图的形式描述：,a1,a2,a3,.,an 插入和删除端,栈的
2、特征,结论：后进先出（Last In First Out），简称为LIFO线性表。举例1：家里吃饭的碗，通常在洗干净后一个一个地落在一起存放，在使用时，若一个一个地拿，一定最先拿走最上面的那只碗，而最后拿出最下面的那只碗。举例2：在建筑工地上，使用的砖块从底往上一层一层地码放，在使用时，将从最上面一层一层地拿取。举例3：子弹夹。,栈的基本运算,（1）插入元素称为入栈运算；（2）删除元素称为退栈运算；（3）读栈顶元素是将栈顶元素赋给一个指定的变量，此时指针无变化,top=0 栈空Top=m 栈满（m为栈的最大容量）,B,A,C,D,1.4.2 队列及其基本运算,队列(Queue)也是一种运算受限
3、的线性表。它只允许在表的一端进行插入，而在另一端进行删除。允许删除的一端称为队头(front)，允许插入的一端称为队尾(rear)。例如：排队购物。操作系统中的作业排队。先进入队列的成员总是先离开队列。因此队列亦称作先进先出(First In First Out)的线性表，简称FIFO表。当队列中没有元素时称为空队列。在空队列中依次加入元素a1,a2,an之后，a1是队头元素，an是队尾元素。显然退出队列的次序也只能是a1,a2,an，也就是说队列的修改是依先进先出的原则进行的。,下图是队列的示意图：a1a2an,出队,入队,队列的顺序存储结构,J1,J2,J3,设两个指针front,rear
4、,约定：rear指示队尾元素；front指示队头元素前一位置初值front=rear=-1,空队列条件：front=rear入队列：sq+rear=x;出队列：x=sq+front;,实现：用一维数组实现sqM,存在问题设数组维数为M，则：当front=-1,rear=M-1时，再有元素入队发生溢出真溢出当front-1,rear=M-1时，再有元素入队发生溢出假溢出解决方案队首固定，每次出队剩余元素向下移动浪费时间循环队列基本思想：把队列设想成环形，让sq0接在sqM-1之后，若rear+1=M,则令rear=0;,入队运算是指在循环队列的队尾加入一个新元素(1)首先将队尾指针进一,即rea
5、r=rear+1,并当rear=m+1时置rear=1。(2)然后将新元素插入到队尾指针指向的位置。,出队运算是指在循环队列的排头位置退出一个元素并赋给指定变量。(1)首先将排头指针进一，即front=front+1,并且当front=m+1时置front=1(2)然后将排头指针指向的元素赋值给指定变量,队空：front=rear队满：front=rear,解决方案：另外设一个标志以区别队空、队满S=0(队空)S=1(队满),队列是指允许在一端（队尾）进入插入，而在另一端（队头）进行删除的线性表。Rear指针指向队尾，front指针指向队头。队列是“先进先出”（FIFO）或“后进后出”（LIL
6、O）的线性表。队列运算包括（1）入队运算：从队尾插入一个元素；（2）退队运算：从队头删除一个元素。循环队列：s=0表示队列空 s=1且front=rear表示队列满,队列特征总结,1.5.1 线性链表的基本概念线性表顺序存储结构的特点：是一种简单、方便的存储方式。它要求线性表的数据元素依次存放在连续的存储单元中，从而利用数据元素的存储顺序表示相应的逻辑顺序，这种存储方式属于静态存储形式。线性表顺序存储结构暴露的问题在做插入或删除元素的操作时，会产生大量的数据元素移动；对于长度变化较大的线性表，要一次性地分配足够的存储空间，但这些空间常常又得不到充分的利用；线性表的容量难以扩充。,1.5 线性链
7、表,线性表的链式存储结构,线性表的链式存储结构：指用一组任意的存储单元（可以连续，也可以不连续）存储线性表中的数据元素。链表中结点的逻辑次序和物理次序不一定相同,为了存储线性表中的每一个元素，一方面要存储数据元素的值，另一方面要存储各数据元素之间的前后件关系数据结构中的每一个元素对应于一个存储单元，这种存储单元称为存储结点，简称结点。存储空间中的每一个结点分两部分：一部分用于存储元素的值，称数据域；另一部分用于存放下一个数据元素的 存储序号（存储结点的地址），即指向后件结点，称为指针域。,指针域，用来存放结点的直接后继的地址,数据域，用来存放结点的值,例如：线性表（a,b,c,d),在链式存储
8、结构中，存储数据结构的存储空间可以不连续，各数据结点的存储顺序与数据元素之间的逻辑关系可以不一致，而数据元素之间的逻辑关系是由指针域来确定的。链式存储方式即可用于表示线性结构，也可用于表示非线性结构。,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,17
9、0 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、在线性链表中查找指定元素在对线性链表进行插入或删除的
10、运算中，总是首先需要找到插入或删除的位置，这就需要对线性链表进行扫描查找，要找到线性链表中指定值的前一个结点。,查找：查找单链表中是否存在结点X，若有则返回指向X结点的指针；否则返回NULL,算法评价,插入：在线性表两个数据元素a和b间插入x，已知p指向a,s-link=p-link;,p-link=s;,算法评价,p,a,b,c,删除：删除链表中b结点，已知p指向a结点,p-link=p-link-link,算法评价,若是栈中元素的数目变化范围较大或不清楚栈元素的数目，就应该考虑使用链式存储结构。人们将用链式存储结构表示的栈称作“链栈”。链栈通常用一个无头结点的单链表表示。如图所示。由于栈的
11、插入删除操作只能在一端进行，而对于单链表来说，在首端插入删除结点要比尾端相对地容易一些，所以，我们将单链表的首端作为栈顶端，即将单链表的头指针作为栈顶指针。,栈的链式存储,队列的链式存储结构简称为链队列，它是限制仅在表头删除和表尾插入的单链表。,front,rear,队列的链式存储,循环链表是表中最后一个结点的指针指向头结点，使链表构成环状特点：从表中任一结点出发均可找到表中其他结点，提高查找效率操作与单链表基本一致，它可以使空表和非空表的运算统一单链表p或p-link=NULL循环链表p或p-link=H,1.5.2 循环链表的基本运算,例题讲解,线性表的顺序存储结构和线性表的链式存储结构分
12、别是 A)顺序存取的存储结构、顺序存取的存储结构 B)随机存取的存储结构、顺序存取的存储结构 C)随机存取的存储结构、随机存取的存储结构 D)任意存取的存储结构、任意存取的存储结构链表不具有的特点是A)不必事先估计存储空间 B)可随机访问任一元素C)插入删除不需要移动元素 D)所需空间与线性表长度成正比,线性表若采用链式存储结构时，要求内存中可用存储单元的地址 A)必须是连续的 B)部分地址必须是连续的 C)一定是不连续的 D)连续不连续都可以栈和队列的共同特点是 A)都是先进先出 B)都是先进后出 C)只允许在端点处插入和删除元素 D)没有共同点,如果进栈序列为e1,e2,e3,e4，则可能
13、的出栈序列是 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)链表存储结构和
14、数组 D)线性存储结构和非线性存储结构栈和队列通常采用的存储结构是【1】。下列数据结构中，按先进后出原则组织数据的是 A)线性链表 B)栈 C)循环链表 D)顺序表,由两个栈共享一个存储空间的好处是 A)减少存取时间，降低下溢发生的机率 B)节省存储空间，降低上溢发生的机率 C)减少存取时间，降低上溢发生的机率 D)节省存储空间，降低下溢发生的机率下列关于栈的叙述中正确的是）在栈中只能插入数据 B）在栈中只能删除数据C）栈是先进先出的线性表 D）栈是后进先出的线性表,下列关于队列的叙述中正确的是）在队列中只能插入数据 B）在队列中只能删除数据C）队列是先进先出的线性表 D）队列是后进先出的线性
15、表,1.6 树与二叉树,树是一种简单的非线性结构，所有元素之间具有明显的层次特性。例如家谱、行政组织机构都可用树形象地表示,在树结构中，每一个结点只有一个前件，称为父结点，没有前件的结点只有一个，称为树的根结点，简称树的根。每一个结点可以有多个后件，称为该结点的子结点。没有后件的结点称为叶子结点。一棵非空树是由若干棵子树构成的，而子树又可由若干棵更小的子树构成。,本例是有13个结点的树，其中A是根，其余结点分成3个子集：T1、T2、T3。都是根A的子树，且本身也是一棵树。例如：T1 其根为B，两棵子树为 T11=F，T12=E,K,L，T12 又是一棵子树，树根为F，K 和 L是E的两个互不相
16、交的子集。,结点：数据元素的内容及其指向其子树根的分支统称为结点。结点的度（Degree):结点的分支数，即结点拥有的子树数。终端结点（叶子leaf）:度为0的结点。非终端结点:度不为0的结点。结点的层次:树中根结点的层次为1，根结点子树的根为第2 层，以此类推。树的度:树中所有结点度的最大值。树的深度:树中所有结点层次的最大值。有序树、无序树:如果树中每棵子树从左向右的排列拥有一定的顺序，不得互换，则称为有序树，否则称为无序树。,术语,1.6.2 二叉树及其基本性质,二叉树是树形结构的一个重要类型。特征：（1）每个结点最多有两棵子树；（2）子树有左右之分。,G H,D E F,B C,A,(
17、a),(b),(c),(d),(e),(a)空树(b)只有根结点的二叉树(c)右子树为空的二叉树(d)左子树为空的二叉树(e)左、右子树均非空的二叉树,二叉树的5种形态,二叉树具有下列5个重要的性质。【性质1】在二叉树的第i层上最多有2i-1个结点（i1）。二叉树的第1层只有一个根结点，所以，i=1时，2i-1=21-1=20=1成立。假设对所有的j，1ji成立，即第j层上最多有2j-1个结点成立。若j=i-1，则第j层上最多有2j-1=2i-2个结点。由于在二叉树中，每个结点的度最大为2，所以可以推导出第i层最多的结点个数就是第i-1层最多结点个数的2倍，即2i-2*2=2i-1。,二叉树的
18、性质,【性质2】深度为K的二叉树最多有2K-1个结点(K1）。由性质1可以得出，1至K层各层最多的结点个数分别为：20,21,22,23,.,2K-1。这是一个以2为比值的等比数列，前n项之和的计算公式为：,二叉树的性质,其中 a1为第一项，an为第k项，q为比值。可以得到，该数列前K项之和为：,【性质3】对于任意一棵二叉树BT，如果度为0的结点（叶子）个数为n0，度为2的结点个数为n2，则n0=n2+1。证明：1.假设度为1的结点个数为n1，结点总数为n。因为在二叉树中，所有结点的度均小于或等于2，所以结点总数为：n=n0+n1+n2（1）,二叉树的性质,2.设B为二叉树中的分支数从入支的角
19、度看，即前驱结点的角度看，二叉树中，除根结点之外，其余每个结点都有一个且只有一个前驱结点，即有一个从上向下的分支指向(即占有一个分支)，所以，总的结点个数n与分支数B之间的关系为：n=B+1。（2）,从出支的角度看，即后继结点的角度看，因为在二叉树中，度为0的结点没有后继结点，即不占分支，度为1的结点有一个后继结点，产生1个分支，度为2的结点产生2个分支，所以分支数B可以表示为：B=n1+2n2。（3）将此式代入上式，得：n=n1+2n2+1（4）用（1）式减去（4）式，并经过调整后得到：n0=n2+1。,满二叉树,如果一个深度为K的二叉树拥有2K-1个结点，则将它称为满二叉树。特点：每一层上
20、的结点数都是最大结点数,完全二叉树,有一棵深度为h，具有n个结点的二叉树，若将它与一棵同深度的满二叉树中的所有结点按从上到下，从左到右的顺序分别进行编号，且该二叉树中的每个结点分别与满二叉树中编号为1n的结点位置一一对应，则称这棵二叉树为完全二叉树。就说从满二叉树里，最下一层的叶子，如果是从右往左拿掉叶子，不论多少，都是完全的。从完全二叉树的定义可见，其叶子结点只能在最下面两层上，且从左到右的排满,完全二叉树的特点：（1）叶子结点只可能在层次最大的两层上出现（2）对任意结点，若其右分支下的子孙的最大层次是p，则其左分支下的子孙的最大层次必是p 或p+1,【性质4】具有n个结点的完全二叉树的深度
21、为 log2n+1。其中，log2n 的结果是不大于log2n的最大整数。证明：假设具有n个结点的完全二叉树的深度为K，第k-1层一定是满二叉树，则根据性质2可以得出：2K-1-1n2K-1将不等式两端加1得到：2K-1n2K将不等式中的三项同取以2为底的对数，并经过化简后得到：K-1log2nK 因为k-1和k是两个相邻的整数 由此可以得到：log2n=K-1。整理后得到：K=log2n+1。,【性质5】对于有n个结点的完全二叉树中的所有结点按从上到下，从左到右的顺序进行编号，则对任意一个结点i（1in），都有：（1）如果i=1，则结点i是这棵完全二叉树的根，没有双亲；如果i 1其双亲结点的
22、编号为 i/2。（2）如果2in，则结点i没有左孩子（结点i为叶子结点）；否则其左孩子结点的编号为2i。（3）如果2i+1n，则结点i没有右孩子；否则其右孩子结点的编号为2i+1。,2i+2,2i 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 二叉树的遍历,二叉树是一种非线性的数据结构，在对它进行操作时，总是需要逐一对每个数据元素实施操作，这样就存在一个操作顺序问题，由此提出了二叉树的遍历操作。所谓遍
23、历二叉树就是按某种顺序访问二叉树中的每个结点一次且仅一次的过程。这里的访问可以是输出、比较、更新、查看元素内容等等各种操作。,二叉树的遍历方式为：按根、左子树和右子树三个部分进行访问；遍历二叉树的顺序存在下面三种顺序DLR、LDR和LRD，根据根访问的位置不同分别被称为先序遍历、中序遍历和后序遍历。下面我们将分别进行讨论。,（1）先序遍历若二叉树为空，则结束遍历操作；否则访问根结点；先序遍历左子树；先序遍历右子树。（2）中序遍历若二叉树为空，则结束遍历操作；否则中序遍历左子树；访问根结点；中序遍历右子树。,（3）后序遍历若二叉树为空，则结束遍历操作；否则后序遍历左子树；后序遍历右子树；访问根结
24、点。,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
25、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)有且只有1B)1或多于1 C)0或1D)至少2,在深度为5的满二叉树中，叶子结点的个数为 A)32B)31 C)16 D)15 若某二叉树的前序遍历访问顺序是abdgcefh，中序遍历
26、访问顺序是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）。,
