嵌入式开发学习日志（数据结构--树、哈希表和内核链表）Day23

一、树

（一）树的基本概念

1、树的定义

   树(Tree)是n(n≥0)个结点的有限集。n=0时称为空树。在任意一棵非空树中：有且仅有一个特定的称为根(Root)的结点;(2)当n>1时，其余结点可分为m(m>0)个互不相交的有限集 T1、T2、…、Tm，其中每一个集合本身又是一棵树，并且称为根的子树(SubTree)。

注意：

（1）n>0时根结点是唯一的，不可能存在多个根结点，别和现实中的大树混在一起，现实中的树有很多根须，那是真实的树，数据结构中的树是只能有一个根结点。

（2）m>0 时，子树的个数没有限制，但它们一定是互不相交的。

2、树的结点

（1）结点分类： 树的结点包含一个数据元素及若干指向其子树的分支。结点拥有的子树数称为结点的度(Degree)。度为0的结点称为叶结点(Leaf)或终端结点;度不为0的结点称为非终端结点或分支结点。除根结点之外，分支结点也称为内部结点。树的度是树各结点的度的最大值。如图所示，因为这棵树结点的度的最大值是结点D的度，为3，所以树的度也为3。

 

（2）结点间关系：结点的子树的根称为该结点的孩子(Chid)，相应地，该结点称为孩子的双亲(Parent)。同一个双亲的孩子之间互称兄弟(Sibling)。结点的祖先是从根到该结点所经分支上的所有结点。所以对于H来说，D、B、A都是它的祖先。反之，以某结点为根的子树中的任一结点都称为该结点的子孙。B的子孙有 D、G、H、I，如图所示。

 

3、树的其他概念

（1）结点的层次(Level)从根开始定义起，根为第一层，根的孩子为第二层。若某结点在第1层，则其子树的根就在第 1+1 层。其双亲在同一层的结点互为堂兄弟。显然图中的 D、E、F是堂兄弟，而 G、H、I、J也是。树中结点的最大层次称为树的深度(Depth)或高度，当前树的深度为4。

 

（2）如果将树中结点的各子树看成从左至右是有次序的，不能互换的，则称该树为有序树，否则称为无序树。

（3）森林(Forest)是m(m>=0)棵互不相交的树的集合。对树中每个结点而言，其子树的集合即为森林。

4、树的存储结构（顺序结构 链式结构）

 （二）、二叉树

1、二叉树的定义

        二叉树(Binary Tree)是n(n≥0)个结点的有限集合，该集合或者为空集(称为空二叉树)，或者由一个根结点和两棵互不相交的、分别称为根结点的左子树和右子树的二叉树组成。

2、二叉树的特点

（1）每个结点最多有两棵子树，所以二叉树中不存在度大于2的结点。注意不是只有两棵子树，而是最多有。没有子树或者有一棵子树都是可以的。

（2）左子树和右子树是有顺序的，次序不能任意颠倒。

（3）即使树中某结点只有一棵子树，也要区分它是左子树还是右子树。

3、二叉树的五种基本形态

（1）空二叉树。

（2）只有一个根结点。

（3）根结点只有左子树。

（4）根结点只有右子树。

（5）根结点既有左子树又有右子树.

4、特殊二叉树

（1）斜树：所有的结点都只有左子树的二叉树叫左斜树；所有结点都是只有右子树的二叉树叫右斜树；这两者统称为斜树。

（2）满二叉树：在一棵二叉树中，如果所有分支结点都存在左子树和右子树，并且所有叶子都在同一层上，这样的二叉树称为满二叉树。

单是每个结点都存在左右子树，不能算是满二叉树，还必须要所有的叶子都在同一层上，这就做到了整棵树的平衡。因此，满二叉树的特点有:

a.叶子只能出现在最下一层。出现在其他层就不可能达成平衡。

b.非叶子结点的度一定是 2。否则就是“缺胳膊少腿”了。

c.在同样深度的二叉树中，满二叉树的结点个数最多，叶子数最多。

（3）完全二叉树：对一棵具有 n个结点的二叉树按层序编号，如果编号为i(1<i<n)的结点与同样深度的满二叉树中编号为i的结点在二叉树中位置完全相同，则这棵二叉树称为完全二叉树，如图所示：

 

完全二叉树的特点:

a.叶子结点只能出现在最下两层。

b.最下层的叶子一定集中在左部连续位置。

c.倒数二层，若有叶子结点，一定都在右部连续位置。

d.如果结点度为 1，则该结点只有左孩子，即不存在只有右子树的情况。

e.同样结点数的二叉树，完全二叉树的深度最小。

5、二叉树的性质

（1）在二叉树的第i层上最多有2^(i-1)个结点 i>=1

（2）深度为k的二叉树至多有2^k  -1 个结点 k>=1

（3）任意一个二叉树T，如果其叶子结点的个数是n0,度数为2的结点数为 n2， n0 = n2 +1;

（4）有n个结点的完全二叉树深度为(logn/log 2) +1;

（5）如果对一棵有n个结点的完全二叉树(其深度为[logzn]+1)的结点按层序编号(从第1

层到第[l0gzn]+1层，每层从左到右)，对任一结点i(1<i<n)有:

        a.如果 i=1，则结点是二叉树的根，无双亲;如果 i>1，则其双亲是结点[i/2」。

        b.如果 2i>n，则结点i无左孩子(结点i为叶子结点);否则其左孩子是结点2i。

        c.如果 2i+1>n，则结点i无右孩子;否则其右孩子是结点 2i+1。

6、层序

（1）前序：根左右；先访问根，然后访问左，再访问右。

（2）中序：左根右；先从根开始（不是先访问根），从左开始访问，再访问根，再访问右结点。
（3）后序：左右根；先从根开始（不是先访问根），先访问左，再访问右，再访问 根。

（4）示例：

（三）二叉树的基本操作

1、定义结构体

typedef char DATATYPE;  // 将char类型重命名为DATATYPE，方便后续使用，可灵活替换树节点数据类型

typedef struct _tree_node_
{
    DATATYPE data;       // 树节点存储的数据，类型为前面定义的DATATYPE（即char）
    struct _tree_node_ *left, *right;  // 指向左子节点和右子节点的指针
} TreeNode;
  
全局变量定义
char data[] = "abd#f###c#eg###";  // 用于构建树的字符数组，按特定格式表示树的节点，'#'表示空节点
int ind = 0;  // 用于记录在data数组中当前处理的位置索引

2、树的静态创建

void CreateTree(TreeNode **root)
{
    char c = data[ind++];  // 取出data数组中当前位置的字符，并将索引ind后移一位
    if ('#' == c)  // 如果取出的字符是'#'，表示该位置为空节点
    {
        *root = NULL;  // 将当前节点指针设为空
        return;  // 结束当前递归分支
    }
    else
    {
        *root = malloc(sizeof(TreeNode));  // 为当前树节点分配内存空间
        if (NULL == *root)  // 如果内存分配失败
        {
            fprintf(stderr, "CreateTree malloc error");  // 向标准错误输出打印错误信息
            return;  // 结束当前递归分支
        }
        (*root)->data = c;  // 将取出的字符赋值给当前树节点的数据域
        CreateTree(&(*root)->left);  // 递归创建当前节点的左子树
        CreateTree(&(*root)->right); // 递归创建当前节点的右子树
    }
}

3、先序遍历

void PreOrderTraverse(TreeNode *root)
{
    if (NULL == root)  // 如果当前节点为空，直接返回，结束当前递归分支
    {
        return;
    }
    printf("%c", root->data); // 先访问根节点，打印根节点的数据
    PreOrderTraverse(root->left); // 递归遍历左子树
    PreOrderTraverse(root->right); // 递归遍历右子树
}

4、中序遍历

void InOrderTraverse(TreeNode *root)
{
    if (NULL == root)  // 如果当前节点为空，直接返回，结束当前递归分支
    {
        return;
    }
    InOrderTraverse(root->left); // 先递归遍历左子树
    printf("%c", root->data); // 再访问根节点，打印根节点的数据
    InOrderTraverse(root->right); // 最后递归遍历右子树
}

5、后序遍历

void PostOrderTraverse(TreeNode *root)
{
    if (NULL == root)  // 如果当前节点为空，直接返回，结束当前递归分支
    {
        return;
    }
    PostOrderTraverse(root->left); // 先递归遍历左子树
    PostOrderTraverse(root->right); // 再递归遍历右子树
    printf("%c", root->data); // 最后访问根节点，打印根节点的数据
}

6、销毁树

void DestroyTree(TreeNode *root)
{
    if(NULL == root)  // 如果当前节点为空，直接返回，结束当前递归分支
    {
        return ;
    }
    DestroyTree(root->left); // 递归销毁左子树
    DestroyTree(root->right); // 递归销毁右子树
    free(root); // 释放当前节点的内存空间
}

7、主函数

int main(int argc, char **argv)
{
    TreeNode *root = NULL;  // 初始化根节点指针为空
    CreateTree(&root);  // 创建树，传入根节点指针的地址
    PreOrderTraverse(root);  // 对树进行先序遍历并打印节点
    puts("");  // 打印换行符
    InOrderTraverse(root);  // 对树进行中序遍历并打印节点
    puts("");  // 打印换行符
    PostOrderTraverse(root);  // 对树进行后序遍历并打印节点
    puts("");  // 打印换行符
    DestroyTree(root);  // 销毁树，释放树占用的内存
    root = NULL;  // 将根节点指针设为空
    // system("pause");  // 被注释掉，原本可能用于暂停程序，在Windows下常见，Linux下一般无此需求
    return 0;  // 程序正常结束返回0
}

二、哈希表

（一）哈希表的基本概念

1、定义：

散列技术是在记录的存储位置和它的关键字之间建立一个确定的对应关系f，使得每个关键字 key 对应一个存储位置f(key)。查找时，根据这个确定的对应关系找到给定值 key的映射f(key)，若查找集合中存在这个记录，则必定在f(key)的位置上这里我们把这种对应关系f称为散列函数，又称为哈希(Hash)函数。按这个思想，采用散列技术将记录存储在一块连续的存储空间中，这块连续存储空间称为散列表或哈希(Hashtabke)。那么关键字对应的记录存储位置我们称为散列地址。

2、散列表的查找步骤：

（1）在存储时，通过散列函数计算记录的散列地址，并按此散列地址存储该记；

（2）当查找记录时，我们通过同样的散列函数计算记录的散列地址，按此散列地址访问该记录。

注：散列技术既是一种存储方法，也是一种查找方法。

3、常用的构造散列函数方法：（除留余数法）

对于散列表长为m的散列函数公式为: f( key )=key mod p(p≤m )

mod 是取模(求余数)的意思。事实上，这方法不仅可以对关键字直接取，也在折叠、平方取中后再取模。

4、处理散列冲突的方法：由于哈希函数可能将不同的键映射到相同的哈希值，因此会发生哈希冲突，常见的冲突解决方法包括链地址法和开放地址法。

        链地址法：每个数组位置存储一个链表，所有哈希值相同的键值对都存储在这个链表中；

        开放地址法：当发生冲突时，通过探测方法（如线性探测、二次探测）寻找下一个

可用的位置。

（二）哈希表的基本操作

1、数据类型的定义

typedef int DATATYPE;  // 将int类型重命名为DATATYPE，方便后续表示哈希表存储的数据类型

typedef struct
{
    DATATYPE* head;  // 指向哈希表存储数据的数组指针
    int tlen;        // 哈希表的长度
} HSTable;

2、创建哈希表

HSTable* CreateHsTable(int len)
{
    HSTable* hs = malloc(sizeof(HSTable));  // 为哈希表结构体分配内存
    if (NULL == hs)  // 如果内存分配失败
    {
        fprintf(stderr, "CreateHsTable malloc error");  // 向标准错误输出打印错误信息
        return NULL;  // 返回空指针表示创建失败
    }
    hs->head = malloc(sizeof(DATATYPE) * len);  // 为哈希表的数据存储数组分配内存
    if (NULL == hs->head)  // 如果内存分配失败
    {
        fprintf(stderr, "CreateHsTable malloc2 error");  // 向标准错误输出打印错误信息
        return NULL;  // 返回空指针表示创建失败
    }
    hs->tlen = len;  // 设置哈希表的长度
    int i = 0;
    for (i = 0; i < len; i++)  // 初始化哈希表数组，将每个元素设为-1
    {
        hs->head[i] = -1;  // -1表示该位置为空
    }
    return hs;  // 返回创建好的哈希表指针
}

3、哈希函数

int HSFun(HSTable* hs, DATATYPE* data)

{
        return *data % hs->tlen;

}  // 哈希函数，通过取余计算数据在哈希表中的索引位置

4、数据放入哈希表内

int HSInsert(HSTable* hs, DATATYPE* data)
{
    int ind = HSFun(hs, data);  // 通过哈希函数计算数据应插入的索引位置
    while (hs->head[ind] != -1)  // 如果该位置已被占用（不为-1）
    {
        printf("pos %d, num:%d\n", ind, *data);  // 打印冲突位置和要插入的数据
        ind = (ind + 1) % hs->tlen;  // 采用线性探测法寻找下一个空位置
    }
    hs->head[ind] = *data;  // 将数据插入到找到的空位置
    return 0;  // 插入成功返回0
}

5、查找函数

int HsSearch(HSTable* hs, DATATYPE* data)
{
    int ind = HSFun(hs, data);  // 通过哈希函数计算数据在哈希表中的起始索引位置
    int old_ind = ind;  // 保存起始索引位置
    while (hs->head[ind] != *data)  // 当当前位置的数据与要查找的数据不相等时
    {
        ind = (ind + 1) % hs->tlen;  // 采用线性探测法寻找下一个位置
        if (old_ind == ind)  // 如果回到了起始位置，说明没找到
        {
            return -1;  // 返回-1表示未找到
        }
    }
    return ind;  // 返回找到数据的索引位置
}

6、主函数调用

int main(int argc, char** argv)
{
    HSTable* hs = CreateHsTable(12);  // 创建长度为12的哈希表
    int array[] = {12, 67, 56, 16, 25, 37, 22, 29, 15, 47, 48, 34};  // 定义要插入哈希表的数据数组
    int i = 0;
    for (i = 0; i < 12; i++)  // 遍历数组，将数据插入哈希表
    {
        HSInsert(hs, &array[i]);  // 插入数据到哈希表
    }
    int want_num = 37;  // 定义要查找的数据
    int ret = HsSearch(hs, &want_num);  // 在哈希表中查找数据
    if (-1 == ret)  // 如果返回-1，说明未找到
    {
        printf("not find \n");  // 打印未找到信息
    }
    else  // 找到数据
    {
        printf("find ,%d\n", hs->head[ret]);  // 打印找到的数据
    }
    // system("pause");  // 被注释掉，原本可能用于暂停程序（在Windows下常见，Linux下一般无此需求）
    return 0;  // 程序正常结束返回0
}

三、内核链表

1、Linux内核链表是一种数据结构，它在Linux内核编程中广泛使用，用于管理各种类型的数据元素。链表由一系列节点组成，每个节点包含指向下一个节点和前一个节点的指针。这种设计使得链表在插入和删除操作时非常高效，因为不需要移动其他元素。

2、链表的定义和初始化

（1）在Linux内核中，链表通过包含list_head结构体的方式在各种数据结构中实现。

（2）list_head结构体定义在<linux/list.h>头文件中，包含next和prev两个指针，分别指向链表的下一个和前一个元素。要使用内核链表，首先需要包含这个头文件。

（3）初始化链表时，可以使用INIT_LIST_HEAD宏，它将链表的next和prev指针都指向链表本身，形成一个循环链表。

内核链表是双向循环链表：

注：内部增删改查已经写好，将需要的内容组合到结构体中即可使用

（可通过www.kernel.org去下载内核）

3、内核链表的思想：普通链表与数据耦合性高，自己定义结构体，将数据放入；

（1）offset宏：传入结构体，成员，通过宏进入，计算node的偏移量是多少；

（2）contrainof宏：返回该类型指针的地址。

4、内核链表提供了一系列宏和函数来进行操作，如添加、删除和遍历节点：

（1）添加节点：使用list_add或list_add_tail函数可以在链表的头部或尾部添加新节点。

（2）删除节点：使用list_del函数可以从链表中删除节点。

（3）遍历链表：使用list_for_each或list_for_each_entry宏可以遍历链表中的每个元素。

5、注意事项在：使用内核链表时，需要注意几个重要的点：

（1）内存管理：当添加新节点到链表时，需要确保为节点分配了内存。同样，从链表中删除节点时，需要释放节点占用的内存。

（2）同步：在多线程环境中操作链表时，可能需要使用锁来避免竞态条件。

（3）性能：虽然链表在插入和删除操作时非常高效，但在查找元素时可能需要遍历整个链表，这可能会影响性能。