C语言 链表 使用BKDRHash 如何遍历呢

遍历链表的基本方法是使用指针，从链表的头节点开始依次遍历每个节点，直到遍历到链表的尾节点为止。使用BKDRHash的方法可以将链表中的每个节点以哈希表的形式组织起来，这样可以更加高效地查找和访问链表中的节点。

遍历使用BKDRHash组织的链表时，需要先定位到哈希表中相应的桶，然后依次访问桶中的每个节点即可。具体的实现方法可以参考下面的代码示例：

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

#define HASH_SIZE 10000

// 定义链表节点的结构体
typedef struct ListNode {
    char* key;
    char* value;
    struct ListNode* next;
} ListNode;

// 定义哈希表的结构体
typedef struct HashTable {
    ListNode* buckets[HASH_SIZE];
} HashTable;

// 计算字符串的哈希值
unsigned int BKDRHash(char* str) {
    unsigned int seed = 131; // 31、33、131、137、65537等常用的哈希种子
    unsigned int hash = 0;
    while (*str) {
        hash = hash * seed + (*str++);
    }
    return hash % HASH_SIZE;
}

// 添加节点到哈希表中
void HashTablePut(HashTable* table, char* key, char* value) {
    unsigned int hash = BKDRHash(key);
    ListNode* node = table->buckets[hash];
    while (node) {
        if (strcmp(node->key, key) == 0) {
            // 如果key已经存在，则更新value
            free(node->value);
            node->value = strdup(value);
            return;
        }
        node = node->next;
    }
    // 如果key不存在，则创建新节点并插入到桶中
    node = (ListNode*)malloc(sizeof(ListNode));
    node->key = strdup(key);
    node->value = strdup(value);
    node->next = table->buckets[hash];
    table->buckets[hash] = node;
}

// 根据key查找节点的value
char* HashTableGet(HashTable* table, char* key) {
    unsigned int hash = BKDRHash(key);
    ListNode* node = table->buckets[hash];
    while (node) {
        if (strcmp(node->key, key) == 0) {
            return node->value;
        }
        node = node->next;
    }
    return NULL;
}

// 遍历哈希表中的节点
void HashTableTraverse(HashTable* table) {
    for (int i = 0; i < HASH_SIZE; i++) {
        ListNode* node = table->buckets[i];
        while (node) {
            printf("%s:%s\n", node->key, node->value);
            node = node->next;
        }
    }
}

// 释放哈希表中的所有节点
void HashTableFree(HashTable* table) {
    for (int i = 0; i < HASH_SIZE; i++) {
        ListNode* node = table->buckets[i];
        while (node) {
            ListNode* next = node->next;
            free(node->key);
            free(node->value);
            free(node);
            node = next;
        }
        table->buckets[i] = NULL;
    }
}

int main() {
    HashTable table = {0};
    // 添加节点
    HashTablePut(&table, "apple", "red");
    HashTablePut(&table, "banana", "yellow");
    HashTablePut(&table, "orange", "orange");
    HashTablePut(&table, "grape", "purple");

    // 遍历节点
    HashTableTraverse(&table);

    // 查找节点
    printf("%s\n", HashTableGet(&table, "apple"));

    // 释放节点
    HashTableFree(&table);

    return 0;
}

这个示例程序实现了一个使用BKDRHash组织的哈希表，使用了链表节点结构体和哈希表结构体，以及相关的操作函数。在遍历哈希表时，使用了两个嵌套的while循环，依次遍历哈希表中的桶和桶中的节点，然后输出每个节点的key和value。