数据结构-查找

》基本概念

        -查找表：用于查找的数据元素集合。查找表由同一类型的数据元素（或记录）构成。

        -静态查找表：

                在查找表中查看某个特定的数据元素是否在查找表中；检索某个特定元素的各种属性。

                静态查找表在查找过程中查找表本身不发生变化。对静态查找表进行的查找操作称为静态查找。

        -动态查找表：

                若在查找过程中可以将查找表中不存在的数据元素插入，或者从查找表中删除某个数据元素。

                动态查找表在查找过程中查找表可能会发生变化。对动态查找表进行的查找操作称为动态查找。

        -关键字：

                是数据元素中的某个数据项。唯一能标识数据元素（或记录）的关键字，即每个元素的关键字值互不相同，这种关键字称为主关键字；若查找表中某些元素的关键字值相同，称这种关键字为次关键字。

        -查找:

                在数据元素集合中查找满足某种条件的数据元素的过程称为查找。最简单且最常用的查找条件是“关键字值等于某个给定值”，在查找表搜索关键字等于给定值的数据元素（或记录）。若表中存在这样的记录，则称查找成功，此时的查找结果应给出找到记录的全部信息或指示找到记录的存储位置；若表中不存在关键字等于给定值的记录，则称查找不成功，此时查找的结果可以给出一个空记录或空指针。若按主关键字查找，查找结果是唯一的；若按次关键字查找，结果可能是多个记录，即结果可能不唯一。

        -查找表的存储结构：

                查找表是一种非常灵活的数据结构，对于不同的存储结构，其查找方法不同。为了提高查找速度，有时会采用一些特殊的存储结构。

        -查找算法的时间效率：

                查找过程的主要操作是关键字的比较，所以通常以“平均比较次数”来衡量查找算法的时间效率。

》顺序查找

        顺序查找是一种最简单的查找方法。其基本思想是将查找表作为一个线性表，可以是顺序表，也可以是链表，依次用查找条件中给定的值与查找表中数据元素的关键字值进行比较，若某个记录的关键字值与给定值相等，则查找成功，返回该记录的存储位置，反之，若直到最后一个记录，其关键字值与给定值均不相等，则查找失败，返回查找失败标志。

        顺序查找算法简单，对表的结构无任何要求；但是执行效率较低，尤其当n较大时，不宜采用这种查找方法。

        -顺序表的顺序查找

          假设在查找表中，数据元素个数为n（n<MAX_NUM），并分别存放在数组的下标变量a[1]~a[n]中。

          类型定义

          const MAX_NUM=100 //定义表的长度

          typedef struct ElemType{

                KeyType key;

                AnyType otheritem;

          }Se_List[MAX_NUM],Se_Item;

          //  在顺序表中查找关键字值等于k的记录，若查找成功，返回该记录的位置下标序号，否则返回0。

          int Seq_Search(Se_List a,KeyType k){

                i=1;

                while(i<=n&&a[i].key!=k)i++;

                   if(i<=n)return i;

                   else return 0;

          }//Seq_Search   

          //改进算法：设置了监视哨的顺序表查找，查找关键字值等于指定值k的记录，若查找成功，返回记录存放位置的下标值，否则返回0。

          int Seq_Search1(Se_List a,KeyType k){

                i=n;

                a[0].key=k;

                while(a[i].key!=k)i--;

                return i;

            }//Seq_Search

        -链表的顺序查找

        链表的顺序查找是指将查找表作为线性表并以链式存储结构存储，用顺序查找方法查找与指定关键字值相等的记录。

        类型定义

        typedef struct Node{

            KeyType key;        //结点的关键字类型

            AnyType otheritem;  //结点的其他成分

            struct Node *next;    //指向链表结点的指针

        }Link_Node,*Link;

        //将查找表中的数据元素用这种结构的结点表示，并以指向头结点的指针标识。对链表实现顺寻查找就是在有头结点的链式查找表中查找关键字值等于给定值的记录，若查找成功，返回指向相应结点的指针，否则返回空指针。

        Link_Node *Link_Search(Link h,KeyType k){

            p=h-next;

            while((p!=NULL)&&(p->key!=k))p=p->next;

            return p;

        }//Link_Search

