导图社区 数据结构教程
- 43
- 5
- 2
- 举报
数据结构教程
数据结构基础框架，包括线性表、栈和队列、串、数组和广义表、树和二叉树、图等内容梳理，总结的非常全面，感兴趣的伙伴可以收藏哦。
编辑于2022-07-19 19:42:28
- 相似推荐
- 大纲
数据结构
绪论
什么是数据结构
数据结构的定义
数据结构定义
数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。 数据结构是一门介于数学、计算机硬件和软件三者之间的核心课程。
数据
是描述客观事物的数和字符的集合
数据项
是具有独立含义的数据最小单位，也称字段或域。
数据对象
是指性质相同的数据元素的集合，它是数据的一个子集。
数据结构
是指所有数据元素以及数据元素之间的关系，可以看作是相互之间存在着某种特定关系的数据元素的集合。
逻辑结构
概述
数据的逻辑结构是从数据元素的逻辑关系上描述数据的，是指数据元素之间的逻辑关系的整体，通常是从求解问题中提炼出来的。
表示方法
图标表示
二元组表示
类型
集合
线性结构
树形结构
存储结构
顺序存储结构
顺序存储结构是采用一组连续的存储单元存放所有的数据元素，所有的数据元素在存储器中占有一整块存储空间，而且两个逻辑上相邻的元素在存储器上的存储位置也相邻。借助元素在存储器中的相对位置来表示数据元素间的逻辑关系。
链式存储结构
在链式存储结构中，每个逻辑元素用一个内存结点存储，每个结点是单独分配的，所有的结点地址不一定连续，所以无需占用一整块存储空间。借助指示元素存储地址的指针表示数据元素间的逻辑关系。
索引存储结构
索引存储结构是指在存储数据元素信息的同时还建立附加的索引表。存储所有数据元素信息的表称为主数据表，其中每个数据元素有一个关键字和对应的存储地址。
哈希(或散列)存储结构
哈希存储结构的基本思想是根据元素的关键字通过哈希函数直接计算出一个值，并将这个值作为该元素的存储地址。
数据运算
数据运算是指对数据实施的操作。
最常用的运算有检索、插入、删除、更新、排序
算法及其描述
什么是算法
概念
算法是对特定问题求解步骤的一种描述，它是指令的有限序列。
算法特性
有穷性
确定性
可行性
有输入
有输出
算法设计的目标
正确性
可使用性
可读性
健壮性
高效率与低存储量需求
算法分析
概述
算法分析就是分析算法占用计算机资源的多少。算法分析的目的是分析算法的时空性能以便改进算法。
时间性能
算法时间复杂度也称为渐进时间复杂度，它表示随问题规模n的增大，算法执行时间的增长率和f(n)的增长率相同。
一般情况下，一个没有循环(或者有循环，但循环次数与问题规模n无关)的算法中原操作执行次数与问题规模n无关，记作O(1)，也称为常数阶。
O(1)<O(log2n)<O(n)<O(nlog2n)<O(n²)<O(n³)<O(2n)<O(n!)
空间性能
算法空间复杂度是对一个算法在运行过程中临时占用的存储空间大小的度量。
数据结构+算法=程序
计算机软件的最终成果都是以程序的形式表现的，数据结构和算法分析的目的是设计好的程序。程序设计的本质是对要处理的问题选择好的数据结构，同时在此结构上施加一种好的算法。
线性表
线性表及其逻辑结构
线性表的定义
线性表是具有相同特征的数据元素的一个有限序列。该序列中所含元素的个数称为线性表的长度。
线性表的特性
有穷性
一个线性表中元素的个数是有限的。
一致性
一个线性表中所有元素的性质相同。
序列性
一个线性表中所有元素之间的相对位置是线性的，即存在唯一的开始元素和终端元素，除此之外，每个元素只有唯一的前驱元素和后继元素。
线性表的抽象数据类型描述
InitList(&L)
初始化线性表，构造一个空的线性表L
DestroyList(&L)
销毁线性表，释放线性表L占用的内存空间
ListEmpty(L)
判断线性表是否为空表，若L为空表，则返回真，否则返回假
ListLength(L)
求线性表的长度，返回L中元素的个数
DispList(L)
输出线性表，当线性表L不为空时顺序显示L中各结点的值域
GetElem(L,i,&e)
求线性表中某个数据元素值，用e返回L中第i个元素的值
LocateElem(L,e)
按元素值查找，返回L中第一个值域与e相等的元素的序号，若这样的元素不存在，则返回值为0
ListInsert(&L,i,e)
插入数据元素，在L的第i个位置插入一个新的元素e，L的长度增1
ListDelete(&L,i,&e)
删除数据元素，删除L的第i个元素，并用e返回其值，L的长度减1
线性表的作用
当一个线性表实现后，程序员可以直接使用它来存放数据，即作为存放数据的容器，另外程序员可以直接使用它的基本运算来完成更复杂的功能。
线性表的顺序存储结构
线性表的顺序存储结构是把线性表中的所有元素按照其逻辑顺序依次存储到从计算机存储器中指定存储位置开始的一块连续存储空间中。线性表的顺序存储结构简称为顺序表。
线性表的链式存储结构
线性表的链式存储结构称为链表。线性表中每个元素最多只有一个前驱元素和一个后继元素，所以当采用链式存储结构时，一种最简单、最常用的方法是在每个结点中除包含有数据域以外只设置一个指针域，用于指向其后继结点，这样构成的链表称为线性单向链接表，简称单链表；另一种可以采用的方法是在每个结点中除包含有数据域以外设置两个指针域，分别用于指向其前驱节点和后继节点，这样构成的链表称为线性双向链接表，简称双链表。
链表和顺序表的比较
在顺序表中，逻辑上相邻的元素对应的存储位置也相邻，所以当进行插入或删除操作时通常需要平均移动半个表的元素，这是相当费时的操作。 在链表中，逻辑上相邻的元素对应的存储位置是通过指针来链接的，当进行插入或删除操作时只需要修改相关结点的指针域即可，既方便又省时。
在线性表的链式存储中,通常每个链表带有一个头结点，并通过头结点的指针唯一标识该链表，称之为头指针，相应的指向首结点或者开始结点的指针称之为首指针，指向尾结点的指针称为尾指针。
循环链表 ：循环链表是另一种形式的链式存储结构。循环链表有循环单链表和循环双链表两种类型。把单链表改为循环单链表的过程是将它的尾结点next指针域由原来的空改为指向头结点，整个单链表形成一个环。
线性表的应用
笛卡尔积 自然连接
有序表
所谓有序表是指这样的线性表，其中所有元素以递减或递增方式有序排列。
栈和队列
栈
栈的定义
栈是一种只能在一端进行插入或删除操作的线性表。表中允许进行插入、删除操作的一端称为栈顶，表的另一端称为栈底。栈顶的当前位置是动态的，栈顶的当前位置由一个被称为栈顶指针的位置指示器来指示。当栈中没有数据元素时称为空栈。栈的插入操作通常称为进栈或入栈(push)，栈的删除操作通常称为出栈或退栈(pop)。
栈的特点
后进先出(Last In First Out)，即后进栈的元素先出栈。栈也称为后进先出表。
4个要素
栈空的条件：s->top==-1
栈满的条件：s->top==MaxSize-1(data数组的最大下标)
元素e的进栈操作：先将栈顶指针top增1，然后将元素e放在栈顶指针处。
出栈操作：先将栈顶指针top处的元素取出放在e中，然后将栈顶指针减1。
6种基本运算算法
初始化栈initStack(&s)
销毁栈DestroyStack(&s)
判断栈是否为空StackEmpty(s)
进栈Push(&s,e)
出栈Pop(&s,&e)
取栈顶元素GetTop(s,&e)
栈的链式存储结构
栈中数据元素的逻辑关系呈线性关系，所以栈可以像线性表一样采用链式存储结构。采用链式存储结构的栈称为链栈。 链栈的优点是不存在栈满上溢出的情况。
队列
队列的定义
队列简称队，它也是一种操作受限的线性表，其限制为仅允许在表的一端进行插入操作，而在表的另一端进行删除操作。把进行插入的一端称为队尾(rear)，把进行删除的一端称为队头或队首(front)，向队列中插入新元素称为进队或入队(enqueue),新元素进队后就成为新的队尾元素；从队列中删除元素称为出队或离队(dequeue),元素出队后，其直接后继元素就成为队首元素。 队列称为先进先出表(First In First Out,FIFO)
队列的顺序存储结构
采用顺序存储结构的队列称为顺序队
环形队列
元素进队时队尾指针rear增1，元素出队时队首指针增1，当队满的条件成立时(rear==MaxSize-1)，表示此时队满了(上溢出)，不能再进队元素。队列中还可能有空位置，因为队满条件设置不合理导致队满条件成立而队列中仍然有空位置的情况称为假溢出。解决方法是把data数组的前端和后端连接起来，形成一个环形数组，即把存储队列元素的数组从逻辑上看成一个环，称为环形队列或循环队列。
队列的链式存储结构
采用链式存储结构的队列称为链队。
单链表链队：只允许在单链表的表头进行删除操作(出队)和在单链表的表尾进行插入操作(进队)，因此需要使用队头指针front和队尾指针rear两个指针。和链栈一样，链队中也不存在队满上溢出的情况。
双端队列
所谓双端队列是指两端都可以进行进队和出队操作的队列。将队列的两端分别称为前端和后端，两端都可以进队和出队。其元素的逻辑关系仍然是线性的。
串
串的基本概念
字符串简称串，串是由字符元素构成的，其中元素的逻辑关系也是一种线性关系。串的处理在计算机非数值处理中占有重要的地位，如信息检索系统、文字编辑等都是以串数据作为处理对象。
串
是由零个或多个字符组成的有限序列。
子串
一个串中任意个连续字符组成的序列称为该串的子串。
真子串
真子串是指不包含本身的子串。
空串
含有零个字符的串称为空串。
串长
串中所含字符的个数称为该串的长度(或串长)
串的存储结构
串的匹配模式
概述
设有两个串s和t，串t的定位就是要在串s中找到一个与t相等的子串。通常把s称为目标串，把t称为模式串，因此串定位查找也称为模式匹配。模式匹配成功是指在目标串s中找到模式串t；不成功则指目标串s中不存在模式串t。
Brute-Force(暴力)算法
简称为BF算法，也称简单匹配算法，采用穷举方法。
KMP算法
该算法与Brute-Force算法相比有较大的改进，主要消除了主串指针的回溯，从而使算法效率有了某种程度的提高。
递归
什么是递归
递归的定义
在定义一个过程或函数时出现调用本过程或本函数的成分称为递归。若调用自身，称为，称为直接递归。若过程或函数p调用过程或函数q，而q又调用函数p，称为间接递归。
栈和递归
递归算法的设计
图
概述
图形结构术语复杂的非线性数据结构，在实际应用中很多问题可以用图来描述。在图形结构中，每个元素可以有零个或多个前驱元素，也可以有零个或多个后继元素，也就是说元素之间的关系是多对多的。
图的基本概念
图的定义
图(graph)G由两个集合V(vertex)和E(edge)组成，记为G=(V,E)，其中V是顶点的有限集合，记为V(G),E是连接V中两个不同顶点(顶点对)的边的有限集合，记为E(G)。
有向图
在图G中，如果表示边的顶点对是有序的，则称G为有向图。在有向图中代表边的顶点用尖括号括起来，<j,i>和<i,j>是两条不同的边。
无向图
在无向图中(j,i)(i,j)代表的是同一条边
图的基本术语
端点和邻接点
在一个无向图中，若存在一条边(i,j)，则称顶点i和顶点j为该边的两个端点，并称它们互为邻接点。
在一个有向图中，存在有向边<i,j>，i为此边的起始端点，j为此边的终止端点，顶点j是顶点i的出边邻接点，顶点i是顶点j的入边邻接点。
顶点的度、入度和出度
在无向图中，一个顶点所关联的边的数目称为该顶点的度 在有向图中，顶点的度又分为入度和出度，以顶点j为终点的边数目，称为该顶点的入度，以顶点i为起点的边数目，称为该顶点的出度。一个顶点的入度与出度的和为该顶点的度。
完全图
若无向图中的每两个顶点之间都存在着一条边，有向图中的每两个顶点之间都存在着方向相反的两条边，则称此图为完全图。无向完全图存在n(n-1)/2条边，有向完全图存在n(n-1)条边。
稠密图和稀疏图
当一个图接近完全图时，称为稠密图。相反，当一个图含有较少的边数时，则称为稀疏图。
子图
设有两个图G=(V,E)和G'=(V',E')，若V'是V的子集，且E'是E的子集，则称G'是G的子图。
路径和路径长度
在一个图G=(V,E)中，从顶点i到顶点j的一条路径是一个顶点序列(i,i1,i2,···,im,j)。 路径长度是指一条路径上经过的边的数目。 若一条路径上除开始点和结束点可以相同以外，其余顶底啊均不相同，则称此路径为简单路径。
回路或环
若一条路径上的开始点和结束点为同一个顶点，则此路径被称为回路或环。 开始点和结束点相同的简单路径被称为简单回路或简单环。
连通、连通图和连通分量
在无向图G中，若顶点i到顶点j有路径，则称顶点i和顶点j是连通的。若图G中任意两个顶点都是连通的，则称G为连通图，否则称为非连通图。 无向图G中的极大连通子图称为G的连通分量，连通图的连通分量只有一个(即本身)。
强连通图和连通分量
在有向图中，若图G中任意两个顶点i和j都连通，即从顶点i到顶点j和从顶点j到顶点i都存在路径，则称图G是强连通图。在有向图G中的极大强连通子图称为G的强连通分量。强连通图只有一个强连通分量(即本身)。
权和网
图中的每一条边都可以附有一个对应的数值，这种与边相关的数值称为权。权可以表示从一个顶点到另一个顶点的距离或花费的代价。边上带有权的图称为带权图，也称作网。
图的存储结构和基本运算算法
邻接矩阵存储方法
图的邻接矩阵是一种采用邻接矩阵数组表示顶点之间关系的存储结构
邻接表存储方法
图的邻接表是一种顺序与链式存储相结合的存储方法
图基本运算算法
创建图
输出图
销毁图
图的遍历
从给定图中任意指定的顶点出发，按照某种搜索方法沿着图的边访问图中的所有顶点，使每个顶点仅被访问一次，这个过程称为图的遍历。
图的遍历有两种：深度优先遍历、广度优先遍历
生成树和最小生成树
一个连通图的生成树是一个极小连通子图，其中含有图中的全部顶点，和构成一棵树的(n-1)条边。
图的所有生成树中具有边上的权值之和最小的树称为图的最小生成树。
普里姆算法
普里姆算法就是通过一个顶点扩散开找权值最小的边,所经过的顶点和边就是这个图的最小生成树。
克鲁斯卡尔算法
Kruskal算法是一种按权值的递增次序选择合适的边来构造最小生成树的方法。
最短路径
由于从一顶点到另一顶点可能存在着多条路径，每条路径上所经过的边数可能不同，即路径长度不同，把路径长度最短的那条路径称为最短路径，其长度称为最短路径长度或最短距离。
Dijkstra算法：从一个顶点到其余各顶点的最短距离
拓扑排序
设G=(V,E)是一个具有n个顶点的有向图，V中的顶点序列v1，v2，···，vn称为一个拓扑排序。 在一个有向图中找一个拓扑序列的过程称为拓扑排序。
拓扑排序方法
从有向图中选择一个没有前驱的顶点并且输出它
从图中删去该顶点，并且删去从该顶点发出的全部有向边
重复上述两步，直到剩余的图中不再存在没有前驱的顶点为止
AOE网与关键路径
图中入度为0的顶点表示工程的开始事件，出度为0的顶点表示工程结束事件，称这样的有向图为边表示活动的网(AOE网)
通常每个工程都只有一个开始事件和一个结束事件，因此表示工程的AOE网都只有一个入度为0的顶点，称为源点，和一个出度为0的顶点，称为汇点。
在AOE网中，从源点到汇点的所有路径中具有最大路径长度的路径称为关键路径。 完成整个工程的最短时间就是AOE网中关键路径的长度，或者说是AOE网中一条关键路径上各活动持续时间的总和，把关键路径上的活动称为关键活动。 通常一个AOE网可能存在多条关键路径，但它们的长度是相同的。
树和二叉树
树的基本概念
树是由n个(n>=0)结点或元素组成的有限集合(记为T)
如果n=0，它是一棵空树，这是树的特例。
如果n>0，这n个结点中有且仅有一个结点作为树的根结点，简称为根，其余结点可分为m(m>=0)个互不相交的有限集，其中每个子集本身又是一棵符合本定义的树，称为根结点的子树。
树结构通常用于表示具有层次关系的数据
树的逻辑表示方法
树形表示法
用一个圆圈表示一个结点，圆圈内的符号表示该结点的数据信息，结点之间的关系通过连线表示。连线的上方结点是下方结点的前驱结点，下方结点是上方结点的后继节点。
文氏图表示法
每棵树对应一个圆圈，圆圈内包含根结点和子树的圆圈，同一根节点下的各子树对应的圆圈不能相交。
凹入表示法
每棵树的根节点对应一个条形，其子树的根对应着一个较短的条形，且树根在上，子树的根在下，同一个根下的各子树的根对应的条形长度是一致的。
括号表示法
每棵树对应一个形如"根(子树1，子树2，子树3，子树m)"的字符串，每棵子树的表示方式如整棵树类似，各子树之间用逗号分开。结点之间的关系是通过括号的嵌套表示的。
树的基本术语
结点的度与树的度
树中某个结点的子树的个数称为该结点的度。树中所有结点的度中最大值称为树的度。
分支节点与叶子节点
树中度不为零的结点称为非终端结点，又叫分支结点。度为零的结点称为叶子结点。在分支结点中，每个结点的分支数就是该结点的度。对于度为1的结点，其分支数为1，称为单分支结点；对于度为2的结点，其分支数为2，被称为双分支结点。
路径与路径长度
路径就是从ki出发"自上而下"到达kj所通过的树中结点序列。路径长度是该路径所通过的结点数减1。
孩子结点、双亲结点、兄弟结点
在一棵树中，每个结点的后继结点被称为该结点的孩子结点
该结点被称为孩子结点的双亲结点
具有同一双亲结点的孩子结点互为兄弟结点。
每个结点对应子树中的所有结点称为该结点的子孙结点，把从根结点到达某个结点的路径上经过的所有结点称为祖先结点。
结点层次和树的高度
树中的每个结点都处在一定的层次上。结点层次或结点深度是从树根开始定义的，根结点为第一层，它的孩子结点为第二层，以此类推。树中结点的最大层次称为树的高度或树的深度。
有序树和无序树
若树中各结点的子树是按照一定的次序从左向右安排的，且相对次序是不能随意变换的，则称为有序树，否则称为无序树。
森林
n(n>0)个互不相交的树的集合称为森林。把含有多棵子树的树的根结点删去就成了森林。反之，给m(m>1)棵独立的树加上一个根结点，并把这m棵树作为该结点的子树，则森林就变成了一棵树。
树的性质
树中的结点数等于所有结点的度数之和加1
度为m的树中第i层上最多有m的i-1次方个结点(i>=1)
树的基本运算
寻找满足某种特定条件的结点
插入或删除某个结点
遍历树中的所有结点
先根遍历
访问根结点，按照从左到右的顺序先根遍历根结点的每一棵子树
后根遍历
按照从左到右的顺序后根遍历根结点的每一棵子树，访问根结点
层次遍历
过程是从根结点开始按从上到下、从左到右的顺序访问树中的每一个结点
树的存储结构
双亲存储结构
是一种顺序存储结构，用一组连续存储空间存储树的所有结点，同时在每个结点中附设一个伪指针指示其双亲结点的位置(除了根结点的以外，每个结点只有唯一的双亲结点，将根结点的双亲结点位置设置为特殊值-1)
孩子链存储结构
每个结点不仅包含结点值，还包括指向所有孩子结点的指针 优点：查找某结点的孩子结点十分方便 缺点：查找某节点的双亲结点比较费时，另外，树的度较大时存在较多的空指针域
孩子兄弟链存储结构
为每个结点设计3个域，即一个数据元素域、一个指向该结点的左边第一个孩子结点的指针域、一个指向该结点的下一个兄弟结点的指针域。 优点：可方便地实现树和二叉树的相互转换 缺点：和孩子链存储结构的缺点一样，从当前结点查找双亲结点较为麻烦，需要从树的根结点开始逐个结点比较查找。
二叉树的概念和性质
二叉树的定义
二叉树是一个有限的结点集合，这个集合或者为空，或者由一个根结点和两棵互不相交的称为左子树和右子树的二叉树组成。
度为2的树中至少有一个结点的度为2，而二叉树没有这种要求 度为2的树不区分左、右子树，而二叉树是严格区分左右子树的
满二叉树
在一棵二叉树中，如果所有分支结点都有左孩子结点和右孩子结点，并且叶子结点都集中在二叉树的最下一层，这样的二叉树称为满二叉树。
非空满二叉树
叶子结点都在最下一层 只有度为0和度为2的结点
完全二叉树
若二叉树中最多只有最下面两层的结点的度数可以小于2，并且最下面一层的叶子结点都依次排列在该层最左边的位置上，则这样的二叉树称为完全二叉树。
非空完全二叉树
叶子结点只可能在最下面两层中出现 对于最大层次中的叶子结点，都依次排列在该层最左边的位置上 如果有度为1的结点，只可能有一个，且该结点只有左孩子而无右孩子 按层序编号时，一旦出现编号为i的结点是叶子结点或只有左孩子，则编号大于i的结点均为叶子结点 当结点总数n为奇数时，n1=0，当结点总数为偶数时，n1=1
二叉树的表示方法
树形表示法
文氏图表示法
凹入表示法
条形表示法
二叉树的性质
非空二叉树上的叶子结点数等于双分支结点数加1
非空二叉树的第i层上最多有2的i-1次方个结点(i>=1)
高度为h的二叉树最多有2的h次方-1个结点(h>=1)
二叉树与树、森林之间的转换
森林、树转换为二叉树
树中所有相邻兄弟之间加一条连线
对树中的每个结点只保留它与长子之间的连线，删除与其他孩子之间的连线
以树的根结点为轴心，将整棵树顺时针转动45°，使之结构层次分明
二叉树还原为树/森林
树转换成二叉树的还原
若某结点是其双亲的左孩子，则把该结点的右孩子、右孩子的右孩子等都与该结点的双亲结点用连线连起来
删除原二叉树中所有双亲结点与右孩子结点之间的连线
整理由前两步得到的树，以根结点为轴心，逆时针转动 45°，使之结构层次分明
实际上，二叉树的还原就是将二叉树中的左分支保持不变，将二叉树中的右分支还原成兄弟关系。
森林转换成二叉树的还原
抹掉二叉树根结点右链上的所有结点之间的“双亲--右孩子”关系，将其分成若干个以右链上的结点为根结点的二叉树，设这些二叉树为bt1、bt2、……btm。
分别将bt1、bt2、……btm各自还原成一棵树
二叉树的存储结构
二叉树的顺序存储结构
二叉树的顺序存储结构是用一组地址连续的存储单元来存放二叉树的数据元素，因此必须确定好树中各数据元素的存放次序，使得各数据元素在这个存放次序中的相互位置能反映出数据元素之间的逻辑关系。
二叉树的链式存储结构
二叉树的链式存储结构是指用一个链表来存储一棵二叉树，二叉树中的每一个结点用链表中的一个结点来存储。
data表示值域，用于存储对应的数据元素，lchild和rchild分别表示左指针域和右指针域，分别用于存储左孩子结点和右孩子结点的存储地址。这种链式存储结构通常简称为二叉链
二叉树的基本运算及其实现
创建二叉树CreateBTree(b,str)
销毁二叉树DestroyBTree(&b)
查找结点FindNode(b,x)
找孩子结点LchildNode(p)和RchildNode(p)
求高度BTHeight(b)
输出二叉树DispBTree(b)
二叉树的遍历
先序遍历
中序遍历
后序遍历
层次遍历
层次遍历不同于前三种，它是非递归的，用于一层一层的访问二叉树中的所有结点
二叉树的构造
任何n(n>=0)个不同节点的二叉树,都可由它的中序序列和先序序列唯一地确定
任何n(n>0)个不同节点的二叉树，都可由它的中序序列和后序序列唯一地确定
线索二叉树
规定是当某结点的做指针为空时，令该指针指向这个线性序列中该结点的前驱结点；当某结点的右指针为空时，令该指针指向这个线性序列中该结点的后继结点，这样的指向该线性序列中的“前驱结点”和“后继结点”的指针称为线索。
创建线索的过程称为线索化。线索化的二叉树称为线索二叉树。
一般分类有先序线索二叉树、中序线索二叉树、后序线索二叉树。
创建线索二叉树的目的是提高该遍历过程的效率。
哈夫曼树
概述
带权路径长度
将树中的结点赋予一个某种意义的数值，称此数值为该结点的权。从根结点到该结点之间的路径长度与该结点上权的乘积称为结点的带权路径长度(Weighted Path Length,WPL)。树中所有叶子结点的带权路径长度之和称为该树的带权路径长度。
哈夫曼树 (最优二叉树)
在n0个带权叶子结点构成的所有二叉树中，带权路径长度WPL最小的二叉树称为哈夫曼树(Huffman tree)或最优二叉树。
哈夫曼编码
在数据通信中，将传送的文字转换成二进制字符0和1组成的二进制字符串，称这个过程为编码。哈夫曼树可用于构造使电文编码的代码长度最短的编码方案。
设需要编码的字符集合为{d1,d2,···,dn}，各个字符在电文中出现的次数集合为{w1,w2,···,wn}，以d1,d2,···,dn作为叶子结点，以w1,w2,···,wn作为各根结点到每个叶子结点的权值构造一棵哈夫曼树，规定哈夫曼树中的左分支为0、右分支为1，则从根结点到每个叶子结点所经过的分支对应的0和1组成的序列便是该结点对应字符的编码。这样的编码称为哈夫曼编码。
哈夫曼编码的实质就是使用频率越高的字符采用越短的编码。
用并查集求解等价问题
当给出两个元素的一个无序对(a,b)时，需要快速"合并"a和b分别所在的集合，这期间需要反复"查找"某元素所在的集合。“并”、“查”和“集”由此而来。在这种数据类型中，n个不同的元素被分为若干组。每组是一个集合，这种集合叫分离集合，称之为并查集。
数组和广义表
数组
数组的基本概念
数组是具有相同类型的数据元素的有限序列，可以将它看作是线性表的推广。
二维数组及多维数组
一个二维数组可以看作是每个数据元素都是相同类型的一维数组的一维数组。以此类推，任何多维数组都可以看作一个线性表，线性表中的每个数据元素也是一个线性表。
数组的操作
数组除了初始化和销毁外，通常只有两种操作 读操作：给定一组下标，读取相应的数据元素。 写操作：给定一组下标，存储或者修改相应的数据元素。
数组数据类型的性质
数据中的数据元素数目固定，一旦定义了一个数组，其数据元素的数目不再有增减的变化。
数组中的数据元素具有相同的数据类型。
数组中的每个数据元素都和一组唯一的下标对应。
数组是一种随机存储结构，可以随机存取数组中的任意数据元素。
数组的存储结构
设计数组的存储结构时，通常将数组的所有元素存储到存储器的一块地址连续的内存单元中，即数组特别适合采用顺序存储结构来存储。
特殊矩阵的压缩存储
对称矩阵
若一个n阶方阵A[n][n]中的元素满足ai,j=aj,i(0<=i,j<=n-1)，则称其为n阶对称矩阵
对称矩阵的元素是按主对角线对称的，即上三角部分和下三角部分中的对应元素相等，因此在存储时可以只存储主对角线加上三角部分的元素，或者主对角线加下三角部分的元素，让对称的两个元素共享一个存储空间。
上三角矩阵
是指矩阵的下三角部分中的元素均为常数c的n阶
下三角矩阵
是指矩阵的上三角部分中的元素均为常数c的n阶方阵
对角矩阵
若一个n阶方阵A满足其所有非零元素都集中在以主对角线为中心的带状区域中，则称其为对角矩阵。
稀疏矩阵
概述
当一个阶数较大的矩阵中的非零元素个数s相对于矩阵元素的总个数t非常小时，即s<<t时，称该矩阵为稀疏矩阵。
稀疏矩阵和特殊矩阵的明显差异：特殊矩阵中特殊元素的分布具有某种规律，而稀疏矩阵中特殊元素(非零元素)的分布没有规律，即具有随机性。
稀疏矩阵的三元组表示
不同于特殊矩阵的压缩存储方法，稀疏矩阵的压缩存储方法是只存储非零元素。由于稀疏矩阵中非零元素的分布没有任何规律，所以在存储非零元素时必须同时存储该非零元素对应的行下标、列下标和元素值。这样稀疏矩阵中的每一个非零元素由一个三元组(i,j,ai,j)唯一确定，稀疏矩阵中的所有非零元素构成三元组线性表。
若把稀疏矩阵三元组线性表按照顺序存储结构存储，则称为稀疏矩阵的三元组顺序表，简称为三元组表。
稀疏矩阵的十字链表表示
对于稀疏矩阵中的每个非零元素创建一个结点存放它，包含元素的行号、列号和元素值。
将同一行的所有结点构成一个带头结点的循环单链表，行号为i的单链表的头结点为hr[i]。
将同一列的所有结点构成一个带头结点的循环单链表，列号为j的单链表的头结点为hd[j]。
再将所有头结点h[i](0<=i<=3)连起来构成一个带头结点的循环单链表，这样需要增加一个总头结点hm，总头结点中存放稀疏矩阵的行数和列数等信息。
广义表
广义表的定义
广义表是线性表的推广，是有限个元素的序列，其逻辑结构采用括号表示法表示如下：GL=(a1,a2,···,ai,···,an)，其中n表示广义表的长度，即广义表中所含元素的个数，n>=0。若n=0，称为空表。ai为广义表的第i个元素，如果ai属于原子类型，称为广义表GL的原子；如果ai又是一个广义表，称为广义表GL的子表。
广义表的存储结构
广义表是一种递归的数据结构，因此很难为每个广义表分配固定大小的存储空间，所以其存储结构只好采用链式存储结构。
广义表有两类结点，一类为圆圈结点，对应子表，另一类为方形结点，在这里对应原子。