数据结构

x33g5p2x  于2021-11-21 转载在 其他  
字(5.7k)|赞(0)|评价(0)|浏览(417)

稀疏数组

稀疏数组存储的值不是第几行第几列是多少,而是原来数组的arr[][]=多少,比如这里,不是第一行第二列是1,而是原来数组arr[1][2]=1

队列

先进先出

数组模拟队列

问题分析并优化:
1 目前数组使用一次就不能用, 没有达到复用的效果
2) 将这个数组使用算法,改进成一个环形的队列 取模:%

数组模拟环形队列

分析说明:
1)尾索引的下一个为头索引时表示队列满,即将队列容量空出一个作为约定,这个在做判断队列满的
时候需要注意 (rear + 1) % maxSize == front 满]
2) rear == front [空]
3) 分析示意图:

链表

特点:

  1. 链表是以节点的方式来存储,是链式存储
  2. 每个节点包含 data 域, next 域:指向下一个节点.
  3. 链表的各个节点不一定是连续存储.
  4. 链表分带头节点的链表和没有头节点的链表,根据实际的需求来确定

单向链表
不按顺序:

按编号顺序添加(插入):

删除:

双向链表:

单向链表,查找的方向只能是一个方向,而双向链表可以向前或者向后查找。
单向链表不能自我删除,需要靠辅助节点 ,而双向链表,则可以自我删除,所以前面我们单链表删除时节点,总是找到 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 的那个人又出列,依次类推,直到所有人出列为止,由此产生一个出队编号的序列。

栈的应用场景

  1. 子程序的调用:在跳往子程序前,会先将下个指令的地址存到堆栈中,直到子程序执行完后再将地址取出,以
    回到原来的程序中。
  2. 处理递归调用:和子程序的调用类似,只是除了储存下一个指令的地址外,也将参数、区域变量等数据存入堆
    栈中。
  3. 表达式的转换[中缀表达式转后缀表达式]与求值(实际解决)。
  4. 二叉树的遍历。
  5. 图形的深度优先(depth 一 first)搜索法。

数组模拟栈

栈完成计算器

以上是中缀表达式
后缀表达式计算

例如: (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. 数组存储方式的分析
    优点:通过下标方式访问,查找元素,速度快。对于有序数组,还可使用二分查找提高检索速度。
    缺点:如果要检索具体某个值,或者插入值(按一定顺序)会整体移动,效率较低

  1. 链式存储方式的分析
    优点:在一定程度上对数组存储方式有优化(比如:插入一个数值节点,只需要将插入节点,链接到链表中即可,删除效率也很好)。
    缺点:在进行检索时,效率仍然较低,比如(检索某个值,需要从头节点开始遍历)
  2. 树存储方式的分析
    能提高数据存储,读取的效率, 比如利用 二叉排序树(Binary Sort Tree),既可以保证数据的检索速度,同时也可以保证数据的插入,删除,修改的速度。

二叉树:

  1. 树有很多种,每个节点最多只能有两个子节点的一种形式称为二叉树。
  2. 二叉树的子节点分为左节点和右节点。
  3. 如果该二叉树的所有叶子节点都在最后一层,并且节点总数= 2^n -1 , n 为层数,则我们称为满二叉树。
  4. 如果该二叉树的所有叶子节点都在最后一层或者倒数第二层,而且最后一层的叶子节点在左边连续,倒数第二层的叶子节点在右边连续,我们称为完全二叉树。

遍历:

前序遍历:先输出父节点,再遍历左子树和右子树

中序遍历:先遍历左子树,再输出父节点,再遍历右子树

后序遍历:先遍历左子树,再遍历右子树,最后输出父节点

查找:

前序查找

中序查找

后序查找

删除:

要求:
如果删除的节点是叶子节点,则删除该节点
如果删除的节点是非叶子节点,则删除该子树

顺序存储二叉树

从数据存储来看,数组存储方式和树的存储方式可以相互转换,即数组可以转换成树,树也可以转换成数组。

特点:

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]

堆排序的基本思想是:

  1. 将待排序序列构造成一个大顶堆
  2. 此时,整个序列的最大值就是堆顶的根节点。
  3. 将其与末尾元素进行交换,此时末尾就为最大值。
  4. 然后将剩余 n-1 个元素重新构造成一个堆,这样会得到 n 个元素的次小值。如此反复执行,便能得到一个有序
    序列了。

