データ構造C言語-リニアテーブル検索(逐次検索、半変換検索)

10994 ワード

#include 
#include 

#define OK 1
#define ERROR 0
#define OVERFLOW -2
typedef int status;
typedef int KeyType;
typedef int InfoType;

typedef struct
{
    KeyType key;
    InfoType otherinfo;
}ElemType;

typedef struct
{
    ElemType *R;
    int length;
}SSTable;

/*          */
int Search_Seq(SSTable ST,KeyType key)
{
    ST.R[0].key=key;//ST.R[0]    ,[0]      
    int i;
    for(i=ST.length;ST.R[i].key!=key;i--);//  ;        
    return i;
}
/*    */
int Search_Bin(SSTable ST,KeyType key)
{
    int low=1,high=ST.length,mid;
    while(low<=high)
    {
        mid=(low+high)/2;
        if(key==ST.R[mid].key)
            return mid;
        else if(key<ST.R[mid].key)
            high=mid-1;
        else
            low=mid+1;
    }
    return 0;
}

int main()
{
    SSTable ST;
    ST.length=11;
    KeyType k[12]={0,5,16,20,27,30,36,44,55,60,67,71};
    int i;
    ST.R=(ElemType *)malloc(sizeof(ElemType)*(ST.length+1));
    printf("Create sequence as following:
"
); for(i=1;i<=ST.length;i++) { ST.R[i].key=k[i]; printf("%d ",ST.R[i].key); } KeyType key=27; printf("
Search_Seq %d result:%d"
,key,Search_Seq(ST,key)); printf("
Search_Bin %d result:%d"
,key,Search_Bin(ST,key)); return 0; }