》折半查找

        折半查找要求查找表用顺序存储结构存放且各数据元素按关键字有序（升序或隆序）排列，也就是说折半查找只适用于对有序顺序表进行查找。

        基本思想：

        首先以整个查找表作为查找范围，用查找条件中给定值k与中间位置结点的关键字比较，若相等，则查找成功，否则，根据比较结果缩小查找范围；

        如果k的值小于关键字的值，根据查找表的有序性可知查找的数据元素只有可能在表的前半部分，即在左半部分子表中，所以继续对左子表进行折半查找；

        若k的值大于中间结点的关键字值，则可以判定查找的数据元素只有可能在表的后半部分，即在右半部分子表中，所以应该继续对右子表进行折半查找。每进行一次折半查找，要么查找成功，结束查找，要么将查找范围缩小一半，如此重复，直到查找成功或查找范围缩小为空即查找失败为止。

        -算法实现：

            设查找表存放在a[1]~a[n]中，且升序，查找关键字值为k。
            折半查找的主要步骤为：
            置初始查找范围：low=1，high=n;
            求查找范围中间项：mid=(low+high)/2；
            将指定的关键字值k与中间项a[mid].key比较；
            若相等,查找成功,找到的数据元素为此时mid 指向的位置；
            若小于,查找范围的低端数据元素指针low不变,高端数据元素指针high更新为mid-1;
            若大于,查找范围的高端数据元素指针high不变，低端数据元素指针low更新为mid+1;
            重复步骤(2)、(3)直到查找成功或查找范围空(low>high)即查找失败为止。
            如果查找成功，返回找到元素的存放位置，即当前的中间项位置指针mid；否则返回查找失败标志。

        int Bin_Search(Se_List a,KeyType k){

            low=1;high=n;    //设置初始查找范围的高、低端指针

            while(low<=high){

                    mid=(low+high)/2;        //计算中间项的位置

                    if(k==a[mid].key)break;         // 找到，结束循环

                    else if(k<a[mid].key) high=mid-1; //计算mid值

                    else low=mid+1; //计算mid值

            }//while

            if(low<=high) return mid;        //查找成功

            else return 0;         //查找失败

        }//Bin_Search

》二叉排序树（动态查找）

        二叉排序树是一种常用的动态查找表，二叉排序树是一棵二叉树，它或者为空，或者具有如下性质：
            任一非终端结点若有左孩子，则该结点的关键字值大于其左孩子结点的关键字值，
            任一非终端结点若有右孩子，则该结点的关键字值小于其右孩子结点的关键字值。
        也可用递归的形式定义：
            若它的左子树非空，则其左子树所有结点的关键字值均小于其根结点的关键字值，
            若它的右子树非空，则其右子树所有结点的关键字值均大于其根结点的关键字值，
            它的左右子树都是二叉排序树。

        

        基本思想：

           若二叉树为空树，则查找失败，将给定值k与根结点的关键字值比较，若相等，则查找成功；

           若k < r->key，在左子树检索k，否则：若k > r->key，在右子树检索k，否则：k = r->key，找到，返回k的指针；若找到某个结点的左子树或右子树是空，则查找失败并返回空指针。

        类型定义：（链式存储结构）

        typedef struct Node{

            KeyType key;

            AnyType  otheritem;

            struct Node *lchild;

            struct Node *rchild;

        }Bin_Sort_tree_Node,*Bin_Sort_Tree;

        //  二叉排序树查找过程的描述是一个递归过程，若用链式存储结构存储，其查找操作的递归算法如下所示：

        //  在根指针为bt的二叉排序树上查找一个关键字值为k的结点，若查找成功返回指向该结点的指针，否则返回空指针。

        Bin_Sort_Tree_Node *Bt_Search(Bin_Sort_Tree bt,KeyType k){

            if((bt==NULL)||(bt->key==k)) return bt;      //树为空或找到返回该节点的指针

            else if(k<bt->key)    return Bt_Search(bt->lchild,k);   //在左子树中搜索

            else return bt(bt->rchild,k);                                //在右子树中搜索

        }//Bt_Search

        //非递归算法

        Bin_Sort_Tree_Node *Bt_Search1(Bin_Sort_Tree bt，KeyType k){

            p=bt;            //指针p指向根节点，搜索从根节点开始

            while(p!=NUll&&p->key!=k){

                if(k<p->key)p=p->lchild;

                else p=p->rchild;

            }//while

        }//Bt_Search1

        //插入

        //在一棵给定的二叉排序树中插入新结点，只要保证插入仍符合二叉排序树的定义即可。插入结点时，不需要遍历树，仅需走一条从根到某个有空子树的结点的路径。而插入的结点作为叶子结点。

        //方法：

                若二叉排序树(以r为根)为空，则待插入结点*s作为根结点插入空树中；
                否则(非空)，在二叉排序树中查找给定的结点，若找到（即：将待插入结点的关键字（前者）和树根的关键字（后者）比较，两者相等)，则无须插入，否则(查找必停止在左指针或右指针处)；
                若前者<后者，插入到左子树中，若前者>后者，插入到右子树中。

                

        //在以bt为根的二叉排序树上插入一个由指针p指向的新的结点(递归算法)

        void Bt_Insert(Bin_Sort_Tree *bt,Bin_Sort_Tree_Node *p){

            if(*bt==NULL) bt=p;

            else if(*bt->key>p->key) Bt_Insert(&(*bt->lchild),p);

            else if(*bt->key<p->key) Bt_Insert(&(*bt->rchild),p);

        }//Bt_Insert

        //非递归实现

        void Bt_Insert1(Bin_Sort_Tree *bt,Bin_Sort_Tree_Node *p){

            q=bt;

            while(q!=NULL&&q->key!=p->key){

                  s=q;

                  if(q->key>p->key) q=q->lchild;

                  else q=q->rchild; 

            }//while

            if(q==null){

                  if(s->key>p->key) s->lchild=p;

                  else s->rchild=p;

            }//if

        }//Bt_insert1

        //删除

        //在一棵给定的二叉排序树中删除一个结点，必须保证删除后仍符合二叉排序树的定义。关键是要找出替换结点。

        //基本思想（递归实现）：

        当r（根）为空时返回，否则：
        当r->key大于k，在r的左子树中删除之，
        当r-<key小于k，在r的右子树中删除之，
        当r的左子树为空时，用r的右子树代替，
        当r的右子树为空时，用r的左子树代替，
        当r的左、右子树不空时，找出r的左子树的“最右下”（最大结点）代替r。

         //非递归实现

       

       

       

       

        

