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

Linux自学day18-二叉树、哈希表、常见的排序与查找算法

article 2025/2/23 6:23:34

一、二叉树、栈、队列

实现二叉树的创建、多种遍历方式（前序、中序、后序、层序）以及使用栈和队列辅助操作，还包含了栈和队列的基本操作：

1 btree.c

实现二叉树的创建、递归和非递归的遍历方式（前序、中序、后序、层序）以及销毁二叉树的功能。

1.1 创建一个完全二叉树

// 函数：create_complete_btree
// 功能：创建一个完全二叉树
// 参数：startno - 起始节点编号，endno - 最大节点编号
// 返回值：指向二叉树根节点的指针，如果内存分配失败则返回 NULL
treenode_t *create_complete_btree(int startno, int endno)
{
    treenode_t *pnode = NULL;  // 定义一个指向二叉树节点的指针，并初始化为 NULL

    pnode = malloc(sizeof(treenode_t));  // 为二叉树节点分配内存
    if (NULL == pnode)  // 检查内存分配是否失败
    {
        return NULL;  // 如果内存分配失败，返回 NULL
    }

    pnode->no = startno;  // 将起始节点编号赋值给当前节点的编号
    if (2 * startno <= endno)  // 如果左子节点编号在范围内
    {
        pnode->pleftchild = create_complete_btree(2 * startno, endno);  // 递归创建左子树
    }
    else 
    {
        pnode->pleftchild = NULL;  // 左子节点为空
    }

    if (2 * startno + 1 <= endno)  // 如果右子节点编号在范围内
    {
        pnode->prightchild = create_complete_btree(2 * startno + 1, endno);  // 递归创建右子树
    }
    else 
    {
        pnode->prightchild = NULL;  // 右子节点为空
    }
    
    return pnode;  // 返回当前节点的指针
}

1.2 前序遍历二叉树

// 函数：preoder_traversal_btree
// 功能：前序遍历二叉树
// 参数：proot - 指向二叉树根节点的指针
// 返回值：返回 0
int preoder_traversal_btree(treenode_t *proot)
{
    if (NULL == proot)  // 如果根节点为空
    {
        return 0;  // 直接返回 0
    }

    printf("%d ", proot->no);  // 输出当前节点的编号
    preoder_traversal_btree(proot->pleftchild);  // 递归遍历左子树
    preoder_traversal_btree(proot->prightchild);  // 递归遍历右子树

    return 0;  // 返回 0
}

1.2.1 示例演示

递归前序遍历过程分析：

访问根节点：从根节点 1 开始，首先访问根节点，输出 1。
遍历左子树：接着进入左子树，根节点 2 成为当前根节点，访问该节点并输出 2。
继续遍历左子树：进入节点 2 的左子树，节点 4 成为当前根节点，访问该节点并输出 4。由于节点 4 没有左右子树，递归返回。
遍历右子树：回到节点 2，进入其右子树，节点 5 成为当前根节点，访问该节点并输出 5。由于节点 5 没有左右子树，递归返回。
回到根节点并遍历右子树：回到最初的根节点 1，进入其右子树，节点 3 成为当前根节点，访问该节点并输出 3。由于节点 3 没有左右子树，递归结束。

最终前序遍历的结果为：1 2 4 5 3。

1.3 中序遍历二叉树

// 函数：inoder_traversal_btree
// 功能：中序遍历二叉树
// 参数：proot - 指向二叉树根节点的指针
// 返回值：返回 0
int inoder_traversal_btree(treenode_t *proot)
{
    if (NULL == proot)  // 如果根节点为空
    {
        return 0;  // 直接返回 0
    }

    inoder_traversal_btree(proot->pleftchild);  // 递归遍历左子树
    printf("%d ", proot->no);  // 输出当前节点的编号
    inoder_traversal_btree(proot->prightchild);  // 递归遍历右子树

    return 0;  // 返回 0
}

示例演示：

中序遍历的步骤如下：

从根节点 1 开始，先递归遍历左子树。
左子树的根节点是 2，继续递归遍历 2 的左子树，找到节点 4。
节点 4 没有左子树，输出 4。
回到节点 2，输出 2。
遍历节点 2 的右子树，找到节点 5，输出 5。
回到根节点 1，输出 1。
遍历根节点 1 的右子树，找到节点 3，输出 3。

最终的中序遍历结果是：4 2 5 1 3。

1.4 后序遍历二叉树

// 函数：postoder_traversal_btree
// 功能：后序遍历二叉树
// 参数：proot - 指向二叉树根节点的指针
// 返回值：返回 0
int postoder_traversal_btree(treenode_t *proot)
{
    if (NULL == proot)  // 如果根节点为空
    {
        return 0;  // 直接返回 0
    }

    postoder_traversal_btree(proot->pleftchild);  // 递归遍历左子树
    postoder_traversal_btree(proot->prightchild);  // 递归遍历右子树
    printf("%d ", proot->no);  // 输出当前节点的编号

    return 0;  // 返回 0
}

示例演示：

后序遍历的步骤如下：

从根节点 1 开始，先递归遍历左子树。
左子树的根节点是 2，继续递归遍历 2 的左子树，找到节点 4。
节点 4 没有左子树和右子树，输出 4。
回到节点 2，遍历其右子树，找到节点 5，节点 5 没有左子树和右子树，输出 5。
回到节点 2，输出 2。
回到根节点 1，遍历其右子树，找到节点 3，节点 3 没有左子树和右子树，输出 3。
回到根节点 1，输出 1。

最终的后序遍历结果是：4 5 2 3 1。

1.5 层序遍历二叉树

