一、哈希表介绍① 哈希存储散列存储将要存储数据的关键字key和数据存储位置值之间建立起对应的函数映射关系。当数据存储时根据该关系映射数据的存储位置当查找数据时利用该函数关系运算出数据的存储位置② 目的为了快速检索数据从而实现 O(1) 级别的快速读写。③ 哈希表的核心三要素缺一不可部件作用关键要求哈希函数 (Hash Function)把任意长度的 Key如字符串转化为一个整数数组下标。计算要快分布要均匀避免扎堆。数组 (Array / Buckets)真正存储数据的地方。也叫“桶数组”。大小可动态扩展扩容。冲突解决机制 (Collision Resolution)当两个不同 Key 落在同一个下标时如何处理。决定哈希表的稳定性和最坏情况性能。④核心问题哈希冲突Collision/哈希矛盾因为输入空间无限数组空间有限必然会出现两个不同的 Key 算出了同一个下标。⑤ 解决哈希冲突的方法:解决方案原理优缺点链地址法拉链法每个位置是一个链表冲突了就挂到链表尾部。实现简单删除方便但链表太长时查询退化为 O(n)。开放寻址法线性探测冲突了就往后找下一个空位放进去。数据全存在数组里缓存友好但删除麻烦且容易产生“聚集”效应。二、链地址法的实现2.1 哈希表的声明/创建//哈希表中每个节点要存储的业务数据 typedef struct info { char name[32]; char tel[16]; }DataType_t; //链表节点哈希桶的挂载点 typedef struct node { DataType_t data; struct node *pnext; }HSNode_t; #define HASH_MAX_SIZE 27 //创建哈希表 HSNode_t *hash_table[HASH_MAX_SIZE] {NULL}; HSNode_t *ptmp NULL; DataType_t pers[] {{zhangsan, 110}, {lisi, 112}, {wanger, 120}, {zhaowu, 119}, {maliu, 10086}};2.2 创建哈希函数//创建哈希函数把字符映射到数组下标 int hash_function(char key) { if (key a key z) //判断是否小写字母 { return key - a; //小写字母映射到 0~25 } else if (key A key Z)//判断是否大写字母 { return key - A; //大写字母也映射到 0~25 } else { return HASH_MAX_SIZE-1;//其他字符全部塞到最后一个桶 } }2.3 哈希表中插入数据头插法//哈希表中插入数据头插法 //二级指针指向哈希表桶数组的指针数组本身是指针数组所以需要二级指针才能修改数组内容 int insert_hash_table(HSNode_t **hash_table, DataType_t data) { HSNode_t *pnode malloc(sizeof(HSNode_t)); //在堆上动态分配一个节点所需的内存 if (NULL pnode) { printf(malloc error\n); return -1; } pnode-data data; //结构体整体赋值 pnode-pnext NULL; //新节点的next指针先置空 int addr hash_function(data.name[0]); //取姓名的第一个字符 pnode-pnext hash_table[addr] ; // 新节点指向旧头节点 hash_table[addr] pnode;//更新桶的头指针为新节点 return 0; }2.4 遍历哈希表void show_hash_table(HSNode_t **hash_table) { for (int i 0; i HASH_MAX_SIZE; i) //依次访问哈希表的每个桶槽位 { HSNode_t *ptmp hash_table[i]; //定义一个临时指针指向当前桶的链表头 while (ptmp ! NULL) //遍历当前桶的链表 { printf(%s : %s\n, ptmp-data.name, ptmp-data.tel); ptmp ptmp-pnext; //将临时指针移动到下一个节点 } printf(\n); } }2.5 哈希表中查找数据//基于名字查找 HSNode_t *find_hash_table(HSNode_t **hash_table, char *name) { int addr hash_function(name[0]); //取姓名的第一个字符 HSNode_t *ptmp hash_table[addr]; //临时指针指向该桶的链表头节点 while (ptmp ! NULL) //遍历链表直到链表末尾 { //字符串比较判断姓名是否匹配如果相等返回0则找到 if (0 strcmp(ptmp-data.name, name)) { return ptmp; } ptmp ptmp-pnext; //指针后移继续遍历 } return NULL; }2.6 销毁哈希表void destroy_hash_table(HSNode_t **hash_table) { for (int i 0; i HASH_MAX_SIZE; i) //外层循环——遍历所有桶 { HSNode_t *ptmp hash_table[i]; //临时指针指向当前桶的链表头 while (hash_table[i] ! NULL) //内层循环——释放当前桶的所有节点 { hash_table[i] ptmp-pnext; //更新头指针将头指针指向下一个节点 free(ptmp); //释放当前节点释放 ptmp 指向的内存块 ptmp hash_table[i]; //移动临时指针将临时指针指向新的头节点 } } } //执行过程图解假设桶[3]有3个节点 【初始状态】 hash_table[3] → [A|pnext] → [B|pnext] → [C|pnext] → NULL ↑ ptmp 【第1次循环】hash_table[3] ! NULL ✅ ① hash_table[3] ptmp-pnext → hash_table[3] 指向 B ② free(ptmp) → 释放 A ③ ptmp hash_table[3] → ptmp 指向 B 当前状态 hash_table[3] → [B|pnext] → [C|pnext] → NULL ↑ ptmp 【第2次循环】hash_table[3] ! NULL ✅ ① hash_table[3] ptmp-pnext → hash_table[3] 指向 C ② free(ptmp) → 释放 B ③ ptmp hash_table[3] → ptmp 指向 C 当前状态 hash_table[3] → [C|pnext] → NULL ↑ ptmp 【第3次循环】hash_table[3] ! NULL ✅ ① hash_table[3] ptmp-pnext → hash_table[3] 指向 NULL ② free(ptmp) → 释放 C ③ ptmp hash_table[3] → ptmp 指向 NULL 当前状态 hash_table[3] → NULL ↑ ptmp (指向NULL) 【第4次循环】hash_table[3] NULL ❌ 退出循环2.7 附件代码① hash.h#ifndef __HASH_H__ #define __HASH_H__ typedef struct info { char name[32]; char tel[16]; }DataType_t; typedef struct node { DataType_t data; struct node *pnext; }HSNode_t; #define HASH_MAX_SIZE 27 extern int insert_hash_table(HSNode_t **hash_table, DataType_t data); void show_hash_table(HSNode_t **hash_table); extern HSNode_t *find_hash_table(HSNode_t **hash_table, char *name); extern void destroy_hash_table(HSNode_t **hash_table); #endif② hash.c#include hash.h #include stdio.h #include stdlib.h #include string.h int hash_function(char key) { if (key a key z) { return key - a; } else if (key A key Z) { return key - A; } else { return HASH_MAX_SIZE-1; } } int insert_hash_table(HSNode_t **hash_table, DataType_t data) { HSNode_t *pnode malloc(sizeof(HSNode_t)); if (NULL pnode) { printf(malloc error\n); return -1; } pnode-data data; pnode-pnext NULL; int addr hash_function(data.name[0]); pnode-pnext hash_table[addr] ; //---phead hash_table[addr] pnode; return 0; } void show_hash_table(HSNode_t **hash_table) { for (int i 0; i HASH_MAX_SIZE; i) { HSNode_t *ptmp hash_table[i]; while (ptmp ! NULL) { printf(%s : %s\n, ptmp-data.name, ptmp-data.tel); ptmp ptmp-pnext; } printf(\n); } } HSNode_t *find_hash_table(HSNode_t **hash_table, char *name) { int addr hash_function(name[0]); HSNode_t *ptmp hash_table[addr]; while (ptmp ! NULL) { if (0 strcmp(ptmp-data.name, name)) { return ptmp; } ptmp ptmp-pnext; } return NULL; } void destroy_hash_table(HSNode_t **hash_table) { for (int i 0; i HASH_MAX_SIZE; i) { HSNode_t *ptmp hash_table[i]; while (hash_table[i] ! NULL) { hash_table[i] ptmp-pnext; free(ptmp); ptmp hash_table[i]; } } }③ main.c#include hash.h #include stdio.h int main(int argc, const char *argv[]) { HSNode_t *hash_table[HASH_MAX_SIZE] {NULL}; HSNode_t *ptmp NULL; DataType_t pers[] {{zhangsan, 110}, {lisi, 112}, {wanger, 120}, {zhaowu, 119}, {maliu, 10086}}; insert_hash_table(hash_table, pers[0]); insert_hash_table(hash_table, pers[1]); insert_hash_table(hash_table, pers[2]); insert_hash_table(hash_table, pers[3]); insert_hash_table(hash_table, pers[4]); show_hash_table(hash_table); ptmp find_hash_table(hash_table, zhaowu); if (ptmp ! NULL) { printf(find : %s : %s\n, ptmp-data.name, ptmp-data.tel); } destroy_hash_table(hash_table); return 0; }三、工程管理工具makefile3.1 makefile介绍① makefile用来组织和管理代码工程的编译和链接通过make工具解释和执行。② Makefile 通过定义规则来指导 make 工具进行程序的编译和链接能够智能地选择需要编译的代码文件。③ Makefile 会根据文件间的依赖关系和修改时间戳自动判断哪些代码需要重新编译哪些可以直接使用之前的编译结果。④ C语言中.h/.c文件介绍.h文件只放声明函数原型、外部变量、宏、类型定义可以多次被包含。函数原型int add(int a, int b);函数声明外部全局变量声明extern int global_counter;类型定义typedef struct、enum宏定义#define PI 3.14159防止重复包含的#ifndef/#define/#endif 守卫.c文件放定义函数体、变量实体。只能被编译一次。必须#include自己的头文件确保声明和定义一致函数的具体代码体定义头文件里声明过的全局变量不带extern模块内部私有的辅助函数用static修饰防止外部调用3.2 makefile使用① 文件名要求Makefile/makefile; 编译make② Makefile核心规则目标文件一般是a.out,依赖文件一般是.c文件目标文件:依赖文件(回车)(TAB键)编译规则③ Makefile的语法1自定义变量字符串的方式自定义变量的名称 值 : 给变量直接赋值 在原变量基础上增加新值? 变量如果没有被赋值则赋新值如果之前有被赋值则保留原值引用变量 $(变量名) ----- 使用该变量中的值2) 系统变量$ : 目标文件$^ : 所有的依赖文件源文件$ : 第一个依赖文件④ 时间戳根据文件修改的时间戳只编译最后发生修改的源文件最后完成所有文件的链接。gcc编译的4步骤预处理处理#相关的命令 gcc -E main.c -o main.i编译将源文件编译成汇编程序 gcc -S main.i -o mian.s汇编将汇编指令转换成二进制指令 gcc -c main.s -o main.o链接完成函数库等的链接操作 gcc main.o xxx.o -o a.out⑤链接规则编译并链接vi makefile #目标文件 OBJa.out #源文件 SRCmain.c SRChash.c #编译器 CCgcc # 编译选项 FLAG # 编译规则这个规则是直接编译链接一步到位 $(OBJ) : $(SRC) # $(CC) $(SRC) -o $(OBJ) $(FLAG) $(CC) $^ -o $ $(FLAG) # 清理编译产物 clean: rm $(OBJ) //使用方式 make # 编译 make clean # 删除可执行文件⑥编译规则编译链接vi makefile #目标文件 OBJa.out #源文件 SRCmain.o SRChash.o #编译器 CCgcc # 编译选项 FLAG # 编译规则这个规则是直接编译链接一步到位 $(OBJ) : $(SRC) # $(CC) $(SRC) -o $(OBJ) $(FLAG) $(CC) $^ -o $ $(FLAG) #根据时间戳更新%通配符只编译不链接 %.o : %.c $(CC) -c $^ -o $ #main.o:main.c # $(CC) -c main.c -o main.o #hash.o:hash.c # $(CC) -c hash.c -o hash.0 # 清理编译产物 clean: rm $(OBJ) //使用方式 make # 编译 make clean # 删除可执行文件