最基础的数据结构

引言
　　
　　 任何一个受过专业训练的程序员，对“数据结构”这门课程中涉及到的各种数据结构都不会感到陌生。但是，在实际的编程工作中，大部分的数据结构都不会用到，而且也许永远都不会用到。造成这种现象的原因有二：一是根据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; // 定义了宽字符类型的字符串