学习指南(数据结构基础).doc

数据结构基础学习指南数据结构是计算机、信息管理与信息系统等信息系统相关专业的一门重要的核心基础课程，主要任务是讨论现实世界中数据的各种逻辑结构、在计算机中的存储结构以及一些非数值运算的种类、方法和算法设计。通过学习，学生不仅要掌握数据的组织、存储和处理的常用方法，更重要的是能针对问题的应用背景分析、选择最佳的数据结构与算法，从而提高问题求解和软件的研发能力。作为核心基础课，数据结构与算法课程的内容比较成熟、稳定，是一门理论性与实践性都很强的课程。学习的主要内容包括：数据结构的基本概念；算法的评价方法；数据的逻辑结构，包括线性表、堆栈、队列、树、图等常用数据结构；数据的存储结构，包括顺序存储和链式存储；以及各类操作的实现，包括插入、删除、查找、排序、输入输出、遍历等；在此基础上进行简单的应用，能用C语言写出存储结构及相应的算法，并上机通过。一. 数据结构课程的难点数据结构课程普遍反映难学。既有理论又有实践，尤其在刚开始学习时，由于与前驱程序设计课程的跨度比较大，学生往往是听听容易做做难，一时难以理解。1 上机实现难数据结构学习很重要的一方面就是上机实现，相比前期程序设计课程，无论是解决的问题、算法设计、程序调试还是代码量上，都有一个很大的提升。虽然有时候理解内容了，但是实现上面还是很困难。2 原理知识难数据结构是一门理论和实践都很强的课程，除了要清楚各种数据结构的特征外，还需要理解各种与结构有关的性质，如二叉树就具有多个相关性质。更重要的是理解算法的核心思想，切记不要把算法等同于程序，这是学习这门课的一个很简单的大忌，在理解思想的基础上再开始看算法。3 与实际结合难很多同学在学习数据结构时提出缺少与实际应用的结合。数据结构讲述的是现实生活中计算机所要处理的数据的逻辑关系、存储结构以及在此上的各种操作的实现。本身是一个基础课程，与实际问题的结合前提是先理解各种结构的特征、组织方式以及常有的操作算法。在此基础上，考虑与现实问题的结合。二、数据结构课程的学习方法与一般的课程类似，基本上就是课前看看书、课时仔细听课、课后认真复习、独立做习题、多上机实现。仔细看书与独立上机编程是学好数据结构课程的两大前提。1 课堂中课堂中讲解的一般都是些重点与难点，这些内容靠自己课后看会比较难理解，或者未能切中要点，故课堂中仔细听时前提，且数据结构是一门逻辑型很强的课程，稍不留神可能会难以跟上教师的思路。2 课堂后数据结构要反复看书，特别是算法思想以及设计技巧，量变引起质变，当看多了的时候，突然会茅塞顿开。很多同学上课听懂了但课后又不会做的主要原因就是课后未能有效看书。以理解为前提，切忌死记硬背。3 习题习题是检验课程内容掌握程度的最有效的方法，对每一个知识点必须做一定数量的习题，用以了解结题的思路、方法以及各种的变化，并加以独立的思考，多在纸上画画写写，可以相互讨论，但切忌为完成任务而抄袭。4 实验编程是一门熟练科学，多编程，水平肯定会提高，最重要的是能够养成一种感觉，就是对程序、对算法的敏感。不少同学在上机编程时照搬教材的原代码，不考虑为什么，不管方法的好坏，使得实验课变成打字课；其次，当碰到程序错误时，不知如何调试修改。比较好的方法是：事先看懂教材的算法或原代码，包括其设计的思想、设计的方法，然后独立编写相应的实验题，一旦碰到问题，可再参考教材的方法。第三，程序的错误必定会存在，但需要掌握自己的调试改错方法，清楚错误的原因、错误的地方、解决的方法等，在独立调试改错的过程中不断提高程序设计的能力与水平。数据结构基础各章知识点概述第一章 绪论 1.1 基本术语数据是计算机操作对象的总称，它是计算机处理的符号的集合，集合中的个体为一个数据元素。数据元素可以是不可分割的原子，也可以由若干数据项合成，因此在数据结构中讨论的基本单位是数据元素，而最小单位是数据项。数据结构是由若干特性相同的数据元素构成的集合，且在集合上存在一种或多种关系。由关系不同可将数据结构分为四类（称为数据的逻辑结构）：集合、线性结构、树形（层次）结构、图形（网状）结构。如图1.1所示。 a) 线性结构 b) 集合结构 c) 树形结构 d) 图形结构图1.1 四种常见的数据结构数据的存储结构是数据逻辑结构在计算机中的映像，由关系的两种映像方法可得到两类存储结构：一类是顺序存储结构，它以数据元素相对的存储位置表示关系，则存储结构中只包含数据元素本身的信息；另一类是链式存储结构，它不仅仅包含数据元素本身的信息，并附加的指针信息（后继元素的存储地址）表示关系。数据结构的操作是和数据结构本身密不可分的，两者作为一个整体可用抽象数据类型进行描述。抽象数据类型是一个数学模型以及定义在该模型上的一组操作，因此它和高级程序设计语言中的数据类型具有相同含义，而抽象数据类型的范畴更广，它不局限于现有程序设计语言中已经实现的数据类型，但抽象数据类型需要借用固有数据类型表示并实现。抽象数据类型的三大要素为数据对象、数据关系和基本操作，同时数据抽象和数据封装是抽象数据类型的两个重要特性。 1.2 算法和算法的量度算法是进行程序设计的不可缺少的要素。算法是对问题求解的一种描述，是为解决一个或一类问题给出的一种确定规则的描述。一个完整的算法应该具有下列五个要素：有穷性、确定性、可行性、有输入和有输出。一个正确的算法应对苛刻且带有刁难性的输入数据也能得出正确的结果，并且对不正确的输入也能做出正确的反映。算法设计的原则主要包含以下几个方面：正确性、可读性、健壮性以及高效率与低存储量需求。算法的时间复杂度是比较不同算法效率的一种准则，算法时间复杂度的估算基于算法中基本操作的重复执行次数，或处于最深层循环内的语句的频度。常见的时间复杂度，按数量级递增排列依次为：常数阶、对数阶、线性阶、线性对数阶、平方阶、立方阶、指数阶、阶层阶()、指数阶()。算法空间复杂度可作为算法所需存储量的一种量度，它主要取决于算法的输入量和辅助变量所占空间，若算法的输入仅取决于问题本身而和算法无关，则算法空间复杂度的估算只需考察算法中所用辅助变量所占空间，若算法的空间复杂度为常量级，则称该算法为原地工作的算法。1.3 实践1） 自定义类型为了使程序便于理解，应该把一些数据类型名与要说明的对象性质建立某些语义上的对应关系，可以用typedef向用户提供了一种自定义类型说明符，一般形式为：typedef 类型 定义名；使用typedef定义数据类型新名字既照顾了用户编程使用词汇的习惯，又增加了程序的可读性，便于程序的移植。用typedef定义类型，只定义了一个数据类型的新名字而不是定义一种新的数据类型。2） 输入输出语句使用包含文件语句 #include后，可使用以下关键字进行输入/输出： cin 代表标准输入设备（键盘）流对象，后面跟“”运算符，“”是C+的输入运算符； cout 代表标准输出设备（屏幕）流对象，后跟“”运算符，“”是C+的输出运算符； cerr 代表标准错误输出设备（屏幕）流对象，后跟“”运算符。3） 引用参数在C语言中，可以使用指针参数达到修改形参所指向的变量的值，但指针的间接性给人一种不实在感。C+引入引用的主要目的是建立某种类型的虚实体，这种虚实体不占有实际的存储空间。它作为函数参数时，从实参得到相应的地址，与实参共用相同的存储空间，也就是被调用函数中形参的变化会导致所对应实参的变化。使用方法是在形式参数之前插入“&”符号。 4） 动态存储分配C+的 new运算符和delete运算符提供了动态分配内存的功能。new的功能是给程序实体动态地分配存储空间，delete运算符的功能是将用new运算符动态分配的空间回收。new和delete运算符都是单目运算符，new运算符不能对动态分配的存储区进行初始化。第二章 线性结构2.1 线性表的定义和抽象数据类型线性表是最简单、最常用的一类数据结构。简单地说，线性表是 n（n0）个相同类型数据元素a1, a2, , ai , , an 构成的有限序列，通常表示为 (a1, a2, , ai , , an)。线性表中元素的个数n 称为线性表的长度，n=0时称为空表。线性表的第一个元素a1称为表头元素，最后一个元素an称为表尾元素。线性表中的元素是按照前后位置线性有序的，通常把第i个元素ai称为第i+1个元素ai+1的前驱，元素ai+1称为元素ai的后继。线性表是一种线性结构，用二元组表示为：Linear_list = (D, R)其中， D=ai| aiElemType, i=1,2,.,n, n0R=r r=| ai, ai+1ElemType, i=1,2,.,n-1线性表相当灵活，它的长度可根据需要增长或缩短，即对线性表的数据元素不仅可以进行访问，还可以在任意位置进行插入和删除等。线性表的抽象数据类型定义如下：ADT LinearList is Data: n（n0）个相同类型数据元素a1, a2, , an 构成的有限序列，用类型名 ListType 表示。 Operation: void InitList( ListType &L); /初始化L为空 void ClearList( ListType &L); /清除L中所有元素 int LenthList( ListType L); /返回L的长度 bool EmptyList( ListType L); /判断L是否为空，若空返回1，否则返回0 ElemType GetList( ListType L, int pos); /返回L中第pos个元素的值 void TraverseList( ListType L); /遍历输出L中的所有元素 bool FindList( ListType L, ElemType item); /从L中查找元素item，若查找成功返回1，否则返回0 bool InsertList( ListType &L, ElemType item, int pos); /向L插入元素item，并返回是否插入成功。1posn时插在第pos位置；/pos=-1时插在表尾；pos =0时插在有序表的适当位置，使保持有序 bool DeleteList( ListType &L, ElemType &item, int pos);/从L删除元素，被删元素赋给item , 并返回是否删除成功。/1posn时删除第pos位置上的元素；pos=-1时删除表尾元素；/ pos =0时删除指定元素item void SortList( ListType &L); /对L中的元素进行排序end LinearList这里列出的线性表的基本操作是线性表中一些常见的基本操作，读者可以根据需要添加一些别的基本操作。2.2 线性表的顺序存储表示线性表的存储结构主要有两种，即顺序存储和链接存储。线性表的顺序存储结构是指用一组地址连续的存储单元依次存储线性表的各个数据元素。其特点是逻辑上相邻的元素在物理存储上也相邻。假设线性表的每个元素需占用b个存储单元，并以所占的第一个单元的存储地址作为数据元素的存储位置，则线性表中第i个数据元素的存储位置LOC(ai) 为：LOC(ai) = LOC(a1) + (i-1) * b其中：LOC(a1) 是线性表的第一个数据元素a1的存储位置，通常称为线性表的起始位置。线性表的顺序存储结构示意图如图2.1所示，其中MAXSIZE为顺序存储的线性表允许的最大空间量。图2.1 线性表的顺序存储结构示意图通常把顺序存储结构的线性表称为顺序表。顺序表可以使用数组来实现，数组的基本类型就是线性表中元素的类型，数组的大小（又称数组长度）要大于等于线性表的长度。 顺序表的存储结构类型定义可描述为：typedef struct ElemType listMaxSize; /数组名为list int size; /存储当前元素的个数，最后一个元素的数组下标为size-1 SeqList；由于线性表的长度可变，且所需最大存储空间随问题的不同而不同，人们常使用动态分配的一组连续的存储空间存放顺序表中各个元素，类型定义可表示为：typedef struct ElemType *list; /动态存储空间的首地址 int size; /存储当前元素的个数，最后一个元素的数组下标为size-1 int MaxSize; /动态存储空间的大小，即list数组的长度 SeqList；顺序表的优点是：1. 无需为表示数据元素之间的关系增加额外空间，空间单元利用率高。2. 是属于随机存储机制，可以根据元素的位置方便地随机存取表中的任一元素。顺序表的缺点是：1. 插入和删除运算需移动数据元素，时间效率较低。2. 顺序表开辟的存储空间不易扩充。2.3 线性表的链接存储表示线性表的链接存储结构是指用一组任意的存储单元存储线性表的数据元素，这组存储单元可以是连续的，也可以是不连续的。在链接存储中，对每个数据元素来说，除了存储其本身的信息之外，还需要存储一个指示其直接后继的信息 (即直接后继的存储地址)。线性表的链接存储结构的特点是逻辑上相邻的元素在物理位置上不一定相邻。链式存储结构的线性表称为线性链表。线性链表是一种动态存储的数据结构，在创建时利用动态存储分配函数申请存储空间。链表由结点构成，每个结点包含数据域（值域）与指针域。数据域用来存储数据元素信息，指针域用来存储直接后继的存储地址（即指向该结点的下一个结点）。当链表的每个结点中只包含一个指针域时，则链表被称为单向链表（简称为单链表），否则被称为多向链表（简称为多链表）。链表的优点是： （1）插入和删除运算不必移动大量的元素，时间效率高。（2）链表容易扩充与缩小。链表的缺点是：（1）需要为表示数据元素之间的关系增加额外空间，空间单元利用率低。（2）是属于顺序存储机制，在存取元素时不太方便，需从给定的某结点开始逐步向后（或向前）一一遍历，直到遍历到所需结点。1. 单向链表构成链表的结点只有一个指针域时，链表被称为单向链表。单向链表数据元素之间的关系由结点的指针指示。单链表示意图如图2.2所示。其中存储第一个元素的结点即a1结点称为表头结点，存储最后一个元素的结点即an结点称为表尾结点，指向表头结点的指针即L称为表头指针。由表头指针可遍历单链表中的所有结点，故通常用表头指针表示单链表。a1a2anL图2.2 单链表示意图有时，在单链表的表头结点之前附设一个结点，称之为表头附加结点。表头附加结点的数据域可以不存储任何信息，也可以存储如线性表的长度等附加信息；表头附加结点的指针域存储表头结点的地址 (即指向第一个元素结点) 。带表头附加结点的单链表示意图如图2.3所示。 La1anL (a) 非空表 (b) 空表图2.3 带表头附加结点的单链表示意图单向链表中设置表头附加结点的主要作用是：（1）使空表和非空表统一，即链表始终具有一个表头指针。（2）使算法处理结点一致，无需特别关注结点是否为第一个结点。单向链表的结点类型可定义如下：typedef struct Node ElemType data; / 存放数据元素信息 struct Node *next;/ 存放下一个结点的地址 LNode;2. 循环链表当链表中最后一个结点的指针域指向表头结点（或表头附加结点），整个链表形成一个环时称为循环链表。循环链表的优势在于从表中任一结点出发均可找到表中其他结点。带表头附加结点的单向循环链表的示意图如图2.4所示。 La1anL (a) 非空表 (b) 空表图2.4 带表头附加结点的循环单链表示意图3. 双向链表单链表中的每个结点只设有一个指向其直接后继结点的指针域，由此，从某个结点出发只能顺指针方向往后寻找其他结点。若要查寻某结点的直接前驱，则需从表头指针出发一一遍历查找。为了克服单链表的这种单向性缺陷，可以在链表的每个结点中增设一个指向该结点直接前驱的指针域，构成一个双向链表。双向链表示意图如图2.5所示。 Lana1L (a) 非空表 (b) 空表图2.5 带表头附加结点的双向链表示意图有时也可构成一个双向循环链表，其示意图如图2.6所示。Lana1L (a) 非空表 (b) 空表图2.6 带表头附加结点的双向循环链表示意图双向链表的结点类型可定义如下：typedef struct Node ElemType data; /存放数据元素信息 struct Node *left; / 存放直接前驱结点的地址 struct Node *right; / 存放直接后继结点的地址 DNode; 第三章 栈和队列3.1 栈1栈的定义和抽象数据类型栈又称堆栈，是一种操作受限制的线性表，只允许在表的固定一端（表尾）进行插入或删除。对栈进行运算的一端称为栈顶，栈顶的第1个元素称为栈顶元素，相对的，把另一端称为栈底。向一个栈插入新元素称为进栈或入栈，它是把该元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素称为出栈或退栈，栈操作的主要特点是后进先出，如图3.1所示。出栈入栈栈顶a3a2a1栈底图3.1入栈与出栈示意图栈的抽象数据类型的定义如下： ADT STACK is Data： n(n=0) 个相同类型数据元素a1, a2, ， an 构成的有限序列。用类型名 StackType 表示。 Operation:： void InitStack (StackType &S); /构造一个空栈 S int EmptyStack (StackType S); /若栈S为空栈返回1，否则返回0 void Push(StackType &S, ElemType item); /元素 item进栈 ElemType Pop(StackType &S); /栈S的栈顶元素出栈并返回 ElemType Peek(StackType S); /取栈S的当前栈顶元素并返回 void ClearStack (StackType &S); /清除栈s，使成为空栈 End STACK2. 栈的顺序存储表示栈的存储结构主要有两种，即顺序存储和链式存储。通常把顺序存储结构的堆栈称为顺序栈。顺序栈需要使用一个数组和一个整型变量来实现。利用数组来顺序存储栈中的所有元素，利用整型变量来存储栈顶元素的下标位置。顺序栈的存储结构类型定义可描述为：typedef struct ElemType stackMaxSize; int top; /top为栈顶指针，表示栈顶元素的位置 Stack；若要对存储栈的数组空间采用动态分配，类型定义可表示为：typedef struct ElemType *stack; int top; /top为栈顶指针，表示栈顶元素的位置 int MaxSize; Stack；在顺序栈中，top的值为-1表示栈空，每次向栈中压入一个元素时，首先使top增1，用以指向新的栈顶位置，然后再把元素赋值到这个空位置上，每次从栈中弹出一个元素时，首先取出栈顶元素，然后使top减1，指向前一个元素即新的栈顶元素。topbasea1aia1aiai+1topbase图3.2 入栈示意图a1ai-1aitopbasea1ai-1topbase图3.3 出栈示意图3. 栈的链式存储表示栈的链式存储结构是通过由结点构成的单链表实现的，此时表头指针被称为栈顶指针，由栈顶指针指向的表头结点称为栈顶结点，整个单链表称为链栈。当向一个链栈插入元素时，是把该元素插入到栈顶，使该元素结点的指针域指向原来的栈顶结点，而栈顶指针则指向该元素结点，使该结点成为新的栈顶结点。当从一个链栈中删除元素时，是把栈顶元素结点删除掉，即取出栈顶元素后，使栈顶指针指向原栈顶指针的指针域指向的结点。top 图3.4链式栈示意图链栈的结点类型可定义如下： typedef struct node ElemType data; struct node *next; LNode;3.2队列1. 队列的定义和抽象数据类型在实际问题中还经常使用一种“先进先出” (FIFO-First In First Out)的数据结构：即插入在表一端进行，而删除在表的另一端进行，我们将这种数据结构称为队或队列，把允许插入的一端叫队尾(rear) ，把允许删除的一端叫队头(front)。图3.5为队列的示意图。a1a2an队头队尾出队列进队列图3.5队列示意图如图3.6所示是一个有5 个元素的队列。入队的顺序依次为a1、 a2 、a3 、a4 、 a5 ，出队时的顺序将依然是a1、 a2 、a3 、a4 、 a5 。a1 a2 a3 a4 a5 入队出队图3.6入队与出队示意图队列的抽象数据类型的定义如下： ADT QUEUE is Data： n (n=0) 个相同类型数据元素a1, a2, ， an 构成的有限序列。用类型名 QueueType 表示。 Operation: void InitQueue (QueueType &Q); /构造一个空队列 Q int EmptyQueue (QueueType Q); /判断队列Q是否为空 void EnQueue (QueueType &Q, ElemType item); /元素 item 进队列Q，成为队尾元素 ElemType OutQueue (QueueType &Q); /队头元素出队列Q ，并返回其值 ElemType PeekQueue (QueueType Q); /返回队头元素值 void ClearQueue (QueueType &Q); /清空队列 End QUEUE2. 队列的顺序存储表示队列的存储结构主要有两种，即顺序存储和链式存储。顺序存储结构的队列称为顺序队列。队列的顺序存储结构就是利用一组地址连续的存储单元依次存放队列中的数据元素，同时设立front和rear作为队头和队尾指针，分别指向队头元素的前一个位置和队尾元素的位置。队列的顺序存储结构描述： typedef struct ElemType queueMaxSize; int front, rear; Queue;若要对存储队列的数组空间采用动态分配，类型定义可表示为： typedef struct ElemType *queue; int front, rear; int MaxSize; Queue; 在顺序队列中，当rear=front时表示队空，每次向队中进队一个元素时，首先使队尾指针后移1个位置，然后再向该位置写入新的元素。当队尾指针指向数组空间的最后一个位置MaxSize-1时，若队首元素的前面仍存在空闲的位置，则表明队列未占满整个数组空间，下一个存储位置应该是下标为0的空闲位置，因此，首先要使队尾指针指向下标为0 的位置，然后再向该位置写入新元素。通过表达式赋值rear=(rear+1)%MaxSize可使存储队列的整个数组空间变成首尾相接的一个环，所以顺序存储的队列又称为循环队列。每次从队列中删除一个元素时，若队列非空，则首先把队首指针后移，使之指向队首元素，然后再返回该元素的值。使队首指针后移也必须采用取模运算，该计算表达式为front=(front+1)%MaxSize，这样才能够实现存储空间的首尾相接。具体操作如图3.7所示。ABCDCDfront=0rearfront=0rear=4rear=4front=24321043210EFCDrear=1front=243210假设该队列的MaxSize=5队列为空示意图入队4个元素后的示意图出队2个元素后的示意图入队2个元素后队满示意图图 3.7 顺序存储循环队列入队和出队示意图3. 队列的链式存储表示队列的链式存储结构是通过由结点构成的单链表实现的，利用单链表来作为队列的存储结构，第一个结点作为队头，最后一个结点作为队尾。为了操作上的方便，设置 front 指针与 rear 指针分别指向队头与队尾。如图3.8所示。reara1a3fronta2an图3.8链式队列示意图头指针front和尾指针rear是两个独立的指针变量，从结构性上考虑，通常将二者封装在一个结构中。队列的结点类型可定义如下：typedef struct node ElemType data; struct node *next; LNode; typedef struct LNode *front; LNode *rear; LinkQueue;第四章 树4.1 树的定义和基本概念树（tree）是树形结构的简称。它是一种重要的非线性数据结构。树是n (n0) 个结点的有限集。当n0时称为空树，在任意一棵非空树上：1) 有且只有一个特定的称为根 (root) 的结点；2) 当n1时，其余结点可分为m (m0) 个互不相交的有限集T1, T2, , Tm，其中每一个集合本身又是一棵树，并且称为根的子树 (SubTree) ，并且每棵子树的根结点是整个树根结点的后继。显然，树的定义是递归的，树是一种递归的数据结构。用二元组表示为：tree = ( K , R )K = ki | 1in , n0, kiElemTypeR= r 其中，n为树中结点数，n0时则为空树，当 n 0（非空树）时，关系r满足下列条件： 有且仅有一个结点没有前驱，此结点称为树的根。 除根结点以外，其余每个结点有且仅有一个前驱结点。 所有结点可以有任意多个(含0个)后继。在图4.1中，A结点是树的根结点，其余结点分成3个独立的子集：T1=B, E, F, K, L，T2=C, G，T3=D, H, I, J, M，T1、T2、T3都是根A的子树，且本质也是子树。B、C、D结点分别是T1、T2、T3的根结点。T1、T2、T3又可分为更小的子树，D结点的子树是 H, M ，I 和 J，其中 I 和 J 是只有一个根结点的子树。(a) 只有根结点的树 (b) 一般的树图4.1 树的示例树中的结点包含一个数据元素及若干指向其子树的分支。结点拥有的子树数目或者说后继结点数称为结点的度（degree）。树中所有结点的度的最大值称为该树的度。度为0的结点称为叶子或终端结点，度不为0的结点称为非终端结点或分支结点。结点的子树的根称为该结点的孩子，相应地，该结点称为孩子结点的双亲，同一个双亲的孩子之间互称兄弟。结点的祖先是从根到该结点所经过的分支上所有结点。反之，以某结点为根的子树中任一结点都称为该结点的子孙。例如，在图4.1（b）中，F、G、I、J、K、L和M都是叶子结点；树的度为3；D是H、I、J的双亲，H、I、J是D的孩子且互为兄弟；E的祖先是A、B，而K、L既是E的孩子也是E的子孙。树型结构也是一种层次结构，树中的每个结点都处在一定的层数上。结点的层次从根开始定义，根为第一层，根的孩子为第二层，以此类推。树中结点的最大层次称为树的深度。如图4.1（b）的深度为4。如果将树中结点的各个子树看成从左到右是有次序的，则称此树为有序树，否则称为无序树。4.2 二叉树的定义和基本概念二叉树（binary tree）是一种特殊的树，是树的度最大为2的有序树。它是一种最简单、而且最重要的树，在计算机领域有着广泛的应用。二叉树的递归定义为：二叉树或者是一棵空树，或者是一棵由一个根结点和两棵互不相交的分别称做根的左子树和右子树所组成的非空树，左子树和右子树又同样都是一棵二叉树。 二叉树的特点是每个结点至多只有二棵子树 (即二叉树中不存在度大于2的结点) ，并且，二叉树的子树有左右之分，结点左子树的根称为结点的左孩子（left child），结点右子树的根称为结点的右孩子（right child）。其次序不能任意颠倒。图4.2所示的是二叉树的基本形态。(a) (b) (c) (d) (e) (f)(a) 空二叉树 (b) 仅有根结点的二叉树 (c) 右子树为空的二叉树(d) 左子树为空的二叉树(e) 左右子树均非空的二叉树(f) 一般的二叉树图4.2 二叉树的五种基本形态示例二叉树有下列重要特性：性质1：二叉树上终端结点数等于双分支结点数加1。性质2：二叉树的第i层上至多有2i-1个结点 (i1) 。性质3：深度为k的二叉树至多有2k-1个结点 (k1) 。一棵深度为k且有2k-1个结点的二叉树称为满二叉树，即满二叉树上每一层的结点数都是满的。若对满二叉树自顶向下，同层自左向右连续编号，则深度为k有n个结点的二叉树，当且仅当其每个结点都与深度为k的满二叉树中的编号从1 n的结点一一对应，则称之为完全二叉树。也就是说，完全二叉树除最后一层外，其余各层都是满的，并且最后一层或者是满的，或者是在右边缺少连续若干个结点。图4.3所示的特殊形态的二叉树。(a) 满二叉树 (b) 安全二叉树(c) 非完全二叉树图4.3 特殊形态的二叉树性质4：对一棵有n个结点的完全二叉树的结点按层序（从上往下，从左往右）从1开始顺序编号，则对任意结点编号 i 有：若编号为i的结点有左孩子，则左孩子结点的编号为2i；若编号为i的结点有右孩子，则右孩子结点的编号为2i+1。若编号i=1，则此为根结点；否则编号为i的结点其双亲结点的编号为i/2。即当i为偶数时，其双亲结点编号为i/2，它是双亲结点的左孩子；当i为奇数时，其双亲结点编号为 (i-1)/2，它是双亲结点的右孩子。若编号in/2，即2in，则编号为 i的结点为分支结点，否则为叶子结点。若n为奇数，则每个分支结点都既有左孩子又有右孩子；若n为偶数，编号最大的分支结点（编号为n/2）只有左孩子，没有右孩子，其余分支结点左右孩子都有。性质5：具有n（n0）个结点的完全二叉树的深度为log2n+1。二叉树的抽象数据类型定义如下：ADT BinaryTree is Data: 某一存储结构方式的二叉树，设用BTreeType表示， BTreeType BT Operations void InitBtree(BTreeType &BT); /初始化二叉树，即把它置为一棵空树 void CreateBtree(BTreeType &BT , char *s ); /根据字符串s表示的二叉树建立对应的存储结构 bool EmptyBtree(BTreeType BT); /判断二叉树是否为空，若是则返回true，否则返回false void TraverseBtree(BTreeType BT); /按照一定次序遍历二叉树，使得每个结点的值均被访问一次 bool FindBtree(BTreeType BT ,ElemType &item); /从二叉树中查找值为item的结点，若存在则由item带回它的完整值 /并返回true，否则返回false表示查找失败 int BtreeDepth(BTreeType BT); /求二叉树的深度 void PrintBtree(BTreeType BT); /输出二叉树 void ClearBtree(BTreeType &BT); /清楚二叉树中所有结点，使之变为一棵空树End BinaryTree 4.3 二叉树的存储结构同线性表一样，二叉树也有顺序和链接两种存储结构。1顺序存储结构按照4.1.2节中二叉树的性质4，当对二叉树的各个结点按顺序编号时，利用各个结点的编号与一维数组的下标一一对应的关系，把结点的值存放到相应的数组下标中，由于编号规则是从1开始，故对于一维数组放弃使用0号单元。如此编号为i的结点其左右孩子的编号为2i和2i+1。假定用一维数组bt1和bt2来顺序存储图5.3（b）和图5.3（c）中的二叉树，则数组中个元素的值如图4.4所示，个单元存储二叉树结点的值。012345678bt1123456012345678bt2123456图4.4 二叉树的顺序存储结构二叉树顺序存储结构定义如下：#define MAX_TREE_SIZE 100 /二叉树的最大结点数typedef ElemType SqBiTreeMAX_TREE_SIZE;SqBiTree bt;顺序存储二叉树的优劣：1）对于完全二叉树用顺序存储既节约空间，存取也方便；2）对于一般二叉树用顺序存储，空间较浪费，最坏情况为单分支二叉树。2链接存储结构根据二叉树的特性，因为二叉树结点度不大于2，故二叉树的结点可由一个数据元素值域和两个分别指向左右树根结点的指针域构成。即二叉树的链接存储结构中至少包含3个域：数据域和左、右指针域，称为二叉链表，如图4.5（a）所示。有时为了便于找到结点的双亲，则还可在结点结构中增加一个指向其双亲的指针域，称为三叉链表，如图4.5（b）所示。 (a) 二叉链表结点 (b) 三叉链表结点图4.5二叉树结点及其存储结构 二叉树的二叉链表存储结构定义如下： struct BTreeNode ElemType data; / 结点值域 BTreeNode *lchild , *rchild ;/ 定义左右孩子指针 ;对于图4.3（c）的二叉树，其二叉链表存储结构如图4.6所示，其中f为指向树根结点的指针，称为根指针。图4.6二叉树的二叉链表存储结构4.4 二叉树的遍历二叉树的遍历是二叉树中最重要的运算。二叉树的遍历是指按照一定次序访问二叉树中所有结点，并且每个结点的值仅被访问一次的过程。根据二叉树的递归定义，二叉树由根结点、左子树和右子树所组成，因此，遍历一棵非空二叉树的问题可分解为3个子问题：访问根节点、遍历左子树和遍历右子树。假如用D、L和R分别表示上述三个部分，则可产生DLR、LDR、LRD、DRL、RDL、RLD这6中次序的遍历方案。若限定先左后右的次序访问，则只有前三种情况。按照何时访问根结点的次序，称DLR为先序（先根）遍历，LDR为中序（中根）遍历，LRD为后序（后根）遍历。显然根据二叉树的递归定义，遍历左右子树的问题仍然是遍历二叉树的问题，由此可得出遍历算法为递归算法。先序遍历二叉树的的操作定义为：若二叉树为空，则结束（返回，为递归出口）；否则： 访问根结点； 先序遍历左子树； 先序遍历右子树。由此可给出先序遍历的算法：void PreOrder(BTreeNode *BT) if (BT!=NULL) coutdataleft) ; /递归调用，先序遍历左子树 PreOrder(BT-right) ; /递归调用，先序遍历右子树 很容易根据上述算法写出相应的中序遍历和后序遍历的算法。若对图5.6的二叉树进行先序遍历，则得到的序列为1 2 4 5 3 6。另一方面，二叉树的递归定义也说明了二叉树的其他运算大多也可用递归的方法加以解决，当然也可用非递归的方法，但相应地增加了算法的复杂性，并且可能将会用到栈或队列。第五章 图5.1 图的定义图型结构（简称图，graph）是由顶点(vertex)集合及顶点间的关系（edge）集合组成的一种数据结构，其二元组定义为：Graph(V, E ) 其中，V = vi | 0=i=0, vi VertexType 是顶点的有穷集合，数据元素（即顶点）具有相同数据类型VertexType；由于空的图在实际应用中没有意义，因此一般不讨论空的图，即V是顶点的有穷非空集合。E = (x, y) | x, y V 或E = | x, y V 是顶点之间二元关系的有穷集合，也叫做边集合。图是比线性表和树更为复杂的非线性数据结构，线性表和树可看成是图的简单情况。数据结构中所了解的图，和离散数学中的图论有关联，但图论侧重研究图的纯数学性质，而数据结构中图的研究则重在计算机中如何表示图以及如何实现图的操作和应用等。5.2图的基本术语几个有关图的基本术语：l 顶点（结点，vertex）：图中的数据元素；l 边：两个顶点之间的关系；图的二元组定义可简述为：图由顶点集（vertexset）和边集（edgeset）组成。l 有向图：若图G中的每条边都是有方向的，则称G为有向图。有向边也称为弧(包括弧头和弧尾)。l 无向图：若图G中的每条边都是没有方向的，则称G为无向图。图5.1 无向图G1（左）和有向图G2（右）在图5.1中所示的无向图G1和有向图G2中，顶点集和边集分别为：V（G1）=A，B，C，D，E，FE（G1）=(A,B),(A,E),(B,E),(C,D),(D,F),(B,F),(C,F) V（G2）=A