自考数据结构公式汇总
1. O(1)、O(log2n)、O(n)、O(nlog2n)、O(n2)、 O(n3)、O(nk)、O(2n)。
2. 在顺序表中第i个位置插入一个结点的移动次数为n-i+1，插入平均移动n/2次，删除顺序表第i个结点移动次数为n-i，平均移动(n-1)/2次。
3. 定义变量p=(LinkList)malloc(sizeof(ListNode))或p=(LinkNode*)malloc(sizeof(ListNode))
4. 单循环链表判断空：head= =head->next
5. 共享向量空间判断满top1=top2-1
6. 入队EnQueue，出队DeQueue，front=rear空队列，循环队列克服假上溢
7. 循环队列判断队满(rear+1)%m=front，循环队列指针移动方向顺时针。判队列长度(rear-front+m)%m
8. 链队列判空：Q->front=Q->rear=NULL
9. 求串长strlen，串复制strcpy(to,from)，联接strcat(to,from)，串比较strcmp(s1大就大于s1小就小于，小写字母>大写字母)，字符定位strchr
10. 串的子串定位（模式匹配）下标从0开始，最坏情况下时间复杂度比较次数O((n-m+1)m)
11. 二维数组下标为0公式：行优先LOC(a00)+[i*n+j]*d，列优先LOC(a00)+[j*m+i]*d
12. 三维数组下标为0公式：三维数组Amnp按行优先LOC(aijk)=LOC(a000)+[i*n*p+j*p+k]*d
13. 对称矩阵一共有n(n+1)/2个元素，存储位置k=I*(I+1)/2+J(I=max(i,j),J=min(i,j))下标0开始
14. 上三角矩阵：k=i*(2n-i+1)+j-i，下三角矩阵：k=i*(i+1)/2+j。上三角i>j下三角i<j常数n*(n+1)/2
15. 对角矩阵：若︱i-j︱>(k-1)/2，则元素aij=0
16. 三元组表组成：i(行)j(列)v(值)，转置时间复杂度O(m*n),带行表的三元组表是一种顺序存储结构。
17. 二叉树第i层上的结点数目最多为2i-1，深度为k的二叉树至多有2k-1个结点。终端结点的个数为n0，度为2的结点数为n2，则n0=n2+1。一棵深度为k且有2k-1个结点的二叉树称满二叉树。具有n个结点的完全二叉树的深度为⌊lgn⌋+1 或⌈lg(n+1)⌉
18. 完全二叉树中编号i>⌊n/2⌋的结点必定是叶结点。
19. 二叉链表共有2n个指针域，其中n-1个用来指示结点的左右孩子，其余的n+1个指针域为空。
20. 线索二叉树ltag=0左孩子，ltag=1左线索；rtag=0右孩子，rtag=1右线索。线索查对查指定结点的后续后继无帮助。
21. 最优二叉树：哈夫曼树WPL带权路径长度=第几层(第0层开始)*权值，累加。哈夫曼树共有2n-1个结点，其中n为原始结点，生产过程中产生n-1个新结点，如原始结点为4，新结点为3，哈夫曼树则有2*4-1七个结点。
22. 构造哈夫曼树过程：选两个权值最小的，合并成一个新的权值，再在剩下的权值中（包
括新合并的权值）再造两个最小的，再合并，直到所有权值合并结束。哈夫曼树编码，左边为0右边为1。
23. 无向完全图有n(n-1)/2条边，有向完全图有n(n-1)条边。一条有向边<vi,vj>vi邻接到vj,vj邻接于vi
24. 顶点数n、边数e和度数D(vi)关系边数e=1/2(所有顶点入度+出度)之和
25. 稀疏图用邻接表，稠密图用邻接矩阵。无向图：邻接表表示中有n个顶点和2e个边表结点，有向图，有n个顶点和e个边表结点。空间复杂度O(n+e)
26. 无向图：邻接表表示中有n个顶点和2e个边表结点，有向图，有n个顶点和e个边表结点。空间复杂度O(n+e)
27. n个顶点的连通图至少有n-1条边。
28. 各种排序方法的比较
方法
类型
稳定性
最好
平均
最坏
空间
直插
插入
稳定
O(n)
O(n2)
O(1)
直选
选择
不稳定
O(n2)
冒泡
交换
稳定
O(n)
O(n2)
二叉树公式
希尔
插入
不稳定
n1.25
快速
交换
不稳定
O(nlgn)
O(n2)
Olgn
堆
选择
不稳定
O(nlgn)
O(1)
归并
归并
稳定
O(nlgn)
O(n)
基数
分配
稳定
O(d﹒n+d﹒rd)
O(n+rd)
29. 冒泡排序的移动次数为3n(n-1)/2，比较次数为n(n-1)/2。
30. 顺序查：平均查长度：ASLsq=(n+1)/2
31. 二分查：平均查长度：ASLbn=(n+1)/n*lg(n+1)-1=lg(n+1)-1。二分查判定树深度为⌈lg(n+1)⌉
32. 分块查：要求分块有序。
按二分查定块：ASLblk=lg(n/s+1)+s/2。
按顺序查定块：ASL'blk=(s2+2s+n)/(2s)，
其中n为节点数，s为块的大小，s=⌈n/b⌉，
当 s=(根号)N 时ASL'blk取极小值 (根号N) +1。
33. 二叉排序树：typedef BSTNode *BSTree；生成：小的插左边，大的插右边。平均查长度：从1开始。例：(1+2*2+3*4)/7。AVL树，平衡二叉树。
34. 散列表冲突处理方法：开放定址法：线性探查法：hi=(h(key)+i)%m，二次探查法：hi=(h(key)+i*i)%m。
35. B-树关键字个数满足：至少有⌈m/2⌉-1个结点至多有m-1个结点。每个非根的内部结点至少有⌈m/2⌉棵子树，至多有m棵子树。根至少有1个关键字，至少有2棵子树，根至多有m-1个关键字。B-树的高度h=logt(n+1/2)+1 t=⌈m/2⌉

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。