type
status
date
slug
summary
tags
category
icon
password
文章目录
- * 完全无向图和完全有向图公式
- 串
- 结点计算公式
- 最小生成树
- 矩阵:
- 哈夫曼树
- _自考数据结构公式汇总_ </p>
数据结构答疑机器人：
<https://www.coze.cn/s/iYoueDL3/>
数据结构题目 已上传到资源,没积分可以vx加我获取:
<https://download.csdn.net/download/xianyu120/68011213>
完全无向图和完全有向图公式
将一个具有 n 个顶点 e 条边的无向图存储在邻接矩阵中，则非零元素的个数是 2e。
对于一个具有 n 个顶点 e 条边的有向图存储在邻接矩阵中，则非零元素的个数是 e。
假设只有 1 个结点的二叉树的深度为 1，具有 256 个结点的完全二叉树的深度为 9。**
若对含n个结点的完全二叉树从上到下且从左至右进行0至n-1的编号,则
对完全二叉树中任意一个编号为i的结点,有
其双亲结点;
(2)若2i+1≥n,则该结点无左孩子,否则,编号为2i+1的结点为其左孩子结点
(3)若2i+2≥n,则该结点无右孩子结点,否则,编号为2i+2的结点为其右孩子结
从 0 开始，自顶向下、自左向右对一棵二叉树进行顺序编号，则编号为 i
的结点，若它存在左、右孩子，则左、右孩子编号分别为____2i+1____、****2i+2**** 。**
串
子串的个数
串（string）：是由零个或多个字符组成的有限序列，又名叫字符串。
子串：串中任意个连续的字符组成的子序列称为该串的子串，空串也属于子串。
实例应用：若串S=′software′,其子串的数目是()
解析：n(n+1)/2+1=8（8+1）/2+1=37
串中字符出现重复：字符串’wwwpqqpcom’所有非空子串（两个子串如果内容相同则只算一个）个数是（）
答案：50
解析：包含重复子串共：n(n+1)/2+1=10（10+1）/2+1=55，减去重复：2个w，1个ww，1个q，1个.，所以共55-5=50个
串的定位操作通常称为串的模式匹配
结点计算公式
设只有 1 个结点的二叉树的深度为 1，则深度为 k 的完全二叉树至少有** 2k-1** 个结点,至多有 **2k-1** 个结点
设 n0为哈夫曼树的叶子结点数目，则该哈夫曼树共有** 2n0-1 **个结点
一棵满二叉树的结点个数为 n，高度为 h，则 n= ** 2^h -1**
有 n 个顶点的无向完全图具有** n(n-1)/2** 条边
设有一个长度为 n 的顺序表，要删除第 i(0<=i<=n-1)个元素，需移动元素的个数
为 **n-i-1** 。
叶节点 节点的关系:**2i+1 2i-1**
从 0 开始，自顶向下、自左向右对一棵二叉树进行顺序编号，则编号为 i
的结点，若它存在左、右孩子，则左、右孩子编号分别为____**2i+1******、******2i+2** ____
在包含 n 个元素的顺序表中删除一个元素，需要平均移动** (n-1)/2 **个元素
最小生成树
已知一个网的形式如下：
请利用克鲁斯卡尔算法构造该网的最小生成树，绘制每一步构造过程情况。
记忆技巧：一个人玩井口游戏
请利用普里姆(Prim)算法从a点出发构造该网的最小生成树，绘制每一步构造过程情况。
记忆技巧：多个人玩井口游戏
克鲁斯卡尔算法，生成图的最小生成树，步骤：
普里姆(Prim)算法从a点出发构造该网的最小生成树，步骤：
矩阵:
题目：有一个10阶矩阵，他的基地址是GDP，每个元素占用6个空间大小，那么
A（8，9）的起始地址是（GDP+534）,这个10阶共占用的空间大小是（600）
解析：10阶：10m*10n
特殊矩阵-对称矩阵、上三角、下三角:
A(2,3) 对应下标index是多少
层次遍历(记忆诀窍:想象成一个人爬山)
先跟遍历：先根再左最后右
中根遍历：先左再根最后右
后根遍历：先左再右最后根
哈夫曼树
_自考数据结构公式汇总_
- O(1)、O(log 2n)、O(n)、O(nlog 2n)、O(n 2)、 O(n 3)、O(n k )、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 ，循环队列指针移动方向顺时针。判队列长度(rear-front+m)%m
- 链队列判空：Q->front=Q->rear=NULL
- 求串长strlen ，串复制strcpy(to,from)，联接strcat(to,from)，串比较strcmp(s1大就大于s1小就小于，
小写字母>大写字母)，字符定位strchr
- 串的子串定位（模式匹配）下标从0开始，最坏情况下时间复杂度比较次数O((n-m+1)m )
- 二维数组下标为0公式：行优先LOC(a 00)+[i*n+j ]_d ，列优先LOC(a 00)+[j_ m+i ]*d
- 三维数组下标为0公式：三维数组A mnp 按行优先LOC(a ijk )=LOC(a 000)+[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 。上三角i>j 下三角i<j 常数n*(n+1)/2
- 对角矩阵：若︱i-j ︱>(k-1)/2，则元素a ij =0
- 三元组表组成：i(行)j(列)v(值)，转置时间复杂度O(m*n),带行表的三元组表是一种顺序存储结构。
- 二叉树第i 层上的结点数目最多为2i-1，深度为k 的二叉树至多有2k -1个结点。终端结点的个数为n 0，度为2
的结点数为n 2，则n 0=n 2+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右线索。线索查找对查找指定结点的后续
后继无帮助。
- 最优二叉树：哈夫曼树WPL 带权路径长度=第几层(第0层开始)*权值，累加。哈夫曼树共有2n-1个结点，其中
n 为原始结点，生产过程中产生n-1个新结点，如原始结点为4，新结点为3，哈夫曼树则有2*4-1七个结点。 22.
构造哈夫曼树过程：选两个权值最小的，合并成一个新的权值，再在剩下的权值中（包括新合并的权值）再造两
个最小的，再合并，直到所有权值合并结束。哈夫曼树编码，左边为0右边为1。 23.
无向完全图有n(n-1)/2条边，有向完全图有n(n-1)条边。一条有向边<v i ,v j >v i 邻接到v j ,v j 邻接于v i
- 稀疏图用邻接表，稠密图用邻接矩阵。无向图：邻接表表示中有n 个顶点和2e 个边表结点，有向图，有n 个顶
点和e 个边表结点。空间复杂度O(n+e)
- 无向图：邻接表表示中有n 个顶点和2e 个边表结点，有向图，有n 个顶点和e 个边表结点。空间复杂度O(n+e)
- n 个顶点的连通图至少有n-1条边。
- 各种排序方法的比较
方法 类型 稳定性
最好 平均 最坏 空间 直插 插入
稳定 O(n) O(n 2) O(1) 直选 选择 不稳定 O(n 2) 冒泡 交换 稳定 O(n)
O(n 2) 希尔 插入 不稳定 n 1.25
快速 交换 不稳定 O(nlgn) O(n 2) Olgn
- 作者:Maynor
- 链接:https://maynor1024.live/article/2dd1f390-6aa9-8133-aa99-c9d14a3fc480
- 声明:本文采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。
