开卷
# 数据结构定义
# 逻辑结构
- 集合结构
- 线型结构
- 树形结构
- 图形结构
# 物理结构
- 顺序存储结构
- 链接存储结构
# 抽象数据类型
# 算法
算法是解决特定问题求解步骤的描述,在计算机中表现为指令的有限序列,并且每条指令表示一个或多个操作。
# 算法的特性
- 输入、输出
- 具有0个或者过个输入,一点有输出。不输出结果,要算法何用
- 有穷性
- 算法在执行有限的步骤之后,自动结束而不会出现无限循环
- 具有在实际应用当中合理的、可以接受的“边界”
- 确定性
- 算法的每一步骤都具有确定的含义,不会出现二义性
- 算法在一定条件下,只有一条执行路径,相同的输入只能有唯一的输出结果。算法的每个步骤被精确定义而无歧义。
- 可行性
- 算法的每一步都必须是可行的,也就是说,每一步都能够通过执行有限次数完成。可行性意味着算法可以转换为程序上机运行,并得到正确的结果。
# 算法设计要求
- 正确性 (应该具有输入、输出和加工处理无歧义性、能正确反映问题的需求、能够得到问题的正确答案 )
- 算法程序没有语法错误。
- 算法程序对于合法的输入数据能够产生满足要求的输出结果。
- 算法程序对于非法的输入数据能够得出满足规格说明的结果。
- 算法程序对于精心选择的,甚至刁难的测试数据都有满足要求的输出结果
- 可读性:
- 算法设计的另一目的是为了便于阅读、理解和交流,可读性高有助于人们理解算法,晦涩难懂的算法往往隐含错误,不易被发现,并且难于调试和修改
- 健壮性
- 一个好的算法还应该能对输入数据不合法的情况做合适的处理
- 时间效率高和存储量低
- 时间效率指的是算法的执行时间,对于同一个问题,如果有多个算法能够解决, 执行时间短的算法效率高,执行时间长的效率低。
- 存储量需求指的是算法在执行过程中需要的最大存储空间, 主要指算法程序运行时所占用的内存或外部硬盘存储空间。
- 设计算法应该尽量满足时间效率高和存储量低的需求。
# 算法效率度量
- 事后统计方法
- 这种方法主要是通过设计好的测试程序和数据,利用计算机计时器对不同算法编制的程序的运行时间进行比较,从而确定算法效率的高低
- 受各种实际因数影响,不够科学
- 事前分析法
- 算法采用的策略、方法。
- 编译产生的代码质量。
- 问题的输入规模。
- 机器执行指令的速度。
- 抛开这些与计算机硬件、软件有关的因素,一个程序的运行时间,依赖于算法的好坏和问题的输入规模。( 输入规模是指输入量的多少)
# 函数的渐近增长
给定两个函数f(n)和g(n),如果存在一个整数N,使得对于所有的n>N,f(n)总是比g(n)大,那么,我们说f(n)的增长渐近快于g(n)。 从中我们发现,随着n的增大,后面的+3还是+1其实是不影响最终的算法变化的,例如算法A′与算法B′,所以,我们可以忽略这些加法常数。
次数 | 2n^2 | 3n+1 | 2n^2 + 3n +1 |
---|---|---|---|
n=1 | 2 | 4 | 6 |
n=5 | 50 | 16 | 66 |
n=10 | 200 | 31 | 231 |
n=100 | 2000 | 301 | 2301 |
n=1000 | 20000 | 3001 | 23001 |
n=10000 | 200000 | 30001 | 230001 |
n=100000 | 2000000 | 300001 | 2300001 |
# 时间复杂度
在进行算法分析时,语句总的执行次数T(n)是关于问题规模n的函数,进而分析T(n)随n的变化情况并确定T(n)的数量级。
算法的时间复杂度,也就是算法的时间量度,记作:T(n)=O(f(n))。它表示随问题规模n的增大,算法执行时间的增长率和f(n) 的增长率相同,称作算法的渐近时间复杂度,简称为时间复杂度。
其中f(n)是问题规模n的某个函数。
这样用大写O( )来体现算法时间复杂度的记法,我们称之为大O记法。
一般情况下,随着n的增大,T(n)增长最慢的算法为最优算法。
显然,由此算法时间复杂度的定义可知,我们的三个求和算法的时间复杂度分别 O(1)常数阶、O(n)线性阶、O(n2)平方阶
# 推导大O阶 (可能需要补数学了)
用常数1取代运行时间中的所有加法常数。
在修改后的运行次数函数中,只保留最高阶项。
如果最高阶项存在且不是1,则去除与这个项相乘的常数。
# 常见的时间复杂度
执行次数 | 函数阶 | 非正式术语 |
---|---|---|
12 | O(1) | 常数阶 |
2n+3 | O(n) | 线性阶 |
3n2+2n+1O | (n2 ) | 平方阶 |
5log2n+20O | (logn) | 对数阶 |
2n+3nlog2n+19O | (nlogn) | nlogn阶 |
6n3+2n2 +3n+4O | (n3 ) | 立方阶 |
2n | O(2n ) | 指数阶 |
对数
在数学中,对数是对求幂的逆运算,正如除法是乘法的逆运算,反之亦然。这意味着一个数字的对数是必须产生另一个固定数字(基数)的指数。
在简单的情况下,乘数中的对数计数因子。更一般来说,乘幂允许将任何正实数提高到任何实际功率,总是产生正的结果,因此可以对于b不等于1的任何两个正实数b和x计算对数。
如果a的x次方等于N(a>0,且a≠1),那么数x叫做以a为底N的对数(logarithm),记作x=loga N。其中,a叫做对数的底数,N叫做真数。
常用的时间复杂度所耗费的时间从小到大依次是:
O(1)<O(logn)<O(n)<O(nlogn)<O(n2)<O(n3)<O(2n)<O(n!)<O(nn)
# 最坏和平均
对算法的分析
一种方法是计算所有情况的平均值, 这种时间复杂度的计算方法称为平均时间复杂度。
另一种方法是计算最坏情况下的时间复杂度,这种方法称为最坏时间复杂度。
一般在没有特殊说明的情况下,都是指最坏时间复杂度
# 空间复杂度
算法的空间复杂度通过计算算法所需的存储空间实现,算法空间复杂度的计算公式记作:S(n)=O(f(n)),其中,n为问题的规模,f(n) 为语句关于n所占存储空间的函数。
# 数据结构
# 线型表
# 顺序存储
- 采用联系的存储单元依次存储元素
- 读取 O(1) (顺序读取)
- 插入需要移动元素 O(n)
- 需要需分配空间,容易造成资源浪费/溢出
# 链式存储
- 采用链式存储结构,可用任意一组存储单元存放元素
- 读取 O(n) (需要找头节点)
- 可直接插入到指定位置 O(1)
- 只要有足够的空间便可以分配,不受存储空间/个数限制
# 静态链表
- 采用下标和游标,下标代表当前节点位置,游标记录下一节点位置
- 下标0的游标记录第一个空闲空间的下标
- 下标最后一位的游标记录第一个可用元素的下标
- 插入修改只需要修改游标
- 失去了顺序存储结构随机存储的特性
# 循环链表
- 单链表的基础上,链接了头尾
- 采用尾指针表示循环列表
- 尾指针 lastIndex 复杂度 O(1), 头指针 lastIndex.next 复杂度 O(1)
如果还是用头指针表示循环列表呢
头指针 index 复杂度 O(1)
尾指针 遍历index到结尾indexN 复杂度O(N)
# 双向链表
- 解决链表next指针的特性,导致遍历单向性问题
- 采用双指针记录前后节点,代价变更时需要同时改变两个指针变量
# 栈与队列
# 何为栈?
栈(stack)是限定仅在表尾进行插入和删除操作的线性表。 我们把允许插入和删除的一端称为栈顶,另一端称为栈底,
不含任何数据元素的栈称为空栈。栈又称为后进先出的(LastIn First Out)线性表,简称LIFO结构。栈特殊之处就在于限制了这个线性表的插入和删除位置,它始终只在栈顶进行。
这也就使得:栈底是固定的,最先进栈的只能在栈底。
栈的插入操作,叫作进栈,也称压栈、入栈
栈的删除操作,叫作出栈,也有的叫作弹栈
# 顺序存储(顺序栈)
- 表头(index 0侧)为底,表尾为顶
- 需要指定栈大小(StackSize)
- top为栈顶下标, MAX(top) == StackSize -1
- 空栈 => top == -1
# 同类数据两栈共享
- 一个栈(A)底数组头部,另一个栈(B)底为数组尾部
- 当数组头部侧(A)栈顶指针+1 == 另一个栈顶指针时,为栈满
- 通常用于两个栈需求相反时,及A加B减,B加A减
# 链式存储 (链栈)
- 头部(头指针侧)为顶
- 无需指定栈大小 (栈链基本不存在占满问题,除非电脑死机)
- 空栈 => 同链表,头指针指向null,等同于top == null
# 队列
- 队列(queue)是只允许在一端进行插入操作,而在另一端进行删除操作的线性表。
- 队列是一种先进先出(First In First Out)的线性表,简称FIFO
- 允许插入的一端称为队尾,允许删除的一端称为队头
# 顺序存储(顺序队列)
- 基于线性表
- 入队时直接队尾插入数据,性能O(1),出队时移除队首数据,其他项向前移动,性能O(n)
# 循环队列
- 解决顺序队列出队时性能问题
定义头尾指针 ,front指针指向队头元素,rear指针指向队尾元素的下一个位置
入队时移动 rear 当移动到队尾时,队首有空间, rear可移动到队首
当移动到队为尾,队首无空间, 队列满
出队时移动 front队列满计算公式: (rear+1)%QueueSize==front
队列长度计算公式: (rear-front+QueueSize)%QueueSize
# 链式存储(链队列)
- 队列的链式存储结构,其实就是线性表的单链表,只不过它只能尾进头出而已,我们把它简称为链队列。
front指针指向链首,rear指针指向队尾元素的下一个位置
空列时 rear 指向 front
入队时 当前rear.next = 新节点 , 然后设置新节点为当前rear: rear = 新节点
出队时 头节点后续节点出列,front.next指向出列节点的后续例如: 头 > 1 > 2 > 3
头.next = 1 > 2 > 3
1.next = 2 > 3
出列时移除1 ,头.next = 1.next = 2 > 3
若链表除头结点外只剩一个元素时,则需将rear指向头结点
# 串
串(string)是由零个或多个字符组成的有限序列,又名叫字符串。
# KMP匹配算法
# 树
结点拥有的子树数称为结点的度(De-gree)。
度为0的结点称为叶结点(Leaf)或终端结点;
度不为0的结点称为非终端结点或分支结点。
除根结点之外,分支结点也称为内部结点。
树的度是树内各结点的度的最大值。
树中结点的最大层次称为树的深度(Depth)或高度,当前树的深度为4。
如果将树中结点的各子树看成从左至右是有次序的,不能互换的,则称该树为有序树,否则称为无序树。
森林(Forest)是m(m≥0)棵互不相交的树的集合。对树中每个结点而言,其子树的集合即为森林。
线性结构 | 树结构 |
---|---|
第一个节点无前驱 | 根节点无双亲,唯一 |
最后个节点无后继 | 叶节点,无孩子,多个 |
中间节点有前驱有后继 | 中间节点,一个双亲多个孩子 |
对于同级节点:称之为:兄弟
对于父节点:称之为:双亲
对于子节点: 称之为:孩子
对于子节点及以下: 称之为:子孙
# 双亲表示法
定义指针
data(节点数据)
parent(父节点,没有为-1)
firstChild (长子域,没有 -1 )
rightSid (右兄弟,没有 -1 )
关系如下:
下标 | data | parent | firstChild | rightSid |
---|---|---|---|---|
0 | A | -1 | 1 | -1 |
1 | B | 0 | 3 | 2 |
2 | C | 0 | 4 | -1 |
3 | D | 1 | 6 | -1 |
4 | E | 2 | 9 | 5 |
5 | F | 2 | -1 | -1 |
6 | G | 3 | -1 | 7 |
7 | H | 3 | -1 | 8 |
8 | I | 3 | -1 | -1 |
9 | J | 4 | -1 | -1 |
如此能快速找到节点的双亲和兄弟
如
index = 3 ,parent:2,rightSid=-1,firstChild =6
得到长子的兄弟
index = 6 ,rightSid=7
index = 7 ,rightSid=8
index = 8 ,rightSid=-1
最终得到 双亲为:3 ,无兄弟,子节点:6,7,8
如
index = 6 ,parent:3,rightSid=7 ,firstChild=-1
得到右兄弟的右兄弟
index = 7 ,rightSid=8
index = 8 ,rightSid=-1
最终得到 双亲为:3 ,兄弟为:7,8,无子节点
# 孩子表示法
- 一棵树有多个子树,每个子树都为一个链表,那么一棵树就是多重链表
- 一个链表的指针域的个数为树的度 (各个结点度的最大值)
表示
一棵树:
data > child1 > child2 > child3 > childN示例:
root-A > node-B > node-C
node-B > node-D
node-C > node-E > node-leaf--F
node-D > node-leaf-G > node-leaf-H > node-leaf-I
node-E > node-leaf-J指定空间开辟
root-A > 2 > node-B > node-C
node-B > 1 > node-D
node-C > 2 > node-E > node-leaf--F
node-D > 3 > node-leaf-G > node-leaf-H > node-leaf-I
node-E > 1 > node-leaf-J上例要维护度 既然要遍历树,将所以结果放入一个线性表如下:
0 root-A
1 node-B
2 node-C
3 node-D
4 node-E
5 node-leaf-F
6 node-leaf-G
7 node-leaf-H
8 node-leaf-I
9 node-leaf-J
....上例中我们能得到所有节点,但是无法得到子节点的关系
所以在每个线性节点建立一个单链表维护子节点关系0 root-A > 1 > 2
1 node-B > 3
2 node-C > 4 > 5
3 node-D > 6 > 7 > 8
4 node-E > 9
5 node-leaf-F
6 node-leaf-G
7 node-leaf-H
8 node-leaf-I
9 node-leaf-J如此我们就能快速查找到某个节点孩子或者是某个节点孩子的兄弟,但是我并不能得到节点的双亲
# 双亲孩子表示法
上例中的基础上结合双亲表示法
0 root-A [-1] > 1 > 2
1 node-B [0] > 3
2 node-C [0] > 4 > 5
3 node-D [1] > 6 > 7 > 8
4 node-E [2] > 9
5 node-leaf-F [2]
6 node-leaf-G [3]
7 node-leaf-H [3]
8 node-leaf-I [3]
9 node-leaf-J [4]
# 孩子兄弟表示法
当前根节点 长子节点(fistChild) 右兄弟节点 (rightSib) root-A > node-B > null
node-B > node-D > node-C
node-D > node-leaf-G > null
node-leaf-G > null > node-leaf-H
node-leaf-H > null > node-leaf-I
node-leaf-I > null > nullnode-C > node-E > null
node-E > node-leaf-J > node-leaf-F
node-leaf-J > null > null5 node-leaf-F > null > null
得到一个节点,能得到长子(fistChild)和右兄弟(rightSib)
得到所有儿子: 通过 fistChild 的 rightSib 一直遍历
得到所有兄弟: 通过自己的 rightSib 一直遍历
但是无法快速得到双亲
# 二叉树
- 只有两个分叉,所以叫二叉树 ,也就是是说不存在度大于2
- 分左树和右树,位置不同,意义不同
# 斜树
所有的节点都只有左子树的二叉树叫左斜树,所有节点都是只有右子树的二叉树叫右斜树,
斜树有很明显的特点,就是每一层都只有一个节点,节点的个数与二叉树的深度相同
线性表结构就可以理解为是树的一种极其特殊的表现形式
# 满二叉树
在一棵二叉树中,如果所有分支节点都存在左子树和右子树,并且所有叶子都在同一层上,这样的二叉树称为满二叉树。
特点
(1) 叶子只能出现在最下一层。出现在其他层就不可能达成平衡。
(2)非叶子节点的度一定是2。否则就是“缺胳膊少腿”了。
(3)在同样深度的二叉树中,满二叉树的节点个数最多,叶子数最多。
# 完全二叉树
对一棵具有n个节点的二叉树按层序编号,如果编号为i(1≤i≤n)的节点与同样深度的满二叉树中编号为i的节点在二叉树中位置完全相同,则这棵二叉树称为完全二叉树
满二叉树一定是一棵完全二叉树,但完全二叉树不一定是满的
特点 (1)叶子节点只能出现在最下两层。
(2)最下层的叶子一定集中在左部连续位置。
(3)倒数二层,若有叶子节点,一定都在右部连续位置。
(4)如果节点度为1,则该节点只有左孩子,即不存在只有右子树的情况。
(5)同样节点数的二叉树,完全二叉树的深度最小。 (反过来,多组节点相同的树里,深度最小的不一定是完全二叉数)
# 二叉树性质
- 性质1:在二叉树的第i层上至多有2^(i-1)个结点(i≥1)。
层数 | 公式 | 节点数 |
---|---|---|
1 | 2^(1-1) | 1 |
2 | 2^(2-1) | 2 |
3 | 2^(3-1) | 4 |
4 | 2^(4-1) | 8 |
5 | 2^(5-1) | 16 |
性质2:深度为k的二叉树至多有2^k-1个结点(k≥1)
深度 | 公式 | 节点数 |
---|---|---|
1 | 2^1-1 | 1 |
2 | 2^2-1 | 3 |
3 | 2^3-1 | 7 |
4 | 2^4-1 | 15 |
5 | 2^5-1 | 31 |
性质3: 对任何一棵二叉树T,如果其终端节点数(子节点)为n0,度为2的节点数为n2,则n0=n2+1。
性质4:具有n个结点的完全二叉树的深度为|log2n+1|(|x|表示不大于x的最大整数)。
由满二叉树的定义我们可以知道,深度为k的满二叉树的结点数n一定是2k-1。因为这是最多的结点个数。
那么对于n=2k-1倒推得到满二叉树的深度为k=log2(n+1),比如结点数为15的满二叉树,深度为4。
完全二叉树我们前面已经提到,它是一棵具有n个结点的二叉树,
若按层序编号后其编号与同样深度的满二叉树中编号结点在二叉树中位置完全相同,那它就是完全二叉树。也就是说,它的叶子结点只会出现在最下面的两层。
它的结点数一定少于等于同样深度的满二叉树的结点数2k-1,但一定多于2k-1-1。
即满足 2k-1-1<n≤2k-1。 由于结点数n是整数,n≤2k-1意味着n<2k,n>2k-1-1,意味着n≥2k-1,
所以2k-1≤n<2k,不等式两边取对数,得到k-1≤log2n<k,而k作为深度也是整数,因此k=|log2n|+1。
性质5:如果对一棵有n个结点的完全二叉树(其深度为)的结点按层序编号(从第1层到第层,每层从左到右),对任一结点i(1≤i≤n)有:
1.如果i=1,则结点i是二叉树的根,无双亲;如果i>1,则其双亲是结点。
2.如果2i>n,则结点i无左孩子(结点i为叶子结点);否则其左孩子是结点2i。
3.如果2i+1>n,则结点i无右孩子;否则其右孩子是结点2i+1。
# 二叉树存储性质
# 顺序存储
因为二叉树的性质,下标从上层到下层,同层级序号从左到右
满二叉数
0
1 2
3 4 5 6
表示
[0,1,3,4,5,6]
完全二叉数
0
1 2
3 4 ^ ^
表示
[0,1,3,4,^,^]
特殊二叉数
0
^ 2
^ ^ ^ 6
表示
[0,^,^,^,^,6]
如上,在二叉树不完整的情况下,顺序存储造成了大量资源的浪费,
所以顺序存储结构一般只用于完全二叉树
# 链式存储
# 二叉链表
[1,A,2]
[5,B,6] [7,C,^]
[^,D,^] [^,E,^] [^,F,^]
单链,分别设置两个指针指向孩子的下标,没有补^
# 三叉链表
[1,A,2,-1]
[5,B,6,1] [7,C,^,1]
[^,D,^,2] [^,E,^,2] [^,F,^,e]
单链,分别设置两个指针指向孩子的下标,没有补^
最后设置一直指针指向父亲下标,头结点为-1
# 二叉树的遍历
是指从根结点出发,按照某种次序依次访问二叉树中所有结点,使得每个结点被访问一次且仅被访问一次。
# 前序遍历
- 步骤1:节点是否为空,为空退出
- 打印当前节点
- 读取左子节点,重复步骤1
- 读取右子节点,重复步骤1
# 中序遍历
- 步骤1:节点是否为空,为空退出
- 读取左子节点,重复步骤1
- 打印当前节点
- 读取右子节点,重复步骤1
# 后序遍历
- 步骤1:节点是否为空,为空退出
- 读取左子节点,重复步骤1
- 读取右子节点,重复步骤1
- 打印当前节点
已知前序遍历序列和中序遍历序列,可以唯一确定一棵二叉树。 已知后序遍历序列和中序遍历序列,可以唯一确定一棵二叉树。
# 线索二叉树
对于普通的二叉树的链式存储,在左右节点无孩子的情况下会造成大量的资源浪费,如下:
[1,A,2]
[5,B,6] [7,C,^]
[^,D,^] [^,E,^] [^,F,^]
有7个^符号的资源浪费,此时我们知道每个节点的左右节点,但是不知道节点的前驱和后继
做如下改动:
设置两个tag位,为0时指向该结点的孩子,为1时指向该结点的前驱/后继
然后根据中序遍历,左^指向前驱,右^指向后继,首节点和尾节点补NULl
[1,0,A,0,2]
[5,0,B,0,6] [7,0,C,1,null]
[null,1,D,1,B] [B,1,E,1,A] [A,1,F,1,C]
此时发现 线程二叉树的遍历其实就是操作一个双向链表
和双向链表一样添加一个头节点
这样定义的好处就是我们既可以从第一个结点起顺后继进行遍历,也可以从最后一个结点起顺前驱进行遍历。
[0,0,头,1,C]
[1,0,A,0,2]
[5,0,B,0,6] [7,0,C,1,头]
[头,1,D,1,B] [B,1,E,1,A] [A,1,F,1,C]
# 树,二叉树,森林的转换
# 树 => 二叉树
- 加线:所有兄弟间连接一条线
- 去线:去除长子外孩子的线
- 调整结构层次,长子为二叉树左节点,兄弟为二叉树右节点
# 森林 => 二叉树
- 将森林的每颗 树 -> 二叉树
- 二叉树根节点互为兄弟,再右节点连接
# 二叉树 => 树
- 加线:将节点 与 左孩子的右孩子相连
- 曲线:将节点的 左孩子的右孩子取消连接
- 调整结构
# 二叉树 => 森林
- 将二叉树所有右节点取消连接,得到各个二叉树
- 二叉树 -> 树