第五章-数据结构基础

第五章数据结构基础5.1引言数据是对客观事物的符号表示，在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称，是程序加工的原始材料。它可以是数字、字符串或两者兼而有之；可以是从磁带或磁盘上读出的一串二进制数；也可以是模数转换器的输出(即采样了大电子信号)；也可以是键盘操作的输出等。

任何程序都要处理数据，把数据从最初的格式转换成结果所需的格式。例如记账程序，将业务往来的数据转换成收入和支出的报表。可见，程序是将原始资料转换成最终格式的一种或一组工具。数据的组织和处理过程是影响程序开发的最重要因素，也是主要控制程序设计的原始材料。简洁而高效的程序设计，自然依赖于数据的组织形式，这便是数据结构产生的背景。5.1.1什么是数据结构所谓数据结构是指数据之间的相互关系；它包括三方面内容：数据的逻辑结构、数据的存储结构和数据的运算。例如，一个线性表，它的逻辑结构是指表中每个元素前后之间的逻辑关系；它的存储结构是指表中元素在存储器中的存储方式(是顺序存储还是链式存储)；对它的运算包括插入、删除、检索、更新、排序等等。学号姓名性别出生时间入学时间籍贯院系班级10011002……张三丰貂蝉……男女………………辽宁山西……计算机系计算机系……计061计061……5.1.1什么是数据结构表中每个学生各占一行，每行的信息说明一个学生的情况，是学生档案表的基本单位，我们把整个学生档案为一个数据结构。表中的每一行称为一个结点(也称为元素、记录表目等，是数据结构中的基本单位)。每一行由一系列数据项组成，数据项又称字段，能唯一确定一个结点的字段称为关键码。上例中学号字段就是关键码，它能唯一确定一个学生的情况。数据类型是和数据结构紧密相关的一个概念，它是一个值的集合和定义在这个值集上的一组操作的总称。按照“值”的不同特性，高级程序语言中的数据类型可以分为两类：一类是非结构的原子类型。原子类型是不可分解的。另一类是结构类型，即由原子类型构造而成的。抽象数据类型是指一个数学模型以及定义在该模型上的一组操作。抽象数据类型与数据类型实质上是一个概念，对于用户来讲它们都是用来定义计算机中具有一定特性的数据的，“抽象”的意义在于数据类型的数学抽象特性。5.1.1什么是数据结构上述学生档案表就是一个线性表，表中结点与结点之间是简单的线性关系，每一个数据元素都有自己相应的数据类型。表中第一个结点称为表头，最后一个结点称表尾，其他结点有一个前趋和一个后继，这就是人事档案表的逻辑结构。如果结点和结点之间采用顺序方式存放在计算机系统中，这就是存储结构。表中的结点随学生情况的变更，要执行增加、删除、更新等操作，这就是数据的运算问题。5.1.2数据的逻辑结构对数据之间关系的描述是数据的逻辑结构，可以用一个二元组来表示：B=(K,R)式中，K是结点的有穷集合，R是K上的关系的有穷集合。有时也将数据的逻辑结构称为数据结构。每个结点k(k∈K)的值(即数据)可以由几个字段组成。每个字段可以有一个或多个初等项和组合组成。结点可以分为初等类型和组合类型。只包含一个初等项的结点属于初等类型，否则属于组合类型。5.1.2数据的逻辑结构只包含一个初等项的结点属于初等类型，否则属于组合类型。所谓初等类型就是计算机能直接存储并能直接用机器指令对它们进行处理的数据类型。整型、实型、字符型等就是初等类型。组合类型是由初到类型用某种方式结合而成的数据类型，记录(或结构)类型等就是组合类型。指针是一种特殊的类型，它的值一般来说对应于存储器中的一个地址或相对地址。学生档案表中的结点就是属于组合类型。根据数据元素之间的关系的不同特性，数据结构通常分为四种基本结构：1.

集合结构中的元素仅仅只是同属于一个集合，不存在其他关系2.

线性结构结构中的元素之间是一对一的关系。3.

树型结构结构中的元素之间是一对多的关系。4.

