查找的数据结构实验报告（哈希表）

一、实验目的：

二、实验内容（实验题目与说明）

三、算法设计（核心代码或全部代码）

四、运行与测试（测试数据和实验结果分析）

五、总结与心得

一、实验目的：

(1)理解查找表的基本概念，定义、分类和各类的特点;

(2)掌握哈希表的构造方法以及解冲突的方法;

(3)掌握哈希存储和哈希查找的基本思想及有关方法。

二、实验内容（实验题目与说明）

使用哈希函数:H(K)=3K MOD 11

并采用链地址法处理冲突。试对关键字序列(22，41，53，46,30，13，01，67)构造哈希表，设计构造哈希表的完整算法去。

三、算法设计（核心代码或全部代码）

#include <stdio.h>

#include <stdlib.h>

#define MAX_SIZE 11

typedef struct Node {

    int key;

    struct Node* next;

} Node;

typedef struct HashTable {

    Node** data;

    int size;

} HashTable;

HashTable* initHashTable(int size) {

    HashTable* hashTable = (HashTable*)malloc(sizeof(HashTable));

    hashTable->size = size;

    hashTable->data = (Node**)malloc(sizeof(Node*) * size);

    for (int i = 0; i < size; i++) {

        hashTable->data[i] = NULL;

    }

    return hashTable;

}

// 计算哈希值

int hash(int key) {

    return 3 * key % MAX_SIZE;

}

// 向哈希表中插入关键字

void insert(HashTable* hashTable, int key) {

    int position = hash(key); // 计算哈希值

    Node* node = (Node*)malloc(sizeof(Node)); // 创建新节点

    node->key = key;

    node->next = NULL;

    if (hashTable->data[position] == NULL) { // 插入新节点

        hashTable->data[position] = node;

    } else {

        Node* p = hashTable->data[position];

        while (p->next != NULL) {

            p = p->next;

        }

        p->next = node;

    }

}

// 在哈希表中查找关键字

int search(HashTable* hashTable, int key) {

    int position = hash(key); // 计算哈希值

    Node* p = hashTable->data[position];

    while (p != NULL) { // 遍历链表

        if (p->key == key) {

            return position; // 返回位置

        }

        p = p->next;

    }

    return -1; // 没有找到返回-1

}

int main() {

    int keys[] = {22, 41, 53, 46, 30, 13, 1, 67};

    int size = sizeof(keys) / sizeof(int);

    // 构造哈希表

    HashTable* hashTable = initHashTable(MAX_SIZE);

    for (int i = 0; i < size; i++) {

        insert(hashTable, keys[i]);

    }

    // 查找关键字

    printf("输入要查找的关键字: ");

    int key;

    scanf("%d", &key);

    int position = search(hashTable, key);

    if (position == -1) {

        printf("没有找到该关键字\n");

    } else {

        printf("该关键字在哈希表中的位置为: %d\n", position);

    }

    return 0;

}

四、运行与测试（测试数据和实验结果分析）

先定义了哈希节点结构体 Node 和哈希表结构体 HashTable。然后使用 initHashTable 函数初始化哈希表，并使用 hash 函数计算哈希值。使用 insert 函数向哈希表中插入关键字，并使用 search 函数在哈希表中查找关键字。最后，我们在 main 函数中构造哈希表并进行关键字查找。