顺序表查找和折半查找

#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#include <memory.h>  //包含memsetd的函数

//对两个数值型关键字的比较约定如下：
#define EQ(a,b)   ((a) == (b))
#define LT(a,b)   ((a) < (b)) 
#define LQ(a,b)   ((a) <= (b))

#define OK 1;
#define KeyType int
//#define ElemType int

typedef struct KeyTable
{
    KeyType key;  //关键字字域
}ElemType;

struct SSTable
{
    ElemType *elem; //数据元素存储空间基址，建表时按实际长度分配，0号单元留空
    int length;   
    int cnt; //有效元素的个数
};

void Init_arr(SSTable *ST,ElemType *arr,int n);
void Creat_Seq(SSTable *ST,ElemType *arr,int n);  //给数组赋值
void Ascend(SSTable *ST);  //重建静态查找表，排序 升序
void Creat_Ord(SSTable *ST, ElemType *arr,int n);
int Destroy(SSTable *ST);
int Search_Seq(SSTable *ST,KeyType key);
int Search_Bin(SSTable *ST,KeyType key); //折半查找
void Traverse(SSTable *ST);

int main(void)
{
    int seq,bin;
    struct SSTable pSSTable;
    ElemType r[6] = {4,2,1,3,6,5};
    Init_arr(&pSSTable,r,6);
    Creat_Seq(&pSSTable,r,6);
    Traverse(&pSSTable);


    Ascend(&pSSTable);
    printf("排序后的元素为：\n");
    Traverse(&pSSTable);

    seq = Search_Seq(&pSSTable,3);
    printf("顺序查找元素的下标为：%d\n",seq);

    bin = Search_Bin(&pSSTable,8);
    printf("折半查找元素的小标为：%d\n",bin);

    return 0;
}

void Init_arr(SSTable *ST,ElemType *arr,int n)
{
    ST->elem = (ElemType *)calloc(n+1,sizeof(ElemType));
    if(NULL == ST->elem)
    {
        printf("动态内存分配失败!\n");
        exit(-1);
    }
    else
    {
        memset(ST->elem,0,n+1);//初始化分配的内存区域，初始化为0
        ST->length = n+1; //整个数组的长度
        ST->cnt = 0;
    /*  for(int i=0 ; i<n ; i++)
     *  {
     *      ST->elem[i+1] = arr[i];
     *      (ST->cnt)++;
     *  } 
     */
    }
}

void Creat_Seq(SSTable *ST,ElemType *arr,int n)  //给数组赋值
{
    int i;
    for(i=0 ,ST->cnt = 0 ; i<n ; i++)
    {
        ST->elem[i+1] = arr[i];
        (ST->cnt)++;
    }   
}

void Ascend(SSTable *ST)
{
    int i,j;
    for(i=1 ; i<ST->cnt ; i++)
    {
        ST->elem[0] = ST->elem[i];  //待比较值存[0]单元

        for(j=i+1 ; j<=ST->cnt ; j++)
        {
            if(ST->elem[i].key > ST->elem[j].key)
            {
                ST->elem[0] = ST->elem[j];
                ST->elem[j] = ST->elem[i];
                ST->elem[i] = ST->elem[0];
            }
        }
    }
}


int Destroy(SSTable *ST)
{
    free(ST->elem);
    ST->elem = NULL;
    ST->length = 0;
    ST->cnt = 0;
    return OK;
}

int Search_Seq(SSTable *ST,KeyType key)
{
    int i;
    ST->elem[0].key = key; //哨兵

    for(i=ST->cnt ; key != (ST->elem[i].key) ; --i); //从前往后找

    return i; //找不到i=0
}

int Search_Bin(SSTable *ST,KeyType key) //折半查找
{
    int low,high,mid;
    low = 1;
    high = ST->cnt;
    while(low <= high)
    {
        mid = (low + high)/2;
        if(key == ST->elem[mid].key)
            return mid;  //返回查找元素的下标
        else if(key < (ST->elem[mid].key))
            high = mid -1;
        else
            low = mid + 1;
    }
    return 0; //查找失败返回0
}

void Traverse(SSTable *ST)
{
    int i;
    ElemType *p = ST->elem;
    for(i = 1;i <= ST->cnt ;i++)
        printf("  %d",p[i].key);
    printf("\n");
}