1. Toy模板网首页
  2. > Toy博客

【数据结构与算法】哈希表设计（C\C++）

10月前 作者：hiddenSharp429 分类：Toy博客 阅读(53) 违法举报

这篇具有很好参考价值的文章主要介绍了【数据结构与算法】哈希表设计（C\C++）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

实践要求

1. 问题描述

针对某个集体中人名设计一个哈希表，使得平均查找长度不超过R，并完成相应的建表和查找程序。

2. 基本要求

假设人名为中国人姓名的汉语拼音形式。待填入哈希表的人名共有30个，取平均查找长度的上限为2。哈希函数用除留余数法构造。用伪随机探测再散列法处理冲突。

3. 测试数据

取读者周围较熟悉的30个人的姓名拼音。

4. 实现提示

如果随机函数自行构造，则应首先调整好随机函数，使其分布均匀。人名的长度均不超过度20个字符。字符的取码方法可直接利用PASCAL语言中的ord函数。可先对过长的人名作折叠处理。

5. 选作内容

  1. 从教科书上介绍的几种哈希函数构造方法中选出适用者并设计几个不同的哈希函数，比较它们的地址冲突率(可以用更大的名字集合作试验)。
  2. 研究这30个人名的特点，努力找一个哈希函数，使得对于不同的拼音名一定不发生地址冲突。
  3. 在哈希函数确定的前题下尝试各种不同处理冲突的方法，考查平均查找长度的变化和造好的哈希表中关键字的聚簇性。

实践报告

1. 题目分析

说明程序设计的任务，强调的是程序要做什么，此外列出各成员分工

程序设计任务：
针对某个集体中人名设计一个哈希表，使得平均查找长度不超过R，并完成相应的建表和查找程序。假设人名为中国人姓名的汉语拼音形式。待填入哈希表的人名共有30个，取平均查找长度的上限为2。哈希函数用除留余数法构造。用伪随机探测再散列法处理冲突。

2. 数据结构设计

说明程序用到的数据结构的定义，主程序的流程及各模块之间的层次关系

该程序主要用到的数据结构是自定义的哈希表，该数据结构包含以下成员：

  1. Person: 人名节点结构体，包含一个 name 字符数组用于存储人名。

  2. HashTable: 哈希表结构体，包含以下成员：

    成员名称 解释
    data 一个 Person 类型的指针，用于存储哈希表中的数据。
    flags 一个整数数组，用于标记哈希表中的位置是否为空。当一个位置有 人名时，对应位置的标记为1；否则，标记为0。
    size 哈希表的大小，表示哈希表可以容纳的最大元素数量。

主程序流程图

3. 程序设计

实现概要设计中的数据类型，对主程序、模块及主要操作写出伪代码，画出函数的调用关系

各模块伪代码

初始化哈希表
// 初始化哈希表
void initHashTable(HashTable *table, int size)
{
    // 为哈希表分配空间
    // 为标记数组分配空间
    // 设置哈希表的大小
    for (int i = 0; i < size; i++)
    {
    // 初始化人名为空
    // 初始化标记数组为0
    }
}
除留余数法
// 哈希函数：除留余数法
int hashFunction(char *name, int size)
{
    int sum = 0;
    for (int i = 0; i < strlen(name); i++)
    {
        // 将人名中每个字符的ASCII码相加
    }
    return sum % size;
}
插入人名到哈希表中
// 插入人名到哈希表中
void insertName(HashTable *table, char *name)
{
    // 计算人名在哈希表中的位置
    int i = 0;
    // 记录发生冲突的次数
    while // 人名发生冲突
    {
        // 发生冲突时，使用伪随机探测再散列法处理
    }
    // 将人名填入哈希表中
    // 标记数组中的位置为1，表示该位置已经有人名
}
查找人名在哈希表中
// 查找人名在哈希表中的位置
int findName(HashTable *table, char *name)
{
    // 计算人名在哈希表中的位置
    int i = 0;
    while // 人名发生冲突
    {
        if// 比较人名是否相同
        {
            return index; // 找到了人名，返回索引位置
        }
        // 发生冲突时，使用伪随机探测再散列法处理
    }
    return NOT_FOUND; // 未找到人名
}

