全国计算机等级考试四级考试要点(4)

卫文 1172分享

  (2)其余结点分为两个互不相交的集合T 1 、T 2 ,T 1 与T 2 都是二叉树,并且T 1 与T 2 有顺序关系(T 1 在T 2 之前),它们分别称为根的左子树和右子树。

  二叉树是一类与树不同的树形结构。它们的区别是:第一,二叉树可以是空集,这种二叉树称为空二叉树。第二,二叉树的任一结点都有两棵子树(当然,它们中的任何一个可以是空子树),并且这两棵子树之间有次序关系,也就是说,它们的位置不能交换。相应地,二叉树上任一结点左、右子树的根分别称为该结点的左孩子和右孩子。另外,二叉树上任一结点的度定义为该结点的孩子数(即非空子树数)。除这个几个术语之外,树的其它术语也适用于二叉树。

  特别值得注意的是,由于二叉树上任一结点的子树有左、右之分,因此即使一结点只有一棵非空子树,仍须区别它是该结点的左子树还是右子树,这是与树不同的。

  (2)二叉树的性质

  在某些情况下,了解二叉树的下列性质是有帮助的。

  4.二叉树的存储结构

  二叉树通常有两类存储结构,顺序存储结构和链式存储结构。

  (1)二叉树的链式存储结构

  二叉树有不同的链式存储结构,其中最常用的是二叉树链表与三叉链表。

  其中,data域称为数据域,用于存储二叉树结点中的数据元素;lchild域称为左孩子指针域,用于存放指向本结点左孩子的指针(这个指针及指针域有时简称为左指针)。类似地,rchild域称为右孩子指针域,用于存放指向本结点右孩子的指针(简称右指针)。二叉链表中的所有存储结点通过它们的左、右指针的链接而形成一个整体。此外,每个二叉链表还必须有一个指向根结点的指针,该指针称为根指针。根指针具有标识二叉链表的作用,对二叉链表的访问只能从根指针开始。值得注意的是,二叉链表中每个存储结点的每个指针域必须有一个值,这个值或者是指向该结点的一个孩子的指针,或者是空指针NULL。

  若二叉树为空,则root=NULL。若某结点的某个孩子不存在,则相应的指针为空。具有n个结点的二叉树中,一共有2n个指针域,其中只有n-1个用来指向结点的左右孩子,其余的n+1个指针域为NULL。

  二叉树的链式存储结构操作方便,表达简明(二叉树的逻辑关系———结点间的父子关系———在二叉链表和三叉链表中被直接表达成对应存储结点之间的指针),因而成为二叉树最常用的存储结构。然而在某些情况下,二叉树的顺序存储结构也很有用。

  (2)二叉树的顺序存储结构

  二叉树的顺序存储结构由一个一维数组构成,二叉树上的结点按某种次序分别存入该数组的各个单元。显然,这里的关键在于结点的存储次序,这种次序应能反映结点之间的逻辑关系(父子关系),否则二叉树的基本运算就难以实现。

  由二叉树的性质5可知,若对任一完全二叉树上的所有结点按层编号,则结点编号之间的数值关系可以准确地反映结点之间的逻辑关系。因此,对于任何完全二叉树来说,可以采用“以编号为地址”的策略将结点存入作为顺序存储结构的一维数组。具体地说就是:将编号为i的结点存入一维数组的第i个单元。

  在这一存储结构中,由于一结点的存储位置(即下标)也就是它的编号,故结点间的逻辑关系可通过它们下标间的数值关系确定。

  5.二叉树的遍历

  由于二叉树的基本运算在链式存储结构上的实现比较简单,无需详加讨论。下面研究二叉树的一种较为复杂的重要运算———遍历及其在二叉链表上的实现。

  遍历一棵二叉树就是按某种次序系统地“访问”二叉树上的所有结点,使每个结点恰好被“访问”一次。所谓“访问”一个结点,是指对该结点的数据域进行某种处理,处理的内容依具体问题而定,通常比较简单。遍历运算的关键在于访问结点的“次序”,这种次序应保证二叉树上的每个结点均被访问一次且仅一次。

  由定义可知,一棵二叉树由三部分组成:根、左子树和右子树。因此对二叉树的遍历也可相应地分解成三项“子任务”:

  ①访问根根点;

  ②遍历左子树(即依次访问左子树上的全部结点);③遍历右子树(即依次访问右子树上的全部结点)。

  因为左、右子树都是二叉树(可以是空二叉树),对它们的遍历可以按上述方法继续分解,直到每棵子树均为空二叉树为止。由此可见,上述三项子任务之间的次序决定了遍历的次序。若以D、L、R分别表示这三项子任务,则人有六种可能的次序:DLR、LDR、LRD、DRL、RDL和RLD。通常限定“先左后右”,即子任务②在子任务③之前完成,这样就只剩下前三种次序,按这三种次序进行的遍历分别称为先根遍历(或前序遍历)、中根(或中序)遍历、后根(或后序)遍历。三种遍历方法的定义如下:

  先根遍历 若需遍历的二叉树为空,执行空操作;否则,依次执行下列操作:

  ①访问根结点;

  ②先根遍历左子树;

  ③先根遍历右子树。

  中根遍历 若需遍历的二叉树为空,执行空操作,否则,依次执行下列操作:

  ①中根遍历左子树;②访问根结点;③中根遍右子树。

  后根遍历 若需遍历的二叉树为空,执行空操作,否则,依次执行下列操作:

  ①后根遍历左子树。②后根遍历右子树。③访问根结点。

  显然,上述三种遍历方法的区别在于执行子任务“访问根结点”的“时机”不同;最先(最后、在中间)执行此子任务,则为先根(后根、中根)遍历。

  按某种遍历方法遍历一棵二叉树,将得到该二叉树上所有结点的访问序列。

  6.树

  树是一种常用的数据结构。为了适应各种应用问题的需要,多种不同的存储结构也相应地建立起来。下面介绍树的三种常用存储结构。

  (1)孩子链表表示法

  孩子链表表示法是树的一种链式存储结构。与二叉树的二叉链表存储方法类似,孩子链表表示法的基本思想是:树上的一个结点的内容(数据元素)以及指向该结点所有孩子的指针存储在一起以便于运算的实现。由于树上的结点的度(孩子数)没有限制,而且各个结点的度可能相差很大,一种自然的表示方法是为树上的每个结点X建立一个“孩子链表”,以便存储X中的数据元素和指向X的所有孩子的指针。一个孩子链表是一个带头结点的单链表,单链表的头结点含两个域:数据域和指针域。其中,数据域用于存储结点X中的数据元素;指针域用于存储指向该单链表中第一个表结点(首结点)的指针。为了检索方便,所有头结点组织成一个数组,称为表头数组。对每个结点X的孩子链表来说,其中的所有表结点也含两个域,孩子域(即数据域)和指针域。第i个表结点的孩子域存储X的第i个孩子在头结点数组中的下标值。

  (2)孩子兄弟链表表示法

  孩子兄弟链表中所有存储结点的形式相同,均含三个域:数据域———用于存储树上的结点中的数据元素;孩子域———用于存储指向本结点第一个孩子的指针;兄弟域———用于存放指向本结点下一个兄弟的指针。

  值得注意的是,孩子兄弟链表的结构形式与二叉链表完全相同;但存储结点中指针的含义不同。二叉链表中存储结点的左、右指针分别指向左、右孩子;而孩子兄弟链表中存储结点的两个指针分别指向“长子”和“大弟”。

  在孩子兄弟链表表示法中,结点形式统一,结点间的联系比较简捷。同时,在这种存储结构上容易实现树数据结构的大多数运算。

  (3)双亲表示法

  树上每个结点的孩子可以有任意多个,但双亲只有一个。因此,通过指向双亲的指针而将树中所有结点组织在一起形成一种存储结构是十分简法的。树的这种存储表示方法称为双亲表示法。在双亲表示法下,每个存储结点由两个域组成:数据域———用于存储树上结点中的数据元素;“指针”域———用于指示本结点之双亲所在的存储结点。值得注意的是,“指针”域的类型定义可以有两种选择。第一种是将其定义为高级语言(如C语句)中的指针类型。通过将存储结点中的指针域定义为高级语言中的指针类型,就得到各种链式存储结构,如单链表、二叉链表、孩子链表等等。第二种选择是将“指针”域定义为整型、子界型等型。严格地说,无论选择上述哪种定义,得到的都是链式存储结构,因为在这两种定义之下,各存储结点之间的联结是通过“指针”完成的,而且这些指针反映了结点之间的逻辑关系。

  为了区别这两种链式结构,通常将指针域定义为高级语言中的指针类型的各种链式存储结构(如单链表、二叉链表等等)称为“动态链表”,相应的指针称为“动态指针”;将指针域定义为整型、子界型等类型的各种键式存储结构称为“静态链表”,相应的“指针”称为:“静态指针”。动态链表中的结点是通过高级语言中的标准过程例如C语言的库函数malloc(size)动态(即运行期间)生成的(动态链表由此得名),无需事先规定链表的容量,因此动态链表的大小是动态变化的。相反,静态链有的容量必须事先说明,因而其大小是固定的。然而,在某些情况下,特别是当结点数固定不变且可事先确定时,采用静态链表往往更加方便、直观。

  静态双亲链表由一个一维数组树成。数组的每个分量包含两个域:数据域和双亲域。数据域用于存储树上一个结点中的数据元素;双亲域用于存放本结点的双亲结点在数组中的序号(下标值)。

  7.树的遍历

  与二叉树类似,遍历是树的一种重要运算。树的主要遍历方法有以下三种。

  (1)先根遍历若树非空,则

  ①访问根结点;

  ②依次先根遍历根的各个子树T 1 ,…,T m 。

  (2)后根遍历若树非空,则

  ①依次先根遍历根的各个子树T 1 ,…,T m 。②访问根结点;

  (3)层次遍历

  ①若树非空,访问根结点;

  ②若第1,…,i(i≥1)层结点已被访问,且第i+1层结点未访问,则从左到右依次访问第i+1层结点。

  显然,按层次遍历所得的结点访问序列中,各结点的序号与按层编号所得的编号一致。

  8.树与二叉树之间的转换

  一般树转换为二叉树的基本思想是:将树中每个结点用两个链接表示就可以了,一个指向它最左边的孩子,另一个指向它右边的一个兄弟,从图形上看,具体步骤是:

  ①加线:在兄弟结点直接加一虚线;

  ②抹线:对每个结点,除了其最左的一个孩子外,抹去该结点原来与其余孩子之间的边线;

  ③旋转:将新加上的虚线改为实线,并将虚线以及有关的实线顺时钟旋转45度。

  二叉树还原为一般树的步骤是:

  ①加线:若某结点是一父结点的左孩子,则将该结点的右孩子以及沿着右链搜索到的所有右孩子结点都用线与那个父结点连接起来;

  ②抹线:抹去原二叉树中所有结点与其右孩子的连线;

  ③旋转:将虚线及有关实线逆时钟旋转约45度,并将几个结点按层次排列。

  9.二叉树与森林之间的转换

  森林转换为二叉树的步骤是:

  ①将森林中的每棵树转换为二叉树;

  ②森林中第一棵树的根结点就是转换后二叉树的根结点,依次将后一棵树作为前一棵树根结点的右子树。

  二叉树转换为森林的步骤是:

  ①森林第一棵树的根就是二叉树的根;

  ②二叉树的左子树转换为森林的第一棵树,二叉树的右子树对应于森林中其余的树;③二叉树右子树的根结点作为余下树中第一棵树的根结点……,以此类推。

  五、图

  图的概念

  图是一种较线性表和树形结构更为复杂的数据结构。在线性表中每个数据元素只有一个(直接)前驱和后继,即各数据元素之间仅有线性关系。在树形结构中,数据元素之间有明显的层次关系,每一层中的数据元素只和上一层中的一个元素(即双亲结点)相关。而在图中,任意两个数据元素之间均有可能相关。

  图(graph)是图型结构的简称。它是一种复杂的非线性数据结构。图在各个领域都有着广泛的应用。图的二元组定义为:

  G=(V,E)

  其中,V是非空的顶点集合,即

  V={v i |1≤i≤n,n≥1,v i ∈elemtype,n为顶点数}

  E是V上二元关系的集合,一般只讨论仅含一个二元关系的情况,且直接用E表示这个关系。这样,E就是V上顶点的序偶或无序对(每个无序对(x,y)是两个对称序偶和的简写形式)的集合。对于V上的每个顶点,在E中都允许有任意多个前驱和任意多个后继,即对每个顶点的前驱和后继个数均不加限制。回顾一下线性表和树的二元组定义,都是在其二元关系上规定了限制条件,线性表的限制条件是只允许每个结点有一个前驱和一个后继,树的限制条件是只允许每个结点有一个前驱。因此,图比线性表和树更具有广泛性,它包含线性表和树在内,线性表和树可以认为是图的简单情况。

  对于一个图G,若E是序偶的集合,则每个序偶对应图形中的一条有向边,若E是无序对的集合,则每个无序对对应图形中的一条无向边,所以可把E看作为边的集合。这样,图的二元组定义可叙述为:图的非空顶点集(vertexset)和边集(edgeset)所组成。针对图G,顶点集和边集可分别记为V(G)和E(G)。边集E(G)允许是空集,若是空集,图G中的顶点均为孤立顶点。对于一个图G,若边集E(G)为有向边的集合,则称此图为有向图(digraph),若边集E(G)为无向边的集合,则称此图为无向图(undigraph)。

  六、排序

  1.直接插入排序

  直接插入排序的基本思想是把表中元素依次插入一个已排好序的表中,就像人们打扑克摸牌时把牌插入手中的若干张牌里一样。表中n个元素依次插入的比较次数为1+2+3+…+(n-1)=n(n-1)/2。在插入时,元素的移动次数最多为1+2+3+…+(n-1)=n(n-1)/2。如果表中元素已排好序,则只需比较n-1次,而移动次数为0。

  2.直接选择排序

  直接选择排序的基本思想是在表的n个元素中,经过n-1次比较得到其最大值(或最小值,下同),这就排好了第一个元素;再经过n-2次比较得到余下元素中的最大值,这就排好了第二个元素…直到比较1次后排好第n-1个元素,第n个元素的位置也就自然确定了。所需的比较次数为(n-1)+(n-2)++1=n(n-1)/2。所需移动次数最多也为n(n-1)/2。如果表中元素排好序,也需要比较n(n-1)/2次,而移动次数为0。

  3.冒泡排序

  冒泡排序的基本思想是将表中元素两个相邻元素依次比较,若不符合排序要求,则交换位置,这样经过n-1次比较后,将确定出最大(或最小)元素的位置,这称为一趟扫描。经过n-1次扫描后,就完成了整个表的排序。第一趟扫描的比较次数是n-1,第二趟扫描的比较次数是n-2……,总的比较次数是(n-1)+(n-2)+……+1=n(n-1)/2。如果恰好表中元素按反序排列,则需要移动的次数为3×n(n-1)/2。如果表中元素已排好序,并采用交换标志来表示并未发生过交换,则只需一趟扫描,只比较n-1次,就够了;当然,移动次数也是0。

  4.归并排序

  归并排序的基本思想是表中元素两两比较排序,使表中的n个元素变成n/2个已排序的组,再两两组比较,而变成n/4个已排序的组……,直到表中只含有一个已排序的组,即完成排序。所需要的比较次数为nlog 2 n,移动次数为n。若表已排好序,则比较次数仍为nlog 2 n,但移动次数为0。

  5.快速排序

  快速排序的基本思想是把表中某元素作为基准,将表划分为大于该值和小于该值的两部分,然后用递归的方法处理这两个子表,直到完成整个表的排序。快速排序的比较次数为(n-1)+(n-2)+…+1=n(n-1)/2,移动次数最多也是n(n-1)/2。如果每次的基准元素刚好是表的中值,使表分为大小相等的两个子表,则比较次数为nlog 2 n;如果表已排好序,则移动次数为0。

  6.常用排序方法的性能比较如下表所示:

  常用排序方法的性能比较

  排序方法 平均时间 最坏情况的时间 辅助存储

  冒泡法、直接选择法、直接插入法 O(n2 ) O(n2 ) O(1)

  快速排序 O(nlog2 n) O(n2 ) O(log2 n)

  堆排序 O(nlog2n) O(nlog2 n) O(1)

  归并排序 O(nlog2 n) O(nlog2 n) O(n)

  注:在上表中,我们将n(n-1)/2也记为O(n2 )。如果在待排序的表中含有多个码值相同的记录,经过排序后,这些记录的相对次序不变,则称这种排序方法是稳定的,否则是不稳定的。根据上述说法,可以看出直接插入法、归并法是稳定的;而直接选择法、冒泡法、快速排序法、堆排序法是不稳定的。

  七、检索

  1.顺序检索

  检索又称为查找。顺序检索是将待查找的关键码值与线性表中个结点的关键码值逐一比较,直到找到所需的记录,检索成功;或者在表中找不到所需记录而检索失败。顺序检索不要求线性表事先排序。设线性表有n个元素,则最多检索次数为n,最少检索次数为1。

  2.二分法检索

  二分法检索要求线性表结点按关键排序且以顺序方式存储。在查找时,首先与表的中间位置上结点的关键值比较,若相等则检索成功;否则根据比较结果确定下一步在表的前半部或后半部中继续进行。二分法检索的效率较主动,设线性表有n个元素,则最多的检索次数为大于log 2 n的最小整数,最少的检索次数为1。

  3.分块检索

  分块检索把线性表分成若干块,块内结点不必有序,但块与块之间必须有序,即每一块中各结点的关键值必须大于(或小于,与此类推)前一块最大关键值。为加快查找,还要建立一个索引表,表中给出每一块的最大关键值和指向块内第一个结点位置的指针。分块检索分两步进行,先查索引表,确定要找的记录在哪一块;然后再在相应的块中检索。分块检索适合于线性表很大,数据又是动态变化的情况。在查索引表时,可采用顺序法或二分法;在块内查找所求记录时,采用顺序法。由于分块而缩小了查找范围,从而加快检索速。

  4.散列表检索

  根据关键值,就可以迅速找到该记录所对应的存储位置,这就是建立在散列函数基础上的散列检索。设记录的关键值为k,则该记录的存储位置可用散列函数H来计算H=H(k)。常用来产生的散列函数的方法是除余法,即取H(k)=k mod p设散列表长度为n,取p为小于n的最大素数。一般说来,关键码值的集合比散列表存储位的数目大得多,这正是体现散列表的优势所在,但同时带来了冲突问题,即不同的关键值经散列函数计算,可能得到相同的存储位置。一个好的散列函数应该使冲突的可能性尽量小。最常用的解决冲突的方法是线性探测法,就是在发生冲突时,从H(k)以后的位置逐一探测,直至找到一个空位置,将新记录插入;在检索时,如果H(k)中不是所需关键值的记录,也是从H(k)往下逐一搜索,直到找到所需关键值或查找失败为止。应注意查找次序是:H(k),H(k)+1,H(k)+2,…n-1,0,1,2,…,H(k)-1即在n-1以后,又从0开始,因为在位置上是循环的。双重散列技术是对线性探测法的改进。它使用两个散列函数H1和H2。对关键值k,计算H1(k),求得0到n-1之间的一个散列地址;若在这个地址上冲突,下一个被探测的地址为(H1(k)+H2(k))mod n,关于选择H2的方法在此不做讨论。

相关文章

热门标签

495825