数据结构笔记1

1.a(中序)+b(前序) 方法是找到根节点
层序+后序 层序的一个是根节点
2.线索二叉树
中序线索二叉树
定义
typedef struct ThreadNode{
int data;
struct ThreadNode *lchild,*rchild;
int ltag,rtag; //是否有左右线索 (0 1)

}ThreadNode,*ThreadTree;
3.怎么解决中死循环问题要用tag判断
4.用pre全局变量来记录前面的节点

5.树的方法 双亲表示法(顺序存储)
孩子表示法(顺序+链)
孩子兄弟(链)
6.10.10森林和二叉树的转换
7.森林先序遍历(转换为二叉树)=变为二叉树的先序遍历
8.二叉排序树(查找树) 左子树节点值<根节点值<右子树节点值
19
13 23
11 12 21 25
1.非递归 o(1) 用while循环 根据他的大小 从头按方向走
删除:注意删除非叶子节点 删除有孩子的要使用它的孩子的左孩子代替,或者左子树的右孩子
平均查找长度
2.递归 空间复杂度o(n) 往深处走

9.平衡二叉树(在二叉排序树基础上) 简称平衡树avl树 树上的任一节点的左子树和右子树的高度之差不超过1
节点的平衡因子:左子树-右子树高(除了它的 接下来的节点的全部高度) 只可能是 -1 0 1
改变最小不平衡子树 原来树根连接子节点,后改变树根
左孩子只能右旋 右孩子只能左旋
10.哈夫曼树(最优二叉树) 节点的权:节点的重要性
节点的带权路径长度:树根到该节点 该节点上权值
在节点10的带权路径为 22=20
带权路径长度:叶子节点的带权路径全部相加:11+22+3*2
带权路径长度最小的二叉树是哈夫曼树

 1

1 4
2 3

11.构造哈夫曼树(特点:带权路径最短)
a->1 b->3 c->2 d->7 e->2
1.选择两个最小的节点
1 2
2.把他们相加生成一个除这些以外的节点
3
1 2
3.继续选择两个最小的节点(包括新生成的节点)在加起来生成新节点
5
3 2
1 2
4.继续上面步骤(翻转一下得到正确的顺序)
15
8 7
5 3
3 2
1 2
12.哈夫曼编码压缩(用左右节点为0和1)字符集的每个字符作为一个叶子节点
固定长度编码–每个字符用 相等长度 的二进制表示 00 10 11 01
可变长度编码–允许不同字符用不等长的二进制位表示 00 111 010 00
前缀编码:没有其他编码的前缀 10 01

13.图(每根线都必须有节点)
图G由顶点集V和边集E组成
|V|表示图G中顶点的个数S也称为图G的阶
|E|表示图中边的条数
A
B C D
E F
无向图 两个节点之间没有方向
有向图 弧尾(线的尾部) 弧头(箭头的头) 尾A–>B头 (可以有单个的节点)
简单图(也分无向和有向 重点探讨)
多重图(也分无向和有向)有节点自己连向自己
A–>A
14.有向图的:
度:有几条边
入度:进去的箭头有多少个 ID(v)=
出度:出去的箭头有多少个 OD(v)=
顶点v的度=入度+出度
图所有的度=2|E| 边
路径:顶点到另外顶点之间的一条路径是指顶点系列 入 c->a->b
回路:图形成一个环(圆)
简单路径:顶点不重复出现的称为简单路径(不重复走) c->a->c->d(x) c->a->d(对的)
简单回路:有上面同
路径长度:路径上 边 的数目
点到点的距离: 最短路径存在则称为u到v的距离 不存在路径记为无穷
强连通性:节点有进有出,无向图为连通
15. 2
(无向)连通图: 最少有n-1条边 最多有 C 条边
n-1
(有向)强连通图:只要全部边都有连通 最少有n条边
16.子图 图的一部分(有节点有边)
17.生成子图 有部分节点 但是可以少掉 部分边使顶点称为独立
18.(无向图)极大连通子图称为 连通分量(必须连通子图尽可能多的顶点和边)比如大陆 和台湾铁路网 都是连通分量
19.有向图 极大强连通子图 称为 强连通分量 他有尽可能的节点和边
20.生成树:(有图的全部节点,但是几条边没有连接)包括图中全部顶点的一个极小连通子图
21.生成森林(可以有许多分量组成,就是一个图分开来看包含生成树) 非连通图中, 连通分量的生成树 构成了非连通图的生成森林
22.边的权 美条边可以标上具有某种含义的值,他的值叫做 权值
带权图/网 --边上带有权值的图称为 带权网 也称网(有权值的线)
带权路径长度 一条路径上所有边的权值之和(北京(200km)到上海(300km) = 500km)
23特殊的图
1.无向完全图(边全部加上)
2.有向完全图(边全部加上而且有双箭头)
3.稀疏图 边很少的图(logn条)
4.稠密图 边很多的图
5.树 没有回路
6.森林