各函数层次关系图

4. 调试分析

程序复杂度分析

1. 空间复杂度
时间复杂度：

  1. 初始化哈希表时间复杂度为 O ( s i z e ) O(size) O(size)
    注：其中 size 是哈希表的大小。
  2. 插入人名到哈希表中的时间复杂度
    平均情况下 O ( 1 ) ，最坏情况下为 O ( s i z e ) 平均情况下O(1)，最坏情况下为 O(size) 平均情况下O(1)，最坏情况下为O(size)
    这是因为哈希函数的散列操作通常具有 O(1) 的复杂度，但在发生冲突时可能需要执行一系列探测再散列操作，导致最坏情况下的复杂度为 O(size)。
  3. 查找人名在哈希表中的位置的时间复杂度
    平均情况下为 O ( 1 ) ，最坏情况下为 O ( s i z e ) 平均情况下为 O(1)，最坏情况下为 O(size) 平均情况下为O(1)，最坏情况下为O(size)
    与插入操作类似，平均情况下的复杂度是常数级别，但最坏情况下需要遍历整个哈希表才能找到人名或确定其不存在。

2. 时间复杂度
O ( s i z e ) O(size) O(size)
哈希表数据和标记数组：O(size)，其中 size 是哈希表的大小。哈希表数据占用的空间是 O(size)，标记数组占用的空间也是 O(size)。

心得体会

使用链表要注意不能使用空指针，不能使用指向未知内存的指针，以及用完指针后要及时释放。否则就会碰到一些莫名其妙的错误。

5. 测试结果

列出测试结果，包括输入和输出

测试结果

测试结果说明：
输入姓名集里面的姓名，
将会输出该姓名在哈希表中的位置。

input

chenxinxin

output

Found at index 47

哈希表的构造与使用实验报告csdn,算法与数据结构,C/C++,散列表,c语言,c++

6. 用户使用说明

给出主界面及主要功能界面

使用说明

用户运行程序后系统会自动打印各个姓名插入到哈希表中冲突的次数，随后可以输入姓名集合里面的的一个姓名，系统会输出其在哈希表中的位置。
注：姓名集是在源文件中一直写进去的，而不是txt或者文档读入的，故若想修改姓名集合，则需要重写main函数里面的数组。

7. 选作内容

实现了(1),(2),(3)

7.1 (1)的实现

从教科书上介绍的几种哈希函数构造方法中选出适用者并设计几个不同的哈希函数，比较它们的地址冲突率(可以用更大的名字集合作试验)。

解：将书本上的平方去中法与上述的除留取余法进行地址冲突比较，发现平方去中法的冲突率非常高，达到了31.22%。

除留余数法
除留余数法
总冲突次数:12
平均冲突次数:0.4
冲突率:0.013333
哈希表的构造与使用实验报告csdn,算法与数据结构,C/C++,散列表,c语言,c++

哈希表的构造与使用实验报告csdn,算法与数据结构,C/C++,散列表,c语言,c++

平方取中法
平方取中法
总冲突次数:281
平均冲突次数:9.366
冲突率:0.312222

哈希表的构造与使用实验报告csdn,算法与数据结构,C/C++,散列表,c语言,c++
哈希表的构造与使用实验报告csdn,算法与数据结构,C/C++,散列表,c语言,c++

7.2 (2)的实现

研究这30个人名的特点，努力找一个哈希函数，使得对于不同的拼音名一定不发生地址冲突。

解：根据以下名字集合，总结了三个特点，针对这三个特点实现了一个自定义哈希函数。

//名字集合
"chencaiyi", "chenxinxin", "fangsongjie", "huangjiawei", "huangjunlin", "leiyang",
"luwei", "wangzhanqi", "wuweidong", "longjiajing", "huangweiqin", "chenshangming", "huangtao",
"maixupeng", "chenying", "liujunhui", "chenqingdong", "guoziming", "chenyilong", "libaiyang", "liangdeguang",
"zhangyuxing", "huangyibin", "liuwenlong", "zengzihao", "wangshulian", "zhuzixian", "lidingkun", "caofu", "yuemingju"
  1. 大多数名字遵循“姓+名”或“姓+中间名+名字”的模式。
  2. 有些名字有重复的字符，如chencaiyi,chenxinxni,huangjunlin。
  3. 名称的长度各不相同，从 5 到 12 个字符不等。

