数据结构(公式及要点汇总)汇.docVIP

O(1)、O(log2n)、O(n)、O(nlog2n)、O(n2) O(n3)、O(nk)、O(2n)。 在顺序表中第i个位置插入一个结点的移动次数为n-i+1，插入平均移动n/2次， 删除顺序表第i个结点移动次数为n-i，平均移动(n-1)/2次。 定义变量p=(LinkList)malloc(sizeof(ListNode))或p=(LinkNode*)malloc(sizeof(ListNode)) 单循环链表判断空：head= =head-next 共享向量空间判断满top1=top2-1 入队EnQueue，出队DeQueue，front=rear空队列，循环队列克服假上溢 循环队列判断队满(rear+1)%m=front，循环队列指针移动方向顺时针。 链队列判空：Q-front=Q-rear=NULL 求串长strlen，串复制strcpy(to,from)，联接strcat(to,from)，串比较strcmp(s1大就大于s1小就小于，小写字母大写字母)，字符定位strchr 串的子串定位（模式匹配）下标从0开始，最坏情况下时间复杂度比较次数O((n-m+1)m) 二维数组下标为0公式：行优先LOC(a00)+[i*n+j]*d，列优先LOC(a00)+[j*m+i]*d 三维数组下标为0公式：三维数组Amnp按行优先LOC(aijk)=LOC(a000)+[i*n*p+j*p+k]*d 对称矩阵一共有n(n+1)/2个元素，存储位置k=I*(I+1)/2+J(I=max(i,j),J=min(i,j))下标0开始 上三角矩阵：k=i*(2n-i+1)+j-i，下三角矩阵：k=i*(i+1)/2+j。上三角ij下三角ij常数n*(n+1)/2 对角矩阵：若︱i-j︱(k-1)/2，则元素aij=0 三元组表组成：i(行)j(列)v(值)，转置时间复杂度O(m*n),带行表的三元组表是一种顺序存储结构。 广义表的深度是指表展开后所含括号的层数。分纯表（限制了共享和递归）、再入表（允许结点共享）、递归表 树可以有一个前驱，多个后继。一个结点拥有的子树称为该结点的度。一棵树的度是指该树中结点最大的度数，度为零的结点称为叶子，树之间连接称路径，树中结点的最大层数称为树的高度或深度。 二叉树第i层上的结点数目最多为2i-1，深度为k的二叉树至多有2K-1个结点。终端结点的个数为n0，度为2的结点数为n2，则n0=n2+1。一棵深度为k且有2k-1个结点的二叉树称满二叉树。具有n个结点的完全二叉树的深度为?lgn?+1 或?lg(n+1)? 完全二叉树中编号i?n/2?的结点必定是叶结点。 二叉链表共有2n个指针域，其中n-1个用来指示结点的左右孩子，其余的n+1个指针域为空。 线索二叉树ltag=0左孩子，ltag=1左线索；rtag=0右孩子，rtag=1右线索。线索查找对查找指定结点的后续后继无帮助。 森林转换为二叉树：第一步：根连起来，第二步：原来和根连的左孩子继续向左，第三步：原来和根连的右孩子向右，第四步：下一层，原来向左的继续向左，原来笔直的也向左，原来向右的还是向右。 树的存储结构：双亲链表表示法（结点附设一个指向其双亲的指针parent）、孩子链表表示法(每个结点设置一个孩子链表)、孩子兄弟链表表示法（附加两个分别指向该结点最左孩子和右邻兄弟的指针域）。 树的遍历：前序相当于二叉树前序，后续相当于二叉树中序遍历。 最优二叉树：哈夫曼树WPL带权路径长度=第几层(第0层开始)*权值，累加。哈夫曼树共有2n-1个结点，其中n为原始结点，生产过程中产生n-1个新结点，如原始结点为4，新结点为3，哈夫曼树则有2*4-1七个结点。 构造哈夫曼树过程：选两个权值最小的，合并成一个新的权值，再在剩下的权值中（包括新合并的权值）再造两个最小的，再合并，直到所有权值合并结束。哈夫曼树编码，左边为0右边为1。 无向完全图有n*(n-1)/2条边，有向完全图有n(n-1)条边。一条有向边vi,vjvi邻接到vj,vj邻接于vi 顶点数n、边数e和度数D(vi)关系边数e=1/2(入度+出度)之和 有向图的极大强连通子图称为G的强连通分量。强连通图只有一个强连通分量，即是其自身。非强连通有向图有多个强连通分量，其中一个是其自身。 邻接矩阵：行代表入度，列代表出度。邻接表：无向图：顶点表，边表。有向图：顶点表，出边表，入边表。。 稀疏图用邻接表，稠密图用邻接矩阵。无向图：邻接表表示中有n个顶点和2e个边表结点，有向图，有n个顶点和e个边表结点。空间复杂度O(n+e) 深度优先遍历类似于前序遍历，从出发点v，依次经过v的每个邻接点，并将其标记为已访问过，然后依次从v出发有哪些信誉好的足球投注网站v的每个邻接点w，若未曾访问过，则以该点出发继续深度优先遍