数据结构

数据结构

数据结构与算法(三十一)图的遍历--深度优先遍历和广度优先遍历

图的深度优先遍历介绍图遍历介绍所谓图的遍历,即是对结点的访问。一个图有那么多个结点,如何遍历这些结点,需要特定策略,一般有两种访问策略:(1)深度优先遍历(2)广度优先遍历深度优先遍历基本思想图的深度优先搜索(DepthFirstSearch)。深度优先遍历,从初始访问结点出发,初始访问结点可能有多

2020-08-21
77 0

数据结构与算法(三十)图的基本介绍

为什么要有图前面我们学了线性表和树线性表局限于一个直接前驱和一个直接后继的关系树也只能有一个直接前驱也就是父节点当我们需要表示多对多的关系时,这里我们就用到了图图是一种数据结构,其中结点可以具有零个或多个相邻元素。两个结点之间的连接称为边。结点也可以称为顶点。如图:图的常用概念顶点(vertex)边

2020-08-21
93 0

数据结构与算法(二十九)多路查找树

二叉树的问题分析二叉树的操作效率较高,但是也存在问题二叉树需要加载到内存的,如果二叉树的节点少,没有什么问题,但是如果二叉树的节点很多(比如1亿),就存在如下问题:问题1:在构建二叉树时,需要多次进行i/o操作(海量数据存在数据库或文件中),节点海量,构建二叉树时,速度有影响问题2:节点海量,也会造

2020-08-17
66 0

数据结构与算法(二十八)平衡二叉树(AVL树)

看一个案例(说明二叉排序树可能的问题)给你一个数列{1,2,3,4,5,6},要求创建一颗二叉排序树(BST),并分析问题所在.存在的问题分析:左子树全部为空,从形式上看,更像一个单链表.插入速度没有影响查询速度明显降低(因为需要依次比较),不能发挥BST的优势,因为每次还需要比较左子树,其查询速度

2020-08-14
52 0

数据结构与算法(二十七)二叉排序树

二叉排序树介绍二叉排序树:BST:(BinarySort(Search)Tree),对于二叉排序树的任何一个非叶子节点,要求左子节点的值比当前节点的值小,右子节点的值比当前节点的值大。特别说明:如果有相同的值,可以将该节点放在左子节点或右子节点二叉排序树创建和遍历一个数组创建成对应的二叉排序树,并使

2020-08-14
41 0

数据结构与算法(二十六)赫夫曼编码--文件解压(文件恢复)

最佳实践-文件解压(文件恢复)具体要求:将前面压缩的文件,重新恢复成原来的文件。思路:读取压缩文件(数据和赫夫曼编码表)->完成解压(文件恢复)赫夫曼编码压缩文件注意事项如果文件本身就是经过压缩处理的,那么使用赫夫曼编码再压缩效率不会有明显变化,比如视频,ppt等等文件[举例压一个.ppt]赫

2020-08-10
45 0

数据结构与算法(二十五)赫夫曼编码--解码

上面我们完成了赫夫曼编码,我们来实现下解码。完成对压缩数据的解码。/****@paramhuffmanCodes赫夫曼编码表map*@paramhuffmanBytes赫夫曼编码得到的字节数组*@return就是原来的字符串对应的数组*/privatestaticbyte[]decode(Map&l

2020-08-09
57 0

数据结构与算法(二十三)赫夫曼树

基本介绍给定n个权值作为n个叶子结点,构造一棵二叉树,若该树的带权路径长度(wpl)达到最小,称这样的二叉树为最优二叉树,也称为哈夫曼树(HuffmanTree),还有的书翻译为霍夫曼树。赫夫曼树是带权路径长度最短的树,权值较大的结点离根较近。赫夫曼树几个重要概念和举例说明路径和路径长度:在一棵树中

2020-08-09
60 0

数据结构与算法(二十二)堆排序

堆排序基本介绍堆排序是利用堆这种数据结构而设计的一种排序算法,堆排序是一种选择排序,它的最坏,最好,平均时间复杂度均为O(nlogn),它也是不稳定排序。堆是具有以下性质的完全二叉树:每个结点的值都大于或等于其左右孩子结点的值,称为大顶堆,注意:没有要求结点的左孩子的值和右孩子的值的大小关系。每个结

2020-08-06
84 0

数据结构与算法(二十一)线索化二叉树

前言先看一个问题将数列{1,3,6,8,10,14}构建成一颗二叉树.n+1=7问题分析:当我们对上面的二叉树进行中序遍历时,数列为{8,3,10,1,6,14}但是6,8,10,14这几个节点的左右指针,并没有完全的利用上.如果我们希望充分的利用各个节点的左右指针,让各个节点可以指向自己的前后节点

2020-08-06
59 0