数据结构核心知识（精简版）ysfullStack

简单地说，数据结构是计算机组织数据和存储数据的方式；即数据结构是指一组相互之间存在一种或多种特定关系的数据的组织方式和它们在计算机内的存储方式，以及定义在该组数据上的一组操作。

引申：

1、计算机解决一个具体问题时，一般需要经过以下几个步骤：

在每个步骤中，数据的表现形式都不相同，实际问题中的数据称为原始数据。在数学模型中，需要把原始数据按照某种方式组织起来，以便很好地体现数据之间的关系，数据及数据的组织方式称为数据的逻辑结构。为了能用计算机加工处理，逻辑结构还必须转换为能被计算机存储的存储结构。

2、瑞士计算机科学家NiklausWirth曾提出一个著名公式：算法+数据结构=程序；简洁地描述了算法、数据结构和程序之间关系。数据结构是相互之间存在一种或多种特定关系的数据元素的集合。它包括数据的逻辑结构、数据的存储结构和数据的基本运算。

二、数据的逻辑结构

1、数据的逻辑结构是指数据元素之间的逻辑关系。所谓逻辑关系是指数据元素之间的关联方式或“邻接关系”。

2、数据元素之间的关系，有四类基本的逻辑结构：

（1）集合中任意两个结点之间都没有邻接关系，组织形式松散。

（2）线性结构中结点按逻辑关系依次排列形成一条“链”，结点之间一个一个依次相邻接。

（3）树形结构具有分支、层次特性，其形态像自然界中的树，上层的结点可以和下层多个结点相邻接，但下层结点只能和上层的一个结点相邻接。

（4）图结构最复杂，其中任何两个结点都可以相邻接。

三、数据的存储结构

1、数据的逻辑结构在计算机中的实现称为数据的存储结构（或物理结构）。一般情况下，一个存储结构包括以下两个部分：

（1）存储数据元素；（2）数据元素之间的关联方式。

2、数据元素的存储（映像方法）

用二进制位（bit）的位串表示数据元素。通常称这种位串为节点（node）。当数据元素由若干个数据项组成时，位串中与各个数据项对应的子位串称为数据域（datafield）。因此，节点是数据元素的机内表示（或机内映像）。

3、表示数据元素之间的关联方式主要有顺序存储方式和链式存储方式。

（1）顺序存储方式是指所有存储结点存放在一个连续的存储区里。利用结点在存储器中的相对位置来表示数据元素之间的逻辑关系。

（2）链式存储方式是指每个存储结点除了含有一个数据元素外，还包含指针，每个指针指向一个与本结点有逻辑关系的结点，用指针表示数据元素之间的逻辑关系。除了上述两种存储方式之外，还有索引存储方式和散列存储方式。

4、一种逻辑结构可以采用一种或几种存储方式来表达数据元素之间的逻辑关系，相应的存储结构称为给定逻辑结构的存储实现或存储映像。

四、运算

运算是指在某种逻辑结构上施加的操作，即对逻辑结构的加工。一般来说，在每个逻辑结构上，都定义了一组基本运算，这些运算包括：建立、查找、读取、插入和删除等。

注：线性表、栈和队列中的元素具有相同的逻辑结构（即线性结构），但有不同的运算集，它们是不同的数据结构。

五、线性表

线性表是一种线性结构，它是由n(n≥0)个数据元素组成的有穷序列，数据元素又称结点。线性表中结点具有一对一的关系，如果结点数不为零，则除起始结点没有直接前驱外，其他每个结点有且仅有一个直接前驱；除终端结点没有直接后继外，其他每个结点有且仅有一个直接后继。

1、线性表的顺序存储

将表中的结点依次存放在计算机内存中一组连续的存储单元中，数据元素在线性表中的邻接关系决定它们在存储空间中的存储位置，即逻辑结构中相邻的结点其存储位置也相邻。用顺序存储实现的线性表称为顺序表，一般使用数组来表示顺序表。

2、线性表的基本运算

1）、插入

算法描述如下：

