数据结构复习笔记
-
花剌子密（al-Khwārizmī）：用阿拉伯数字进行算 数运算的规则，求解线性和二次方程的方法
-
P：一类问题可以有算法在多项式时间求解。NP： 没有已知算法在多项式时间求解，但是可以用多 项式时间验证一个答案是否其解 如果P ̸= NP，则存在NP问题（NPC），它们的求解 比验证要困难。例如，旅行销售员问题就是NPC问 题
-
费波拉契数列
递归：2^n
迭代：
插入排序
从数组第二个数开始，作为元，依次进行往前比较，前面的数比元大则交换位置。
-
最大公约数的欧几里德算法（辗转相除法）logϕ n，ϕ =1.618
-
折半查找
-
求幂（x的n次方）
-
寻找3到n的质数-筛法
-
最大子序列和问题的求解-分治
-
线性表，数组实现和链表实现
-
链表：单链表，双链表，循环链表，排序链表，多重链表，搜索链表
-
多项式加法，乘法
-
求一个数组的主元，主元是数组中出现次数超过一半的数
-
桶式排序，基数排序(低位优先)
-
堆栈。
-
栈解决符号平衡问题。
-
中缀表达式转换为后缀表达式
-
队列
-
游标实现链表
-
树，
- 父子兄弟树（firstChild ，nextSibling）
- 二叉树（left ， right），树的遍历（先序，中序，后序遍历）（标准是根遍历的先后顺序），表达式树，决策树
- 二叉查找树（BST），
- 平衡二叉树（AVL树），
- B树
-
约瑟夫问题
-
层序遍历
-
B树。建立B树在查找时减少对磁盘 的访问。
-
二叉树同构
-
2-d树，2个关键字的二叉树，奇数层用关键字1作为键分左右，偶数层用关键字2作为键分左右
-
散列（压缩映射）
-
很难避免冲突，
-
开放地址散列法中，如果有冲突发生，就尝试选择另外单元，直到找出空的单元为止。
-
解决冲突的方法（如下）：
-
哈希表的方式。
-
随机数算法
-
再散列的方式。
1.线性探测
2.平方探测：只要表大小是素数，则表至少有一半是空的
-
-
二叉堆（所有的根节点比左右节点小）
- 插入操作O(log n)：先满足完全二叉树的条件，再上滤。
- 删除最小元O(log n)：先下滤到叶，再删除，再将堆最底层的最靠右的叶补到删除的位置。下滤往子节点中较小（最小堆）的一个滤。
- 二叉堆的数组实现：左孩子2i，右孩子2i+1， 父在i/2
- 建堆（O(n)） deleteMin(Max),->O(log n)
- 堆排序（最大堆删除最大值（下滤），数组实现则将这个值放在数组最后）
-
排序
- 简单排序：插入排序，冒泡排序（任何相邻项比较的算法复杂度都是Θ(n 2 )的）
- 希尔排序
- 归并排序（O(nlogn) ）
- 快速排序（O(nlogn)）
- 最优排序
- 外部排序
-
图
-
邻接表，领接矩阵
-
一条最短路径的子路径是一条最短路径
-
加权最短路径（总是选择最短的边）
Dijkstra算法
-
最小生成树
Kruskal算法（在不构成循环的条件下，永远选择最小的边）
-
-
贪婪算法（哈夫曼编码）
-
分治算法
-
动态规划
-
回溯算法
