C#数据结构和算法学习系列十一----构建字典DictionaryBase 类和SortedList 类

字典是一种把数据作为键值对来存储的数据结构。作为一种抽象的类，DictionaryBase 类可以用来实现不同的数据结构，其中这些数据结构全部把数据存储成键值对。这些数据结构可能是散列表、链表或者其他一些数据结构类型。SortedList类是按照分类顺序基于键值来存储键值对的。这是一种有趣的数据结构，因为通过引用数据结构中值的索引位置也可以访问到存储在结构中的数据，这也使得结构的行为在某些方面和数组很相像。

A.Dictionary类。DictionaryBase 类是一种用作专有字典实现基础的抽象（MusInherit）类。存储在字典中的键值对实际上是作为DictionaryEntry 对象来存储的。DictionaryEntry 结构提供了两个域，一个用于关键字而另一个用于值。在这个结构中所要关注的只是Key 属性和Value 属性这两个属性（或方法）。当把键值对录入到字典内的时候，这些方法会返回存储的值。DictionaryBase 类实际上实现了来自System.Collections 名字空间的界面，即IDictionary。

1.DictionaryBase 类的基础方法和属性。在用字典对象进行操作的时候需要执行几种操作。就最少操作数量而言，需要Add 方法来添加新数据，需要Item 方法来取回数值，需要Remove 方法来移除掉键值对，还需要Clear方法来清除所有数据的数据结构。实例如下：

public class IPAddresses : DictionaryBase
{
     public IPAddresses()
     {
     }
     public void Add(string name, string ip)
     {
          base.InnerHashtable.Add(name, ip);
     }
     public string Item(string name)
     {
          return base.InnerHashtable[name].ToString();
     }
     public void Remove(string name)
     {
          base.InnerHashtable.Remove(name);
     }
}

相应调用如下：

class chapter11
{
     static void Main()
     {
          IPAddresses myIPs = new IPAddresses();
          myIPs.Add(" Mike", "192.155.12.1");
          myIPs.Add(" David", "192.155.12.2");
          myIPs.Add(" Bernica", "192.155.12.3");
          Console.WriteLine("There are " + myIPs.Count + " IP addresses");
          Console.WriteLine("David's ip address: " + myIPs.Item("David"));
          myIPs.Clear();
          Console.WriteLine("There are " + myIPs.Count + " IP addresses");
     }
}

这里还有其他两种方法， 它们都是DictionaryBase 类的成员： CopyTo 方法和GetEnumerator 方法。CopyTo 方法把字典的内容复制给一维的数组。尽管可以把数组声明成Object，然后用CType 函数把对象转换成为DictionaryEntry，但是这里应该把数组声明成DictionaryEntry数组。

IPAddresses myIPs = new IPAddresses(@"c:\ips.txt ");
DictionaryEntry[] ips = new DictionaryEntry[myIPs.Count-1];
myIPs.CopyTo(ips, 0);

B.KeyValuePair类
C#语言提供了一种小类用来允许创建象字典式的对象，此对象是基于关键字来存储数据的。这种类被称为是KeyValuePair 类。由于每个对象只能持有一个关键字和一个值，所以它的使用是受到限制的。实例化:

KeyValuePair<string, int> mcmillan = new KeyValuePair<string, int>("McMillan", 99);

如果把对象放置在数组内，那么KeyValuePair 类是比较好用的。下列程序举例说明如何实现简单等级书:

using System;
using System.Collections.Generic;
using System.Text;
namespace Generics
{
     class Program
     {
          static void Main(string[] args)
          {
               KeyValuePair<string, int>[] gradeBook = new KeyValuePair<string,
int>[10];
               gradeBook[0] = new KeyValuePair<string,int>("McMillan", 99);
               gradeBook[1] = new KeyValuePair<string,int>("Ruff", 64);
               for (int i = 0; i <= gradeBook.GetUpperBound(0); i++)
                    if (gradeBook[i].Value != 0)
                         Console.WriteLine(gradeBook[i].Key + ": " +
gradeBook[i].Value);
               Console.Read();
          }
     }
}

C.SortedList 是按照分类顺序基于键值来存储键值对。当存储的关键字很重要时可以使用这种数据结构。比如，在标准词典中希望所存储的词是按照字母的顺序存储的情况。
1.SortedList 类的使用。实例化如下：

SortedList myips = new SortedList();
myips.Add("Mike", "192.155.12.1");
myips.Add("David", "192.155.12.2");
myips.Add("Bernica", "192.155.12.3");

SortedList 类的通用版本允许确定关键字和值两者的数据类型：SortedList<Tkey, TValue>。类似用法同Dictionay类

总结：DictionaryBase 类是用来创建用户字典的抽象类。而字典则是利用散列表（或者有时为单独的链表）作为潜在的数据结构来把数据存储到键值对内的一种数据结构。键值对作为DictionaryEntry 对象来进行存储， 而且必须使用Key 方法和Value 方法来取回DictionaryEntry 对象中的实际值。当程序员需要创建强类型的数据结构的时候，经常会用到DictionaryBase 类。通常情况下会把添加给字典的数据作为Object 来存储，但是对于自定义字典而言，程序员可能会削减需要执行的类型转换的数量，从而使得程序变得更加有效且更易于阅读。SortedList 类是Dictionary 类的一种特殊类型。它会按照分类的顺序通过关键字来存储键值对。此外，也可以通过引用索引数的方式来取回存储在SortedList 中的值，其中索引数是存储数值的位置，这和使用数组非常相似。在System.Collections.Generic 名字域中还有SortedDictionary 可以像通用SortedList 类一样操作。