24.邻接矩阵o(n) 用一个一维数组记录数据 和 一个二维数组存放(0和1 1代表他们相连)
无向图: 度=第i行的非零元素个数(如下 求b的度1+1+1=3)
有向图:出度=第i行 的非零元素个数(从纵向到横向可以看出方向)
入度=第i列 的非零元素个数
A B C
A 0 1 1
B 1 1 1
C 1 0 1
25.带权图 在上面的基础上改为 加上权值和0(自己指向自己) 无穷(没有连接顶点)
26.邻接矩阵法的性质 2
1.平方后可以是算出 可通过的路径有多少条 A [1][4]=1行全部*第4列 4 A-D可能的路径有
27.邻接表法(指针指向并不唯一表示)(链表+顺序存储) 按照先后顺序(层次)存储表 0->a 1->b 2->c
a
b c
无向图(指针指向并不唯一表示):把全部的连接的节点相互指向 第一个节点是存储他的父亲
有向图: 节点之中有个存储^的 是代表有后继节点,没有为空 依次指向和上同
30.十字链表法(有向图) |data|firstint|firstout|
31.邻接多重表(无向图) 上同 利用数组 |i|j|info|
iLink| jLink

32.树的广度优先遍历(层序遍历) 不会回路 辅助队列
33.图的广度优先遍历(层序遍历) 要标记节点有没有被访问 问题无法遍历非连通图
34.广度优先生成树
35.广度优先生成森林
36.树的深度优先遍历(深入往子找,没有孩子去找兄弟)
37.图的应用 最小生成树(最小代价树)所有节点一定连通但是以最小路径代价到达
prim算法 1.找到连接所有节点的一个节点,然后围绕他找到最小的,对他周围的节点进行挑选 2.按照权值一 一连接 可能有多颗相同值的最小生成树(边多适合)
kruskal算法 1.先找到最小的边连通(连续连接) 2.如果前面两个节点已经连通 则不连通这个节点转而其他节点挑选
(边少适合)
38.最短路径
单源最短路径: 只有一个单独的源头 bfs广度优先算法
定义两个数组d一开始全部为无穷 path一开始全部为-1 要开始的顶点标记为 0,可以确定最短路径的路
dijkstra算法 final true/false dist[] 无穷代表找不到直接相连的路径 0代表要开始的节点 10代表最短路径(的权值)(是一个一个连接的节点加来的) path[] 找到的数组路径的最小长度(走的实现方案)
不适用用于负权值的带权图
每对顶点间的最短路径: floyd算法 在 允许一个中转点的时候 路径是否可以更短 A[][]初始化他的路径权值 path[][]初始化为-1 逐步更新两个数组 (解决了前面负值的问题 但 不适用用于负权值回路的带权图)

