KMP算法的两种实现(DFA&PMT)
KMP算法是一种改进的字符串匹配算法, 由D.E.Knuth, J.H.Morris和V.R.Pratt提出, 无论是基于确定有限状态自动机机(Determinstic Finite Automata, DFA)的KMP实现还是基于部分匹配表(Parital Match Table, PMT)的KMP实现,其核心思想都是利用匹配失败后的信息,尽可能的减少模式串与主串的匹配次数以达到快速匹配的目的。 朴素模式(Brute-Force)匹配算法朴素的模式匹配算法又称为暴力匹配算法,即当遇到不相等时,回退从头开始逐个比较。 1234567891011121314151617181920212223242526272829303132333435#include<stdio.h>#include<string.h>int find(char *txt, char *pat){ int i = 0; int j = 0; while(i < strlen(txt) && j < strlen(pat)) /* strl...
Skip List跳跃表
Skip lists are a data structure that can be used in place of balanced trees. Skip lists use probabilistic balancing rather than strictly enforced balancing and as a result the algorithms for insertion and deletion in skip lists are much simpler and significantly faster than equivalent algorithms for balanced trees.–William Pugh 装在整理至: Skip List（跳跃表）原理详解与实现 skiplist 跳跃表详解及其编程实现 跳表SkipList 跳表是由William Pugh发明的，上面的引言就是他给出的解释。跳表是一种随机化的数据结构，目前开源软件 Redis 和 LevelDB 都有用到它，它的效率和红黑树以及 AVL 树不相上下，但跳...
字典(Trie)树
Trie树，即字典树，又称单词查找树或键树，是一种树形结构，是一种哈希树的变种。典型应用是用于统计和排序大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是：最大限度地减少无谓的字符串比较。 1234567891011121314151617181920212223#ifndef TRIE_H#define TRIE_Htypedef struct word_trie_t word_trie_t;typedef enum bool bool;enum bool{ false = 0, true = 1,};struct word_trie_t{ bool (*insert)(word_trie_t *this, char *str); bool (*find_word)(word_trie_t *this, char *str); int (*find_prefix)(word_trie_t *this, char *str); bool (*delete)(word_trie...
图
图(graph)由顶点(vertex)与边(edge)的构成，研究元素间多对多的关系。 图由顶点(vertex)与边(edge)组成。由一条边链接的两个顶点互为邻接点。若边有方向则此时的图为有向图，连接图的边无方向则为无向图。 若一个无向图中每两个顶点之间都存在一条边，则称这个无向图为完全无向图。完全无向图中若顶点数为n，则边数为n(n-1)/2。 若一个有向图中每两个顶点都存在方向相反的两个边，则称该图为完全有向图。完全有向图中顶点数为n,边数为n(n-1)。 某个顶点的边数称为顶点的度(degree)。有向图中度又分为出度与入度，出度与入度的和为该顶点的度。 图的边数很多接近完全图的称为稠密图，边数很少的称为稀疏图。 与边有关的数据信息称为权(weight)，边上带权值的图称为网图或网络。 路径长度指一条路径上经过的边的数目。 在无向图中，若两顶点之间有路径，则称者两顶点是连通的。若无向图中任意两个顶点之间都连通，则称为连通图。如果不是连通图，则图中极大连通子图称为连通分量。连通图只有一个连通分量，即它本身，非连通图不止一个连通分量。 在有向图中，若任意两个顶点...
平衡二叉(AVL)树
平衡二叉树(balance binary tree)是二叉排序树的进化体，由G.M.Adelson-Velsky和E.M. Landis提出的，所以又叫AVL树。 平衡二叉树是指它除了具备二叉排序树的基本特征之外，还具有一个重要的特定：它的左子树与右子树的深度之差(平衡因子)的绝对值不超过1，且都是平衡二叉树。 平衡因子平衡因子(Balance Factor,BF):二叉树结点的左子树深度减去右子树深度的值。平衡二叉树的平衡因子的绝对值不超过1。平衡因子绝对值大于1的结点为根节点的子树就是最小不平衡子树。调整节点之间的链接关的基本方法就是旋转。 旋转左旋(朝左旋转) 左旋规则：在产生的最小不平衡子树根结点右孩子的右孩子处插入结点，即最小不平衡子树的根结点及其右孩子的平衡因子都为负，则以根结点的右孩子为支点进行左旋转，根结点变为支点的左孩子。 12345678910111213static Node* right_right_rotation(AVLTree k1){ AVLTree k2; k2 = k1->right; k1->rig...
二叉排序(BST)树
二叉排序树(Binary Sort Tree,BST)又称为二叉查找树,二叉搜索树,具有以下性质: 如果左子树不为空,则左子树上所有结点的值都小于根结点的值. 如果右子树不为空,则右子树上所有结点的值均大于根结点的值. 左右子树也分别为二叉排序树. 树中没有相同的结点. 如果用中序遍历二叉排序树,则遍历结果是一个递增序列. 与二分查找类似，查找过程中和关键字比较的次数不超过树的深度。当二叉排序树形态比较对称，此时与折半查找相似，时间复杂度为$O(\log_{2}n)$，最坏情况下二叉排序树是一颗单树(只有左子树或只有右子树)，时间复杂度为$O(n)$。 BST结点结构1234567typedef int Type;typedef struct BSTreeNode{ Type key; /* 关键字(键值) */ struct BSTreeNode *left; /* 左孩子 */ struct BSTreeNode *right; /* 右孩子 */ struct BSTreeNode *parent...
LRU缓存淘汰算法
LRU(Least recently used，最近最少使用)算法根据数据的历史访问记录来进行淘汰数据，其核心思想是“如果数据最近被访问过，那么将来被访问的几率也更高”。 常见的LRU实现策略是: 新数据插入到链表头部； 每当缓存命中（即缓存数据被访问），则将数据移到链表头部； 当链表满的时候，将链表尾部的数据丢弃。 但是如上实现存在一个问题：命中时需要遍历链表，找到命中的数据块索引，然后需要将数据移到头部，时间复杂度是$O(N)$。未解决遍历带来的消耗，再此设计的是一种哈希表维护的双向链表结构，以减少寻找数据块时的时间消耗。 如上图所示，每个数据块拥有2个角度的身份，一个身份是缓存双向链表的成员，一个身份是哈希表成员。 LRU结构体设计 1234567891011121314151617/*定义LRU缓存的缓存单元*/typedef struct cacheEntryS{ char key; /* 数据块的key */ char data; /* 数据块的data */ struct cacheEntryS *hashLi...
排序
方法 最好 最坏 平均 空间复杂度 稳定性 冒泡排序 $O(n)$ $O(n^2)$ $O(n^2)$ $O(1)$ 稳定 快速排序 $O(n\log_{2}n)$ $O(n^2)$ $O(n\log_{2}n)$ $O(n\log_{2}n)$ 不稳定 直接插入排序 $O(n)$ $O(n^2)$ $O(n^2)$ $O(1)$ 稳定 希尔排序 $O(n^{1.3})$ $O(1)$ 不稳定 简单选择排序 $O(n^2)$ $O(n^2)$ $O(n^2)$ $O(1)$ 不稳定 堆排序 $O(n\log_{2}n)$ $O(n\log_{2}n)$ $O(n\log_{2}n)$ $O(1)$ 不稳定 归并排序 $O(n\log_{2}n)$ $O(n\log_2{2}n)$ $O(n\log_{2}n)$ $O(n)$ 稳定 基数排序 $O(d(r+n))$ $O(d(r+n))$ $O(d(r+n))$ $O(r)$ 稳定 排序算法的稳定性: 若在原始序列中,$a_i$和$a_j$的关键字相同,$a_i$出现在$a_j$...
线性查找算法
查找是在一些(有序/无序)的数据元素中通过一定的方法找出与给定关键字相同的数据元素。 无序查找最简单的无序查找为: 12345678int sq_find(int arr[], int n, int key){ for(int i = 0; i < n; i++){ if(arr[i] == key) return i; } return -1;} 对于这个for循环查找,一般的时间浪费在了i<n的边界检查上了,因此可以设置一个监视哨兵来优化无序查找: 12345678int sq_find(int arr[], int n, int key){ int i = n; arr[0] = key; while(arr[i] != key) i--; return i;} 有序查找二分查找非递归实现 12345678910111213141516171819int BiSearch(int arr[], const int num, int begin, ...
二叉树
树(Tree)是由$n(n>=0)$个结点组成的一个具有层次关系的非线性有限集合，树中的每个元素被称为树的节点，每个节点有若干个指针指向的后继结点(子结点)。树中节点的子树数目称为节点的度(degree)。树中各结点度的最大值称为树的度，通常称为几次树。度为0的结点称为叶子结点。 二叉树二叉树每个结点最多只有两个分支，左孩子右兄弟表示法可以将一颗 多叉树转化为二叉树。 非完全二叉树：普通二叉树。 完全二叉树：除最后一层外，每层的结点数均达到最大值，在最后一层上只缺少右边的结点。 满二叉树：除叶子结点外，每个结点都有两个孩子结点，且每一层的结点数都达到最大值。一颗深度为k的二叉树有$2^{k}-1$个结点。 二叉树的性质性质1：在二叉树的第i层上至多有$2^{i-1} (i>0)$个结点。 性质2：深度为k的二叉树至多有$2^{k}-1 (i>0)$个结点。 性质3：对于任何一颗二叉树，若度为2的结点数目有 n 个，则叶子数必定为 n+1 个。 性质4：具有n个结点的完全二叉树，它的深度必为$\lfloor \log_{2^n} \rfloor +...