算法速成（七）线性表之顺序存储

2017年02月05日 52 阅读

算法速成（七）线性表之顺序存储2014-04-28 csdn博客 特种兵—AK47人活在社会上不可能孤立，比如跟美女有着千丝万缕的关系，有的是一对一，有的是一对多，有的 是多对多。哈哈，我们的数据也一样，存在这三种基本关系，用术语来说就 是:<1> 线性关系。<2> 树形关系。<3> 网状关系。一： 线性表1 概念：线性表也就是关系户中最简单的一种 关系，一对一。如：学生学号的集合就是一个线性表。2 特征：① 有且只有 ...

算法速成（八）线性表之链表

2017年02月05日 50 阅读

算法速成（八）线性表之链表2014-04-28 csdn博客 特种兵—AK47一：线性表的简单回顾上一篇跟大家聊过“线性表"顺序存储，通过实验，大家也知 道，如果我每次向顺序表的头部插入元素，都会引起痉挛，效率比较低下，第二点我们用顺序 存储时，容易受到长度的限制，反之就会造成空间资源的浪费。二：链表对于 顺序表存在的若干问题，链表都给出了相应的解决方案。1. 概念：其实链表的“每个节点” 都包含一个&rdqu...

算法速成（六）五大经典查找之二叉排序树

2017年02月05日 54 阅读

算法速成（六）五大经典查找之二叉排序树2014-04-28 csdn博客 特种兵—AK47大家是否感觉到，树在数据结构中大行其道，什么领域都要沾一沾，碰一碰。就拿我们前 几天学过的排序就用到了堆和今天讲的”二叉排序树“，所以偏激的说，掌握的树你就是牛人了。今天就聊聊这个”五大经典查找“中的最后一个”二叉排序树“。1. 概 念:<1> 其实很简单，若根节点有左子树，则左子树的...

算法速成（九）队列

2017年02月05日 50 阅读

算法速成（九）队列2014-04-28 csdn 特种兵—AK47可能大家都知道，线性表的变种非常非常多，比如今天讲的“队列”，灰常有意思啊。一：概念队列是一个”先进先出“的线性表，牛X的名字就是“First in First Out（FIFO）”，生活中有很多这样的场景，比如读书的时候去食堂打饭时的”排队“。当然我们拒绝插队。二：存储结构 前几天也说过，线性表...

算法速成（十）栈

2017年02月05日 49 阅读

算法速成（十）栈2014-04-28 csdn博客 特种兵—AK47今天跟大家聊聊栈，在程序设计中，栈的使用还是非常广泛的，比如有“括号匹配问题“，”html 结构匹配问题“。所以说掌握了”栈“的使用，对我们学习算法还是很有帮助的。一 ： 概念栈，同样是一种特殊的线性表，是一种Last In First Out（LIFO）的形式，现实中有 很多这样的例子，比如：食堂中的一叠盘子，我们只...

算法速成（十一）树操作之基本操作

2017年02月05日 48 阅读

算法速成（十一）树操作之基本操作2014-04-28 csdn 特种兵—AK47先前我们讲的都是“线性结构”，他的特征就是“一个节点最多有一个”前驱“和一个”后继“ 。那么我们今天讲的树会是怎样的呢？我们可以对”线性结构“改造一下，变为”一个节点最 多有一个"前驱“和”多个后继“。哈哈，这就是...

算法速成（十二）树操作之线索二叉树

2017年02月05日 48 阅读

算法速成（十二）树操作之线索二叉树2014-04-28 csdn博客 特种兵—AK47先前说了树的基本操作，我们采用的是二叉链表来保存树形结构，当然二叉有二叉的困扰之处，比 如我想找到当前结点的“前驱”和“后继”，那么我们就必须要遍历一下树，然后才能定位到 该“节点”的“前驱”和“后继”，每次定位都是O（n），这不是我们想看到的，那么有什...

算法速成（十三）树操作之赫夫曼树

2017年02月05日 51 阅读

