第十二章 数据结构

第十二章数据结构第1页，共91页，2023年，2月20日，星期三主要内容：12.1数据结构的主要研究内容12.2数据结构基本概念12.3数据的逻辑结构12.4线性表及其顺序存储结构12.5栈和队列12.6树与二叉树12.7查找技术12.8排序技术第2页，共91页，2023年，2月20日，星期三12.1数据结构的主要研究内容■12.1数据结构的主要研究内容数据结构是相互之间存在一种或多种特定关系的数据元素的集合。数据结构作为计算机的一门学科，主要研究和讨论以下三个方面的问题：1．数据集合中各数据元素之间所固有的逻辑关系，即数据的逻辑结构。数据的逻辑结构是从逻辑关系上描述数据，与数据的存储无关，是独立于计算机的。数据的逻辑结构可以看作是从具体问题抽象出来的数学模型。数据的逻辑结构包含：（1）表示数据元素的信息；（2）表示各数据元素之间的前后件关系。第3页，共91页，2023年，2月20日，星期三2．各数据元素在计算机中存储关系，即数据的存储结构。数据的存储结构有顺序、链接、索引等。数据的存储结构是逻辑结构用计算机语言的实现（亦称为映象），它依赖于计算机语言。对机器语言而言，存储结构是具体的。一般只在高级语言的层次上讨论存储结构。对各种数据结构进行的运算。3.数据的运算定义在数据的逻辑结构上，每种逻辑结构都有一个运算的集合。最常用的检索、插入、删除、更新、排序等运算实际上只是在抽象的数据上所施加的一系列抽象的操作。所谓抽象的操作，是指只知道这些操作是“做什么”，而无须考虑“如何做”。只有确定了存储结构之后，才考虑如何具体实现这些运算。第4页，共91页，2023年，2月20日，星期三12.2数据结构基本概念■12.2.1数据数据是指所有能输入到计算机中并被计算机程序处理的符号的总称。数据是信息的载体，它能够被计算机识别、存储和加工处理，是计算机程序加工的“原料”。随着计算机应用领域的扩大，数据可以分为两大类：一类是整数、实数等数值数据；另一类是图形、图像、声音、文字等非数值数据。这里要注意数据并不等于数字，数字是隶属于数据的。第5页，共91页，2023年，2月20日，星期三■12.2.2数据元素与数据项数据元素也称为元素、结点、顶点或记录，是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。一个数据元素可由若干个数据项组成，数据项是数据的最小单位。数据元素具有广泛的含义，一般来说，现实世界中客观存在的一切个体都可以是数据元素。例如在表12-1中，整个表记录的是学生成绩数据，每个学生的记录行是其中一个数据元素，即该表由4个数据元素构成，而某一个数据元素（记录行）又是由5个数据项组成。例如语文成绩67则是表中第一个数据元素（记录行）中的数据项。数据项是不可再分的数据内容。第6页，共91页，2023年，2月20日，星期三数据对象是性质相同的数据元素的集合。如上例中一个班级的成绩表可以看作一个数据对象。一般来说，人们不会同时处理特征完全不同且互相之间没有任何关系的各类数据元素，对于具有不同特征的数据元素总是分别进行处理。学号姓名语文数学英语04060101李丽67878304060102张鹏92826404060103刘海78727604060104金玉566871第7页，共91页，2023年，2月20日，星期三■12.2.3数据结构数据元素都不是孤立存在的，而是在它们之间存在着某种特定的关系，这种数据元素相互之间的关系称为结构。在数据处理领域中，通常把数据元素之间这种固有的关系简单地用前后件关系(或直接前驱与直接后继关系)来描述。例如，在考虑一年四个季节的顺序关系时，则“春”是“夏”的前件（即直接前驱），而“夏”是“春”的后件（即直接后继）。同样，“夏”是“秋”的前件，“秋”是“夏”的后件；“秋”是“冬”的前件，“冬”是“秋”的后件。前后件关系是数据元素之间的一个基本关系，但前后件关系所表示的实际意义随具体对象的不同而不同。一般来说，数据元素之间的任何关系都可以用前后件关系来描述。第8页，共91页，2023年，2月20日，星期三■12.2.4数据的逻辑结构通俗地说，数据结构是指带有结构的数据元素的集合。在此，所谓结构实际上就是指数据元素之间的前后件关系。数据元素之间的前后件关系即指它们的逻辑关系，而与它们在计算机中的存储位置无关。所谓数据的逻辑结构，是指反映数据元素之间逻辑关系的数据结构。

