九九热这里直有精品,1区二区三区在线播放,玖玖爱在线观看资源,国产aⅴ综合网,午夜福利男女,日本亚洲欧美三级,日韩无码黄色导航,内射少妇13区,中文字幕高清网

　　一符號(hào)表

　　在開始介紹查找算法之前，我們需要定義一個(gè)名為符號(hào)表（Symbol Table）的抽象數(shù)據(jù)結(jié)構(gòu)，該數(shù)據(jù)結(jié)構(gòu)類似我們再C#中使用的Dictionary，他是對具有鍵值對元素的一種抽象，每一個(gè)元素都有一個(gè)key和value，我們可以往里面添加key，value鍵值對，也可以根據(jù)key來查找value。在現(xiàn)實(shí)的生活中，我們經(jīng)常會(huì)遇到各種需要根據(jù)key來查找value的情況，比如DNS根據(jù)域名查找IP地址，圖書館根據(jù)索引號(hào)查找圖書等等：

　　SymbolTableApplication

　　為了實(shí)現(xiàn)這一功能，我們定義一個(gè)抽象數(shù)據(jù)結(jié)構(gòu)，然后選用合適的數(shù)據(jù)結(jié)構(gòu)來實(shí)現(xiàn)：

　　public class ST<Key, Value>

　　ST()

　　創(chuàng)建一個(gè)查找表對象

　　void Put(Key key, Value val)

　　往集合中插入一條鍵值對記錄，如果value為空，不添加

　　Value Get(Key key)

　　根據(jù)key查找value，如果沒找到返回null

　　void Delete(Key key)

　　刪除鍵為key的記錄

　　boolean Contains(Key key)

　　判斷集合中是否存在鍵為key的記錄

　　boolean IsEmpty()

　　判斷查找表是否為空

　　int Size()

　　返回集合中鍵值對的個(gè)數(shù)

　　Iterable<Key> Keys()

　　返回集合中所有的鍵

　　二實(shí)現(xiàn)

　　1 使用無序鏈表實(shí)現(xiàn)查找表

　　查找表的實(shí)現(xiàn)關(guān)鍵在于數(shù)據(jù)結(jié)構(gòu)的選擇，最簡單的一種實(shí)現(xiàn)是使用無序鏈表來實(shí)現(xiàn)，每一個(gè)節(jié)點(diǎn)記錄key值，value值以及指向下一個(gè)記錄的對象。

　　SymbolTableImplementByUnOrderedLinkList

　　如圖，當(dāng)我們往鏈表中插入元素的時(shí)候，從表頭開始查找，如果找到，則更新value，否則，在表頭插入新的節(jié)點(diǎn)元素。

　　實(shí)現(xiàn)起來也很簡單：

　　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++;

　　}

　　....

　　}

　　分析：

　　從圖或者代碼中分析可知，插入的時(shí)候先要查找，如果存在則更新value，查找的時(shí)候需要從鏈表頭進(jìn)行查找，所以插入和查找的平均時(shí)間復(fù)雜度均為O(n)。那么有沒有效率更好的方法呢，下面就介紹二分查找。

　　2 使用二分查找實(shí)現(xiàn)查找表

　　和采用無序鏈表實(shí)現(xiàn)不同，二分查找的思想是在內(nèi)部維護(hù)一個(gè)按照key排好序的二維數(shù)組，每一次查找的時(shí)候，跟中間元素進(jìn)行比較，如果該元素小，則繼續(xù)左半部分遞歸查找，否則繼續(xù)右半部分遞歸查找。整個(gè)實(shí)現(xiàn)代碼如下：

　　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>

　　/// 根據(jù)key查找value。

　　/// 首先查找key在keys中所處的位置，如果在length范圍內(nèi)，且存在該位置的值等于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>

　　/// 向符號(hào)表中插入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;

　　}

　　//如果長度相等，則擴(kuò)容

　　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在數(shù)組中的位置

　　/// </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;

　　}

　　。。。

　　}

　　這里面重點(diǎn)是Rank方法，我們可以看到首先獲取mid位置，然后將當(dāng)前元素和mid位置元素比較，然后更新lo或者h(yuǎn)i的位置用mid來替換，如果找到相等的，則直接返回mid，否則返回該元素在集合中應(yīng)該插入的合適位置。上面是使用迭代的方式來實(shí)現(xiàn)的，也可以改寫為遞歸：

　　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;

　　}