因此设计了一个自定义哈希函数，函数如下

// 哈希函数：自定义哈希函数
int hashFunction(char *name, int size)
{
    int hash = 0;
    int nameLength = strlen(name);
    for (int i = 0; i < nameLength; i++)
    {
        hash = (hash * 31 + name[i]) % size;
    }
    return hash;
}

7.3 (3)的实现

在哈希函数确定的前题下尝试各种不同处理冲突的方法，考查平均查找长度的变化和造好的哈希表中关键字的聚簇性。

解：在确定使用（2）所说的自定义哈希函数后，将采用单独链接法来处理冲突的情况。

单独链接法：在此方法中，哈希表中的每个插槽都包含一个链表或其他数据结构，用于存储散列到同一索引的多个元素。发生冲突时，新元素将添加到该索引处的链接列表中。要搜索元素，请在相应的索引处遍历链表，直到找到匹配项。

下面是改动最大的函数findName。

// 查找人名在哈希表中的位置
int findName(HashTable *table, char *name)
{
    int index = hashFunction(name, table->size); // 计算人名在哈希表中的位置
    // 遍历链表查找人名
    PersonNode *currentNode = table->data[index];
    while (currentNode != NULL)
    {
        if (strcmp(currentNode->name, name) == 0)
        {
            return index; // 找到了人名，返回索引位置
        }
        currentNode = currentNode->next;
    }
    return NOT_FOUND; // 未找到人名
}

8. 附录

附录说明：
一共有四个.cpp文件，分别为HashMap.cpp、HashMap(1).cpp、HashMap(2).cpp、HashMap(3).cpp 。

源程序文件清单:
HashMap.cpp ：使用求留取余法的哈希表。
HashMap(1).cpp ：使用平方取中法的哈希表。
HashMap(2).cpp ：使用自定义哈希方法来改善求留取余法的哈希表。
HashMap(3).cpp ：使用单链接法来处理冲突情况来改善HashMap(2).cpp中的程序。

9. 全部代码

HashMap.cpp

/*
 * @Author: hiddenSharp429 z404878860@163.com
 * @Date: 2023-06-13 16:38:25
 * @LastEditors: hiddenSharp429 z404878860@163.com
 * @LastEditTime: 2023-06-14 17:28:58
 * @FilePath: \appe:\C OR C++\code\HashMap.cpp
 * @Description: 这是默认设置,请设置`customMade`, 打开koroFileHeader查看配置 进行设置: https://github.com/OBKoro1/koro1FileHeader/wiki/%E9%85%8D%E7%BD%AE
 */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define HashTABLE_SIZE 61  // 哈希表的大小，选择一个较大的素数
#define MAX_NAME_LENGTH 20 // 人名的最大长度
#define NOT_FOUND -1       // 未找到的标志

typedef struct
{
    char name[MAX_NAME_LENGTH]; // 人名
} Person;

typedef struct
{
    Person *data; // 哈希表的数据
    int *flags;   // 标记哈希表中的位置是否为空
    int size;     // 哈希表的大小
} HashTable;

// 哈希函数：除留余数法
int hashFunction(char *name, int size)
{
    int sum = 0;
    for (int i = 0; i < strlen(name); i++)
    {
        sum += name[i]; // 将人名中每个字符的ASCII码相加
    }
    return sum % size;
}

