2、哈希表的构造与查找 #include <stdio.h> #include <stdlib.h> #define m 13 #define NULLKEY 0 typedef int KeyType; /* 假设关键字为整型 */ typedef struct { KeyType key; }RecordType; typedef RecordType HashTable[m]; int hash(KeyType k) { int h; h = k%m; return h; } int HashSearch( HashTable ht, KeyType K) { int h0; int i; int hi; h0=hash(K); if (ht[h0].key==NULLKEY) return (-1); else if (ht[h0].key==K) return (h0); else /* 用线性探测再散列解决冲突 */ { for (i=1; i<=m-1; i++) { hi=(h0+i) % m; if (ht[hi].key==NULLKEY) return (-1); else if (ht[hi].key==K) return (hi); } return (-1); } } int main() { int i,j; int n; int p; int hj; int k; int result; HashTable ht; for(i=0; i<m; i++) ht[i].key = NULLKEY; printf("请输入哈希表的元素个数:"); scanf("%d",&n); for(i=1; i<=n; i++) { printf("请输入第%d个元素:",i); fflush(stdin); scanf("%d",&p); j = hash(p); if (ht[j].key == NULLKEY) ht[j].key = p; else { for (i=1; i<=m-1; i++) { hj=(j+i) % m; if (ht[hj].key==NULLKEY) { ht[j].key = p; i = m; } } } } printf("请输入要查找的元素:"); fflush(stdin); scanf("%d",&k); result = HashSearch(ht,k); if(result == -1) printf("未找到!\n"); else printf("元素位置为%d\n",result); return 0; }

这段代码实现了一个基于哈希表的查找算法。其中，哈希表的大小为m，关键字为整型。哈希表中的每个元素是一个RecordType类型的结构体，其中只包含了一个整型关键字key。哈希函数hash(k)将关键字映射到哈希表中的一个位置，如果该位置已经被占用，则采用线性探测再散列的方法解决冲突。具体地，如果哈希表位置h0被占用，则依次检查h0+1, h0+2, ..., h0+m-1位置，找到第一个空位置或者关键字等于k的位置返回。如果找不到，则返回-1表示未找到。在main函数中，先读入哈希表的元素个数n和n个元素的值，然后读入要查找的元素k，最后调用HashSearch函数查找k在哈希表中的位置。如果找到，则返回对应位置的下标；否则返回-1表示未找到。

相关问题

STM32使用标准库建立哈希表，怎么清空哈希表

对于使用标准库建立的哈希表，清空哈希表可以采取以下步骤：

1. 遍历哈希表中的每个桶，将每个桶的链表或二叉树的节点全部删除。
2. 将哈希表的元素数量重置为0。

以下是一个示例代码，演示如何清空哈希表：

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

// 假设哈希表中的节点是链表节点
typedef struct ListNode {
    int key;
    int value;
    struct ListNode* next;
} ListNode;

// 假设哈希表有16个桶
#define BUCKET_SIZE 16

typedef struct HashTable {
    ListNode* buckets[BUCKET_SIZE];
    int count;
} HashTable;

// 初始化哈希表
void initHashTable(HashTable* table) {
    for (int i = 0; i < BUCKET_SIZE; i++) {
        table->buckets[i] = NULL;
    }
    table->count = 0;
}

// 清空哈希表
void clearHashTable(HashTable* table) {
    for (int i = 0; i < BUCKET_SIZE; i++) {
        ListNode* node = table->buckets[i];
        while (node != NULL) {
            ListNode* temp = node;
            node = node->next;
            free(temp);
        }
        table->buckets[i] = NULL;
    }
    table->count = 0;
}

// 其他操作...

int main() {
    HashTable table;
    initHashTable(&table);

    // 向哈希表中插入数据...

    // 清空哈希表
    clearHashTable(&table);

    return 0;
}

c语言哈希表的建立与查找

好的，下面是一个简单的哈希表实现，包括建立和查找操作。以下是示例代码：

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

#define MAX_SIZE 10

typedef struct _hash_node {
    char *key;
    int value;
    struct _hash_node *next;
} HashNode;

typedef struct _hash_table {
    HashNode *table[MAX_SIZE];
} HashTable;

unsigned int hash_function(const char *key) {
    unsigned int hash = 0;
    for (int i = 0; i < strlen(key); i++) {
        hash = hash * 31 + key[i];
    }
    return hash % MAX_SIZE;
}

HashNode *create_node(const char *key, int value) {
    HashNode *new_node = (HashNode *) malloc(sizeof(HashNode));
    new_node->key = strdup(key);
    new_node->value = value;
    new_node->next = NULL;
    return new_node;
}

void insert(HashTable *hash_table, const char *key, int value) {
    unsigned int hash = hash_function(key);
    HashNode *node = hash_table->table[hash];
    while (node != NULL) {
        if (strcmp(node->key, key) == 0) {
            node->value = value;  // replace value
            return;
        }
        node = node->next;
    }
    HashNode *new_node = create_node(key, value);
    new_node->next = hash_table->table[hash];
    hash_table->table[hash] = new_node;
}

int get(HashTable *hash_table, const char *key) {
    unsigned int hash = hash_function(key);
    HashNode *node = hash_table->table[hash];
    while (node != NULL) {
        if (strcmp(node->key, key) == 0) {
            return node->value;
        }
        node = node->next;
    }
    return -1;  // key not found
}

int main() {
    HashTable hash_table;
    memset(&hash_table, 0, sizeof(HashTable));
    insert(&hash_table, "apple", 1);
    insert(&hash_table, "banana", 2);
    insert(&hash_table, "orange", 3);

    printf("%d\n", get(&hash_table, "apple"));  // 输出 1
    printf("%d\n", get(&hash_table, "banana"));  // 输出 2
    printf("%d\n", get(&hash_table, "orange"));  // 输出 3
    printf("%d\n", get(&hash_table, "watermelon"));  // 输出 -1
    return 0;
}

在上面的代码中，我们使用哈希函数将键映射到哈希表中的索引位置，然后使用链表方法解决哈希冲突。`create_node`函数用于创建哈希表中的节点，`insert`函数用于将键和值插入哈希表中，如果哈希表中已经存在该键，则更新其对应的值；`get`函数用于根据键查找哈希表中的值。

注意：在实际使用中，我们需要处理哈希冲突，这里使用了链表法，可以有效地解决冲突问题。

下面是一个使用示例：

1
2
3
-1

在上面的示例中，我们创建了一个哈希表，并向其中插入了三个键值对。然后我们使用`get`函数来查找键对应的值。如果键不存在于哈希表中，则返回-1。