算法速成（十三）树操作之赫夫曼树2014-04-28 csdn博客 特种兵—AK47今天说下最后一种树，大家可否知道，文件压缩程序里面的核心结构，核心算法是什么？或许你知 道，他就运用了赫夫曼树。听说赫夫曼胜过了他的导师，被认为”青出于蓝而胜于蓝“，这句 话也是我比较欣赏的，嘻嘻。一 概念了解”赫夫曼树“之前，几个必须要知道 的专业名词可要熟练记住啊。1： 结点的权 “权”就相当于&l...

算法速成（十四）图之非线性数据结构

2017年02月05日 50 阅读

算法速成（十四）图之非线性数据结构2014-04-28 csdn博客 特种兵—AK47今天来分享一下图，这是一种比较复杂的非线性数据结构，之所以复杂是因为他们的数据元素之间 的关系是任意的，而不像树那样被几个性质定理框住了，元素之间的关系还是比较明显的，图 的使用范围很广的，比如网络爬虫，求最短路径等等，不过大家也不要胆怯，越是复杂的东西 越能体现我们码农的核心竞争力。既然要学习图，得要遵守一下图的游戏规则。一： 概念图是由“顶点”...

算法速成（十五）图之“最小生成树”和“最短路径”

2017年02月05日 54 阅读

算法速成（十五）图之“最小生成树”和“最短路径”2014-04-28 csdn博客 特种兵—AK47今天是大结局，说下“图”的最后一点东西，“最小生成树“和”最短路径“。一： 最小 生成树1. 概念首先看如下图，不知道大家能总结点什么。对于一个连通图G， 如果其全部顶点和一部分边构成一个子图G1，当G1满足：① 刚好将图中所有顶点连通。② 顶点不存在回路。则称G1就是G的“...

算法系列（一） Google方程式

2017年02月05日 50 阅读

算法系列（一） Google方程式2014-04-30 csdn博客 吹泡泡的小猫有一个字符组成的等式：WWWDOT - GOOGLE = DOTCOM，每个字符代表一个0－9之间的数字，WWWDOT 、GOOGLE和DOTCOM都是合法的数字，不能以0开头。请找出一组字符和数字的对应关系，使它们互相替 换，并且替换后的数字能够满足等式。这个字符等式是Google公司能力倾向测试实验室的一道题目， 这种题目主要考察人的逻辑推导能力和短期记忆能力，通常棋下的...

算法系列（二） 三只水桶等分水问题

2017年02月05日 49 阅读

算法系列（二） 三只水桶等分水问题2014-04-30 吹泡泡的小猫 有一个容积为8升的水桶里装满了水，另外还有一个容积为3升的空桶和一个容积为5升的空桶，如 何利用这两个空桶等分8升水？附加条件是三个水桶都没有体积刻度，也不能使用其它辅助容器。这是一道经典题目，一般人都可以在一分钟内给出答案，不过，很多人可能没有注意到这道题 的答案不是唯一的。先来看看最常见的一个答案，也是目前已知最快的操作步骤，共需要7次倒水动作 ：从容积是8升的桶中倒5升水到容积是5...

算法系列（三） 妖怪与和尚过河问题

2017年02月05日 50 阅读

算法系列（三） 妖怪与和尚过河问题2014-04-30 csdn博客 吹泡泡的小猫有三个和尚（或传教士）和三个妖怪（或食人怪）过河，只有一条能装下两个人（和尚或妖怪）的 船，在河的任何一方或者船上，如果妖怪的人数大于和尚的人数，那么和尚就会有被吃掉的危险。你 能不能找出一种安全的渡河方法呢？这是一个很有意思的智力题，但是并不难，每次可以选择 一个人或者两个人过河，只要保证在河的任何一边的和尚数量总是大于或等于妖怪的数量即可。这里 先给出一种过河方法：两个妖...

算法系列（四） 字符串的相似度

2017年02月05日 53 阅读

算法系列（四） 字符串的相似度2014-04-30 csdn博客 吹泡泡的小猫我们把两个字符串的相似度定义为：将一个字符串转换成另外一个字符串的代价（转换的方法可 能不唯一），转换的代价越高则说明两个字符串的相似度越低。比如两个字符串：“SNOWY”和 “SUNNY”，下面给出两种将“SNOWY”转换成“SUNNY”的方法：变换1： S - N O W Y S ...