// 初始化哈希表
void initHashTable(HashTable *table, int size)
{
    table->data = (Person *)malloc(sizeof(Person) * size); // 为哈希表分配空间
    table->flags = (int *)malloc(sizeof(int) * size);      // 为标记数组分配空间
    table->size = size;                                    // 设置哈希表的大小
    for (int i = 0; i < size; i++)
    {
        strcpy(table->data[i].name, ""); // 初始化人名为空
        table->flags[i] = 0;             // 初始化标记数组为0
    }
}
// 插入人名到哈希表中
void insertName(HashTable *table, char *name)
{
    int index = hashFunction(name, table->size); // 计算人名在哈希表中的位置
    int i = 0;
    int conflicts = 0;               // 记录发生冲突的次数
    while (table->flags[index] == 1) // 人名发生冲突
    {
        // 发生冲突时，使用伪随机探测再散列法处理
        i++;
        index = (index + i * i) % table->size;
        conflicts++;
    }
    strcpy(table->data[index].name, name); // 将人名填入哈希表中
    table->flags[index] = 1;               // 标记数组中的位置为1，表示该位置已经有人名

    printf("Inserted %s with %d conflicts.\n", name, conflicts);
}

// 查找人名在哈希表中的位置
int findName(HashTable *table, char *name)
{
    int index = hashFunction(name, table->size); // 计算人名在哈希表中的位置
    int i = 0;
    while (table->flags[index] != 0) // 人名发生冲突
    {
        if (strcmp(table->data[index].name, name) == 0) // 比较人名是否相同
        {
            return index; // 找到了人名，返回索引位置
        }
        i++;
        index = (index + i * i) % table->size; // 发生冲突时，使用伪随机探测再散列法处理
    }
    return NOT_FOUND; // 未找到人名
}

int main()
{
    HashTable table;
    initHashTable(&table, HashTABLE_SIZE); // 初始化哈希表

    // 待填入哈希表的人名
    char names[30][MAX_NAME_LENGTH] = {
        "chencaiyi", "chenxinxin", "fangsongjie", "huangjiawei", "huangjunlin", "leiyang",
        "luwei", "wangzhanqi", "wuweidong", "longjiajing", "huangweiqin", "chenshangming", "huangtao",
        "maixupeng", "chenying", "liujunhui", "chenqingdong", "guoziming", "chenyilong", "libaiyang", "liangdeguang",
        "zhangyuxing", "huangyibin", "liuwenlong", "zengzihao", "wangshulian", "zhuzixian", "lidingkun", "caofu", "yuemingju"};

    // 建立哈希表
    for (int i = 0; i < 30; i++)
    {
        insertName(&table, names[i]);
    }

    // 查找程序
    char searchName[MAX_NAME_LENGTH];
    printf("Enter a name to search: "); // 输入要查找的人名
    scanf("%s", searchName);            // 读取人名

    int index = findName(&table, searchName); // 查找人名在哈希表中的位置
    if (index != NOT_FOUND)                   // 找到了人名
    {
        printf("Found at index %d\n", index);
    }
    else // 未找到人名
    {
        printf("Not found\n");
    }

    return 0;
}

HashMap(1).cpp

/*
 * @Author: hiddenSharp429 z404878860@163.com
 * @Date: 2023-06-14 17:27:57
 * @LastEditors: hiddenSharp429 z404878860@163.com
 * @LastEditTime: 2023-06-14 17:28:14
 * @FilePath: \appe:\C OR C++\code\HashMap(1).cpp
 * @Description: 这是默认设置,请设置`customMade`, 打开koroFileHeader查看配置 进行设置: https://github.com/OBKoro1/koro1FileHeader/wiki/%E9%85%8D%E7%BD%AE
 */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define HashTABLE_SIZE 61  // 哈希表的大小，选择一个较大的素数
#define MAX_NAME_LENGTH 20 // 人名的最大长度
#define NOT_FOUND -1       // 未找到的标志

typedef struct
{
    char name[MAX_NAME_LENGTH]; // 人名
} Person;

typedef struct
{
    Person *data; // 哈希表的数据
    int *flags;   // 标记哈希表中的位置是否为空
    int size;     // 哈希表的大小
} HashTable;

// 哈希函数：平方取中法
int hashFunction(char *name, int size)
{
    int nameLength = strlen(name);
    int square = nameLength * nameLength;
    int midDigits = (square / 100) % 100; // 取中间两位数

    return midDigits % size;
}

