频道栏目
首页 > 程序开发 > 软件开发 > Java > 正文
浅谈算法和数据结构: 六 符号表及其基本实现
2014-03-13 08:42:59      个评论      
收藏   我要投稿
前面几篇文章介绍了基本的排序算法,排序通常是查找的前奏操作。从本文开始介绍基本的查找算法。

 

在介绍查找算法,首先需要了解符号表这一抽象数据结构,本文首先介绍了什么是符号表,以及这一抽象数据结构的的API,然后介绍了两种简单的符号表的实现方式。

 

一符号表

在开始介绍查找算法之前,我们需要定义一个名为符号表(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;

}

点击复制链接 与好友分享!回本站首页
上一篇:Logging的这点小事
下一篇:Spring-Context之三:使用XML和Groovy DSL配置Bean
相关文章
图文推荐
点击排行

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站