博客专栏 - 数据结构

数据结构

数据结构是一门非常重要的课程，要设计出一个结构好效率高的程序，必须研究数据的特性及数据间的相互关系及其对应的存储表示，并利用这些特性和关系设计出相应的算法和程序。所以很有必要好好学习掌握数据结构。

A星寻路算法

最近再弄cocos2d-x lua手游开发，我相信大家在开发手游时经常容易碰到寻路问题。寻路算法也挺多的，这里主要总结我在开发时使用的A satrt寻路算法。 A星算法是基于启发式函数的一种寻路算法，A start的介绍就不重复了。主要是说明如何使用A start寻路算法。如图要从起点A移动到终点B，地图中表示可行走的方块。 ...

A星寻路 cocos2d-lua 地图寻路最短路径

hm4123660 评论(1) 有11150人浏览 2015-08-02 22:38

排序算法--归并排序和基数排序

前面几篇博客学习介绍了插入排序，交换排序，选择排序等排序算法。本篇博客将主要学习介绍归并排序和基数排序。学习完这两个算法， ...

基数排序归并排序排序算法排序效率数据结构

hm4123660 评论(1) 有2638人浏览 2015-04-03 23:07

排序算法--选择排序,堆排序

介绍学习完插入排序和交换排序，本篇博客来学习选择排序，选择排序的基本思想是：每趟从待排的记录中选出关键字最小的记录，顺序放在已经排好序子表的最后，直到全部记录排序完毕。由于选择排序每趟总是从无序区中选出全局最小或最大的关键字，所以适合于大量的记录中选择一部分排序记录。在这里，我们主要介绍选择排序里的直接选择排序和堆排序。 1.直接选择排序(简单选择排序) 基本 ...

堆排序选择排序排序算法数据结构

hm4123660 评论(0) 有2260人浏览 2015-04-03 16:02

排序算法--交换排序

前面学习了内排序里面的插入排序，插入排序包含直接插入排序，二分插入排序和希尔排序，其中希尔排序的速度通常比较快。这篇博� ...

交换排序冒泡排序快速排序数据结构排序算法

hm4123660 评论(1) 有1632人浏览 2015-04-02 23:49

排序算法--插入排序

排序有内部排序和外部排序，内部排序是数据记录在内存中进行排序，而外部排序是因排序的数据很大，一次不能容纳全部的排序记录，在排序过程中需要访问外存。我们这里的排序是内部排序。所谓排序，就是要整理表中的记录，使之按关键字递增(或递减)有序排列，当排序的关键字都不相同时，排序结果是唯一的。本篇博客介绍插入排序。插入排序的基本思想是：每 ...

直接排序希尔排序排序算法数据结构

hm4123660 评论(0) 有1451人浏览 2015-04-02 20:47

查找算法--哈希表查找

哈希表的概念哈希表又称散列表，是一种线性的存储结构。是根据关键码值（Key Value）而直接进行访问的数据结构。它通过把关键码值映射到哈希表中的一个位置来访问记录，以加快查找的速度。这个映射函数就做散列函数，存放记录的数组叫做散列表。哈希表存储思路以数据中每个元素的关键字K为自变量，通过散列函数h（k）计算出函数值，以该函数值作为一块 ...

哈希表哈希表冲突数据结构

hm4123660 评论(0) 有3566人浏览 2015-04-01 14:39

查找算法--树表查找之B树

前面介绍的BST(二叉排序树)和AVL(平衡二叉树)都是二叉树，用作内部查找的数据结构，即被查找的数据集不大，可以放在内存中。这篇博客将主要介绍B树,是非二叉树，用作外部查找的数据结构，其数据存放在外存中。 B－树又称为多路平衡查找树，是一种组织和维护外存文件系统非常有效的数据结构。具体讲解之前，有一点，强调一下：B-树，即为B树。因为B树的原英文名称为B-tree，而国内很多人 ...

B－树 B树数据结构多路平衡查找树

hm4123660 评论(0) 有2763人浏览 2015-03-31 20:40

查找算法--树表查找之平衡二叉树

前一篇博客学习了高效动态表查找的二叉排序树，虽然在二叉排序树上实现的插入，删除和查找等基本操作的平均时间为O(log2(n)),但随� ...

平衡二叉树 AVL 平衡因子数据结构

hm4123660 评论(0) 有2515人浏览 2015-03-30 23:43

查找算法--树表查找之二叉排序树

从前面介绍的查找方法我们知道，折半查找较顺序查找速度快，但折半查找要求表中记录必须有序，因为当在已排序的表中找到新记录恰当的位置时，需要移动许多记录以便为新记录腾出位置。有没有哪一种组织记录的方法使得记录的插入与查找都能够很快地完成呢？本篇博客介绍的树表查找就能解决这个问题。二叉排序树(BST 也叫二叉查找树) 定义：二叉排序树或者是一棵空树，或者是 ...

二叉排序树 BST 树表查找查找算法

hm4123660 评论(1) 有3261人浏览 2015-03-29 22:13

查找算法--顺序表查找