// 函数：layerout_traversal_tree
// 功能：层序遍历二叉树
// 参数：proot - 指向二叉树根节点的指针
// 返回值：返回 0
int layerout_traversal_tree(treenode_t *proot)
{
    struct list_head *pqueue = NULL;  // 定义一个指向队列头节点的指针，并初始化为 NULL
    treenode_t *ptmpdata = NULL;  // 定义一个指向树节点的指针，并初始化为 NULL

    pqueue = create_queue();  // 创建一个队列

    enter_queue(pqueue, proot);  // 将根节点入队

    // 打印出队元素，并让该节点的左右孩子入队
    while (!is_empty_queue(pqueue))  // 当队列不为空时
    {
        ptmpdata = quit_queue(pqueue);  // 出队一个节点
        printf("%d ", ptmpdata->no);  // 输出出队节点的编号
        if (ptmpdata->pleftchild != NULL)  // 如果出队节点有左子节点
        {
            enter_queue(pqueue, ptmpdata->pleftchild);  // 左子节点入队
        }
        if (ptmpdata->prightchild != NULL)  // 如果出队节点有右子节点
        {
            enter_queue(pqueue, ptmpdata->prightchild);  // 右子节点入队
        }
    }

    destroy_queue(&pqueue);  // 销毁队列

    return 0;  // 返回 0
}

1.6 销毁二叉树

// 函数：destroy_btree
// 功能：销毁二叉树
// 参数：proot - 指向二叉树根节点的指针
// 返回值：返回 0
int destroy_btree(treenode_t *proot)
{
    if (proot->pleftchild != NULL)  // 如果根节点有左子节点
    {
        destroy_btree(proot->pleftchild);  // 递归销毁左子树
    }
    if (proot->prightchild != NULL)  // 如果根节点有右子节点
    {
        destroy_btree(proot->prightchild);  // 递归销毁右子树
    }
    free(proot);  // 释放当前节点的内存
    proot = NULL;  // 将当前节点指针置为 NULL
    return 0;  // 返回 0 表示销毁操作完成
}

1.7 使用栈实现二叉树的前序遍历

// 函数：preorder_btree_stack
// 功能：使用栈实现二叉树的前序遍历
// 参数：proot - 指向二叉树根节点的指针
// 返回值：返回 0
int preorder_btree_stack(treenode_t *proot)
{
    struct list_head *pstack = NULL;  // 定义一个指向栈头节点的指针，并初始化为 NULL
    treenode_t *ptmpdata = NULL;  // 定义一个指向树节点的指针，并初始化为 NULL

    pstack = create_stack();  // 创建一个栈

    if (proot != NULL)  // 如果根节点不为空
    {
        push_stack(pstack, proot);  // 将根节点压入栈
    }

    while (!IS_EMPTY_STACK(pstack))  // 当栈不为空时
    {
        ptmpdata = pop_stack(pstack);  // 弹出栈顶节点
        printf("%d ", ptmpdata->no);  // 输出弹出节点的编号

        if (ptmpdata->prightchild != NULL)  // 如果弹出节点有右子节点
        {
            push_stack(pstack, ptmpdata->prightchild);  // 右子节点压入栈
        }
        if (ptmpdata->pleftchild != NULL)  // 如果弹出节点有左子节点
        {
            push_stack(pstack, ptmpdata->pleftchild);  // 左子节点压入栈
        }
    }

    destroy_stack(&pstack);  // 销毁栈

    return 0;  // 返回 0
}

示例演示：

前序遍历的顺序是：根节点 -> 左子树 -> 右子树。

非递归前序遍历过程分析：

初始化栈：将根节点 1 压入栈。
弹出栈顶元素并访问：弹出栈顶元素 1 并输出，然后将其右子节点 3 和左子节点 2 依次压入栈（注意栈的后进先出特性）。
继续弹出栈顶元素并访问：弹出栈顶元素 2 并输出，将其右子节点 5 和左子节点 4 依次压入栈。
弹出栈顶元素并访问：弹出栈顶元素 4 并输出，由于 4 没有子节点，不进行压栈操作。
弹出栈顶元素并访问：弹出栈顶元素 5 并输出，由于 5 没有子节点，不进行压栈操作。
弹出栈顶元素并访问：弹出栈顶元素 3 并输出，由于 3 没有子节点，不进行压栈操作。此时栈为空，遍历结束。

最终前序遍历的结果同样为：1 2 4 5 3。

1.8 使用栈实现二叉树的中序遍历

// 函数：inorder_btree_stack
// 功能：使用栈实现二叉树的中序遍历
// 参数：proot - 指向二叉树根节点的指针
// 返回值：返回 0
int inorder_btree_stack(treenode_t *proot)
{
    struct list_head *pstack = NULL;  // 定义一个指向栈头节点的指针，并初始化为 NULL
    treenode_t *ptmpdata = proot;  // 定义一个指向树节点的指针，初始化为根节点

    pstack = create_stack();  // 创建一个栈

    while (ptmpdata != NULL || !IS_EMPTY_STACK(pstack))  // 当当前节点不为空或者栈不为空时
    {
        while (ptmpdata != NULL)  // 当当前节点不为空时
        {
            push_stack(pstack, ptmpdata);  // 将当前节点压入栈
            ptmpdata = ptmpdata->pleftchild;  // 移动到左子节点
        }

        ptmpdata = pop_stack(pstack);  // 弹出栈顶节点
        printf("%d ", ptmpdata->no);  // 输出弹出节点的编号
        ptmpdata = ptmpdata->prightchild;  // 移动到右子节点
    }

    destroy_stack(&pstack);  // 销毁栈

    return 0;  // 返回 0
}

示例演示：

中序遍历的顺序是：左子树 -> 根节点 -> 右子树。

