数据结构笔记总结_数据结构遵从率

目录

数据结构的四种基本逻辑

线性表

栈的顺序存储实现

一维数组单方向堆栈

另一种堆栈方式

表达式在程序中的存储

广义表

树的初识

树的一些基本定义

树的表示

一些特殊的二叉树

树的遍历

二叉树的遍历（非递归）

搜索二叉树

调整方法

哈夫曼树

哈夫曼编码特点

集合

集合的表示

具体如何存储呢

查找某个元素所在的集合

集合的并运算

图

邻接矩阵

图的遍历

---

分类1：线性结构与 非线性结构

线性结构：链表，队列，对，堆栈...

非线性结构：树，图

---

---

分类2：四种基本逻辑结构

首先，有一类共性问题：有线性序列的组织和管理，我们用线性表来存储线性结构数据

线性表的关键信息：

主要含有

数据对象集：n个元素构成的有序序列

操作集：假设 线性表L属于list类型，i表示位置，元素属于数据类型elementtype。

对表的主要操作：

一、线性表的存储实现（利用数组）

思路：定义一个结构体指针，自定义数据类型。内部元素有数组和一个末尾元素的地址。（这就跟上面的衔接起来，这跟链表的节点好像）那个数组是用来存储个数组。

（1）入栈：检验知否堆栈满，如果没满就把元素堆入栈，top值+1。

（2）出栈：检验是否堆栈空，如果没空，就将元素出栈，top值-1。

一维数组从两头分别堆栈。这里用一个tag来区分top1和top2，即赋予tag值1或2。但是这个tag只是用来让人识别的，对数组并没有实际上的作用。

（1）入栈：先判断堆栈满了没。如果没满，要往第一个堆栈里添加元素，就top1++。要往第二个堆栈添加元素就top2--。

（2）出栈： 先判断是否空栈。再分别进行操作。

我们常见的表达式一般是中缀表达式，儿在程序中一般转换为后缀表达式进行存储。

如何把中缀表达式转换为后缀表达式： 数字读下来，遇到运算符号就存储在堆栈中，每一次比较堆栈中运算符的优先级，读入整个表达式之后按运算级最高的进行计算。

不同部分转换方式：

注意：

广义表

• 广义表是线性表的推广
• 对于线性表而言，n个元素都是基本的氮元素
• 广义表中，这些元素不急可以是单元素也可以是另一个广义表。

如图，这是广义表的形象图

树的初识

树：n（n>=0）个节点构成的有限集合；当n=0时称为空树；树有一个称为“根”的特殊节点，其余节点可以分为m个互不相交的有限集，其中每一个集合本身又是一棵树，称为原来的“子树”。

树的一些基本定义

• 节点的度：节点的子树个数
• 树的度：树的所有节点中最大的度数
• 叶节点：度为0的节点
• 父节点：有子树的节点是其子树的根节点的父节点
• 兄弟节点：具有统一父节点的节点彼此称为兄弟节点。
• 路径和路径长度：路径所包含边的个数。
• 祖先节点：沿着树根到某一节点路径上的所有节点都是这个节点的祖先节点。
• 树的深度：树中所有节点最大层次是这颗树的深度。

树的表示

二叉树：一个节点有三个东西，一个内容，两个指针。

一些特殊的二叉树

• 斜二叉树（相当于链表，只有左/右支）

• 完美二叉树（满二叉树）：每个节点的子节点都满2

• 完全二叉树：每一行从左往右没有空的，但是不一定是完美二叉树。（如下图1是2不是)

树的遍历

一般有四种方法：

先序遍历：根 - 左子树 - 右子树

中序遍历：左子树 - 根 - 右子树

后序遍历：左子树 - 右子树 - 根

层序遍历：从上到下，从左到右

先序遍历

利用一种递归的思想实现遍历

• 先检验是否为空（即BT）

• 然后访问左侧，再访问右侧

先序遍历过程图解

中序遍历

中序遍历过程图解

后序遍历

后序遍历过程图解

遍历总结

所有遍历方法都是使用递归的方法

只有先序遍历是从上往下的，其他遍历方法都是从下往上的

如图，×代表先序遍历路径，⭐代表中序遍历，▲代表后序遍历。

二叉树的遍历（非递归）

