顺序查找 排序 二分查找

顺序查找 排序 二分查找代码

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

typedef int ElemType;
typedef struct {
    ElemType *elem; // 整形指针
    int length;  // 存储动态数组里边元素的个数
} SSTable;

// 初始化
void initSSTable(SSTable &S, int length) {
    // 多申请一个位置，为了存哨兵
    S.length = length + 1;
    S.elem = (ElemType *) malloc(sizeof(ElemType) * S.length);
    int i;
    // 随机生成数
    srand(time(NULL)); //生成随机数
    // 因为第0个是哨兵，所以从第1个开始随机
    for (i = 1; i < S.length; i++) {
        S.elem[i] = rand() % 100;
    }
}

// 打印
void printST(SSTable S) {
    // 从1开始打印，0是哨兵
    for (int i = 1; i < S.length; i++) {
        printf("%3d", S.elem[i]);
    }
    printf("\n");
}

// 查找
int selSSTable(SSTable S, ElemType e) {
    S.elem[0] = e;
    int i;
    // 方式一循环
//    for (i = S.length - 1; S.elem[i] != e; i--);
//    return i;
    // 方式二循环
    for (i = S.length - 1; i >= 0; i--) {
        if (S.elem[i] == e) {
            return i;
        }
    }
    return -1;
}

// 二分查找 时间复杂度 logN
int binarySearch(SSTable L, ElemType key) {
    int low = 0, mid, high = L.length - 1;
    while (low <= high) {
        mid = (low + high) / 2;
        if (L.elem[mid] == key) {
            return mid;//等于就找到了
        } else if (L.elem[mid] > key) {
            high = mid - 1;
        } else {
            low = mid + 1;
        }
    }
    return -1;
}

// 排序
int compare(const void *left, const void *right) {//left，right 是任意两个元素的地址值
    return *(ElemType *) left - *(ElemType *) right;
    //return *(ElemType*)right - *(ElemType*)left;//从大到小
}

// 顺序查找 折半查找（二分查找）
int main() {
    SSTable S;
    // 初始化
    initSSTable(S, 10);
    // 打印
    printST(S);
    // 顺序查找，输入要查找的元素
    ElemType key;
    printf("请输入要查询的元素\n");
    scanf("%d", &key);
    int index = selSSTable(S, key);
    if (index) {
        printf("查找元素的位置为：%d\n", index);
    } else {
        printf("没有找到");
    }

    //排序 qsort 实现的是快排
    qsort(S.elem, S.length, sizeof(ElemType), compare);
    printf("排序后的顺序是\n");
    printST(S);
    // 二分查找
    printf("请输入要查询的值\n");
    scanf("%d", &key);
    int ret = binarySearch(S, key);
    if (ret != -1) {
        printf("查找成功 位置为 %d\n", ret);
    } else {
        printf("查找失败\n");
    }
    return 0;
}