voidInsertSeqlist(SeqListL,DataTypex,inti){//将元素x插入到顺序表L的第i个数据元素之前if(L.length==Maxsize)exit(“表已满”);if(i<1||i>L.length+1)exit(“位置错”)；//检查插入位置是否合法for(j=L.length;j>=i;j--)//初始i=L.lengthL.data[j]=L.data[j-1];//依次后移L.data[i-1]=x;//元素x置入到下标为i-1的位置L.length++;//表长度加1}2）、删除

voidDeleteSeqList(SeqListL,inti){//删除线性表L中的第i个数据结点if(i<1||i>L.length)//检查位置是否合法exit(“非法位置”);for(j=i;j

定位运算LocateSeqlist(SeqListL,DataTypex)的功能是查找出线性表L中值等于x的结点序号的最小值，当找不到值为x的结点时，返回0。

描述算法如下：

intLocateSeqlist(SeqListL,DataTypex){inti=0;while((i

3、顺序表实现算法的分析

在分析线性表的顺序表实现算法时，一个重要指标就是数据元素的比较和移动的次数。

4、线性表的链接存储

线性表的链接存储是指它的存储结构是链式的。线性表常见的链式存储结构有单链表、循环链表和双向循环链表，其中最简单的是单链表。

1）、单链表的结点结构

（1）data部分称为数据域，用于存储线性表的一个数据元素。

（2）next部分称为指针域或链域，用于存放一个指针，该指针指向本结点所含数据元素的直接后继结点。

2)、单链表

所有结点通过指针链接形成链表。

（1）head称为头指针变量，该变量的值是指向单链表的第一个结点的指针。可以用头指针变量来命名单链表。

（2）链表中第一个数据元素结点称为链表的首结点。

（3）链表中最后一个数据元素结点称为尾结点或终端结点。尾结点指针域的值NULL称为空指针，它不指向任何结点，表示链表结束。如果head等于NULL，则表示该链表无任何结点，是空单链表。

3)、单链表的类型定义如下：

typedefstructnode{DataTypedata;//数据域structnode*next;//指针域}Node,*LinkList;4)、带头结点的单链表

在单链表的第一个结点之前增设一个类型相同的结点，称之为头结点，其他结点称为表结点。表结点的第一个和最后一个结点分别就是首结点和尾结点。

七、线性表的基本运算在单链表上的实现

1、初始化

空表由一个头指针和一个头结点组成。

LinkListInitiateLinkList()//建立一个空的单链表{LinkListhead;//头指针head=malloc(sizeof(Node));//动态构建一结点，它是头结点head->next=NULL;returnhead;}在算法中，变量head是链表的头指针，它指向新创建的结点，即头结点。一个空单链表仅有一个头结点，它的指针域为NULL。

2、求表长

在单链表存储结构中，线性表的表长等于单链表中数据元素的结点个数，即除了头结点以外的结点的个数。设置一个工作指针p，初始时，p指向头结点，并设置一个计数器cnt，初值设置为0。然后，让工作指针p通过指针域逐个结点向尾结点移动，工作指针每向尾部移动一个结点，让计数器加1。直到工作指针p->next为NULL时，说明已经走到了表的尾部，这时已完成对所有结点的访问，计数器cut的值即是表的长度。

3、读表元素

通常给定一个序号i，查找线性表的第i个元素。在链表中，任何相邻的两个结点通过一个指针相连，一个结点的位置包含在直接前驱结点的next域中。所以，必须从头指针出发，一直往后移动，直到第i个结点。

4、定位

线性表的定位运算，就是对给定表元素的值，找出这个元素的位置。在单链表的实现中，则是给定一个结点的值，找出这个结点是单链表的第几个结点。定位运算又称作按值查找。在定位运算中，也需要从头至尾访问链表，直至找到需要的结点，返回其序号。若未找到，返回0。

定位运算算法描述如下：

intLocateLinklist(LinkListhead,DataTypex)//求表head中第一个值等于x的结点的序号，若不存在这种结点，返回结果为0{Node*p=head;//p是工作指针p=p->next;//初始时p指向首结点inti=0;//i代表结点的序号，这里置初值为while(p!=NULL&&p->data!=x)//访问链表{i++;p=p->next;}if(p!=NULL)returni+1;elsereturn0;}5、插入

单链表的插入运算是将给定值为x的元素插入到链表head的第i个结点之前。

插入运算描述如下：

voidInsertLinklist(LinkListhead,DataTypex,inti)//在表head的第i个数据元素结点之前插入一个以x为值的新结点{Node*p,*q;if(i==1)q=head;elseq=GetLinklist(head,i-1);//找第i-1个数据元素结点if(q==NULL)//第i-1个结点不存在exit(“找不到插入的位置”);else{p=malloc(sizeof(Node));p->data=x;//生成新结点p->next=q->next;//新结点链域指向*q的后继结点q->next=p;//修改*q的链域}}注意：链接操作p->next=q->next和q->next=p两条语句的执行顺序不能颠倒，否则结点*q的链域值（即指向原表第i个结点的指针）将丢失。

6、删除

单链表的删除运算算法描述如下：

voidDeleteLinklist(LinkListhead,inti)//删除表head的第i个结点{Node*q;if(i==1)q=head;elseq=GetLinklist(head,i-1);//先找待删结点的直接前驱if(q!==NULL&&q->next!=NULL)//若直接前驱存在且待删结点存在{p=q->next;//p指向待删结点q->next=p->next;//移出待删结点free(p);//释放已移出结点p的空间}elseexit(“找不到要删除的结点”);//结点不存在}八、其他链表

1、循环链表：在单链表中，如果让最后一个结点的指针域指向第一个结点可以构成循环链表。在循环链表中，从任一结点出发能够扫描整个链表。

2、双向循环链表：在单链表的每个结点中再设置一个指向其直接前驱结点的指针域prior，这样每个结点有两个指针，其结点结构如图：

prior与next类型相同，它指向直接前驱结点。头结点的prior指向最后一个结点，最后一个结点的next指向头结点，由这种结点构成的链表称为双向循环链表，双向循环链表适合应用在需要经常查找结点的前驱和后继的场合。双向循环链表的对称性可以用下列等式表示：p=p->prior->next=p->next->prior。即结点p的前驱结点的next和后继结点的prior都指向结点p。

九、顺序实现与链接实现的比较

2、线性表与链表的优缺点

(1)单链表的每个结点包括数据域与指针域，指针域需要占用额外空间。

(2)从整体考虑，顺序表要预分配存储空间，如果预先分配得过大，将造成浪费，若分配得过小，又将发生上溢；单链表不需要预先分配空间，只要内存空间没有耗尽，单链表中的结点个数就没有限制。

十、栈、队列和数组

栈和队列可看作是特殊的线性表。它们的特殊性表现在它们的基本运算是线性表运算的子集，它们是运算受限的线性表。栈和队列是计算机科学中使用得较为广泛的两种结构。

1、栈

栈是运算受限的线性表，这种线性表上的插入和删除运算限定在表的某一端进行。允许进行插入和删除的一端称为栈顶，另一端称为栈底。栈的修改原则是后进先出，因此，栈又称为后进先出线性表，简称后进先出表。

2、栈的顺序实现

桟的顺序存储结构是用一组连续的存储单元依次存放桟中的每个元素，并用始端作为栈底。栈的顺序实现称为顺序栈。通常用一个一维数组和一个记录栈顶位置的变量来实现栈的顺序存储。

3、双栈

在某些应用中，为了节省空间，让两个数据元素类型一致的栈共享一维数组空间data[max]，成为双栈，两个栈的栈底分别设在数组两端，让两个栈彼此迎面“增长”，两个栈的栈顶变量分别为top1、top2，仅当两个栈的栈顶位置在中间相遇时（top1+1=top2）才发生“上溢”，双栈如图：

注意：判断上溢为top1+1=top2。判栈空时，两个栈不同，当top1=0时栈1为空栈，top2=max-1时栈2为空桟。

4、栈的链接实现

栈的链接实现称为链栈，链栈可以用带头结点的单链表来实现，LS指向链表的头结点，首结点是栈顶结点，LS->next指向栈顶结点，尾结点为栈底结点。各结点通过链域的连接组成栈，由于每个结点空间都是动态分配产生，链栈不用预先考虑容量的大小。

5、队列

队列是有限个同类型数据元素的线性序列，是一种先进先出的线性表，出队列的数据元素在队列首部被删除。排队的规则是不允许插队。

6、队列的顺序实现

顺序存储实现的队列称为顺序队列，它由一个一维数组（用于存储队列中元素）及两个分别指示队列首和队列尾元素的变量组成，这两个变量分别称为“队列首指针”和“队列尾指针。

7、循环队列

为了避免元素的移动，可以将存储队列元素的一维数组首尾相接，形成一个环状；如图所示：

8、队列的链接实现

队列的链接实现实际上是使用一个带有头结点的单链表来表示队列，称为链队列。头指针指向链表的头结点，单链表的头结点的next域指向队列首结点，尾指针指向队列尾结点，即单链表的最后一个结点，如图所示：

9、数组

数组可以看成线性表的一种推广。数组类型是许多程序设计语言的基本类型。一维数组又称向量，它由一组具有相同类型的数据元素组成，并存储在一组连续的存储单元中。一般地，一个n维数组可以看成元素为n-1维数组的线性表。

10、数组通常只有两种基本运算：

（1）读：给定一组下标，返回该位置的元素内容；（2）写：给定一组下标，修改该位置的元素内容。

11、数组的存储结构

一维数组元素的内存单元地址是连续的；二维数组有2种存储方法，以列序为主序的存储和以行序为主序的存储。数组元素的存储位置是下标的线性函数。

十一、矩阵的压缩存储

矩阵可以用二维数组来表示。在数值分析中经常出现一些高阶矩阵，这些高阶矩阵中有许多值相同的元素或零元素，为了节省存储空间，对这类矩阵采用多个值相同的元素只分配一个存储空间，零元素不存储的策略，这一方法称为矩阵的压缩存储。矩阵的非零元素个数很少的矩阵称为稀疏矩阵。

1、特殊矩阵

（1）对称矩阵：若一个n阶方阵A中的元素满足下述条件：aij=aji0≤i，j≤n-1，则A称为对称矩阵。

（2）三角矩阵：以主对角线为界的上(下)半部分是一个固定的值c或零，这样的矩阵叫做下(上)三角矩阵。

2、稀疏矩阵：假设m行n列的矩阵有t个非零元素，当t＜＜m*n时，则称矩阵为稀疏矩阵。

十二、树

1、树：树是n(n多0)个结点的有限集合，一棵树满足以下两个条件：

（1）当n=0时，称为空树；

（2）当n>0时，有且仅有一个称为根的结点，除根结点外，真余结点分m(m≥0)个互不相交的非空集合T1，T2，…，Tm，这些集合中的每一个都是一棵树，称为根的子树。

2、森林：是m(m>0)棵互不相交的树的集合。树的每个结点的子树是森林。删除一个非空树的根结点，它的子树便构成森林。

3、基本术语

(1)结点的度：树上任一结点所拥有的子树的数目称为该结点的度。

(2)叶子：度为0的结点称为叶子或终端结点。

(3)树的度：一棵树中所有结点的度的最大值称为该树的度。

(4)一个结点的子树的根称为该结点的孩子（或称子结点）。相应地该结点称为孩子的双亲（也称父结点）。

(5)结点的层次：从根开始算起，根的层次为1,其余结点的层次为其双亲的层次加1。

(6)树的高度：一棵树中所有结点层次数的最大值称为该树的高度或深度。

(7)有序树：若树中各结点的子树从左到右是有次序的，不能互换，称为有序树。有序树中最左边子树的根称为第1个孩子，左边第i个子树的根称为第i个孩子。

(8)无序树：若树中各结点的子树是无次序的，可以互换，则称为无序树。

4、树的存储结构

树有如下三种常用的存储结构：

1）、孩子链表表示法

孩子链表表示法是树的一种链式存储结构。它的主体是一个数组元素个数和树中结点个数相同的一维数组。树上的一个结点X以及该结点的所有孩子结点组成一个带头结点的单链表，单链表的头结点含有两个域：数据域和指针域。其中，数据域用于存储结点X中的数据元素，指针域用于存储指向X第一个孩子结点的指针。除头结点外，其余所有表结点也含两个域：孩子域(child)和指针域(next)，孩子域存储其中一个孩子的序号，指针域指向其下一个孩子的结点。为了便于找到双亲，可在各个头结点中增加一个双亲域以存储双亲在头结点数组中的下标值。这种存储结构称为带双亲的孩子链表表示法。

2）、孩子兄弟链表表示法

存储时每个结点除了数据域外，还有指向该结点的第一个孩子和下一个兄弟结点的指针。

注意：孩子兄弟链表的结构形式与二叉链表完全相同，但结点中指针的含义不同。二叉链表中结点的左、右指针分别指向左、右孩子；而孩子兄弟链表中结点的两个指针分别指向孩子和兄弟。

3）、双亲表示法

双亲表示法由一个一维数组构成。数组的每个分量包含两个域：数据域和双亲域。数据域用于存储树上一个结点中数据元素，双亲域用于存储本结点的双亲结点在数组中的序号(下标值)。

十三、二叉树（BinaryTree）

0、二叉树的作用

二叉树是一种重要的数据结构，与数组、链表都是一种顺序容器，它们提供了按位置访问数据的手段。想要通过值来获取数据，只能通过遍历的方式。而二叉树是按值来保存元素，也按值来访问元素。

1、二叉树是n(n≥0)个元素的有限集合，该集合或者为空，或者由一个根及两棵互不相交的左子树和右子树组成，其中左子树和右子树也均为二叉树。

注意：二叉树的任一结点都有两棵子树（它们中的任何一个都可以是空子树），并且这两棵子树之间有次序关系，即如果互换了位置就成为一棵不同的二叉树。二叉树上任一结点左、右子树的根分别称为该结点的左孩子和右孩子。

2、二叉树有五种基本形态。如图所示，其中方块表示子树。

3、二叉树的基本运算包括：

(1)初始化Initiate(BT)：建立一棵空二叉树，BT=0。

(2)求双亲Parent(BT,X)：求出二叉树BT上结点X的双亲结点，若X是BT的根或X根本不是BT上的结点，运算结果为NULL。

(3)求左孩子Lchild(BT，X)和求右孩子Rchild(BT，X)：分别求出二叉树BT上结点X的左、右孩子；若X为BT的叶子或X不在BT上，运算结果为NULL。

(4)建二叉树

(5)先序遍历、中序遍历、后序遍历、层次遍历

4、满二叉树和完全二叉树

满二叉树：深度为k（k≥1）且有2k-1个结点的二叉树称为满二叉树。满二叉树上的结点数已达到了二叉树可以容纳的最大值。

完全二叉树：如果对满二叉树按从上到下，从左到右的顺序编号，并在最下一层删去部分结点（删后最后一层仍有结点），如果删除的这些结点的编号是连续的且删除的结点中含有最大编号的结点，那么这棵二叉树就是完全二叉树。满二叉树一定是完全二叉树，完全二叉树不一定是满二叉树。

二叉查找树：二叉查找树，又被称为二叉搜索树。其特点如下：设x为二叉查找树中的一个结点，x节点包含关键字key，一句话就是左孩子比父节点小，右孩子比父节点大，还有一个特性就是”中序遍历“可以让结点有序。

5、二叉树的存储结构

二叉树通常有两类存储结构：顺序存储结构和链式存储结构。链式存储结构在插入删除结点时较方便；二叉树的顺序存储结构可以用一维数组来实现，二叉树上的结点按某种次序分别存入该数组的各个单元中。由二叉树的性质可知，如果对任一完全二叉树上的所有结点按层编号，则结点编号之间的关系可以准确地反映结点之间的逻辑关系。对于任何完全二叉树来说，可以采用以编号作为数组的下标的方法将结点存入一维数组中，也就是将编号为i的结点存入一维数组的以i为下标的数组元素中。

如果需要顺序存储的非完全二叉树，首先必须用某种方法将其转化为完全二叉树，为此可增设若干个虚拟结点。这样可以用与处理完全二叉树相同的方法实现二叉树的基本运算。但这种方法的缺点是造成了空间的浪费。如图所示：

6、二叉树的链式存储结构

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

2）、每个二叉链表还必须有一个指向根结点的指针，该指针称为根指针。与链表头指针类似，根指针具有标识二叉链表的作用，对二叉链表的访问只能从根指针开始。如果某个结点的左孩子或右孩子不存在时，则相应指针域值为空，可知叶结点的左右指针必为空(NULL)。在三叉链表中每个结点增加一个指针域parent，用于指向该结点的双亲。

3）、类型定义

（1）二叉链表

typedefstructbtnode{DataTypedata;structbtnode*lchild,*rchild;//指向左右孩子的指针}*BinTree;（2）三叉链表

typedefstructttnode{datatypedata;structttnode*lchild,*parent,*rchild;}*TBinTree;二叉树的链式存储结构操作方便，结点间的父子关系在二叉链表和三叉链表中被直接表达成对应存储结点之间的指针，因而成为二叉树最常用的存储结构。

7、二叉树的遍历

1）、二叉树的层次遍历

二叉树的层次遍历，是指从二叉树的根结点的这一层开始，逐层向下遍历，在每一层上按从左到右的顺序对结点逐个访问。层次遍历可以用一个队列来实现。

2）、二叉树遍历的非递归实现

借助栈实现二叉树遍历的非递归过程。实现中序遍历的非递归算法，只需将先序遍历的非递归算法中的Visit(p->data)移动到Pop(LS，p)和p=p->rchild之间即可。后序遍历与先序遍历和中序遍历不同，在后序遍历过程中，结点在第一次出栈后，还需再次入栈，也就是说，结点要两次入栈，两次出栈，遍历结点是在结点的第二次出栈时进行。

8、平衡二叉查找树-------AVL树（平衡二叉树）

背景：两位俄罗斯的数学家G.M.Adelson-Velskii和E.M.Landis在1962年发明了平衡二叉树，为了解决如果插入二叉搜索树的数据是有序或接近有序的，此时二叉搜索树会退化为单支树，在单支树当中查找数据相当于在单链表当中查找数据，效率是很低下的。

AVL树是平衡叉查找树，增加和删除节点后通过树形旋转重新达到平衡。右旋是以某个节点为中，将它沉当前右节点的位置，让当前的左节点作为新树的根节点，也称为顺时针旋转。同理左旋是以某个节点为中，将它沉当前左节点的位置，让当前的右节点作为新树的根节点，也称为逆时针旋转。

9、平衡二叉查找树--------红黑树

称为对称叉B树，1978年正式命名红树。主要特征是在每个节点上增加个属性表示节点颜，可以红或。

10、平衡二叉树和红黑树区别：

红树的平衡性不如AVL树，它维持的只是种致的平衡，不严格保证左右树的度差不超过1。这导致节点数相同的情况下，红树的度可能更，也就是说平均查找次数会于相同情况的AVL树。

11、多路查找树------B树(B-树)和B+树（文件系统、数据库底层的重要数据结构）

B树

特点：

（1）树中每个结点至多有m棵子树（注：m指的是树的阶）；

（2）若根结点不是叶子结点，则至少有两棵子树（注：根节点至少有两个儿子）；

如上图所示：根节点存储磁盘块1的数据，p1指针指向盘块2，检索数据先从根节点开始，将磁盘块1的数据加载到内存中，从内存中根据索引查找符合条件的数据，若是17和35则直接命中，返回data；若小于17则通过p1指针加载磁盘块2中的数据，每加载一次磁盘块的数据进行一次IO。B树的缺点是由于data占用空间较大，每次IO加载的数据有限，造成检索期间IO次数过多。

B+树

B-Tree是为磁盘等外存储设备设计的一种平衡查找树，B-树中每个节点同时存储key和data，B+树中只有叶节点才存储data，叶节点只存储key。InnoDB对B+树进了优化，在每个叶节点上增加了个指向相邻叶节点的链表指针，形成了带有顺序指针的B+树，提区间访问的性能。

B+树的优点在于：

①由于B+树在叶节点上不含数据信息，因此在内存中能够存放更多的key，数据存放得更加紧密，具有更好的空间利率，访问叶节点上关联的数据也具有更好的缓存命中率。

②B+树的叶结点都是相连的，因此对整棵树的遍历只需要次线性遍历叶节点即可。B树则需要进每层的递归遍历，相邻的元素可能在内存中不相邻，所以缓存命中性没有B+树好。但是B树也有优点，由于每个节点都包含key和value，因此经常访问的元素可能离根节点更近，访问也更迅速。

十四、树、森林与二叉树的关系

1、树转换成二叉树：任何一棵树可唯一地与一棵二叉树对应。相应地，一棵二叉树也唯一地对应一棵树，即树与二叉树可以互相转换。

2、森林可转换成二叉树，同样，二叉树可转换成森林

十五、判定树和哈夫曼树

1、分类与判定树

分类是一种常用运算，其作用是将输入数据按预定的标准划分成不同的种类。用于描述分类过程的二叉树称为判定树。

2、哈夫曼树与哈夫曼算法给定一组值p1…，pk，如何构造一棵有k个叶子且分别以这些值为权的判定树，使得其平均比较次数最小。满足上述条件的判定树称为哈夫曼树。哈夫曼率先给出了一个求哈夫曼树的简单而有效的方法，称为哈夫曼算法。应用于哈夫曼编码。

十六、图

1、有向图、无向图

图G由两个集合V和E组成，记为G=(V，E)，其中，V是顶点的有穷非空集合；E是边的集合，边是V中顶点的偶对。若顶点的偶对是有序的，则称此图为有向图，有序偶对用尖括号<>括起来；若顶点的偶对是无序的，则称此图为无向图，无序偶对用圆括号（）括起来。

3、无向完全图、有向完全图

任何两点之间都有边的无向图称为无向完全图。一个具有n个顶点的无向完全图的边数为n(n-1)/2。

任何两点之间都有弧的有向图称为有向完全图。一个具有n个顶点的有向完全图的弧数为n(n-1)。

4、权、带权图

图的边附带数值，这个数值叫权。权在实际应用中可表示从一个顶点到另一个顶点的距离、代价或耗费等。每条边都带权的图称为带权图。

5、顶点的度、入度、出度

6、子图

7、图的基本运算：

(1)建立图CreateGraph(G，V，E)：建立一个图G，其中V是G的顶点集合，E是G的边的集合；

(2)取顶点信息GetVex(G，u)：获取图G中顶点u的信息；

(3)取边信息Getarc(G，v)：获取图G中边(u，v)或的信息；

(4)查询第一个邻接点FirstVex(G，u)：获取图G中顶点u的第一个邻接点；

(5)查询下一个邻接点NextVex(G,u，v)：已知v是u的一个邻接点，获取图G中顶点u的下一个邻接点；

(6)插入顶点InsertVex(G，v)：在图G中插入一个顶点v;

(7)删除顶点DeleteVex(G，v)：在图G中删除一个顶点v;

(8)插入边InsertArc(G，v，w)：在图G中插入一条边(v，w)或;

(9)删除边DeleteArc(G，v，w)：在图G中删除一条边(v，w)或;

(10)遍历图Traverse(G,tag)：遍历图G，使G中每个顶点被访问一次且仅被访问一次，当tag=0，则遍历的方法为深度优先搜索，当tag=1，则遍历的方法为广度优先搜索。

十七、图的存储结构

邻接矩阵

1、邻接矩阵就是用矩阵来描述图中顶点之间的关联关系，在程序设计语言中很容易用二维数组来实现矩阵。设G=(V，E)是一个图，其中V={v0,v1，…，vn-1}，那么G的邻接矩阵A定义为如下的n阶方阵：

注意：无向图的邻接矩阵是一个对称矩阵。

2、利用邻接矩阵可以判定任意两个顶点之间是否有边，并容易求得各个顶点的度。对于有向图，顶点vi的出度OD(vi)是邻接矩阵中第i行元素之和，顶点vi的入度ID(vi)是

邻接矩阵中第i列元素之和。

3、无向带权图的邻接矩阵的建立方法是：首先将矩阵A的每个元素都初始化为最大值，然后读入边及权值(i，j,wij)，将A的相应元素置成wij。

邻接表

1、邻接表是顺序存储与链式存储相结合的存储方法

在邻接表中，对图中每个顶点建立一个单链表。对于无向图，第i个单链表中的结点表示依赖于顶点vi的边，对于有向图是以顶点vi为尾的弧，这个单链表称为顶点vi的邻接表。每一个单链表设一个表头结点，每一个表头结点有两个域vertex和firstarc，vertex用来存放顶点vi的信息，firstarc用来指向邻接表中的第一个结点。为了便于随机访问，将所有单链表的头结点组成一个一维数组Adjlist。单链表中每一个结点称为表结点，包括两个域：邻接点域(adjvex)和链域(nextarc)，邻接点域用以存放与vi相邻接的顶点在数组Adjlist中的序号，链域用以指向同vi邻接的下一个结点。在带权图的表结点中增加一个权值域，用于存储边的权值(weight)。

2、邻接表的类型定义

如果一个无向图有n个顶点，e条边，那么它的邻接表需要n个头结点和2e个表结点。显然，在边稀疏(e<

4、逆邻接表

对于有向图，有时需要建立一个逆邻接表，即对每个顶点vi建立一个以vi为弧头的邻接点的链表。这同邻接表正好相反。对于逆邻接表可以很容易求出vi的入度。

十八、图的遍历

图的遍历是指从图的某个顶点出发，系统地访问图的每个顶点，并且每个顶点只被访问一次。遍历图的基本方法有两种：深度优先搜索和广度优先搜索。这两种方法都适用于有向图和无向图。

1、连通图的深度优先搜索

连通图深度优先搜索的基本思想：假定以图中某个顶点vi为出发点，首先访问出发点vi，然后任选一个vi的未访问过的邻接点vj，以vj为新的出发点继续进行深度优先搜索，依此类推，直至图中所有顶点都被访问过。深度优先搜索遍历类似于树的先序遍历。

2、连通图的广度优先搜索

1）、连通图广度优先搜索的基本思想是：从图中某个顶点vi出发，在访问了vi之后依次访问vi的所有邻接点，然后依次从这些邻接点出发按广度优先搜索方法遍历图的其他顶点，重复这一过程，直至所有顶点都被访问到。广度优先搜索遍历类似于树的按层次遍历的过程。

2）、在广度优先搜索中，若对x的访问先于y，则对x的邻接点的访问也先于对y的邻接点的访问，也就是说广度优先搜索邻接点的寻找具有先进先出的特征。因此，为了保证结点的这种先后关系，可采用队列来暂存那些刚访问过的顶点。

3）、若图的存储结构为邻接表，队采用链队列。

4）、如果采用邻接矩阵作为存储结构，查找邻接点操作实际上通过循环语句顺序访问邻接矩阵的某一行。

二十、拓扑排序

1、AOV网

如果以图中的顶点来表示活动，有向边表示活动之间的优先关系，这种用顶点表示活动的有向图称为AOV网。AOV网中的弧表示了活动之间存在着的制约关系。

2、拓扑排序

设G=(V，E)是一个具有n个顶点的有向图，V中顶点的序列v1，v2，…，vn称为一个拓扑序列，当且仅当该顶点序列满足下列条件：若在有向图G中，从顶点vi到vj有一条路径，则在拓扑序列中顶点vi必须排在顶点Vj之前。找一个有向图的一个拓扑序列的过程称为拓扑排序。完成拓扑排序的前提条件是AOV网中不允许出现回路。

可以证明，任何一个无环有向图，其全部顶点可以排成一个拓扑序列。

二十一、查找

1、查找表

查找表(SearchTable)是由同一类型的数据元素构成的集合，它是一种以查找为“核心”，同时包括其他运算的非常灵活的数据结构。

2、静态查找表、动态查找表

作为一种数据结构，查找表的逻辑结构是集合，对查找表进行的操作包括查找表中某一元素、读取表中“特定”数据元素、插入和删除一个数据元素等。若对查找表只进行前两项操作，则称此类查找表为静态查找表。若在查找过程中，向表中插入不存在的数据元素，或者从表中删除某个数据元素，则称此类表为动态查找表。

二十二、静态查找表

1、顺序表上的查找

1）、静态查找表最简单的实现方法是以顺序表作为存储结构。静态查找表顺序存储结构的类型定义如下：

constintMaxsize=20;//静态查找表的表长typedefstruct{KeyTypekey;//关键字…//其他域}TableElem;typedefstruct{TableElemelem[Maxsize+l];intn;//最后一个数据元素的下标}SqTable;这里，将静态查找表中的数据元素存放在上述数组的第1到第n个单元中，第n+1到最后一个单元为备用区(空闲区）。

2）、查找长度

2、有序表上的查找

1）、如果顺序表中数据元素是按照键值大小的顺序排列的，则称为有序表。二分查找(BinarySearch)的查找过程为每次用给定值与处在表的中间位置的数据元素的键值进行比较，确定给定值的所在区间，然后逐步缩小查找区间。

2）、平均查找长度

二分查找算法每进行一次键值与给定值的比较，查找区间的长度至少减小为原来二分之一，“二分查找”由此得名。由此易推算出二分查找的查找长度不超过Llog2n」+1。二分查找的平均查找长度为ASLb≈log2(n+1)-1

3、索引顺序表上的查找

1）、索引顺序表是结合了顺序查找和二分查找的优点构造的一种带索引的存储结构。

一个索引顺序表由两部分组成：一个索引表和一个顺序表。其中的顺序表在组织形式上与普通的顺序表完全相同，而索引表本身在组织形式上也是一个顺序表。索引表通过索引将顺序表分割为若干块，而顺序表呈现出“按块有序”的性质。

2）、若静态查找表用索引顺序表表示，则查找操作可用分块查找来实现，也称为索引顺序查找。

3）、平均查找长度：分块查找的平均查找长度等于两阶段各自的查找长度之和。

4）、优缺点

静态查找表的上述三种不同实现各有优缺点。其中，顺序查找效率最低但限制最少。二分查找效率最高，但限制最强。而分块查找则介于上述二者之间。在实际应用中应根据需要加以选择。

二十三、二叉排序树

一种实现动态查找的树表，这种树表的结构本身是在查找过程中动态生成的，即对于给定key，若表中存在与key相等的元素，则查找成功，不然，插入关键字等于key的元素。一棵二叉排序树(又称二叉查找树)或者是一棵空二叉树，或者是具有下列性质的二叉树：

(1)若它的左子树不空，则左子树上所有结点的键值均小于它的根结点键值；

(2)若它的右子树不空，则右子树上所有结点的键值均大于它的根结点键值；

(3)根的左、右子树也分别为二叉排序树。

1、二叉排序树上的查找

由于二叉排序树的特点，要找键值比某结点键值小(大)的结点，只需通过此结点的左指针(右指针)到它的左(右)子树中去找。所以查找操作的递归实现较为简单。

由上面的查找过程可知：在二叉排序树上进行查找，若查找成功，则是从根结点出发走了一条从根结点到待查结点的路径；若查找不成功，则是从根结点出发走了一条从根到某个叶子的路径。因此与二分查找类似，关键字比较的次数不超过二叉树的深度。

2、二叉排序树的插入

在二叉排序树上进行插入的原则是：必须要保证插入一个新结点后，仍为一棵二叉排序树。这个结点是查找不成功时查找路径上访问的最后一个结点的左孩子或右孩子。

3、二叉排序树的查找分析

二叉排序树上的平均查找长度是介于O(n)和O(log2n)之间的，其查找效率与树的形态有关。二叉排序树的平均查找长度ASL≤1+log2n。

二十四、散列表

为了使数据元素的存储位置和键值之间建立某种联系，以减少比较次数，使用散列技术实现动态查找表。数据元素的键值和存储位置之间建立的对应关系H称为散列函数，用键值通过散列函数获取存储位置的这种存储方式构造的存储结构称为散列表(HashTable)，这一映射过程称为散列。

如果选定了某个散列函数H及相应的散列表L，则对每个数据元素X，函数值H(X.key)就是X在散列表L中的存储位置，这个存储位置也称为散列地址。设有散列函数H和键值k1、k2(k1≠k2)，若H(k1)=H(k2)，则这种现象称为“冲突”，且称键值k1和k2互为同义词。

1、常用散列法

若对于键值集合中的任一个键值，经散列函数映射到地址集合中任何一个地址的概率是相等的，则称此种散列函数是均匀的。以下假定散列地址是自然数，另外，假定键值也都是自然数。

1）、数字分析法

数字分析法又称数字选择法，其方法是收集所有可能出现的键值，排列在一起，对键值的每一位进行分析，选择分布较均匀的若干位组成散列地址。所取的位数取决于散列表的表长，见表长为100，则取2位即可。

2）、除留余数法

除留余数法是一种简单有效且最常用的构造方法，其方法是选择一个不大于散列表长n的正整数p，以键值除以p所得的余数作为散列地址，即H(key)=keymodp(p≤n)

注意：通常选p为小于散列表长度n的素数。

3）、平方取中法

平方取中法以键值平方的中间几位作为散列地址。这一方法计算简单，是一种较常用的构造散列函数的方法，通常在选定散列函数时不一定能知道键值的分布情况。取其中哪几位也不一定合适，而一个数平方的中间几位与这个数的每一位都有关，所得散列地址比较均匀。

4）、基数转换法

将键值看成另一种进制的数再转换成原来进制的数，然后选其中几位作为散列地址。

2、解决散列表的冲突的方式

假设散列表的地址集为0(n-1)，冲突是指由键值得到的散列地址上己存有元素，则解决冲突就是为该键值的元素找到一个空闲单元的散列地址。通常用来解决冲突的方法有以下几种：

1）、线性探测法

对任何键值key，设H(key)=d，设散列表的容量为m，则线性探测法生成的后继散列地址序列为d+1，d+2，…，m-1，0，1，…，d-1

2）、二次探测法

二次探测法的基本思想：生成的后继散列地址不是连续的，而是跳跃式的，以便为后续数据元素留下空间从而减少堆积。二次探测法的缺点是不易探测到整个散列表的所有空间，也就是说，上述后继散列地址可能难以包括散列表的所有存储位置。

3）、链地址法

链地址是对每一个同义词都建一个单链表来解决冲突，其组织方式如下：设选定的散列函数为H,H的值域(即散列地址的范围)为0(n-1)。设置一个“指针向量”

PointerHP[n]，其中的每个指针HP[i]指向一个单链表，该单链表用于存储所有散列地址为i的数据元素。每一个这样的单链表称为一个同义词子表。

4）、多重散列法

此法要求设立多个散列函数Hi，i=1，…，k。当给定值key与散列表中的某个键值是相对于某个散列函数氏的同义词而发生冲突时，继续计算这个给定值key在下一个散列函数Hi+1下的散列地址，直到不再产生冲突为止。这种方法的优点是不易产生“堆积”，缺点是计算量较大。

5）、公共溢出区法

按这种方法，散列表由两个一维数组组成。一个称为基本表，它实际上就是上面所说的散列表，另一个称为溢出表。插入首先在基本表上进行，假如发生冲突，则将同义词存入溢出表。这样，基本表不可能发生“堆积”。

3、散列表的基本操作算法

1）、链地址法散列表

（1）查找

首先计算给定值key的散列地址i,由它到指针向量中找到指向key的同义词子表的表头指针。然后，在该同义词子表中顺序查找键值为key的结点。

（2）插入

散列表上的插入算法应包含查找功能，并在查找不成功时申请一个结点来存储这个元素，实施新结点的链入操作。用“前插法”插入新结点，即将新结点插到同义词子表的表头结点之后、原表首结点(若存在的话)之前。