1. 首页
  2. 策略和技术

图的遍历（广度优先遍历）- 数据结构和算法61

图的遍历（广度优先遍历）让编程改变世界Change the world by program广度优先遍历广度优先遍历（BreadthFirstSearch），又称为广度优先搜索，简称BFS。如果以之前我们找钥匙的例子来讲，运用深度优先遍历意味着要先彻底查找完一个房间再开始另一个房间的搜索。但我们知道，钥匙放在沙发地下等犄角旮旯的可能性极低，因此我们运用新的方案：
策略和技术 2014年06月06日

图的遍历（深度优先遍历）- 数据结构和算法59

图的遍历（深度优先遍历）让编程改变世界Change the world by program图的遍历树的遍历我们谈了四种方式，大家回忆一下，树因为根结点只有一个，并且所有的结点都只有一个双亲，所以不是很难理解。但是谈到图的遍历，那就复杂多了，因为它的任一顶点都可以和其余的所有顶点相邻接，因此极有可能存在重复走过某个顶点或漏了某个顶点的遍历过程。对于图的遍历，如果
策略和技术 2014年06月06日

马踏棋盘算法（骑士周游问题）- 数据结构和算法60

马踏棋盘算法（骑士周游问题）让编程改变世界Change the world by program马踏棋盘算法（骑士周游问题）题目渊源：马踏棋盘问题（又称骑士周游或骑士漫游问题）是算法设计的经典问题之一。题目要求：国际象棋的棋盘为8*8的方格棋盘，现将“马”放在任意指定的方格中，按照“马”走棋的规则将“马”进行移动。要求每个方格只能进入一次，最终使得“马”走遍棋
策略和技术 2014年06月06日

图的存储结构（十字链表、邻接多重表、边集数组）- 数据结构和算法58

图的存储结构（十字链表、邻接多重表、边集数组）让编程改变世界Change the world by program十字链表邻接表固然优秀，但也有不足，例如对有向图的处理上，有时候需要再建立一个逆邻接表~那我们思考了：有没有可能把邻接表和逆邻接表结合起来呢？答案是肯定的，这就是我们现在要谈的十字链表(Orthogonal List)为此我们重新定义顶点表结点结构
策略和技术 2014年06月06日

图的定义与术语2 – 数据结构和算法55

图的定义与术语2让编程改变世界Change the world by program图的顶点与边之间的关系对于无向图G=(V,E)，如果边(V1,V2)∈E，则称顶点V1和V2互为邻接点(Adjacent)，即V1和V2相邻接。边(V1,V2)依附(incident)于顶点V1和V2，或者说边(V1,V2)与顶点V1和V2相关联。顶点V的度(Degree)是和V
策略和技术 2014年06月06日

图的存储结构（邻接表）- 数据结构和算法57

图的存储结构（邻接表）让编程改变世界Change the world by program邻接表（无向图）邻接矩阵看上去是个不错的选择，首先是容易理解，第二是索引和编排都很舒服~但是我们也发现，对于边数相对顶点较少的图，这种结构无疑是存在对存储空间的极大浪费。邻接表（有向图）因此我们可以考虑另外一种存储结构方式，例如把数组与链表结合一起来存储，这种方式在图结构也
策略和技术 2014年06月06日

图的存储结构（邻接矩阵）- 数据结构和算法56

图的存储结构（邻接矩阵）让编程改变世界Change the world by program图的存储结构图的存储结构相比较线性表与树来说就复杂很多。我们回顾下，对于线性表来说，是一对一的关系，所以用数组或者链表均可简单存放。树结构是一对多的关系，所以我们要将数组和链表的特性结合在一起才能更好的存放。那么我们的图，是多对多的情况，另外图上的任何一个顶点都可以被看作
策略和技术 2014年06月06日

赫夫曼编码 – 数据结构和算法52

赫夫曼编码让编程改变世界Change the world by program赫夫曼编码上一节课我们已经谈了赫夫曼树的基本原理和构造方式，而赫夫曼编码可以很有效地压缩数据（通常可以节省20%~90%的空间，具体压缩率依赖于数据的特性）。名词解释：定长编码，变长编码，前缀码定长编码：像ASCII编码变长编码：单个编码的长度不一致，可以根据整体出现频率来调节前缀
策略和技术 2014年06月06日

赫夫曼树 – 数据结构和算法51

赫夫曼树让编程改变世界Change the world by program赫夫曼树在数据膨胀、信息爆炸的今天，数据压缩的意义不言而喻。谈到数据压缩，就不能不提赫夫曼（Huffman）编码，赫夫曼编码是首个实用的压缩编码方案，即使在今天的许多知名压缩算法里，依然可以见到赫夫曼编码的影子。另外，在数据通信中，用二进制给每个字符进行编码时不得不面对的一个问题是如何使电
策略和技术 2014年06月06日

二叉树的建立和遍历算法 – 数据结构和算法47