图12-1数据的逻辑结构第9页，共91页，2023年，2月20日，星期三表中的每一行是一个数据元素（或记录、结点），它由学号、姓名、各科成绩等数据项组成。表中数据元素之间的逻辑关系是：对表中任一个结点，与它相邻的直接前趋（ImmediatePredecessor）最多只有一个；与表中任一结点相邻的直接后继（ImmediateSuccessor）也最多只有一个。表中只有第一个结点没有直接前趋，故称为开始结点；也只有最后一个结点没有直接后继，故称之为终端结点。上述结点间的关系构成了这张学生成绩表的逻辑结构。逻辑结构主要可分为线性结构（线性表、栈和队列）和非线性结构（树、图和集合）。如图12-1所示。第10页，共91页，2023年，2月20日，星期三■12.2.5数据的存储结构数据的存储结构又称为物理结构，是数据及其逻辑结构在计算机中的表示。在数据的存储结构中，不仅要存放各数据元素的信息，还存放元素之间的前后件关系的信息。数据的存储结构属于具体实现的视图，是面向计算机的，其基本目标是将数据及其逻辑关系存储到计算机的内存中。一般来说，一种数据的逻辑结构根据需要可以表示成多种存储结构，常用数据的存储结构有如下4种。1．顺序存储方式每一个存储结点只含有一个数据元素；所有的存储结点相继存储在一个连续的存储区里；用存储结点之间的位置关系表示数据元素之间的逻辑关系。第11页，共91页，2023年，2月20日，星期三2．链式存储方式每一个存储结点不仅含有各数据元素，还包括指针。每一个指针指向一个与本结点有逻辑关系的结点，即用指针表示逻辑关系。3．索引存储方式每一个存储结点仅含有一个数据元素，所有的存储结点都连续存放。此外，增设一个索引表。4．散列存储方式每一个存储结点仅含有一个数据元素，数据元素按散列函数确定存储位置。数据的逻辑结构与数据的存储结构不一定相同。一般来说，一种数据的逻辑结构根据需要可以表示成多种存储结构。采用不同的存储结构，其数据处理的效率是不相同的。第12页，共91页，2023年，2月20日，星期三数据的逻辑结构有两个要素：一是数据元素的集合；二是各数据元素之间的前后件关系。对这两个要素的表示可有两种方式：一是用二元关系表示；二是直观地用图形表示。在二元关系表示中，将数据元素的集合记为D，反映D中各数据元素之间的前后件关系记为R。一个数据结构就可以表示成B=（D,R）的二元组关系，其中B表示数据结构。例如：假设a和b是D中的两个数据，则二元组(a，b)表示a是b的前件，b是a的后件。这样，在D中的每两个元素之间的关系都可以用这种二元组来表示。12.3数据的逻辑结构■12.3.1逻辑结构的表现方式第13页，共91页，2023年，2月20日，星期三在数据结构的图形表示中，对于数据集合D中的每一个数据元素用中间标有元素值的方框表示，一般称之为数据结点，并简称为结点。为了进一步表示各数据元素之间的前后件关系，对于关系R中的每一个二元组，用一条有向线段从前件结点指向后件结点。例如，一年四季的数据结构可以用如图12-2所示的图形来表示。春夏秋冬图12-2逻辑结构的图形表示第14页，共91页，2023年，2月20日，星期三1．线性结构如果一个非空的数据结构满足下列两个条件：（1）有且只有一个根结点。（2）每一个结点最多有一个前件，也最多有一个后件。则称该数据结构为线性结构，线性结构又称线性表。2．线性结构逻辑特征（1）存在唯一的一个被称作“第一个”的数据元素。（2）存在唯一的一个被称作“最后一个”的数据元素。（3）除第一个之外，集合中的每个数据元素均只有一个前驱。（4）除最后一个之外，集合中的每个数据元素均只有一个后继。■12.3.2线性逻辑结构第15页，共91页，2023年，2月20日，星期三在线性结构中，各数据元素之间的前后关系是很简单的。如上述的一年四季这个数据结构，属于线性结构。线性表是一个线性结构。特别需要说明的是在一个线性结构中插入或删除任何一个结点后还应是线性结构。如果一个数据结构满足上述两个条件，但当在此数据结构中插入或删除任何一个结点后就不满足这两个条件，则该数据结构不能称为线性结构。如果一个数据结构不是线性结构，则称之为非线性结构。

第16页，共91页，2023年，2月20日，星期三非线性结构的逻辑特征是一个结点可能有多个直接前驱和直接后继。例如，树和图都是非线性结构。线性结构与非线性结构都可以是空的数据结构。一个空的数据结构究竟是属于线性结构还是属于非线性结构，这要根据具体情况来确定。如果对该数据结构的运算是按线性结构的规则来处理的，则属于线性结构，否则属于非线性结构。■12.3.3非线性逻辑结构第17页，共91页，2023年，2月20日，星期三线性表是最基本、最简单、也是最常用的一种数据结构。线性表中数据元素之间的关系是一对一的关系，即除了第一个和最后一个数据元素之外，其他数据元素都是首尾相接的。线性表的逻辑结构简单，便于实现和操作。因此，线性表这种数据结构在实际应用中是广泛采用的一种数据结构。12.4线性表及其顺序存储结构■12.4.1线性表的基本概念第18页，共91页，2023年，2月20日，星期三线性结构特点如下：1．有且仅有一个开始结点(表头结点)，它没有直接前驱，只有一个直接后继。2．有且仅有一个终端结点(表尾结点)，它没有直接后继，只有一个直接前驱。3．其他结点都有一个直接前驱和直接后继。4．元素之间为一对一的线性关系。需要注意的是线性表中数据元素的相对位置是确定的，如果把一个线性表中的数据元素的位置做改动，那么变动后的线性表与原来的线性表是两个不同的线性表。在实现线性表数据元素的存储方面，一般可用顺序存储结构和链式存储结构两种方法。第19页，共91页，2023年，2月20日，星期三■12.4.2线性表的顺序存储结构线性表的顺序存储是指用一组地址连续的存储单元依次存储线性表中的数据元素，从而使得逻辑上相邻的两个元素在物理位置上也相邻，如图12-3所示。在这种存储方式下，存储逻辑关系无须占用额外的存储空间。a1a2a3……an第20页，共91页，2023年，2月20日，星期三一般地，以Loc(a1)表示线性表中第一个元素的存储位置，则在顺序存储结构中，第i个元素的存储位置为：Loc(a1)=Loc(a1)+(i–1)×L其中L是表中每个元素所占空间的大小。根据该计算关系，可随机存取表中的任意一个元素。1．线性表的顺序存储结构基本特点：（1）线性表中所有元素所占的存储空间是连续的。（2）线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。由此可以看出，在线性表的顺序存储结构中，其前后件两个元素在存储空间中是紧邻的，且前件元素一定存储在后件元素的前面。线性表采用顺序存储结构的优点是可以随机存取表中的元素，查找元素的速度很快。第21页，共91页，2023年，2月20日，星期三2．线性表的顺序存储结构存在以下几方面的缺点：（1）在一般情况下，要在顺序存储的线性表中插入一个新元素或删除一个元素时，为了保证插入或删除后的线性表仍然为顺序存储，则在插入或删除过程中需要移动大量的数据元素。因此，对于大的线性表，特别是元素的插入或删除很频繁的情况下，采用顺序存储结构是很不方便的，插入与删除运算的效率都很低。（2）在顺序存储结构下，线性表的存储空间不便于扩充。当为一个线性表分配顺序存储空间后，如果出现线性表的存储空间已满，但还需要插入新的元素时，就会发生“上溢”错误。在这种情况下，如果在原线性表的存储空间后找不到与之连续的可用空间，则会导致运算的失败或中断。

