常用的查找算法_.NET_程序员俱乐部

您所在的位置：程序员俱乐部 > 编程开发 > .NET > 常用的查找算法

常用的查找算法

2014/10/27 3:16:12 麻将我会程序员俱乐部我要评论(0)

摘要：顺序查找二分法查找分块查找散列表查找（哈希表）顺序查找的基本思想：从表的一端开始，顺序扫描表，依次将扫描到的结点关键字和给定值（假定为a）相比较，若当前结点关键字与a相等，则查找成功；若扫描结束后，仍未找到关键字等于a的结点，则查找失败。说白了就是，从头到尾，一个一个地比，找着相同的就成功，找不到就失败。很明显的缺点就是查找效率低。适用于线性表的顺序存储结构和链式存储结构。计算平均查找长度。例如上表，查找1，需要1次，查找2需要2次，依次往下推，可知查找16需要16次，可以看出
标签：常用查找算法

顺序查找
二分法查找
分块查找
散列表查找（哈希表）

顺序查找的基本思想：

从表的一端开始，顺序扫描表，依次将扫描到的结点关键字和给定值（假定为a）相比较，若当前结点关键字与a相等，则查找成功；若扫描结束后，仍未找到关键字等于a的结点，则查找失败。

说白了就是，从头到尾，一个一个地比，找着相同的就成功，找不到就失败。很明显的缺点就是查找效率低。

适用于线性表的顺序存储结构和链式存储结构。

计算平均查找长度。

例如上表，查找1，需要1次，查找2需要2次，依次往下推，可知查找16需要16次，

可以看出，我们只要将这些查找次数求和（我们初中学的，上底加下底乘以高除以2），然后除以结点数，即为平均查找长度。

设n=节点数

平均查找长度=（n+1）/2

演示代码：

class="brush:csharp;gutter:true;">int[] aa = { 3, 6, 8, 7, 10, 15, 12, 14, 16, 17, 20, 21 };
for (int i = 0; i < aa.Length; i++)
{
  if(8 == aa[i])
  {
    Console.WriteLine("找到目标元素");
  }
}

二分法查找（折半查找）的基本思想：

（1）确定该区间的中点位置：mid=（low+high）/2

min代表区间中间的结点的位置，low代表区间最左结点位置，high代表区间最右结点位置

（2）将待查a值与结点mid的关键字（下面用R[mid].key）比较，若相等，则查找成功，否则确定新的查找区间：

如果R[mid].key>a，则由表的有序性可知，R[mid].key右侧的值都大于a，所以等于a的关键字如果存在，必然在R[mid].key左边的表中。这时high=mid-1

如果R[mid].key<a,则等于a的关键字如果存在，必然在R[mid].key右边的表中。这时low=mid

如果R[mid].key=a，则查找成功。

（3）下一次查找针对新的查找区间，重复步骤（1）和（2）

（4）在查找过程中，low逐步增加，high逐步减少，如果high<low，则查找失败。

平均查找长度=Log2(n+1)-1

注：虽然二分法查找的效率高，但是要将表按关键字排序。而排序本身是一种很费时的运算，所以二分法比较适用于顺序存储结构。为保持表的有序性，在顺序结构中插入和删除都必须移动大量的结点。因此，二分查找特别适用于那种一经建立就很少改动而又经常需要查找的线性表。

代码实现：

       /// <summary>
        /// 二分法查找
        /// </summary>
        /// <param name="array">目标数组(已经排序好了)</param>
        /// <param name="a">查找的数</param>
        /// <returns>目标数的索引</returns>
        public int BinarySearch(int[] array, int T)
        {
            int low, high, mid;
            low = 0;
            high = array.Length - 1;
            while (low <= high)
            {
                mid = (low + high) / 2;
                if (array[mid] < T)
                {
                    low = mid + 1;
                }
                else if (array[mid]>T)
                {
                    high = mid - 1;
                }
                else
                {
                    return mid;
                }
            }
            return -1;
        }

分块查找的基本思想：

分块查找(Blocking Search)又称索引顺序查找。它是一种性能介于顺序查找和二分查找之间的查找方法

前提条件： 块内无序块间有序
方法：二分查找块间 顺序查找块内

二分查找表由"分块有序"的线性表和索引表组成
1."分块有序"的线性表
表R[1..n]均分为b块，前b-1块中结点个数为 s ，第b块的结点数小于等于s；每一块中的关键字不一定有序，但前一块中的最大关键字必须小于后一块中的最小关键字，即表是"分块有序"的。
2.索引表
抽取各块中的最大关键字及其起始位置构成一个索引表ID[l..b]，即：
ID[i](1≤i≤b)中存放第i块的最大关键字及该块在表R中的起始位置。由于表R是分块有序的，所以索引表是一个递增有序表。

因此采用顺序或二分查找索引表，以确定待查结点在哪一块，由于块内无序，只能用顺序查找

logs_code_hide('bfc9803c-2984-4be1-a861-2d71cf7bdd14',event)" src="/Upload/Images/2014102703/2B1B950FA3DF188F.gif" alt="" />

using System;
using System.Collections.Generic;
using System.Text;

