《数据结构(公式及要点汇总)》由会员分享，可在线阅读，更多相关《数据结构(公式及要点汇总)（2页珍藏版）》请在金锄头文库上搜索。
1、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-next5. 共享向量空间判断满top1=top2-16. 入队EnQueue，出队DeQueue，front=rear空队列，循环队
2、列克服假上溢7. 循环队列判断队满(rear+1)%m=front，循环队列指针移动方向顺时针。8. 链队列判空：Q-front=Q-rear=NULL9. 求串长strlen，串复制strcpy(to,from)，联接strcat(to,from)，串比较strcmp(s1大就大于s1小就小于，小写字母大写字母)，字符定位strchr10. 串的子串定位（模式匹配）下标从0开始，最坏情况下时间复杂度比较次数O(n-m+1)m)11. 二维数组下标为0公式：行优先LOC(a00)+i*n+j*d，列优先LOC(a00)+j*m+i*d12. 三维数组下标为0公式：三维数组Amnp按行优先LOC
3、(aijk)=LOC(a000)+i*n*p+j*p+k*d13. 对称矩阵一共有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。上三角ij下三角i(k-1)/2，则元素aij=016. 三元组表组成：i(行)j(列)v(值)，转置时间复杂度O(m*n),带行表的三元组表是一种顺序存储结构。17. 广义表的深度是指表展开后所含括号的层数。分纯表（限制了共享和递归）、再入表（允许结点共享）、递归表18. 树可以有一个前驱，多个后继。一个结点
4、拥有的子树称为该结点的度。一棵树的度是指该树中结点最大的度数，度为零的结点称为叶子，树之间连接称路径，树中结点的最大层数称为树的高度或深度。19. 二叉树第i层上的结点数目最多为2i-1，深度为k的二叉树至多有2K-1个结点。终端结点的个数为n0，度为2的结点数为n2，则n0=n2+1。一棵深度为k且有2k-1个结点的二叉树称满二叉树。具有n个结点的完全二叉树的深度为lgn+1 或lg(n+1)20. 完全二叉树中编号in/2的结点必定是叶结点。21. 二叉链表共有2n个指针域，其中n-1个用来指示结点的左右孩子，其余的n+1个指针域为空。22. 线索二叉树ltag=0左孩子，ltag=1左线
5、索；rtag=0右孩子，rtag=1右线索。线索查找对查找指定结点的后续后继无帮助。23. 森林转换为二叉树：第一步：根连起来，第二步：原来和根连的左孩子继续向左，第三步：原来和根连的右孩子向右，第四步：下一层，原来向左的继续向左，原来笔直的也向左，原来向右的还是向右。24. 树的存储结构：双亲链表表示法（结点附设一个指向其双亲的指针parent）、孩子链表表示法(每个结点设置一个孩子链表)、孩子兄弟链表表示法（附加两个分别指向该结点最左孩子和右邻兄弟的指针域）。25. 树的遍历：前序相当于二叉树前序，后续相当于二叉树中序遍历。26. 最优二叉树：哈夫曼树WPL带权路径长度=第几层(第0层开始
6、)*权值，累加。哈夫曼树共有2n-1个结点，其中n为原始结点，生产过程中产生n-1个新结点，如原始结点为4，新结点为3，哈夫曼树则有2*4-1七个结点。27. 构造哈夫曼树过程：选两个权值最小的，合并成一个新的权值，再在剩下的权值中（包括新合并的权值）再造两个最小的，再合并，直到所有权值合并结束。哈夫曼树编码，左边为0右边为1。28. 无向完全图有n*(n-1)/2条边，有向完全图有n(n-1)条边。一条有向边vi邻接到vj,vj邻接于vi29. 顶点数n、边数e和度数D(vi)关系边数e=1/2(入度+出度)之和30. 有向图的极大强连通子图称为G的强连通分量。强连通图只有一个强连通分量，即
7、是其自身。非强连通有向图有多个强连通分量，其中一个是其自身。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. 拓扑排序：图中存在有向环，则不可能使顶点满足拓扑次序。无前趋的顶点优先，无后继的顶点优先。
