从零开始的敲代码生活--数据结构篇（哈希表与算法）

一、哈希表基础概念

散列存储(哈希存储)：将要存储的元素的关键字和存储位置之间建立起对应关系，这个关系称为哈希函数。

• 数据存储时，按照哈希函数的映射进行存储
• 数据查找时，也按照哈希函数的映射进行查找

哈希表（散列表）：利用哈希函数计算元素存储位置的数据结构，查找时直接根据关键字计算位置，理想情况下查找时间复杂度可达到 $(O(1))$。

常用术语

• 哈希函数(散列函数)：将元素的关键字映射为存储位置(数组下标)的函数
• 哈希冲突(碰撞)：不同的关键字通过哈希函数计算出相同的存储位置

冲突处理方式

哈希表 API

示例说明：本示例实现一个"姓名 + 电话"电话簿哈希表，哈希函数按姓名首字母(a‑z)映射到 0‑25 号桶，非字母字符放入 26 号桶(HASH_SIZE‑1)，同字母开头的姓名冲突时采用头插法链入同一个桶。

文件说明

二、哈希表代码

1. 头文件 hash.h

#ifndef _HASH_H
#define _HASH_H
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define HASH_SIZE 27 // 哈希表桶的个数:26个字母桶 + 1个其他字符桶

/* 存储的数据类型:姓名 + 电话 */
typedef struct data
{
char name[32];
char tel[16];
}P_info;

/* 哈希桶结点结构体:数据域 + 指针域 */
typedef struct node
{
P_info data; // 数据域:电话信息
struct node *pnext; //指针域:下一个结点的地址
}Node_t;

extern int inserte_hash(Node_t **phash,P_info data);
extern void show_hash(Node_t **phash);
extern int find_hash(Node_t **phash,char name[]);
extern void free_hash(Node_t **phash);
#endif

2. 功能实现 hash.c

hash_fun 哈希函数

功能：以姓名首字母为关键字计算哈希值(下标)。小写字母返回 key-'a'(0~25)，大写字母返回 key-'A'(0~25)，其他字符统一返回 HASH_SIZE‑1(26 号桶)。返回：哈希值(桶下标)。

int hash_fun(char key)
{
if(key >= 'a' && key <= 'z')
{
return key-'a';
}
else if (key >= 'A' && key <= 'Z')
{
return key-'A';
}
else
{
return HASH_SIZE-1;
}
}

inserte_hash 插入数据

功能：计算关键字哈希值得到桶下标，采用头插法将新结点插入对应哈希桶(链地址法解决冲突)。返回：0 成功，‑1 失败(malloc 失败)。

int inserte_hash(Node_t **phash,P_info data)
{
Node_t *pinsert = malloc(sizeof(Node_t));
if(pinsert == NULL)
{
printf("mallloc fail\\n");
return -1;
}
int idx = hash_fun(data.name[0]);
pinsert->data = data;
pinsert->pnext = phash[idx];
phash[idx] = pinsert;
return 0;
}

show_hash 遍历打印

功能：依次遍历每个哈希桶，打印桶中所有结点的姓名与电话。

void show_hash(Node_t **phash)
{
for(int i = 0;i < HASH_SIZE;i++)
{
Node_t *ptemp = phash[i];
while(ptemp != NULL)
{
printf("%s,%s\\n",ptemp->data.name,ptemp->data.tel);
ptemp = ptemp->pnext;
}
}
}

find_hash 查找数据

功能：按姓名计算哈希值定位到桶，遍历桶内链表逐个比较姓名，找到则打印结点地址，找不到打印 NotFind。返回：0 成功，‑1 失败(未找到或入参为 NULL)。

int find_hash(Node_t **phash,char name[])
{
if(phash == NULL)
{
return -1;
}
int idx = hash_fun(name[0]);
Node_t *ptemp = phash[idx];
while(ptemp != NULL)
{
if(strcmp(ptemp->data.name,name) == 0)
{
printf("%p\\n",ptemp);
return 0;
}
ptemp = ptemp->pnext;
}
printf("NotFind\\n");
return -1;
}

free_hash 释放哈希表

功能：遍历所有哈希桶，释放桶内链表上的全部结点。

