最基础的数据结构(转自程序员杂志)(选一)

任何一个受过专业训练的程序员，对“数据结构”这门课程中涉及到的各种数据结构都不会感到陌生。但是，在实际的编程工作中，大部分的数据结构都不会用到，而且也许永远都不会用到。造成这种现象的原因有二：一是根据80/20法则，常用的数据结构只会占到少部分；二是计算机语言往往已经对常用的数据结构进行了良好的封装，程序员不需要关心内部的实现。 
　　 虽然如此，深入地理解基本数据结构的概念和实现细节，仍然是每一个程序员的任务。这不仅是因为，掌握这些知识，将有利于更加正确和灵活地应用它们，而且也是因为，对于语言背后的实现细节的求知欲，是一个优秀的程序员的素质。 
　　 本文将讨论实际编程最经常使用的三种数据结构：字符串、数组和Hash表，比较它们在不同语言中的实现思路，并涉及它们的使用技巧。 
　　 
　　字符串 
　　 严格地说，字符串（string）甚至不能算作一种单独的数据结构，至少在C语言中，它仅仅是某种特定类型的数组而已。但是，字符串在实际使用中是如此重要，在不同语言中的实现又差异颇大，因此，它值得被作为一种抽象数据类型单独进行讨论，并且在我们讨论的三种结构中排名第一。 
　　 最经典的字符串实现，应该是C语言中的零终结(null-terminated)字符串。如上所述，C风格的字符串实质上是一个字符数组，它依次存放字符串中的每个字符，最后以零字符（’\0’，表示为常量null）作为结束。因此，字符串占据的空间比它实际的长度要多1个单元。在实际应用中，它常以数组或字符指针的形式被定义，如下例： 
　　 
　　char[] message = “this is a message”; 
　　char* pmessage = “an other message”; 
　　 
　　 C语言中，字符串并不是一种独立的数据类型，也没有提供将字符串作为一个整体进行处理的运算符。对字符串的所有操作，实际上都是通过对字符数组的操作来完成。 
　　 试想一个函数，功能是求C风格字符串的长度。实现的思路是：设置一个计数器，然后用一个指针遍历整个字符数组，同时对计数器进行累加，直到字符串结束（指针指向了null）。实际上，C语言中的strlen函数也是这么实现的。这种方式看上去非常合理，但是在处理一个非常大的字符数组时，会遭遇到严重的性能问题。如果一个字符串长达数M甚至更大，那么求其长度的操作，需要执行数百万次甚至更长的循环。更糟糕的是，由于这个结果没有被缓存，所以每次求长度的操作都会重复执行这些循环。 
　　 C风格字符串的另一个缺陷是，它不会自动管理内存。这意味着，如果字符串的长度超出了数组能够容纳的范围，程序员必须手动申请新的内存空间，并将原来的内容复制过去。这种方式不但产生了大量无谓的工作，而且是无数臭名昭著的溢出漏洞的原因。一个最简单的例子是，当一个程序要求用户输入一个字符串时，如果用户输入的字符串的长度大于程序设定的缓冲区的长度，将会导致溢出，最终程序会崩溃。 
　　 针对C风格字符串的这些缺陷，新的语言进行了相应的改进。作为C的直接继承者，C++语言在标准库中提供了一个基础字符串的实现：std :: basic_string。它封装了大量常见的操作，例如取长度、比较、插入、拼接、查找、替换等等，并且能够自动管理内存。例如，由于C++支持运算符重载，因此C++字符串可以使用运算符直接进行运算，而不需要调用strcpy函数。另外，C++字符串也提供了与C风格字符串进行转换的功能。基于强大的模板机制，C++字符串将字符串的实现和具体的字符类型分离开来了。下面是两种最常见的字符串类型： 
　　 
　　typedef basic_string<char> string; // 定义了ansi类型的字符串 
　　typedef basic_string<wchar_t> wstring; // 定义了宽字符类型的字符串 
　　 
　　 不幸的是，由于复杂的历史原因，许多C++方言（例如Visual C++和Borland C++Builder）都提供了与标准字符串不同的字符串实现。这些字符串实现各有长处，但是将它们和C++标准字符串以及C风格字符串进行转换，又成为了一项令人头疼的工作。 
　　 Delphi对字符串的改进基于另外一种思路。在Delphi中，字符串仍然是一种基本类型，而不是类。它的实现方式也是字符数组，不同于C风格字符串的是，在数组的头部增加了两个32位整数存储空间，分别用于存放字符串的长度和引用计数。通过前者可以方便地获得字符串的长度，而不需要进行无谓的遍历操作。后者实现了COW（Copy on Write）技术，这种技术的效果是：当字符串被复制时，并不会复制其内容，而只是建立一个新的指针，指向原有的字符串，并在引用计数上加一。当字符串被删除时，引用计数减一，当引用计数为0时，字符串的内存将被释放。只有当对字符串进行写入操作时，才会建立一个新的字符串并复制内容。这些工作是由编译器自动完成的，程序员完全可以象使用C风格字符串一样使用Delphi风格的字符串，只是效率大大地提高了。 
　　 Java和C#中的字符串，是一个封装了常见操作的类，这一点和C++类似。一个特殊之处（往往导致经典的性能问题）是，无论是在Java还是在C#中，String类都是不变(immutable)的。也就是说，String的内容不能够被改变，如果代码试图改变一个String对象的内容，实际的结果是建立了一个新的String对象，并抛弃旧的对象。如下例： 
　　 
　　String s = ""; 
　　for (int i = 0;i < 10000;i++) { 
　　 s += i + ", "; 
　　} 
　　 
　　 结果是建立并抛弃了10000个String对象，这在性能上的开销是惊人的。为了避免这种情况，应该使用StringBuilder对象，它可以改变其内容。（C#一直使用StringBuilder。Java从1.5开始引入StringBuilder以部分替代StringBuffer，它们的主要区别在于线程安全性。）如下例： 
　　 
　　StringBuilder sb = new StringBuilder(); 
　　for (int i = 0; i < 10000; i++) { 
　　sb.append(i + ","); 
　　} 
　　 
　　数组 
　　 从抽象数据类型的意义上来说，一维数组(array)的定义是：具有相同数据类型的若干个元素的有限序列。 
　　 在C语言中，数组意味着一块连续的内存空间，按顺序存放着若干个相同数据类型的元素。可以通过下标来访问数组中的元素。如下例： 
　　 
　　int a[10]; // 定义一个int型的数组 
　　for (int i = 0;i < 10;i++) { 
　　 a[i] = i; // 赋值 
　　} 
　　 
　　 在C语言中，数组名事实上是一个指针（指向该数组的第一个元素），因此所有通过数组下标完成的操作，都可以通过指针来完成。通过指针来访问数组，效率上比数组下标要高，而且更加灵活，例如，指针可以进行偏移量的运算，甚至可以进行绝对地址的存取。 
　　 C语言中的数组没有越界检查，这意味着，程序员可以访问数组最后一个元素以后的地址，或者第一个元素之前的地址（例如，a[-1]、a[-2]这种形式是合法的）。在某些情况下，这是一种有用的技巧，但大多数情况下是一场灾难。C语言的数组也不支持自动增长，如果数组的长度发生了变化，程序员必须手动处理所有关于申请和释放内存的工作。 
　　 C++提供了C风格的数组，同样不支持越界检查和自动增长。但是，C++（至少是Stroustrup博士本人）建议，应该尽量使用STL中的容器作为替代品，一般是vector。Vector基于面向对象和模板技术，构建了一个强大而复杂的类，实现了如下特性：高效率的自动内存管理；按任何顺序访问、插入和删除元素；越界检查，但同时也提供了不进行检查的访问方式，以照顾性能上的考虑；基于运算符重载技术的运算符支持；基于迭代器的漫游机制；与数据类型无关的算法支持；等等。相对于C风格的数组，vector是一种更高抽象层次上的序列概念。它对大量常用的功能进行了封装（例如，对内存的直接操作），同时又尽可能地照顾了效率和可移植性（例如，在自动扩充时通过缓存机制来提高效率）。这也正是C++语言对C语言进行改进时的指导思想。 
　　 Delphi也支持C风格的数组，但提供了越界检查。另外，Delphi还提供了一种动态数组（Dynamic Array），可以在运行时通过SetLength函数动态地改变它的大小。事实上，SetLength函数就是对内存管理操作的一种封装。类似于C++中的vector，Delphi也提供了两个可以自动增长的容器：TList和TObjectList，前者用于存放无类型的指针，后者用于存放对象。由于Delphi不支持模板机制，所以TList不会自动释放指针所指向的内存，它只会维护指针自身占用的内存（TObjectList能够在销毁时自动释放元素所占用的空间，如果它的OwnsObjects属性被设置为True的话）。一种常用的解决方法是，编写一个针对具体类型的包裹类，使用一个作为私有数据成员的TList对象来管理指针，并手动编写申请和释放内存的那部分代码。这样总比C语言中的情况要好得多。 
　　 Java也支持加上了越界检查的C风格数组，但它提供的类似容器更为引人注目。Java将序列（List）作为一个单独的接口提取出来，并提供了两个实现：ArrayList和LinkedList。从名字就可以看出来，前者是通过数组来实现的，后者则通过链表。由于都实现了List接口，二者可以支持同样的基本操作方式，不同的是，ArrayList在频繁进行随机访问时有效率上的优势，而LinkedList在频繁进行插入和删除操作时效率较优。实现了List接口的类还有Vector和Stack，但是它们在Java 1.1以后就被废弃了。由于LinkedList可以在序列的头尾插入和删除元素，它可以很好地实现Stack和Queue的功能。 
　　 Java在1.5以前的版本中也不支持模板，因此List（以及其他的容器）接受Object类型作为元素。由于在Java中所有的类都派生自Object，所以这些容器能够支持任何对象。对于不是对象的基本类型，Java提供了一种包裹类(wrapped class)，它能够将基本类型转换成常规的类，从而获得容器的支持。这和Delphi的解决思路异曲同工。