yangyang

a .NET Developer

Data Structures and Algorithms


浅谈算法和数据结构: 十一 哈希表

在前面的系列文章中,依次介绍了基于无序列表的顺序查找,基于有序数组的二分查找,平衡查找树,以及红黑树,下图是他们在平均以及最差情况下的时间复杂度: 可以看到在时间复杂度上,红黑树在平均情况下插入,查找以及删除上都达到了lgN的时间复杂度。 那么有没有查找效率更高的数据结构呢,答案就是本文接下来要介绍了散列表,也叫哈希表(Hash Table) 什么是哈希表 哈希表就是一种以 键-值(key-indexed) 存储数据的结构,我们只要输入待查找的值即key,即可查找到其对应的值。 哈希的思路很简单,如果所有的键都是整数,那么就可以使用一个简单的无序数组来实现:将键作为索引,值即为其对应的值,这样就可以快速访问任意键的值。这是对于简单的键的情况,我们将其扩展到可以处理更加复杂的类型的键。 使用哈希查找有两个步骤: 使用哈希函数将被查找的键转换为数组的索引。在理想的情况 …

Hashtable Dictionary .NET

浅谈算法和数据结构: 十二 无向图相关算法基础

从这篇文章开始介绍图相关的算法,这也是Algorithms在线课程第二部分的第一次课程笔记。 图的应用很广泛,也有很多非常有用的算法,当然也有很多待解决的问题,根据性质,图可以分为无向图和有向图。本文先介绍无向图,后文再介绍有向图。 之所以要研究图,是因为图在生活中应用比较广泛: 无向图 图是若干个顶点(Vertices)和边(Edges)相互连接组成的。边仅由两个顶点连接,并且没有方向的图称为无向图。 在研究图之前,有一些定义需要明确,下图中表示了图的一些基本属性的含义,这里就不多说明。 图的API 表示 在研究图之前,我们需要选用适当的数据结构来表示图,有时候,我们常被我们的直觉欺骗,如下图,这两个其实是一样的,这其实也是一个研究问题,就是如何判断图的形态。 要用计算机处理图,我们可以抽象出以下的表示图的API: Graph的API的实现可以由多 …

.NET

浅谈算法和数据结构: 十 平衡查找树之B树

前面讲解了平衡查找树中的2-3树以及其实现红黑树。2-3树种,一个节点最多有2个key,而红黑树则使用染色的方式来标识这两个key。 维基百科对B树的定义为“在计算机科学中,B树(B-tree)是一种树状数据结构,它能够存储数据、对其进行排序并允许以O(log n)的时间复杂度运行进行查找、顺序读取、插入和删除的数据结构。B树,概括来说是一个节点可以拥有多于2个子节点的二叉查找树。与自平衡二叉查找树不同,B-树为系统最优化大块数据的读和写操作。B-tree算法减少定位记录时所经历的中间过程,从而加快存取速度。普遍运用在数据库和文件系统。” 定义 B 树可以看作是对2-3查找树的一种扩展,即他允许每个节点有M-1个子节点。 根节点至少有两个子节点 每个节点有M-1个key,并且以升序排列 位于M-1和M key的子节点的值位于M-1 和M key对 …

.NET Algorithm

浅谈算法和数据结构: 九 平衡查找树之红黑树

前面一篇文章介绍了2-3查找树,可以看到,2-3查找树能保证在插入元素之后能保持树的平衡状态,最坏情况下即所有的子节点都是2-node,树的高度为lgN,从而保证了最坏情况下的时间复杂度。但是2-3树实现起来比较复杂,本文介绍一种简单实现2-3树的数据结构,即红黑树(Red-Black Tree) 定义 红黑树的主要是想对2-3查找树进行编码,尤其是对2-3查找树中的3-nodes节点添加额外的信息。红黑树中将节点之间的链接分为两种不同类型,红色链接,他用来链接两个2-nodes节点来表示一个3-nodes节点。黑色链接用来链接普通的2-3节点。特别的,使用红色链接的两个2-nodes来表示一个3-nodes节点,并且向左倾斜,即一个2-node是另一个2-node的左子节点。这种做法的好处是查找的时候不用做任何修改,和普通的二叉查找树相同。 根据以上描述,红黑树定义如下: …

Red-Black Tree .NET

浅谈算法和数据结构: 八 平衡查找树之2-3树

前面介绍了二叉查找树(Binary Search Tree),他对于大多数情况下的查找和插入在效率上来说是没有问题的,但是他在最差的情况下效率比较低。本文及后面文章介绍的平衡查找树的数据结构能够保证在最差的情况下也能达到lgN的效率,要实现这一目标我们需要保证树在插入完成之后始终保持平衡状态,这就是平衡查找树(Balanced Search Tree)。在一棵具有N 个节点的树中,我们希望该树的高度能够维持在lgN左右,这样我们就能保证只需要lgN次比较操作就可以查找到想要的值。不幸的是,每次插入元素之后维持树的平衡状态太昂贵。所以这里会介绍一些新的数据结构来保证在最坏的情况下插入和查找效率都能保证在对数的时间复杂度内完成。本文首先介绍2-3查找树(2-3 Search Tree),后面会在此基础上介绍红黑树和B树。 定义 和二叉树不一样,2-3树运行每个节点保存1个或者两个的值。 …

