C#怎么使用符号表实现查找算法

这里我们使用一个字符串数组来测试上面的算法，键是数组中的值，值是插入的索引：

string[]strs=newstring[]{"S","E","A","R","C","H","E","X","A","M","P","L","E"};

下面是顺序查找的索引用例的轨迹：

分析符号表算法比排序算法更困难，因为不同的用例所进行的操作序列各不相同。常见的情形是虽然查找和插入的使用模式是不可预测的，但它们的使用肯定不是随机的。因此我们主要研究最坏情况下的性能。我们使用命中表示一次成功的查找，未命中表示一次失败的查找。

在含有 N 对键值的基于链表的符号表中，未命中的查找和插入操作都需要 N 次比较。命中的查找在最坏情况下需要 N 次比较。特别地，向一个空表中插入 N 个不同的键需要 ~ N^2 /2 次比较。

查找一个已经存在的键并不需要线性级别的时间。一种度量方法是查找表中的每个键，并将总时间除以 N 。在查找表中每个键的可能性都相同的情况下，这个结果就是一次查找平均所需的比较次数。称它为随机命中。由上面的算法可以得到平均比较次数为 ~N/2: 查找第一个键需要比较一次，查找第二个键需要比较两次 ...... 平均比较次数为（1+2+3.....+N）/ N = (N+1)/2。

这证明基于链表的实现以及顺序查找是低效的。

4.有序数组中的二分查找

有序符号表API的实现使用的数据结构是一对平行的数组，一个存储键一个存储值。下面的代码保证数组中IComparable 类型的键有序，然后使用数组的索引来高效地实现 Get 和其他操作。

下面算法的核心是 Rank 方法(它使用二分查找的算法)，它返回表中小于给定键的键的数量。对于 Get 方法，只要给定的键存在于表中就返回，否则返回空。

Put 方法，只要给定的键存在于表中，Rank 方法就能够精确告诉我们它的为并去更新，以及当键不存在时我们也能直到将键存储到什么位置。插入键值对时，将更大的键和值向后移一格，并将给定的键值对分别插入到数组。

publicclassBinarySearchST:BaseSymbolTableswhereKey:IComparable{privateKey[]keys;privateValue[]vals;privateintN;publicBinarySearchST(intcapacity){keys=newKey[capacity];vals=newValue[capacity];}publicoverrideintSize(){returnN;}publicoverrideValueGet(Keykey){if(IsEmpty())returndefault(Value);inti=Rank(key);if(i0)lo=mid+1;elsereturnmid;}returnlo;}publicoverridevoidPut(Keykey,Valuevalue){inti=Rank(key);if(ii;j--){keys[j]=keys[j-1];vals[j]=vals[j-1];}keys[i]=key;vals[i]=value;N++;}publicoverrideKeyMin(){returnkeys[0];}publicoverrideKeyMax(){returnkeys[N-1];}publicoverrideKeySelect(intk){returnkeys[k];}publicoverrideKeyCeilling(Keykey){inti=Rank(key);returnkeys[i];}publicoverrideIEnumerableKeys(){returnkeys;}}

下面是该算法的用例移动轨迹：

对二分查找的分析

Rank 方法的递归实现使用了二分查找，二分查找比顺序查找快很多。在 N 个键的有序数组中进行二分查找最多需要 （lgN + 1）次比较。

尽管该算法能够保证查找所需的时间是对数级别的，但 Put 方法还是太慢，需要移动数组。对于随机数组，构造一个基于有序数组的符号表所需访问数组的次数是数组长度的平方级别。

向大小为 N 的有序数组中插入一个新的键值对在最坏情况下需要访问 ~2N 次数组，因此向一个空符号表中插入 N 个元素在最坏情况下需要访问 ~N^2 次数组。

对于一个静态表（不允许插入）来说，将其在初始化时就排序是值得的。下面是符号表简单实现的总结：

以上就是“C#怎么使用符号表实现查找算法”这篇文章的所有内容，感谢各位的阅读！相信大家阅读完这篇文章都有很大的收获，小编每天都会为大家更新不同的知识，如果还想学习更多的知识，请关注恰卡编程网行业资讯频道。