2023年数据结构公式及要点超详细知识汇总全面汇总归纳.pdf

学习必备 欢迎下载 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。上三角 ij 下三角 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.线索二叉树 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,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.拓扑排序：图中存在有向环，则不可能使顶点满足拓扑次序。无前趋的顶点优先，无后继的顶点优先。队满循环队列指针移动方向顺时针链队列判空求串长串复制联接小写字先对称矩阵一共有个元素存储位置下标开始上三角矩阵下三角矩阵上三制了共享和递归再入表允许结点共享递归表树可以有一个前驱多个后继