.NET Algorithm

浅谈算法和数据结构: 七 二叉查找树

前文介绍了符号表的两种实现,无序链表和有序数组,无序链表在插入的时候具有较高的灵活性,而有序数组在查找时具有较高的效率,本文介绍的二叉查找树(Binary Search Tree,BST)这一数据结构综合了以上两种数据结构的优点。 二叉查找树具有很高的灵活性,对其优化可以生成平衡二叉树,红黑树等高效的查找和插入数据结构,后文会一一介绍。 一 定义 二叉查找树(Binary Search Tree),也称有序二叉树(ordered binary tree),排序二叉树(sorted binary tree),是指一棵空树或者具有下列性质的二叉树: 1. 若任意节点的左子树不空,则左子树上所有结点的值均小于它的根结点的值; 2. 若任意节点的右子树不空,则右子树上所有结点的值均大于它的根结点的值; 3. 任意节点的左、右子树也分别为二叉查找树。 4. 没有键值相等的节点(no …

Binary Search Tree Data Structure

浅谈算法和数据结构: 六 符号表及其基本实现

前面几篇文章介绍了基本的排序算法,排序通常是查找的前奏操作。从本文开始介绍基本的查找算法。 在介绍查找算法,首先需要了解符号表这一抽象数据结构,本文首先介绍了什么是符号表,以及这一抽象数据结构的的API,然后介绍了两种简单的符号表的实现方式。 一符号表 在开始介绍查找算法之前,我们需要定义一个名为符号表(Symbol Table)的抽象数据结构,该数据结构类似我们再C#中使用的Dictionary,他是对具有键值对元素的一种抽象,每一个元素都有一个key和value,我们可以往里面添加key,value键值对,也可以根据key来查找value。在现实的生活中,我们经常会遇到各种需要根据key来查找value的情况,比如DNS根据域名查找IP地址,图书馆根据索引号查找图书等等: 为了实现这一功能,我们定义一个抽象数据结构,然后选用合适的数据结构来实现: …

Symbol Table Binary Search

浅谈算法和数据结构: 五 优先级队列与堆排序

在很多应用中,我们通常需要按照优先级情况对待处理对象进行处理,比如首先处理优先级最高的对象,然后处理次高的对象。最简单的一个例子就是,在手机上玩游戏的时候,如果有来电,那么系统应该优先处理打进来的电话。 在这种情况下,我们的数据结构应该提供两个最基本的操作,一个是返回最高优先级对象,一个是添加新的对象。这种数据结构就是优先级队列(Priority Queue) 。 本文首先介绍优先级队列的定义,有序和无序数组以及堆数据结构实现优先级队列,最后介绍了基于优先级队列的堆排序(Heap Sort) 一 定义 优先级队列和通常的栈和队列一样,只不过里面的每一个元素都有一个”优先级”,在处理的时候,首先处理优先级最高的。如果两个元素具有相同的优先级,则按照他们插入到队列中的先后顺序处理。 优先级队列可以通过链表,数组,堆或者其他数据结构实现。 二 实现 数组 …

Priority Queue Heap-Sort

浅谈算法和数据结构: 四 快速排序

上篇文章介绍了时间复杂度为O(nlgn)的合并排序,本篇文章介绍时间复杂度同样为O(nlgn)但是排序速度比合并排序更快的快速排序(Quick Sort)。 快速排序是20世纪科技领域的十大算法之一 ,他由C. A. R. Hoare于1960年提出的一种划分交换排序。 快速排序也是一种采用分治法解决问题的一个典型应用。在很多编程语言中,对数组,列表进行的非稳定排序在内部实现中都使用的是快速排序。而且快速排序在面试中经常会遇到。 本文首先介绍快速排序的思路,算法的实现、分析、优化及改进,最后分析了.NET 中列表排序的内部实现。 一 原理 快速排序的基本思想如下: 对数组进行随机化。 从数列中取出一个数作为中轴数(pivot)。 将比这个数大的数放到它的右边,小于或等于它的数放到它的左边。 再对左右区间重复第三步,直到各区间只有一个数。 如上图所示快 …

Quick Sort Median of three partitioning 3-way partitioning

浅谈算法和数据结构: 三 合并排序

合并排序,顾名思义,就是通过将两个有序的序列合并为一个大的有序的序列的方式来实现排序。合并排序是一种典型的分治算法:首先将序列分为两部分,然后对每一部分进行循环递归的排序,然后逐个将结果进行合并。 合并排序最大的优点是它的时间复杂度为O(nlgn),这个是我们之前的选择排序和插入排序所达不到的。他还是一种稳定性排序,也就是相等的元素在序列中的相对位置在排序前后不会发生变化。他的唯一缺点是,需要利用额外的N的空间来进行排序。 一 原理 合并排序依赖于合并操作,即将两个已经排序的序列合并成一个序列,具体的过程如下: 申请空间,使其大小为两个已经排序序列之和,然后将待排序数组复制到该数组中。 设定两个指针,最初位置分别为两个已经排序序列的起始位置 比较复制数组中两个指针所指向的元素,选择相对小的元素放入到原始待排序数组中,并移动指针到下一位置 重复步骤3直到某一指 …

Merge Sort Algorithm