分类：数据结构
← 分类总览
数据结构数据结构与算法（三十）图的基本介绍
为什么要有图 前面我们学了线性表和树 线性表局限于一个直接前驱和一个直接后继的关系 树也只能有一个直接前驱也就是父节点 当我们需要表示多对多的关系时， 这里我们就用到了图 图是一种数据结构，其中结点可以具有零个或多个相邻元素。两个结点之间的连接称为边。 结点也可以称为顶点。如图：
数据结构数据结构与算法（三十一）图的遍历--深度优先遍历和广度优先遍历
图的深度优先遍历介绍 图遍历介绍 所谓图的遍历，即是对结点的访问。一个图有那么多个结点，如何遍历这些结点，需要特定策略，一般有两种访问策略: (1)深度优先遍历 (2)广度优先遍历 深度优先遍历基本思想 图的深度优先搜索(Depth First Search) 。 深度优先遍历，
数据结构数据结构与算法（二十九）多路查找树
二叉树的问题分析 二叉树的操作效率较高，但是也存在问题 二叉树需要加载到内存的，如果二叉树的节点少，没有什么问题，但是如果二叉树的节点很多(比如1亿)， 就存在如下问题: 问题1：在构建二叉树时，需要多次进行i/o操作(海量数据存在数据库或文件中)，节点海量，构建二叉树时，速度有
数据结构数据结构与算法（二十七）二叉排序树
二叉排序树介绍 二叉排序树：BST: (Binary Sort(Search) Tree), 对于二叉排序树的任何一个非叶子节点，要求左子节点的值比当前节点的值小，右子节点的值比当前节点的值大。 特别说明：如果有相同的值，可以将该节点放在左子节点或右子节点 二叉排序树创建和遍历
数据结构数据结构与算法（二十八）平衡二叉树(AVL树)
看一个案例(说明二叉排序树可能的问题) 给你一个数列{1,2,3,4,5,6}，要求创建一颗二叉排序树(BST), 并分析问题所在. 存在的问题分析: 左子树全部为空，从形式上看，更像一个单链表. 插入速度没有影响 查询速度明显降低(因为需要依次比较), 不能发挥BST 的优势，
数据结构数据结构与算法（二十六）赫夫曼编码--文件解压(文件恢复)
最佳实践-文件解压(文件恢复) 具体要求：将前面压缩的文件，重新恢复成原来的文件。 思路：读取压缩文件(数据和赫夫曼编码表)-> 完成解压(文件恢复) 赫夫曼编码压缩文件注意事项 如果文件本身就是经过压缩处理的，那么使用赫夫曼编码再压缩效率不会有明显变化, 比如视频,ppt 等等
数据结构数据结构与算法（二十五）赫夫曼编码--解码
上面我们完成了赫夫曼编码，我们来实现下解码。完成对压缩数据的解码。 /** * * @param huffmanCodes 赫夫曼编码表 map * @param huffmanBytes 赫夫曼编码得到的字节数组 * @return 就是原来的字符串对应的数组 */ priva
数据结构数据结构与算法（二十四）赫夫曼编码
基本介绍 赫夫曼编码也翻译为 哈夫曼编码(Huffman Coding)，又称霍夫曼编码，是一种编码方式, 属于一种程序算法 赫夫曼编码是赫哈夫曼树在电讯通信中的经典的应用之一。 赫夫曼编码广泛地用于数据文件压缩。其压缩率通常在20%～90%之间 赫夫曼码是可变字长编码(VLC)
数据结构数据结构与算法（二十三）赫夫曼树
基本介绍 给定n个权值作为n个叶子结点，构造一棵二叉树，若该树的带权路径长度(wpl)达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(Huffman Tree), 还有的书翻译为霍夫曼树。 赫夫曼树是带权路径长度最短的树，权值较大的结点离根较近。 赫夫曼树几个重要概念和举例
数据结构数据结构与算法（二十一）线索化二叉树
前言 先看一个问题 将数列 {1, 3, 6, 8, 10, 14 } 构建成一颗二叉树. n+1=7 问题分析: 当我们对上面的二叉树进行中序遍历时，数列为 {8, 3, 10, 1, 6, 14 } 但是 6, 8, 10, 14 这几个节点的 左右指针，并没有完全的利用上.
数据结构数据结构与算法（二十二）堆排序
堆排序基本介绍 堆排序是利用堆这种数据结构而设计的一种排序算法，堆排序是一种选择排序，它的最坏，最好，平均时间复杂度均为O(nlogn)，它也是不稳定排序。 堆是具有以下性质的完全二叉树：每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆, 注意 : 没有要求结点的左孩子的值
数据结构数据结构与算法（二十）顺序存储二叉树
顺序存储二叉树的概念 基本说明 从数据存储来看，数组存储方式和树 的存储方式可以相互转换，即数组可 以转换成树，树也可以转换成数组， 看右面的示意图。 要求: 图的二叉树的结点，要求以数组 的方式来存放 arr : [1, 2, 3, 4, 5, 6, 6] 要求在遍历数组 ar
数据结构数据结构与算法（十九）二叉树基本操作
为什么需要树这种数据结构 数组存储方式的分析 优点：通过下标方式访问元素，速度快。对于有序数组，还可使用二分查找提高检索速度。 缺点：如果要检索具体某个值，或者插入值(按一定顺序)会整体移动，效率较低 [示意图] 链式存储方式的分析 优点：在一定程度上对数组存储方式有优化(比如：
数据结构数据结构与算法（十七）斐波那契(黄金分割法)查找算法
斐波那契(黄金分割法)查找基本介绍: 黄金分割点是指把一条线段分割为两部分，使其中一部分与全长之比等于另一部分与这部分之比。取其前三位数字的近似值是0.618。由于按此比例设计的造型十分美丽，因此称为黄金分割，也称为中外比。这是一个神奇的数字，会带来意向不大的效果。 斐波那契数列
数据结构数据结构与算法（十八）哈希表(散列)
基本介绍： 散列表（Hash table，也叫哈希表），是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。 案例分析 看一个实际需求，goog
数据结构数据结构与算法（十六）插值查找算法
插值查找原理介绍: 插值查找算法类似于二分查找，不同的是插值查找每次从自适应mid处开始查找。 将折半查找中的求mid 索引的公式 , low 表示左边索引left, high表示右边索引right. key 就是前面我们讲的 findVal int mid = low + (h
数据结构数据结构与算法（十五） 二分查找算法
二分查找算法 二分查找是一种在有序数组中查找某一特定元素的搜索算法。搜素过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜素过程结束；如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。如果在某一步骤数组已
数据结构数据结构与算法（十四）顺序(线性)查找
简单介绍 有一个数列，判断数列中是否包含此名称【顺序查找】 要求: 如果找到了，就提示找到，并给出下标值。 思路：如果查找到全部符合条件的值。 代码实现 public static void main(String[] args) { int [] arr={3,4,1,5,7}
数据结构数据结构与算法（十三）排序总结
排序算法总结 排序也称排序算法 (Sort Algorithm)，排序是将一 组数据，依指定的顺序进行排列 的过程。 排序的分类： 内部排序: 指将需要处理的所有数据都加载 到内部存储器中进行排序。 外部排序法： 数据量过大，无法全部加载到内 存中，需要借助外部存储进行 排序。
数据结构数据结构与算法（十三）排序----基数排序（桶排序）
基数排序(桶排序)介绍: 基数排序（radix sort）属于“分配式排序”（distribution sort），又称“桶子法”（bucket sort）或bin sort，顾名思义，它是通过键值的各个位的值，将要排序的元素分配至某些“桶”中，达到排序的作用 基数排序法是属于稳
数据结构数据结构与算法（十二）排序--归并排序
归并排序介绍: 归并排序（MERGE-SORT）是利用归并的思想实现的排序方法，该算法采用经典的分治（divide-and-conquer）策略（分治法将问题分(divide)成一些小的问题然后递归求解，而治(conquer)的阶段则将分的阶段得到的各答案"修补"在一起，即分而治
数据结构数据结构与算法（十一）排序---快速排序
快速排序法介绍: 快速排序（Quicksort）是对冒泡排序的一种改进。基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序
数据结构数据结构与算法（十）排序---希尔排序
简单插入排序存在的问题 数组 {2,3,4,5,6,1},当需要插入的是1的时候，后移动的次数很多，对效率有影响。 希尔排序法介绍 希尔排序是希尔（Donald Shell）于1959年提出的一种排序算法。希尔排序也是一种插入排序，它是简单插入排序经过改进之后的一个更高效的版本，
数据结构数据结构与算法（九）排序---插入排序
插入排序法介绍: 插入式排序属于内部排序法，是对于欲排序的元素以插入的方式找寻该元素的适当位置，以达到排序的目的。 插入排序法思想: 插入排序（Insertion Sorting）的基本思想是：把n个待排序的元素看成为一个有序表和一个无序表，开始时有序表中只包含一个元素，无序表中
数据结构数据结构与算法（八）排序---选择排序
基本介绍 选择式排序也属于内部排序法，是从欲排序的数据中，按指定的规则选出某一元素，再依规定交换位置后达到排序的目的。 选择排序的思想： 选择排序（select sorting）也是一种简单的排序方法。它的基本思想是：第一次从arr[0]~arr[n-1]中选取最小值，与arr[
数据结构数据结构与算法（七）排序--冒泡排序
冒泡排序： 冒泡排序（Bubble Sorting）的基本思想是：通过对待 排序序列从前向后（从下标较小的元素开始）,依次比较 相邻元素的值，若发现逆序则交换，使值较大 的元素逐渐从前移向后部，就象水底下的气泡一样逐渐 向上冒。 代码实现 /** * 冒泡排序 * @param
数据结构数据结构与算法（六）栈 ---前缀、中缀、后缀表达式(逆波兰表达式)
前言 前缀表达式、中缀表达式、后缀表达式都是四则运算的表达方式,用以四则运算表达式求值,即数学表达式的求值。 中缀表达式 简介 中缀表达式就是常见的运算表达式，如(3+4)×5-6 前缀表达式 简介 前缀表达式又称波兰式，前缀表达式的运算符位于操作数之前 比如:- × + 3 4
数据结构数据结构与算法（五）单向环形链表---约瑟夫问题
一、Josephu 问题 Josephu 问题为：设编号为1，2，… n的n个人围坐一圈，约定编号为k（1<=k<=n）的人从1开始报数，数到m 的那个人出列，它的下一位又从1开始报数，数到m的那个人又出列，依次类推，直到所有人出列为止，由此产生一个出队编号的序列。 二、代码实现
数据结构数据结构与算法（四） 双向链表
一、简单介绍 双向链表是一种对称结构，它克服了单链表上指针单向性的缺点，其中每一个节点即可向前引用，也可向后引用，这样可以更方便的插入、删除数据元素。 由于双向链表需要同时维护两个方向的指针，因此添加节点、删除节点时指针维护成本更大；但双向链表具有两个方向的指针，因此可以向两个方
数据结构数据结构与算法（二）单链表
一、简单介绍 单链表是链表的其中一种基本结构。一个最简单的结点结构如图所示，它是构成单链表的基本结点结构。在结点中数据域用来存储数据元素，指针域用于指向下一个具有相同结构的结点。 因为只有一个指针结点，称为单链表。 二、代码简单实现 1、节点对象 /** * 链表节点 */ cl
数据结构数据结构与算法（一）数组模拟环形队列
一、队列的基本认识 队列就是一个只允许在一端进行插入，在另一端进行删除操作的线性表。 队列是一种常用的数据结构之一，队列是“先进先出”。队列有队头（front）和队尾（rear），数据从队尾进入队列，从队头出队列，队头（front）指向队列的第一个数据，队尾（rear）指向队列中
数据结构Java 中 IO 流
Java 中 IO 流分为几种? 按照流的流向分，可以分为输入流和输出流； 按照操作单元划分，可以划分为字节流和字符流； 按照流的角色划分为节点流和处理流。 Java Io 流共涉及 40 多个类，这些类看上去很杂乱，但实际上很有规则，而且彼此之间存在非常紧密的联系， Java