学步园

作者：Scott Mitchell

时间：2003年11月

摘要：这篇文章是关注重要的数据结构及它们的应用的系列文章的开始。该系列文章一共分六部分。我们将研究.NET Framework中内建的数据结构和我们自己创建的数据结构。第一部分我们主要关注数据结构是什么，如何有效地分析数据结构和为什么这样的分析是重要的。在这篇文章中，我们将研究在.NET Framework中常用的两种数据结构：Array和ArrayList。

 

前言：

欢迎进入系列文章的第一部分：在.NET中使用数据结构。虽然在这个系列文章中，我们将研究不同的数据结构，一些包含在.NET Framework基础类库中，还有一些我们自己创建的数据结构。如果你不熟悉“数据结构”术语，我简单介绍一下。数据结构是抽象的结构或类，用于组织数据并提供在数据上的不同操作。最常用、或许是最有名的数据结构是数组，它包含通过索引访问的连续的数据集。

         在进入文章的内容之前，让我简单介绍一下共分六部分的文章系列，对它有个整体的了解。如果你认为有任何主题是错误的，请你发Mail给我:mitchell@4guyfromrolla.com,共享你的想法。只要有空，我将非常高兴将你的建议增加到文章的适当部分，如果有必要，我可以在该系列中增加第七部分。

         在该系列文章的第一部分，我们将了解一下为什么数据结构是重要的，以及它对算法性能的影响。为了确定数据结构对性能的影响，我们需要仔细分析一个数据结构完成的不同操作。最后我们将关注.NET Framework中的两种数据结构：Array和ArrayList。也许你在做过的项目已经用过这两种数据结构。在这篇文章中，我们将研究它提供什么样的操作以及这些操作的效率。

         在第二部分，我们将更深入地研究ArrayList类以及和它类似的Queue和Stack类。和ArrayList一样，Queue和Stack类存储连续的数据集合并存在于.NET Framework基础类库中。然而，不像ArrayList可以随意地访问任何数据项，Queue和Stack只允许数据以预先确定的连续的顺序访问。我们将研究一些使用Queues和Stacks的应用程序，并通过扩展ArralyList类来实现这两个类。在研究Queues和Stacks之后，我们将了解一下HashTables，它允许像ArrayList一样直接访问，但通过字符串关键字进行索引。

         ArrayLists适合于直接访问与存储数据，但它并不适合存储需要被搜索的数据。在第三部分，我们将研究binary search tree数据结构，它提供比ArrayList更有效的搜索方法。.NET　Framework不提供内建的binary search tree数据结构，我们不得不自已创建。

         搜索一个binary search tree的效率与数据插入到树中的次序有关。如果数据按排序或就近排序的顺序插入，binary search tree将失去所有的与ArrayList相比效率上的优点。为了解决这个问题，在第四部分，我们将研究有趣的随机的数据结构－SkipList。SkipList可以高效地搜索一个binary search tree,而不受到数据插入顺序的影响。

         在第五部分，我们将关注表现图的数据结构。一个图是节点的集合，并带有连接不同节点的边线。例如，一个地图可以用图形象化地表示，城市用节点表示，高速公路用节点之间的边线表示。许多真实世界的问题都可以图来抽象地定义，所以图是一种常用的数据结构。

         最后，在第六部分我们将讨论表示集合和不相交集合的数据结构。一个集合是数据的无次序的聚集。不相交的集合是任何两个集合之间没有公共的元素的集合。这两种集合在程序经常使用，我们将在最后的部分详细介绍它们。

 

分析数据结构的性能

         当考虑一个特定的应用程序或编程问题时，许多开发者(包含我)的乐趣在于通过自己编写算法解决遇到的问题，或者通过为应用程序增加cool的特性来增强用户体验。你很少听说有人因为他们使用的数据结构而兴奋。然而，对于一定特定的算法来说，不同的数据结构会对性能产生很大的影响。一个通常的例子是在一个数据结构中寻找一个元素。对于数组来说，这个查找需要的时间与查找元素的数量成正比。对于binary search trees或SkipLists来说，当搜索大量数据时，花费的时间是次线性的。数据结构的选择会影响到应用程序性能的好坏。

         既然算法使用的数据结构会对算法的性能产生很大的影响，那么关键的是要有一种严格的方法来比较不同数据结构的效率。对于使用数据结构的开发者来说，主要感兴趣的是当存储的数据数量增加时数据结构的性能如何变化。也就是说，在数据结构中每增加一个新的元素，会对数据结构的操作运行时间产生多大的影响？

         考虑这样一个情况，你有一个程序，用System.IO.Directory.GetFiles(path)方法返回用字符串数组存储的一个特定目录中的文件列表。现在，假如你想通过搜索这个数组去发现文件列表中存在的XML文件(即扩展名是.xml的文件)。一种方法是检查整个数组，在遇到XML文件时设置一些标志。程序代码如下：

using System;

using System.Collections;

using System.IO;

 

public class MyClass

{

   public static void Main()