第22页，共91页，2023年，2月20日，星期三（3）线性表的顺序存储结构不便于对存储空间的动态分配。在实际应用中，往往是同时有多个线性表共享计算机的存储空间。如果将存储空间平均分配给各线性表，则有可能造成有的线性表的空间不够用，而有的线性表的空间根本用不着或用不满，这就使得在有的线性表空间无用而处于空闲的情况下，另外一些线性表的操作由于“上溢”而无法进行。如果对每一个线性表的存储空间进行动态分配，则为了保证每一个线性表的存储空间连续且顺序分配，会导致在对某个线性表进行动态分配存储空间时，必须要移动其他线性表中的数据元素。第23页，共91页，2023年，2月20日，星期三■12.4.3线性表的链式存储结构1．线性链表的基本概念线性表的链式存储结构称为线性链表。为了适应线性表的链式存储结构，计算机存储空间被划分为一个一个小块，每一小块占若干字节，通常称这些小块为存储结点。为了存储线性表中的每一个元素，一方面要存储数据元素的值，另一方面要存储各数据元素之间的前后件关系。为此目的，将存储空间中的每一个存储结点分为两部分：一部分用于存储数据元素的值，称为数据域；另一部分用于存放下一个数据元素的存储序号（存储结点的地址），称为指针域。线性链表的存储结构如图12-4所示。第24页，共91页，2023年，2月20日，星期三第25页，共91页，2023年，2月20日，星期三HEAD数据1数据2数据nNULL…图12-5线性链表的逻辑结构一般来说，在线性表的链式存储结构中，各数据结点的存储序号是不连续的，并且各结点在存储空间中的位置关系与逻辑关系也不一致。线性链表的逻辑结构如图12-5所示。在线性链表中，各数据元素之间的前后件关系是由各结点的指针域来指示的。指向线性表中第一个结点的指针HEAD称为头指针。当HEAD=NULL（或0）时称为空表。对于栈和队列，除了采用顺序存储结构外，还可采用链式存储结构。第26页，共91页，2023年，2月20日，星期三2．线性链表及其基本运算（1）在线性链表中查找指定元素在非空线性链表中寻找包含指定元素值x的前一个结点p的基本方法如下：从头指针指向的结点开始往后沿指针进行扫描，直到后面已没有结点或下一个结点的数据域为x为。因此，由这种方法找到的结点p有两种可能：当线性链表中存在包含元素x的结点时，则找到的p为第一次遇到的包含元素x的前一个结点序号；当线性链表中不存在包含元素x的结点时，则找到的p为线性链表中的最后一个结点序号。第27页，共91页，2023年，2月20日，星期三（2）线性链表的插入线性链表的插入是指在链式存储结构下的线性表中插入一个新元素。前面主要讨论了线性表的顺序存储结构。线性表的顺序存储结构具有简单、运算方便等优点，特别是对于小线性表或长度固定的线性表，采用顺序存储结构的优越性更为突出。但是，线性表的顺序存储结构在某些情况下显得不那么方便，运算效率不那么高。因此，对于大的线性表，特别是元素变动频繁的大线性表不宜采用顺序存储结构，而是采用上面介绍的链式存储结构。假设要在线性表的两个数据元素a和b之间插入一个数据元素x，已知p为其链表存储结构中指向结点a的指针，如图所示。为插入数据元素x，首先要生成一个数据域为x的结点，然后插入在链表中。根据插入操作的逻辑定义，还需要修改结点a中的指针域，令其指向结点x，而结点x中的指针域应指向结点b，从而实现3个元素a、b和x之间逻辑关系的变化。插入后的链表如图所示。第28页，共91页，2023年，2月20日，星期三第29页，共91页，2023年，2月20日，星期三反之，如图12-7所示，在线性表中删除元素b时，为在链表中实现元素a、b和c之间逻辑关系的变化，仅需修改结点a中的指针域即可。apbc图12-7链表的删除操作第30页，共91页，2023年，2月20日，星期三线性链表分为单链表、双向链表和循环链表三种类型。在单链表中，每一个结点只有一个指针域，因此，在这种线性链表中，只能沿指针向链尾方向进行扫描，这对于某些问题的处理会带来不便，因为在这种链接方式下，由某一个结点出发，只能找到它的后件，而为了找出它的前件，必须从头指针开始重新寻找。因此，在某些应用中，对于线性链表中的每个结点设置两个指针，一个称为左指针(Llink)，指向其前件结点；另一个称为右指针(Rlink)，指向其后件结点，这种链表称为双向链表。循环链表与单链表的区别仅仅在于其尾结点的链域值不是空，而是一个指向头结点的指针。循环链表的主要优点是：从表中任一结点出发都能通过后移操作而扫描整个循环链表。但对单链表来说，只有从头结点开始才能扫描表中全部结点。第31页，共91页，2023年，2月20日，星期三■12.5.1栈及其基本运算栈和队列是两种特殊的线性表，它们的逻辑结构和线性表相同，只是其运算规则较线性表有更多的限制，故又称运算受限的线性表。栈和队列被广泛应用于各种程序设计中。12.5栈和队列1．栈的基本概念栈（Stack）是限制仅在表的一端进行插入和删除运算的线性表。（1）通常称插入、删除的这一端为栈顶（Top），另一端称为栈底（Bottom）。（2）当表中没有元素时称为空栈。（3）栈顶元素总是最后被插入的元素，栈底元素总是最先被插入的元素。（4）栈为后进先出（LastInFirstOut，简称为LIFO）或先进后出（FirstInLastOut，简称为FILO）的线性表。第32页，共91页，2023年，2月20日，星期三栈的修改是按后进先出的原则进行。每次删除（退栈）的总是当前栈中“最新”的元素，即最后插入（进栈）的元素，而最先插入的是被放在栈的底部，要到最后才能删除。例如元素是以，，…，的顺序进栈，退栈的次序却是，，…，。在顺序存储结构下，对这种类型线性表的插入与删除运算是不需要移动表中其他数据元素的。栈的顺序存储结构示意图如图12-8所示。通常用指针top来指示栈顶的位置，用指针bottom指向栈底。栈中插入一个元素称为入栈运算，从栈中删除一个元素(即删除栈顶元素)称为退栈运算。栈顶指针top动态反映了栈中元素的变化情况。

