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表示未找到。

相关问题

2、基于哈希表的顺序存储表示，采用哈希函数H(key) = key MOD p，其中 MOD表示取余运算，并用线性 探测再散列法处理冲突。编程实现哈希表的下列基本操作。 （1）构造哈希表 （2）哈希表的查找 （3）哈希表的插入用C语言写

在C语言中，我们可以使用数组（作为底层的顺序存储结构）和链表（解决哈希碰撞）来实现基于哈希表的操作。这里我会提供一个简化的示例：

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

#define TABLE_SIZE 1000 // 哈希表大小
typedef struct Entry {
    int key;
    int value; // 存放元素值
    struct Entry* next; // 链表节点，用于处理哈希冲突
} Node;

// 哈希函数
int hash_function(int key) {
    return key % TABLE_SIZE;
}

// 线性探测再散列
Node* linear_probe(Node** table, int key) {
    Node* probe = table[hash_function(key)];
    while (probe != NULL && probe->key == key) {
        probe = probe->next; // 如果找到相同的键，则继续往后找
    }
    return probe;
}

// 构造哈希表
void createHashTable(Node** table) {
    for (int i = 0; i < TABLE_SIZE; ++i) {
        table[i] = NULL;
    }
}

// 查找
int searchHashTable(Node** table, int key) {
    Node* entry = linear_probe(table, key);
    if (entry == NULL) {
        return -1; // 没有找到
    } else {
        return entry->value; // 找到并返回对应值
    }
}

// 插入
void insertHashTable(Node** table, int key, int value) {
    Node* new_entry = (Node*)malloc(sizeof(Node));
    if (new_entry == NULL) {
        printf("Memory allocation failed.\n");
        return;
    }
    new_entry->key = key;
    new_entry->value = value;
    new_entry->next = linear_probe(table, key); // 如果已有该键，替换现有值

    if (new_entry->next == NULL) { // 如果链表为空，直接添加
        table[hash_function(key)] = new_entry;
    } else {
        // 否则将新节点添加到链表的末尾
        Node* current = table[hash_function(key)];
        while (current->next != NULL) {
            current = current->next;
        }
        current->next = new_entry;
    }
}

int main() {
    Node** table = (Node**)malloc(TABLE_SIZE * sizeof(Node*)); // 初始化哈希表

    // 创建、查找和插入示例
    createHashTable(table);
    insertHashTable(table, 5, 100);
    insertHashTable(table, 7, 200);
    
    int found_key = searchHashTable(table, 5);
    if (found_key != -1) {
        printf("Value for key 5 is: %d\n", found_key);
    }

    free(table); // 注意释放内存
    return 0;
}

这个示例展示了如何创建、查找和插入一个简单的基于哈希表的数据结构。请注意，这只是一个基础版本，实际应用中可能需要考虑更多的优化，比如负载因子、动态扩容等。

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;
}