初始化栈 pstack 为空，当前节点 pnode 为根节点 1。
第一次循环：
- 不断将左子节点入栈，依次入栈 1、2、4。
- 此时栈内元素为 [4, 2, 1]（栈顶在左边）。
- 栈不为空，弹出栈顶元素 4 并打印，pnode 指向 4 的右子节点（NULL）。
第二次循环：
- 由于 pnode 为 NULL，不会再向左走。
- 栈不为空，弹出栈顶元素 2 并打印，pnode 指向 2 的右子节点 5。
- 将 5 入栈，此时栈内元素为 [5]。
- 栈不为空，弹出栈顶元素 5 并打印，pnode 指向 5 的右子节点（NULL）。
第三次循环：
- 由于 pnode 为 NULL，不会再向左走。
- 栈不为空，弹出栈顶元素 1 并打印，pnode 指向 1 的右子节点 3。
- 将 3 入栈，此时栈内元素为 [3]。
- 栈不为空，弹出栈顶元素 3 并打印，pnode 指向 3 的右子节点（NULL）。
第四次循环：
- 由于 pnode 为 NULL，不会再向左走。
- 栈为空，遍历结束。

最终中序遍历的结果为：4 2 5 1 3。

1.9 使用栈实现二叉树的后序遍历

// 函数：postorder_btree_stack
// 功能：使用栈实现二叉树的后序遍历
// 参数：proot - 指向二叉树根节点的指针
// 返回值：返回 0
int postorder_btree_stack(treenode_t *proot)
{
    struct list_head *pstack = NULL;  // 定义一个指向栈头节点的指针，并初始化为 NULL
    treenode_t *ptmpdata = proot;  // 定义一个指向树节点的指针，初始化为根节点
    treenode_t *plastvisit = NULL;  // 定义一个指向最后访问节点的指针，并初始化为 NULL

    pstack = create_stack();  // 创建一个栈

    while (ptmpdata != NULL || !IS_EMPTY_STACK(pstack))  // 当当前节点不为空或者栈不为空时
    {
        while (ptmpdata != NULL)  // 当当前节点不为空时
        {
            push_stack(pstack, ptmpdata);  // 将当前节点压入栈
            ptmpdata = ptmpdata->pleftchild;  // 移动到左子节点
        }

        ptmpdata = list_entry(pstack->next, stack_node_t, node)->data;  // 获取栈顶节点

        // 如果右子节点为空或者右子节点已经被访问过
        if (ptmpdata->prightchild == NULL || ptmpdata->prightchild == plastvisit)
        {
            ptmpdata = pop_stack(pstack);  // 弹出栈顶节点
            printf("%d ", ptmpdata->no);  // 输出弹出节点的编号
            plastvisit = ptmpdata;  // 更新最后访问节点
            ptmpdata = NULL;  // 将当前节点置为 NULL
        }
        else
        {
            ptmpdata = ptmpdata->prightchild;  // 移动到右子节点
        }
    }

    destroy_stack(&pstack);  // 销毁栈

    return 0;  // 返回 0
}

示例演示：

后序遍历的顺序是：左子树 -> 右子树 -> 根节点。

初始化栈 pstack 为空，当前节点 pnode 为根节点 1。
第一次循环：
- 不断将左子节点入栈并标记为第一次访问，依次入栈 1、2、4。
- 此时栈内元素为 [4, 2, 1]（栈顶在左边）。
- 弹出栈顶元素 4，由于是第一次访问，标记为第二次访问并重新入栈，pnode 指向 4 的右子节点（NULL）。
第二次循环：
- 由于 pnode 为 NULL，不会再向左走。
- 弹出栈顶元素 4，由于是第二次访问，打印 4。
- 弹出栈顶元素 2，由于是第一次访问，标记为第二次访问并重新入栈，pnode 指向 2 的右子节点 5。
- 将 5 入栈并标记为第一次访问，此时栈内元素为 [5, 2]。
第三次循环：
- 弹出栈顶元素 5，由于是第一次访问，标记为第二次访问并重新入栈，pnode 指向 5 的右子节点（NULL）。
第四次循环：
- 由于 pnode 为 NULL，不会再向左走。
- 弹出栈顶元素 5，由于是第二次访问，打印 5。
- 弹出栈顶元素 2，由于是第二次访问，打印 2。
- 弹出栈顶元素 1，由于是第一次访问，标记为第二次访问并重新入栈，pnode 指向 1 的右子节点 3。
- 将 3 入栈并标记为第一次访问，此时栈内元素为 [3, 1]。
第五次循环：
- 弹出栈顶元素 3，由于是第一次访问，标记为第二次访问并重新入栈，pnode 指向 3 的右子节点（NULL）。
第六次循环：
- 由于 pnode 为 NULL，不会再向左走。
- 弹出栈顶元素 3，由于是第二次访问，打印 3。
- 弹出栈顶元素 1，由于是第二次访问，打印 1。
- 栈为空，遍历结束。

最终后序遍历的结果为：4 5 2 3 1。

2 queue.c

实现队列的基本操作，包括创建队列、判断队列是否为空、入队、出队和销毁队列，同时还提供了计算二叉树高度的函数。

2.1 创建一个新的队列

// 函数：create_queue
// 功能：创建一个新的队列
// 参数：无
// 返回值：指向新创建队列头节点的指针，如果内存分配失败则返回 NULL
struct list_head *create_queue(void)
{
    struct list_head *phead = NULL;  // 定义一个指向队列头节点的指针，并初始化为 NULL

    phead = malloc(sizeof(struct list_head));  // 为队列头节点分配内存
    if (NULL == phead)  // 检查内存分配是否失败
    {
        return NULL;  // 如果内存分配失败，返回 NULL
    }

    INIT_LIST_HEAD(phead);  // 初始化队列头节点的链表结构

    return phead;  // 返回队列头节点的指针
}

2.2 判断队列是否为空

