自考数据结构公式汇总
1.O(1)、O(log2n)、O(n)、O(nlog2n)、O(n2)、 O(n3)、O(n k)、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公式：三维数组A mnp按行优先LOC(a ijk)=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，则元素a ij=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)条边。
一条有向边<v i,v j>v i邻接
到v j,v j邻接于v i
24.顶点数n、边数e和度数D(v i)关系边数e=1/2(所有顶点入度+出度)之和
25.稀疏图用邻接表，稠密图用邻接矩阵。
无向图：邻接表表示中有n个顶点和2e个边
表结点，有向图，有n个顶点和e个边表结点。
空间复杂度O(n+e)
26.无向图：邻接表表示中有n个顶点和2e个边表结点，有向图，有n个顶点和e个边
表结点。
空间复杂度O(n+e)
27.n个顶点的连通图至少有n-1条边。
28.各种排序方法的比较
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.分块查找：要求分块有序。
按二分查找定块：ASL blk=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=log t(n+1/2)+1 t=⌈m/2⌉。