《数据结构(公式及要点汇总)》由会员分享,可在线阅读,更多相关《数据结构(公式及要点汇总)(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. 拓扑排序:图中存在有向环,则不可能使顶点满足拓扑次序。无前趋的顶点优先,无后继的顶点优先。