第33页，共91页，2023年，2月20日，星期三与一般的线性表一样，在程序设计语言中，用一维数组S(1：m)作为栈的顺序存储空间，其中m为栈的最大容量。通常，栈底指针指向栈空间的低地址一端(即数组的起始地址这一端)。在栈的顺序存储空间S(1：m)中，S(bottom)通常为栈底元素(在栈非空的情况下)，S(top)为栈顶元素。top=0表示栈空，top=m表示栈满。

第34页，共91页，2023年，2月20日，星期三2．栈的基本运算栈具有记忆作用，栈的基本运算主要包括入栈、退栈及读栈顶元素三种。（1）入栈运算：指在栈顶位置插入一个新元素。这个运算有两个基本操作：首先将栈顶指针进一(即top加1)，然后将新元素插入栈顶指针指向的位置。当栈顶指针已经指向存储空间的最后一个位置时，说明栈空间已满，不可能再进行入栈操作。这种情况称为栈“上溢”错误。（2）退栈运算：是取出栈顶元素并赋给一个指定的变量。这个运算有两个基本操作：首先将栈顶元素(栈顶指针指向的元素)赋给一个指定的变量，然后将栈顶指针退一(即top减1)。当栈顶指针为O时，说明栈空，不可能进行退栈操作。这种情况称为栈“下溢”错误。第35页，共91页，2023年，2月20日，星期三（3）读栈顶元素：是指将栈顶元素赋给一个指定的变量。必须注意，这个运算不删除栈顶元素，只是将它的值赋给一个变量，因此，在这个运算中，栈顶指针不会改变。当栈顶指针为0时，说明栈空，读不到栈顶元素。图12-9，图12-10，图12-11分别表示了栈的初始，入栈及退栈的过程。图12-9栈的初始示意第36页，共91页，2023年，2月20日，星期三图12-10入栈操作图12-11出栈操作第37页，共91页，2023年，2月20日，星期三为了更好的理解入栈与退栈操作，假设有4个元素a,b,c,d依次入栈，入栈过程中允许出栈，则所有可能的出栈序列为abcd、abdc、acbd、acdb、adcb、bacd、badc、bcad、bcda、bdca、cbad、cbda、cdba、dcba，读者可自行分析其结果。第38页，共91页，2023年，2月20日，星期三■12.5.2队列及其基本运算1．队列的基本概念队列（Queue）是只允许在一端进行插入，而在另一端进行删除的运算受限的线性表。（1）允许删除的一端称为队头，通常也用一个排头指针(front)指向排头元素的前一个位置。（2）允许插入的一端称为队尾，通常用一个称为尾指针(rear)的指针指向队尾元素，即尾指针总是指向最后被插入的元素。（3）当队列中没有元素时称为空队列。（4）队列亦称作先进先出（FirstInFirstOut）的线性表，简称为FIFO表。

第39页，共91页，2023年，2月20日，星期三队列的修改是依“先进先出”或“后进后出”的原则进行的。新来的成员总是加入队尾（即不允许“加塞”），每次离开的成员总是队列头上的（不允许中途离队），即当前“最老的”成员离队。例如在队列中依次加入元素a1，a2，…an，之后，a1是队头元素，an是队尾元素。退出队列的次序只能是a1，a2，…an，。在队列中，队尾指针rear与排头指针front共同反映了队列中元素动态变化的情况。图12-12是具有6个元素的队列示意图。图12-12队列示意图第40页，共91页，2023年，2月20日，星期三2．队列的基本运算图12-13是在队列中进行插入与删除的示意图。由图12-13可以看出，在队列的末尾插入一个元素(入队运算)只涉及队尾指针rear的变化，而要删除队列中的排头元素(退队运算)只涉及排头指针front的变化。与栈类似，在程序设计语言中，用一维数组作为队列顺序存储空间。和栈一样，队列也可以采用顺序存储或链式存储的方式。对于顺序存储的队列，主要有入队和出队操作。队列的队头和队尾的位置是变化的，设置两个指针front和rear分别指示队头元素和队尾元素。在向量空间中的位置，它们的初值在队列初始化时均应置为0。入队时：将新元素插入rear所指的位置，然后将rear加1。出队时：删去front所指的元素，然后将front加1并返回被删元素。

第41页，共91页，2023年，2月20日，星期三操作时应注意到以下两点：当头尾指针相等时，队列为空。在非空队列里，队头指针始终指向队头元素，尾指针始终指向队尾元素的下一位置。ABCDfrontrear(a)一个队列frontrear(b)删除一个元素后的队列frontrear(c)插入元素E后的队列图12-13插入与删除示图BCD