图型结构结构中的元素之间存在多对多的关系。5.1.2数据的逻辑结构基本结构关系示意图结点与结构是相对而言的。不严格的说，结构是由若干结点及其相互的关系所组成的。在特殊场合下，需要研究某个结点内部组成时，也可以把结点看成一个结构，而把组成该结点的数据项看作为结点，把数据项组成该结点的组成方式看作为结点之间的关系。5.1.3数据的存储结构数据的存储结构是它的逻辑结构在计算机存储器中的实现，也称为物理结构。它是依赖于计算机的。计算机的存储器是由许多存储单元组成的，每个单元有唯一的地址，各存储单元的地址是连续编码的。一片相邻的存储单元的整体称为存储区M。要把逻辑结构B＝(K,R)存到计算机中，就要建立一个从K的结点到M的映射S:K－>M，同时该映射应具有显式或隐式地体现关系R的能力。5.1.3数据的存储结构有四种基本的存储映射方式：1. 顺序映射方式主要用于线性数据结构。该映射方式是把逻辑上相邻的结点存储在物理上相邻的存储单元里，结点之间的逻辑关系由存储单元的邻接关系体现出来。2. 链接映射方式给每个结点附加一个指针字段，即将结点占用的存储单元分为存放结点本身信息(数据项)和存放其后继结点所对应的存储单元的地址(指针项)两部分。指针项可以包含一个或多个指针，以指向结点的一个或多个后继。3. 索引映射方式将结点按关键字排成一个序列，这样每个结点在序列中均有一个对应的位置数，这个位置就是结点索引。索引映射就是用结点索引号来确定结点的存储地址。4. 散列映射方式这是一种根据结点关键字的值，通过计算来确定其存储地址的方法，所以又称为关键码——地址转换法。用散列映射时，K的结点k分散列地存储在M的存储单元里。5.1.4数据的运算所谓数据的运算是指对于数据的进行某一特定处理的操作。计算机中的数据运算是包括数值运算和抽象数据类型的运算两方面内容的。在本书第一章中已经介绍了关于计算机中数值运算的基本概念和方法，在本章中我们主要讨论抽象数据类型的运算。数据的运算是定义在数据的逻辑结构上的，而运算的具体的实现要在存储结构上进行。数据的每一种逻辑结构都有一个运算的集合。常用的运算有检索、插入、更新、排序等。5.2线性结构线性结构是一种最常用且最简单的数据结构，其结点之间存在着一一对应的相互关系。无论是现实世界还是计算机应用中，线性结构都有广泛的应用。如我们利用自然语言，表述一句话或写作一篇文章都是把文字按照线性的方式组织起来的；又如操作键盘向计算机中输入的信息也是线性结构。本节主要介绍线性结构的存储表示、运算的具体实现等有关内容。5.2.1线性表所谓线性表是由n≥0个结点组成的有限序列。表中有且只有一个开始结点(表头)，它没有前趋而只有一个后继；有且只有一个终端结点(表尾)，它没有后继而只有一个前趋；其余结点都只有一个前趋和一个后继。根据它们之间的关系可以排成一个线性序列：(a1，a2,……,an)这里，a1为开始结点；an为终端结点；ai-1是ai的前趋，ai是ai-1的后继。n称为该表的长度。长度n＝0的表称为空表。将一个线性表存入计算机，可采用许多不同的方法。一种简单而且自然的存储方法是顺序存储：即把结点按其索引从小到大一个接一个地存放在一片连续的存储区内。假设表中每个结点所需L个内存单位，则表的第I个结点的存储地址为：LOC(ai)=LOC(a1)+L*(i-1)式中，LOC(a1)为表中第一个结点的存储地址。利用此公式可以很快算出表中任一结点的地址。5.2.1线性表如果线性表的所有结点都具两个主要类型，称其为向量(或一维数组)。向量的结点称为元素，元素的索引称为下标。向量有两个主要的特性：一是均匀性，向量所有元素必须具有相同的元素描述(不管元素是简单的还是复杂的，都要一致)，元素长度相同；二是有序性，向量中各元素是有序的，并且元素之间的次序时不能改变的。对向量经常进行的运算有下列几种：向量中的第i个元素；修改向量中的第i个元素；删除向量中的第i个元素；在向量第i个元素之后(或之前)插入一个新元素；对向量中的元素按某个数据项值递增(或递减)的顺序进行重新排序；按某个特定值查找向量中的元素。5.2.1线性表对于向量中的插入和删除运算，由于需要保持运算结果仍然是顺序存储，因此要移动一系列元素。在插入和删除过程中，向量中元素的个数n不能超过某个整数N0。在所有的程序设计语言中，都已建立了向量(即一维数组)的形式定义并实现了对向量的运算。因此，用语言编制程序时只要按所有语言的规定引用即可。5.2.2栈栈是一种线性表，它限定只能在表的一端进行插入和删除。在表中，允许插入和删除的一端称为栈顶，而不允许插入和删除的另一端称为栈底。根据上述定义，栈的修改时按后进先出的原则进行的，因此栈又称后进先出(LIFO)表。栈通常是顺序存储的，分配一片连续的存储区域来存放栈中的结点，并用一个变量来指示当前栈顶的位置。5.2.2栈栈在系统软件中用得很多，包括编译器和解释程序。事实上，大多数C编译器都利用栈将参数传递给函数。入栈和出栈是栈的两个基本操作。要实现栈，需要两个函数：push()和pop()。push()将新结点置于栈顶，而pop()函数将结点从栈顶取出。除此之外，还要用数组为栈在内存中安排空间。根据存放数据的类型和可能要存放数据的最大数目，定义一维数组stack,用下标变量top作为栈顶的指示变量。top=0表示栈空，数组元素stack[0]称为栈底，stack[top]表示最新进栈的元素，称为栈顶。当top的值等于数组的最大下标时，则栈满。5.2.2栈栈的一个重要作用是在程序设计语言中实现递归过程。程序设计语言的运行组织是在程序运行期间表示程序变量值的一组数据结构。任何允许使用递归过程的语言，如C、pascal、APL、LISP和PL/1等，都要将属于各递归层次的过程变量的值所组成的现场纪录保存在一个栈中。每当需要调用过程P时，就要在栈顶为P建立一个新的现场纪录，无论栈中是否已有过去调用P时建立的其他现场纪录。一旦结束当前对过程P的调用，则将相应的现场纪录从栈中取走。当P返回时，相应的现场纪录一定是在栈顶，因为只有当执行P时所调用的其它过程都已返回后，P才能返回。从而保证在P返回时，其相应的现场纪录又出现在栈顶。从该记录中，可知调用P的指令地址，以控制P的返回。5.2.2栈递归可以使程序简洁而清晰，但一般情况下它既不省时间，也不省空间，因为它必须依赖系统中的运行栈，保存每次调用时的参数、变量及返回信息等。这个运行栈对用户来说是不可见的。通常任何递归过程(或函数)都可修改成非递归的形式。这就需要用户自己定义一个栈，以保存调用时的现场纪录。现场纪录一般含有过程参数的当前值、过程的所有局部变量的当前值和表示返回地址的值(即当前调用的过程结束时，控制返回位置的值)。非递归过程虽然运行快，也省内存，但它结构复杂、不易理解，只有当程序的运行速度非常重要时，采用非递归过程才是适宜的。5.2.3队列队列也是一种线性表，对于它所有的插入都在表的一端进行，而所有的删除都在表的另一端进行。插入数据的一端称为队列的头，删除数据的一端称为队列的尾。满足先进先出的原则，简称为先进先出(FIFO)表。队列总日常生活中到处可见，银行、快餐店中顾客的队都是队列。队列在程序设计中也经常出现，例如操作系统中作业排队。在可运行多道程序的计算机系统中，同时有几个作业运行，运行的结果都需要通过通道输出。若通道未完成传输，则作业等待，并按请求输出的先后顺序排队。当通道传输完毕可接受新的传输任务时，排头的作业便从队列中退出，并准备输出。排头的作业是下次要输出的作业，排尾的作业是刚进入队列的作业。5.2.3队列通常队列用顺序存储的形式实现，分配一片连续的存储空间来存放队列元素，并用两个变量分别指向当前队列的排头和排尾。入队和出队是队列的两个基本操作。根据存放数据的类型和可能存放数据的最大数目，定义一维数组queue,用下标变量front和rear分别指示队列的排头和排尾。5.2.3队列由于队列的两端是变的，需要克服假溢出问题，即当排头位置的元素已经出队产生了空位置，但排尾元素填满，队列依然被认为是满的，在进行入队操作就会“溢出”。一个满意的办法是把队列设想为一个首尾相接的环形表。5.2.3队列初始状态，变量front和rear的值为0，队列空。如果有MAX+1个元素要参加排队，则数组queue的下标范围从0到MAX。要加入一个数据时，排尾指示变量rear的值取下一个相邻单元的下标，数据赋给修改后rear指示的单元。如果修改前的rear值为MAX，则queae[0]作为queue[MAX]的下一个单元。如果修改后rear的值与front的值相等，表示环形队列首尾相接，这时为队满，不能再加入任何数据了。需恢复rear的原来值，并向系统报告队满。从队列取数据时，想修改front使其指示下一个队列元素，然后取出front所指单元的数据。如果修改前front与rear的值相等，说明队列空，没有可取数据。结论是：向队列加入数据时要判断队列是否满，从队列取数据时要判断是否空。5.2.4链表采用顺序存储方式的线性表，在插入和删除操作时往往造成大量信息的移动，效率较低。同时，顺序存储必须占用一片连续的存储空间，存储分配只能预先进行。如果插入数据量超出预先分配的存储空间，要临时扩大有很大困难。对插入和删除操作频繁、存储空间大小难以预先确定的线性表，通常采用链式存储。链式存储的线性表称为链表。其结点一般由两部分组成：一部分存放结点的数据，称为数据字段；另一部分存放指向一下结点的地址，称为指针字段。5.2.4链表利用以上的存储结构就可以把物理上不连续的结点利用指针连成一个链表，即线性表的链式存储结构。链式存储结构可以应用于各类线性表中，以提高存储性能。1. 链式栈链式栈的结构如图所示，top为指向栈顶结点的指针变量。在初始状态下，top的值为空，用∧表示，说明栈中没有任何结点。当一个数据要进栈时，先要向系统申请一个结点，把数据存入数据字段，然后按规定拨动指针将其链入栈中。当要从栈中删除一个结点时，要先取出栈顶结点中的数据，然后把该结点指针字段的值赋给指针变量top，调用free函数释放该结点。5.2.4链表2. 链式队列下图是链式队列及其插入和删除操作示意图。指针变量front指向队列的头结点，rear指向队列的尾结点。队空时，front和rear均为空。向对中插入一个结点时，先向系统申请结点，将该结点链入rear所指向的指针字段，并使rear指向新的结点。如果插入的新结点前队是空的，则还要使front指向新插入的结点。要从队中删除一个结点时，要把front所指结点的指针字段值赋给front，然后释放该结点，也可能删除一个结点后队列为空，则需置rear为空。5.2.4链表3. 单向链表下图是单向链表及其插入和删除操作示意图。指针变量head指向单向链表的表头结点。表头结点中数据字段通常不用，指针字段用于存放第一个结点的指针。5.2.3链表4. 单环链表将单链表的形式稍加改动，让表中最后一个结点的指针指向单链表的表头结点，这就形成了一个环链表，称为单环链表。图(a)所示的单环链表中，为了要找到最后一个结点，必须从head出发，访问所有的结点。如果改用表尾变量rear来代替head,rear指向最后一个结点，如图(b)所示。从最后一个结点的指针字段立即可找到第一个结点的位置。这样改动后，无论找最后一个结点还是找第一个结点都很方便。实用中常采用这种方式。5.2.3链表5. 双向链表双向链表的每一个结点除了数据字段外，还包括两个指针，一个指针，一个指向该结点的后继结点，另一个指针指向它的前趋结点。双向链表有两个好处：一是可以从两个方向搜索某个结点，这不但使链表的排序操作变得比较简单，而且在数据库情况下允许用户在两个方向进行搜索；二是无论利用向量前这一链还是向后这一链，都可以遍历整个链表。如果有一根链失效了，还可以利用另一根链修复整个链表。5.2.3链表6. 双向循环链表类似单向环链表，也可以将双链表的头结点和尾结点链接起来。这样不增加额外内存却给某些运算带来了方便。通常将链表的头尾指针存放在一个称为表头结点的特殊结点之中。该结点链接在始结点和终结点之间，从而构成如图5.11所示的双向环链表。表头结点的数据字段可以空着不用，也可以用来存储诸如表中结点个数等信息。表头结点的引入使得双环链表一创建就有结点存在，这给某些运算带来方便。双向链表的插入和删除操作与双链表相同。5.3树形结构树形结构是一种重要的非线性数据结构，其结点之间具有分支和层次关系，在各种算法问题求解、文件管理系统和数据库系统中有广泛的应用。本节主要介绍树形结构的存储表示、运算的具体实现等有关内容。5.3.1树及其遍历树的递归定义：树T是一个或多个结点的有限集合。它满足如下条件：(1)有一个特别指定的结点称为根结点；(2)其余结点分别成为m≥0个互不相交的子集T1、T2、…、Tm,每一子集Ti都是一颗树，称为根的子树。树的结构5.3.1树及其遍历一个结点的子树个数称为该结点的度数。度数为0的结点称为叶或终端结点。度数大于0的结点称为非终端结点。树形结构中常使用家族关系来描述。图中结点A是结点B和C的父结点，而B和C是A的子结点；B和C是兄弟；D、E、F是B的子结点，I又是E的子结点，B是D、E、F和I的祖先，D、E、F和I是B的后代。树T中如果子树T1、T2、…、Tm的相对次序是重要的，则称树T为有序树。在有序树中可以称T1为根的第一棵子树，T2为根的第二棵子树，等等。由零棵或多棵树构成的集合称为森林。删去树根，树就变成森林，加上一个结点作树根，森林就变成树。右图就是去掉树根A得到的森林。5.3.1树及其遍历树型结构的重要运算是遍历。遍历一棵树就是按一定的次序系统地访问树的所有结点，使每个结点恰好被访问一次。遍历一棵树的过程实际上把树进行线性化。遍历树和森林可以按深度优先遍历，也可按广度优先遍历。1. 深度优先遍历，有先根次序和后根次序两种方法。先根次序的递归定义：(1)访问的一棵树的根；(2)在先根次序下遍历的一棵树根的子树；(3)在先根次序下遍历其它的树。后根次序的递归定义：(1)在后根次序下遍历第一棵树根的子树；(2)访问第一棵树的根；(3)在后根次序下遍历其它的树。5.3.1树及其遍历如图所示的森林，按先根次序遍历得到的结点序列是:

BEFGKCHILMDJ按后根次序遍历得到的结点序列是：

EFKGBHLMICJD5.3.1树及其遍历2. 广度优先遍历首先依次访问层数为0的结点，然后依次访问层次为1的结点，等等，直到访问完最后一层的所有结点。即访问是从上到下、从左到右依次进行的。按广度优先遍历上图所示的森林，得到的结点序列是：

BCDEFGHIJKLM遍历树形结构是系统地访问树或森林的所有结点。可以利用树形结构的遍历来查找满足某种条件的结点，形同于线性表的顺序查找。5.3.2二叉树二叉树的定义：二叉树是结点的有限集合，此集合或为空集，或为由一个根结点和两棵互不相交的称为左右的二叉树构成。二叉树的结构5.3.2二叉树由定义可知二叉树中每个结点至多只有两个子树。二叉树与树有区别：树至少有一个结点，而二叉树可以是空的；树的子树不区分其次序，二叉树的子树有左右之分。下图是二叉树的五种基本形式。5.3.2二叉树在计算机中，为了表示二叉树结点之间的关系，最自然的方法是链接方法。二叉树的每个结点至多只有两棵子树。因此，在每个结点中除存储结点本身的数据外，再设置两个指针字段llink和rlink,分别指向结点的左子树和右子树。当结点的某个子树为空时，相应的指针为空指针。结点的形式为：5.3.2二叉树这样，一棵二叉树里所有这种形式的结点，再加上一个指向树根的指针root构成二叉树的存储表示。这种存储表示又称为llink－rlink表示法。下图是二叉树的llink－rlink表示。5.3.2二叉树树和二叉树不同，树的每个结点的子结点数没有作限制。因此，如果也采用二叉树的方法在结点内设置指针，则每个结点内设置的指针数不好确定。若以树中子结点最多的结点来统一设置指针，显然浪费内存空间。若以每个结点的实际子结点数来设置指针，则各个结点大小不统一，很难管理。由于树或森林与二叉树之间有一个对应关系，任何森林均可唯一地对应到一棵二叉树。反过来，任何一棵二叉树也能唯一地对应到一棵树或森林。因此，通常可先把树或森林转换成一棵对应的二叉树，然后再用llink－rlink的方法进行存储和运算。最后再将二叉树转换成树或森林。如果将森林F看作树的有序集合，F=(T1,T2,…,Tn)，则对应于F的二叉树B(F)定义如下：(1)若n=0,到B(F)为空；(2)若n>0,则B(F)的根是T1的根W1,B(F)的左子树是B(T11,T12,…,T1m)，其中T11,T12,…,T1m是W1的子树；B(F)的右子树是B(T2,…,Tn)。5.3.2二叉树用一种自然方式来描述这种转换：兄弟之间用连线连起来；保留父结点到第一个子结点的连线，去掉其余子结点与父结点的连线。下图表示森林转换成二叉树的结果。(a)森林b)转换后未经整理的二叉树(c)经整理后的二叉树5.3.2二叉树反之，一棵二叉树唯一地对应于一棵树或森林。设B为一棵二叉树，W为B的根，L、R分别为W的左、右子树，则对应的树或森林F(B)定义如下：(1)若B为空，则F(B)是空的森林；(2)若B不为空，则F(B)是一棵树T1加上森林F(R)，其中树T1的根为W，W的子树为F(L)。用一个自然方式来描述这种转换：若结点是其父结点的左子树，则把该结点的右子树，右子树的右子树，都与该结点的父结点用线连接起来，然后去掉所有父结点到右子树的连线。(a)二叉树(b)经整理后的森林5.3.2二叉树二叉树概念很重要。一方面，许多实际问题中抽象出来的数据结点是二叉树的形式，而且许多算法问题可以方便地用二叉树形式来解决。另一方面，树或森林与二叉树之间有唯一的一一对应关系，这为树的存储与运算带来了方便。二叉树具有下列特性：(1)深度为k的二叉树的结点总数最大为：2k-1(k≥1)；在二叉树第i层的结点数最大为：2i-1(i≥1)。(2)任何一棵二叉树T，如果其终端结点数为n0，而其度数为2的结点数为n2，则n0=n2+1。(3)如果有n个结点的完全二叉树(其深度为log2n+1),从前第一层的结点自上而下、自左至右地对结点进行编号(1～n)，则对任一结点i(1≤i≤n)有：a、如果i≠1，则其父结点的编号为;如果i=1，则i为根，无父结点b、如果2i≤n，则其左子树结点的编号为2i;如2i>n,则I无左子结点。c、如果2i+1≤n，则其右子树的编号为2i+1;如果2i+1>n，则I无右子结点。5.3.2二叉树所有结点的平衡因子的绝对值不大于1的二叉树称为平衡二叉树。所谓平衡因子，就是二叉树中任一结点的右子树的深度与左子树的深度之差。图5-20(a)是非平衡二叉树的例子。5.3.2二叉树一棵深度为k的有2k-1个结点的二叉树，称为深度为k的满二叉树(k≥1)。图5-20(b)为一棵深度为4的满二叉树。5.3.2二叉树如果一棵二叉树有n(2i-1≤n≤2i+1-1,i≥1)个结点，其中2i-1个结点排满上面i个层，而剩下的n-(2i-1)个结点从左到右排在第i+1层，则称该二叉树为完全二叉树(有时又称拟满二叉树)。图5-20(c)是一棵完全二叉树。5.3.2二叉树如果一棵二叉树有n(2i-1≤n≤2i+1-1,i≥1)个结点，其中2i-1个结点排满上面i个层，而剩下的n-(2i-1)个结点随意地排在第i+1层上，则称该二叉树为丰满二叉树，图5-20(d)是一棵丰满二叉树。由上定义可知，满二叉树一定是完全二叉树，也是丰满二叉树。而完全二叉树一定是丰满二叉树。反之则不然。5.3.3遍历二叉树遍历二叉树是指按一定规律访问二叉树的每个结点，使每个结点被访问一次，而且只被访问一次。按照访问结点的次序。可得到二叉树结点的线性序列。由于二叉树是一种非线性结构，要找一个完整而有规律的遍历方法，以便得到二叉树结点的一个线性序列。令L、D、R分别表示遍历左子树、访问根结点、遍历右子树，则对一棵二叉树可有LDR、LRD、DLR、DRL、RDL和LRD六种情况。若限定先左后右，则只有DLR、LRD和LRD三种情况，分别称为先根顺序遍历、中根顺序遍历和后根顺序遍历。三种遍历二叉树的递归算法定义如下：先根顺序遍历：若二叉树为空，则退出；否则，访问根结点，按先根顺序遍历左子树，按先根顺序遍历右子树。中根顺序遍历：若二叉树为空，则退出；否则，按中根顺序遍历左子树，访问根结点，按中根顺序遍历右子树。后根顺序遍历：若二叉树为空，则退出；否则，按后根顺序遍历左子树，按后根顺序遍历右子树，访问根结点。5.3.3遍历二叉树例如图5-21所示的二叉树的按照不同顺序的遍历序列有：先根遍历序列：ABDGEHCFIJ中根遍历序列：DGBEHACIFJ后根遍历序列：GDHEBIJFCA5.4图形结构图形结构在计算机科学、人工智能、工程学等许多领域中均有广泛的应用。本节介绍图形结构的存储表示及有关操作。5.4.1图的概念数据结构B=(K,R)仅含一种任意的关系N,则称这种数据结构为图。通常，图用G=(V,E)来表示。图中结点又称为顶点，V是结点的非空有限集合，结点的偶对称为边，E是边的集合。图中代表一条边的偶对称如是无序的，则此图称为无向图；如果是有序的，则此图称为有向图。无向图和有向图有些性质是相同的。无向图中(V1,V2)和(V2,V1)这两个偶对代表同一条边。有向图中<V1,V2>和<V2,V1>这两个偶对代表不同的两条边，它们有自己的始点和终点。有向图中的边有时也称为弧。(a)无向图(b)有向图5.4.1图的概念边集E为空的图称为零图。边集E为空且结点V中只有一个元素的图称为平凡图。任何一个具有n个结点的无向图，其边数小于等于n*(n-1)/2。边数正好为n*(n-1)/2的n个结点的无向图称为完全图。任何一个具有n个结点的有向图，其最大边数为n*(n-1)/2。若(V1,V2)∈E，则称V1和V2是相邻结点，而边(V1,V2)则是与结点V1和V2相关连的边。若<V1,V2>是有向图一条边，则称结点V1邻接到结点V2，结点V2邻接于结点V1,而边<V1,V2>是与结点V1和V2相关连的。与图中结点k相关连的边的数目，称为该结点的度。在有向图中，以结点k为终点的边的数目，称为k的入度；以结点k为始点的边的数目，称为k的出度。有向图中出度为0的结点称为叶。图G=(V,E)和图G’(V’,E’),若V’包含于V,E’包含于E,且E’中的边所关连的结点均在V’中，则称图G’为图G的子图。5.4.1图的概念在图G=(V,E)中，如果存在结点序列V1、V2、…、Vk,使(V1,V2)、(V2,V3)、…、(Vk-1,Vk)都在E中(对有向图，则使得<V1,V2>、…、<Vk-1,Vk>都在E中)，则称从结点V1到Vk存在一条路径。路径上的边数称为长度。如果一条路径上的点除V1和Vk可以相同外，其他结点都不相同，则称该路径为简单路径。如果V1和Vk是同一个结点，则此简单路径称为回路。设图G(V,E)中，至少存在一个结点W(W∈V)，由W出发可以到达图中其他所有结点，则称W是图的根，称图G为有根图。对于无向图G=(V,E)，如果从Vi到Vj有一条路径(从Vi到Vj也有一条路径)，则称Vi和Vj是连通的。若G中任意两个结点都是连通的，则称G是连通的。一个无向图的最大连通子图，称为该图的连通分支。5.4.1图的概念对于有向图G=(V,E)，如果略去有向边的方向所得的无向图是连通的，则称G是弱连通的。若G是弱连通的，且G中任意两结点之间至少有一个结点可以到达另一个结点，则称G为单向连通的。若G中任意一对结点之间都是互相可达的，则称此有向图是强连通的。一有向图的强连通的最大子树，称为该有向图的强连通分支。如果给图G=(V,E)的每一条边加一个权值，称此图为带权图。带权的连通图又称为网。如图5-23所示。5.4.2图的存储表示法这里主要介绍图的邻接矩阵表示法。在计算机中常用邻接矩阵来表示图。表示图中结点之间相邻关系的矩阵称为邻接矩阵。一个有n个结点的图G，其邻接矩阵咳定义为n*n的矩阵A，即

