考察数据结构——第一部分:数据结构简介[译]
相关文档：
考察数据结构——第二部分：队列、堆栈和哈希表 考察数据结构——第三部分：二叉树和BSTs 第一部分:数据结构简介
原文链接：Part 1: An Introduction to Data Structures
介绍:
本文是介绍在.Net平台下使用数据结构的系列文章,共分为六部分,这是本文的第一部分.本文试图考察几种数据结构,其中有的包含在.Net Framework的基类库中,有的是我们自己创建的.如果你对这些名词不太熟悉,那么我们可以把数据结构看作是一种抽象结构或是类,它通常用来组织数据,并提供对数据的操作.最常见并为我们所熟知的数据结构就是数组array,它包含了一组连续的数据,并通过索引进行访问.
在阅读本文内容之前,让我们先看看这六部分的主要内容.如果你有什么想法,或觉得本文有什么遗漏之处,希望你通过e-mail(mitchell@4guysfromrolla.com)和我联系,共同分享你的思想.假如有时间的话,我很高兴将你的建议放到合适的部分,如有必要,可以在这篇系列文章中加上第七部分. 第一部分:首先介绍数据结构在算法设计中的重要性.决定数据结构的优劣在于其性能.我们将经过严格分析数据结构的各种性能.此部分还将介绍.Net Frameword下两种常用的数据机构:Array 和ArrayList.我们将考察其结构的操作方式及其效率.
第二部分:我们将继续从更多细节上分析ArrayList结构,同时还将介绍Queue类和Stack类.和ArrayList一样,Queue和Stack存放的都是一组连续的数据集合,都属于.Net Framework基类库.与ArrayList不同的是,Stack和Queue只能以预先规定的序列顺序读取其数据(先进先出和先进后出),而ArrayList可以任意获取数据项.我们将通过示例程序来考察Queue,Stack,并通过扩展ArrayList类来实现它们.之后,我们还要分析哈希表HashTable,它象ArrayList一样可以直接访问数据,不同的是它以key(字符串)为索引.
ArrayList对数据直接读取和存储是一种理想的数据结构,同时,它也是支持数据搜索的候选方案.在第三部分,我们将考察二叉树结构,对于数据搜索而言,它比ArrayList更加有效. .Net Framework并不包含此种内置数据结构,因此需要我们自己创建.
二叉树搜索的效率受制于插入到树中的数据的顺序.如果我们插入的是有序或近似有序的数据,实际上,它的效率不如ArrayList.为了将这两种的优势结合起来,在第四部分,我门将考察一种有趣的随机数据结构——SkipList. SkipList既保留了二叉树搜索的高效率,同时输入数据的顺序对其效率影响甚微.
第五部分我们将注意力转向通常用来表现图形的数据结构.图(graph)是众多节点以及节点之间边的集合.举例来说,地图就可以图的形式来表现.城市是节点,公路则是连接节点之间的边.许多现实问题都可以抽象成图的形式,因此,图也是我们经常要用到的数据结构.
最后,第六部分我们将谈到reprisent sets(表示集?)和disjoint sets(非关联集,即交集为空?)集合是一种无序数据的集中.非关联集是指它和另外一个集合没有共同的元素.我们在程序编写时会经常用到集合和非关联集.我们将在这一部分中详细描述它.
数据结构性能分析
当我们在思考一个特别的应用程序或者程序的问题时,多数开发人员(包括我自己)都将兴趣集中到算法上以解决手头的难题,或者为应用程序加上一个很酷的特色以丰富用户的经验.我们似乎很少听到有人会为他所使用的数据结构而激动不已,啧啧赞叹. 然而,用在一个特定算法中的数据结构能够很大程度上影响其性能.最常见的例子就是在数据结构中查找一个元素.在数组中,查找过程所耗时间是与这个数组中元素的个数是成正比的.采用二叉数或者SkipLists(我找不到合适的翻译,按前所述,它包含了随机数的集合,也许看了后面的部分会想到合适的中文),耗时与数据个数比例成线型下降(sub-linear,我又黔驴词穷了).当我们要搜索大量的数据时,数据结构的选择对程序的性能尤其重要,其差别甚至达到数秒,乃至于数分钟.
既然在算法中使用的数据结构影响了算法的效率,因此比较各种数据结构的效率并从中选择一种更佳的方法就显得尤为重要.作为开发者而言,我们首先要关注的是随着存储的数据量的增长,数据结构性能是怎样随之改变的的?也就是说,每当数据结构中添加一个新元素时,它将怎样影响数据结构的运行时间?
考虑这样一种情形,我们在程序中使用了System.IO.Directory.GetFiles(路径)方法以返回文件的列表,存放到一个特定的字符串数组directory中.假设你需要搜索这个数组以判断在文件
列表中是否存在XML文件(即扩展名为.xml的文件),一种方法是扫描(scan,或者是遍历)整个数组,当找到XML文件时,就设置一个标识.代码可能是这样: using System;
using System.Collections; using System.IO; public class MyClass {
public static void Main() {
string [] fs = Directory.GetFiles(@\ bool foundXML = false; int i = 0;
for (i = 0; i < fs.Length; i++)
if (String.Compare(Path.GetExtension(fs[i]), \ {
foundXML = true; break; }
if (foundXML)
Console.WriteLine(\ else
Console.WriteLine(\ } }
现在我们来看看最糟糕的一种情况,当这个列表中不存在XML文件或者XML文件是在列表的最后,我们将会搜索完这个数组的所有元素.再来分析一下数组的效率,我们必须问问自己,\假设数组中现有n个元素,如果我添加一个新元素,增长为n+1个元素,那么新的运行时间是多少?(术语\
运行时间\不能顾名思义地认为是程序运行所消耗的绝对时间,而指的是程序完成该任务所必须执行的步骤数.以数组而言,运行时间特定被认为是访问数组元素所需执行的步骤数。)要搜索数组中的一个值，潜在的可能是访问数组的每一个元素，如果数组中有n+1个元素，就将执行n+1次检查。那就是说，搜索数组耗费的时间与数组元素个数成几何线形比。 当数据结构的长度趋于无穷大时，分析其结构的效率，我们把这种分析方法称为渐进分析（asymptotic analysis)。渐进分析中常用的符号是大写的O（big-Oh)，以O(n)的形式描述遍历数组的性能。O是术语学中big-Oh符号的表示，n则代表遍历数组时随长度增长而与之线形增长的程序执行步数。
计算代码块中算法的运行时间的一种系统方法应遵循以下步骤：
1、判断组成算法运行时间的步骤。如前所述，对于数组而言，典型的步骤应是对数组进行读写访问的操作。而对于其他数据结构则不尽然。特别地，你应该考虑的是数据结构自身的步骤，而与计算机内部的操作无关。以上面的代码块为例，运行时间应该只计算访问数组的次数，而不用考虑创建和初始化变量以及比较两个字符串是否相等的时间。 2、找到符合计算运行时间条件的代码行。在这些行上面置1。
3、判断这些置1的行是否包含在循环中，如果是，则将1改为1乘上循环执行的最大次数。如果嵌套两重或多重循环，继续对循环做相同的乘法。 4、找到对每行写下的最大值，它就是运行时间。
现在我们按照这种步骤来标记上面的代码块。首先我们已经能够确定与计算运行时间有关的代码行，再根据步骤2，在数组fs被访问的两行代码作上标记，一行是数组元素作为String.Compare()方法的参数，一行是在Console.WriteLine()方法中。我们将这两行标记为1。然后根据步骤3，String.Compare()方法是在循环中，最大循环次数为n（因为数组长度为n）。因此将该行的标记1改为n。最后，我们得到的运行时间就是标记的最大值n，记为O(n)。（译注：即为数据结构中通常所说的时间复杂度）
O(n)，或者说线形时间(linear-time)，表示了多种算法运行时间中的一种。其他还有O(log2 n)，O(n log 2 n)，O(n2)，O(2n)等等。我们无须关心这些繁杂的big-Oh记号，只需要知道在括号中的值越小，则代表数据结构的性能越好。举例来说，时间复杂度（在这里我还是觉得用时间复杂度比运行时间更能理解）为O(log n)的算法远比O(n)更有效率，因为log n 我们需要温习以下数学知识。在这里，log a b另外一种表示方法为a=b。因此，log24=2，因为2=4。Log2n增长速度比单个的n要慢得多，在第三部分我们将考察时间复杂度为O(log2n)的二叉树结构。（这个注释没多大意思啊！） 在这篇系列文章中，我们将计算每一种新的数据结构和它们的渐进操作运行时间，并通过相似的操作比较其他数据结构在运行时间上的区别。 数组：一种线形的，可以直接访问的，单一数据结构 在程序编写中，数组是最简单也是最广泛使用的数据结构。在所有的程序语言中数组都具备以下共同的属性： 1．数组的数据存储在一段连续的内存之中； 2．数组的所有元素都必须是同一种数据类型，因此数组又被认为是单一数据结构(homogeneous data structures)； 3．数组元素可以直接访问。（在很多数据结构中，这一特点是不必要的。例如，文章第四部分介绍的数据结构SkipList。要访问SkipList中的特定元素，你必须根据搜索其他元素直到找到搜索对象为止。然而对于数组而言，如果你知道你要查找第i个元素，就可以通过arrayName[i]来访问它。）（译注：很多语言都规定数组的下标从0开始，因此访问第i个元素，应为arrayName[i-1]） 以下是数组常用的操作： 1．分配空间 2．数据访问 3．数组空间重分配（Redimensioning） 在C#里声明数组时，数组为空值（null）。下面的代码创建了一个名为booleanArray的数组变量，其值为空（null）： Bool [] boolleanArray; 在使用该数组时，必须用一个特定数字给它分配空间，如下所示： booleanArray = new bool[10]; 通用的表述为： arrayName = new arrayType[allocationSize]; 2 y