BCDE第42页，共91页，2023年，2月20日，星期三在实际应用中，队列的顺序存储结构一般采用循环队列的形式。所谓循环排列，就是将队列存储空间的最后一个位置绕到第一个位置，形成逻辑上的环状空间，供队列循环使用，如图12-14所示。在循环队列结构中，当存储空间的最后一个位置已被使用而再要进行入队运算时，只要存储空间的第一个位置空闲，便可将元素加入到第一个位置，即将存储字间的第一个位置作为队尾。在循环队列中，用队尾指针rear指向队列中的队尾元素，用排头指针front指向排头元素的前一个位置，因此，从排头指针front指向的后一个位置直到队尾指针rear指向的位置之间所有的元素均为队列中的元素。循环队列的初始状态为空，即rear=front=m。■12.5.3循环队列及其运算第43页，共91页，2023年，2月20日，星期三01m-1Q(0:m-1)…图12-14循环队列示意图第44页，共91页，2023年，2月20日，星期三1.循环队列两种基本运算：(1)入队运算每进行一次入队运算，队尾指针就进一。当队尾指针rear=m+1时，则置rear=1。(2)退队运算每进行一次退队运算，排头指针就进一。当排头指针front=m+1时，则置front=1。在实际使用循环队列时，为了能区分队列满还是队列空，通常还需增加一个标志s，s值的定义如下：由此可知：当s=0时，队列为空。当s=1且front=rear时，队列为满。第45页，共91页，2023年，2月20日，星期三2.循环队列入队与退队的算法(假设循环队列的初始状态为空，即：s=0，且front=rear=m。)(1)入队运算入队运算是指在循环队列的队尾加入一个新元素。这个运算有两个基本操作：首先将队尾指针进一（即rear=rear+1），并当rear=m+1时置rear=1；然后将新元素插入到队尾指针指向的位置。当循环队列非空（s=1）且队尾指针等于排头指针时，说明循环队列已满，不能进行入队运算。这种情况称为“上溢”。(2)退队运算退队运算是指在循环队列的排头位置退出一个元素并赋给指定的变量。这个运算有两个基本操作：首先将排头指针进一（即front=front+1），并当front=m+1时置front=1；然后将排头指针指向的元素赋给指定的变量。当循环队列为空（s=0）时，不能进行退队运算。这种情况称为“下溢”。第46页，共91页，2023年，2月20日，星期三3.循环链表两个特点：(1)在链表中增加了一个表头结点，其数据域为任意或者根据需要来设置，指针域指向线性表的第一个元素的结点，而循环链表的头指针指向表头结点。(2)循环链表中最后一个结点的指针域不是空，而是指向表头结点。即在循环链表中，所有结点的指针构成了一个环状链。如图12-15所示，其中图a是一个非空的循环链表，图b是一个空的循环链表。图12-15循环链表示意图第47页，共91页，2023年，2月20日，星期三树是一种重要的非线性数据结构，直观地看，它是数据元素（在树中称为结点）按分支关系组织起来的结构，很像自然界中的树那样。

12.6树与二叉树■12.6.1树的基本概念

第48页，共91页，2023年，2月20日，星期三树在计算机领域中也得到广泛应用，如在编译源程序时，可用树表示源程序的语法结构。又如在数据库系统中，树型结构也是信息的重要组织形式之一。1.树的定义树是由一个或多个结点组成的有限集合，其中：(1)必有一个特定的称为根(ROOT)的结点。(2)剩下的结点被分成ｎ≥0个互不相交的集合T1、T2、……Tn，而且，这些集合的每一个又都是树。树T1、T2、……Tn被称作根的子树(Subtree)。第49页，共91页，2023年，2月20日，星期三2.树结构的基本术语。(1)父结点：在树结构中，每一个结点的前件称为父结点，且只有一个父结点。(2)根结点：没有前件的结点称为树的根结点，简称为树的根。一棵树有且只有一个树根结点。例如，在图9.16中，结点R是树的根结点。(3)子结点：在树结构中，每一个结点可以有多个后件，它们都称为该结点的子结点。其中没有后件的结点称为叶子结点，也称为终端结点。例如，在图9.16中，结点C、M、F、E、X、G、S、L、Z、A均为叶子结点。(4)子孙（后裔）：如果在树中存在一条从结点K到结点M的路径，则称结点K是结点M的祖先，也称结点M是结点K的子孙。第50页，共91页，2023年，2月20日，星期三(5)结点的度：在树结构中，一个结点所拥有的后件个数称为该结点的度。例如，在图7.16中，根结点R的度为4；结点T的度为3；结点K、B、N、H的度为2：结点P、Q、D、O、Y、W的度为l；叶子结点的度为均为0，因为叶子结点没有后件结点。(6)树的度：在树中，所有结点中的最大的度称为树的度。例如，图9.16所示的树的度为4。(7)路径长度：如果存在树中的一个结点序列,,..,，使得结点是结点的父结点(1≤i≤j)，则称该结点序列是树中从结点到结点的一条路径或道路。称这条路径的长度为j-1，它是该路径所经过的边（即连接两个结点的线段）的数目。树中任一结点有一条到其自身的长度为零的路径。例如结点R到结点Y的路径长度为3。