1,若(Vj,Vj)或<Vj,Vj>∈EA[i,j]= 0,否则图5-24中G1和G2的邻接矩阵分别为A1和A2。5.4.2图的存储表示法图5-24G1和G2的邻接矩阵5.4.2图的存储表示法对于带权图(网)，其邻接矩阵中值为1的元素用相应边的权取代即可。如图5-25所示。用邻接矩阵表示图，对有向图需要n*n个单元来存储此矩阵。对于无向图，由于它的邻接矩阵是对称的，只需存储其下三角部分即可。带权有向图G3

邻接矩阵

图5-25带权有向图的邻接矩阵5.4.2图的存储表示法用邻接矩阵表示图，对有向图需要n*n个单元来存储此矩阵。对于无向图，由于它的邻接矩阵是对称的，只需存储其下三角部分即可。用邻接矩阵表示图，很容易判定任意两结点之间的相邻关系和各个结点的度数。5.4.3图的遍历和生成树在给定的图G中，从任一结点V0出发，系统地访问图中每一个结点一次，称为图的遍历。图的遍历有按深度和按广度优先两种。1.深度优先遍历先访问结点V0，然后选择一个与V0邻接的未访问过的结点V1，再从V1出发按深度优先遍历。当遇到一个所有邻接与它的结点均被访问完了的结点W时，退回到以访问序列的最后一个拥有未被访问过的序列结点，再从该结点按深度优先遍历。当任何已被访问过的结点的所有邻接结点均未被访问过，此遍历结束。5.4.3图的遍历和生成树按深度优先遍历图5-26的有向图和无向图的结点序列分别为:有向图

