數據結構-靜態查找

數據結構-靜態查找

查找

主要討論順序表、有序表、索引表和哈希表查找的各種實現方法，以及相應查找方法在等概率情況下的平均查找長度。

 查找表(Search Table)：相同類型的數據元素(對象)組成的集合，每個元素通常由若干數據項構成。
   關鍵字(Key，碼)：數據元素中某個(或幾個)數據項的值，它可以標識一個數據元素。若關鍵字能唯一標識一個數據元素，則關鍵字稱為主關鍵字（Primary Key） ；將能標識若干個數據元素的關鍵字稱為次關鍵字（Secondary Key） 。
   查找/檢索(Searching)：根據給定的K值，在查找表中確定一個關鍵字等於給定值的記錄或數據元素。

◆ 查找表中存在滿足條件的記錄：查找成功；結果：所查到的記錄信息或記錄在查找表中的位置。
◆ 查找表中不存在滿足條件的記錄：查找失敗。
根據查找表的操作方式，分為靜態查找表和動態查找表。
靜態查找表(Static Search)： 只對查找表進行如下操作：
（1）查看某個特定的數據元素是否在查找表中，
（2）檢索某個特定元素和各種屬性。
動態查找表(Dynamic Search)：在查找過程中，可進行如下操作：
（1）可以將查找表中不存在的數據元素插入，
（2）從查找表中刪除已存在的某個記錄。
為了提高查找的效率，除了應用好的查找算法外，也會為查找設立專門的數據結構來存儲數據，比如表、樹等等。
查找表的存儲結構：
查找表是一種非常靈活的數據結構，可以用多種方式來存儲。
根據存儲結構的不同，查找方法可分為三大類：
① 順序表和鏈表的查找：將給定的K值與查找表中記錄的關鍵字進行比較， 找到要查找的記錄；
② 散列表的查找：根據給定的K值直接訪問查找表， 從而找到要查找的記錄；
③ 索引查找表的查找：首先根據索引確定待查找記錄所在的塊 ，然後再從塊中找到要查找的記錄。
一般地，認為記錄的關鍵字是一些可以進行比較運算的類型，如整型、字符型、實型等，本章以後各節中討論所涉及的關鍵字、數據元素等的類型描述如下：
典型的關鍵字類型說明是：

typedef  float   KeyType ;       /*  實型  */
typedef  int   KeyType ;       /*  整型  */
typedef  char  KeyType ;       /*  字符型  */
       數據元素類型的定義是：
typedef  struct  RecType
{  KeyType  key ;          /* 關鍵字碼  */
┇ /* 其他域  */
}RecType ;

    靜態查找表的抽象數據類型定義如下：

＃define MAX_SIZE  100
typedef  struct  SSTable
{  RecType  elem[MAX_SIZE] ;    /*  順序表  */
int  length ;     /*  實際元素個數  */
}SSTable ;

int  Seq_Search ( SSTable  ST , KeyType key)
{   int i ;   
ST. elem[0].key=key ;    /*  設置監視哨兵,失敗返回0  */
for (i=ST.length; i>=1;i--)
     if (ST. elem[i].key==key)
            return i; 
return 0; 
} 

2  算法實現
int  Bin_Search(SSTable  ST , KeyType  key)
{    int  Low=1，High=ST.length, Mid ;
while (Low<High)
{     Mid=(Low+High)/2 ;
if  (ST. elem[Mid].key== key))  
    return(Mid) ; 
else if (ST. elem[Mid].key<key))  
           Low=Mid+1 ;
       else   High=Mid-1 ;
}
return(0) ;      /*   查找失敗  */ 
}

       Fibonacci查找方法是根據Fibonacci數列的特點對查找表進行分割。Fibonacci數列的定義是：
        F(0)=0，F(1)=1，F(j)=F(j-1)+F(j-2) 。
若共有20（F(8)-1）個數， j=8,則mid= low+F(7)-1 =13
若key <a[13], 則low=1，high=12
下一步：j=7, mid= low+F(6)-1 =8
若key >a[13], 則low=14，high=20（ F(8) -1）
下一步：j=6, mid=low+F(5)-1=18

int fib(int n)
{    int i, f , f0=0 , f1=1 ;
if (n==0)  return(0) ;
if (n==1)  return(1) ;
for (i=2 ; i<=n ; i++ )
{   f=f0+f1 ; f0=f1 ; f1=f ;   }
return(f) ;
}
int Fib_search(RecType ST[] , KeyType key , int n)
    /*  在有序表ST中用Fibonacci方法查找關鍵字為key的記錄  */
{    int Low=1, High, Mid, f1, f2 ;
High=fib(n)-1 ; f1=fib(n-1) ; f2=fib(n-2) ;
while (Low<=High)
{   Mid=Low+f1-1;
                          if ( ST.[Mid].key==key )   return(Mid) ;
                          else if ( key<ST.[Mid].key) )
                                {   High=Mid-1 ; f2=f1-f2 ; f1=f1-f2 ;     }
                                 else  
                                {   Low=Mid+1 ;f1=f1-f2 ; f2=f2-f1 ;  }
                      }
      return(0) ; 
} 

算法實現
typedef struct IndexType
{ keyType  maxkey ;     /*  塊中最大的關鍵字  */
   int startpos ;     /*  塊的起始位置  */
}Index;
int Block_search(RecType ST[] , Index ind[] , KeyType key , int n , int b)
      /*  在分塊索引表中查找關鍵字為key的記錄 */   
      /*表長為n ，塊數為b */
{          int i=0 , j , k ;
while ((i<b)&&LT(ind[i].maxkey, key) )  i++  ;
if (i>b) {  printf("\nNot found");   return(0);  }
j=ind[i].startpos ;
while ((j<n)&&LQ(ST[j].key, ind[i].maxkey) )
{   if ( EQ(ST[j].key, key) )  break ;
j++ ;
}     /*  在塊內查找  */
           if (j>n||!EQ(ST[j].key, key) )
               {  j=0; printf("\nNot found");  }
          return(j); 
}