第51页，共91页，2023年，2月20日，星期三(8)结点深度：从树根到任一结点n有唯一的一条路径，称这条路径的长度为结点n的深度或层数。根结点在第1层。同一层上所有结点的所有子结点都在下一层。树的最大层次称为树的深度。例如，图9.16所示的树的深度为5。(9)真祖先和真子孙：将树中一个结点的非自身祖先和子孙分别称为该结点的真祖先和真子孙。在一棵树中，树根是唯一没有真祖先的结点。叶结点是那些没有真子孙的结点。子树是树中某一结点及其所有真子孙组成的一棵树。例如，在图9.16中结点R有4棵子树，它们分别以K、P、Q、D为根结点；结点P有l棵子树，其根结点为N；结点T有3棵子树，它们分别以W、Z、A为根结点；在树中，叶子结点没有子树。第52页，共91页，2023年，2月20日，星期三(10)高度：树中一个结点的高度是指从该结点到作为它的子孙的各叶子结点的最长路径的长度。树的高度是指根结点的高度。例如图9.16中的结点K，B和C的高度分别为3，2和0。(11)森林：是m（m≥0）棵树的集合。如图9-16，去掉根结点R，其原来的二棵子树K、P、Q、D的集合{K，P，Q，D}就为森林。第53页，共91页，2023年，2月20日，星期三1．二叉树的基本概念二叉树(binarytree)是一种很有用的非线性结构。二叉树不同于前面介绍的树结构，但它与树结构很相似，并且，树结构的所有术语都可以用到二叉树这种数据结构上。它具有以下两个特点：（1）非空二叉树只有一个根结点；（2）每一个结点最多有两棵子树。两棵子树分别称为该结点的左子树与右子树。例图12-17所示即为一棵二叉树。根据二叉树的特点可知，二叉树的度可以为0（叶结点）、1（只有一棵子树）或2（有2棵子树），也就是说在二叉树中，每一个结点的度最大为2，即所有子树(左子树或右子树)也均为二叉树，而树结构中的每一个结点的度可以是任意的。

■12.6.2二叉树及其基本性质第54页，共91页，2023年，2月20日，星期三RTLTR左子树右子树R1R2L1L2L3L4图12-17二叉树结构第55页，共91页，2023年，2月20日，星期三在二叉树中，一个结点可以只有左子树而没有右子树，也可以只有右子树而没有左子树。当一个结点既没有左子树也没有右子树时，该结点即是叶子结点。要注意：一棵只有根结点的树是二叉树，没有结点的树也是二叉树。二叉树的五种基本形态如图12-18所示。ø图12-18二叉树的五种基本形态第56页，共91页，2023年，2月20日，星期三2．二叉树的基本性质二叉树具有以下几个性质：（1）在二叉树的第i层上，最多有2i-1（i≥1）个结点。叉树的第1层只有一个根结点，所以，i=1时，2i-1=21-1=20=1成立。假设对所有的j，1≤ji成立，即第j层上最多有个2j-1结点成立。若j=i-1，则第j层上最多有2j-1=2i-2个结点。由于在二叉树中，每个结点的度最大为2，所以可以推导出第i层最多的结点个数就是第i-1层最多结点个数的2倍，即2i-2×2=2i-1。第57页，共91页，2023年，2月20日，星期三（2）深度为m的二叉树最多有2m-1个结点。深度为m的二叉树是指二叉树共有m层。根据性质（1），只要将第1层到第m层上的最大的结点数相加，就可以得到整个二叉树中结点数的最大值，即:21-1+22-1+L+2m-1=2m-1（3）对于任意一棵二叉树BT，如果度为0的结点个数为n0，度为2的结点个数为n2，则n0=n2+1。（4）具有n个结点的二叉树，其深度至少为[]+1，其中[]表示取的整数部分。第58页，共91页，2023年，2月20日，星期三满二叉树与完全二叉树是两种特殊形态的二叉树。1．满二叉树所谓满二叉树是指这样的一种二叉树：除最后一层外，每一层上的所有结点都有两个子结点。这就是说，在满二叉树中，每一层上的结点数都达到最大值，即在满二叉树的第k层上有-1个结点，且深度为m的满二叉树有-1个结点。图12-19分别是深度为2、3、4的满二叉树。■12.6.3满二叉树与完全二叉树ACBACBACBDEFGEDFGNOLMJKIH图12-19满二叉树第59页，共91页，2023年，2月20日，星期三2．完全二叉树有一棵深度为h，具有n个结点的二叉树，若将它与一棵同深度的满二叉树中的所有结点按从上到下，从左到右的顺序分别进行编号，且该二叉树中的每个结点分别与满二叉树中编号为1至n的结点位置一一对应，则称这棵二叉树为完全二叉树。对于完全二叉树来说，叶子结点只可能在层次最大的两层上出现：对于任何一个结点，若其右分支下的子孙结点的最大层次为p，则其左分支下的子孙结点的最大层次或为p，或为p+l。图12-20是深度为3的完全二叉树及非完全二叉树。由满二叉树与完全二叉树的特点可以看出，满二叉树也是完全二叉树，而完全二叉树一般不是满二叉树。第60页，共91页，2023年，2月20日，星期三完全二叉树还具有以下两个性质：（1）具有n个结点的完全二叉树的深度为[log2n]+1。其中，[log2n]的结果是不大于的最大整数。（2）对于有n个结点的完全二叉树中的所有结点按从上到下，从左到右的顺序进行编号，则对任意一个结点i（1≤i≤n），都有：①如果i=1，则结点i是这棵完全二叉树的根，没有双亲；否则其双亲结点的编号为[i/2]。②如果2in，则结点i没有左孩子；否则其左孩子结点的编号为2i。③如果2i+1n，则结点i没有右孩子；否则其右孩子结点的编号为2i+1。第61页，共91页，2023年，2月20日，星期三BDAEHIJCFG完全二叉树(深度2)具有所有可能的结点BADECFG完全二叉树(深度3)BDAEHIC非完全二叉树(深度3)层次2遗漏结点BDAEHIKCFG非完全二叉树(深度3)层次3的结点不在最左边的位置HIDEBACHDBAEKICFG图12-20完全二叉树与非完全二叉树第62页，共91页，2023年，2月20日，星期三二叉树也可以采用两种存储方式：顺序存储结构和链式存储结构。1．二叉树的顺序存储结构这种存储结构适用于完全二叉树。其存储形式为：用一组连续的存储单元按照完全二叉树的每个结点编号的顺序存放结点内容。2．二叉树的链式存储结构在顺序存储结构中，利用编号表示元素的位置及元素之间孩子或双亲的关系，因此对于非完全二叉树，需要将空缺的位置用特定的符号填补，若空缺结点较多，势必造成空间利用率的下降。在这种情况下，就应该考虑使用链式存储结构。常见的二叉树结点结构如下所示：■12.6.4二叉树的存储结构LchilditemRchild第63页，共91页，2023年，2月20日，星期三二叉树是一种非线性的数据结构，在对它进行操作时，总是需要逐一对每个数据元素实施操作，这样就存在一个操作顺序问题，由此提出了二叉树的遍历操作。所谓遍历二叉树就是按某种顺序访问二叉树中的每个结点一次且仅一次的过程。这里的访问可以是输出、比较、更新、查看元素内容等等各种操作。二叉树的遍历方式分为两大类：一类按根、左子树和右子树三个部分进行访问；另一类按层次访问。在遍历二叉树的过程中，一般先遍历左树，再遍历右树。在先左后右的原则下，根据访问结点的顺序，二叉树的遍历可以分为三种：前序遍历、中序遍历、后序遍历。下面分别介绍这三种遍历的方法。■12.6.5二叉树的遍历第64页，共91页，2023年，2月20日，星期三1．前序遍历（DLR）所谓前序遍历是指在访问根结点、遍历左子树与遍历右子树这三者中，首先遍历根结点，然后访问左子树，最后遍历右子树；并且，在遍历左、右子树时，仍然先遍历根结点，然后访问左子树，最后遍历右子树。下面是二叉树前序遍历的简单描述：若二叉树为空，则结束返回。否则：（1）前序遍历左子树。（2）访问根结点（3）前序遍历右子树。第65页，共91页，2023年，2月20日，星期三2．中序遍历（LDR）所谓中序遍历是指在访问根结点、遍历左子树与遍历右子树这三者中，首先遍历左子树，然后访问根结点，最后遍历右子树；并且，在遍历左、右子树时，仍然先遍历左子树，然后访问根结点，最后遍历右子树。下面是二叉树中序遍历的简单描述：若二叉树为空，则结束返回。否则：（1）中序遍历左子树。（2）访问根结点。（3）中序遍历右子树。第66页，共91页，2023年，2月20日，星期三3．后序遍历（LRD）所谓后序遍历是指在访问根结点、遍历左子树与遍历右子树这三者中，首先遍历左子树，然后遍历右子树，最后访问根结点，并且，在遍历左、右子树时，仍然先遍历左子树，然后遍历右子树，最后访问根结点。下面是二叉树后序遍历的简单描述：若二叉数为空，则结束返回。否则：（1）后序遍历左子树。（2）后序遍历右子树。（3）访问根结点。第67页，共91页，2023年，2月20日，星期三第68页，共91页，2023年，2月20日，星期三查找是数据处理领域中的一个重要内容，查找的效率将直接影响到数据处理的效率。所谓查找是指在一个给定的数据结构中查找某个指定的元素。通常，根据不同的数据结构，应采用不同的查找方法