①，②，③，⑥，④，⑤，⑦无向图

①，②，④，⑧，⑤，⑥，③，⑦(a)有向图

(b)无向图图5-26图的深度优先遍历示例5.4.3图的遍历和生成树对于连通的无向图和强连通的有向图，从图中任何一个结点出发均可系统地遍历所有结点。对不连通的无向图和不是强连通的有向图，从图中任意一个结点出发一般不能系统地遍历所有的结点。要访问其它结点尚需从未访问过的结点中找一个结点作为起点，再进行遍历。从图G=(V,E)中任一点出发遍历图时，将边集E(G)分成两个集合T(G)和B(G)，其中T(G)是遍历时走过的边集，B(G)是剩余的边集。显然，G=(V,T)是G=(V,E)的子图，称此子图为以V6为起点的深度优先遍历生成树。上述图5-26从结点①出发的深度优先生成树如图5-27所示。5.4.3图的遍历和生成树(a)从有向图结点①出发的深度优先生成树(b)从无向图结点①出发的深度优先生成树图5-27深度优先生成树5.4.3图的遍历和生成树2.广度优先遍历访问图G=(V,E)中结点V0，然后访问与V0相邻接的所有未被访问过的结点V1、V2、…、Vk，然后再依次访问与V1、V2、…、Vk，相邻接的所有未被访问过的结点，如此一直进行下去，之至所有结点均被访问遍历为止。其他情况与深度优先遍历类似。图5-28是图5-26有向图和无向图的广度优先遍历结点序列和广度优先遍历生成树：(a)从结点①出度的遍历序列：①、②、④、⑤、⑥、③、(b)从结点①出度的遍历序列：①、②、③、④、⑤、⑥、⑦、⑧(a)有向图广度优先遍历生成树(b)无向图广度优先遍历生成树5.5内部排序按规定的顺序将一组数据重新排列称为排序(或分类)。排序过程中文件放在内存处理的称为内部排序；如果排序过程中还要使用外存的称为外部排序。这里介绍的是内部排序。如果待排序文件中存在多个相同关键码的记录，经过排序后这些记录原来的相对次序仍保持不变的，称这种排序算法是稳定的，否则称为不稳定的。排序有广泛的应用，下面介绍几种常用的排序方法。5.5.1简单插入排序简单插入排序是插入排序的一种。它是将待排序的数据逐一取出，与已排序数据进行比较，并插在适当的位置。第i次插入时，a[1]、a［2］、…、a[i—1]已排序好。取出a[i]，在1到i的范围为其找一个合适的位置