哈夫曼树:

给定 n 个权值作为 n 个叶子结点,构造一棵二叉树,若该树的带权路径长度(wpl)达到最小,称这样的二叉树为最优二叉树,也称为哈夫曼树(Huffman Tree)。

树的带权路径长度:树的带权路径长度规定为所有叶子结点的带权路径长度之和,记为 WPL(weighted path length) ,权值越大的结点离根结点越近的二叉树才是最优二叉树。

哈夫曼编码

通常用来压缩文件
属于变长编码

原理剖析:
传输的字符串

  1. i like like like java do you like a java
  2. d:1 y:1 u:1 j:2 v:2 o:2 l:4 k:4 e:4 i:5 a:5 :9 // 各个字符对应的个数
  3. 按照上面字符出现的次数构建一颗赫夫曼树, 次数作为权值
  4. 根据赫夫曼树,给各个字符,规定编码 (前缀编码), 向左的路径为0 向右的路径为1 , 编码如下:
    o: 1000 u: 10010 d: 100110 y: 100111 i: 101
    a : 110 k: 1110 e: 1111 j: 0000 v: 0001
    l: 001 : 01
  5. 按照上面的赫夫曼编码,我们的"i like like like java do you like a java" 字符串对应的编码为 (注意这里我们使用的无损压缩)
    1010100110111101111010011011110111101001101111011110100001100001110011001111000011001111000100100100110111101111011100100001100001110 通过赫夫曼编码处理长度为133
    说明:
    原来长度是 359 , 压缩了 (359-133) / 359 = 62.9%
    此编码满足前缀编码, 即字符的编码都不能是其他字符编码的前缀。不会造成匹配的多义性,赫夫曼编码是无损处理方案

注意, 这个赫夫曼树根据排序方法不同,也可能不太一样,这样对应的赫夫曼编码也不完全一样,但是wpl 是一样的,都是最小的。所以编码可能不太一样,但是长度都一样,都可以达到无损压缩。

哈夫曼压缩文件注意事项

1.如果文件本身就是经过压缩处理的,那么使用赫夫曼编码再压缩效率不会有明显变化, 比如视频,ppt 等等文件
2.赫夫曼编码是按字节来处理的,因此可以处理所有的文件(二进制文件、文本文件)
3.如果一个文件中的内容,重复的数据不多,压缩效果也不会很明显.

二叉排序树(二叉查找,搜索树)

BST: (Binary Sort(Search) Tree), 对于二叉排序树的任何一个非叶子节点,要求左子节点的值比当前节点的值小,右子节点的值比当前节点的值大。
特别说明:如果有相同的值,可以将该节点放在左子节点或右子节点

增加和遍历

删除:

二叉排序树的删除情况比较复杂
删除叶子节点 (比如:2, 5, 9, 12)
删除只有一颗子树的节点 (比如:1)
删除有两颗子树的节点. (比如:7, 3,10 )

平衡二叉树(AVL树)

平衡二叉树=平衡二叉搜索树=自平衡二叉树=红黑树=AVL树

一个数列{1,2,3,4,5,6},要求创建一颗二叉排序树(BST),
左子树全部为空,从形式上看,更像一个单链表.
插入速度没有影响
查询速度明显降低(因为需要依次比较), 不能发挥BST的优势,因为每次还需要比较左子树,其查询速度比单链表还慢
解决方案-平衡二叉树(AVL) ,保证查询效率较高

基本介绍
平衡二叉树也叫平衡二叉搜索树(Self-balancing binary search tree)又被称为AVL树, 可以保证查询效率较高。

具有以下特点:
平衡二叉树首先是一个二叉排序树(左小于右)
它是一棵空树或它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一棵平衡二叉树。
平衡二叉树的常用实现方法有红黑树、AVL、替罪羊树、Treap、伸展树等。

左旋转
当右子树大于左子树的高度,要进行左旋转

左子树的高度是1,右子树的高度是3,树的高度是4

右旋转

谁矮谁旋转

双旋转

问题分析

  1. 当符合右旋转的条件时
  2. 如果它的左子树的右子树高度大于它的左子树的高度
  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):

类似于一个分层搜索的过程,广度优先遍历需要使用一个队列以保持访问过的结点的顺序,以便按这个顺序来访问这些结点的邻接结点

相关文章