轉發請聲明轉發:
原文在這裡:http://www.cnblogs.com/yangecnu/p/Introduce-Symbol-Table-and-Elementary-Implementations.html
前面幾篇文章介紹了基本的排序算法,排序通常是查找的前奏操作。從本文開始介紹基本的查找算法。
在介紹查找算法,首先需要了解符号表這一抽象資料結構,本文首先介紹了什麼是符号表,以及這一抽象資料結構的的API,然後介紹了兩種簡單的符号表的實作方式。
一符号表
在開始介紹查找算法之前,我們需要定義一個名為符号表(Symbol Table)的抽象資料結構,該資料結構類似我們再C#中使用的Dictionary,他是對具有鍵值對元素的一種抽象,每一個元素都有一個key和value,我們可以往裡面添加key,value鍵值對,也可以根據key來查找value。在現實的生活中,我們經常會遇到各種需要根據key來查找value的情況,比如DNS根據域名查找IP位址,圖書館根據索引号查找圖書等等:
![](https://img.laitimes.com/img/9ZDMuAjOiMmIsIjOiQnIsIyZuBnL3QzMzYzMzETN5MzNxITMvw1MwQTMwIzLcFzMwQTOvw1ZvxmYvwVbvNmLn9GbiRXauNmLzV2Zh1Wavw1LcpDc0RHaiojIsJye.png)
為了實作這一功能,我們定義一個抽象資料結構,然後選用合适的資料結構來實作:
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值以及指向下一個記錄的對象。
如圖,當我們往連結清單中插入元素的時候,從表頭開始查找,如果找到,則更新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;
}
二分查找的示意圖如下:
分析:
使用有序的二維數組來實作查找表可以看出,采用二分查找隻需要最多lgN+1次的比較即可找到對應元素,是以查找效率比較高。
但是對于插入元素來說,每一次插入不存在的元素,需要将該元素放到指定的位置,然後,将他後面的元素依次後移,是以平均時間複雜度O(n),對于插入來說效率仍然比較低。
三 總結
本文介紹了符号表這一抽象資料結構,然後介紹了兩種基本實作:基于無序連結清單的實作和基于有序數組的實作,兩種實作的時間複雜度如下:
可以看到,使用有序數組的二分查找法提高了符号表的查找速度,但是插入效率仍舊沒有得到提高,而且在要維護數組有序,還需要進行排序操作。這兩種實作方式簡單直覺,但是無法同時達到較高查找和插入效率。那麼有沒有一種資料結構既能夠在查找的時候有較高的效率,在插入的時候也有較好的效率呢,本文隻是一個引子,後面的系列文章将會介紹二叉查找樹,平衡查找樹以及哈希表。
希望本文對您了解查找表的基本概念以及兩種基本實作有所幫助。