   {

      string [] fs = Directory.GetFiles(@"C:/Inetpub/wwwroot");

      bool foundXML = false;

      int i = 0;

      for (i = 0; i < fs.Length; i++)

         if (String.Compare(Path.GetExtension(fs[i]), ".xml", true) == 0)

         {

            foundXML = true;

            break;

         }

  

     if (foundXML)

        Console.WriteLine("XML file found - " + fs[i]);

     else

        Console.WriteLine("No XML files found.");

     

   }

}

 

         我们先看一下最坏的情况，当文件列表中没有XML文件或XML文件是最后一个文件，我们不得不搜索整个数组的每个元素。为了按一定的顺序分析数组的效率，我们必须问自己“假设有一个n个元素的数组。如果增加另外一个元素，这个数组就有n+1元素，那增加元素后的新的运行时间是多少？”(术语“运行时间”，并不是度量程序运行的绝对时间，而是表示程序完成指定任务的步骤数。当使用数组时，典型的步骤数是需要完成多少次数组访问。)为了在数组中搜索一个值，我们需要访问每一个数组值，所以如果我们有n+1个数组元素，我们必须检查n+1个元素。也就是说，搜索一个数组的花费的时间与数组中的元素数量成正比。

         这种分析方法被称为渐近分析，即当数据结构中的数据数量接近无穷大时，数据结构的效率如何变化。在渐近分析中常用的符号表示法是big-Oh。在big-Oh中用O(n)表示搜索一个数组的性能。大写字母O是big-Oh符号中的专用符号。n表示搜索数组的操作步骤数，它随着数组的增大而线性地增加。

         计算一个代码段的渐近运行时间，更系统的方法请遵循下面的步骤：

1.          确定组成算法运行时间的步骤。如前所述的数组，被考虑的步骤应该是对数组的读写访问。其他的数据结构也许不同。你不能简单地认为数据结构中包含的操作步骤就是计算机完成的原子操作。也就是说，对于上面的代码段，我分析它的运行时间时，只计算访问数组的操作的次数，而不关心创建和初始化变量以及比较字符所用的时间。

2.          找到你用于计算运行时间的代码行。在那些代码行后标一个1。

3.          对于那些标了1的代码行，看看是否处在一个循环中。如果是这样，将1改为循环的最高计数。如果有两个或更多的嵌套循环，则将每个循环的计数相乘。

4.          找到你写下的最大的一个值，这就是运行时间。

让我们在上面的代码段中使用这些步骤。我们已经标出我们感兴趣的步骤，也就是数组访问操作，第一步工作已经完成。进入第二步，注意访问数组fs的两行代码：在String.Compare()和Console.WriteLine()方法中fs数组被作为参数，所以在每行标上一个1。现在，进入第3步，在循环中，String.Compare()访问fs的次数最高为n次(n是数组的大小)。因此，擦掉循环中的1并改为n。最后，我们发现最大值是n,所以运行时间用O(n)表示。

O(n)或者叫线性时间，表现了无数种渐近运行时间中的一种。其他的包含O(log2 n), O(n log2 n), O(n2), O(2n)等等。当n值增大时，括号中表达式的值越小，则数据结构的性能越好。例如:运行在O(log n)上的操作的效率比运行在O(n)上的高，因为log n<n。

 

注意：在这里，你需要复习一下数学知识。Loga b=y的另一种表示方法是a^y=b。所以，Log₂ 4=2，因为2²=4。同样地，Log₂ 8=3，因为2³=8。很明显，Log₂ n的增长速度比单独的n慢得多，因为当n=8, Log₂ n=3。在第三部分我们将研究binary search trees，它的搜索操作只花费O(Log₂ n)的运行时间。

 

通过该系列文章，我们将计算每个新的数据结构的操作的渐近运行时间，并比较不同数据结构中类似操作的运行时间。

 

大家熟悉的、线性的、直接访问的、存储同类型数据的数据结构－数组

数组是计算机程序中最简单和最广泛使用的数据结构。在任何编程语言中，数组都拥有一些共同特性：

l          数组中的数据内容存储在连续的内存空间中

l          数组中的所有元素都是相同的类型；所以数组被称为同类数据结构。

l          数组元素可以被直接访问。(许多其他的数据结构不是这样的。例如：在这个系列文章的第四部分，我们将研究SkipList数据结构。为了访问SkipList的每个元素，你必须通过其他元素去搜索你要找的元素。对于数组来说，无论何时，如果你想要访问数组中的一个元素，你只要简单地使用这样的代码：arrayName[i]。)

在数组上进行的常用操作：

l          分配空间

l          访问元素

l          改变大小

在C#中，当你初次申明一个数组时，它被赋与一个null值。例如，下面的代码简单地创建一个变量booleanArrary,它的值等于null:

bool [] booleanArray;

在我们使用数组之前，我们必须分配一定数目的元素。通过下面的语法实现：

booleanArray = new bool[10];

或都更通用的表示：

ArrayName = new arrayType[allocationSize];

这样会在CLR－managed堆中分配足够大的连续的内存块用于保存allocationSize数目的arrayTypes。如果arrayType是值类型，allocationSize数目的unboxed arrayType值被创建。如果arrayType是引用类型，allocationSize数目的arrayType引用被创建。(如果你不熟悉引用类型与值类型，以及managed heap与stack之间的区别，你参考Understanding .NET's Common Type System)

为了帮助理解.NET Framework如何存储数组的内部数据,请考虑下面的例子:

         bool [] booleanArray;

         FileInfo [] files;

         booleanArray = new bool[10];

         files = new FileInfo[10];

         这里,booleanArray是一个值类型System.Boolean的数组,而fies数组是引用类型数组.。图1显示了在这四行代码执行后CLR-managed堆的分配情况。

 

图1在managed heap中数组内容在内存中的连续分布

 

值得注意的是在files数组中10个元素是对FileInfo实例的引用。图2显示了如果我们将FileInfo实例分配给files数组中的一些元素后内存的分布情况：

 

图2在managed heap中数组内容在内存中的连续分布

 

在.NET中所有的数组都允许读和写。访问数组元素的语法是：

// Read an array element

bool b = booleanArray[7];

 

// Write to an array element

booleanArray[0] = false;