实现哈希表的构造和查找算法,要求:用除留余数法构造哈希函数,用链地址法解决冲突。c语言

为了实现哈希表的构造和查找算法，我们需要遵循以下步骤：

1. 定义哈希表的结构体，包括哈希表的大小、每个元素的结构体等信息。
2. 定义哈希函数，这里我们使用除留余数法构造哈希函数。
3. 定义链表结构体，用于解决哈希冲突。
4. 定义插入函数，将元素插入到哈希表中。
5. 定义查找函数，根据关键字查找元素。

下面是C语言的实现代码：

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

#define MAX_SIZE 30 // 哈希表的大小

// 定义哈希表元素的结构体
typedef struct {
    char name[20]; // 姓名
} Element;

// 定义哈希表的结构体
typedef struct {
    Element *data[MAX_SIZE]; // 哈希表的数据
    int count; // 哈希表中元素的数量
} HashTable;

// 定义链表结构体
typedef struct _Node {
    Element *data; // 链表中的数据
    struct _Node *next; // 链表的下一个节点
} Node;

// 定义哈希函数
int hash(char *name) {
    int sum = 0;
    for (int i = 0; i < strlen(name); i++) {
        sum += name[i];
    }
    return sum % MAX_SIZE;
}

// 定义插入函数
void insert(HashTable *hashTable, Element *element) {
    int index = hash(element->name);
    if (hashTable->data[index] == NULL) {
        // 如果该位置为空，则直接插入元素
        hashTable->data[index] = element;
    } else {
        // 如果该位置不为空，则使用链表解决冲突
        Node *node = (Node *)malloc(sizeof(Node));
        node->data = element;
        node->next = NULL;
        Node *p = hashTable->data[index];
        while (p->next != NULL) {
            p = p->next;
        }
        p->next = node;
    }
    hashTable->count++;
}

// 定义查找函数
Element *search(HashTable *hashTable, char *name) {
    int index = hash(name);
    if (hashTable->data[index] == NULL) {
        // 如果该位置为空，则说明元素不存在
        return NULL;
    } else {
        // 如果该位置不为空，则使用链表查找元素
        Node *p = hashTable->data[index];
        while (p != NULL) {
            if (strcmp(p->data->name, name) == 0) {
                return p->data;
            }
            p = p->next;
        }
        // 如果链表中没有找到元素，则说明元素不存在
        return NULL;
    }
}

int main() {
    // 初始化哈希表
    HashTable *hashTable = (HashTable *)malloc(sizeof(HashTable));
    hashTable->count = 0;
    for (int i = 0; i < MAX_SIZE; i++) {
        hashTable->data[i] = NULL;
    }

    // 插入元素
    Element *element1 = (Element *)malloc(sizeof(Element));
    strcpy(element1->name, "Tom");
    insert(hashTable, element1);

    Element *element2 = (Element *)malloc(sizeof(Element));
    strcpy(element2->name, "Jerry");
    insert(hashTable, element2);

    // 查找元素
    Element *result = search(hashTable, "Tom");
    if (result != NULL) {
        printf("找到了元素：%s\n", result->name);
    } else {
        printf("没有找到元素\n");
    }

    // 释放内存
    free(element1);
    free(element2);
    free(hashTable);

    return 0;
}