Hi, nice to meet you!

哈希

今天我们来聊一下哈希(Hashing),有时候也被称为散列。简单来说,哈希是一个唯一标识,用于标识一个东西。例如,一个人的身份证号就可以称为一个哈希,通过一个身份证号,可以定位到某一个人的信息。一个人的名字,也可以用作哈希,不过这个可能会产生重复,因为有很多人重名,这样导致的问题就是,通过名字,可能定位到多个人的信息,这种情况叫做哈希碰撞。

哈希

二叉堆

今天我们来说一下二叉堆(BinaryHeap)。堆是很有用的数据结构,例如后面会学到的优先队列,堆排序等,都和堆有关。操作系统中很多调度,也和堆有关。

还记得我们之前学过的完全二叉树吗?如果不记得了,就需要先回去复习一下,因为二叉堆,首先是一棵完全二叉树,或者近似完全二叉树。

再来说一下二叉堆的特性。二叉堆分为最小堆和最大堆。如果是最小堆,那么父节点的值,总是小于或等于任何一个子节点的值,通俗点就是把一棵树从上往下看,值在变大,下面的大于等于上面的。如果是最大堆,则是反过来,父节点的值,总是大于或等于任何一个子节点的值。

如果要简单点记忆,那就是这棵树上的值按层来看,如果是从小到大,那就是最小堆,如果是从大到小,那就是最大堆。

接下来我们就开始说二叉堆的细节,插入节点,删除节点。

二叉堆

一个公平的洗牌算法 | Knuth-Shuffle

洗牌(随机)算法有很多应用,例如我们平时用的音乐播放器随机播放,棋牌游戏中的洗牌,扫雷游戏中雷的位置随机等等,都会用到洗牌算法。

今天来介绍一个简单,公平,时间复杂度为O(n)的洗牌算法。什么是洗牌算法呢?其实就是将一些数据以公平随机的方式打乱顺序。这个算法,是由Knuth(高纳德),也就是计算机程序设计艺术的作者发明的。下面我们直接进入正题。

一个公平的洗牌算法 | Knuth-Shuffle

二叉查找树

二叉查找树(Binary Search Tree),简写BST,是满足某些条件的特殊二叉树。任何一个节点的左子树上的点,都必须小于当前节点。任何一个节点的右子树上的点,都必须大于当前节点。任何一棵子树,也都满足上面两个条件。另外二叉查找树中,是不存在重复节点的。

p001801_BSTSearch

二叉查找树

二叉树

这篇博客来聊一下二叉树。呆萌数据结构系列,终于开始了树型结构的部分。这篇文章你能够学到的内容有 树,有哪些应用二叉树的结构什么是满二叉树什么是完全二叉树二叉树的遍历方式二叉树的构建。二叉树是很基本的结构,在此基本上,会有很多很多变种,变成各种各样的树,理解了二叉树,对于后面学习其他更复杂的树型结构,会有很大的帮助。

这篇文章首先理解文字上的内容,不要管代码,对二叉树的结构,操作,理解原理,最后再看代码。

好了,下面开始吧。

二叉树

队列

生活中的一些排队行为,基本上都是队列的形式。这篇博客涉及的概念有 队列循环队列优先队列双端队列

很多编程语言已经内置了队列结构,在实际项目中可以直接使用。这篇文章里的代码实现,主要用做原理理解。

p001601_1

拿超市买单为例,买完东西,一般会找一个结账台排队,等待结账。如果前面已经有人在排队,那你肯定是排在当前队伍的最后面,如果再来人,肯定是排在你的后面,依次往后排。每当有一个顾客买完单,那后面的顾客就会往前走,直到整个买单队伍没有人排队。这就是队列结构。是不是很简单~

队列

堆栈

有一堆书,一本叠一本地放入箱子里,最后放入的,一定是在最上面,对不对。取书的时候,规定只能从上面一本一本地取,如果要拿最先放入箱子里的那本书,也就是最下面的那本书,只能先把上面的拿出来。

p001301_stack

堆栈

链表

什么是链表

链表和数组一样,是一种线性的数据结构,由一个一个节点构成,节点中存放着数据,以及指向下一个或上一个节点的指针,通过指针,将节点链接在一起,构成整个链表结构。不同于数组,链表在内存中并不是连续的存储空间。

p001201_Linkedlist

链表

数组

数组,在数据结构中,是很基础,也很常用的一个,在很多很多业务中,都能看到它的身影。数组很简单,在不同的编程语言中,操作方式,也几乎都是类似的。

那数组是什么呢?简单来说,就是在内存中分配一块连续的空间,用来存储相同类型的元素。使用索引,可以直接访问某一个元素的数据。大多数编程语言,数组的索引是从0开始的。

数组

数据结构概述

经常有小伙伴想系统地学习一下数据结构,但很难找到适合自己的教程。好吧,其实说的是我自己。那今天就来聊一聊这个问题。

我们先把一些常用的数据结构列表出,大概讲一下他们的结构及应用,后面分篇细细讲解。在分篇讲解时,我们的关注点是某个数据结构是什么,怎样用代码描述出来。而更多涉及到这个数据结构的一些算法,将在后面的算法系列中详细讲解。

这个系列的博客,是面向那些和我差不多,大概了解数一些数据结构(知道一些名字,不太了解内部详细实现),又想系统地巩固一下,深入一下的小朋友们~

快来一起学习吧 ^_^

数据结构概述