您身边的App定制专业企业--10年开发经验为您护航

18678812288
0531-88887250

2138com太阳集团浅谈算法和数据结构: 符号表及其基本实现

文章编辑:2138com太阳集团 时间:2016年11月08日

  一符号表

  在开始先容查找算法之前,大家需要定义一个名为符号表(Symbol Table)的抽象数据结构,该数据结构类似大家再C#中使用的Dictionary,他是对具有键值对元素的一种抽象,每一个元素都有一个key和value,大家可以往里面添加key,value键值对,也可以根据key来查找value。在现实的生活中,大家经常会遇到各种需要根据key来查找value的情况,比如DNS根据域名查找IP地址,图书馆根据索引号查找图书等等:

  SymbolTableApplication

  为了实现这一功能,大家定义一个抽象数据结构,然后选用合适的数据结构来实现:

  public class ST<Key, Value>

  ST()

  创建一个查找表对象

  void Put(Key key, Value val)

  往集合中插入一条键值对记录,如果value为空,不添加

  Value Get(Key key)

  根据key查找value,如果没找到返回null

  void Delete(Key key)

  删除键为key的记录

  boolean Contains(Key key)

  判断集合中是否存在键为key的记录

  boolean IsEmpty()

  判断查找表是否为空

  int Size()

  返回集合中键值对的个数

  Iterable<Key> Keys()

  返回集合中所有的键

  二实现

  1 使用无序链表实现查找表

  查找表的实现关键在于数据结构的选择,最简单的一种实现是使用无序链表来实现,每一个节点记录key值,value值以及指向下一个记录的对象。

  SymbolTableImplementByUnOrderedLinkList

  如图,当大家往链表中插入元素的时候,从表头开始查找,如果找到,则更新value,否则,在表头插入新的节点元素。

  实现起来也很简单:

  public class SequentSearchSymbolTable<TKey, TValue> : SymbolTables<TKey, TValue> where TKey : IComparable<TKey>, IEquatable<TKey>

  {

  private int length = 0;

  Node first;

  private class Node

  {

  public TKey key { get; set; }

  public TValue value { get; set; }

  public Node next { get; set; }

  public Node(TKey key, TValue value, Node next)

  {

  this.key = key;

  this.value = value;

  this.next = next;

  }

  }

  public override TValue Get(TKey key)

  {

  TValue result = default(TValue);

  Node temp = first;

  while (temp != null)

  {

  if (temp.key.Equals(key))

  {

  result = temp.value;

  break;

  }

  temp = temp.next;

  }

  return result;

  }

  public override void Put(TKey key, TValue value)

  {

  Node temp = first;

  while (temp != null)

  {

  if (temp.key.Equals(key))

  {

  temp.value = value;

  return;

  }

  temp = temp.next;

  }

  first = new Node(key, value, first);

  length++;

  }

  ....

  }

  分析:

  从图或者代码中分析可知,插入的时候先要查找,如果存在则更新value,查找的时候需要从链表头进行查找,所以插入和查找的平均时间复杂度均为O(n)。那么有没有效率更好的方法呢,下面就先容二分查找。

  2 使用二分查找实现查找表

  和采用无序链表实现不同,二分查找的思想是在内部维护一个按照key排好序的二维数组,每一次查找的时候,跟中间元素进行比较,如果该元素小,则继续左半部分递归查找,否则继续右半部分递归查找。整个实现代码如下:

  class BinarySearchSymbolTable<TKey, TValue> : SymbolTables<TKey, TValue> where TKey : IComparable<TKey>, IEquatable<TKey>

  {

  private TKey[] keys;

  private TValue[] values;

  private int length;

  private static readonly int INIT_CAPACITY = 2;

  public BinarySearchSymbolTable(int capacity)

  {

  keys = new TKey[capacity];

  values = new TValue[capacity];

  length = capacity;

  }

  public BinarySearchSymbolTable() : this(INIT_CAPACITY)

  {

  }

  /// <summary>

  /// 根据key查找value。

  /// 首先查找key在keys中所处的位置,如果在length范围内,且存在该位置的值等于key,则返回值

  /// 否则,不存在

  /// </summary>

  /// <param name="key"></param>

  /// <returns></returns>

  public override TValue Get(TKey key)

  {

  int i = Rank(key);

  if (i < length && keys[i].Equals(key))

  return values[i];

  else

  return default(TValue);

  }

  /// <summary>

  /// 向符号表中插入key,value键值对。

  /// 如果存在相等的key,则直接更新value,否则将该key,value插入到合适的位置

  ///  1.首先将该位置往后的元素都往后移以为

  ///  2.然后再讲该元素放到为i的位置上

  /// </summary>

  /// <param name="key"></param>

  /// <param name="value"></param>

  public override void Put(TKey key, TValue value)

  {

  int i = Rank(key);

  if (i < length && keys[i].Equals(key))

  {

  values[i] = value;

  return;

  }

  //如果长度相等,则扩容

  if (length == keys.Length) Resize(2 * keys.Length);

  for (int j = length; j > i; j--)

  {

  keys[j] = keys[j - 1];

  values[j] = values[j - 1];

  }

  keys[i] = key;

  values[i] = value;

  length++;

  }

  /// <summary>

  /// 返回key在数组中的位置

  /// </summary>

  /// <param name="key"></param>

  /// <returns></returns>

  private int Rank(TKey key)

  {

  int lo = 0;

  int hi = length - 1;

  while (lo <= hi)

  {

  int mid = lo + (hi - lo) / 2;

  if (key.CompareTo(keys[mid]) > 0) lo = mid + 1;

  else if (key.CompareTo(keys[mid]) < 0) hi = mid - 1;

  else return mid;

  }

  return lo;

  }

  。。。

  }

  这里面重点是Rank方法,大家可以看到首先获取mid位置,然后将当前元素和mid位置元素比较,然后更新lo或者hi的位置用mid来替换,如果找到相等的,则直接返回mid,否则返回该元素在集合中应该插入的合适位置。上面是使用迭代的方式来实现的,也可以改写为递归:

  private int Rank(TKey key, int lo, int hi)

  {

  if (lo >= hi) return lo;

  int mid = lo + (hi - lo) / 2;

  if (key.CompareTo(keys[mid]) > 0)

  return Rank(key, mid + 1, hi);

  else if (key.CompareTo(keys[mid]) < 0)

  return Rank(key, lo, hi - 1);

  else

  return mid;

  }


想要了解更多详情欢迎来电咨询18678812288
登陆网址:www.jnydkj.cn。
联系人:王经理。

XML 地图 | Sitemap 地图