datastruct_5

查找相关笔记

#include <ctype.h>
#include <limits.h>
#include <math.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct {   //【适用于顺序表】
    int* elem;     //动态数组基址（利用malloc）
    int TableLen;  //表长
} SSTable;
int Search_Seq(SSTable ST, int key) {
    int i;
    for (i = 0; i < ST.TableLen && ST.elem[i] != key; ++i) {
        return i == ST.TableLen ? -1 : i;  //返回元素下标或返回-1
    }
}  //顺序查找
int Binary_Search(SSTable L, int key) {
    int low = 0, high = L.TableLen - 1, mid;
    while (low <= high) {
        mid = low + (high - low) / 2;
        if (L.elem[mid] == key) {
            return mid;
        } else if (L.elem[mid] > key) {
            high = mid - 1;
        } else {
            low = mid + 1;
        }
    }
    return -1;
}  //折半查找(升序排列)
//分块查找：
// B树：
// B+树：
//散列查找（哈希表）【用空间换时间】：
//如何解决哈希冲突：
//拉链法：
// 1.除留余数法：H（key）=key%p【散列表表长为m，p为不大于m且最接近m的质数】
// 2.直接定址法：H（key）=a*key+b【a，b为常数】
// 3.数字分析法：选取数码分布较为均匀的若干位作为散列地址
// 4.平方取中法：关键词平方的中间几位作为散列地址
//开放地址法：
// 1.线性探索法：探测后一位后取模
// 2.平方查找法：
// 冲突数平方后取正负数再取模（发生偏移）【此时散列表长度应为4*j+3长度的素数，才能完成所有位置的搜索】
// 3.伪随机序列法 :加随机数后取模
//再散列法：