// 函数：is_empty_queue
// 功能：判断队列是否为空
// 参数：phead - 指向队列头节点的指针
// 返回值：如果队列为空返回非零值，否则返回 0
int is_empty_queue(struct list_head *phead)
{
    return list_empty(phead);  // 调用 list_empty 函数判断队列是否为空
}

2.3 将一个树节点数据入队

// 函数：enter_queue
// 功能：将一个树节点数据入队
// 参数：phead - 指向队列头节点的指针，tmpdata - 要入队的树节点指针
// 返回值：入队成功返回 0，内存分配失败返回 -1
int enter_queue(struct list_head *phead, treenode_t *tmpdata)
{
    queue_t *pnode = NULL;  // 定义一个指向队列节点的指针，并初始化为 NULL

    pnode = malloc(sizeof(queue_t));  // 为队列节点分配内存
    if (NULL == pnode)  // 检查内存分配是否失败
    {
        return -1;  // 如果内存分配失败，返回 -1
    }

    pnode->data = tmpdata;  // 将树节点指针赋值给队列节点的数据域

    list_add_tail(&pnode->node, phead);  // 将队列节点添加到队列的尾部

    return 0;  // 入队成功，返回 0
}

2.4 将队首元素出队

// 函数：quit_queue
// 功能：将队首元素出队
// 参数：phead - 指向队列头节点的指针
// 返回值：出队的树节点指针，如果队列为空则返回 NULL
treenode_t *quit_queue(struct list_head *phead)
{
    treenode_t *tmpdata;  // 定义一个指向树节点的指针，用于存储出队的树节点指针
    queue_t *pnode = NULL;  // 定义一个指向队列节点的指针，并初始化为 NULL

    pnode = list_entry(phead->next, queue_t, node);  // 通过链表节点获取队列节点的地址
    tmpdata = pnode->data;  // 获取队列节点的数据域，即树节点指针
    list_del(&pnode->node);  // 从链表中删除队列节点
    free(pnode);  // 释放队列节点的内存

    return tmpdata;  // 返回出队的树节点指针
}

2.5 销毁队列

// 函数：destroy_queue
// 功能：销毁队列
// 参数：pphead - 指向队列头节点指针的指针
// 返回值：返回 -1
int destroy_queue(struct list_head **pphead)
{
    while (!is_empty_queue(*pphead))  // 当队列不为空时
    {
        quit_queue(*pphead);  // 不断将队首元素出队
    }

    free(*pphead);  // 释放队列头节点的内存
    *pphead = NULL;  // 将队列头节点指针置为 NULL

    return -1;  // 返回 -1
}

2.6 获取二叉树的高度

// 函数：get_btree_high
// 功能：获取二叉树的高度
// 参数：proot - 指向二叉树根节点的指针
// 返回值：二叉树的高度
int get_btree_high(treenode_t *proot)
{
    int left_high = 0;  // 定义左子树的高度，初始化为 0
    int right_high = 0;  // 定义右子树的高度，初始化为 0

    if (NULL == proot)  // 如果根节点为空
    {
        return 0;  // 二叉树高度为 0
    }

    left_high = get_btree_high(proot->pleftchild);  // 递归计算左子树的高度
    right_high = get_btree_high(proot->prightchild);  // 递归计算右子树的高度

    return (left_high > right_high ? left_high : right_high) + 1;  // 返回左右子树高度的最大值加 1
}

3 stack.c

实现栈的基本操作，包括创建栈、压栈、弹栈和销毁栈。

3.1 创建一个新的栈

// 函数：create_stack
// 功能：创建一个新的栈
// 参数：无
// 返回值：指向新创建栈头节点的指针，如果内存分配失败则返回 NULL
struct list_head *create_stack(void)
{
    struct list_head *phead = NULL;  // 定义一个指向栈头节点的指针，并初始化为 NULL

    phead = malloc(sizeof(struct list_head));  // 为栈头节点分配内存
    if (NULL == phead)  // 检查内存分配是否失败
    {
        return NULL;  // 如果内存分配失败，返回 NULL
    }
  
    INIT_LIST_HEAD(phead);  // 初始化栈头节点的链表结构

    return phead;  // 返回栈头节点的指针
}

3.2 将一个树节点数据压入栈

// 函数：push_stack
// 功能：将一个树节点数据压入栈
// 参数：phead - 指向栈头节点的指针，tmpdata - 要压入栈的树节点指针
// 返回值：压栈成功返回 0，内存分配失败返回 -1
int push_stack(struct list_head *phead, treenode_t *tmpdata)
{
    stack_node_t *ptmpnode = NULL;  // 定义一个指向栈节点的指针，并初始化为 NULL

    ptmpnode = malloc(sizeof(stack_node_t));  // 为栈节点分配内存
    if (NULL == ptmpnode)  // 检查内存分配是否失败
    {
        return -1;  // 如果内存分配失败，返回 -1
    }

    ptmpnode->data = tmpdata;  // 将树节点指针赋值给栈节点的数据域

    list_add(&ptmpnode->node, phead);  // 将栈节点添加到栈的头部

    return 0;  // 压栈成功，返回 0
}

3.3 将栈顶元素弹出

// 函数：pop_stack
// 功能：将栈顶元素弹出
// 参数：phead - 指向栈头节点的指针
// 返回值：弹出的树节点指针，如果栈为空则返回 NULL
treenode_t *pop_stack(struct list_head *phead)
{
    stack_node_t *ptmpnode = NULL;  // 定义一个指向栈节点的指针，并初始化为 NULL
    treenode_t *tmpdata = 0;  // 定义一个指向树节点的指针，用于存储弹出的树节点指针

    if (IS_EMPTY_STACK(phead))  // 检查栈是否为空
    {
        return NULL;  // 如果栈为空，返回 NULL
    }

    ptmpnode = list_entry(phead->next, stack_node_t, node);  // 通过链表节点获取栈节点的地址

    list_del(&ptmpnode->node);  // 从链表中删除栈节点

    tmpdata = ptmpnode->data;  // 获取栈节点的数据域，即树节点指针
    free(ptmpnode);  // 释放栈节点的内存
    
    return tmpdata;  // 返回弹出的树节点指针
}