namespace 分块查找
{
    class Program
    {
        static void Main(string[] args)
        {
            int[] aa = { 3, 6, 8, 7, 10, 15, 12, 14, 16, 17, 20, 21 };

            for (int i = 0; i < aa.Length; i++)
            {
                if (8 == aa[i])
                {
                    Console.WriteLine("找到目标元素");
                }
            }

            int ysnum, zu, ww = 0;
            for (int aa1 = 0; aa1 < aa.Length; aa1++)
                Console.Write(aa[aa1] + " ");
            Console.WriteLine();
            Console.WriteLine("元素个数：{0}", aa.Length);
            ysnum = aa.Length;

            #region 分块
            Console.Write("请输入组数：");
            zu = Convert.ToInt32(Console.ReadLine());
            int d = aa.Length / zu;
            int[,] fenkuai = new int[zu, d];
            Console.WriteLine("分块如下：");
            for (int z = 0; z < zu; z++)//进行分块
                for (int y = 0; y < d; y++)
                {
                    fenkuai[z, y] = aa[ww];
                    ww++;
                }


            for (int z = 0; z < zu; z++)//输出分块
            {
                for (int y = 0; y < d; y++)
                {
                    Console.Write("{0}  ", fenkuai[z, y]);
                }
                Console.WriteLine();
            }
            #endregion

            #region 确定各分块的索引表
            Console.WriteLine("关键字：");
            int[] suoyin = new int[zu];
            int q = 0;
            int index = 0;
            for (int z = 0; z < zu; z++)
            {
                int y;
                for (y = 0; y < d; y++)
                {
                    if (q < fenkuai[z, y])
                    {
                        q = fenkuai[z, y];
                    }
                }
                //Console.Write("{0}  ", q);//输出索引表
                ////建立索引表
                if (index < zu)
                {
                    suoyin[index] = q;
                }
                index++;
            }
            for (int n = 0; n < zu; n++)
            {
                Console.Write(suoyin[n] + " ");
            }
            #endregion

            #region 块内进行顺序查找
            Console.WriteLine("请输入要查找的值：");
            int kk = Convert.ToInt32(Console.ReadLine());
            int pp = shunxu(suoyin, kk);
            for (int n = 0; n < d; n++)
            {
                if (kk == fenkuai[pp, n])
                {
                    Console.WriteLine("该数值在元素当中");
                }
            }
            #endregion

            Console.ReadLine();
        }


        public static int shunxu(int[] aa, int k)
        {
            for (int a = 0; a < aa.Length - 1; a++)
            {
                if (k <= aa[a])
                {
                    return a;
                }
            }
            return -1;
        }
    }
}

View Code

散列表查找（哈希表）

哈希技术是查找和检索与唯一标识键相关信息的最好方法之一。哈希表的基本原理是将给定的键值转换为偏移地址来检索记录。

键转换为地址是通过一种关系来完成，就是哈希函数。哈希函数对键执行操作，从而给定一个哈希值，该值是代表可以找到该记录的位置。

哈希法的基本思想是：设置一个长度为m的表T，用一个函数将数据集合中n个记录的关键字尽可能唯一地转换成0~m-1范围内的数值

哈希表的冲突现象

两个不同的关键字，由于哈希函数值相同，因而被映射到同一个位置，为冲突。

解决哈希冲突

链表法：将所有关键字为同义词的结点链接在同一个单链表中。即同一位置用单链表存储键相同而值不同的记录。

   /// <summary>
        /// 在哈希表中插入记录，用链表法解决冲突
        /// </summary>
        /// <param name="a"></param>
        /// <param name="key"></param>
        /// <param name="Mod"></param>
        /// <returns></returns>
        public bool HashInsert(chaintype[] a, int key, int Mod)
        {
            int i;
            i = Hash(key, Mod);
            chaintype pre;
            chaintype cur;
            pre = a[i];
            cur = a[i];

            while (cur != null && cur.Key != key)
            {
                pre = cur;
                cur = cur.Next;
            }

            /*未查找到时插入该记录在对应的链表尾*/
            if (cur == null)
            {
                cur = new chaintype();
                cur.Key = key;
                cur.Next = null;
                /*在该链插入第一个记录*/
                if (a[i] == null)
                    a[i] = cur;
                else
                    pre.Next = cur;
                return true;
            }
            return false;
        }


        public chaintype HashSearch(chaintype[] a, int key, int Mod)
        {
            chaintype p;
            int i = Hash(key, Mod);
            p = a[i];
            while (p != null && p.Key != key)
            { p = p.Next; }
            if (p == null) return null;
            else
                return p;
        }

代码调用：

      searchA.HashInsert(a, 70, 13);
                            searchA.HashInsert(a, 30, 13);
                            searchA.HashInsert(a, 40, 13);
                            searchA.HashInsert(a, 10, 13);
                            searchA.HashInsert(a, 80, 13);
                            searchA.HashInsert(a, 20, 13);
                            searchA.HashInsert(a, 90, 13);
                            searchA.HashInsert(a, 100, 13);
                            searchA.HashInsert(a, 75, 13);
                            searchA.HashInsert(a, 60, 13);
                            searchA.HashInsert(a, 45, 13);
                            Console.WriteLine("请输入要查找的数字：");
                            long time1 = System.DateTime.Now.Ticks;
                            int num = Convert.ToInt32(Console.ReadLine());
                            chaintype p = searchA.HashSearch(a, num, 13);
                            if (p == null)
                                Console.WriteLine("{0}在数据列表中不存在", num);
                            else
                                Console.WriteLine("您查找的关键字是：{0}", p.Key);
                            long time2 = System.DateTime.Now.Ticks;
                            Console.WriteLine("哈希表查找用时{0}", time2 - time1);