j，将从

a[j]到a[i-1]的数据依次后移一个位置，在空出来的位置j上插入原来的a[j]。例如，现有待排序记录8个，它们的关键分别为7、5、4、9、1、6、3、2。从i=2开始经过七步插入即可完成排序。图5-29表示直接插入的处理过程。5.5.2简单选择排序简单选择排序是选择排序的一种。该排序十分简单。首先从所有待排序记录选出关键码最小的记录，将其与第1个记录交换，然后在其余未排序的记录中选出关键码最小的记录，将其与第2个记录交换位置。如此反复进行，直到全部记录排完序为止。图5-30给出这种排序方法的示例。5.5.3冒泡排序冒泡排序是交换排序的一种。该排序方法是:从底部开始,反复地从下向上比较相邻的数据,如果a[i]<a[i-1],则交换,既小的数据向上浮。第一遍比较后，最小的数据浮到最上面。第二遍继续从下向上逐个比较，将次最小的浮到a[2]的位置。如此反复进行直到所有数据均排好序为止。图5-31给出了冒泡排序示例。5.6检索检索又称查找，是从一大堆数据中按某种方式找出所需内容的过程。检索是数据处理中常用的一种重要运算。检索的结果有两种可能：检索失败，就是在数据结构中不存在满足条件的结点；检索成功，就是在数据结构中找到了满足条件的结点。在日常生活中，查找信息是人们一项非常频繁且重要的活动。例如，在通讯录中查找某个人的电话号码和地址，或在字典中查找某个词的读音和词义。在信息时代，我们将大量的信息存储在计算机系统中，如何快速、准确的查找到我们需要的数据也是非常重要的。在计算机检索过程中，我们使用的数据结构称为查找表。所谓查找表，就是同一类型的数据(或记录)组成的集合。下面介绍几种常用的检索方法。5.6.1顺序检索这是一种最简单的检索方法。检索时用待查的关键码与给定数据结构中各结点的关键码依次比较，直到找出相应的结点则检索成功，或找遍所有结点都没有相应的结点则检索失败。顺序检索时存储表示可以是顺序的，也可以是链式的，对查找表中结点之间没有排序的要求。例如，已知一组由10个数据元素组成的查找表为： (13，41，23，15，19，33，28，06，55，37)现在要用顺序检索法查找关键字为33和66的数据元素。根据顺序检索方法，第一步取出查找表中的第一个元素13与关键字33做比较，得到的结果为不相等，第二步，顺序地取第二个元素41与关键字33比较，……，以此类推，直到取到第六个元素33，它与关键字相同，然后输出结果为：6，即目标关键字在查找表的位置为6。5.6.1顺序检索关键字33的顺序查找过程如图5-32所示。5.6.1顺序检索顺序检索关键字66的过程和检索33的方法完全一致。但是我们会发现顺序比较之后，查找表中不能找到与关键字66相同的数据，此时遍历的指针应该是指向查找表中最后一个数据之后的位置。这个值并不是一个特殊值，它会根据查找表中元素个数的不同而不同，而且如果要区分出这个返回值是指关键字所在的位置，或是指关键字不存在，还需要与查找表中数据元素的个数做比较。因此，改进的算法在顺序检索遍历开始时，会设置一个“哨兵”位置，即位于第一个元素之前的0号位置，如果遍历完查找表之后不能找到与关键字匹配的元素，则返回值为0，这样对于数据个数不同的查找表，如果返回值为0就意味着检索失败。5.6.1顺序检索关键字66的顺序查找过程如图5-33所示。5.6.2二分法检索采用二分法检索(折半查找)，要求查找表中的结点按关键码值的大小排序，并且要求采用顺序存储表示。二分检索时，先用待检索的关键码值与数据结构中间位置的结点的关键码比较，若相等则检索成功，返回结点的位置序号；若不相等，则根据比较结果确定下一步检索是在左子表中进行，还是在右子表中进行。直到检索成功或检索失败为止。5.6.2二分法检索例如，已知一组由10个数据元素组成的查找表为： (13，41，23，15，19，33，28，06，55，37)用二分法检索关键字为33和66的数据元素。首先，要将查找表进行排序，如由小到大排序为(06，13，15，19，23，28，33，37，41，55)。然后，确定查找表的中间位置，一般的方法为