3.4 销毁栈

// 函数：destroy_stack
// 功能：销毁栈
// 参数：pphead - 指向栈头节点指针的指针
// 返回值：返回 0
int destroy_stack(struct list_head **pphead)
{
    while (!IS_EMPTY_STACK(*pphead))  // 当栈不为空时
    {
        pop_stack(*pphead);  // 不断将栈顶元素弹出
    }
    free(*pphead);  // 释放栈头节点的内存
    *pphead = NULL;  // 将栈头节点指针置为 NULL

    return 0;  // 返回 0
}

4 main.c

创建一个完全二叉树，并依次调用不同的遍历函数进行测试，最后销毁二叉树。

4.1 测试二叉树的各种遍历操作

// 函数：main
// 功能：程序的入口函数，用于测试二叉树的各种遍历操作
// 参数：无
// 返回值：返回 0 表示程序正常结束
int main(void)
{
    treenode_t *proot = NULL;  // 定义一个指向二叉树根节点的指针，并初始化为 NULL

    proot = create_complete_btree(1, 5);  // 创建一个完全二叉树，根节点编号从 1 开始，节点编号最大为 5
    
    printf("前序遍历:");  // 输出提示信息
    preoder_traversal_btree(proot);  // 前序遍历二叉树
    printf("\n");  // 换行

    printf("中序遍历:");  // 输出提示信息
    inoder_traversal_btree(proot);  // 中序遍历二叉树
    printf("\n");  // 换行

    printf("后序遍历:");  // 输出提示信息
    postoder_traversal_btree(proot);  // 后序遍历二叉树
    printf("\n");  // 换行

    printf("层序遍历:");  // 输出提示信息
    layerout_traversal_tree(proot);  // 层序遍历二叉树
    printf("\n");  // 换行

    printf("高度: %d\n", get_btree_high(proot));  // 输出二叉树的高度

    printf("前序遍历:");  // 输出提示信息
    preorder_btree_stack(proot);  // 使用栈实现前序遍历二叉树
    printf("\n");  // 换行

    printf("中序遍历:");  // 输出提示信息
    inorder_btree_stack(proot);  // 使用栈实现中序遍历二叉树
    printf("\n");  // 换行

    printf("后序遍历:");  // 输出提示信息
    postorder_btree_stack(proot);  // 使用栈实现后序遍历二叉树
    printf("\n");  // 换行

    destroy_btree(proot);  // 销毁二叉树
    proot = NULL;  // 将根节点指针置为 NULL

    return 0;  // 程序正常结束，返回 0
}

二、哈希表

实现一个简单的哈希表，主要包括以下几个部分：

哈希表的创建：create_hashtable函数用于创建一个哈希表，即一个链表数组。
节点比较函数：asc_compare函数用于按升序比较两个链表节点中存储的数值。
插入操作：insert_hashtable函数用于向哈希表中插入一个数值。
打印操作：show_hashtable函数用于打印哈希表中的所有数值。
查找操作：find_hashtable函数用于在哈希表中查找指定的数值。
删除操作：delete_hashtable函数用于从哈希表中删除指定的数值。
销毁操作：destroy_hashtable函数用于销毁哈希表，释放所有内存。

2.1 创建一个哈希表

// 函数：create_hashtable
// 功能：创建一个哈希表
// 参数：无
// 返回值：指向哈希表（链表数组）的指针，如果内存分配失败则返回NULL
struct list_head *create_hashtable(void)
{   
    int i = 0;  // 初始化循环变量i为0，用于遍历哈希表的每个链表
    struct list_head *pheadlist = NULL;  // 定义一个指向链表数组的指针pheadlist，并初始化为NULL
    
    pheadlist = malloc(MAXNUM * sizeof(struct list_head));  // 为哈希表（链表数组）分配内存，大小为MAXNUM个struct list_head的大小
    if (NULL == pheadlist)  // 检查内存分配是否失败
    {
        return NULL;  // 如果内存分配失败，返回NULL
    }

    for (i = 0; i < MAXNUM; i++)  // 遍历哈希表的每个链表
    {
        INIT_LIST_HEAD(&pheadlist[i]);  // 初始化每个链表的头节点
    }

    return pheadlist;  // 返回指向哈希表（链表数组）的指针
}

2.2 按升序比较两个链表节点中存储的数值

// 函数：asc_compare
// 功能：按升序比较两个链表节点中存储的数值
// 参数：pnew - 新节点的指针，pnode - 当前节点的指针
// 返回值：如果新节点的值大于当前节点的值，返回1；如果小于，返回-1；如果相等，返回0
static int asc_compare(struct list_head *pnew, struct list_head *pnode)
{
    if (list_entry(pnew, hashnode_t, node)->num > list_entry(pnode, hashnode_t, node)->num)  // 比较新节点的值和当前节点的值
    {
        return 1;  // 新节点的值大于当前节点的值，返回1
    }
    else if (list_entry(pnew, hashnode_t, node)->num < list_entry(pnode, hashnode_t, node)->num)  // 比较新节点的值和当前节点的值
    {
        return -1;  // 新节点的值小于当前节点的值，返回-1
    }
    else 
    {
        return 0;  // 新节点的值等于当前节点的值，返回0
    }
}

2.3 向哈希表中插入一个数值

