扫码关注官方微信

扫码下载APP
返回顶部
首页 > 资讯 > 后端开发 > 其他教程 >C#使用符号表实现查找算法
  • 770

0
分享到

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

2024-04-02 19:04:59 770人浏览 薄情痞子
摘要

高效检索海量信息（经典查找算法）是现代信息世界的基础设施。我们使用符号表描述一张抽象的表格，将信息（值）存储在其中，然后按照指定的键来搜索并获取这些信息。键和值的具体意义取决于不同的

高效检索海量信息（经典查找算法）是现代信息世界的基础设施。我们使用符号表描述一张抽象的表格，将信息（值）存储在其中，然后按照指定的键来搜索并获取这些信息。键和值的具体意义取决于不同的应用。符号表中可能会保存很多键和很多信息，因此实现一张高效的符号表是很重要的任务。

符号表有时被称为字典，有时被称为索引。

1.符号表

符号表是一种存储键值对的数据结构，支持两种操作：插入（put），即将一组新的键值对存入表中；查找（get），即根据给定的键得到相应的值。符号表最主要的目的就是将一个健和一个值联系起来。

构造符号表的方法有很多，它们不光能够高效地插入和查找，还可以进行其他几种方便的操作。要实现符号表，首先要定义其背后的数据结构，并指明创建并操作这种数据结构以实现插入，查找等操作所需的算法。

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>
        /// 表中的键值对数量
        /// </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 的键的数量（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]之间的键的数量
        /// </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);
    }

基本实现：

    /// <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>
        /// 表中的键值对数量
        /// </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 的键的数量（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]之间的键的数量
        /// </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，根据键的相对位置定义更多实用操作。例如，最大和最小的键。

排名（Rank 方法）和选择 （Select 方法）

检查一个新的键是否插入合适位置的基本操作是排名（Rank，找出小于指定键的键的数量）和选择（Select，找出排名为 k 的键）。对于 0 到 Size（）-1 的所有 i 都有 i == Rank( Select(i) )，且所有的键都满足 key == Select( Rank( key ) ) 。

键的等价性

IComparable 类型中 CompareTo 和 Equals 方法是一致的，但为了避免任何潜在的二义性，这里只是用a.CompareTo( b ) == 0 来判断 a 和 b 是否相等。

成本模型

查找的成本模型：在符号表的实现中，将比较的次数作为成本模型。在内循环不进行比较的情况下，使用数组的访问次数。

符号表实现的重点在于其中使用的数据结构和 Get() , Put() 方法。

3.无序链表中的顺序查找

符号表中使用的数据结构的一个简单选择是链表，每个结点存储一个键值对。

Get 方法的实现即为遍历链表，用Equals 方法比较需要查找的键和每个结点中键。如果匹配就返回相应的值，否则返回 null。Put 方法的实现也是遍历，如果匹配就更新相应的值，否则就用给定的键值对创建一个新的结点并将其插入链表的开头。这种方法称为顺序查找。

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

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