查找又称检索，是指在某种数据结构中找出满足给定条件的元素。若在查找的同时对表做修改运算(如插入删除），则相应的表称为动态查找表，否则，称为静态查找表。我们分别从线性表查找，树表查找和哈希表查找来分析总结查找算法。线性表查找线性表是最简单的一种表的组织方式，我们不考虑在查找的同时对表做修改，即在静态表上进行查找 1）顺序查找基本思路：从表中一端开始，逐 ...

顺序查找查找算法二分查找数据结构

hm4123660 评论(0) 有3864人浏览 2015-03-29 16:24

最短路径-Floyd

之前我们接触学习了Dijkstra算法求解一个顶点到其他各个顶点的最短路径和距离，但如果我们想知道每一对顶点的最短路径和距离时，可以通过以每一个顶点作为源点循环求出每对顶点之间的最小距离。除此之外，我们可以利用本篇博客即将学习的弗洛伊德(Floyd）算法来求两顶点之间的最短距离。弗洛伊德(Floyd)算法 1)算法思想原理：从任意节点i到任意节点j的最短 ...

最短路径 Floyd 弗洛伊德数据结构 c++

hm4123660 评论(0) 有4851人浏览 2015-03-28 16:41

最短路径-Dijkstra

在日常生活中，我们如果需要常常往返A地区和B地区之间，我们最希望知道的可能是从A地区到B地区间的众多路径中，那一条路径的路途最短。最短路径问题是图论研究中的一个经典算法问题，旨在寻找图（由结点和路径组成的）中两结点之间的最短路径。用于解决最短路径问题的算法被称做“最短路径算法”，有时被简称作“路径算法”。最常用的路径算法有：Dijkstra算法、A*算法、B ...

Dijkstra 最短路径 c++数据结构最短

hm4123660 评论(0) 有3635人浏览 2015-03-28 01:07

最小生成树详解

生成树和最小生成树有许多重要的应用。例如：要在n个城市之间铺设光缆，主要目标是要使这 n 个城市的任意两个之间都可以通信，但铺设光缆的费用很高，且各个城市之间铺设光缆的费用不同，因此另一个目标是要使铺设光缆的总费用最低。这就需要找到带权的最小生成树。下面开始最小生成树的学习。首先需要清楚一些概念。生成树的定义:连通图G的一个子图如果是一棵包含G的所有顶点的树，则该子图称为G的生 ...

最小生成树 Prim c++数据结构

hm4123660 评论(0) 有3514人浏览 2015-03-27 16:31

图的遍历算法详解

图是一种比较重要的数据结构，无论多复杂的图都是由顶点和边构成的，图有两种常用的存储结构为邻接矩阵和邻接表。本篇博客将使用邻接表存储图，邻接表是一种顺序分配和链式分配相结合的存储方式。邻接表是表示图的标准方法，尤其对于稀疏图节省很多存储空间，空间复杂度是O(|E|+|V|). 对于每个顶点，使用一个表存放所有邻接的顶点。我们要操作的有向图如下：通过图我们 ...

图的遍历队列深度优先广度优先

hm4123660 评论(0) 有3773人浏览 2015-03-26 20:28

二叉树详解

树是一种比较重要的数据结构，尤其是二叉树。二叉树是一种特殊的树，在二叉树中每个节点最多有两个子节点，一般称为左子节点和右子节点（或左孩子和右孩子），并且二叉树的子树有左右之分，其次序不能任意颠倒。本篇博客将详细为大家解析二叉树。首先介绍两个概念：满二叉树：在一棵二叉树中，如果所有分支结点都有左孩子和右孩子结点，并且叶子结点都集中在二叉树的最下层，这样的树叫做满二叉树 ...

二叉树 c++数据结构完全二叉树

hm4123660 评论(0) 有8352人浏览 2015-03-25 16:38

KMP算法详解

字符串模式匹配我们相信大家都有遇过，然而我们也习惯用简单匹配法（即Brute-Force算法)，其基本思路就是一个个逐一对比下去，这也是我们大家熟知的方法，然而这种算法的效率并不高，但利于理解。假设主串s="ababcabcacbab",模式串为t="abcac"，我们用肉眼很容易看出匹配位置为是s[5]--s[10];利用简单 ...

KMP C++数据结构字符串算法

hm4123660 评论(0) 有3847人浏览 2015-03-22 15:37

C++迷宫求解详解--栈

相信大家都应该听过栈吧，一直想利用栈来实现一个算法，最近有点空，就利用栈的先进后出的特性来完成迷宫求的问题，下面将详细介绍栈的实现和迷宫求解的过程，可以很好的学习栈的使用。栈有两种实现方法，一种是顺序，即数组形式，一种是线性，即链表形式，个人还是比较喜欢链表形式实现栈的基本功能。首先弄一个简单的迷宫，如图：我们很容易看出这个迷宫解的路径， ...

C++迷宫求解栈算法数据结构

hm4123660 评论(0) 有7031人浏览 2015-03-20 15:54

专栏创建者：hm4123660
创建时间：2015-04-04 19:30:48
专栏文章数：17篇
专栏被浏览：70103 次