// 函数：insert_hashtable
// 功能：向哈希表中插入一个数值
// 参数：pheadlist - 指向哈希表（链表数组）的指针，num - 要插入的数值
// 返回值：插入成功返回0，内存分配失败返回-1
//插入
int insert_hashtable(struct list_head *pheadlist, int num)
{
    int key = 0;  // 初始化哈希键值为0
    hashnode_t *ptmpnode = NULL;  // 定义一个指向哈希节点的指针ptmpnode，并初始化为NULL

    ptmpnode = malloc(sizeof(hashnode_t));  // 为新的哈希节点分配内存
    if (NULL == ptmpnode)  // 检查内存分配是否失败
    {
        return -1;  // 如果内存分配失败，返回-1
    }

    ptmpnode->num = num;  // 将待插入的数值存储到新节点中

    key = num % MAXNUM;  // 计算哈希键值

    list_add_order(&ptmpnode->node, &pheadlist[key], asc_compare);  // 将新节点按升序插入到对应的链表中

    return 0;  // 插入成功，返回0
}

2.4 打印哈希表中的所有数值

// 函数：show_hashtable
// 功能：打印哈希表中的所有数值
// 参数：pheadlist - 指向哈希表（链表数组）的指针
// 返回值：始终返回0
//打印
int show_hashtable(struct list_head *pheadlist)
{
    int i = 0;  // 初始化循环变量i为0，用于遍历哈希表的每个链表
    struct list_head *ptmpnode = NULL;  // 定义一个指向链表节点的指针ptmpnode，并初始化为NULL

    for (i = 0; i < MAXNUM; i++)  // 遍历哈希表的每个链表
    {
        printf("%d:", i);  // 打印链表的索引
        list_for_each(ptmpnode, &pheadlist[i])  // 遍历当前链表的每个节点
        {
            printf("%d ", list_entry(ptmpnode, hashnode_t, node)->num);  // 打印节点中存储的数值
        }
        printf("\n");  // 换行
    }

    return 0;  // 函数执行完毕，返回0
}

2.5 在哈希表中查找指定的数值

// 函数：find_hashtable
// 功能：在哈希表中查找指定的数值
// 参数：pheadlist - 指向哈希表（链表数组）的指针，num - 要查找的数值
// 返回值：如果找到，返回指向该数值所在节点的指针；如果未找到，返回NULL
//查找
hashnode_t *find_hashtable(struct list_head *pheadlist, int num)
{
    int key = 0;  // 初始化哈希键值为0
    struct list_head *ptmpnode = NULL;  // 定义一个指向链表节点的指针ptmpnode，并初始化为NULL

    key = num % MAXNUM;  // 计算哈希键值
    list_for_each(ptmpnode, &pheadlist[key])  // 遍历对应的链表
    {
        if (list_entry(ptmpnode, hashnode_t, node)->num == num)  // 检查当前节点的值是否等于要查找的数值
        {
            return list_entry(ptmpnode, hashnode_t, node);  // 如果找到，返回指向该节点的指针
        }
        else if (list_entry(ptmpnode, hashnode_t, node)->num > num)  // 如果当前节点的值大于要查找的数值
        {
            break;  // 由于链表是按升序排列的，后面的节点的值会更大，所以可以提前退出循环
        }
    }
    
    return NULL;  // 未找到，返回NULL
}

2.6 从哈希表中删除指定的数值

// 函数：delete_hashtable
// 功能：从哈希表中删除指定的数值
// 参数：parray - 指向哈希表（链表数组）的指针，num - 要删除的数值
// 返回值：删除的节点数量
//删除
int delete_hashtable(struct list_head *parray, int num)
{
    hashnode_t *ptmpnode = NULL;  // 定义一个指向哈希节点的指针ptmpnode，并初始化为NULL
    int cnt = 0;  // 初始化删除节点的计数器为0

    while (1)  // 循环删除所有匹配的节点
    {
        ptmpnode = find_hashtable(parray, num);  // 查找要删除的节点
        if (NULL == ptmpnode)  // 如果未找到
        {
            break;  // 退出循环
        }

        list_del(&ptmpnode->node);  // 从链表中删除该节点
        free(ptmpnode);  // 释放该节点的内存
        cnt++;  // 计数器加1
    }
    
    return cnt;  // 返回删除的节点数量
}

2.7 销毁哈希表，释放所有内存

// 函数：destroy_hashtable
// 功能：销毁哈希表，释放所有内存
// 参数：parray - 指向哈希表（链表数组）的指针
// 返回值：始终返回0
//销毁
int destroy_hashtable(struct list_head *parray)
{
    int i = 0;  // 初始化循环变量i为0，用于遍历哈希表的每个链表
    hashnode_t *ptmpnode = NULL;  // 定义一个指向哈希节点的指针ptmpnode，并初始化为NULL
    hashnode_t *pnextnode = NULL;  // 定义一个指向哈希节点的指针pnextnode，并初始化为NULL

    for (i = 0; i < MAXNUM; i++)  // 遍历哈希表的每个链表
    {
        list_for_each_entry_safe(ptmpnode, pnextnode, &parray[i], node)  // 安全地遍历链表的每个节点
        {
            free(ptmpnode);  // 释放节点的内存
        }
    }

    free(parray);  // 释放哈希表（链表数组）的内存

    return 0;  // 函数执行完毕，返回0
}

三、常见的排序和查找算法

3.1 冒泡排序