string[] strs = new string[] { "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 方法就能够精确告诉我们它的为并去更新，以及当键不存在时我们也能直到将键存储到什么位置。插入键值对时，将更大的键和值向后移一格，并将给定的键值对分别插入到数组。

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

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

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

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

算法

最坏情况下的成本

（N 次插入后）

平均情况下的成本

（N 次随机插入后）

是否支持有序性相关的操作
查找插入查找插入
顺序查找（无序链表）NNN/2N否
二分查找（有序数组）lgN2NlgNN是

到此这篇关于C#使用符号表实现查找算法的文章就介绍到这了。希望对大家的学习有所帮助，也希望大家多多支持编程网。

--结束END--

本文标题: C#使用符号表实现查找算法

本文链接: https://lsjlt.com/news/146180.html(转载时请注明来源链接)

有问题或投稿请发送至: 邮箱/279061341@qq.com    QQ/279061341

猜你喜欢
  • C#使用符号表实现查找算法
    高效检索海量信息（经典查找算法）是现代信息世界的基础设施。我们使用符号表描述一张抽象的表格，将信息（值）存储在其中，然后按照指定的键来搜索并获取这些信息。键和值的具体意义取决于不同的...
    99+
    2024-04-02
  • C#怎么使用符号表实现查找算法
    今天小编给大家分享一下C#怎么使用符号表实现查找算法的相关知识点，内容详细，逻辑清晰，相信大部分人都还太了解这方面的知识，所以分享这篇文章给大家参考一下，希望大家阅读完这篇文章后有所收获，下面我们一起来了解一下吧。高效检索海量信息（经典查找...
    99+
    2023-06-30
  • 用C语言实现二分查找算法
    目录一.前言二.二分查找法1.什么是二分查找法2.如何用c语言来实现二分查找法三.总结总结一.前言 假如今天我们需要在一个有序的数组中来寻找一个数的下标，就用"1，2，3，...
    99+
    2024-04-02
  • Python查找算法之分块查找算法的实现
    一、分块查找算法 分块查找是二分法查找和顺序查找的改进方法，分块查找要求索引表是有序的，对块内结点没有排序要求，块内结点可以是有序的也可以是无序的。 分块查找就是把一个大的线性表分解...
    99+
    2024-04-02
  • Python查找算法之插补查找算法的实现
    一、插补查找算法 插补查找算法又称为插值查找，它是折半查找算法的改进版。插补查找是按照数据的分布，利用公式预测键值所在的位置，快速缩小键值所在序列的范围，慢慢逼近，直到查找到数据为止...
    99+
    2024-04-02
  • Python查找算法之折半查找算法的实现
    一、折半查找算法 折半查找算法又称为二分查找算法，折半查找算法是将数据分割成两等份，首先用键值(要查找的数据)与中间值进行比较。如果键值小于中间值，可确定要查找的键值在前半段；如果键...
    99+
    2024-04-02
  • 如何使用PHP实现顺序查找和二分查找算法
    这篇文章主要介绍了如何使用PHP实现顺序查找和二分查找算法，具有一定借鉴价值，感兴趣的朋友可以参考下，希望大家阅读完这篇文章之后大有收获，下面让小编带着大家一起了解一下。使用PHP描述顺序查找和二分查找（也...
    99+
    2024-04-02
  • php如何实现查找算法
    小编给大家分享一下php如何实现查找算法，相信大部分人都还不怎么了解，因此分享这篇文章给大家参考一下，希望大家阅读完这篇文章后大有收获，下面让我们一起去了解一下吧！php有什么特点1、执行速度快。2、具有很好的开放性和可扩展性。3、PHP支...
    99+
    2023-06-14
  • Python查找算法如何实现
    本文小编为大家详细介绍“Python查找算法如何实现”，内容详细，步骤清晰，细节处理妥当，希望这篇“Python查找算法如何实现”文章能帮助大家解决疑惑，下面跟着小编的思路慢慢深入，一起来学习新知识吧。查找算法是用来检索序列数据（群体）中是...
    99+
    2023-06-30
  • c语言逗号运算符的使用方法
    本文将为大家详细介绍“c语言逗号运算符的使用方法”，内容步骤清晰详细，细节处理妥当，而小编每天都会更新不同的知识点，希望这篇“c语言逗号运算符的使用方法”能够给你意想不到的收获，请大家跟着小编的思路慢慢深入，具体内容如下，一起去收获新知识吧...
    99+
    2023-06-06
  • sqlserver查找括号()中字符串内容的方法实现
    目录PATINDEX()函数charindex()函数SUBSTRING函数假如有一张学生表，表中学生姓名是学生的中文名(英文名)，如何获取括号中的英文名称。 需要用到两个SQL函数的配合，一个是PATINDEX()函...
    99+
    2023-05-16
    sqlserver查找括号中字符串 sqlserver查找字符串
  • C#二分查找算法怎么用
    这篇“C#二分查找算法怎么用”文章的知识点大部分人都不太理解，所以小编给大家总结了以下内容，内容详细，步骤清晰，具有一定的借鉴价值，希望大家阅读完这篇文章能有所收获，下面我们一起来看看这篇“C#二分查找算法怎么用”文章吧。1、定义：折半搜索...
    99+
    2023-06-30
  • C语言算法练习之折半查找的实现
    目录1. 题目描述2. 问题分析3. 算法设计4. 动图演示5. 代码实现6.知识点补充continue 语句break 语句continue语句 和 break语句的区别7. 问题...
    99+
    2024-04-02
  • 详解Go语言实现线性查找算法和二分查找算法
    目录线性查找算法二分查找算法小结线性查找 线性查找又称顺序查找，它是查找算法中最简单的一种。它的基本思想是在在一组数据中，从第一个元素开始，依次和预期值比较，直到和预期值相等，则查找...
    99+
    2022-12-20
    Go线性查找算法 Go二分查找算法 Go查找算法
  • C#运算符表达式的使用
    这篇文章主要介绍“C#运算符表达式的使用”，在日常操作中，相信很多人在C#运算符表达式的使用问题上存在疑惑，小编查阅了各式资料，整理出简单好用的操作方法，希望对大家解答”C#运算符表达式的使用”的疑惑有所帮助！接下来，请跟着小编一起来学习吧...
    99+
    2023-06-18
  • Python 语言实现六大查找算法
    目录一、顺序查找算法二、折半查找算法三、插补查找算法四、哈希查找算法五、分块查找算法六、斐波那契查找算法七、六种查找算法的时间复杂度一、顺序查找算法 顺序查找又称为线性查找，是最简单...
    99+
    2024-04-02
  • php二分查找算法怎么实现
    PHP实现二分查找算法的步骤如下： 确定要查找的数组和目标值。 定义一个函数，传入查找的数组、目标值以及数组的起始位置和结束位置作...
    99+
    2024-03-15
    php
  • Python算法练习之二分查找算法的实现
    目录1. 算法描述2. 算法分析3. 算法思路4. 代码实现纯算法实现递归法实现1. 算法描述 二分法是一种效率比较高的搜索方法 回忆之前做过的猜数字的小游戏，预先给定一个小于100...
    99+
    2024-04-02
  • Android编程实现从字符串中查找电话号码的方法
    本文实例讲述了Android编程实现从字符串中查找电话号码的方法。分享给大家供大家参考，具体如下： private List<String> getNumbe...
    99+
    2022-06-06
    电话 方法 字符串 字符 Android
  • Java实现查找算法的示例代码(二分查找、插值查找、斐波那契查找)
    目录1.查找概述2.顺序查找3.二分查找3.1 二分查找概述3.2 二分查找实现4.插值查找4.1 插值查找概述4.2 插值查找实现5.斐波那契查找5.1 斐波那契查找概述5.2 斐...
    99+
    2024-04-02
软考高级职称资格查询
热门wiki
近期文章
推荐阅读
热门问答
热门标签
编程网，编程工程师的家园，是目前国内优秀的开源技术社区之一，形成了由开源软件库、代码分享、资讯、协作翻译、讨论区和博客等几大频道内容，为IT开发者提供了一个发现、使用、并交流开源技术的平台。

  • 官方手机版

  • 微信公众号

  • 商务合作