// 初始化哈希表
void initHashTable(HashTable *table, int size)
{
    table->data = (Person *)malloc(sizeof(Person) * size); // 为哈希表分配空间
    table->flags = (int *)malloc(sizeof(int) * size);      // 为标记数组分配空间
    table->size = size;                                    // 设置哈希表的大小
    for (int i = 0; i < size; i++)
    {
        strcpy(table->data[i].name, ""); // 初始化人名为空
        table->flags[i] = 0;             // 初始化标记数组为0
    }
}

// 插入人名到哈希表中
void insertName(HashTable *table, char *name)
{
    int index = hashFunction(name, table->size); // 计算人名在哈希表中的位置
    int i = 0;
    int conflicts = 0; // 记录发生冲突的次数
    while (table->flags[index] == 1) // 人名发生冲突
    {
        // 发生冲突时，使用平方探测再散列法处理
        i++;
        index = (index + i * i) % table->size;
        conflicts++;
    }
    strcpy(table->data[index].name, name); // 将人名填入哈希表中
    table->flags[index] = 1;               // 标记数组中的位置为1，表示该位置已经有人名

    printf("Inserted %s with %d conflicts.\n", name, conflicts);
}

// 查找人名在哈希表中的位置
int findName(HashTable *table, char *name)
{
    int index = hashFunction(name, table->size); // 计算人名在哈希表中的位置
    int i = 0;
    while (table->flags[index] != 0) // 人名发生冲突
    {
        if (strcmp(table->data[index].name, name) == 0) // 比较人名是否相同
        {
            return index; // 找到了人名，返回索引位置
        }
        i++;
        index = (index + i * i) % table->size; // 发生冲突时，使用平方探测再散列法处理
    }
    return NOT_FOUND; // 未找到人名
}

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

    // 待填入哈希表的人名
    char names[30][MAX_NAME_LENGTH] = {
        "chencaiyi", "chenxinxin", "fangsongjie", "huangjiawei", "huangjunlin", "leiyang",
        "luwei", "wangzhanqi", "wuweidong", "longjiajing", "huangweiqin", "chenshangming", "huangtao",
        "maixupeng", "chenying", "liujunhui", "chenqingdong", "guoziming", "chenyilong", "libaiyang", "liangdeguang",
        "zhangyuxing", "huangyibin", "liuwenlong", "zengzihao", "wangshulian", "zhuzixian", "lidingkun", "caofu", "yuemingju"};

    // 建立哈希表
    for (int i = 0; i < 30; i++)
    {
        insertName(&table, names[i]);
    }

    // 查找程序
    char searchName[MAX_NAME_LENGTH];
    printf("Enter a name to search: ");
    scanf("%s", searchName);

    int index = findName(&table, searchName);
    if (index != NOT_FOUND)
    {
        printf("Found at index %d\n", index);
    }
    else
    {
        printf("Not found\n");
    }

    return 0;
}

HashMap(2).cpp

/*
 * @Author: hiddenSharp429 z404878860@163.com
 * @Date: 2023-06-14 17:29:44
 * @LastEditors: hiddenSharp429 z404878860@163.com
 * @LastEditTime: 2023-06-14 17:45:38
 * @FilePath: \appe:\C OR C++\code\HashMap(2).cpp
 * @Description: 这是默认设置,请设置`customMade`, 打开koroFileHeader查看配置 进行设置: https://github.com/OBKoro1/koro1FileHeader/wiki/%E9%85%8D%E7%BD%AE
 */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define HashTABLE_SIZE 61  // 哈希表的大小，选择一个较大的素数
#define MAX_NAME_LENGTH 20 // 人名的最大长度
#define NOT_FOUND -1       // 未找到的标志

typedef struct
{
    char name[MAX_NAME_LENGTH]; // 人名
} Person;

typedef struct
{
    Person *data; // 哈希表的数据
    int *flags;   // 标记哈希表中的位置是否为空
    int size;     // 哈希表的大小
} HashTable;

// 哈希函数：自定义哈希函数
int hashFunction(char *name, int size)
{
    int hash = 0;
    int nameLength = strlen(name);

    for (int i = 0; i < nameLength; i++)
    {
        hash = (hash * 31 + name[i]) % size;
    }

    return hash;
}

