首页 > 编程语言 >查找算法与哈希表

查找算法与哈希表

时间:2022-10-15 23:12:35浏览次数:50  
标签:node Node return 哈希 int 算法 查找 str table

三分查找

应用场景:求下列一元二次函数的极大值

\[ax^2 + bx + c \]

#include <stdio.h>

int ternary_search(int *arr, int l, int r) {
    int tri, m1, m2;
    do {
        tri = (r - l) / 3;
        m1 = l + tri, m2 = r - tri;
        if (arr[m1] < arr[m2]) l = m1 + 1;
        else r = m2 - 1;
    } while (m1 < m2);
    return arr[m1];
}

int main() {
    int MAX_N;
    printf("test_amount = ");
    while (scanf("%d", &MAX_N)) {
        int y[MAX_N];
        int a = -1, b = MAX_N, c = 1;
        for (int x = 0; x < MAX_N; x++) {
            y[x] = a * x * x + b * x + c; //^为按位异或
            printf("%d ", y[x]);
        }
        printf("\n");
        int max = ternary_search(y, 0, MAX_N - 1);
        printf("max = %d\n", max);
        printf("\n");
        printf("test_amount = ");
    }
    return 0;
}

哈希表(散列表)

哈希表查找:

  1. 哈希函数:BKDRHash
  2. 冲突处理方法:拉链法

本质是通过“哈希函数”建立“索引”

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

typedef struct Node {
    char *str;
    struct Node *next;
} Node;

typedef struct HashTable {
    Node **data;
    int size;
} HashTable;

Node *init_node(char *str, Node *head) {
    Node *node = (Node *)malloc(sizeof(Node));
    node->str = strdup(str); //深复制
    //node->str = str; //浅复制
    //禁用原因:节点中字符串的值会跟随着scanf("%s", str)而发生改变。若Hash值刚好相同时,则此时即便不存在的字符串也会被显示为找到!如:首先输入"0 A]",之后输入"1 B>"便会出错。
    //Hash("A]") = 65 * 31 + 93
    //Hash("B>") = 66 * 31 + 62
    node->next = head;
    return node;
}

HashTable *init_table(int size) {
    HashTable *table = (HashTable *)malloc(sizeof(HashTable));
    table->data = (Node **)calloc(size, sizeof(Node *));
    table->size = size;
    return table;
}

void clear_node(Node *node) {
    if (node == NULL) return;
    Node *post_node;
    while (node != NULL) {
        post_node = node->next;
        free(node->str);
        free(node);
        node = post_node;
    }
    return;
}

void clear_table(HashTable *table) {
    if (table == NULL) return;
    for (int i = 0; i < table->size; i++) {
        clear_node(table->data[i]);
    }
    free(table->data);
    free(table);
    return;
}

int BKDRHash(char *str) {
    int seed = 31, hash = 0; //seed只能是奇数,偶数作为高位会被舍弃,但为什么是31?
    for (int i = 0; str[i]; i++) hash = hash * seed + str[i]; //编码
    return hash & 0x7fffffff; //保证余数一定非负
}

int insert(HashTable *table, char *str) {
    int hash = BKDRHash(str);
    int ind = hash % table->size;
    table->data[ind] = init_node(str, table->data[ind]); //拉链法
    return 1;
}

int search(HashTable *table, char *str) {
    int hash = BKDRHash(str);
    int ind = hash % table->size;
    Node *node = table->data[ind];
    while (node != NULL) {
        if (strcmp(node->str, str) == 0) return 1;
        node = node->next;
    }
    return 0;
}

int main() {
    int op;
    #define MAX_N 100
    char str[100] = {0};
    HashTable *table = init_table(MAX_N * 2);
    while (scanf("%d%s", &op, str)) {
        switch (op) {
            case 0:
                printf("insert %s to the HashTable = %d\n", str, insert(table, str));
                break;
            default:
                printf("search %s from the HashTable = %d\n", str, search(table, str));
                break;
        }
        printf("\n");
    }
    #undef MAX_N
    clear_table(table);
    return 0;
}

标签:node,Node,return,哈希,int,算法,查找,str,table
From: https://www.cnblogs.com/Kelvin-Wu/p/16795307.html

相关文章

  • 排序算法
    内部排序:稳定排序(冒泡、插入、归并):重复的元素一定按原始顺序排列非稳定排序(选择、快排)外部排序:多路归并排序#include<stdio.h>#include<stdlib.h>#include<......
  • 比较排序算法概述
    文章目录​​排序​​​​ref​​​​排序的对象​​​​排序分类​​​​排序算法的稳定性SortAlgorithmStability​​​​性能分析​​​​比较排序算法的性能分析原则​......
  • 原来ShardingSphere也用雪花算法
    原来ShardingSphere也用雪花算法分布式主键的生成有很多实现方式,比如百度开源的UidGenerator、美团的Leaf、以及众所周知的雪花算法,而在分库分表的场景下,id要保证唯一性,分......
  • 代码随想录算法训练营第四天 | 24. 两两交换链表中的节点 19.删除链表的倒数第N个节
    24.两两交换链表中的节点本题是一道模拟过程的题目。搞清楚两两交换的步骤之后,写出对应的代码也就不是难题了。不过在学习题解的过程中发现,两两交换的步骤也有很多种实现......
  • AcWing 算法提高课 通过递推求等比数列的和(防止使用逆元出现问题)
    基于分治的思想:  例题:https://www.acwing.com/problem/content/99/模板:求num^0+num^1+...+num^kconstintMOD=9901;intQuickExp(intbase,intexp){bas......
  • 【翻译】Raft 共识算法:集群成员变更
    转载请注明出处:https://www.cnblogs.com/morningli/p/16770129.html之前都在集群配置是固定的(参与共识算法的server集合)假设下讨论raft。在实践中,偶尔有需要改变配置,比如......
  • kmp算法快速简易理解
    1.求next数组1.1定义什么是最长相等前后缀长度?​ 字符串ab的最长相等前后缀为空集,长度为0​ 字符串aba的最长相等前后缀为a,长度为1​ 字符串aaa的最长相等前......
  • 【算法】KNN、SVM算法详解!
    什么是KNN算法寻找未知分类数据的离它最近的n个已知数据,通过已知数据的分类来推断这个未知数据的分类KNN的原理步骤计算距离(常用欧几里得距离或马氏距离)升序排列(最近......
  • Problem P28. [算法课回溯] 电话号码的字母组合
    回溯,唯一麻烦的是要建立一个字典,键值对为数字字符对应英文字符串#include<iostream>#include<bits/stdc++.h>#include<cstdio>#include<string>usingnamespaces......
  • 查找nginx路径
    1.查找nginxwhichnginx输出/usr/local/bin/nginx2.查找nginx配置文件/usr/local/bin/nginx-t#检测配置是否正确,同时可以输出配置文件路径输出:nginx......