三分查找
应用场景:求下列一元二次函数的极大值
\[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;
}
哈希表(散列表)
哈希表查找:
- 哈希函数:BKDRHash
- 冲突处理方法:拉链法
本质是通过“哈希函数”建立“索引”
#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