// 初始化哈希表
void initHashTable(HashTable *table, int size)
{
    table->data = (Person *)malloc(sizeof(Person) * size); // 为哈希表分配空间
    table->flags = (int *)malloc(sizeof(int) * size);      // 为标记数组分配空间
    table->size = size;                                    // 设置哈希表的大小
    for (int i = 0; i < size; i++)
    {
        strcpy(table->data[i].name, ""); // 初始化人名为空
        table->flags[i] = 0;             // 初始化标记数组为0
    }
}

// 插入人名到哈希表中
void insertName(HashTable *table, char *name)
{
    int index = hashFunction(name, table->size); // 计算人名在哈希表中的位置
    int i = 0;
    int conflicts = 0; // 记录发生冲突的次数
    while (table->flags[index] == 1) // 人名发生冲突
    {
        // 发生冲突时，使用平方探测再散列法处理
        i++;
        index = (index + i * i) % table->size;
        conflicts++;
    }
    strcpy(table->data[index].name, name); // 将人名填入哈希表中
    table->flags[index] = 1;               // 标记数组中的位置为1，表示该位置已经有人名

    printf("Inserted %s with %d conflicts.\n", name, conflicts);
}

// 查找人名在哈希表中的位置
int findName(HashTable *table, char *name)
{
    int index = hashFunction(name, table->size); // 计算人名在哈希表中的位置
    int i = 0;
    while (table->flags[index] != 0) // 人名发生冲突
    {
        if (strcmp(table->data[index].name, name) == 0) // 比较人名是否相同
        {
            return index; // 找到了人名，返回索引位置
        }
        i++;
        index = (index + i * i) % table->size; // 发生冲突时，使用平方探测再散列法处理
    }
    return NOT_FOUND; // 未找到人名
}

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

    // 待填入哈希表的人名
    char names[30][MAX_NAME_LENGTH] = {
        "chencaiyi", "chenxinxin", "fangsongjie", "huangjiawei", "huangjunlin", "leiyang",
        "luwei", "wangzhanqi", "wuweidong", "longjiajing", "huangweiqin", "chenshangming", "huangtao",
        "maixupeng", "chenying", "liujunhui", "chenqingdong", "guoziming", "chenyilong", "libaiyang", "liangdeguang",
        "zhangyuxing", "huangyibin", "liuwenlong", "zengzihao", "wangshulian", "zhuzixian", "lidingkun", "caofu", "yuemingju"};

    // 建立哈希表
    for (int i = 0; i < 30; i++)
    {
        insertName(&table, names[i]);
    }

    // 查找程序
    char searchName[MAX_NAME_LENGTH];
    printf("Enter a name to search: ");
    scanf("%s", searchName);

    int index = findName(&table, searchName);
    if (index != NOT_FOUND)
    {
        printf("Found at index %d\n", index);
    }
    else
    {
        printf("Not found\n");
    }

    return 0;
}

HashMap(3).cpp

/*
 * @Author: hiddenSharp429 z404878860@163.com
 * @Date: 2023-06-14 17:28:46
 * @LastEditors: hiddenSharp429 z404878860@163.com
 * @LastEditTime: 2023-06-14 17:46:28
 * @FilePath: \appe:\C OR C++\code\HashMap(3).cpp
 * @Description: 这是默认设置,请设置`customMade`, 打开koroFileHeader查看配置 进行设置: https://github.com/OBKoro1/koro1FileHeader/wiki/%E9%85%8D%E7%BD%AE
 */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define HashTABLE_SIZE 61  // 哈希表的大小，选择一个较大的素数
#define MAX_NAME_LENGTH 20 // 人名的最大长度
#define NOT_FOUND -1       // 未找到的标志

typedef struct PersonNode
{
    char name[MAX_NAME_LENGTH]; // 人名
    struct PersonNode *next;    // 指向下一个节点的指针
} PersonNode;

typedef struct
{
    PersonNode **data; // 哈希表的数据
    int size;          // 哈希表的大小
} HashTable;

// 哈希函数：自定义哈希函数
int hashFunction(char *name, int size)
{
    int hash = 0;
    int nameLength = strlen(name);

    for (int i = 0; i < nameLength; i++)
    {
        hash = (hash * 31 + name[i]) % size;
    }

    return hash;
}