12.7查找技术■12.7.1顺序查找顺序查找又称顺序搜索。顺序查找一般是指在线性表中查找指定的元素，其基本方法是从线性表的第一个元素开始，依次将线性表中的元素与被查元素进行比较，若相等则表示找到(即查找成功)；若线性表中所有的元素都与被查元素进行了比较但都不相等，则表示线性表中没有要找的元素（即查找失败）。第69页，共91页，2023年，2月20日，星期三1．顺序查找过程（1）如果线性表中的第一个元素就是被查找元素，则只需做一次比较就查找成功，查找效率最高。（2）如果被查的元素是线性表中的最后一个元素，或者被查元素根本不在线性表中，则为了查找这个元素需要与线性表中所有的元素进行比较，这是顺序查找的最坏情况，在这种情况下需要比较n次。（3）在平均情况下，利用顺序查找法在线性表中查找一个元素，大约要与线性表中一半的元素进行比较。因此顺序查找一个具有n个元素的线性表，其平均复杂度为O（n）。■11.6.2计算机病毒及防治第70页，共91页，2023年，2月20日，星期三2．其他情况下的顺序查找对于大的线性表来说，顺序查找的效率是很低的。虽然顺序查找的效率不高，但在下列两种情况下也只能采用顺序查找：（1）如果线性表为无序表(即表中元素的排列是无序的)，则不管是顺序存储结构还是链式存储结构，都只能用顺序查找。（2）即使是有序线性表，如果采用链式存储结构，也只能用顺序查找。第71页，共91页，2023年，2月20日，星期三■12.7.2二分法查询二分法查找只适用于顺序存储的有序表。在此所说的有序表是指线性表中的元素按值非递减排列（即从小到大，但允许相邻元素值相等）。设有序线性表的长度为n，被查元素为x，则对分查找的方法如下：1．将x与线性表的中间项进行比较；2．若中间项的值等于x，则说明查到，查找结束；3．若x小于中间项的值，则在线性表的前半部分（即中间项以前的部分）以相同的方法进行查找；4．若x大于中间项的值，则在线性表的后半部分（即中间项以后的部分）以相同的方法进行查找。第72页，共91页，2023年，2月20日，星期三■12.8.1交换类排序法排序也是数据处理的重要内容。所谓排序是指将一个无序序列整理成按值非递减顺序排列的有序序列。排序的方法有很多，排序可以在各种不同的存储结构上实现。本节主要介绍一些常用的排序方法。其排序的对象一般认为是顺序存储的线性表，在程序设计语言中就是一维数组。12.8排序技术所谓交换类排序法是指借助数据元素之间的互相交换进行排序的一种方法。冒泡排序法与快速排序法都属于交换类的排序方法。1．冒泡排序法冒泡排序法是一种最简单的交换类排序方法，它是通过相邻数据元素的交换逐步将线性表变成有序。第73页，共91页，2023年，2月20日，星期三冒泡排序法的基本过程如下：首先，从表头开始往后扫描线性表，在扫描过程中逐次比较相邻两个元素的大小。若相邻两个元素中，前面的元素大于后面的元素，则将它们互换，称之为消去了一个逆序。显然，在扫描过程中，不断地将两相邻元素中的大者往后移动，最后就将线性表中的最大者换到了表的最后，这也是线性表中最大元素应有的位置。然后，从后到前扫描剩下的线性表，同样，在扫描过程中逐次比较相邻两个元素的大小。若相邻两个元素中，后面的元素小于前面的元素，则将它们互换，这样就又消去了一个逆序。显然，在扫描过程中，不断地将两相邻元素中的小者往前移动，最后就将剩下线性表中的最小者换到了表的最前面，这也是线性表中最小元素应有的位置。对剩下的线性表重复上述过程，直到剩下的线性表变空为止，此时的线性表已经变为有序。第74页，共91页，2023年，2月20日，星期三2．快速排序法在前面所讨论的冒泡排序法中，由于在扫描过程中只对相邻两个元素进行比较，因此，在互换两个相邻元素时只能消除一个逆序。如果通过两个(不是相邻的)元素的交换，能够消除线性表中的多个逆序，就会大大加快排序的速度。下面介绍的快速排序法可以实现通过一次交换而消除多个逆序。快速排序法也是一种互换类的排序方法，但由于它比冒泡排序法的速度快，因此称之为快速排序法。第75页，共91页，2023年，2月20日，星期三快速排序法的基本思想如下：（1）从线性表中选取一个元素，设为T，将线性表后面小于T的元素移到前面，而前面大于T的元素移到后面，结果就将线性表分成了两部分(称为两个子表)，T插入到其分界线的位置处，这个过程称为线性表的分割。（2）通过对线性表的一次分割，就以T为分界线，将线性表分成了前后两个子表，且前面子表中的所有元素均不大于T，而后面子表中的所有元素均不小于T。如果对分割后的各子表再按上述原则进行分割，并且，这种分割过程可以一直做下去，直到所有子表为空为止。则此时的线性表就变成有序表。（3）由此可知，快速排序法的关键是对线性表进行分割，第76页，共91页，2023年，2月20日，星期三■12.8.2插入类排序法冒泡排序法与快速排序法本质上都是通过数据元素的交换来逐步消除线性表中的逆序。本小节讨论另一类排序的方法，即插入类排序法。有一个已经有序的数据序列，要求在这个已经排好的数据序列中插入一个数，但要求插入后此数据序列仍然有序，这个时候就要用到的就是插入排序法，插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中,从而得到一个新的、个数加一的有序数据，算法适用于少量数据的排序，是稳定的排序方法。第77页，共91页，2023年，2月20日，星期三1．简单插入排序法所谓插入排序是指将无序序列中的各元素依次插入到已经有序的线性表中。可以想像，在线性表中，只包含第1个元素的子表显然可以看成是有序表。接下来的问题是，从线性表的第2个元素开始直到最后一个元素，逐次将其中的每一个元素插入到前面已经有序的子表中。一般来说，假设线性表中前j—1个元素已经有序，现在要将线性表中第j个元素插入到前面的有序子表中，插入过程如下：首先将第j个元素放到一个变量T中，然后从有序子表的最后一个元素(即线性表中第i—1个元素)开始，往前逐个与T进行比较，将大于T的元素均依次向后移动一个位置，直到发现一个元素不大于T为止，此时就将T(即原线性表中的第j个元素)插入到刚移出的空位置上，有序子表的长度就变为j了。第78页，共91页，2023年，2月20日，星期三第79页，共91页，2023年，2月20日，星期三2．希尔排序法希尔排序法(ShellSort)属于插入类排序，但它对简单插入排序做了较大的改进。希尔排序法的基本思想是将整个无序序列分割成若干小的子序列分别进行插入排序。子序列的分割方法如下：将相隔某个增量h的元素构成一个子序列。在排序过程中，逐次减小这个增量，最后当h减到l时，进行一次插入排序，排序就完成。增量序列一般取h=n/2k（k=l，2，…，[log2n]），其中n为待排序序列的长度。图12-23为希尔排序法的示意图。第80页，共91页，2023年，2月20日，星期三第81页，共91页，2023年，2月20日，星期三■12.8.3选择类排序法1．简单选择排序法选择排序法的基本思想是扫描整个线性表，从中选出最小的元素，将它交换到表的最前面(这是它应有的位置)；然后对剩下的子表采用同样的方法，直到子表空为止。对于长度为n的序列，选择排序需要扫描n-l遍，每一遍描述均从剩下的子表中选出最小的元素，然后将该最小的元素与子表中的第一个元素进行交换。简单选择排序法在最坏情况下需要比较n(n-1)/2次。第82页，共91页，2023年，2月20日，星期三2．堆排序法堆排序法属于选择类的排序方法。堆的定义如下：具有n个元素的序列（h1,h2，…，hn），当且仅当满足hi≥h2i或hi≤h2i

hi≥h2i+1hi≤h2i+1

（i=1，2，…，n/2）时称之为堆。本节只讨论满足前者条件的堆。由堆的定义