数据结构公式及重点汇总VIP专享VIP免费

1 / 2 1.O(1) 、O(log 2n) 、O(n) 、O(nlog 2n) 、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，循环队列指针移动方向顺时针。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(k-1)/2，则元素 aij =0 16. 三元组表组成：i( 行)j( 列 )v( 值) ，转置时间复杂度O(m*n), 带行表的三元组表是一种顺序存储结构。17. 广义表的深度是指表展开后所含括号的层数。分纯表（限制了共享和递归）、再入表（允许结点共享）、递归表18. 树可以有一个前驱，多个后继。 一个结点拥有的子树称为该结点的度。一棵树的度是指该树中结点最大的度数，度为零的结点称为叶子，树之间连接称路径，树中结点的最大层数称为树的高度或深度。19. 二叉树第i 层上的结点数目最多为2i-1，深度为k 的二叉树至多有2K-1 个结点。终端结点的个数为n0，度为 2的结点数为n2，则 n0=n2+1。一棵深度为k 且有 2k-1 个结点的二叉树称满二叉树。具有n 个结点的完全二叉树的深度为 ?lgn?+1 或 ?lg(n+1) ?20. 完全二叉树中编号i> ?n/2?的结点必定是叶结点。21. 二叉链表共有2n 个指针域，其中n-1 个用来指示结点的左右孩子，其余的n+1 个指针域为空。22. 线...