字典树
浏览: 3155
2018年01月16日
字典树简介 字典书（Trie Tree），又称单词查找树，是键树的一种，典型应用是用于统计，排序和保存大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。 字典树有3个基本性质： 1、根节点不包含字符，其余的每个节点都包含一个字符； 2、从根节点到某...
HashTable相关操作实现
浏览: 2745
2018年01月15日
前言 学过Java的人肯定对Hash这个词非常之熟悉,HashTable、HashSet、HashMap等都是对哈希表的封装或改进。这次我们来看下哈希表用C语言表示的封装实现。哈希表 哈希表又叫散列表，是实现字典操作的一种有效数据结构。哈希表的查询效率极高，在没有冲突（后面会介绍）的...
内部排序总结
浏览: 2789
2018年01月14日
内部排序总结 这篇博文我们简要地总结下各种内部排序方法。 这10种排序算法中，前面7种属于建立在“比较”基础上的排序算法，通过决策树已经证明，任何基于比较进行的排序算法的时 间复杂度不可能再优于O(n*logn)。后面3种不是建立在比较的基础上的，因此，可以达到线性运行时间。 ...
![内部排序[5]计数排序、基数排序和桶排序](http://www.vxzsk.com/upload/top/3881dbbc-5282-4d1c-9b0f-e739024a602820170112.jpg)
内部排序[5]计数排序、基数排序和桶排序
浏览: 2868
2018年01月13日
前言 最后三种排序算法了，由于都不是基于比较的排序，因此这三种排序算法可以以线性时间运行。但是因为限制条件的特殊性，因此应用面没有基于元素比较的排序算法广，但是在很多特定的情况下还是蛮有用途的，而且效率极高。计数排序 计数排序是建立在这样的前提条件下的：假设n个输入元素的每一个都是0...
![内部排序[4]归并排序和快速排序](http://www.vxzsk.com/upload/top/0b85aa61-7d3c-4e1f-8b2e-bbb3b46fe02a20170111.jpg)
内部排序[4]归并排序和快速排序
浏览: 2827
2018年01月11日
前言 之所以把归并排序和快速排序放在一起探讨，很明显两者有一些相似之处：这两种排序算法都采用了分治的思想。下面来逐个分析其实现思想。归并排序 实现思想 归并的含义很明显就是将两个或者两个以上的有序表组合成一个新的有序表。归并排序中一般所用到的是2-路归并排序，...
![内部排序[3]堆排序](http://www.vxzsk.com/upload/top/d2cce617-8d84-4f87-9a90-a94490e12eec20170109.jpg)
内部排序[3]堆排序
浏览: 2886
2018年01月09日
前言 堆排序、快速排序、归并排序（下篇会写这两种排序算法）的平均时间复杂度都为O（n*logn）。要弄清楚堆排序，就要先了解下二叉堆这种数据结构。本文不打算完全讲述二叉堆的所有操作，而是着重讲述堆排序中要用到的操作。比如我们建堆的时候可以采用堆的插入操作（将元素插入到适当的位置，使新的序列...
![内部排序[2]冒泡排序和选择排序](http://www.vxzsk.com/upload/top/149ef922-2201-40c2-accc-7dd79075146a20170103.jpg)
内部排序[2]冒泡排序和选择排序
浏览: 2523
2018年01月05日
前言 之所以把冒泡排序和选择排序放在一起，是因为二者的实现代码很相似，而且都是最基本的排序方式，非常容易理解和实现。当然，如果仅仅是为了讲述这两种排序方式，那也根本没必要写这篇博文了。和上篇博文一样，我会在冒泡排序和选择排序原始代码的基础上给出一些改进和优化，这才是本文的重点所在。原始冒泡...
内部排序(1)：插入排序和希尔排序的N中实现
浏览: 2709
2018年01月03日
前言 本来想将所有的内部排序总结为一篇博文，但是随着研究的深入，还是放弃了这个念头，斟前酌后，还是觉得分开来写比较好，具体原因，看完本篇博文也就自然明了了。 本篇文章主要探讨插入排序和希尔排序，之所将二者放在一起，很明显，是因为希尔排序是建立在插入排序的基础之上的。 注：以下各排序...
C语言二叉树的实现
浏览: 3424
2018年01月02日
二叉排序树简介 二叉排序树（Binary Sort Tree，简称BST），又称二叉查找树，是红黑树、AVL树等的基础。它或是一棵空树，或者是具有下列性质的一棵二叉树： 1、若它的左子树不空，则左子树上所有节点的值均小于它的根节点的值； 2、若它的右子树不空，则右子树上所有节点的...
图的深度优先搜索和广度优先搜索
浏览: 3666
2017年12月31日
图的存储结构 本文的重点在于图的深度优先搜索（DFS）和广度优先搜索（BFS），因此不再对图的基本概念做过多的介绍，但是要先大致了解下图的几种常见的存储结构。邻接矩阵 邻接矩阵既可以用来存储无向图，也可以用来存储有向图。该结构实际上就是用一个二维数组（邻接矩阵）来存储顶点的信息和顶点...
模式匹配算法之BF算法及KMP算法
浏览: 2778
2017年12月30日
模式匹配 子串的定位操作通常称为串的模式匹配。模式匹配的应用很常见，比如在文字处理软件中经常用到的查找功能。我们用如下函数来表示对字串位置的定位：int index(const string &Tag,const string &Ptn,int pos) 其中，Tag为主串，Ptn为子串...
huffman树及huffman编码的算法实现
浏览: 3206
2017年12月29日
Huffman Tree简介 赫夫曼树（Huffman Tree），又称最优二叉树，是一类带权路径长度最短的树。假设有n个权值{w1,w2,...,wn}，如果构造一棵有n个叶子节点的二叉树，而这n个叶子节点的权值是{w1,w2,...,wn}，则所构造出的带权路径长度最小的二叉树就被称为...
二叉树的层序遍历算法
浏览: 3853
2017年12月26日
前面有篇博客详细分析了二叉树三种遍历（前序、中序、后序）方式的递归与非递归实现，参见：http://www.vxzsk.com/420.html，但把二叉树的层序遍历算法给漏掉了，实际上也不能说漏掉了，毕竟层序遍历的实现方法与这三种遍历的实现方法有所不同，因此单独拿出来分析比较合适。 二叉...
二叉树递归遍历与非递归遍历
浏览: 2799
2017年12月26日
二叉树是一种非常重要的数据结构，很多其他数据机构都是基于二叉树的基础演变过来的。二叉树有前、中、后三种遍历方式，因为树的本身就是用递归定义的，因此采用递归的方法实现三种遍历，不仅代码简洁且容易理解，但其开销也比较大，而若采用非递归方法实现三种遍历，则要用栈来模拟实现（递归也是用栈实现的）。下面先...
链式队列demo代码实现
浏览: 2819
2017年12月13日
队列的链式实现结构图，如下在这个队列里面：r 为低， f 为顶该队列为链式队列，初建队列时，队头和队尾均指向头结点，头结点中不存放数据，只存放指针，头结点的下一个节点才开始存放数据，这这样做的目的是为了在入队和出队时方便对队列的操作，而不用考虑特殊情况。C语言代码demo实现#include<s...
什么是尾递归(java实现)
浏览: 3244
2017年12月11日
在《数据结构与算法分析：C描述》（Data Structures and Algorithm Analysis In C）的第三章中，以打印链表为例，提到了尾递归（tail recursion）并指出了尾递归是使用递归极其不当的例子，它指出虽然编译器会对尾递归自动优化，但即便如此最好还是不要去写...
静态链表的实现(含代码)
浏览: 2928
2017年12月11日
以前学习的各种链表都是由指针实现的，链表中结点的分配和回收(即释放)都是由系统提供的标准函数malloc和free动态实现的，故称之为动态链表。但是有的高级语言，如BASIC、FORTRAN等，没有提供”指针”这种数据类型，此时若想采用链表做存储结构，就必须使用”游标”来模拟指针，由程序员自己编...
动态栈的链式代码实现
浏览: 2806
2017年12月08日
以下为操作栈的算法，该栈为动态栈。在该栈中，pTop指向的节点中存放该栈的栈顶数据,pBottom指向的节点的上一个节点存放该栈的栈底数据，pBottom指向的节点中不存放有效数据，这样做的目的是为了在进行入栈和出栈时方便对栈的操作，而不用考虑特殊情况操作系统：ubuntu编译软件：gcc结果截...
线性表的链式存储结构代码实现
浏览: 3511
2017年12月07日
线性表的顺序存储结构要求逻辑关系上相邻的元素在物理位置上也相邻，这样方便了随机存取，但是在插入和删除元素时，需要移动大量元素，而线性表的链式存储则不要求逻辑上相邻的元素在物理位置上也相邻，因此它没有顺序存储结构的可随机存取的优点，不过在插入和删除元素时比较方便。以下为操作链表的算法，该链表为动态...
操作队列的算法代码实现
浏览: 2958
2017年12月05日
以下为操作队列的算法，该队列为静态队列，用循环数组实现。给该队列分配的内存长度为len+1，但实际只用了len个内存空间来保存数据，这样做是为了更方便判断队列的满与空。队列中front位置中存放的是队首的数据，rear位置的前一个位置中存放队尾的数据，而rear位置中则没有数据存放，这样做的目的...
- 数据结构与算法(23)