稀疏数组存储的值不是第几行第几列是多少,而是原来数组的arr[][]=多少,比如这里,不是第一行第二列是1,而是原来数组arr[1][2]=1
先进先出
数组模拟队列
问题分析并优化:
1 目前数组使用一次就不能用, 没有达到复用的效果
2) 将这个数组使用算法,改进成一个环形的队列 取模:%
数组模拟环形队列
分析说明:
1)尾索引的下一个为头索引时表示队列满,即将队列容量空出一个作为约定,这个在做判断队列满的
时候需要注意 (rear + 1) % maxSize == front 满]
2) rear == front [空]
3) 分析示意图:
特点:
单向链表
不按顺序:
按编号顺序添加(插入):
删除:
双向链表:
单向链表,查找的方向只能是一个方向,而双向链表可以向前或者向后查找。
单向链表不能自我删除,需要靠辅助节点 ,而双向链表,则可以自我删除,所以前面我们单链表删除时节点,总是找到 temp,temp 是待删除节点的前一个节点
对双向链表的增删改查:
查(遍历):遍历方法和单链表一样,只是可以向前,也可以向后查找。
添加 (默认添加到双向链表的最后)
(1) 先找到双向链表的最后这个节点
(2) temp.next = newHeroNode
(3) newHeroNode.pre = temp;
修改思路和原来的单向链表一样
删除
(1) 因为是双向链表,因此,我们可以实现自我删除某个节点
(2) 直接找到要删除的这个节点,比如temp
(3) temp.pre.next = temp.next
(4) temp.next.pre = temp.pre;
单向环形列表
Josephu(约瑟夫,约瑟夫环) 问题
设编号为 1,2,… n 的 n 个人围坐一圈,约定编号为 k(1<=k<=n)的人从 1 开始报数,数到 m 的那个人出列,它的下一位又从 1 开始报数,数到 m 的那个人又出列,依次类推,直到所有人出列为止,由此产生一个出队编号的序列。
栈的应用场景
数组模拟栈
栈完成计算器
以上是中缀表达式
后缀表达式计算
例如: (3+4)×5-6 对应的后缀表达式就是 3 4 + 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,由此得出最终结果
中缀表达式转换为后缀表达式
可以充当缓存层。
散列表(Hash table,也叫哈希表),是根据关键码值(Key value)而直接进行访问的数据结构。也就是说,它通过把关键码值映射到表中一个位置来访问记录,以加快查找的速度。这个映射函数叫做散列函数,存放记录的数组叫做散列表。
结构:
数组+链表
数组+二叉树
为什么需要树这种数据结构?
遍历:
前序遍历:先输出父节点,再遍历左子树和右子树
中序遍历:先遍历左子树,再输出父节点,再遍历右子树
后序遍历:先遍历左子树,再遍历右子树,最后输出父节点
查找:
前序查找
中序查找
后序查找
删除:
要求:
如果删除的节点是叶子节点,则删除该节点
如果删除的节点是非叶子节点,则删除该子树
从数据存储来看,数组存储方式和树的存储方式可以相互转换,即数组可以转换成树,树也可以转换成数组。
特点:
1.顺序二叉树通常只考虑完全二叉树
2.第n个元素的左子节点为 2 * n + 1
3.第n个元素的右子节点为 2 * n + 2
4.第n个元素的父节点为 (n-1) / 2
n : 表示二叉树中的第几个元素(按0开始编号如图所示)
给一个数组,根据二叉树前序遍历方式进行遍历
特点:
n个结点的二叉链表中含有n+1 【公式 2n-(n-1)=n+1】 个空指针域。利用二叉链表中的空指针域,存放指向该结点在某种遍历次序下的前驱和后继结点的指针(这种附加的指针称为"线索")
这种加上了线索的二叉链表称为线索链表,相应的二叉树称为线索二叉树(Threaded BinaryTree)。根据线索性质的不同,线索二叉树可分为前序线索二叉树、中序线索二叉树和后序线索二叉树三种
一个结点的前一个结点,称为前驱结点
一个结点的后一个结点,称为后继结点
说明:
当线索化二叉树后,Node节点的 属性 left 和 right ,有如下情况:
1.left 指向的是左子树,也可能是指向的前驱节点. 比如 ① 节点 left 指向的左子树, 而 ⑩ 节点的 left 指向的就是前驱节点
2.right指向的是右子树,也可能是指向后继节点,比如 ① 节点right 指向的是右子树,而⑩ 节点的right 指向的是后继节点
堆排序(顺序存储二叉树的应用)
1.堆排序是利用堆这种数据结构而设计的一种排序算法,堆排序是一种选择排序,它的最坏,最好,平均时间复杂度均为O(nlogn),它也是不稳定排序。
2.堆是具有以下性质的完全二叉树:每个结点的值都大于或等于其左右孩子结点的值,称为大顶堆, 注意 : 没有要求结点的左孩子的值和右孩子的值的大小关系。
3.每个结点的值都小于或等于其左右孩子结点的值,称为小顶堆。
4.一般升序采用大顶堆,降序采用小顶堆 。
在对堆中的结点按层进行编号,映射到数组中就是下面这个样子:
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 个权值作为 n 个叶子结点,构造一棵二叉树,若该树的带权路径长度(wpl)达到最小,称这样的二叉树为最优二叉树,也称为哈夫曼树(Huffman Tree)。
树的带权路径长度:树的带权路径长度规定为所有叶子结点的带权路径长度之和,记为 WPL(weighted path length) ,权值越大的结点离根结点越近的二叉树才是最优二叉树。
哈夫曼编码
通常用来压缩文件
属于变长编码
原理剖析:
传输的字符串
注意, 这个赫夫曼树根据排序方法不同,也可能不太一样,这样对应的赫夫曼编码也不完全一样,但是wpl 是一样的,都是最小的。所以编码可能不太一样,但是长度都一样,都可以达到无损压缩。
哈夫曼压缩文件注意事项
1.如果文件本身就是经过压缩处理的,那么使用赫夫曼编码再压缩效率不会有明显变化, 比如视频,ppt 等等文件
2.赫夫曼编码是按字节来处理的,因此可以处理所有的文件(二进制文件、文本文件)
3.如果一个文件中的内容,重复的数据不多,压缩效果也不会很明显.
BST: (Binary Sort(Search) Tree), 对于二叉排序树的任何一个非叶子节点,要求左子节点的值比当前节点的值小,右子节点的值比当前节点的值大。
特别说明:如果有相同的值,可以将该节点放在左子节点或右子节点
增加和遍历
删除:
二叉排序树的删除情况比较复杂
删除叶子节点 (比如:2, 5, 9, 12)
删除只有一颗子树的节点 (比如:1)
删除有两颗子树的节点. (比如:7, 3,10 )
平衡二叉树=平衡二叉搜索树=自平衡二叉树=红黑树=AVL树
一个数列{1,2,3,4,5,6},要求创建一颗二叉排序树(BST),
左子树全部为空,从形式上看,更像一个单链表.
插入速度没有影响
查询速度明显降低(因为需要依次比较), 不能发挥BST的优势,因为每次还需要比较左子树,其查询速度比单链表还慢
解决方案-平衡二叉树(AVL) ,保证查询效率较高
基本介绍
平衡二叉树也叫平衡二叉搜索树(Self-balancing binary search tree)又被称为AVL树, 可以保证查询效率较高。
具有以下特点:
平衡二叉树首先是一个二叉排序树(左小于右)
它是一棵空树或它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一棵平衡二叉树。
平衡二叉树的常用实现方法有红黑树、AVL、替罪羊树、Treap、伸展树等。
左旋转
当右子树大于左子树的高度,要进行左旋转
左子树的高度是1,右子树的高度是3,树的高度是4
右旋转
谁矮谁旋转
双旋转
问题分析
二叉树的问题分析
二叉树的操作效率较高,但是也存在问题, 请看下面的二叉树
二叉树需要加载到内存的,如果二叉树的节点少,没有什么问题,但是如果二叉树的节点很多(比如1亿), 就存在如下问题:
问题1:在构建二叉树时,需要多次进行i/o操作(海量数据存在数据库或文件中),节点海量,构建二叉树时,速度有影响
问题2:节点海量,也会造成二叉树的高度很大,会降低操作速度.
B树
通过重新组织节点, 降低了树的高度。最简单的B树是2-3树,还有2-3-4树。
2-3树的特点:
1).2-3树的所有叶子节点都在同一层,(只要是B树都满足这个条件)
2).有2个叶子节点的叫二节点,二节点要么没有子节点,要么有2个子节点
3).有三个子节点的节点叫三节点,三节点要么没有子节点,要么有三个子 节点
4).2-3树由二节点和三节点构成的树
B树的说明:
B树的阶:节点的最多子节点个数。比如2-3树的阶是3,2-3-4树的阶是4
B树的搜索,从根结点开始,对结点内的关键字(有序)序列进行二分查找,如果命中则结束,否则进入查询关键字所属范围的儿子结点;重复,直到所对应的儿子指针为空,或已经是叶子结点
关键字集合分布在整颗树中,
即叶子节点和非叶子节点都存放数据.搜索有可能在非叶子结点结束
其搜索性能等价于在关键字全集内做一次二分查找
B+树
B+树是B树的变体,也是一种多路搜索树
B*树
线性表局限于一个直接前驱和一个直接后继的关系
树也只能有一个直接前驱也就是父节点
当我们需要表示多对多的关系时, 这里我们就用到了图
图的表示方式有两种:
二维数组表示(邻接矩阵)和链表表示(邻接表)
邻接矩阵
邻接表
邻接矩阵需要为每个顶点都分配n个边的空间,其实有很多边都是不存在,会造成空间的一定损失.
邻接表的实现只关心存在的边,不关心不存在的边。因此没有空间浪费,邻接表由数组+链表组成
图的遍历:
深度优先(dfs):
深度优先遍历,从初始访问结点出发,初始访问结点可能有多个邻接结点,深度优先遍历的策略就是首先访问第一个邻接结点,然后再以这个被访问的邻接结点作为初始结点,访问它的第一个邻接结点, 可以这样理解:每次都在访问完当前结点后首先访问当前结点的第一个邻接结点。
我们可以看到,这样的访问策略是优先往纵向挖掘深入,而不是对一个结点的所有邻接结点进行横向访问。
显然,深度优先搜索是一个递归的过程
广度优先(bfs):
类似于一个分层搜索的过程,广度优先遍历需要使用一个队列以保持访问过的结点的顺序,以便按这个顺序来访问这些结点的邻接结点
版权说明 : 本文为转载文章, 版权归原作者所有 版权申明
原文链接 : https://blog.csdn.net/weixin_47160763/article/details/109721581
内容来源于网络,如有侵权,请联系作者删除!