递归的是指其实还是用堆栈，每一次把数据存储在堆栈中，等判断条件达到终止之后再倒着输出。这样一来，如果需要处理的数据非常庞大，仍然存在空间占用过大的问题，就像前面讲的一样，递归虽然是个效率高的方法，但是存储空间消耗很大，就像飞机一样，虽然速度快但是代价昂贵，而且每次运输数量有限。

中序遍历

1. 遇到一个节点把这个节点压栈，然后沿着这个节点便利左支。

2. 左支遍历结束之后从栈顶弹出这个节点病情访问他。

3. 再按照这个方法遍历右支。

层序遍历

大概原理：（必须遵从这个）

1. 非空左子树的所有值小于根节点值

2. 非空右子树的所有值大于根节点值

3. 左右子树都是二叉搜索树

搜索二叉树

搜索效率可以通过计算平均查找长度（ASL）来判断，其中完全二叉搜索树查找效率最搞，斜二叉树查找效率最低。

（ASL计算方法：就是查找每个元素需要遍历的长度相加，除以结点个数。）

为了提高二叉树查找效率，需要平衡二叉树。

（平衡二叉树（AVL树）：平衡因子=|左子树高度-右子树高度|）

调整方法

1.

2.

 调整模式主要有四种：rr，ll，rl，lr。（right，left）

一个核心方法就是找到破患者和被破坏这区域附近的大约3个结点（这三个节点的asl指数都不是0），把asl数剧中的系欸但作为根，把asl小的放左侧，大的放右侧。

概述/引入

又名最优二叉树，树的总路径长度最短

可以说是从堆引入的。堆的作用是构造最大堆和最小堆实现挑选最值删除的东西。

原理：出现频率较高的数占空间小，出现频率较低的数占空间更大。从而实现不压缩数据且节省空间的一种存储方式。

哈夫曼树

引：堆的构造是在所有数字中挑选两个最大/最小的数字合并，再继续挑选继续合并。而哈夫曼树是在数据中挑选两个出现频率最低的数进行合并。

1. 在数据中挑选两个出现频率最低的数进行合并

2. 接着选频率最低的数和上一个父结点进行合并得到新的父结点（父结点的值是两个子结点的和）

3. 一直合并完成所有元素

4. 所有元素必须是叶子结点，保证没有歧义（二义性）

5. 这棵哈夫曼树左侧路径都标0，右侧都标1

哈夫曼编码特点

字符只在叶结点上。（作用是避免二义性。保证每一个参数都没有后缀只有前缀（路径上的数就代表前/后缀)

左支是0，右支是1

如此一来，路径所组成的数就是该字符对应的编码。

1. 在数据中挑选两个出现频率最低的数进行合并

2. 注意我们需要的字符都放在叶结点上。

 这样编码可以很大几率让频率高的字符编码更短。

计算路径长度

要想计算最优二叉树中某个结点权重的路径长度，方法是每个叶子结点的（该结点权重*到根节点路径数量）相加总和。因为哈夫曼树我们认为叶子结点的值本身就是一种频率，所以结点值就是权重，所以哈夫曼树总路径长度一般是每个（叶子结点值*到根节点长度）相加总和。

因哈夫曼树构建方法就是从第频率到高频率进行合并，所以最长的路径总是对应最低的频率，得到的总路径长度总是最短的，也就是最优的。

集合

并查集：“并”把两个集合并在一起；“查”查某个元素属于哪个集合。

具体作用：现在有很多个集合，每个集合又有很多个元素。我们想查一个元素，需要找这个元素在哪个集合的什么位置，或者想把两个集合合并为一个集合。

（该图只是形象的比喻一下，真正的存储方式并不是这样）

子结点指向父结点，这种方法与二叉树有所不同，这个叫做双亲表示法。

我们把一个集合看作一个树状结构，一个根节点何以被大于两个元素指向，根节点和叶结点都是集合中的元素。

这个并查集存储的就是各个集合的根节点的指针。

集合的表示

每个元素可以用一个结构体类型数组进行表示。

每个结构体内有两个东西：数据域；整型数字（这个元素的父节点在数组中的位置，相当于指针）

具体如何存储呢

data是元素内容；parent是每个元素对应的集合的根节点（如果该元素本身就是根节点，其根节点就用-1表示）；下标是各个元素的标签（就是数组下标），因为元素不一定是数字，我们经常用元素下标来查找对应内容。

