C#使用符號表實現(xiàn)查找算法
高效檢索海量信息（經(jīng)典查找算法）是現(xiàn)代信息世界的基礎設施。我們使用符號表描述一張抽象的表格，將信息（值）存儲在其中，然后按照指定的鍵來搜索并獲取這些信息。鍵和值的具體意義取決于不同的應用。符號表中可能會保存很多鍵和很多信息，因此實現(xiàn)一張高效的符號表是很重要的任務。
符號表有時被稱為字典，有時被稱為索引。
1.符號表
符號表是一種存儲鍵值對的數(shù)據(jù)結(jié)構(gòu)，支持兩種操作：插入（put），即將一組新的鍵值對存入表中；查找（get），即根據(jù)給定的鍵得到相應的值。符號表最主要的目的就是將一個健和一個值聯(lián)系起來。
構(gòu)造符號表的方法有很多，它們不光能夠高效地插入和查找，還可以進行其他幾種方便的操作。要實現(xiàn)符號表，首先要定義其背后的數(shù)據(jù)結(jié)構(gòu)，并指明創(chuàng)建并操作這種數(shù)據(jù)結(jié)構(gòu)以實現(xiàn)插入，查找等操作所需的算法。
API
public interface ISymbolTables<Key,Value> where Key : IComparable
{
int CompareCount { get; set; }
/// <summary>
/// 將鍵值對存入表中（若值未空則將鍵key從表中刪除）
/// </summary>
/// <param name="key"></param>
/// <param name="value"></param>
void Put(Key key, Value value);
/// <summary>
/// 獲取鍵 key 對應的值（若鍵不存在則返回 null）
/// </summary>
/// <param name="key"></param>
/// <returns></returns>
Value Get(Key key);
/// <summary>
/// 從表中刪去鍵 key
/// </summary>
/// <param name="key"></param>
void Delete(Key key);
/// <summary>
/// 鍵 key 是否在表中存在
/// </summary>
/// <param name="key"></param>
/// <returns></returns>
bool Contains(Key key);
/// <summary>
/// 表是否未空
/// </summary>
/// <returns></returns>
bool IsEmpty();
/// <summary>
/// 表中的鍵值對數(shù)量
/// </summary>
/// <returns></returns>
int Size();
/// <summary>
/// 表中所有鍵的集合
/// </summary>
/// <returns></returns>
IEnumerable<Key> Keys();
/// <summary>
/// 最小的鍵
/// </summary>
/// <returns></returns>
Key Min();
/// <summary>
/// 最大的鍵
/// </summary>
/// <returns></returns>
Key Max();
/// <summary>
/// 小于等于 key 的鍵
/// </summary>
/// <param name="key"></param>
/// <returns></returns>
Key Floor(Key key);
/// <summary>
/// 大于等于 key 的鍵
/// </summary>
/// <param name="key"></param>
/// <returns></returns>
Key Ceilling(Key key);
/// <summary>
///小于 key 的鍵的數(shù)量（key 的排名）
/// </summary>
/// <param name="key"></param>
/// <returns></returns>
int Rank(Key key);
/// <summary>
/// 排名為 k 的鍵
/// </summary>
/// <param name="k"></param>
/// <returns></returns>
Key Select(int k);
/// <summary>
/// 刪除最小的鍵
/// </summary>
void DeleteMin();
/// <summary>
/// 刪除最大的鍵
/// </summary>
void DeleteMax();
/// <summary>
/// [lo ... hi]之間的鍵的數(shù)量
/// </summary>
/// <param name="lo"></param>
/// <param name="hi"></param>
/// <returns></returns>
int Size(Key lo,Key hi);
/// <summary>
/// [lo ... hi]之間的鍵
/// </summary>
/// <param name="lo"></param>
/// <param name="hi"></param>
/// <returns></returns>
IEnumerable<Key> Keys(Key lo, Key hi);
}基本實現(xiàn)：
/// <summary>
/// 符號表基類
/// </summary>
/// <typeparam name="Key"></typeparam>
/// <typeparam name="Value"></typeparam>
public class BaseSymbolTables<Key, Value>: ISymbolTables<Key, Value>
where Key : IComparable
{
public int CompareCount { get; set; }
/// <summary>
/// 將鍵值對存入表中（若值未空則將鍵key從表中刪除）
/// </summary>
/// <param name="key"></param>
/// <param name="value"></param>
public virtual void Put(Key key, Value value)
{
}
/// <summary>
/// 獲取鍵 key 對應的值（若鍵不存在則返回 null）
/// </summary>
/// <param name="key"></param>
/// <returns></returns>
public virtual Value Get(Key key)
{
return default(Value);
}
/// <summary>
/// 從表中刪去鍵 key
/// </summary>
/// <param name="key"></param>
public void Delete(Key key)
{
}
/// <summary>
/// 鍵 key 是否在表中存在
/// </summary>
/// <param name="key"></param>
/// <returns></returns>
public bool Contains(Key key)
{
return false;
}
/// <summary>
/// 表是否未空
/// </summary>
/// <returns></returns>
public bool IsEmpty()
{
return Size()==0;
}
/// <summary>
/// 表中的鍵值對數(shù)量
/// </summary>
/// <returns></returns>
public virtual int Size()
{
return 0;
}
/// <summary>
/// 表中所有鍵的集合
/// </summary>
/// <returns></returns>
public virtual IEnumerable<Key> Keys()
{
return new List<Key>();
}
/// <summary>
/// 最小的鍵
/// </summary>
/// <returns></returns>
public virtual Key Min()
{
return default(Key);
}
/// <summary>
/// 最大的鍵
/// </summary>
/// <returns></returns>
public virtual Key Max()
{
return default(Key);
}
/// <summary>
/// 小于等于 key 的鍵
/// </summary>
/// <param name="key"></param>
/// <returns></returns>
public virtual Key Floor(Key key)
{
return default(Key);
}
/// <summary>
/// 大于等于 key 的鍵
/// </summary>
/// <param name="key"></param>
/// <returns></returns>
public virtual Key Ceilling(Key key)
{
return default(Key);
}
/// <summary>
///小于 key 的鍵的數(shù)量（key 的排名）
/// </summary>
/// <param name="key"></param>
/// <returns></returns>
public virtual int Rank(Key key)
{
return 0;
}
/// <summary>
/// 排名為 k 的鍵
/// </summary>
/// <param name="k"></param>
/// <returns></returns>
public virtual Key Select(int k)
{
return default(Key);
}
/// <summary>
/// 刪除最小的鍵
/// </summary>
public virtual void DeleteMin()
{
}
/// <summary>
/// 刪除最大的鍵
/// </summary>
public virtual void DeleteMax()
{
}
/// <summary>
/// [lo ... hi]之間的鍵的數(shù)量
/// </summary>
/// <param name="lo"></param>
/// <param name="hi"></param>
/// <returns></returns>
public virtual int Size(Key lo, Key hi)
{
return 0;
}
/// <summary>
/// [lo ... hi]之間的鍵
/// </summary>
/// <param name="lo"></param>
/// <param name="hi"></param>
/// <returns></returns>
public virtual IEnumerable<Key> Keys(Key lo, Key hi)
{
return new List<Key>();
}
}2.有序符號表
典型的應用程序中，鍵都是IComparable 對象，因此可以使用 a.CompareTo( b ) 來比較 a 和 b 兩個鍵。符號表保持鍵的有序性，可以擴展它的API，根據(jù)鍵的相對位置定義更多實用操作。例如，最大和最小的鍵。
排名（Rank 方法）和選擇 （Select 方法）
檢查一個新的鍵是否插入合適位置的基本操作是排名（Rank，找出小于指定鍵的鍵的數(shù)量）和選擇（Select，找出排名為 k 的鍵）。對于 0 到 Size（）-1 的所有 i 都有 i == Rank( Select(i) )，且所有的鍵都滿足 key == Select( Rank( key ) ) 。
鍵的等價性
IComparable 類型中 CompareTo 和 Equals 方法是一致的，但為了避免任何潛在的二義性，這里只是用a.CompareTo( b ) == 0 來判斷 a 和 b 是否相等。
成本模型
查找的成本模型：在符號表的實現(xiàn)中，將比較的次數(shù)作為成本模型。在內(nèi)循環(huán)不進行比較的情況下，使用數(shù)組的訪問次數(shù)。
符號表實現(xiàn)的重點在于其中使用的數(shù)據(jù)結(jié)構(gòu)和 Get() , Put() 方法。
3.無序鏈表中的順序查找
符號表中使用的數(shù)據(jù)結(jié)構(gòu)的一個簡單選擇是鏈表，每個結(jié)點存儲一個鍵值對。
Get 方法的實現(xiàn)即為遍歷鏈表，用Equals 方法比較需要查找的鍵和每個結(jié)點中鍵。如果匹配就返回相應的值，否則返回 null。Put 方法的實現(xiàn)也是遍歷，如果匹配就更新相應的值，否則就用給定的鍵值對創(chuàng)建一個新的結(jié)點并將其插入鏈表的開頭。這種方法稱為順序查找。
/// <summary>
/// 順序查找
/// </summary>
/// <typeparam name="Key"></typeparam>
/// <typeparam name="Value"></typeparam>
public class SequentialSearchST<Key,Value>:BaseSymbolTables<Key, Value>
where Key : IComparable
{
private Node First;
private class Node
{
public Key key;
public Value value;
public Node next;
public Node(Key _key,Value _value,Node _next)
{
key = _key;
value = _value;
next = _next;
}
}
public override Value Get(Key key)
{
for (Node x = First; x != null; x = x.next)
{
if (key.Equals(x.key))
return x.value;
}
return default(Value);
}
public override void Put(Key key, Value value)
{
for (Node x = First; x != null; x = x.next)
{
CompareCount++;
if (key.Equals(x.key))
{
x.value = value;
return;
}
}
First = new Node(key,value,First);
}
}這里我們使用一個字符串數(shù)組來測試上面的算法，鍵是數(shù)組中的值，值是插入的索引：
string[] strs = new string[] { "S", "E", "A", "R", "C", "H", "E", "X", "A", "M", "P", "L", "E" };下面是順序查找的索引用例的軌跡：
分析符號表算法比排序算法更困難，因為不同的用例所進行的操作序列各不相同。常見的情形是雖然查找和插入的使用模式是不可預測的，但它們的使用肯定不是隨機的。因此我們主要研究最壞情況下的性能。我們使用命中表示一次成功的查找，未命中表示一次失敗的查找。
在含有 N 對鍵值的基于鏈表的符號表中，未命中的查找和插入操作都需要 N 次比較。命中的查找在最壞情況下需要 N 次比較。特別地，向一個空表中插入 N 個不同的鍵需要 ~ N^2 /2 次比較。
查找一個已經(jīng)存在的鍵并不需要線性級別的時間。一種度量方法是查找表中的每個鍵，并將總時間除以 N 。在查找表中每個鍵的可能性都相同的情況下，這個結(jié)果就是一次查找平均所需的比較次數(shù)。稱它為隨機命中。由上面的算法可以得到平均比較次數(shù)為 ~N/2: 查找第一個鍵需要比較一次，查找第二個鍵需要比較兩次 ...... 平均比較次數(shù)為（1+2+3.....+N）/ N = (N+1)/2。
這證明基于鏈表的實現(xiàn)以及順序查找是低效的。
4.有序數(shù)組中的二分查找
有序符號表API的實現(xiàn)使用的數(shù)據(jù)結(jié)構(gòu)是一對平行的數(shù)組，一個存儲鍵一個存儲值。下面的代碼保證數(shù)組中IComparable 類型的鍵有序，然后使用數(shù)組的索引來高效地實現(xiàn) Get 和其他操作。
下面算法的核心是 Rank 方法(它使用二分查找的算法)，它返回表中小于給定鍵的鍵的數(shù)量。對于 Get 方法，只要給定的鍵存在于表中就返回，否則返回空。
Put 方法，只要給定的鍵存在于表中，Rank 方法就能夠精確告訴我們它的為并去更新，以及當鍵不存在時我們也能直到將鍵存儲到什么位置。插入鍵值對時，將更大的鍵和值向后移一格，并將給定的鍵值對分別插入到數(shù)組。
public class BinarySearchST<Key,Value> : BaseSymbolTables<Key, Value>
where Key : IComparable
{
private Key[] keys;
private Value[] vals;
private int N;
public BinarySearchST(int capacity)
{
keys = new Key[capacity];
vals = new Value[capacity];
}
public override int Size()
{
return N;
}
public override Value Get(Key key)
{
if (IsEmpty())
return default(Value);
int i = Rank(key);
if (i < N && keys[i].CompareTo(key) == 0)
return vals[i];
else
return default(Value);
}
public override int Rank(Key key)
{
int lo = 0, hi = N - 1;
while (lo <= hi)
{
int mid = lo + (hi-lo) / 2;
CompareCount++;
int cmp = key.CompareTo(keys[mid]);
if (cmp < 0)
hi = mid - 1;
else if (cmp > 0)
lo = mid + 1;
else
return mid;
}
return lo;
}
public override void Put(Key key, Value value)
{
int i = Rank(key);
if (i < N && keys[i].CompareTo(key) == 0)
{
vals[i] = value;
return;
}
for (int j = N; j > i; j--)
{
keys[j] = keys[j-1];
vals[j] = vals[j-1];
}
keys[i] = key;
vals[i] = value;
N++;
}
public override Key Min()
{
return keys[0];
}
public override Key Max()
{
return keys[N-1];
}
public override Key Select(int k)
{
return keys[k];
}
public override Key Ceilling(Key key)
{
int i = Rank(key);
return keys[i];
}
public override IEnumerable<Key> Keys()
{
return keys;
}
}下面是該算法的用例移動軌跡：
對二分查找的分析
Rank 方法的遞歸實現(xiàn)使用了二分查找，二分查找比順序查找快很多。在 N 個鍵的有序數(shù)組中進行二分查找最多需要 （lgN + 1）次比較。
盡管該算法能夠保證查找所需的時間是對數(shù)級別的，但 Put 方法還是太慢，需要移動數(shù)組。對于隨機數(shù)組，構(gòu)造一個基于有序數(shù)組的符號表所需訪問數(shù)組的次數(shù)是數(shù)組長度的平方級別。
向大小為 N 的有序數(shù)組中插入一個新的鍵值對在最壞情況下需要訪問 ~2N 次數(shù)組，因此向一個空符號表中插入 N 個元素在最壞情況下需要訪問 ~N^2 次數(shù)組。
對于一個靜態(tài)表（不允許插入）來說，將其在初始化時就排序是值得的。下面是符號表簡單實現(xiàn)的總結(jié)：
| 算法 | 最壞情況下的成本 （N 次插入后） | 平均情況下的成本 （N 次隨機插入后） | 是否支持有序性相關(guān)的操作 | ||
| 查找 | 插入 | 查找 | 插入 | ||
| 順序查找（無序鏈表） | N | N | N/2 | N | 否 |
| 二分查找（有序數(shù)組） | lgN | 2N | lgN | N | 是 |
到此這篇關(guān)于C#使用符號表實現(xiàn)查找算法的文章就介紹到這了。希望對大家的學習有所幫助，也希望大家多多支持腳本之家。
相關(guān)文章
這篇文章主要給大家介紹了關(guān)于如何創(chuàng)建第一個C#項目的相關(guān)資料,文中通過圖文介紹的非常詳細,對大家的學習或者工作具有一定的參考學習價值,需要的朋友可以參考下2022-12-12
這篇文章主要介紹了C#實現(xiàn)Array添加擴展,對C#初學者有不錯的參考價值,需要的朋友可以參考下2014-08-08
這篇文章主要介紹了C#網(wǎng)頁跳轉(zhuǎn)方法總結(jié)的相關(guān)資料,需要的朋友可以參考下2015-12-12
這篇文章主要介紹了C#中Invoke的用法講解,本篇文章通過簡要的案例,講解了該項技術(shù)的了解與使用,以下就是詳細內(nèi)容,需要的朋友可以參考下2021-07-07
這篇文章主要介紹了C# 添加PDF頁眉/頁腳的示例代碼，小編覺得挺不錯的，現(xiàn)在分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2018-08-08
本文詳細講解了C#中的LINQ?to?Objects，文中通過示例代碼介紹的非常詳細。對大家的學習或工作具有一定的參考借鑒價值，需要的朋友可以參考下2022-06-06
這篇文章主要介紹了c#實現(xiàn)選擇排序的示例，幫助大家更好的理解和使用排序算法，感興趣的朋友可以了解下2020-10-10
這篇文章主要介紹了c# 托管和非托管資源的相關(guān)資料，文中講解非常細致，幫助大家更好的理解和學習，感興趣的朋友可以了解下2020-07-07
這篇文章主要為大家詳細介紹了C#如何利用遞歸實現(xiàn)JS文件的自動引用的功能，文中的示例代碼講解詳細，具有一定的參考價值，需要的可以參考一下2023-03-03
這篇文章主要介紹了基于C#實現(xiàn)一個最簡單的HTTP服務器的方法,詳細分析了http服務器的實現(xiàn)原理與相關(guān)技巧,以及對應的注意事項,需要的朋友可以參考下2014-12-12