// 冒泡排序函数，对传入的整数数组进行排序
// 参数：parray 是指向整数数组的指针，len 是数组的长度
// 返回值：0 表示排序成功
int bubble_sort(int *parray, int len)
{
    int i = 0;  // 初始化循环变量 i 为 0，用于内层循环控制
    int j = 0;  // 初始化循环变量 j 为 0，用于外层循环控制
    int temp = 0; // 临时变量，用于交换数组元素的值

    for (j = 0; j < len-1; j++)  // 外层循环，控制排序的轮数，一共需要 len-1 轮
    {
        for (i = 0; i < len-1-j; i++)  // 内层循环，每一轮比较相邻元素并交换，比较次数逐渐减少
        {
            if (parray[i] > parray[i+1])  // 如果当前元素比下一个元素大
            {
                temp = parray[i];  // 将当前元素的值保存到临时变量 temp 中
                parray[i] = parray[i+1];  // 将下一个元素的值赋给当前元素
                parray[i+1] = temp;  // 将临时变量 temp 的值赋给下一个元素，完成交换
            }
        }
    }

    return 0;  // 排序完成，返回 0 表示成功
}

3.2 选择排序

// 选择排序函数，对传入的整数数组进行排序
// 参数：parray 是指向整数数组的指针，len 是数组的长度
// 返回值：0 表示排序成功
int select_sort(int *parray, int len)
{
    int i = 0;  // 初始化循环变量 i 为 0，用于内层循环控制
    int j = 0;  // 初始化循环变量 j 为 0，用于外层循环控制
    int min = 0; // 用于记录每一轮中最小元素的下标
    int temp = 0; // 临时变量，用于交换数组元素的值

    for (j = 0; j < len-1; j++)  // 外层循环，控制排序的轮数，一共需要 len-1 轮
    {
        min = j;  // 假设当前轮的第一个元素是最小的，记录其下标
        for (i = j+1; i < len; i++)  // 内层循环，从当前轮的下一个元素开始遍历，找到最小元素的下标
        {
            if (parray[i] < parray[min])  // 如果找到比当前最小元素还小的元素
            {
                min = i;  // 更新最小元素的下标
            }
        }
        if (min != j)  // 如果最小元素的下标不是当前轮的第一个元素的下标
        {
            temp = parray[min];  // 将最小元素的值保存到临时变量 temp 中
            parray[min] = parray[j];  // 将当前轮的第一个元素的值赋给最小元素的位置
            parray[j] = temp;  // 将临时变量 temp 的值赋给当前轮的第一个元素，完成交换
        }
    }

    return 0;  // 排序完成，返回 0 表示成功
}

3.3 插入排序

// 插入排序函数，对传入的整数数组进行排序
// 参数：parray 是指向整数数组的指针，len 是数组的长度
// 返回值：0 表示排序成功
int insert_sort(int *parray, int len)
{
    int j = 0;  // 初始化循环变量 j 为 0，用于外层循环控制
    int i = 0;  // 初始化循环变量 i 为 0，用于内层循环控制
    int tmp = 0; // 临时变量，用于保存当前要插入的元素的值

    for (j = 1; j < len; j++)  // 外层循环，从第二个元素开始，依次将元素插入到已排序的序列中
    {
        tmp = parray[j];  // 保存当前要插入的元素的值
        for (i = j; i > 0 && tmp < parray[i-1]; i--)  // 内层循环，将比当前元素大的元素依次向后移动
        {
            parray[i] = parray[i-1];  // 将前一个元素的值赋给当前元素
        }
        parray[i] = tmp;  // 将当前要插入的元素插入到正确的位置
    }

    return 0;  // 排序完成，返回 0 表示成功
}

假设有一个数组 [5, 3, 4, 6, 2]

初始状态：
- 已排序部分：[5]
- 未排序部分：[3, 4, 6, 2]
第一次插入（处理元素 3）：
- 待插入元素 tmp = 3
- 比较 3 和 5，因为 3 < 5，所以将 5 后移一位，得到 [5, 5]
- 插入 3，得到 [3, 5]
- 已排序部分：[3, 5]
- 未排序部分：[4, 6, 2]
第二次插入（处理元素 4）：
- 待插入元素 tmp = 4
- 比较 4 和 5，因为 4 < 5，所以将 5 后移一位，得到 [3, 5, 5]
- 比较 4 和 3，因为 4 > 3，所以停止后移
- 插入 4，得到 [3, 4, 5]
- 已排序部分：[3, 4, 5]
- 未排序部分：[6, 2]
第三次插入（处理元素 6）：
- 待插入元素 tmp = 6
- 比较 6 和 5，因为 6 > 5，所以不需要后移
- 插入 6，得到 [3, 4, 5, 6]
- 已排序部分：[3, 4, 5, 6]
- 未排序部分：[2]
第四次插入（处理元素 2）：
- 待插入元素 tmp = 2
- 比较 2 和 6，因为 2 < 6，所以将 6 后移一位，得到 [3, 4, 5, 6, 6]
- 比较 2 和 5，因为 2 < 5，所以将 5 后移一位，得到 [3, 4, 5, 5, 6]
- 比较 2 和 4，因为 2 < 4，所以将 4 后移一位，得到 [3, 4, 4, 5, 6]
- 比较 2 和 3，因为 2 < 3，所以将 3 后移一位，得到 [3, 3, 4, 5, 6]
- 插入 2，得到 [2, 3, 4, 5, 6]
- 已排序部分：[2, 3, 4, 5, 6]
- 未排序部分：[]

最终，数组完成排序，结果为 [2, 3, 4, 5, 6]。

3.4 希尔排序