算法系列（五）最长公共子序列（LCS）问题（非连续子序列）的两种解法

2017年02月05日 52 阅读

算法系列（五）最长公共子序列（LCS）问题（非连续子序列）的两种解法2014-04-30 csdn博客 吹泡泡的小猫最长公共子序列也称作最长公共子串，英文缩写是LCS（Longest Common Subsequence）。其定义 是：一个序列S，如果分别是两个或多个已知序列的子序列，且是符合此条件的子序列中最长的，则称 S为已知序列的最长公共子序列。关于子序列的定义通常有两种方式，一种是对子序列没有连 续的要求，其子序列的定义就是原序列中删除若干元素后得...

算法系列（六）最长公共子序列（LCS）问题（连续子序列）的三种解法

2017年02月05日 47 阅读

算法系列（六）最长公共子序列（LCS）问题（连续子序列）的三种解法2014-04-30最长公共子序列（LCS）问题有两种方式定义子序列，一种是子序列不要求不连续，一种是子序列 必须连续。上一章介绍了用两种算法解决子序列不要求连续的最终公共子序列问题，本章将介绍要求 子序列必须是连续的情况下如何用算法解决最长公共子序列问题。仍以上一章的两个字符串 “abcdea”和“aebcda”为例，如果子序列不要求连续，其...

算法系列（七） 爱因斯坦的思考题（上）

2017年02月05日 47 阅读

算法系列（七） 爱因斯坦的思考题（上）2014-04-30 csdn博客 吹泡泡的小猫这是一个很有趣的逻辑推理题，传说是爱因斯坦提出来的，他宣称世界上只有2％的人能解出这个 题目，传说不一定属实，但是这个推理题还是很有意思的。题目是这样的，据说有五个不同颜色的房 间排成一排，每个房间里分别住着一个不同国籍的人，每个人都喝一种特定品牌的饮料，抽一种特定 品牌的烟，养一种宠物，没有任意两个人抽相同品牌的香烟，或喝相同品牌的饮料，或养相同的宠物 ，问题是谁在养鱼...

算法系列（七） 爱因斯坦的思考题（下）

2017年02月05日 51 阅读

算法系列（七） 爱因斯坦的思考题（下）2014-04-30 csdn博客 吹泡泡的小猫CheckGroupRelation（）函数需要根据当前组group的位置进行适当的处理，如果当前组是第一个 组或最后一个组，则group的相邻组只有一个，就是最靠近group的组，其它情况下group的相邻组都是 两个。CheckGroupRelation（）函数的实现如下：162 bool CheckGroupRelation（GROUP *groups, int g...

算法系列（八） RLE行程长度压缩算法

2017年02月05日 49 阅读

算法系列（八） RLE行程长度压缩算法2014-04-30 csdn博客 吹泡泡的小猫RLE（Run Length Encoding）行程长度压缩算法（也称游程长度压缩算法），是最早出现、也是 最简单的无损数据压缩算法。RLE算法的基本思路是把数据按照线性序列分成两种情况：一种是连续的 重复数据块，另一种是连续的不重复数据块。对于第一种情况，对连续的重复数据块进行压缩，压缩 方法就是用一个表示块数的属性加上一个数据块代表原来连续的若干块数据。对于第二种情况...

算法系列（九） 计算几何与图形学有关的几种常用算法（一）

2017年02月05日 51 阅读

算法系列（九） 计算几何与图形学有关的几种常用算法（一）2014-04-30 csdn博客 吹泡泡的小猫我的专业是计算机辅助设计（CAD），算是一半机械一半软件，《计算机图形学》是必修课，也是 我最喜欢的课程。热衷于用代码摆平一切的我几乎将这本教科书上的每种算法都实现了一遍，这种重 复劳动虽然意义不大，但是收获很多，特别是丢弃了多年的数学又重新回到了脑袋中，算是最大的收 获吧。尽管已经毕业多年了，但是每次回顾这些算法的代码，都觉得内心十分澎湃，如果换成现在...