王道c语言-顺序查找、二分查找

顺序查找

#include <stdio.h>
#include <stdlib.h>
#include <time.h> //使用随机数

typedef int ElemType;
typedef struct {
    ElemType *elem; //Elem存储申请的堆空间的起始地址
    int TableLen;  //存储动态数组里元素个数
} SSTable;

void ST_Init(SSTable &ST, int len) {
    ST.TableLen = len + 1;//第0个位置，放哨兵
    ST.elem = (ElemType *) calloc(ST.TableLen, sizeof(ElemType));
    int i;
    srand(time(NULL));//随机数生成
    for (int i = 1; i < ST.TableLen; ++i) {
//        *(ST.elem+i)=rand()%100;
        ST.elem[i] = rand() % 100; //随机数被100取余，从而分布在0-99
    }
}

void ST_print(SSTable ST) {
    for (int i = 1; i < ST.TableLen; ++i) {
        printf("%d ", ST.elem[i]);
    }
    printf("\n");
}


int search_seq(SSTable ST, ElemType key) {
    int i;
    //从前往后查找
    //for (i = 1; i < ST.TableLen && key!=ST.elem[i]; ++i);return i;

    //从后往前查找
    ST.elem[0]=key;//0号元素作为哨兵，方便从后往前查找
    for (i = ST.TableLen-1; ST.elem[i]!=key; --i);
    return i;
}

int main() {
    SSTable ST; //顺序表
    ST_Init(ST, 10);
    ST_print(ST);
    ElemType key;
    printf("please input key value to be search:\n");
    scanf("%d", &key);
    int pos = search_seq(ST, key);
    printf("%d", pos);
    return 0;
}

折半查找 — 有序顺序表

#include <stdio.h>
#include <stdlib.h>
#include <time.h> //使用随机数

typedef int ElemType;
typedef struct {
    ElemType *elem; //Elem存储申请的堆空间的起始地址
    int TableLen;  //存储动态数组里元素个数
} SSTable;

//随机数初始化有序的顺序表
void ST_Init(SSTable &ST, int len) {
    ST.TableLen = len;
    ST.elem = (ElemType *) calloc(ST.TableLen, sizeof(ElemType));
    srand(time(NULL));
    for (int i = 0; i < ST.TableLen; ++i) {
        ST.elem[i] = rand() % 100;
    }
}

void ST_print(SSTable ST) {
    for (int i = 0; i < ST.TableLen; ++i) {
        printf("%d ", ST.elem[i]);
    }
    printf("\n");
}

//二分查找
int BinarySearch(SSTable L, ElemType key) {
    int low=0;
    int high=L.TableLen-1;
    int mid;
    //high>=low ，可以让mid既能取到low，也能取到high
    while (high>=low ){
        mid=(high+low)/2;
        if(key>L.elem[mid]){ //目标值大于中位数
            low=mid+1;
        } else if(key<L.elem[mid]){
            high=mid-1;
        } else if(key == L.elem[mid]){
            return mid;
        }
    }
    return -1;
}
//int (*compare)(const void *, const void *)
//compare 函数名中存储的是函数的入口地址，也是一个指针，是函数指针类型
//compare 有qsort调用，所以left right两个参数由qsort传入
//qsort规定如果left指针指向的值大于right指针指向的值，返回正值，小于为负值，等于为0。
//left right指向数组中任意两个元素
int compare(const void *left, const void *right){
    //qsort 可以排各种类型的数组，需要强转指针类型,强转指针类型不改变指针值
    //void*指针，无法取值，因为不知道指针指向多大空间
    return *(int*)left-*(int*)right;
//    return *(int*)right-*(int*)left; //从大到小排序
}

int main() {
    SSTable ST; //顺序表
    ST_Init(ST, 10);
    ST_print(ST);
    qsort(ST.elem,ST.TableLen,sizeof (ElemType),compare);//compare是比较规则
    ST_print(ST);
    ElemType key;
    printf("please input key value to be search:\n");
    scanf("%d", &key);
    int pos = BinarySearch(ST, key);
    if(pos!=-1)
        printf("find key %d\n", pos);
    else
        printf("not find\n");
    return 0;
}