某几个数组下标代表的元素是根节点，这些根节点的根节点值是-1。而非根节点的元素的根节点值是对应根节点的数组下标。

查找某个元素所在的集合

（每个元素都有一个数组下标，根节点本身也拥有一个数组下标。）

1. 第一遍循环，按照数组下标挨个寻找对应的元素。如果找到了就退出循环并返回数组下标，如果没找到就返回-1（结束这个函数）。

2. 第二次循环，判断条件是相应数组下标的根节点值是否大于0，如果大于0，就让数组下标等于这个根节点值，这个根节点值代表的就是其根节点的数组下标。

集合的并运算

干啥的：告诉你两个元素，你要把这两个元素对应的集合并起来。

程序框架：找到两个元素各自的根节点；判断根节点是否相等；如果相等就不管；如果不相等就把其中一个根节点并入另一个根节点（把一个根节点的parent值改成另一个根节点对应的数组下标数）

这样一来“树”会长高一层，随着合并的进行，这个数可能会越来越高。为了尽可能提高效率，我们尽量把小的集合并入大的集合中。

这样一来，还要判断需合并的两个集合的大小。

为了记录集合中元素个数，我们可以使用一个非常巧妙的方法，把根节点parent值记为其中元素个数的负数。

图

一些基本概念

• 无向图/有向图：即途中路径是否有方向。

• 网络：图的路径上有数字，这些数字称为权重。当图上由权重的时候就叫做网络。

• 顶点集和边集，一般由二元组表示，和离散一样，但是这里的图不考虑自回路和平行边。

• 稀疏图：点多边少，矩阵中有大量的0

• 路径：两点之间结点的集合。路径长度就是路径中边的数量（如果是网络就是所有路上的权重之和）。

• 简单路径：两点之间路径上所有顶点都不同。

• 回路：起点等于终点的路径。

• 连通图：图中任意两点均连通

• 连通分量：无向图的极大连通子图

• 强连通：有向图中顶点v和w之间存在双向路径，则称v和w是强连通。

不一定是平行边（事实上程序中不存在平行边），可以通过不同路径，如下图A可以到B，B可以到A

图在程序中表示(邻接矩阵，邻接表）

使用二维数组，两个下标初始化都是结点数-1，接着用两个下标分别表示两个顶点，如果两顶点之间由边则赋值为1，无边则赋值为0。

（假如有9个结点）

邻接矩阵

阐述：邻接矩阵是图的一种存储方式，一般用数组进行存储。有向图一般用二维数组，无向图可以用一维数组。

特点：

1. 左上到右下的数字全是0，因为不允许自回路。

2. 以上面那个对角线为对称轴，如果是无向图，其两侧情况一致，因为两节点之间肯定是情况一致的。这样一来就发现矩阵有一般空间都浪费了，下方进行优化

无向图优化

用一维数组存储。

直接在红色框里从第一行从左到右存储，数组下标是序号，数组值是0/1。

这个方法虽然节省了空间，但是让寻找哪两个点变难了，没办法嘛。

如果是网络的话，把数组值定义为权重就行了。

邻接表

阐述：是图的一种存储方式，利用链表实现。用邻接矩阵存储稀疏图会造成空间浪费，链表的方式解决了这个弊端。

其实不止这两种表示图的方式，用什么方式取决于要解决什么问题。

图的遍历

主要有两种方法：

深度优先搜索DFS，广度优先搜索BFS

深度优先搜索：在一个结点处，望向所有边，优先前往未经过的结点。如果所有邻接点都经过了，就优先原路返回，不会直接去出口。一直返回，指导退回入口。 

这个程序很像堆栈。使用递归的方式点亮邻接点，如果这样一来，经过的结点就会按照顺序被压入，如果没有为点亮的邻接点就返回（弹出）上一个。

广度优先搜索BFS：类似于队列的方式实现。把一个起始结点压入队列，弹出这个起始结点，压入这个起始节点的所有邻接点，再挨个弹出这些邻接点，暗处每个邻接点的时候，压入这个邻接点的邻接点（已经压入过队列的不再重复压入），直到压入过所有结点。（下图是伪码描述）

*Enqueue入队

*V算是起始结点的载体，后面会被赋值为弹出结点

*Dequeue出队

*Q队列