void free_hash(Node_t **phash)
{
for(int i = 0;i < HASH_SIZE;i++)
{
Node_t *pfree = NULL;
while(phash[i] != NULL)
{
pfree = phash[i];
phash[i] = pfree->pnext;
free(pfree);
}
}
}

3. 测试 main 函数 main.c

#include "hash.h"
int main(void)
{
Node_t *phash[HASH_SIZE] = {NULL};
P_info data[5] = {{"zhangsan","111111"},
{"lisi","222222"},
{"wangwu","333333"},
{"xiongda","444444"},
{"xionger","555555"}};
inserte_hash(phash,data[0]);
inserte_hash(phash,data[1]);
inserte_hash(phash,data[2]);
inserte_hash(phash,data[3]);
inserte_hash(phash,data[4]);
show_hash(phash);
find_hash(phash,data[4].name);
free_hash(phash);
return 0;
}

4. 编译运行 & 内存检测

编译：

gcc main.c hash.c -o hash_demo

运行程序：

./hash_demo

valgrind 检测内存泄漏：

写哈希表务必检测内存泄漏，保证每一块 malloc 都有对应的 free

valgrind –leak-check=full ./hash_demo

运行输出结果：

xionger,555555
xiongda,444444
wangwu,333333
lisi,222222
zhangsan,111111
000002E404AD9E20

注：最后一行为 find_hash 打印的结点地址(%p)，为程序运行期随机值，每次运行结果不同。

三、算法基础概念

算法：解决特定问题的步骤。

程序设计 = 数据结构 + 算法

算法的设计要求

空间复杂度：算法执行过程中额外开辟的空间随数据量 n 的变化关系。

• $(O(1))$：额外空间与数据量无关
• $(O(n))$：额外空间随数据量线性增长

算法时间复杂度：执行这个算法所花时间的度量。将数据量增长和时间增长用函数表示出来，这个函数就叫做时间复杂度。一般用大 O 表示法：$(O(n))$ —— 时间复杂度是关于数据量 n 的一个函数。随着 n 的增加，时间复杂度增长较慢的算法时间复杂度低。

时间复杂度的计算规则

常见时间复杂度示例

复杂度大小比较：

$$(O(1)) < (O(logn))<(O(n))<O(n logn)<O(n^2)<O(n^3)<O(2^n)<O(n !)<O(n^n)$$

四、常用排序和查找算法

常用排序算法

查找算法

插入排序

思想：将待排的数据插入到一个已有序的序列中，确保每次插入之后该序列仍然有序

• 时间复杂度：$O(n^2)$
• 空间复杂度：$(O(1))$
• 稳定性：稳定的

希尔排序

思想：将待排序列根据增量划分成若干个子序列，分别对这些子序列进行插入排序。增量由大到小逐步递减，当增量减为 1 时整个序列基本有序，再做一次插入排序完成排序

• 时间复杂度：$(O(nlogn)) \\sim O(n^2)$
• 空间复杂度：$(O(1))$
• 稳定性：不稳定

void shell_sort(int *a, int len)
{
int inc = 0;
int i = 0, j= 0, tmp = 0;
for (inc = len/2; inc > 0; inc /= 2)
{
for (i = inc; i < len; ++i)
{
tmp = a[i];
j = i;
while (j >= inc && tmp < a[j-inc])
{
a[j] = a[j-inc];
j -= inc;
}
a[j] = tmp;
}
}
}

快速排序

思想：选取基准值，从两端向中间比较，比基准值大的放在序列的右边，比基准值小的放在序列的左边；经过一趟排序，优先排好基准值；再对基准值左右两个区域重复以上操作，直到整个数组有序

• 时间复杂度：$(O(nlogn))$
• 空间复杂度：$(O(logn))$
• 稳定性：不稳定

void quick_sort(int *a, int begin, int end)
{
if (begin >= end)
{
return ;
}
int i = begin;
int j = end;
int key = a[i];
while (i < j)
{
while (i < j && key <= a[j])
–j;
a[i] = a[j];
while (i < j && key >= a[i])
++i;
a[j] = a[i];
}
a[i] = key;
quick_sort(a, i+1, end);
quick_sort(a, begin, i-1);
}

排序算法汇总表