数据结构与算法
数据结构与算法
0725 一 队列、链表
1.1 线性结构和非线性结构
- 线性结构
- 特点:一对一
- 顺序结构存储(数组)和链式存储结构(链表)
- 线性结构常见的有:数组、队列、链表和栈
- 非线性结构:
- 二维数组,多维数组,广义表,树结构,图结构
1.2 稀疏数组和队列
稀疏数组定义:当一个数组中大部分元素为0,或者为同一个值的数组时,可以使用稀疏数组来保存该数组。
稀疏数组的处理方法:
- 记录数组一共有几行几列,有多少个不同的值(第一个数据)
- 把具有不同值的元素的行列及值记录在一个小规模的数组中,从而缩小程序的规模
稀疏数组和二维数组的转换练习:day0725/sparseArray.java
- 队列定义:队列是一个有序列表,可以用数组或是链表来实现。
- 特点:先进先出,三个参数
maxSize,front,rear
- 因为队列的输出、输入是分别从前后端来处理,因此需要两个变量 front及rear分别记录队列前后端的下标,front 会随着数据输出而改变,而 rear则是随着数据输入而改变
- front指向队列第一个元素的前一位,rear指向队列的最后一位
- 当front==rear时,队列为空,当rear==maxSize时,队列满
- 采用环形队列以优化队列
- 调整:front指向队列的第一个元素,front初始值为0,rear指向队列的最后一个元素的后一位,rear初始值也为0
- 队列满条件:
(rear+1) % maxSize == front
- 队列空条件:
rear == front
- 队列中有效数据的个数:
(rear - front + maxSize) % maxSize//其实就是rear-front的绝对值
- 特点:先进先出,三个参数
1.3 单向链表
链表是有序的列表,是以节点的方式来存储,是链式存储。
每个节点包含 data 域, next 域:指向下一个节点。链表分带头节点的链表和没有头节点的链表
单链表的定义:day0725/singleLinkedListDemo.java
增:按顺序插入节点:day0725/singleLinkedListDemo.java其中的
addByOrder
方法修改节点
update
方法删除节点
delete
方法;被删除的节点,将不会有其他引用指向,将被垃圾回收获取链表倒数第k个元素:
接收head和index
先从头到尾遍历,得到总长度size
遍历得到第size-index个元素,则为倒数第k个元素
注:对index检验其是否合理
单链表的反转:
reverse
方法- 定义一个节点
reverseHead
为反转后的头 - 从头到尾遍历原链表,每遍历一个就将其取出,放在新链表最前端(类似于指定位置插入元素)
- 原链表中的元素
head.next = reverseHead.next
- 定义一个节点
从尾到头打印链表
- 方法1:先将单链表反转再打印,但是这样做会破坏单链表的结构
- 方法2:利用栈,将各个节点压入到栈内,利用栈先进后出的特点实现逆序打印
java.util.Stack类
1.4 双向链表
- 单向链表的查找方向只有一个,而双向链表可以向前或者向后查找。
- 单向链表不能自我删除,需要靠辅助节点 ,而双向链表,则可以自我删除,所以前面我们单链表删除时节点,总是找到temp,temp是待删除节点的前一个节点
- 结构:多了一个pre指向前一个节点
- 遍历:和单链表一样,只是可以向前或者向后
- 增:
- 找到最后一个节点
temp.next = newNode;
newNode.pre = temp;
- 删:
- 直线找到要删除的节点
temp.pre.next = temp.next;//temp为要删除的节点
temp.next.pre = temp.pre;
- 改:和单向链表一样
- 增删改查的代码实现:day0725/DoubleLinkedListDemo.java
1.5 单向环形问题和约瑟夫问题
约瑟夫问题
构建一个单向的环形链表思路
- 先创建第一个节点,让first指向该节点,并形成环形
- 后面每创建一个新的节点,就把该节点加入已有的环形链表中
遍历:
- 让第一个辅助指针(变量)
curBoy
指向first节点 - 然后通过while循环遍历该环形链表
curBoy.next == first
结束
- 让第一个辅助指针(变量)
约瑟夫问题的实现
创建一个辅助指针helper,事先指向环形链表的最后这个节点
当小孩报数的时候,让first和helper指针同时移动m-1次
这个时候将first指向的小孩节点出圈,
first = first.next;
hleper.next = first;
原来first指向的节点就没有任何用,就会被回收
0726 二 栈、前中后缀表达式、排序
2.1 栈(Stack)
先入后出
栈(stack)是限制线性表中元素的插入和删除只能在线性表的同一端进行的一种特殊线性表。允许插入和删除的一端,为变化的一端,称为栈顶(Top),另一端为固定的一端,称为栈底(Bottom)。
出栈(pop)和入栈(push)
应用
- 子程序的调用:在跳往子程序前,会先将下个指令的地址存到堆栈中,直到子程序执行完后再将地址取出,以回到原来的程序中
- 处理递归调用:和子程序的调用类似,只是除了储存下一个指令的地址外,也将参数、区域变量等数据存入堆栈中
- 表达式的转换
- 二叉树的遍历
- 图形的深度优先(depth一first)搜索法
栈的数组实现
- 定义一个top表示栈顶,初始化为-1
- 入栈操作:当有数据加入的时候,
top++;stack[top] = data;
- 出栈操作:
int value = stack[top];top--;return value;
栈实现综合计算器:使用栈完成一个表达式的结果:day0726/Calculator.java
//有括号不行
两个栈:数栈(存放数字)和符号栈(存放运算符)
创建一个index指针遍历表达式
//String str = "3+2*6-2";
如果是一个数字,就直接加入到数栈中
如果是一个符号,分为两种情况
- 当前符号栈为空,则直接加入到符号栈中
- 当前符号栈非空,进行比较:
- 当前符号的优先级<=栈中的操作符,就从数栈中pop出两个数字,从符号栈中pop出一个符号进行运算,将得到的结果入数栈,然后将当前操作符入符号栈
- 当前符号的优先级>栈中的操作符,则直接入栈
当表达式扫描完毕,就顺序从数栈和符号栈中pop出相应的数和符号并运算
注:数栈中依次pop出ab连个数字,符号栈中pop出xxx运算符,则结果为
bxxxa
最后数栈中只有一个结果,即表达式的结果
注:对于多位数的处理:判断下一个数字是否为运算符。如果是则加入,如果不是则进行拼接,然后下一步循环的时候再对下下个字符进行判断处理
2.2 前缀、中缀、后缀表达式
前缀表达式又称波兰式,前缀表达式的运算符位于操作数之前
(3+4)×5-6 对应的前缀表达式就是 -×+3456
前缀表达式求值:从右至左扫描表达式,遇到数字时,将数字压入堆栈,遇到运算符时,弹出栈顶的两个数,用运算符对它们做相应的计算(栈顶元素 和 次顶元素),并将结果入栈;重复上述过程直到表达式最左端,最后运算得出的值即为表达式的结果
1
2
3
4
5//(3+4)×5-6 对应的前缀表达式就是 -×+3456, 针对前缀表达式求值步骤如下
1.从右至左扫描,将6、5、4、3压入堆栈
2.遇到+运算符,因此弹出3和4(3为栈顶元素,4为次顶元素),计算出3+4的值,得7,再将7入栈
3.接下来是×运算符,因此弹出7和5,计算出7×5=35,将35入栈
4.最后是-运算符,计算出35-6的值,即29,由此得出最终结果中缀表达式:就是常见的运算表达式,如(3+4)×5-6
但是计算机不易识别,一般会转换为其他的表达式来处理(常转为后缀表达式)
后缀表达式:又称逆波兰表达式,与前缀表达式相似,只是运算符位于操作数之后
(3+4)×5-6 对应的后缀表达式就是34+5×6–
后缀表达式求值:从左至右扫描表达式,遇到数字时,将数字压入堆栈,遇到运算符时,弹出栈顶的两个数,用运算符对它们做相应的计算(次顶元素 和 栈顶元素),并将结果入栈;重复上述过程直到表达式最右端,最后运算得出的值即为表达式的结果
1
2
3
4
5
6
7//(3+4)×5-6 对应的后缀表达式就是 34+5×6-, 针对后缀表达式求值步骤如下
1.从左至右扫描,将3和4压入堆栈;
2.遇到+运算符,因此弹出4和3(4为栈顶元素,3为次顶元素),计算出3+4的值,得7,再将7入栈;
3.将5入栈;
4.接下来是×运算符,因此弹出5和7,计算出7×5=35,将35入栈;
5.将6入栈;
6.最后是-运算符,计算出35-6的值,即29,由此得出最终结果逆波兰计算机实现:day0726/PolandNatation.java
中缀表达式转后缀表达式:代码实现在
PolandNatation.java
的toInfixExpressionList
方法中1
2
3
4
5
6
7
8
9
10
11
12
131.初始化两个栈:运算符栈s1和储存中间结果的栈s2;
2.从左至右扫描中缀表达式;
3.遇到操作数时,将其压s2;
4.遇到运算符时,比较其与s1栈顶运算符的优先级:
4.1 如果s1为空,或栈顶运算符为左括号“(”,则直接将此运算符入栈;
4.2 否则,若优先级比栈顶运算符的高,也将运算符压入s1;
4.3 否则,将s1栈顶的运算符弹出并压入到s2中,再次转到(4.1)与s1中新的栈顶运算符相比较;
5.遇到括号时:
5.1 如果是左括号“(”,则直接压入s1
5.2 如果是右括号“)”,则依次弹出s1栈顶的运算符,并压入s2,直到遇到左括号为止,此时将这一对括号丢弃
6.重复步骤2至5,直到表达式的最右边
7.将s1中剩余的运算符依次弹出并压入s2
8.依次弹出s2中的元素并输出,结果的逆序即为中缀表达式对应的后缀表达式
2.3 递归(Recursion)的调用场景
- 递归解决的问题:8皇后问题 , 汉诺塔, 阶乘问题, 迷宫问题, 球和篮子的问题(google编程大赛)
- 各种算法中也会使用到递归,比如快排,归并排序,二分查找,分治算法等.
- 将用栈解决的问题—>递归代码比较简洁
递归的原则
- 执行一个方法时,就创建一个新的受保护的独立空间(栈空间)
- 方法的局部变量是独立的,不会相互影响, 比如n变量
- 如果方法中使用的是引用类型变量(比如数组),就会共享该引用类型的数据.
- 递归必须向退出递归的条件逼近,否则就是无限递归,出现StackOverflowError,死龟了:)
- 当一个方法执行完毕,或者遇到return,就会返回,遵守谁调用,就将结果返回给谁,同时当方法执行完毕或者返回时,该方法也就执行完毕
递归的内存
八皇后问题:
在8×8格的国际象棋上摆放八个皇后,使其不能互相攻击,即:任意两个皇后都不能处于同一行、同一列或同一斜线上,问有多少种摆法。
思路:
- 第一个皇后先放第一行第一列
- 第二个皇后放在第二行第一列、然后判断是否OK, 如果不OK,继续放在第二列、第三列、依次把所有列都放完,找到一个合适
- 继续第三个皇后,还是第一列、第二列……直到第8个皇后也能放在一个不冲突的位置,算是找到了一个正确解
当得到一个正确解时,在栈回退到上一个栈时,就会开始回溯,即将第一个皇后,放到第一列的所有正确解,全部得到.
然后回头继续第一个皇后放第二列,后面继续循环执行 1,2,3,4的步骤
八皇后问题实现:day0726/Queue8.java
说明:理论上应该创建一个二维数组来表示棋盘,但是实际上可以通过算法,用一个一维数组即可解决问题. arr[8] = {0 , 4, 7, 5, 2, 6, 1, 3} //对应arr 下标 表示第几行,即第几个皇后,arr[i] = val , val 表示第i+1个皇后,放在第i+1行的第val+1列
2.4 排序算法
- 直接插入、简单选择、冒泡比较常用
2.5 算法的时间复杂度
- 度量一个程序(算法)执行时间的两种方法
- 事后统计的方法
- 事前估算的方法
- 时间频度:一个算法中的语句执行次数称为语句频度或时间频度。记为
T(n)
一般情况下,算法中的基本操作语句的重复执行次数是问题规模n的某个函数,用
T(n)
表示,若有某个辅助函数f(n)
,使得当n趋近于无穷大时,T(n)/f(n)
的极限值为不等于零的常数,则称f(n)
是T(n)
的同数量级函数。记作T(n)=O(f(n))
,称O(f(n))
为算法的渐进时间复杂度,简称时间复杂度- 注:T(n) 不同,但时间复杂度可能相同。 如:
T(n)=n²+7n+6
与T(n)=3n²+2n+2
它们的T(n) 不同,但时间复杂度相同,都为O(n²)。 - 计算方法:
- 用常数1代替运行时间中的所有加法常数 T(n)=n²+7n+6 => T(n)=n²+7n+1
- 修改后的运行次数函数中,只保留最高阶项 T(n)=n²+7n+1 => T(n) = n²
- 去除最高阶项的系数 T(n) = n² => T(n) = n² => O(n²)
- 注:T(n) 不同,但时间复杂度可能相同。 如:
常见时间复杂度
常数阶
O(1)
:无论代码执行了多少行,只要是没有循环等复杂结构,那这个代码的时间复杂度就都是O(1)对数阶
O(log2n)
:线性阶
O(n)
:for循环里面的代码会执行n遍,因此它消耗的时间是随着n的变化而变化的,因此这类代码都可以用O(n)来表示它的时间复杂度线性对数阶
O(nlogN)
:线性对数阶O(nlogN)
其实非常容易理解,将时间复杂度为O(logn)
的代码循环N遍的话(while套在for循环里面)那么它的时间复杂度就是n * O(logN)
,也就是了O(nlogN)
平方阶
O(n2)
:将O(n)
内代码嵌套一遍(两个for循环)立方阶、k次方阶:相当于k个for循环嵌套
常见排序算法的时间复杂度
2.6 算法空间复杂度
一个算法的空间复杂度(Space Complexity)定义为该算法所耗费的存储空间,它也是问题规模n的函数。
在做算法分析时,主要讨论的是时间复杂度。从用户使用体验上看,更看重的程序执行的速度。一些缓存产品(redis, memcache)和算法(基数排序)本质就是用空间换时间。
2.7 冒泡排序
- 通过对待排序序列从前向后(从下标较小的元素开始),依次比较相邻元素的值,若发现逆序则交换,使值较大的元素逐渐从前移向后部,就象水底下的气泡一样逐渐向上冒。
- 冒泡排序的实现:day0726/BubbleSort.java
- 冒泡排序的优化:因为排序的过程中,各元素不断接近自己的位置,如果一趟比较下来没有进行过交换,就说明序列有序,因此要在排序过程中设置一个标志flag判断元素是否进行过交换。从而减少不必要的比较。
2.8 选择排序
选择式排序也属于内部排序法,是从欲排序的数据中,按指定的规则选出某一元素,再依规定交换位置后达到排序的目的。
比如第一次选出最小的和第一个元素交换位置,第二次再选出剩下的最小的和第二个元素交换位置,以此类推
冒泡排序的实现:day0726/SelectSort.java
0727 三 排序、查找、哈希表
3.1 插入排序
把n个待排序的元素看成为一个有序表和一个无序表,开始时有序表中只包含一个元素,无序表中包含有n-1个元素,排序过程中每次从无序表中取出第一个元素,把它的排序码依次与有序表元素的排序码进行比较,将它插入到有序表中的适当位置,使之成为新的有序表。
思路图
插入排序的实现:day0726/InsertSort.java
插入排序的缺陷:当(从小到大排)插入的数较小,需要遍历的次数多,会导致插入排序的时间增加
希尔排序(缩小增量排序):希尔排序是把记录按下标的一定增量分组,对每组使用直接插入排序算法排序;随着增量逐渐减少,每组包含的关键词越来越多,当增量减至1时,整个文件恰被分成一组,算法便终止
希尔排序的实现(里面有交换式和移位式):day0726/SheelSort.java
3.2 快速排序
- 是对冒泡排序的一种改进
- 思想:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列
- 快速排序的实现:day0726/QuickSort.java
3.3 归并排序
分而治之
重点为“治”的过程:将两个有序子序列合并为一个有序序列
3.4 基数排序(桶排序)
基数排序是桶排序的扩展
基本思想:将所有待比较数值统一为同样的数位长度,数位较短的数前面补零。然后,从最低位开始,依次进行一次排序。这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列
过程:
基数排序的实现:day0726/RadixSort.java
说明:
- 基数排序是对传统桶排序的扩展,速度很快
- 基数排序是经典的空间换时间的方式,占用内存很大, 当对海量数据排序时,容易造成
OutOfMemoryError
。 - 有负数的数组,我们不用基数排序来进行排序,如果要支持负数,参考:https://code.i-harness.com/zh-CN/q/e98fa9
- 基数排序时稳定的。[注:假定在待排序的记录序列中,存在多个具有相同的关键字的记录,若经过排序,这些记录的相对次序保持不变,即在原序列中,r[i]=r[j],且r[i]在r[j]之前,而在排序后的序列中,r[i]仍在r[j]之前,则称这种排序算法是稳定的;否则称为不稳定的]
3.5 常用排序算法对比
3.6 查找算法
常用查找
- 顺序(线性)查找
- 二分查找/折半查找
- 插值查找
- 斐波那契查找
顺序(线性)查找:就是遍历搜索查找,直到找到想要的返回值 3.7 二分查找‘
二分查找:对于有序数组而言,每次从中间分开找
mid = (left+right)/2
(向下取整),直到得到想要的值- 结束递归的条件:找到了想要的值;递归完了整个数组
left > right
- 二分查找的实现:day0726/BinartSearch.java
- 结束递归的条件:找到了想要的值;递归完了整个数组
插值查找:插值查找算法类似于二分查找,不同的是插值查找每次从
自适应mid
处开始查找注:
low
为left
,high
为right
,key
为待查找值- 对于数据量较大,关键字分布比较均匀的查找表来说,采用插值查找速度较快。
- 数据分布不均匀的情况下,该方法不一定比折半查找要好
斐波那契查找(黄金分隔法):
- 斐波那契数列:
F[k]=F[k-1]+F[k-2]
- 斐波那契查找原理与前两种相似,仅仅改变了中间结点(mid)的位置,mid不再是中间或插值得到,而是位于黄金分割点附近,即
mid=low+F(k-1)-1
- 但顺序表长度n不一定刚好等于F[k]-1,所以需要将原来的顺序表长度n增加至F[k]-1。这里的k值只要能使得F[k]-1恰好大于或等于n即可,由以下代码得到,顺序表长度增加后,新增的位置(从n+1到F[k]-1位置),都赋为n位置的值即可。
- 斐波那契查找的实现:day0726/FibonacciSearch.java
- 斐波那契数列:
3.7 哈希表
散列表(Hash table,也叫哈希表),是根据关键码值(Key value)而直接进行访问的数据结构。也就是说,它通过把关键码值映射到表中一个位置来访问记录,以加快查找的速度。这个映射函数叫做散列函数,存放记录的数组叫做散列表。
形式:数组+链表或者数组+二叉树
使用链表实现哈希表,该链表不带表头(即第一个数据就存放员工信息)
使用哈希表来实现增删改查:day0726/HashTabDemo.java
0728 四 二叉树、堆、赫夫曼树
4.1 树结构
常见数据结构特点:
- 数组:优点:通过下标方式访问元素,速度快。对于有序数组,还可使用二分查找提高检索速度。
缺点:如果要检索具体某个值,或者插入值(按一定顺序)会整体移动,效率较低
- 链式存储:优点:在一定程度上对数组存储方式有优化(比如:插入一个数值节点,只需要将插入节点,链接到链表中即可, 删除效率也很好)。
缺点:在进行检索时,效率仍然较低,比如(检索某个值,需要从头节点开始遍历)
- 树存储:能提高数据存储,读取的效率, 比如利用 二叉排序树(Binary Sort Tree),既可以保证数据的检索速度,同时也可以保证数据的插入,删除,修改的速度。
- 数组:优点:通过下标方式访问元素,速度快。对于有序数组,还可使用二分查找提高检索速度。
树结构示意图:
4.2 二叉树
每个节点最多只能有两个子节点的一种形式称为二叉树
二叉树的子节点分为左节点和右节点
如果该二叉树的所有叶子节点都在最后一层,并且
结点总数= 2^n -1
, n 为层数,则我们称为满二叉树如果该二叉树的所有叶子节点都在最后一层或者倒数第二层,而且最后一层的叶子节点在左边连续,倒数第二层的叶子节点在右边连续,我们称为完全二叉树
二叉树的遍历方式:前序、中序、后序遍历
前序遍历:先输出父节点,再遍历左子树和右子树
中序遍历:先遍历左子树,再输出父节点,再遍历右子树
后序遍历:先遍历左子树,再遍历右子树,最后输出父节点
注:看输出父节点的顺序,就确定是前序,中序还是后序
二叉树节点遍历的实现:day0728/BinaryTreeDemo.java
二叉树值的前中后序查找:day0728/BinaryTreeDemo.java
删除:day0728/BinaryTreeDemo.java
4.3 顺序存储二叉树
代码实现:day0728/ArrBinaryTreeDemo.java
4.4 线索化二叉树
线索化二叉树的提出
思路分析
不同的遍历方式会产生不同的线索二叉树(前序遍历产生前序线索二叉树)
代码实现:day0728/ThreadedBinaryTreeDemo.java
4.5 堆排序
堆排序是利用堆这种数据结构而设计的一种排序算法,堆排序是一种选择排序,它的最坏、最好平均时间复杂度均为O(nlogn),它也是不稳定排序。
一般用数组来表示堆,下标为 i 的结点的父结点下标为
(i-1)/2
;其左右子结点分别为(2i + 1)、(2i + 2)
堆是具有以下性质的完全二叉树:每个结点的值都大于或等于其左右孩子结点的值,称为大顶堆, 注意 : 没有要求结点的左孩子的值和右孩子的值的大小关系。
arr[i] >= arr[2*i+1] && arr[i] >= arr[2*i+2]
每个结点的值都小于或等于其左右孩子结点的值,称为小顶堆
arr[i] <= arr[2*i+1] && arr[i] <= arr[2*i+2]
堆排序的思想:
将待排序序列构造成一个大顶堆
此时,整个序列的最大值就是堆顶的根节点
将其与末尾元素进行交换,此时末尾就为最大值。
然后将剩余n-1个元素重新构造成一个堆,这样会得到n个元素的次小值。如此反复执行,便能得到一个有序序列了。
代码实现:day0728/HeapSort.java
4.6 赫夫曼树
给定n个权值作为n个叶子结点,构造一棵二叉树,若该树的带权路径长度(wpl)达到最小,称这样的二叉树为最优二叉树,也称为哈夫曼树(Huffman Tree), 还有的书翻译为霍夫曼树。
赫夫曼树是带权路径长度最短的树,权值较大的结点离根较近。
两个概念:
- 路径和路径长度:在一棵树中,从一个结点往下可以达到的孩子或孙子结点之间的通路,称为路径。通路中分支的数目称为路径长度。若规定根结点的层数为1,则从根结点到第L层结点的路径长度为L-1
- 结点的权及带权路径长度:若将树中结点赋给一个有着某种含义的数值,则这个数值称为该结点的权。结点的带权路径长度为:从根结点到该结点之间的路径长度与该结点的权的乘积
树的带权路径长度:树的带权路径长度规定为所有叶子结点的带权路径长度之和,记为WPL(weighted path length) ,权值越大的结点离根结点越近的二叉树才是最优二叉树。
赫夫曼树的构造:
- 从小到大进行排序, 将每一个数据,每个数据都是一个节点 , 每个节点可以看成是一颗最简单的二叉树
- 取出根节点权值最小的两颗二叉树
- 组成一颗新的二叉树, 该新的二叉树的根节点的权值是前面两颗二叉树根节点权值的和
- 再将这颗新的二叉树,以根节点的权值大小 再次排序, 不断重复 1-2-3-4 的步骤,直到数列中,所有的数据都被处理,就得到一颗赫夫曼树
- 赫夫曼树的构建代码实现:day0728/HuffmanTree.java
4.7 赫夫曼编码
赫夫曼编码也翻译为 哈夫曼编码(Huffman Coding),又称霍夫曼编码,是一种编码方式, 属于一种程序算法
赫夫曼编码是赫哈夫曼树在电讯通信中的经典的应用之一
赫夫曼编码广泛地用于数据文件压缩。其压缩率通常在20%-90%之间
赫夫曼码是可变字长编码(VLC)的一种。Huffman于1952年提出一种编码方法,称之为最佳编码
通讯领域编码的三种方式:
- 定长编码
- 变长编码
- 赫夫曼编码
赫夫曼编码过程:
赫夫曼编码实现文件压缩:day0728/huffmanCode
0729 五 赫夫曼编码的数据压缩和解压、二叉排序树
5.1 数据解压
- 编码的逆操作
- 赫夫曼编码实现文件解压:day0728/huffmanCode
- 赫夫曼编码实现文件压缩与解压:day0728/huffmanCode
5.2 赫夫曼编码压缩文件注意事项
- 如果文件本身就是经过压缩处理的,那么使用赫夫曼编码再压缩效率不会有明显变化, 比如视频,ppt 等等文件
- 赫夫曼编码是按字节来处理的,因此可以处理所有的文件(二进制文件、文本文件)
- 如果一个文件中的内容,重复的数据不多,压缩效果也不会很明显
5.2 二叉排序树(BST)
使用数组、链表在查询和增删都各有优缺,用二叉排序树更好
二叉排序树BST: (Binary Sort(Search) Tree), 对于二叉排序树的任何一个非叶子节点,要求左子节点的值比当前节点的值小,右子节点的值比当前节点的值大。
注:如果有相同的值,可以将该节点放在左子节点或右子节点
二叉排序树的创建和遍历:day0729/BinarySortTreeDemo.java
二叉树的删除
删除叶子节点 (比如:2, 5, 9, 12)
- 找到targetNode
- 找到targetNode的父节点parent
- 确定targetNode是parent的左子节点还是右子节点
- 根据前面的情况删除
删除只有一颗子树的节点 (比如:1)
找到targetNode和parent
确定targetNode是parent的左子节点还是右子节点
确定targetNode的子节点是左子节点还是右子节点
若targetNode有左子节点
- targetNode为parent的左子节点:
parent.left = targetNode.left
- targetNode为parent的右子节点:
parent.right= targetNode.left
- targetNode为parent的左子节点:
若targetNode有右子节点
- targetNode为parent的左子节点:
parent.left = targetNode.right
- targetNode为parent的右子节点:
parent.right= targetNode.right
- targetNode为parent的左子节点:
删除有两颗子树的节点(比如:7, 3,10 )
- 找到targetNode和parent
- 确定targetNode是parent的左子节点还是右子节点
- 从targetNode的右子树找到最小的节点或者左子树最大的节点
- 用一个临时变量将最小节点的值保存
- 删除最小节点
targetNode.value = temp
0730 六 AVL树、多路查找树、图、常用十算法
6.1 平衡二叉树(AVL树)
BST的缺点
平衡二叉树也叫平衡二叉搜索树(Self-balancing binary search tree)又被称为AVL树, 可以保证查询效率较高
特点:它是一 棵空树或它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一棵平衡二叉树。平衡二叉树的常用实现方法有红黑树、AVL(算法)、替罪羊树、Treap、伸展树等。
(前两个是AVL树,第三个不是,因为高度差为2)
构建平衡二叉树
:day0730/AVLTreeDemo.java
左旋转
- ```java
//创建新节点,值为当前节点的值
//把新的节点的左子树设为当前节点的左子树
//把新节点的右子树设为当前节点的右子树的左子树
//把当前节点的值换成右子树的值
//把当前节点的右子树设置成右子树的右子树
//把当前节点的左子树设为新的节点1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
![image-20220730141952800](/TyporaImg/数据结构与算法.assets/image-20220730141952800.png)
- 右旋转
![image-20220730142147504](/TyporaImg/数据结构与算法.assets/image-20220730142147504.png)
- 双旋转:某些情况下,单旋转不能完成平衡二叉树的转换
1. 当符合右旋转条件时
2. 如果左子树的右子树大于它的左子树高度
3. 先对这个节点的左节点进行左旋转
4. 再对当前节点进行右旋转
![image-20220730151113211](/TyporaImg/数据结构与算法.assets/image-20220730151113211.png)
#### 6.2 多路查找树
- 二叉树的问题:当节点较多的时候:
- 多次I/O操作读取
- 高度变高导致速度降低
- 引入多叉树:
- 如2-3树、2-3-4树
![image-20220730182350142](/TyporaImg/数据结构与算法.assets/image-20220730182350142.png)
- B树
- 2-3树
- 最简单 B树
- 特点:
- 2-3树的所有叶子节点都在同一层.(只要是B树都满足这个条件)
- 有两个子节点的节点叫二节点,二节点要么没有子节点,要么有两个子节点
- 有三个子节点的节点叫三节点,三节点要么没有子节点,要么有三个子节点
- 2-3树是由二节点和三节点构成的树
- 2-3树的构建过程
- 插入数据的规则:当不满足前三个特点的时候,就需要拆,先向上拆,如果上层满,则拆本层,拆后仍需要满足上面三个条件。
![image-20220730183836147](/TyporaImg/数据结构与算法.assets/image-20220730183836147.png)
![image-20220730183925033](/TyporaImg/数据结构与算法.assets/image-20220730183925033.png)
- B树
- B-tree树即B树,B即Balanced,平衡的意思。有人把B-tree翻译成B-树,容易让人产生误解。会以为B-树是一种树,而B树又是另一种树。实际上,B-tree就是指的B树。
- B树的阶:节点的最多子节点个数。比如2-3树的阶是3,2-3-4树的阶是4
- B树的搜索,从根结点开始,对结点内的关键字(有序)序列进行二分查找,如果命中则结束,否则进入查询关键字所属范围的儿子结点;重复,直到所对应的儿子指针为空,或已经是叶子结点
- 关键字集合分布在整颗树中, 即叶子节点和非叶子节点都存放数据.
- 搜索有可能在非叶子结点结束
- 其搜索性能等价于在关键字全集内做一次二分查找
![image-20220730184218884](/TyporaImg/数据结构与算法.assets/image-20220730184218884.png)
- B+树
- 是B树的变体
- 所有数据都只在叶子节点中
- 所有关键字都出现在叶子结点的链表中(即数据只能在叶子节点[也叫稠密索引]),且链表中的关键字(数据)恰好是有序的。
- 非叶子结点相当于是叶子结点的索引(稀疏索引),叶子结点相当于是存储(关键字)数据的数据层
- 更适合文件索引系统
- B树和B+树各有自己的应用场景,不能说B+树完全比B树好,反之亦然.
![image-20220730184405939](/TyporaImg/数据结构与算法.assets/image-20220730184405939.png)
- B*树
- 是B+树的变体
- B树定义了非叶子结点关键字个数至少为(2/3)M,即块的最低使用率为2/3,而B+树的块的最低使用率为B+树的1/2。(这里M是它的度:节点的度指的是结点拥有的子树的数目。. 而整棵树的度指的是树中结点的最大的度)
- 从第1个特点我们可以看出,B*树分配新结点的概率比B+树要低,空间使用率更高
![image-20220730184936013](/TyporaImg/数据结构与算法.assets/image-20220730184936013.png)
#### 6.3 图
- 线性表局限于一个直接前驱和一个直接后继的关系,树也只能有一个直接前驱也就是父节点,当我们需要表示多对多的关系时, 这里我们就用到了图
- 图是一种数据结构,其中结点可以具有零个或多个相邻元素。两个结点之间的连接称为边。 结点也可以称为顶点
- 常用概念:
- 顶点(vertex)
- 边(edge)
- 路径
- 无向图与有向图
- 带权图
- 图的表示方式:
- 二维数组(邻接矩阵)
![image-20220730185855050](/TyporaImg/数据结构与算法.assets/image-20220730185855050.png)
- 链表(邻接表)
- 邻接矩阵需要为每个顶点都分配n个边的空间,其实有很多边都是不存在,会造成空间的一定损失
- 邻接表的实现只关心存在的边,不关心不存在的边。因此没有空间浪费,邻接表由数组+链表组成![image-20220730185955246](/TyporaImg/数据结构与算法.assets/image-20220730185955246.png)
- 图的创建和代码实现:<u>*day0730/Graph.java*</u>
#### 6.4 图的深度优先遍历算法(DFS: Depth First Search)
- 从初始访问结点出发,初始访问结点可能有多个邻接结点,深度优先遍历的策略就是首先访问第一个邻接结点,然后再以这个被访问的邻接结点作为初始结点,访问它的第一个邻接结点, 可以这样理解:每次都在访问完当前结点后首先访问当前结点的第一个邻接结点
- 我们可以看到,这样的访问策略是优先往纵向挖掘深入,而不是对一个结点的所有邻接结点进行横向访问
- 步骤:
1. 访问初始结点v,并标记结点v为已访问。
2. 查找结点v的第一个邻接结点w。
3. 若w存在,则继续执行4,如果w不存在,则回到第1步,将从v的下一个结点继续。
4. 若w未被访问,对w进行深度优先遍历递归(即把w当做另一个v,然后进行步骤abc)。
5. 查找结点v的w邻接结点的下一个邻接结点,转到步骤3。
- 代码实现:<u>*day0730/Graph.java*</u>
#### 6.5 图的广度优先遍历算法(BFS: Broad First Search)
- 类似于一个分层搜索的过程,广度优先遍历需要使用一个队列以保持访问过的结点的顺序,以便按这个顺序来访问这些结点的邻接结点
- 步骤
1. 访问初始结点v并标记结点v为已访问。
2. 结点v入队列
3. 当队列非空时,继续执行,否则算法结束。
4. 出队列,取得队头结点u。
5. 查找结点u的第一个邻接结点w。
6. 若结点u的邻接结点w不存在,则转到步骤3;否则循环执行以下三个步骤:
- 6.1 若结点w尚未被访问,则访问结点w并标记为已访问。
- 6.2 结点w入队列
- 6.3 查找结点u的继w邻接结点后的下一个邻接结点w,转到步骤6。
- 代码实现:<u>*day0730/Graph.java*</u>
#### 6.6 常用十算法 1二分查找算法(非递归)
- 二分查找法只适用于从有序的数列中进行查找(比如数字和字母等),将数列排序后再进行查找
- 二分查找法的运行时间为对数时间O(㏒₂n) ,即查找到需要的目标位置最多只需要㏒₂n步,假设从[0,99]的队列(100个数,即n=100)中寻到目标数30,则需要查找步数为㏒₂100 , 即最多需要查找7次( 2^6 < 100 < 2^7)
- 代码实现:<u>*Algorithm/BinarySearchNoRecur.java*</u>
#### 6.7 常用十算法 2分治算法
- 分治法是一种很重要的算法。字面上的解释是“分而治之”,就是把一个复杂的问题分成两个或更多的相同或相似的子问题,再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解,原问题的解即子问题的解的合并。这个技巧是很多高效算法的基础,如排序算法(快速排序,归并排序),傅立叶变换(快速傅立叶变换)……
- 经典问题:二分搜索、大整数乘法、棋盘覆盖、合并排序、快速排序、线性时间选择、最接近点对问题、循环赛日程表、汉诺塔
- 分治算法设计模式
```java
if |P|≤n0
then return(ADHOC(P))
//将P分解为较小的子问题 P1 ,P2 ,…,Pk
for i←1 to k
do yi ← Divide-and-Conquer(Pi) 递归解决Pi
T ← MERGE(y1,y2,…,yk) 合并子问题
return(T)
- ```java
代码实现哈诺塔问题:Algorithm/Hanoitower.java
6.8 动态规划算法
动态规划(Dynamic Programming)算法的核心思想是:将大问题划分为小问题进行解决,从而一步步获取最优解的处理算法
动态规划算法与分治算法类似,其基本思想也是将待求解问题分解成若干个子问题,先求解子问题,然后从这些子问题的解得到原问题的解。
与分治法不同的是,适合于用动态规划求解的问题,经分解得到子问题往往不是互相独立的。 ( 即下一个子阶段的求解是建立在上一个子阶段的解的基础上,进行进一步的求解 )
动态规划可以通过填表的方式来逐步推进,得到最优解
01背包问题实现:Algorithm/KnapsackProblem.java
思路:每次遍历到的第i个物品,根据w[i]和v[i]来确定是否需要将该物品放入背包中。即对于给定的n个物品,设v[i]、w[i]分别为第i个物品的价值和重量,C为背包的容量。再令v[i][j]表示在前i个物品中能够装入容量为j的背包中的最大价值。则我们有下面的结果:
v[i][0]=v[0][j]=0; //表示填入表第一行和第一列是0
当w[i]> j 时:v[i][j]=v[i-1][j] // 当准备加入新增的商品的容量大于当前背包的容量时,就直接使用上一个单元格的装入策略
当j>=w[i]时: v[i][j]=max{v[i-1][j], v[i]+v[i-1][j-w[i]]} // 当准备加入的新增的商品的容量小于等于当前背包的容量,
装入的方式:
v[i-1][j]: 就是上一个单元格的装入的最大值
v[i] : 表示当前商品的价值
v[i-1][j-w[i]] : 装入i-1商品,到剩余空间j-w[i]的最大值
当j>=w[i]时: v[i][j]=max{v[i-1][j], v[i]+v[i-1][j-w[i]]} :
另一种理解方式:
最优解的回溯:
0731 五 常用十算法
5.1 KMP算法
- 查找字符产出现的最早位置
- 暴力匹配算法
- KMP算法解释:https://www.cnblogs.com/zzuuoo666/p/9028287.html
- http://www.ruanyifeng.com/blog/2013/05/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm.html(简版)
- 主要是部分匹配表的推算
- KMP算法实现:Algorithm/KMP.java
5.2 贪心算法
贪婪算法(贪心算法)是指在对问题进行求解时,在每一步选择中都采取最好或者最优(即最有利)的选择,从而希望能够导致结果是最好或者最优的算法
贪婪算法所得到的结果不一定是最优的结果(有时候会是最优解),但是都是相对近似(接近)最优解的结果
贪心算法应用:广播台集合覆盖
- 遍历所有的广播电台, 找到一个覆盖了最多未覆盖的地区的电台(此电台可能包含一些已覆盖的地区,但没有关系)
- 将这个电台加入到一个集合中(比如ArrayList), 想办法把该电台覆盖的地区在下次比较时去掉。
- 重复第1步直到覆盖了全部的地区
代码实现:Algorithm/Greedy.java
5.3 普利姆算法
修路问题本质就是最小生成树(MST)问题
最小生成树(Minimum Cost Spanning Tree):
- 给定一个带权的无向连通图,如何选取一棵生成树,使树上所有边上权的总和为最小,这叫最小生成树
- N个顶点,一定有N-1条边
- 包含全部顶点
- N-1条边都在图中
- 求最小生成树的算法主要是普里姆算法和克鲁斯卡尔算法
Prim算法介绍:
设G=(V,E)是连通网,T=(U,D)是最小生成树,V,U是顶点集合,E,D是边的集合
若从顶点u开始构造最小生成树,则从集合V中取出顶点u放入集合U中,标记顶点v的visited[u]=1
若集合U中顶点ui与集合V-U中的顶点vj之间存在边,则寻找这些边中权值最小的边,但不能构成回路,将顶点vj加入集合U中,将边(ui,vj)加入集合D中,标记visited[vj]=1
重复步骤②,直到U与V相等,即所有顶点都被标记为访问过,此时D中有n-1条边
代码实现:Algorithm/Prim.java
5.4 克鲁斯卡尔算法:http://c.biancheng.net/algorithm/kruskal.html
思路:按照权值从小到大的顺序选择n-1条边,并保证这n-1条边不构成回路
具体做法:首先构造一个只含n个顶点的森林,然后依权值从小到大从连通网中选择边加入到森林中,并使森林中不产生回路,直至森林变成一棵树为止
实现克鲁斯卡尔算法的难点在于“如何判断一个新边是否会和已选择的边构成环路”
选择加入的边的两个顶点不能指向同一个终点,否则将构成回路
代码实现:Algorithm/Kruskal.java
5.5 迪杰斯特拉算法
迪杰斯特拉(Dijkstra)算法是典型最短路径算法,用于计算一个结点到其他结点的最短路径。 它的主要特点是以起始点为中心向外层层扩展(广度优先搜索思想),直到扩展到终点为止。
算法过程:
- 设置出发顶点为v,顶点集合V{v1,v2,vi…},v到V中各顶点的距离构成距离集合Dis,Dis{d1,d2,di…},Dis集合记录着v到图中各顶点的距离(到自身可以看作0,v到vi距离对应为di)
- 从Dis中选择值最小的di并移出Dis集合,同时移出V集合中对应的顶点vi,此时的v到vi即为最短路径
- 更新Dis集合,更新规则为:比较v到V集合中顶点的距离值,与v通过vi到V集合中顶点的距离值,保留值较小的一个(同时也应该更新顶点的前驱节点为vi,表明是通过vi到达的)
- 重复执行两步骤,直到最短路径顶点为目标顶点即可结束
代码实现:Algorithm/Dijkstra.java
5.6 弗洛伊德算法(Floyd)
弗洛伊德算法(Floyd)计算图中各个顶点之间的最短路径
迪杰斯特拉算法用于计算图中某一个顶点到其他顶点的最短路径。
弗洛伊德算法 VS 迪杰斯特拉算法:迪杰斯特拉算法通过选定的被访问顶点,求出从出发访问顶点到其他顶点的最短路径;弗洛伊德算法中每一个顶点都是出发访问点,所以需要将每一个顶点看做被访问顶点,求出从每一个顶点到其他顶点的最短路径。
思路:
设置顶点vi到顶点vk的最短路径已知为Lik,顶点vk到vj的最短路径已知为Lkj,顶点vi到vj的路径为Lij,则vi到vj的最短路径为:min((Lik+Lkj),Lij),vk的取值为图中所有顶点,则可获得vi到vj的最短路径
至于vi到vk的最短路径Lik或者vk到vj的最短路径Lkj,是以同样的方式获得
主要是维护DP两张表(距离表,前驱关系表)
代码实现:Algorithm/Floyd.java
5.7 骑士周游问题
分析:
- 马踏棋盘问题(骑士周游问题)实际上是图的深度优先搜索(DFS)的应用。
- 如果使用回溯(就是深度优先搜索)来解决,假如马儿踏了53个点,如图:走到了第53个,坐标(1,0),发现已经走到尽头,没办法,那就只能回退了,查看其他的路径,就在棋盘上不停的回溯……
思路: