当前位置：首页 > article >正文

Linux-数据结构-哈夫曼树-哈希表-内核链表

article 2025/3/25 23:11:38

一.哈夫曼树

哈夫曼树（Huffman Tree）是一种特殊的二叉树，其定义和原理如下：

【1】定义

哈夫曼树是一种带权路径长度最短的二叉树。给定一组权值，将这些权值作为叶子节点的权值构造一棵二叉树，若该树的带权路径长度（WPL）达到最小，则称这样的二叉树为哈夫曼树。

【2】原理

哈夫曼树的构造基于贪心算法，其原理是通过不断合并权值最小的节点来构建最优二叉树，从而实现最小化带权路径长度。具体步骤如下：

初始化：将所有给定的权值分别作为叶子节点，构造一个只包含一个根节点的二叉树集合。
选择与合并：从集合中选取权值最小的两棵二叉树，分别作为左右子树构造一棵新的二叉树，新二叉树的根节点权值为其左右子树根节点权值之和。
更新集合：从集合中删除作为左右子树的两棵二叉树，并将新构造的二叉树加入集合。
重复操作：重复上述步骤，直到集合中只剩下一棵二叉树，这棵二叉树即为哈夫曼树。

【3】特点

哈夫曼树的带权路径长度最短，权值较大的节点离根节点较近。
哈夫曼树的非叶子节点都有两个孩子。
哈夫曼树的构造是自底向上的。

哈夫曼树常用于数据压缩中的哈夫曼编码，通过为出现频率高的字符分配较短的编码，为出现频率低的字符分配较长的编码，从而实现无损数据压缩。

【4】例：

二.哈希表

【1】hash表初始化

（1）初始化的len就是哈希表的key

（2）将head数组里的数据全部置为-1，以便于判断是否为空

memset 是 C 和 C++ 编程语言中的一个标准库函数，用于将一块内存区域的内容设置为指定的值。它的原型定义在头文件 <string.h>（C语言）或 <cstring>（C++语言）中。

（3）memset函数原型

c复制

void* memset(void* ptr, int value, size_t num);

参数

ptr：
- 指向要填充的内存块的指针。
value：
- 要设置的值。该值会被转换为 unsigned char 类型，并且会重复填充到内存块中。
num：
- 要填充的字节数。

返回值

返回指向被填充的内存块的指针，即参数 ptr 的值。

功能

memset 函数将从 ptr 开始的内存区域的 num 个字节全部设置为 value。需要注意的是，value 会被解释为一个 unsigned char，因此它实际上是一个字节的值。

【2】哈希函数

返回求余数

【3】哈希表插入函数

求余后按位置插入，如果没有位置，循环遍历哈希表，直到有空位

【4】哈希查找（时间复杂度低）

循环查找，如果循环一圈的inx与oldinx相等，则没有找到

【5】主函数

三.liinux内核链表（循环双向链表）

【1】实现思路

【2】klist.h

宏通过指针和地址偏移计算，实现了对链表中元素的遍历和访问。offset宏用于计算成员变量的偏移量，containerof宏用于通过成员变量的指针找到其所属的结构体，klist_for_entry宏用于通过链表节点的指针找到其所属的结构体，klist_for_each宏用于遍历链表中的所有元素。这些宏在Linux内核中被广泛使用，用于链表操作