二叉树的建立和遍历算法让编程改变世界Change the world by program有童鞋会说，我们上节课研究这么多遍历的方法干啥呢？聪明的鱼油们怎么看？！对于二叉树，思路方面我们已经谈得够多了，是时候由小甲鱼带大家来上机操作。题目要求：建议二叉树并输出每个字符所在的层数。如右图要求输出A在第一层B、C在第二层D、E在第三层视频下载备用视频下载
策略和技术 2014年06月06日

二叉树的遍历 – 数据结构和算法46

二叉树的遍历让编程改变世界Change the world by program二叉树的遍历(traversing binary tree)是指从根结点出发，按照某种次序依次访问二叉树中所有结点，使得每个结点被访问一次且仅被访问一次。这里有两个关键词小甲鱼给加红了：次序和访问二叉树的遍历次序不同于线性结构，线性结构最多也就是分为顺序、循环、双向等简单的遍历方式。
策略和技术 2014年06月06日

二叉树2 – 数据结构和算法44

二叉树2让编程改变世界Change the world by program二叉树的性质二叉树的性质一：在二叉树的第i层上至多有2^(i-1)个结点(i>=1)这个性质其实很好记忆，考试的时候懂得画出二叉树的图便可以推出二叉树的性质二：深度为k的二叉树至多有2^k-1个结点(k>=1)这里一定要看清楚哦，是2^k再-1，老方法理解！二叉树的性质三：对任何一棵二
策略和技术 2014年06月06日

二叉树的存储结构 – 数据结构和算法45

二叉树的存储结构让编程改变世界Change the world by program二叉树的存储结构树结构在计算机中的存储形式很多，可谓天马行空任你创造，只要能够按照要求完成任务即可。在前边的演示中，我们发觉很难单单只用顺序存储结构或者链式存储结构来存放。但是二叉树是一种特殊的树，由于它的特殊性，使得用顺序存储结构或链式存储结构都能够简单实现。二叉树的顺序存储
策略和技术 2014年06月06日

二叉树 – 数据结构和算法43

二叉树让编程改变世界Change the world by program二叉树的定义世上树有万千种，唯有二叉课上讲。这里的二叉是二叉树，因为二叉树使用的范围最广，最具有代表意义，因此我们重点讨论二叉树。二叉树（Binary Tree）是n（n>=0）个结点的有限集合，该集合或者为空集（空二叉树），或者由一个根结点和两棵互不相交的、分别称为根结点的左子树和右子树的
策略和技术 2014年06月06日

树的存储结构2 – 数据结构和算法42

树的存储结构让编程改变世界Change the world by program孩子表示法我们这次换个角度来考虑，由于树中每个结点可能有多棵子树，可以考虑用多重链表来实现。就像我们虽然有计划生育，但我们还是无法确保每个家庭只养育一个孩子的冲动，那么对于子树的不确定性也是如此。右图中，树的度为（ ）如果我们用“孩子表示法”，聪明的鱼油可以想出多少种可行方案？这里我
策略和技术 2014年06月06日

树 – 数据结构和算法40

树让编程改变世界Change the world by program树结构之前我们一直在讨论的是一对一的线性结构，无论是线性表也好，栈和队列也罢，都是2P模式。可现实生活中，3P、4P等现象比比皆是，例如一个年轻的妈妈生了4个孩子，而每个孩子都不像他们的爸爸，那么这类情况我们用线性结构的形式就不足以描述了！所以我们需要研究这种一对多的数据结构：树解下来的一些列
策略和技术 2014年06月06日

树的存储结构 – 数据结构和算法41

树的存储结构让编程改变世界Change the world by program树的存储结构不好意思哈，这节课又需要大家搞脑子了。对于知识，你理解的越多，需要记住的就越少！上节课我们简单的介绍了树结构的强大，这节课我们来关心一下如何在内存中安排树这种结构的存放。说到存储结构，就会想到我们前面章节讲过的顺序存储和链式存储两种基本结构。对于线性表来说，很直观就可以
策略和技术 2014年06月06日

KMP算法之NEXT数组代码原理分析 – 数据结构和算法38

KMP算法之NEXT数组代码原理分析让编程改变世界Change the world by programKMP算法之NEXT数组代码原理分析NEXT数组：当模式匹配串T失配的时候，NEXT数组对应的元素指导应该用T串的哪个元素进行下一轮的匹配。i（后缀）= 1 2 。3 4 5 6 7 。8 9j（前缀）= 0 1 0 1 2 3 4 2 1 2 3详细分析请看
策略和技术 2014年06月06日

KMP算法之最终实现及优化 – 数据结构和算法39

KMP算法之最终实现及优化让编程改变世界Change the world by programKMP算法之最终实现及优化搞定了NEXT数组，KMP算法就易如反掌了。一起来完成：kmp.cKMP模式匹配算法改进后来有人发现，KMP算法是有缺陷的。比如我们的主串 S =“aaaabcde”，子串 T =“aaaaax”，其中很容易得到next数组为012345。
策略和技术 2014年06月06日
加载更多