数据结构总结

1. 关于算法

(1) 什么是算法?
算法：顾名思义，一种计算的方法，在程序设计上，就表现为一组指令序列。

(2）算法与程序有什么区别和联系?
程序是指用某种计算机语言对一个算法的具体实现，即具体要怎么做，
算法偏重于对解决问题的方法的描述，即要做什么。

(3）如何评价算法的优劣?
时间复杂度与空间复杂度

一个算法应该具有以下五个重要的特征：

有穷性（Finiteness）
算法的有穷性是指算法必须能在执行有限个步骤之后终止；

确切性(Definiteness)
算法的每一步骤必须有确切的定义；

输入项(Input)
一个算法有0个或多个输入，以刻画运算对象的初始情况，所谓0个输入是指算法本身定出了初始条件；

输出项(Output)
一个算法有一个或多个输出，以反映对输入数据加工后的结果。没有输出的算法是毫无意义的；

可行性(Effectiveness)

2. 栈的特性是什么

栈的特点是先进后出表。栈是一种只能在一端进行插入和删除操作的特殊线性表。它按照先进后出的原则存储数据，先进入的数据被压入栈底，最后的数据在栈顶，需要读数据的时候从栈顶开始弹出数据。


3. 稀疏矩阵
0 0 3 0 0 0
1 0 0 0 0 6
0 0 4 0 0 0
0 2 0 0 5 0
0 0 0 0 0 0
(1) 写出该稀疏矩阵的三元组顺序表(行优先)存储表示。
(2) 简要叙述将稀疏矩阵进行转置的算法思想，并给出转置结果。

行优先的表现形式: (行，列，数值)
（(1,3,3),(2,1,1),(2,6,6),(3,3,4),(4,2,2),(4,5,5)）

进行行转置的方法有：
方法1（简单，但是无序）：直接将行和列的值互换
方法2（最后有序，还是按照行优先显示）：

1. 遍历三元组顺序表，找列为1的值，执行行列互换 ；
2. 依次重复1的操作，直到所有列都互换

4. 哈夫曼树、哈夫曼编码
假定电文字符集为{A,B,C,D,E,F,G,H),它们在电文中出现的次数分别为{20,7,13,6,39,4,14,5},请为这8个字符设计哈夫曼编码。画出哈夫曼树并给出编码。要求在构造哈夫曼树的过程中，其中权值较小结点放在左侧，编码时左分支生成代码0，右分支生成代码1
(术语： 路径 、 路径长度、权重 、wpl : 【路径长度 * 权重】 的总和 )

（画图方法：将最小的两个数进行连接，连接的和又放入比较的数中;  注： 左小右大）


哈夫曼编码：根据画的图写出编码；（左0右1）

wpl : 路径长度*权重  相加之和
如： wpl = (20+39) *2 + (13+14)*3 + (4+5+6+7) * 4

5. 哈希函数

对关键字集合{1,19,10,23,11, 84,14,27,20}，哈希地址空间为HT[O0 ..14]，若采用除留余数法构造哈希函数和线性探测再散列方法处理冲突，试画出最后得到的哈希表，并计算在等概率情况下查找成功时的平均查找长度ASL。

(1)写出用除留余数法构造的哈希函数。
( 函数 ： H（key）=key  MOD  p , p<=m   （最简单，最常用）p的选取很重要
一般情况，p可以选取为小于或等于空间长度的最大质数）)
H(key) = key  mod 13

(2）采用线性探测再散列处理冲突，试画出最后得到的哈希表。
1 mod 13 = 1       23 mod 13 = 10     14 mod 13 = 1
19 mod 13 = 6     11 mod 13 = 11     27 mod 13 = 1
10 mod 13 = 10    84 mod 13 = 6    20 mod 13 = 7

下标	0	1	2	...
数值		1	14
查找长度		1	2

(3）计算在等概率情况下该哈希表在查找成功时的平均查找长度ASL。ASL =  (1+2+3+1+2+2+1+2+2) / 9

6.二叉排序树
依次读入给定的整数序列{6,15,5,7,19,8,5,17,4},完成下列操作:

(1）构造该二叉排序树; (以第一个数为根，比根结点小的放在左边，比根结点大的放在右边)

(2）计算在等概率情况下该二叉排序树的平均查找长度ASL。
（第一层的一次，第二层的两次，依次累推）ASL =  (1+(2*2) +  (3*3) + (4*2) ) / 9 =


7. 最小生成树

克鲁斯卡尔算法(Kruskal算法):
1. 对边进行排序（升序）
2. 不同连通分量上的顶点进行连接



普界姆Prim算法方法:
1. 选择任何一顶点，做为起始点
2. 找与顶点相连接的最小权的边，注:不形成回路的边
3. 重复1、2步骤，直到所有顶点相连，即边为n-1为止


注意事项：

构成生成树的准则有三条:
<1> 必须只使用该网络中的边来构造最小生成树。
<2>必须使用且仅使用n-1条边来连接网络中的n个顶点
<3>不能使用产生回路的边。

8. 线索二叉树

建立线索的规律如下：
1、若当前访问的结点的左指针域为空，则左指针域指向prior指的结点，同时置lbit为0，否则，置lbit为1；
2、若prior所指结点的右指针域为空，则右指针域指向当前访问的结点，同时置rbit为0，否则，置rbit为1；
3、遍历结束时，将prior->rchild指向头结点，并置prior->rbit为0。


（画线索二叉树时，会告诉你是先序线索二叉树，中序线索二叉树，后序线索二叉树；当结点无左孩子时，将其指向它前面的结点，而结点的顺序是指先序或中序或后序的顺序。无右孩子时，指向序列后面的结点）

9. 平衡二叉树

定义：任意结点的左、右子树高度差的绝对值不超过1，将这样的二叉树称为平衡二叉树，简称平衡树（AVL树）。
  定义结点左子树与右子树的高度差为该结点的平衡因子，则平衡二叉树节点的平衡因子的值只可能是-1，0，1


判断是否为大顶堆的方法（参考：https://www.bilibili.com/video/BV1RL4y1e72q）
（看前面的数字是否大于后台两个数字，依次进行判断 - 相当于转成对应二叉树，再来比较）


10. Dijkstra 最短路径

列出起点， 终点，path , dist 距离起点：根据题的要求为0
终点为1,2,3,4;path 表示，从那个点到的终点
dist 表示距离起点到终点有路径就写对应的值，没有就写-1，其它在找距离中最小的点，加入到起点集合中，判断此到其它点的路径，如果小于就一次写的路径，就对路径与距离进行替换

11. 判断有向图是否有环

判断方法：
拓扑排序： 还有顶点末输出，但已经不存在没有前驱的顶点了
深搜：从一个顶点出发存在搜回到自己的路径

12. 拓扑序列
1、从AOV网中选择一个没有前驱的顶点并且输出
2、从AOV网中删除去该顶，并且删除所有以该顶点为尾的弧
2、重复所有操作，直到所有顶点全部输出 ，或AOV网中不存在没有前驱的顶点

若此时输出的顶数小于有向图的顶点数，则说明有向图中存在回路
对一个有向图构造拓扑序列的过程，称为拓扑排序


13. 图的深度遍历DFS与广度遍历BFS

DFS：
1、遍历过的节点不重复遍历（根据邻接表）
2、回溯



BFS:进入一个元素，出队，然后，将出队的这个元素后面的节点，添加再队列后面
判断是否为AOV,什么意思，判断的条件是什么注：不要重复，重复的不要入队




14. 森林与二叉树的转换

森林转二叉树的方法
a. 将森林中所有的普通树各自转化为二叉树
b. 森林中第一棵树的树根作为整个森林的树根，其他树的根节点看作是第一棵树根节点的兄弟节点，采用孩子兄弟表示法将所有树进行连接
树或森林与二叉树之间有一个自然的一一对应关系。任何一个森林或一棵树可惟一地对应到一棵二叉树；反之，任何一棵二叉树也能惟一地对应到一个森林或一棵树。

将树转换为二叉树：
树中每个结点最多只有一个最左边的孩子(长子)和一个右邻的兄弟。按照这种关系很自然地就能将树转换成相应的二叉树：
1.在所有兄弟结点之间加一连线
2.对每个结点，除了保留与其长子的连线外，去掉该结点与其它孩子的连线