》哈希表

    -哈希函数：将记录的关键字值与记录的存储位置对应起来的关系H称为哈希函数，H(k)的结果称为哈希地址。

    -哈希表：根据哈希函数建立的表。

    -基本思想：

        以记录的关键字值为自变量，根据哈希函数，计算出对应的哈希地址，并在此存储该记录的内容。

        当对记录进行查找时，再根据给定的关键字值，用同一个哈希函数计算出给定关键字值对应的存储地址，随后进行访问。所以哈希表既是一种存储形式，又是一种查找方法，通常将这种查找方法称为哈希查找。

     -冲突：有时可能会出现不同的关键字值其哈希函数计算的哈希地址相同的情况，然而同一个存储位置不可能存储两个记录，我们将这种情况称为冲突，具有相同函数值的关键字值称为同义词。在实际应用中冲突是不可能完全避免的。

     -建立哈希表，关键是构造哈希函数。其原则是尽可能地使任意一组关键字的哈希地址均匀地分布在整个地址空间中，即用任意关键字作为哈希函数的自变量其计算结果随机分布，以便减少冲突的发生可能性。

    -常用的哈希函数构造方法：

        //直接定址法：取关键字或关键字的某个线性函数为哈希地址。

                H(key)=key 或 H(key)=a*key+b

                其中a，b为常数，调整 a与b的值可以使哈希地址取值范围与存储空间范围一致。

       //质数取余法：取关键字被某个不大于哈希表表长n的质数m整除后所得余数为哈希地址。

                H(key)=key % m  (m<n，设其中n为哈希表长)

        质数取余法计算简单，适用范围大，但是整数m的选择很重要，如果选择不当，会产生较多同义词，使哈希表中有较多的冲突。

       //平方取中法：取关键字平方后的中间几位为哈希地址。由于平方后的中间几位数与原关键字的每一位数字都相关，只要原关键字的分布是随机的，以平方后的中间几位数作为哈希地址一定也是随机分布。

       //折叠法：把关键字折叠成位数相同的几部分,然后取这几部分的叠加作为哈希地址。在关键字位数较多,且每一位上数字的分布基本均匀时,采用折叠法,得到的哈希地址比较均匀。

       折叠法中数位叠加可以有移位叠加和间界叠加两种方法。移位叠加是将分割后的每一部分最低位对齐,然后相加;间界叠加是从一端向另一端沿分割界来回折迭,然后对齐相加。如关键码为7-302-03800-6,若Hash地址取4位,则此关键字的Hash地址采用折叠法得到如图所示,结果。

           

        //数字分析法：对于关键字的位数比存储区域的地址码位数多的情况，可以采取对关键字的各位进行分析，丢掉分布不均匀的位留下分布均匀的位作为Hash地址，这种方法称为数字分析法。

           

        -解决冲突的方法

        //开放定址法：

        发生冲突时，按照某种方法继续探测基本表中的其它存储单元，直到找到一个开放的地址（即空位置）为止。显然这种方法需要用某种标记区分空单元与非空单元。
        开放定址法的一般形式可表示为：
                    Hi（k）=（H（k）+di）mod m（i=1，2，…，k（k≤m-1））

        其中，H（k）为键字为k的直接哈希地址，m为哈希表长，di为每次再探测时的地址增量。当di=1，2，3，…，m-1时，称为线性探测再散列；当di=1^2，-1^2，2^2，-2^2，…，k^2，-k^2（k≤m/2）时，称为二次探测再散列；当di=随机数序列时，称为随机探测再散列。

        //再哈希法：