// 希尔排序函数，对传入的整数数组进行排序
// 参数：parray 是指向整数数组的指针，len 是数组的长度
// 返回值：0 表示排序成功
int shell_sort(int *parray, int len)
{
    int n = 0;  // 初始化步长 n 为 0
    int j = 0;  // 初始化循环变量 j 为 0，用于内层循环控制
    int i = 0;  // 初始化循环变量 i 为 0，用于内层循环控制
    int tmp = 0; // 临时变量，用于保存当前要插入的元素的值

    for (n = len/2; n >= 1; n /= 2)  // 外层循环，控制步长，步长逐渐缩小到 1
    {
        for (j = n; j < len; j++)  // 中层循环，从步长位置开始，依次将元素插入到已排序的序列中
        {
            tmp = parray[j];  // 保存当前要插入的元素的值
            for (i = j; i > n-1 && tmp < parray[i-n]; i -= n)  // 内层循环，将比当前元素大的元素依次向后移动
            {
                parray[i] = parray[i-n];  // 将前一个元素的值赋给当前元素
            }
            parray[i] = tmp;  // 将当前要插入的元素插入到正确的位置
        }
    }

    return 0;  // 排序完成，返回 0 表示成功
}

数组 [10, 9, 8, 7, 6, 5, 4, 3, 2, 1]

初始状态

数组：[10, 9, 8, 7, 6, 5, 4, 3, 2, 1]
数组长度 n = 10，初始增量 gap = n / 2 = 5

第一轮排序，`gap = 5`

此时数组被分为 5 个子序列：

子序列 1：[10, 5]
子序列 2：[9, 4]
子序列 3：[8, 3]
子序列 4：[7, 2]
子序列 5：[6, 1]

对每个子序列进行插入排序：

子序列 1：[10, 5] 排序后为 [5, 10]
子序列 2：[9, 4] 排序后为 [4, 9]
子序列 3：[8, 3] 排序后为 [3, 8]
子序列 4：[7, 2] 排序后为 [2, 7]
子序列 5：[6, 1] 排序后为 [1, 6]

将排序后的子序列放回原数组，得到：[5, 4, 3, 2, 1, 10, 9, 8, 7, 6]

第二轮排序，`gap = 5 / 2 = 2`

此时数组被分为 2 个子序列：

子序列 1：[5, 3, 1, 9, 7]
子序列 2：[4, 2, 10, 8, 6]

对每个子序列进行插入排序：

子序列 1：
- 初始 [5, 3, 1, 9, 7]
- 处理 3，与 5 比较，交换，得到 [3, 5, 1, 9, 7]
- 处理 1，依次与 5、3 比较并交换，得到 [1, 3, 5, 9, 7]
- 处理 9，无需交换，得到 [1, 3, 5, 9, 7]
- 处理 7，与 9 比较并交换，得到 [1, 3, 5, 7, 9]
子序列 2：
- 初始 [4, 2, 10, 8, 6]
- 处理 2，与 4 比较并交换，得到 [2, 4, 10, 8, 6]
- 处理 10，无需交换，得到 [2, 4, 10, 8, 6]
- 处理 8，与 10 比较并交换，得到 [2, 4, 8, 10, 6]
- 处理 6，依次与 10、8 比较并交换，得到 [2, 4, 6, 8, 10]

将排序后的子序列放回原数组，得到：[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

第三轮排序，`gap = 2 / 2 = 1`

此时 gap = 1，相当于进行普通的插入排序，但由于前面的操作已经让数组基本有序，所以这一轮排序效率较高。

对整个数组 [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] 进行插入排序，数组已经有序，无需进行交换操作。

最终排序结果为：[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

查看全文

http://www.kler.cn/a/549191.html

【信息学奥赛一本通 C++题解】1288：三角形最佳路径问题

PAT乙级真题 — 1084 外观数列(java)

python 视频处理库moviepy 设置字幕

微信小程序markdown转换为wxml（uniapp开发）

使用 MySQL 从 JSON 字符串提取数据

Blazor-设置组件焦点

记忆力训练day19

【Python】错误异常

PHP基础部分

HTTP、HTTPS区别可靠性及POST为什么比GET安全的探讨

光化学腐蚀法制作DIY钢网的制作流程

qt:对象树，窗口坐标，信号与槽

【网络】协议与网络版计算器

BMS项目-面试及答疑整理

linux--关于linux文件IO(2) open、read、lseek、stat

C#中的动态类型用法总结带演示代码

【函数题】6-12 二叉搜索树的操作集

AI程序员(aider)+ollama+DeepSeek-R1安装配置和使用

「vue3-element-admin」Vue3 + TypeScript 项目整合 Animate.css 动画效果实战指南

(学习总结24)Linux 基本命令2

一、二叉树、栈、队列

1 btree.c

1.1 创建一个完全二叉树

1.2 前序遍历二叉树

1.2.1 示例演示

1.3 中序遍历二叉树

1.4 后序遍历二叉树

1.5 层序遍历二叉树

1.6 销毁二叉树

1.7 使用栈实现二叉树的前序遍历

1.8 使用栈实现二叉树的中序遍历

1.9 使用栈实现二叉树的后序遍历

2 queue.c

2.1 创建一个新的队列

2.2 判断队列是否为空

2.3 将一个树节点数据入队

2.4 将队首元素出队

2.5 销毁队列

2.6 获取二叉树的高度

3 stack.c

3.1 创建一个新的栈

3.2 将一个树节点数据压入栈

3.3 将栈顶元素弹出

3.4 销毁栈

4 main.c

4.1 测试二叉树的各种遍历操作

二、哈希表

2.1 创建一个哈希表

2.2 按升序比较两个链表节点中存储的数值

2.3 向哈希表中插入一个数值

2.4 打印哈希表中的所有数值

2.5 在哈希表中查找指定的数值

2.6 从哈希表中删除指定的数值

2.7 销毁哈希表，释放所有内存

三、常见的排序和查找算法

3.1 冒泡排序

3.2 选择排序

3.3 插入排序

3.4 希尔排序

初始状态

第一轮排序，gap = 5

第二轮排序，gap = 5 / 2 = 2

第三轮排序，gap = 2 / 2 = 1

相关文章：

第一轮排序，`gap = 5`

第二轮排序，`gap = 5 / 2 = 2`

第三轮排序，`gap = 2 / 2 = 1`