// 初始化哈希表
void initHashTable(HashTable *table, int size)
{
    table->data = (PersonNode **)malloc(sizeof(PersonNode *) * size); // 为哈希表分配空间
    table->size = size;                                               // 设置哈希表的大小
    for (int i = 0; i < size; i++)
    {
        table->data[i] = NULL; // 初始化每个槽位为空
    }
}

// 插入人名到哈希表中
void insertName(HashTable *table, char *name)
{
    int index = hashFunction(name, table->size); // 计算人名在哈希表中的位置

    // 创建新节点
    PersonNode *newNode = (PersonNode *)malloc(sizeof(PersonNode));
    strcpy(newNode->name, name);
    newNode->next = NULL;

    if (table->data[index] == NULL)
    {
        // 槽位为空，直接插入新节点
        table->data[index] = newNode;
    }
    else
    {
        // 槽位非空，遍历链表找到尾节点并插入新节点
        PersonNode *currentNode = table->data[index];
        while (currentNode->next != NULL)
        {
            currentNode = currentNode->next;
        }
        currentNode->next = newNode;
    }

    printf("Inserted %s\n", name);
}

// 查找人名在哈希表中的位置
int findName(HashTable *table, char *name)
{
    int index = hashFunction(name, table->size); // 计算人名在哈希表中的位置

    // 遍历链表查找人名
    PersonNode *currentNode = table->data[index];
    while (currentNode != NULL)
    {
        if (strcmp(currentNode->name, name) == 0)
        {
            return index; // 找到了人名，返回索引位置
        }
        currentNode = currentNode->next;
    }

    return NOT_FOUND; // 未找到人名
}

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

    // 待填入哈希表的人名
    char names[30][MAX_NAME_LENGTH] = {
        "chencaiyi", "chenxinxin", "fangsongjie", "huangjiawei", "huangjunlin", "leiyang",
        "luwei", "wangzhanqi", "wuweidong", "longjiajing", "huangweiqin", "chenshangming", "huangtao",
        "maixupeng", "chenying", "liujunhui", "chenqingdong", "guoziming", "chenyilong", "libaiyang", "liangdeguang",
        "zhangyuxing", "huangyibin", "liuwenlong", "zengzihao", "wangshulian", "zhuzixian", "lidingkun", "caofu", "yuemingju"};

    // 建立哈希表
    for (int i = 0; i < 30; i++)
    {
        insertName(&table, names[i]);
    }

    // 查找程序
    char searchName[MAX_NAME_LENGTH];
    printf("Enter a name to search: ");
    scanf("%s", searchName);

    int index = findName(&table, searchName);
    if (index != NOT_FOUND)
    {
        printf("Found at index %d\n", index);
    }
    else
    {
        printf("Not found\n");
    }

    return 0;
}

结束语

  因为是算法小菜，所以提供的方法和思路可能不是很好，请多多包涵~如果有疑问欢迎大家留言讨论，你如果觉得这篇文章对你有帮助可以给我一个免费的赞吗？我们之间的交流是我最大的动力！文章来源地址https://www.toymoban.com/news/detail-766379.html

到了这里，关于【数据结构与算法】哈希表设计（C\C++）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处： 如若内容造成侵权/违法违规/事实不符，请点击违法举报进行投诉反馈，一经查实，立即删除！

分享到：
领支付宝红包 赞助服务器费用