其中low为待查范围的下界，high为上界，mid为中间位置。本例中，low和high的初值分别为1和10，。之后，比较第五个元素23与33的大小关系，因为23<33则选择查找表的右半部分作为下一步的待查范围，即

，同理如果mid对应的元素比33大，则选择查找表的左半部分作为下一步的待查范围，而

。以此类推直到找到匹配元素或查找区间的大小小于0(查找不成功)。5.6.2二分法检索图5-33关键字33二分法检索过程5.6.2二分法检索图5-34关键字66二分法检索过程5.6.2二分法检索通过对顺序查找和二分法检索过程的分析，我们可以直观的看到，顺序查找具有一定的盲目性，如果关键字恰好是第一个元素，那么查找活动只需要一步就可以完成，而如果关键字不存在则需要遍历整个查找表。而二分法在查找过程中，每次都可以使查找范围去除一半的元素，直观上查找效率是要高于顺序查找的。但二分法查找只适用于查找表有序的情况，所以当查找表元素过多时排序可能就需要消耗大量的时间。当然在具体分析各种查找方法的性能时，需要考虑该查找算法在查找成功时的平均查找长度，所谓平均查找长度是指在确定记录在查找表中的位置，需要和关键字进行比较的次数的期望值。在后续的数据结构的课程中会详细分析各种检索方法的性能，在这里就不再做深入讨论。5.6.3分块检索分块检索又称索引顺序查找，是顺序查找的一种改进方法，也可以理解为二分法的一种扩展。分块检索要求把查找表分成若干块，在每一块中结点的存放是任意的，但块与块之间必须是有序的。如果按递增次序排列，则第一块中所有结点的关键码值均小于第二块中所有结点的关键码值，第二块中所有结点的关键码值均小于第三块所有结点的关键码值，依此类推。根据各个块之间的关键字大小和起始位置建立“索引表”。在查找过程中，首先根据索引表确定关键字所在的块，然后在选定的块中根据顺序查找的原则进行查找。5.6.2二分法检索例如，已知一组由10个数据元素组成的查找表为： (13，41，23，15，19，33，28，06，55，37)用分块检索法查找关键字为33和66的数据元素。首先对现有的数据元素按照从小到大的顺序进行分块(三块)，并建立索引表。如图5-35所示。当数据元素根据大小不同而需要进行位置调整时，可以参考本章第五节中所提供的排序算法进行操作。5.6.3分块检索然后，比较待查关键字与各个索引块中最大关键字的大小顺序，以确定待查关键字可能的位置，本例中因为28<33<55，所以可以判定33处于第三块中。之后，在第三块中按照顺序查找的方法进行查找，这里就不再详述。而对于关键字66>55(查找表中最后一块的最大关键字)，所以可以直接判定它不在查找表中，即查找失败。虽然分块查找需要对查找表进行建立索引表的预处理，但当索引表建好之后，每次查找时，分块查找明显地提高了顺序查找的效率，也不像二分法查找要求全部元素都有序，算法比较简单，应用也很广泛。5.6.4散列表检索散列表既是一种存储表示，也是一种检索方法。散列法又称关键码—地址转换法(也称哈希法)。散列表的基本思路是：以关键码的值为自变量，通过某种函数关系运算后直接确定结点相应的存储地址，将该结点存入计算得到的存储单元里。检索时根据待检索的关键码值，通过上述同样的函数关系运算后得到地址，再到相应存储单元里去取结点。其中，使用的函数称为散列函数(哈希函数)，用散列法存储的线性表称为散列表。在理想的情况下，查找表中的数据通过哈希函数对应到一个存储地址，在查找时待查关键字通过哈希函数运算后直接取对应地址的元素即可，否则，如果对应位置元素为空则表明查找失败。5.6.4散列表检索在进行散列表检索时有两个难点要处理，一是构造哈希函数的方法，二是处理冲突的方法。构造哈希函数的目的是要将查找表中的关键字尽可能均匀地散列到存储空间中。所谓均匀，是指每一个关键字经过哈希函数处理后映射到存储空间的任一地址的概率是相等的。也就是说要，通过哈希函数给每个关键字赋予一个“随机地址”，而且是他们均匀的分配到整个地址区域中，以节省空间并减少冲突。所谓冲突，是指不同的关键字通过哈希函数处理得到相同的地址的现象。5.6.4散列表检索在一般情况下，我们很难同时兼顾节省查找时间和存储空间的需求，并完全避免冲突。由于查找表的数据信息可能非常庞大，如果我们选择太过复杂的哈希函数，那么在构造散列表是耗费大量是时间，而且如果要完全避免冲突，我们可能需要浪费大量的存储空间。比如，查找表中的数据是4000个0~9999的整数数据，且没有重复。最简单的哈希函数，就是开辟10000个存储单元，将关键字存在它自己对应的序数单元中，但这样就会浪费掉6000个单元的存储空间。因此如何权衡这种关系，还需要针对具体情况进行分析和设计。常用的哈希函数构造方法有：直接定址法、数字分析法、平方取中法、折叠法、除留余数法和随机数法等。常用的处理冲突方法有：开放定址法、再哈希法、链地址法和建立一个公共溢出区等。在后续的数据结构课程中，我们会详细的讨论这些常用的哈希函数构造方法和解决冲突的方法，并分析他们的特点，在此就不再详述。5.6.4散列表检索下面我们再以这组由10个数据元素组成的查找表为例： (13，41