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，循环队列指针移动方向顺时针。
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. 广义表的深度是指表展开后所含括号的层数。分纯表（限制了共享和递归）、再入表（允许结点共享）、递归表
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. 线索二叉树ltag=0左孩子，ltag=1左线索；rtag=0右孩子，rtag=1右线索。线索查对查指定结点的后续后继无帮助。
23. 森林转换为二叉树：第一步：根连起来，第二步：原来和根连的左孩子继续向左，第三步：原来和根连的右孩子向右，第四步：下一层，原来向左的继续向左，原来笔直的也向左，原来向右的还是向右。
24. 树的存储结构：双亲链表表示法（结点附设一个指向其双亲的指针parent）、孩子链表表示法(每个结点设置一个孩子链表)、孩子兄弟链表表示法（附加两个分别指向该结点最左孩子和右邻兄弟的指针域）。
25. 树的遍历：前序相当于二叉树前序，后续相当于二叉树中序遍历。
26. 最优二叉树：哈夫曼树WPL带权路径长度=第几层(第0层开始)*权值，累加。哈夫曼树共有2n-1个结点，其中n为原始结点，生产过程中产生n-1个新结点，如原始结点为4，新结点为3，哈夫曼树则有2*4-1七个结点。
27. 构造哈夫曼树过程：选两个权值最小的，合并成一个新的权值，再在剩下的权值中（包括新合并的权值）再造两个最小的，再合并，直到所有权值合并结束。哈夫曼树编码，左边为0右边为1。
28. 无向完全图有n*(n-1)/2条边，有向完全图有n(n-1)条边。一条有向边<vi,vj>vi邻接到vj,vj邻接于vi
29. 顶点数n、边数e和度数D(vi)关系边数e=1/2(入度+出度)之和
30. 有向图的极大强连通子图称为G的强连通分量。强连通图只有一个强连通分量，即是其自身。非强连通有向图有多个强连通分量，其中一个是其自身。
31. 邻接矩阵：行代表入度，列代表出度。邻接表：无向图：顶点表，边表。有向图：顶点表，出边表，入边表。。
32. 稀疏图用邻接表，稠密图用邻接矩阵。无向图：邻接表表示中有n个顶点和2e个边表结点，有向图，有n个顶点和e个边表结点。空间复杂度O(n+e)
33. 深度优先遍历类似于前序遍历，从出发点v，依次经过v的每个邻接点，并将其标记为已访问过，然后依次从v出发搜索v的每个邻接点w，若未曾访问过，则以该点出发继续深度优先遍历，用栈来实现。广度优先遍历类似于按层次遍历，首先访问v所有邻接点w1,w2,w3，然后再访问与w1,w2,w3邻接的所有未曾访问过的顶点，用队列来实现。
34. n个顶点的连通图至少有n-1条边。
35. 最小生成树：普里姆(prim)算法，克鲁斯卡尔(kruskal)算法。最短路径：迪杰斯特拉(Dijkstra)算法。
36. 拓扑排序：图中存在有向环，则不可能使顶点满足拓扑次序。无前趋的顶点优先，无后继的顶点优先。
37.

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