C语言编写一个函数,用哈希函数将一个字符串转换成一个整型数组的下标。这个怎么写
时间: 2024-05-04 17:16:00 浏览: 16
可以使用简单的取余算法,将字符串转换成一个整数,再对数组长度进行取余来得到对应的数组下标。例如:
```c
unsigned int hash_function(char* str, int array_size){
unsigned int hash = 0;
int c;
while ((c = *str++)){
hash = c + (hash << 6) + (hash << 16) - hash; //DJB Hash算法
}
return hash % array_size; //取余得到数组下标
}
```
这个函数用DJB Hash算法将字符串转换成一个32位的无符号整数,再将该整数对数组长度取余得到对应的下标。
相关问题
c语言 编写一个函数,功能是寻找数组中出现次数最多的元素
好的,这里提供一种使用哈希表来寻找数组中出现次数最多的元素的 C 语言函数:
```c
int find_most_frequent_element(int arr[], int len) {
// 初始化一个哈希表
int max_count = 0, max_element = arr[0];
int hash_table[1000] = {0}; // 假设数组元素非负且小于1000
// 统计每个元素出现的次数
for (int i = 0; i < len; i++) {
hash_table[arr[i]]++;
// 更新出现次数最多的元素
if (hash_table[arr[i]] > max_count) {
max_count = hash_table[arr[i]];
max_element = arr[i];
}
}
return max_element;
}
```
这个函数同样接收一个整数数组 `arr` 和它的长度 `len`。它会使用一个哈希表来统计每个元素出现的次数。遍历整个数组后,函数会返回出现次数最多的元素。
这个函数的时间复杂度为 O(n),比前一个函数更高效。但是需要注意的是,哈希表的大小需要根据数组元素的取值范围来确定,如果数组元素的取值范围比较大,可能会导致哈希表过大,从而影响程序的性能。
c语言使用查找表实现给定两个数组,编写一个函数来计算它们的交集
要使用查找表实现给定两个数组的交集,可以使用哈希表来记录数组中的元素,并比较两个数组中的元素是否存在于哈希表中。以下是使用C语言实现的示例代码:
```c
#include <stdio.h>
#include <stdlib.h>
// 定义哈希表结点结构
struct HashNode {
int key;
struct HashNode* next;
};
// 初始化哈希表
struct HashNode** initHashTable(int size) {
struct HashNode** hashTable = (struct HashNode**)malloc(size * sizeof(struct HashNode*));
for (int i = 0; i < size; i++) {
hashTable[i] = NULL;
}
return hashTable;
}
// 哈希函数
int hash(int key, int size) {
return abs(key) % size;
}
// 插入哈希表
void insert(struct HashNode** hashTable, int key, int size) {
int index = hash(key, size);
struct HashNode* newNode = (struct HashNode*)malloc(sizeof(struct HashNode));
newNode->key = key;
newNode->next = NULL;
if (hashTable[index] == NULL) {
hashTable[index] = newNode;
} else {
struct HashNode* currentNode = hashTable[index];
while (currentNode->next != NULL) {
currentNode = currentNode->next;
}
currentNode->next = newNode;
}
}
// 判断元素是否存在于哈希表中
int contains(struct HashNode** hashTable, int key, int size) {
int index = hash(key, size);
struct HashNode* currentNode = hashTable[index];
while (currentNode != NULL) {
if (currentNode->key == key) {
return 1;
}
currentNode = currentNode->next;
}
return 0;
}
// 释放哈希表内存
void freeHashTable(struct HashNode** hashTable, int size) {
for (int i = 0; i < size; i++) {
struct HashNode* currentNode = hashTable[i];
while (currentNode != NULL) {
struct HashNode* temp = currentNode;
currentNode = currentNode->next;
free(temp);
}
}
free(hashTable);
}
// 计算数组的交集
int* intersect(int* nums1, int nums1Size, int* nums2, int nums2Size, int* returnSize) {
// 确定较小的数组作为哈希表大小
int size = nums1Size > nums2Size ? nums2Size : nums1Size;
// 初始化两个哈希表
struct HashNode** hashTable1 = initHashTable(size);
struct HashNode** hashTable2 = initHashTable(size);
// 插入第一个数组的元素到哈希表1
for (int i = 0; i < nums1Size; i++) {
insert(hashTable1, nums1[i], size);
}
// 插入第二个数组的元素到哈希表2,并检查是否存在于哈希表1中
int* result = (int*)malloc(size * sizeof(int));
int resultIndex = 0;
for (int i = 0; i < nums2Size; i++) {
if (contains(hashTable1, nums2[i], size) && !contains(hashTable2, nums2[i], size)) {
result[resultIndex++] = nums2[i];
insert(hashTable2, nums2[i], size);
}
}
// 更新返回的数组长度
*returnSize = resultIndex;
// 释放哈希表内存
freeHashTable(hashTable1, size);
freeHashTable(hashTable2, size);
return result;
}
int main() {
int nums1[] = {1, 2, 2, 1};
int nums1Size = sizeof(nums1) / sizeof(nums1[0]);
int nums2[] = {2, 2};
int nums2Size = sizeof(nums2) / sizeof(nums2[0]);
int size;
int* result = intersect(nums1, nums1Size, nums2, nums2Size, &size);
printf("交集:");
for (int i = 0; i < size; i++) {
printf("%d ", result[i]);
}
free(result);
return 0;
}
```
以上是一个用C语言实现的示例代码,使用了哈希表来计算两个数组的交集。您可以根据自己的需求进行修改和使用。希望对您有帮助!如有任何疑问,请随时追问。