数据结构与算法总结
1.抽象数据类型(ADT)
1. 表
表是存储一类数据的一个简单数据类型.表的实现有两种:数组实现以及链表实现.
(1) 以数组实现的表,该表创建时被赋予固定的大小,当表满时,自动重新分配大小.这种表的问题有3个:1.数组初始大小如何评估 2.总是会浪费空间,因为只有当数组满才会不浪
费空间.而这种情况实际上是不会有太多的存在时间,如果为了空间浪费减小则缩小分配的空间,那么在插入数据时会频繁的重新分配大小.造成效率低下,同时这种表需要大量
的连续的空间3.这种表的查找速度花费常数级别,但是删除和插入操作则隐藏着昂贵的开销.在对表进行插入删除炒作时,在操作的位置之后的元素都要向前或向后移动一个位
置,这就隐藏的巨大的开销,最坏的情况是O(N).平均来看,两种操作都需要移动表一般的元素.优点是查询快速.
(2) 以链表实现的表,该表在内存中是散乱排列的,可以利用内存的一些零散空间.有效利用内存.但是这种表依然有问题:1.查询速度过慢.如果想要查询表中的元素.每次都需要从
开始节点查询(单链表).当表的大小过大时,这将是非常昂贵的开销.优点是插入和删除操作开销不大,只需要在指定的节点接入一个新节点然后与后续节点连接上即可.
2. 栈
栈是限制插入和删除只能在一个位置上及逆行的表,该位置是表的末端,叫做栈顶.栈的基本操作有push(入栈),pop(出栈).对应表的插入和删除.由于栈的操作都是在栈顶,所以数
组实现与链表实现一般来说都是合理的选择.
3. 队列
对列是插入在一段进行,而插入在另一端进行的表.队列基本操作是入队和出队.入队是在表的末端(队尾rear)插入一个元素,出队是在表的开头(队首front)删除一个元素.同样数
组和链表一般来说都是合理来的实现.
2. 树
- 树的遍历
树的遍历分为先序遍历,中序遍历,后续遍历.三种遍历方法的区别在于先序遍历是先遍历当前节点的值然后遍历左子树,右子树;中序遍历是先遍历左子树的值,然后遍历当前节
点,右子树;后序遍历是先遍历左子树,右子树,然后是当前节点.树的遍历一般以递归的方式实现.
- 二叉树
二叉树是每个节点都不能有多于两个儿子节点的树,二叉树的一个性质是一科平均二叉树的深度要比节点个数N要下的多.二叉树在有许多应用,比如表达式树(P76),二叉查找树
(P78)等.这里详细介绍二叉查找树
3. 二叉查找树
二叉查找树是二叉树的一种,但是他具有一个性质:对于书中的每个节点X,他的左子树中所有项的值都要小于X的值,右子树中所有项的值要大于X.二叉查找树一般情况下的平均
深度是O(log N).二叉查找树在查找元素时实现方式简单,效率较高,其构建方式也简单.例如findMin操作,只需要一直查询节点的左子树即可.但是二叉查找树仍有一定的问题.当我们
往一颗空树插入元素时,元素的顺序为100,99,98.....0.这种序列构建出来的树的所有节点只有左子树,呈线性排列,也就是说这种树的效率跟链表相同.这只是一种极端现象,但是在实
际应用在仍需要注意.
二叉树详细构建代码详见书P78.
4. AVL树
为了解决上面提到的二叉查找树变成一个线性排列的情况,出现了AVL树,AVL树是带有平衡条件的二叉查找树.苛刻的平衡条件为每个节点都必须由相同高度的左子树和右子树,
空子树的高度定义为-1.这种条件保证了树的深度最小,查找效率也高,但是条件太苛刻.所以一般采用另一种平衡条件是每个节点的左右子树的高度最多差1,空子树的高度定义为-1.
实现这种平衡条件的方法是旋转,详情见书P86.代码见AVLTree项目.
3. 优先队列(堆)
1. 二叉堆
二叉堆具有两个性质:结构性和堆序性.结构性质是:堆是一颗完全二叉树.如果将二叉堆的每一个元素从下标为1的位置开始放入数组中,那么会得到一个结论,第i个元素的左儿
子得下标是2i,右儿子的下标是2i+1.堆序性质是任意节点都应该小于他的后裔.下面介绍堆的两个基本操作:
(1) 删除最小元素:由于堆的堆序性质,所以删除最小元素即直接删除根节点.由于结构性质,将调整最后一个节点A的位置,然后在堆中寻找合适位置.在根节点处建立一个空穴,往
小的儿子节点的方向下虑,直到找到一个位置儿子节点的值大于A节点的值或者空穴下虑到了堆的最下层,然后想节点A放在空穴的位置,这种操作成为下滤操作,见书P160.
(2) 插入操作:为插入一个节点A,我们在下一个可用位置创建一个空穴,如果父节点大于要A的值,则将空穴上滤,直到一个为的父节点小于A的值,则将节点A放在空穴的位置.
代码详情见BinaryHeap项目,书P157
4. 排序
- 插入排序
插入排序是在一个已经有序的序列中,插入一个数,要求插入一个数之后依然保持有序使用的一种排序方法.对于一个待排序列,可将其第一个数当做一个有序序列,然后依次向
有序序列中插入待排序列中的数据.插入排序的时间复杂度为O(N^2),由于待排的数据都跟有序序列中最大数据比较,如果满足条件就将数据插入,相等元素前后顺序没变,是稳定的
排序
2. 希尔排序
希尔排序又叫缩小增量排序,给定一个增量序列H1,H2....Hn.第一趟使用增量H1,对待排序列中的第0项,第0+H1项,第0+2H1项....进行排序,第二趟使用H2进行排序,依次类推.
增量序列的一个流行(但是不好)的选择是使用shell建议的序列Hn=(2Hn-1)和Hn=N/2(N为待排序列长度),希尔排序的性能跟增量序列密切相关.希尔排序实际是多个其他排序方法的集
合,他通过增量缩小排序序列,将序列的有序程度逐渐提高,使排序的效率增加,实际将序列排序的是使用的其他排序方法.希尔排序的平均时间复杂度为O(n^1.3),希尔排序是不稳定
的
3. 堆排序
堆排序是使用堆的堆序性质进行的排序.首先将待排序列构建成一个大顶堆堆(小顶堆也可以,具体看要求),然后通过deleteMax操作,将删除的节点放在堆的最后面(该位置已经
不存在),然后堆的大小-1,堆的元素删除完之后,最后会得到相应的有序序列.堆排序的平均时间复杂度是O(N*log N),不稳定.
4. 归并排序
归并排序是将待排序列分为两个数组,分别对两个数组进行排序,然后将排序后的数组,依次按照顺序放入结果数组中,如果有一个数组的元素用完,则将另一个数组的剩下的元
素放入结果数组中.归并排序精妙的使用了递归方法.归并排序也是分治算法的一个典型应用.归并排序的时间复杂度为O(n*log N),稳定的.
5. 快速排序
快速排序的基本做法是在待排序列中选取一个枢纽元,将大于枢纽元的元素放于一个数组,小于枢纽元的元素放于一个数组(相等的随便放在哪里),也可为了节约空间,将大于枢
纽元的元素放于枢纽元的一侧,另一侧放小于枢纽元的元素.然后对两个数组进行排序,快排可用递归实现,也可以不使用.对于枢纽元的选择,不要盲目的直接选取待排序列的第一个
元素,如果待排序列是一个逆序的,那么这次排序的效率是及其低下的.一个安全的做法是使用随机寻找一个枢纽元,但是生成随机数的开销一般是很大的.所以我们这里采用的时候
三数中值分割法,选取序列首尾以及中间三个元素,然后选取其中第2大的元素作为枢纽元.快排的时间平均时间复杂度为O(N*long N),不稳定.
排序的所有代码在sort项目中,在书的P186.
5.图
1.拓扑排序
拓扑排序是对有向无圈图的顶点的一种排序.是从一个点遍历其他点的路径.一个简单的拓扑排序算法是先找出任意一个没有入度的顶点,然后删除该顶点及其边,并输出该点,
然后重复以上操作,知道所有顶点被删除完.
拓扑排序可用来判断有向图是否有环,因为如果有环的话,用上述方法执行要某种程度,剩下的图种没有入度为0的点,最后得不到结果.
拓扑排序效率低下,因为每次都需要遍历所有顶点.为了解决该问题,我们采用另一种方法:将图中所有入度为0的顶点入队,然后每次出队一个顶点,将该顶点及其边删除,并将以该
点为起点的边的终点的入度-1,然后将入度为0的顶点入队,重复操作,知道队列为空.这种方法每次只操作了与删除点有关的点,效率比上一种方法高.
在书的P248
2. 无权最短路径
为了求出图上任意一个顶点到其他顶点的路径长度,我们从该点出发,将该点的路径长设为0,每次我们搜索该点邻接的点,邻接点的路径长度等于上一个的路径长度加一.这种方
法称为广度优先搜索.具体做法是:首先将起点入队,当列队不为空时,出队一个顶点,将该顶点的邻接点找出来,然后将他邻接点的路径长度在出队顶点的路径长度上加一,然后入队该
邻接点.重复操作,直到队列为空.
见书P250
3. 有权最短路径
为了求出图上任意一个顶点到其他顶点的有权路径长度,首先初始化所有顶点的有全路径长为无限大.我们从该点出发,将该点的路径长度设为0,然后将其入队,然后出队一个顶
点,找出该顶点的邻接点,如果该点的有权路径加上到邻接点的有权路径小于邻接点当前的有权路径,表示该邻接点的有权路径及其邻接点的有全路径需要调整,将该邻接点入队并调
整该邻接点有权路径.重复该操作,知道队列为空.该算法为dijkstra算法,核心思想依然是广度优先算法,该算法也是一个经典的贪婪算法.
4. 深度优先搜索算法
深度优先算法是沿着树的深度遍历节点,从起点开始选择任意一个邻接点遍历下去,直到没有未遍历节点,然后返回上一个节点,寻找上一个节点未遍历的邻接点,直到所有可遍
历到的节点遍历到.深度优先算法就是沿着图的深度遍历下去.
5. prim算法
该算法用与从无向图中找出一颗最小生成树,该算法的核心是从图中找到最小权值的边,将他的一个顶点入队,然后出队一个元素,将更新出队元素的邻接点的路径值,然后在出
队元素的邻接点与已经用的顶点的邻接点中找到路径值最小的点,该点即为下一个最小生产树的点,将该点入队.由于最小生成树的边数比顶点树少1,所以其循环次数已知.该算法是
贪婪算法的典型案例.
图的所有代码见graph项目.
Ps:未介绍的一些基本算法与数据结构:幂运算,求最大公因式算法,后缀表达式求算式值,左式堆,二项队列等.