计算机基础——数据结构
数据结构
-
栈
- 中缀表达式求值：操作数栈和运算符栈(25+x)*(a*(a+b)+b)
- 中转后：遇到数直接输出数字加空格……
- 后缀表达式求值：25 x + a a b + * b + *
-
队列(rear指向最后元素的下一个)
- 循环队列判断空：front==rear
- 循环队列判断满：(rear+1)%maxsize==front
-
串
- 穷举的字符串匹配算法：主串和子串指针都回溯。
- KMP算法：发现当主串和子串失配后，若子串中失配的点前面有和子串开头的点吻合，那子串就回溯到相同的下一个位置。模式串和主串不匹配后，主串指针不动，模式串指针回溯到指定位置。next代表不匹配的前面和串最前面有几个相同的。next[1]=-1,next[0]=0，abaababaca，-1001123232，建议从-1开始.
-
树
-
二叉树
- 左孩子：2*i，右孩子：2*i+1，父节点：i/2向下取整
- 在二叉树的第i层上至多有2i-1个结点(i≥1)
- 深度为k的二叉树至多有2k-1个结点(k≥1)
- 对任意一棵二叉树T，若终端结点数为n0，而其度数为2的结点数为n2，则n0= n2+1
-
赫夫曼树
- 路径：结点到结点的距离
- 树的路径长度：根到每个结点的距离和
- 带权路径：根到结点长度*权
- 树的带权路径长度WPL：根到每个叶结点长度*权
-
赫夫曼树：WPL最小的树。
- 应用1：挑权最小的两个，从树的下面开始构造。
- 应用2：编码。用二叉树，左孩子是0，右孩子是1，根据出现频率高低编码。这样编码，没有任何一个码是另一个码的前缀。
- 生成树：无向。图有n个点，有n-1条边
- B树：磁盘页对应b树的节点，只要那些包含元素地节点大小不超过磁盘页大小，树的高度决定访问磁盘次数（一次磁盘io后就进入内存进行比较）。它比二叉树的优势在于，只要树矮一些，就能提高查询效率，适合数据量大的查询。
- B+树：B+树节点最右边的数字是子树中最大的数字，而且非叶子节点不带数据，只是索引。B树的数据放在叶子和非叶子，这样的话磁盘页大小相同时，树的高度更低，每次查询效率都一样。另外它的叶子节点形成链表，方便范围查询。聚簇索引中，叶子节点带数据，非聚簇索引中，叶子节点是指向数据的指针。
-
二叉树
-
图
-
存储
- 邻接矩阵：无向图的邻接矩阵是对角对称，有向图的邻接矩阵不一定对称。
- 邻接表：有向无向都是从0到n为每个点建一个链表，结点：data+指向连着的结点。如果边有权重，则结点加一个权重元素。它只知道它连着谁，不知道谁连着它，因此有逆邻接表。
- 十字链表：一定是有向图。……
- 邻接多重表：一定是无向图。……
-
遍历
-
深度优先：
-
广度优先：
-
深度优先：
-
无向图
- 连通分量：非连通图的极大连通子图
- 生成树：n从无向图的每一个连通分量中的一个顶点出发进行DFS或BFS遍历，可求得无向图的所有连通分量的生成树(DFS或BFS生成树)
-
最小生成树：n-1条边。该生成树上所有边的权值和最小。
- prim：总是找相邻的边
- kruskal：总是找所有边中最小的
-
有向图：
- 最短路径：始点到每个点路径最短
- dijkstra：D[i]：到每个点最短路径。S：已求得最短路径的终点的集合。……
- 有向无环图：用深度优先搜索，找出是否有环。
-
存储
-
查找
-
二叉排序树
- 二叉排序树中序遍历得到由小到大排列。
- 删除：没有孩子直接删除，有孩子，则用中序遍历时被删结点的后继结点代替被删结点的值，然后直接删除后继结点。
- 查找效率：最好：O(log2n)，最差：O(n)。折半查找的平均查找效率O(log2n)
-
平衡二叉树
- 插入时间复杂度：O(logn)。删除时间复杂度：O(logn)。删除和二叉排序树一样。
- AVL树
-
红黑树
- 任何一个节点都有颜色，黑色或者红色
- 根节点是黑色的
- 父子节点之间不能出现两个连续的红节点
- 任何一个节点向下遍历到其子孙的叶子节点，所经过的黑节点个数必须相等
- 空节点被认为是黑色的
- https://tech.meituan.com/redblack-tree.html
- 调整：/，\，<、>。都转化成^。中间的在最顶上，左右各方一小一大。
-
哈希处理冲突
- 开放地址法：线性探测和二次探测法
- 再哈希法：构造若干哈希函数
- 链地址法
-
二叉排序树
-
排序
-
各种排序最好最差时间复杂度
-
各种排序最好最差时间复杂度