软考复习之数据结构篇
算法设计
迭代法：用于求方程的近似根。
1、若方程无解，则算法求出的近似根序列就不会收敛，迭代过程会变成死循环，因此在使用迭代算法前应先考查方程是否有解，并在程序中对迭代的次数给予限制。、方程虽有解，但迭代公式选择不当，或迭代的初始近似根选择不合理，也会导致迭代失败。
算法设计
迭代法：用于求方程的近似根。
1、若方程无解，则算法求出的近似根序列就不会收敛，迭代过程会变成死循环，因此在使用迭代算法前应先考查方程是否有解，并在程序中对迭代的次数给予限制。
2、方程虽有解，但迭代公式选择不当，或迭代的初始近似根选择不合理，也会导致迭代失败。
穷举搜索法：对可能是解的众多候选解按某种顺序进行逐一枚举和检查，并从中找出符合要求的候选解作为问题的解
递推法：利用问题本身所具有的一种递推关系求问题解的一种方法
递归法：执行过程分递推和回归两个阶段：在递推阶段，把较复杂的问题的求解分解成比原问题简单一些的问题的求解。在回归阶段，从获得的最简单情况的解，逐级返回，依次获得稍复杂问题的解。（递归法就是把问题转化为规模缩小了的同类问题的子问题）
分治法：把大问题分解成一些较小的问题，然后由小问题的解方便地构造出大问题的解，每个小问题都是相互独立的。例如二分查找法、汉诺塔问题、斐波那契、归并排序
动态规划法：基本思想也是将大问题分解为多个小问题，但是与分治法不同的是，动态规划法的子问题往往不是独立的。因此，动态规划法可以避免大量重复的计算。以自底向上的方式计算出最优值。例如最大子段问题
贪心法：不追求最优解，只希望得到较为满意解的方法。可以快速得到满意的解，不考虑整体情况，所以贪心法不要回溯。例如哈夫曼编码
回溯法：该方法首先暂时放弃关于问题规模大小的限制，并将问题的候选解按某种顺序逐一枚举和检验。当发现当前候选解不可能是解时，就选择下一个候选解；倘若当前候选键除了不满足问题规模要求外，满足所有其他要求，继续扩大当前候选解的规模，并继续试探。如果当前候选解满足包括问题规模在内的所有要求，该候选键就是问题的一个解。在回溯法中，放弃当前候选解，寻找下一个候选解的过程被称为回溯；扩大当前候选解的规模，以继续试探的过程称为向前试探，回溯法以深度优先的方式搜索解空间树。
分支限界法：类似于回溯法，也是在问题的解空间树上搜索问题解的方法。但在一般情况下，二者的求解目标不同。回溯法是找出解空间树中满足空间树中满足约束条件的解中找出使某一目标函数值达到极大或极小的解，即在某种意义下的最优解。分支限界法以广度优先或以最小耗费优先的方式搜索空间树。例如单源最短路径问题
算法复杂度
一般地，当递归方程为 T(n) = aT(n/c) + O(n)，T(n)的解为：
概率算法
数值概率算法：适用于数值问题的求解，这类算法得到的往往是近似解，且近似解的精度随时间的增加不断提高。在多数情况下，要计算出问题的精确解是不可能的或是没有必要的，因此数值概率算法可得到相当令人满意的解。
蒙特卡罗算法：适用于求问题的精确解，该算法能求得一个解，但该解未必是正确的，正确的概率依赖算法所用的时间，时间越久，正确率越高。因此，该算法的缺点就是无法有效地判断所得到的解是否正确。
拉斯维加斯算法：如果该算法找到一个解，那一定是正确的解，得到正确解的概率依赖算法所用的时间。
舍伍德算法：一定能找到一个正确的解，该算法设法消除最坏情形与特定实例之间的关联性。
邻接矩阵
无向图：其邻接矩阵第i行的元素的和即为顶点i的度
例如：顶点4的度就是第四行的和，即2。
有向图：其邻接矩阵第i行元素之和为顶点i的出度，而邻接矩阵的第j列元素之和为顶点j的入度
例如：顶点3的出度和入度分别为5和16
广义表
广义表的长度是将最外面那层的括号删了以后所剩下的元素（组）个数，深度是括号的层数
存储结构
顺序存储结构：用一组地址连续的存储单元依次存储线性表的各个数据元素，适用于频繁查询时使用
链式存储结构：在计算机中用一组任意的存储单元存储线性表的数据元素，适用于在较频繁的插入、删除、更新元素时使用
(单链表)
(循环链表)
(双链表)
各链表的比较
因为双链表有两个指针域，因此，双链表的灵活度优于单链表，但是双链表的开支要大一些
散列存储结构：将数据元素的存储位置与关键码之间建立确定对应关系的查找技术，即键值对
索引存储结构：索引是一个单独的、物理的数据库结构，它是某个表中一列或若干列值的集合和相应的指向表中物理标识这些值的数据页的逻辑指针清单。比如数据库
树
二叉排序树
- 若它的左子树非空，则左子树所有节点的值均小于它的根节点的值
- 若它的右子树非空，则右子树所有节点的值均大于等于它的根节点的值
- 它的左、右子树也分别为二叉排序树。查找的时候，中序遍历二叉树，得到一个递增序列
- 关键字最大的结点可以有左子树，但一定没有右子树
哈夫曼树（最优二叉树）
定义：哈夫曼树是带权路径（WPL）最短的树，权值越大的叶子节点越靠近根节点
WPL值的计算：树的路径长度是从树根到每一结点的路径长度之和。树的带权路径长度为树中所有叶子结点的带权路径长度之和，通常记作WPL
例题
已知一个文件中出现的各字符及其对应的频率如下表所示。若采用定长编码，则该文件中字符的码长应为（1）。若采用Huffman编码，则字符序列“face”的编码应为（2）。
(1)A．2 B．3 C．4 D．5
(2)A．110001001101 B．001110110011 C．101000010100 D．010111101011
解析：所谓定长编码是指用多少位二进制足够表示字符，图中字符是有6个的，a、b、c、d、e、f，可用000到101表示a到f，这样编码字符的码长可以为3，4位当然也是可以，但我们是找最合适的，自然3位能满足要求。第二问，哈夫曼树的左节点未必要比右节点小，但是通常做题时需要写成左小右大的形式，再左0右1赋值，所谓“face”编码，是指找到这4个字母，从根节点出发，要经历的编码数。如下图所示，所以答案为B、A
平衡二叉树
平衡二叉树又称为AVL树，且具有以下性质：
它是一棵空树或它的左右两棵子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树
满二叉树
除最后一层无任何子节点外，每一层都上的所有节点都有两个子节点或0个子结点的二叉树
二分查找法(折半查找法)
适用情况
不经常变动而查找频繁的有序列表
优点
1、比较次数少
2、查找速度快
3、平均性能好
缺点
1、要求待查表为有序表
2、插入删除困难
实现算法：首先，假设表中元素是按升序排列，将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。
分块查找
适用情况：节点动态变化的情况
优点：比顺序查找算法快得多
缺点：速度不如折半查找法
实现算法：把一个线性表分成若干个块，每块中的节点可以任意存放，但块与块之间必须排序。假设是按关键码值非递减的，那么这种块与块之间必须满足已排序要求，实际上就是对于任意的i，第i 块中的所有节点的关键码值都必须小于第i+1块中的所有节点的关键码值。此外，还要建立一个索引表，把每块中的最关键码值作为索引表的关键码值，按块的顺序存放到一个辅助数组中，显然这个辅助数组是按关键码值递减排序的。查找时，首先在索引表中进行查找，确定要找的节点所在的块。由于索引表的排序的，因此，对索引表的查找可以采用顺序查找或折半查找;然后在相应的块中采用顺序查找，即可找到对应的节点
平均查找长度：
（1）以二分查找确定块时，平均查找长度 = log2(n / s+1) + s / 2
（2）以顺序查找确定块时，平均查找长度 = (b + 1) / 2 + (s + 1) / 2 = (s^2 + 2s + n) / 2s
注：n 表示元素的总个数
s 表示每个块所具有的元素个数
b 表示分为几个块
排序
归并排序的归并路数
归并路数 = | logkm |，其中m为元素个数，k为多路归并趟数
版权声明：本文为aitao2018原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。