相关文章

  • 数据结构，查找算法（二分，分块，哈希）

    一、查找算法         1、二分查找：（前提条件： 必须有序的序列） 2、分块查找：（块间有序，块内无序）     索引表  +  源数据表     思路：     （1）先在索引表中确定在哪一块中     （2）再遍历这一块进行查找 //索引表 typedef  struct  {     int max; //块中最大值

    2024年02月11日
    浏览(60)
  • 【数据结构与算法】哈希—— 位图 | 布隆过滤器 | 哈希切割

    【数据结构与算法】哈希—— 位图 | 布隆过滤器 | 哈希切割

    🐱作者：一只大喵咪1201 🐱专栏：《数据结构与算法》 🔥格言： 你只管努力，剩下的交给时间！ 哈希是一种映射思想，这里再讲解两种应用哈希思想的数据结构。 问题： 给40亿个不重复的无符号整数，没排过序。给一个无符号整数，如何快速判断一个数是否在这40亿个数

    2024年02月02日
    浏览(57)
  • 【数据结构与算法——TypeScript】哈希表

    【数据结构与算法——TypeScript】哈希表

    哈希表介绍和特性 哈希表是一种非常重要的数据结构，但是很多学习编程的人一直搞不懂哈希表到底是如何实现的。 在这一章节中，我门就一点点来实现一个自己的哈希表。 通过实现来理解哈希表背后的原理和它的优势。 几乎所有的编程语言都有直接或者间接的应用这种数

    2024年02月13日
    浏览(42)
  • C++数据结构与算法——哈希表

    C++数据结构与算法——哈希表

    C++第二阶段——数据结构和算法，之前学过一点点数据结构，当时是基于Python来学习的，现在基于C++查漏补缺，尤其是树的部分。这一部分计划一个月，主要利用代码随想录来学习，刷题使用力扣网站，不定时更新，欢迎关注！ 给定两个字符串 s 和 t ，编写一个函数来判断

    2024年02月19日
    浏览(58)

  • 【数据结构实训】哈希表设计

    [问题描述] 针对某个集体中人名设计一个哈希表，使得平均查找长度不超过2，并完成相应的建表和查表程序。 [基本要求] 假设人名为中国人姓名的汉语拼音形式。待填入哈希表的人名共有30个，取平均查找长度的上限为2。哈希函数用除留余数法构造，用线性探测再散列法或

    2024年02月11日
    浏览(41)
  • 数据结构与算法 | 哈希表（Hash Table）

    数据结构与算法 | 哈希表（Hash Table）

    在二分搜索中提到了在有序集合中查询某个特定元素的时候，通过折半的方式进行搜索是一种很高效的算法。那能否根据特征直接定位元素，而非折半去查找？哈希表（Hash Table），也称为散列表，就是一种数据结构，用于实现键-值对的映射关系。它通过将键映射到特定的值

    2024年02月06日
    浏览(52)
  • 算法数据结构基础——哈希表（Hash Table）

    算法数据结构基础——哈希表（Hash Table）

    哈希表（Hash Table） ：也叫做散列表。是根据关键码值（Key Value）直接进行访问的数据结构。 哈希表通过「键 key 」和「映射函数 Hash(key) 」计算出对应的「值 value 」，把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做「哈希函数（散列函数

    2024年02月13日
    浏览(44)

  • 数据结构与算法 --顺序表的创建

    1. 顺序表（Sequence List）是一种线性表的实现方式，通过连续的内存空间存储元素，按照顺序排列。 顺序表的特点包括： 元素在内存中的存储是连续的，通过数组实现。 元素之间的逻辑顺序与物理顺序一致。 可以根据元素的索引直接访问和修改元素。 需要预先分配足够的内

    2024年03月26日
    浏览(50)
  • Python篇——数据结构与算法（第六部分：哈希表）

    Python篇——数据结构与算法（第六部分：哈希表）

      目录 1、直接寻址表 2、直接寻址表缺点 3、哈希 4、哈希表 5、解决哈希冲突 6、拉链法 7、常见哈希函数 8、哈希表的实现 8.1迭代器iter（）和__iter__ 8.2str（）和repr（） 8.3代码实现哈希表 8.4哈希表的应用   直接寻址表：key为k的元素放到k的位置上 改进直接寻址表：哈希（

    2024年02月10日
    浏览(44)
  • 【数据结构与算法】单链表的排序算法(选择，冒泡，递归）

    【数据结构与算法】单链表的排序算法(选择，冒泡，递归）

    目录 选择排序 冒泡排序 快速排序 合并两条链表并排序 选择排序 链表的选择排序思想与数组的排序类似，但是链表需要先找到里面最小或者最大的值，然后将这个值用改链语句进行操作 我们先看这个改链语句的操作（min是笔者打错了应该是max，但是图已经画好了就没有改）

    2024年02月04日
    浏览(56)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包，优惠每天领

二维码1

领取红包

二维码2

领红包