39. 有向无环图(解决上面(直接去掉不成环)成环的问题 合并重复节点)
    20.拓扑排序 aov网(必须有向无环) 定义 indegree[]各个节点入度的大小(可–删除) print[]记录拓扑排序序列 栈保存度为0的节点
    1.找一个没有前驱的节点,删除他的节点和边
    2.重复上面动作后直到不存在无前驱的顶点为止
    21.逆拓扑排序(出度数为0)深度优先实现
    22.关键路径 aoe(acticity on edge network)网:
    1.事件发生后才可以继续进行
    2.前面做的事情 全部 结束时,后面的才发生
    3.活动可以并行进行
    (源点 开始点)v1->v3->v4(汇点 结束点)
    v2/
    关键路径:最大长度的路径 上面的活动->关键活动
    活动的最早开始时间:活动弧的起点的最早发生时间 0
    活动的追迟发生时间:活动弧终点最迟发生时间-活动该活动需要的时间 4
    时间余量:能拖延的时间
    0 活动弧 4
    v1---->v2
    23.关键活动,关键路径的特性
    若关键活动增加,整个工程工期增长->反之减少
    关键活动 缩短 有可能变为 非关键活动
    可能有多条关键路径(就是同时做的事情) 改变一条路径 有可能不能缩短 时间

40. 查找:
    查找表:数据集(图结构)
    关键字:(微信号)字段中的值
    静态查找表: 只需要查找 符合条件的数据
    动态查找表: 插入 删除 某个数据元素
    查找长度:对比 关键字 的次数
    平均查找长度ASL: 关键字比较次数的平均值

25.顺序查找 通常用线性表 从头到尾遍历
哨兵(第一个0 为要查找的值) 从尾到头找
16 12 14 16
0 1 2 3
顺序查找(有序表)
1 2 3 4 16
(4-16)
26.折半查找(二分查找) 必须要有序 定义三个指针 low(头) (中间)mid=(low+high)/2 high(尾)
不断二分 直到low=high 再判断
high<low 查找失败
27.折半查找判定树
右子树节点数-左子树的节点数=0/1—>平衡二叉树
树高h=log2(n+1)
时间复杂度h=log2(n)

28.分块查找算法 建立索引表 声明他的区间范围和最大值(先折半) 最后顺序查找
如果超出范围则 查找失败
发生low>high 要在low里面查找
不存在时 会超出索引表值 判断不存在在 最大范围 后
直接退出
7 10 | 13 14 15 20| 22 23 30|
全部分多少块 根号2+1最快
29.(重要)B树(绝对平衡 有序的) 多路平衡查找树

1. 5阶b树:5个分叉的数
   2)根节点不是终端节点(末端的全部叶子节点),则至少有两颗子树.(要保证平衡必须同时有树)
   3)m叉查找树中,规定 除了根节点外(因为当有1 个节点做不到) ,任何节点 至少有[m/2]个分叉,既至少含有[m/2]-1个关键字
2. 所有叶子节点都出现在同一层，并且不带信息
   最小高度:h=log (n+1)/2+1
   [m/2]

30.b树插入 先在父亲插入一个 后插入元素到儿子 儿子满了使用二分法 把中间节点接到父亲 父亲满了往上分裂
删除 删除根节点元素 用 直接前驱(最下面最右边的元素)代替 或者 直接后继(最下面最左边的元素)代替
当节点小于2(5阶b树[m/2]-1<=n<=m-1)时要把节点的父亲借元素,父亲节点的右边的指针的第一个元素 顶替 父节点元素

31.b加树(支持顺序查找)
一颗m阶的b加树

1. 每个分支节点最多有m颗子树
   2.非叶根节点至少有两颗子树,其他每个分支节点至少有m/2颗子树
   3.节点的子树个数与关键字个数相等(叶子节点=关键字=全部数据在最后一层 上面只存放的是比较的数据(区间))
   15 56
   3 9 15 35 42 56
   1 3 6 8 9 13 15 30 35 40 42 47 48 50 56

32.b+树查找 只有到最下面一层才可以拿到数据

33.b+比较 b树
b:
1.n个 节点n+1个分叉
2.根节点的关键字数 1,m-1
3.其他节点关键字数 [m/2]-1,m-1
4.非叶节点的关键字 会出现在叶子节点上
5.各个节点都包含实际信息(存放地址)
b+:
1. n个节点 n个分叉
2.根节点的关键字数 1,m
3.其他节点关键字数 [m/2]-1,m
4.各节点包含的关键字不重复
5.上面的节点只是起到索引的作用,只有最下面的叶子节点包含实际信息

最后

以上就是生动乐曲为你收集整理的数据结构笔记1的全部内容，希望文章能够帮你解决数据结构笔记1所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。