当前位置: 首页 > news >正文

【数据结构初阶】七、非线性表里的二叉树(堆的实现 -- C语言顺序结构)

=========================================================================

相关代码gitee自取

C语言学习日记: 加油努力 (gitee.com)

 =========================================================================

接上期

【数据结构初阶】六、线性表中的队列(链式结构实现队列)-CSDN博客

 =========================================================================

                     

1 . 非线性表里的 树(Tree)

树的概念及结构:

            

树的概念

是一种非线性的数据结构
它是 n(n>=0) 个有限节点组成一个具有层次关系的集合
把它叫做树是因为它看起来像一棵倒挂的树,也就是说它是根朝上,而叶朝下的。
( jie点线性结构 -- 结点  ;非线性结构 -- 节点 )

               

树的结构

  • 有一个特殊的节点,称为根节点,根节点没有前驱节点
                 
  • 除根节点外其余节点分成 M(M>0) 互不相交的集合 T1 、T2 、……Tm ,
    其中每一个集合 Ti(1<= i <= m) 又是一棵结构与树类似的子树
    每棵子树的根节点有且只有一个前驱节点可以有零个或多个后继节点
                   
  • 递归定义
                 
  • 树形结构中,子树之间不能有交集否则就不是树形结构
图示:

                

树的其它相关概念:

(有些概念对应意思不好理解,可以结合看下列示例图的例子)

概念名称对应意思下图中例子
节点的度一个节点含有子树个数 称为 该节点的度节点A的度为6
🔺叶节点
(终端节点)
度为0节点 称为 叶节点节点BCH……为叶节点

🔺分支节点
(非终端节点)

度不为0节点 称为 分支节点节点DEF……为分支节点
🔺父节点
(双亲节点)
一个节点含有子节点
则这个节点 称为 其子节点的父节点
节点A节点B的父节点
🔺子节点
(孩子节点)
一个节点含有的子树的根节点 称为 该节点的子节点节点B节点A的子节点
兄弟节点具有相同父节点的节点 互称为 兄弟节点节点BC是兄弟节点
树的度一棵树中最大的节点的度 称为 树的度下图中树的度为6
🔺节点的层次从根开始定义起
第一(零)层根的子节点第二(一)层
以此类推建议从第一层起算空树可用零层表示
节点A所在层为第一层,
节点B所在层为第二层……
🔺树的高度
(树的深度)
树中节点的最大层次下图中树的高度(深度)为4
堂兄弟节点父节点(双亲节点)在同一层的节点 互称为 堂兄弟节点HI互为兄弟节点
🔺节点的祖先从根到该节点上的所有的分支节点 都是 祖先节点A是所有节点的祖先
🔺子孙以某节点为根的子树中任一节点
都称为 该节点的子孙
所有节点都是节点A的子孙
森林m(m>0)棵互不相交的树组成的集合 称为 森林
示例图:

                     

                    


                    

树的存储(表示):

                  

树的表示方式:

  • 树结构相对线性表就比较复杂了,要存储表示起来比较麻烦了,
    既要保存值域也要保存节点和节点之间的关系
                      
  • 实际中有很多种表示方式如:
    双亲表示法孩子表示法孩子双亲表示法以及孩子兄弟表示法等,
    我们这里就简单了解其中最常用孩子兄弟表示法
    树结构的最优设计

                          

(左)孩子(右)兄弟表示法结构:

                     //树中各节点数据域存储数据的类型:typedef int DataType;//(左)孩子(右)兄弟表示法:struct TreeNode{//节点中的数据域:DataType data;//第一个孩子节点 -- 最左边的孩子节点:struct TreeNode* firstchild;//指向该节点下一个兄弟节点 -- 右边的兄弟节点:struct TreeNode* nextbrother;};

                

这个表示法本质是用链表实现树:
  • firstchild 指针 -- 相当于链表头指针找到当前节点下一层的头节点
                    
  • nextbrother 指针 -- 相当于链表遍历指针,可以往后遍历该层节点
                     
使用示例图:

               

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

             

2 . 树中的 二叉树(Binary Tree)

二叉树的概念及结构:

            

二叉树的概念

一棵二叉树节点的一个有限集合该集合满足

  • 或者为空
  • 或者由一个根节点加上两棵别称为左子树右子树二叉树组成

             

二叉树的结构

  • 二叉树不存在度大于2的节点
    ( 所以节点的度可能是 0 即空树,也可能是 1 或 2 )

                     
  • 二叉树的子树左右之分次序不能颠倒,因此二叉树是有序树
图示:

               

注意:

对于任意二叉树
都是由以下几种情况复合而成

                     

                    


                    

特殊的二叉树

                   

满二叉树

一个二叉树,如果每一个层的节点数都达到最大值,则这个二叉树就是满二叉树
也就是说,如果一个二叉树的高度 k ,且节点总数2^k - 1,则它就是满二叉树

图示:

                     

                     

完全二叉树

完全二叉树效率很高的数据结构,完全二叉树是满二叉树引出来的概念
对于高度 K 的,有 n 个节点二叉树
当且仅当每一个节点与高度为 K 满二叉树中编号从 1  n 的节点一一对应时,
称之为完全二叉树
          

简单理解:

假设树的高度K , K-1 "满"的
最后一层不一定满至少有一个节点),且树从左到右连续
该树即完全二叉树

                  

注:

满二叉树一种特殊的完全二叉树

完全二叉树的最后一层为满是满二叉树

所以假设完全二叉树的高度为 K ,
节点总数最高2^K - 1  ;节点总数最少(最后一层只有一个节点)是 2^(K - 1) 

                 

图示:

                     

                    


                    

二叉树的存储结构

                 

二叉树一般可以使用两种结构存储
一种顺序结构,一种链式结构

              

顺序结构

  • 顺序结构存储就是使用 数组 来存储
    任意位置通过下标可以找到父亲或者孩子,数组中下标为0的元素为根节点

                   
  • 使用数组进行存储一般只适合表示完全二叉树满二叉树),
    因为不是完全二叉树的话会有空间的浪费
                      
  • 现实使用中只有  才会使用数组来存储
                            
  • 二叉树顺序存储物理上一个数组,在逻辑上一颗二叉树
                        
顺序结构(数学)规律:
  • 通过父节点下标找到子节点下标):
    左节点  ==》  leftchild  =  parent * 2 + 1
    右节点  ==》  rightchild  =  parent * 2 + 2

                   
  • 通过子节点下标找到父节点下标):
    父节点  ==》 parent  = (child - 1) / 2
    通过观察可以发现左节点下标都是奇数右节点下标都是偶数
    (偶数-1) / 2 向下取整得到偶数父节点下标
    所以一个公式即可求得父节点
                   
  • 该规律只适用于完全二叉树,因为完全二叉树从左到右是连续的
    非完全二叉树也可以使用,但因为节点不一定是连续的
    所以数组中有些位置不存储元素,导致空间浪费
图示:

         

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

             

3 . 完全二叉树中的 堆(Heap)

堆的概念及结构

          

堆的概念

如果有一个关键码的集合  K = \left \{ k_{0}, k_{1}, k_{2}, ...,k_{n-1}\right \} ,
它的所有元素完全二叉树的顺序存储方式存储在一个一维数组并满足

  • _{}^{}K_{i} \leqslant K_{2*i+1}  K_{i} \leqslant K_{2*i+2}

    ( K_{i}\geqslant K_{2*i+1} K_{i}\geqslant K_{2*i+2}

    其中 i = 012……

称为小堆大堆
  • 根节点最大的堆叫做最大堆大根堆 -- 大堆
  • 根节点最小的堆叫做最小堆小根堆 -- 小堆

              

简单理解:

小堆 -- 各父节点值总是小于等于其子节点值各子节点值总是大于等于其父节点值
大堆 -- 各父节点值总是大于等于其子节点值各子节点值总是小于等于其父节点值

              

堆的结构

  • 堆中某个节点的值总是不大于或不小于其父节点的值
                  
  • 总是一棵完全二叉树
图示:

         

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

             

4 . 堆的实现

使用二叉树的顺序结构实现堆

  • 普通的二叉树不适合用数组顺序结构来存储,因为会存在大量的空间浪费
                 
  • 完全二叉树适合使用顺序结构存储
    所以现实中通常把一种完全二叉树使用顺序结构的数组来存储

                    
  • 需要注意的是这里的堆操作系统虚拟进程地址空间中的堆是两码事
    一个是数据结构一个是操作系统中管理内存的一块区域分段
                     

(详细解释在图片的注释中,代码分文件放下一标题处)

                             

实现具体功能前的准备工作

  • 堆头文件中包含之后所需头文件
                  
  • 定义节点值(堆底层数组元素)的类型
                  
  • 定义堆类型
图示

            

            

---------------------------------------------------------------------------------------------

            

HeapInit函数 -- 对堆类型中的成员进行初始化

  • assert断言接收的堆类型指针不为空
                   
  • 堆根节点指针置为NULL
    堆当前节点个数置为0
    堆当前开辟的空间单位置为0
图示

            

            

---------------------------------------------------------------------------------------------

            

HeapDestroy函数 -- 对堆类型进行销毁

  • assert断言接收的堆类型指针不为空
                   
  • 释放堆类型中以a为头开辟的动态空间
                  
  • 堆当前节点个数堆当前开辟的空间单位置为0
图示

            

            

---------------------------------------------------------------------------------------------

            

HeapPrint函数 -- 打印堆中各节点值

  • assert断言接收的堆类型指针不为空
                   
  • 使用for循环循环打印
图示

            

            

---------------------------------------------------------------------------------------------

            

Swap函数 -- 在向上向下调整操作中互换节点位置

  • 向上调整AdjustUp内部函数)和向下调整AdjustDown内部函数
    推插入节点HeapPush函数)和堆删除节点HeapPop操作中的重要步骤
    向上调整操作向下调整操作需要用到Swap函数交换两节点值
                   
  • 该函数实现很简单,创建一个临时变量配合调换两节点值即可
图示

            

            

---------------------------------------------------------------------------------------------

            

AdjustUp内部函数
--
用于在插入节点后(HeapPush函数)向上调整该节点在堆中的位置

  • 通过上面顺序结构中讲到的公式
    通过子节点下标child找到其父节点下标parent
                   
  • 使用while循环进行向上调整
图示

            

            

---------------------------------------------------------------------------------------------

            

(难)HeapPush函数 -- 在堆类型中插入一个节点

  • assert断言接收的堆类型指针不为空
                   
  • 断言后要判断是否需要扩容需要则进行扩容操作检查是否扩容成功
                  
  • 空间足够后将插入节点放入堆
    插入后堆当前节点个数size++
                    
  • 插入节点后调用 向上调整AdjustUp内部函数
    对插入节点在堆中的位置进行调整
    使得插入后整体还是一个堆大堆或小堆
图示

            

            

---------------------------------------------------------------------------------------------

            

HeapInitArray函数 -- 接收一个数组将其初始化为一个堆底层数组

  • 实现向上调试AdjusuUp内部函数后,
    可以运用其来建堆建大堆还是小堆取决于AdjustUp函数内的条件设置),
    相比前面HeapInit初始化函数
    该函数会直接为堆开辟动态空间,并放入各节点值
                   
  • assert断言接收的堆类型指针不为空
    assert断言数组a不为空
                  
  • 开辟动态空间检查开辟情况
                    
  • 堆当前节点个数置为n
    堆当前开辟的空间单位置为n
                        
  • 数组a元素拷贝作为堆底层数组元素
                   
  • 循环向上调整堆中的节点底层数组元素进行建堆
图示

            

            

---------------------------------------------------------------------------------------------

            

AdjustDown内部函数
--
用于在删除根节点后(HeapPush函数)向下调整堆,使其还是一个堆

  • 通过上面顺序结构中讲到的公式
    通过父节点下标parent找到其左子节点下标child

                   
  • 使用while循环循环向下调整堆以小堆为例
                  
  • while循环中,先找出当前两个子节点中的较小子节点下标
                    
  • while循环中找到较小节点下标后
    判断是否需要向下调整执行相应操作
图示

            

            

---------------------------------------------------------------------------------------------

            

(难)HeapPop函数 -- 删除堆类型根节点(删除当前堆中最值)

  • assert断言接收的堆类型指针不为空
    assert断言堆节点个数底层数组元素个数不为0
                   
  • 使用交换节点Swap函数将根节点值和尾节点值交换
    将移至尾部的原根节点删除
                  
  • 使用向下调整AdjustDown内部函数对堆进行向下调整
图示

            

            

---------------------------------------------------------------------------------------------

            

HeapTop函数 -- 获取并返回推根节点值

  • assert断言接收的堆类型指针不为空
    assert断言堆节点个数底层数组元素个数不为0

                   
  • 直接返回根节点值
图示

            

            

---------------------------------------------------------------------------------------------

            

HeapEmpty函数 -- 判断堆类型是否为空

  • assert断言接收的堆类型指针不为空
                   
  • 如果堆节点个数底层数组元素个数为0则说明堆为空
图示

            

            

---------------------------------------------------------------------------------------------

            

总体测试:

            

            

---------------------------------------------------------------------------------------------

            

HeapSort排序函数(难)
--
使用堆中向下调整的操作对普通数组进行排序(升序或降序)

  • 建堆
    将要排序的数组看做一棵完全二叉树
    使用循环向下调整操作从倒数第一个父节点非叶子节点开始向下调整
    调整完成后数组就会符合堆的性质(这里以小堆为例)
    升序 -- 建大堆        ;        降序 -- 建小堆
                   
  • 排序
    使用while循环进行排序
    最小值小堆根节点)和尾元素进行交换

    除最小值的其它值看做堆,进行向下调整选出次大小值
    调整好最尾的一个值再循环调整下一个
图示

                

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

                

5 . 对应代码

Heap.h -- 头文件

#pragma once//在堆头文件中包含之后所需头文件:
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>//定义节点值(堆底层数组元素)的类型:
typedef int HPDataType;//定义堆类型:
typedef struct Heap
{//因为底层是用顺序结构实现,//所以该类型和顺序表类似://指向堆节点的指针://(指向堆底层数组的首元素)HPDataType* a;//堆当前节点个数://(堆底层数组的元素个数)int size;//堆当前开辟的空间单位://(堆底层数组动态开辟的空间单位)int capacity;}HP; //堆类型Heap重命名为HP//堆初始化函数1 -- 对堆类型中的成员进行初始化
//接收 堆类型指针(php)
void HeapInit(HP* php);//堆销毁函数 -- 对堆类型进行销毁
//接收 堆类型指针(php)
void HeapDestroy(HP* php);//打印堆函数 -- 打印堆中各节点值
//接收 堆类型指针(php)
void HeapPrint(HP* php);//节点位置互换函数 -- 在向上向下调整操作中互换节点位置:
//接收要互换位置的两个节点的指针(p1 和 p2)
void Swap(HPDataType* p1, HPDataType* p2);//堆插入函数 -- 在堆类型中插入一个节点
//接收 堆类型指针(php)和插入节点的值(x)
void HeapPush(HP* php, HPDataType x);//堆初始化函数2 -- 接收一个数组将其初始化为一个堆底层数组
//接收 堆类型指针(php)、数组首元素地址(a)、数组元素个数(n)
void HeapInitArray(HP* php, int* a, int n);//堆删除函数 -- 删除堆类型根节点(删除当前堆中最值)
//接收 堆类型指针(php)
void HeapPop(HP* php);//堆顶函数 -- 获取并返回推根节点值
//接收 堆类型指针(php)
HPDataType HeapTop(HP* php);//判空函数 -- 判断堆类型是否为空
//接收 堆类型指针(php)
bool HeapEmpty(HP* php);

            

            

---------------------------------------------------------------------------------------------

                

Heap.c -- 实现文件

#define _CRT_SECURE_NO_WARNINGS 1//包含堆头文件:
#include "Heap.h"//堆初始化函数1 -- 对堆类型中的成员进行初始化
// (一开始不给值,之后使用函数插入值形成堆)
//接收 堆类型指针(php)
void HeapInit(HP* php)
{//assert断言接收的堆类型指针不为空://(确保有成功创建堆类型可以被初始化)assert(php);//将堆根节点指针置为NULL:php->a = NULL;//将堆当前节点个数置为0:php->size = 0;//将堆当前开辟的空间单位置为0:php->capacity = 0;
}//堆销毁函数 -- 对堆类型进行销毁
//接收 堆类型指针(php)
void HeapDestroy(HP* php)
{//assert断言接收的堆类型指针不为空://确保有堆类型可以被销毁assert(php);//释放堆类型中以a为头开辟的动态空间:free(php->a);//将堆当前节点个数和堆当前开辟的空间单位置为0:php->a = NULL;php->size = php->capacity = 0;
}//打印堆函数 -- 打印堆中各节点值
//接收 堆类型指针(php)
void HeapPrint(HP* php)
{//assert断言接收的堆类型指针不为空://(确保有成功创建堆类型可以被打印)assert(php);//使用for循环循环打印:for (int i = 0; i < php->size; i++)//size有多少个节点就打印多少个节点值:{//通过下标打印节点值:printf("%d ", php->a[i]);}//换行:printf("\n");
}//节点位置互换函数 -- 在向上向下调整操作中互换节点位置:
//接收要互换位置的两个节点的指针(p1 和 p2)
void Swap(HPDataType* p1, HPDataType* p2)
{//创建一个临时变量配合调换两节点值:HPDataType tmp = *p1;*p1 = *p2;*p2 = tmp;
}//在内部实现一个不对外声明的向上调整函数AdjustUp
//第一个参数接收 堆底层数组的首元素地址
//第二个参数接收 刚刚插入数组元素(子节点)的下标
void AdjustUp(HPDataType* a, int child)
{//使用之前讲到的公式,//通过子节点下标找到其父节点下标:int parent = (child - 1) / 2;//只要child还大于0就继续向上调整//需要向上层调整的话,上层节点的下标是比较小的//所以child不断调整就会越来越小while (child > 0){//小堆中的向上调整:if (a[child] < a[parent])//小堆中子节点值比父节点值还小://大堆中则把条件改为://if (a[child] > a[parent])  //大堆的向上调整{//那就需要两者调换位置:Swap(&a[child], &a[parent]); //值替换成功后,下标也要进行调整://child移到上层后,下标为parent下标:child = parent;//child移到该层后,还可能是再上层父节点的子节点//可能还需要再向上调整,最坏的情况是移到成为堆的根节点://再获得新父节点的下标:parent = (parent - 1) / 2;}else//如果小堆中子节点值已经大于等于父节点值了//即符合小堆的条件了{//那就不用进行向上调整,break退出循环:break;}}
}//堆插入函数 -- 在堆类型中插入一个节点
//接收 堆类型指针(php)和插入节点的值(x)
void HeapPush(HP* php, HPDataType x)
{//assert断言接收的堆类型指针不为空://确保有堆类型可以插入节点assert(php);//断言后要检查是否需要扩容:if (php->size == php->capacity)//堆当前节点个数 == 开辟空间单位//说明插入节点前需先进行扩容:{//创建变量存储新容量单位:int newCapacity = php->capacity == 0 ? 4 : php->capacity * 2;//因为capacity初始化为0,所以可以使用三目操作符进行增容://ps->capacity == 0 ? 4 : ps->capacity * 2//如果为0则直接增容到4,不为0则增容2倍//开辟动态空间:HPDataType* tmp = (HPDataType*)realloc(php->a, sizeof(HPDataType) * newCapacity);//这里直接使用realloc函数进行动态空间开辟//如果realloc函数接收头指针(该函数第一个参数)为空,//那么它的作用相当于malloc函数//对开辟空间进行检查:if (tmp == NULL)//返回空指针,开辟失败:{//打印错误信息:perror("realloc fail");//终止程序:exit(-1);}//成功开辟空间后,将开辟空间的头指针赋给a:php->a = tmp;//将新容量单位赋给原容量单位:php->capacity = newCapacity;}//在堆中进行插入操作://堆:
//物理结构是个数组;逻辑结构是个树
//树就没有头插和尾插的概念了
//节点具体插入哪个位置要看情况
//只要插入值足够大或足够小,就可以一直往上一层替换
//节点插入堆后要保持还是一个堆,是从左到右连续的树//不论什么情况,先默认插入最尾部://(即堆底层数组的末尾)//因为数组下标从0开始,//所以size即末尾插入节点下标:php->a[php->size] = x;//插入后堆当前节点个数size++:php->size++;//此时如果插入节点足够大(或足够小),//则刚好满足大堆(或小堆)的条件,//但如果不满足,就要将插入节点向树的上层调整,//且之后还会再执行该操作,//所以这里可以在文件内部定义一个向上调整函数AdjustUp//并进行调用:AdjustUp(php->a, php->size-1);//第一个参数接收 堆底层数组的首元素地址//第二个参数接收 刚刚插入数组元素(子节点)的下标// php->size-1 -- 前面插入节点后size++了// 所以这里的下标应-1 ,得到插入元素下标
}//堆初始化函数2 -- 接收一个数组将其初始化为一个堆底层数组
// (给你底层数组的各个值,再向上调整形成堆)
//接收 堆类型指针(php)、数组首元素地址(a)、数组元素个数(n)
void HeapInitArray(HP* php, int* a, int n)
{//assert断言断言接收的堆类型指针不为空://(确保有成功创建堆类型可以被初始化)assert(php);//assert断言数组a不为空:assert(a);//开辟动态空间:php->a = (HPDataType*)malloc(sizeof(HPDataType*) * n);//对开辟空间进行检查:if (php->a == NULL)//返回空指针,开辟失败:{//打印错误信息:perror("realloc fail");//终止程序:exit(-1);}//将堆当前节点个数置为n:php->size = n;//将堆当前开辟的空间单位置为n:php->capacity = n;//将数组元素拷贝作为堆底层数组元素:memcpy(php->a, a, sizeof(HPDataType) * n);//再循环向上调整堆中的节点(底层数组元素)进行建堆 :for (int i = 1; i < n; i++){AdjustUp(php->a, i);}
}//在内部实现一个不对外声明的向下调整函数AdjustDown
//第一个参数接收 堆底层数组的首元素地址
//第二个参数接收 堆节点个数(底层数组元素个数)
//第三个参数接收 调换位置后的根节点(原尾节点)下标
void AdjustDown(HPDataType* a, int n, int parent)
{//(小堆中)向下调整需要获得比父节点parent小的子节点:// (该子节点要和其父节点调换位置)//可以先假设左子节点是比父节点小的://获得根节点的左子节点(第一个子节点)下标:int child = parent * 2 + 1;//最坏情况:根节点成为叶子(没有子节点可以替换了)while (child < n)//左子节点下标如果>=堆节点个数(底层数组元素个数)//说明已经超出了数组范围,此时父节点已成为叶子无法再调换{//如果我们上面假设是错的:if (child + 1 < n  &&  a[child + 1] < a[child])//大堆中则把条件改为://if (child + 1 < n  &&  a[child + 1] > a[child]) //大堆的向下调整// child+1 即右子节点的下标/*	左右子节点都存在才用比较出较小节点:	防止不存在的右子节点越界:child + 1 < n上面只要左子节点在数组就能进入while循环而左子节点可能就是数组最后一个元素了可能会出现左子节点存在而右子节点不存在的情况所以要在右子节点存在的情况下比较出较小节点/没有右子节点直接使用左子节点。*///如果右子节点比左子节点小:{//就要获得右子节点(较小子节点)下标:++child; //自增后即右子节点下标}//到这里就获得较小节点的下标://(不关心是左子节点还是右子节点,只要值小的节点)//(小堆中)如果较小节点比父节点还小if (a[child] < a[parent])//大堆中则把条件改为://if (a[child] > a[parent]) //大堆的向下调整{//那就需要调换两者位置:Swap(&a[child], &a[parent]);//调换两节点值后,下标也要刷新:parent = child;//此时新的子节点下标为:child = parent * 2 + 1;}else//如果较小节点已经比父节点大了:{//那就符合小堆的条件,没必要调换:break; //退出循环}}
}//堆删除函数 -- 删除堆类型根节点(删除当前堆中最值)
//接收 堆类型指针(php)
void HeapPop(HP* php)
{//assert断言接收的堆类型指针不为空://确保有堆类型可以删除根节点assert(php);//assert断言堆节点个数(底层数组元素个数)不为0//确保有节点可以删除:assert(php->size > 0);/*如果进行挪动覆盖第一个位置的根节点会导致剩下的节点关系乱套(兄弟变父子)最终结果可能不一定是堆,而且数组中挪动覆盖效率本来就不高所以可以将根节点和尾节点交换位置再进行尾删,就实现了删除根节点且数组中尾删效率较高,*///将根节点值和尾节点值交换:Swap(&php->a[0], &php->a[php->size - 1]);//	&php->a[0] :根节点值//	&php->a[php->size - 1] :尾结点值//再将移至尾部的原根节点删除:--php->size; //直接元素个数size-1即可/*此时堆的左右子树的结构没有变化左右子树依然是小堆(大堆)有了这个前提就可以进行向下调整:因为前面根节点和尾节点交换位置所以现在的根节点(原尾结点)可能就要比起子节点大了树整体不符合小堆条件,所以要进行向下调整(注:向上调整的前提是前面节点符合堆的条件)向下调整操作:成为根节点后,跟其两个子节点比较如果子节点比较小,则互换位置互换位置后再跟下一层子节点比较如果子节点比较小,则互换位置以此类推,最坏情况是到成为叶子为止(小堆中大的值往下移,小的值往上走)*///所以这里可以在文件内部定义一个向下调整函数AdjustDown//并进行调用:AdjustDown(php->a, php->size, 0);//根节点在底层数组中下标是0/** 该函数的意义和示例:该函数的意义是删除第一小的值(小堆中)再找到第二小的值,以此类推,可以依次找到数组的最小值示例:“该城市排名前10的蛋糕店” 小堆根元素就第一好的店,使用该函数后找到第二好的店,以此类推……*//** 该函数时间复杂度:向下或向上调整操作最好情况执行1次,最坏情况执行树的高度次即时间复杂度为 O(logN),10亿个值只需调整30多次 -- 很优秀( log -- 默认以2为底 )*/}//堆顶函数 -- 获取并返回推根节点值
//接收 堆类型指针(php)
HPDataType HeapTop(HP* php)
{//assert断言接收的堆类型指针不为空://确保有堆类型可以获取根节点值assert(php);//assert断言堆节点个数(底层数组元素个数)不为0//确保堆类型中有节点:assert(php->size > 0);//直接返回根节点值:return php->a[0];
}//判空函数 -- 判断堆类型是否为空
//接收 堆类型指针(php)
bool HeapEmpty(HP* php)
{//assert断言接收的堆类型指针不为空://确保有堆类型可以获取根节点值assert(php);//如果堆节点个数(底层数组元素个数)为0则说明堆为空:return php->size == 0;//php->size = 0 -- 成立返回true,堆为空//php->size = 0 -- 不成立返回false,堆不为空 
}

            

            

---------------------------------------------------------------------------------------------

                

Test.c -- 测试文件

#define _CRT_SECURE_NO_WARNINGS 1//包含堆头文件:
#include "Heap.h"//测试函数 -- 未排序
void Test0()
{//创建一个数组创建要放入堆中的各节点值int a[] = { 65,100,70,32,50,60 };//计算数组长度:int alength = sizeof(a) / sizeof(int);//创建堆类型变量:HP hp;//使用HeapInit函数进行初始化:HeapInit(&hp);//使用for循环将数组各值放入堆类型变量中:for (int i = 0; i < alength; i++){//堆类型变量hp在还没有HeapPush之前只是完全二叉树//在使用HeapPush函数插入并排序后就成了堆,//		所以建堆的方式之一就是一直push://使用HeapPush函数插入节点:HeapPush(&hp, a[i]);}printf("当前堆:> ");//使用HeapPrint函数打印堆:HeapPrint(&hp);//使用HeapEmpty函数判断堆是否为空:while (!HeapEmpty(&hp))//不为空就获取堆根节点值:{//使用HeapTop函数获取堆根节点值并打印:printf("当前堆根节点值:> %d\n", HeapTop(&hp));//(小堆中)使用HeapPop函数删除当前根节点,// 并将第二小的节点设置为新的根节点:HeapPop(&hp);}//使用HeapDestroy函数进行销毁:HeapDestroy(&hp);
}测试函数 -- 进行排序
//
堆排序函数(优化前) -- 利用堆类型对普通数组进行排序(升序或降序)
第一个参数:	接收堆底层数组的首元素地址
第二个参数:	堆底层数组的元素个数
//void HeapSort(int* a, int n)
//{
//	//创建堆类型变量:
//	HP hp;
//
//	//使用HeapInit函数进行初始化:
//	HeapInit(&hp);
//
//	//使用for循环将数组各值放入堆类型变量中:
//	for (int i = 0; i < n; i++)
//	{
//		//堆类型变量hp在还没有HeapPush之前只是完全二叉树
//		//在使用HeapPush函数插入并排序后就成了堆,
//		//		所以建堆的方式之一就是一直push:
//
//		//使用HeapPush函数插入节点:
//		HeapPush(&hp, a[i]);
//	}
//
//	//printf("当前堆:> ");
//	使用HeapPrint函数打印堆:
//	//HeapPrint(&hp);
//
//	int i = 0;
//	//使用HeapEmpty函数判断堆是否为空:
//	while (!HeapEmpty(&hp))
//		//不为空就获取堆根节点值:
//	{
//		//(小堆中)依次将堆类型的根节点值赋给数组a,
//		//运用堆实现将数组从小到大排序:
//		a[i++] = HeapTop(&hp);
//
//		//(小堆中)使用HeapPop函数删除当前根节点,
//		// 并将第二小的节点设置为新的根节点:
//		HeapPop(&hp);
//	}
//
//	//使用HeapDestroy函数进行销毁:
//	HeapDestroy(&hp);
//}这种排序的缺陷:1. 得先有一个堆的数据结构2. 空间复杂度的消耗
//void Test1()
//{
//	//创建一个堆底层数组 -- 节点值随机;未进行排序
//	int a[] = { 65,100,70,32,50,60 };
//
//	//计算数组长度:
//	int alength = sizeof(a) / sizeof(int);
//
//	printf("运用堆排序前的数组:> ");
//	//运用堆排序后前的数组:
//	for (int i = 0; i < alength; i++)
//	{
//		printf("%d ", a[i]);
//	}
//	printf("\n");
//	
//	//使用HeapSort函数对未进行排序的堆底层数组进行排序:
//	HeapSort(a, alength);
//
//	printf("运用堆排序后的数组:> ");
//	//运用堆排序后的数组:
//	for (int i = 0; i < alength; i++)
//	{
//		printf("%d ", a[i]);
//	}
//
//}测试函数 -- 进行排序
//
堆排序函数(优化后) -- 利用堆类型的思路对普通数组进行排序(升序或降序)
第一个参数:	接收堆底层数组的首元素地址
第二个参数:	堆底层数组的元素个数
//void HeapSort(int* a, int n)
//{	
//	//之前是使用HeapPush函数创建堆类型后,
//	//再运用到普通数组的排序中,
//	//那我们也可以不用堆,
//	//直接使用HeapPush函数的思路将普通数组建成堆:
//	
//  //向上调整建堆 -- 时间复杂度 -- O(N*logN)
//	//将数组看做完全二叉树,再进行建堆:
//	//在AdjustUp中可设置为是大堆调整还是小堆调整
//	for (int i = 1; i < n; i++)
//		//从数组第二个元素(下标为1)开始排序,第一个元素默认为根节点,
//		//使用AdjustUp函数后再进行进一步调整:
//	{
//		//之前是在堆类型的操作中使用了AdjustUp调整函数
//		//这里在普通数组上也可以使用AdjustUp调整函数
//		//只是堆类型需要扩容,而普通数组不需要扩容而已
//		//把普通数组按大堆或小堆的方式进行调整:
//		AdjustUp(a, i);
//	}
//
//	//现在首元素就相当于(小堆)根节点,即最小值
//	//要想再选出次小的值,只能把剩下的数据看做堆
//	//但是父子关系全乱了,剩下数据也不一定还是堆
//	//可以再重新建堆,但是代价太大了
//
//	//还有一个思路:升序(从小到大)用大堆
//	//把数组建成大堆,把最大值选出来后,把最大值和最尾值交换
//	//这样升序中(从小到大)也排好了一个值,即最大值放尾部
//	//再把除最大值的其它值看做堆,进行向下调整,选出次大值
//	//放倒数第二个位置,循环这套操作 -- 时间复杂度NlogN
//	//(同样的道理,如果是降序(从大到小)就用小堆)
//
//	//以降序(从大到小)用小堆为例:
//
//	//先获得数组尾元素下标:
//	int end = n - 1;
//	//使用while循环进行排序:
//	while (end > 0)
//		//数组尾元素下标大于说明至少还有两个元素,继续排序:
//	{
//		//把最小值(小堆根节点)和尾元素进行交换:
//		Swap(&a[0], &a[end]);
//
//		//把除最小值的其它值看做堆,进行向下调整,选出次大小值:
//		AdjustDown(a, end, 0);
//		//end即是除最小值的其它值(数组前n-1个值)
//
//		//这样就调整好了最尾的一个值,end-1循环调整下一个:
//		end--;
//	}
//  
//}
//
//void Test2()
//{
//	//创建一个堆底层数组 -- 节点值随机;未进行排序
//	//int a[] = { 75,65,100,32,50,60 };
//	int a[] = { 2,3,5,7,4,6,8 };
//
//	//计算数组长度:
//	int alength = sizeof(a) / sizeof(int);
//
//	printf("运用堆排序前的数组:> ");
//	//运用堆排序后前的数组:
//	for (int i = 0; i < alength; i++)
//	{
//		printf("%d ", a[i]);
//	}
//	printf("\n");
//
//	//使用HeapSort函数对未进行排序的堆底层数组进行排序:
//	HeapSort(a, alength);
//
//	printf("运用堆排序后的数组:> ");
//	//运用堆排序后的数组:
//	for (int i = 0; i < alength; i++)
//	{
//		printf("%d ", a[i]);
//	}
//
//}//测试函数 -- 进行排序
//堆排序函数(再再优化) -- 只用向下调整对普通数组进行排序(升序或降序)
//第一个参数:	接收堆底层数组的首元素地址
//第二个参数:	堆底层数组的元素个数
void HeapSort(int* a, int n)
{//向下调整建堆 -- 时间复杂度:O(N)//将要排序的数组看做一棵完全二叉树//从倒数第一个父节点(非叶子节点)开始向下调整:for (int i = (n-1-1)/2; i >= 0; i--)//(n-1-1)/2 -- n-1是最后叶子的下标,该叶子-1再/2(公式)//找到其父节点(倒数第一个父节点),调整好该父节点后i--//再调整上一父节点,直到向下调整到根节点{AdjustDown(a, n, i); //从i位置开始向下调整}//建堆最坏情况下执行次数:T(N) = N - log(N+1)//因此:建堆的时间复杂度为O(N)//开始排序:以降序(从大到小)用小堆为例://先获得数组尾元素下标:int end = n - 1;//使用while循环进行排序:while (end > 0)//数组尾元素下标大于说明至少还有两个元素,继续排序:{//把最小值(小堆根节点)和尾元素进行交换:Swap(&a[0], &a[end]);//把除最小值的其它值看做堆,进行向下调整,选出次大小值:AdjustDown(a, end, 0);//end即是除最小值的其它值(数组前n-1个值)//这样就调整好了最尾的一个值,end-1循环调整下一个:end--;}}void Test3()
{//创建一个堆底层数组 -- 节点值随机;未进行排序//int a[] = { 75,65,100,32,50,60 };int a[] = { 2,3,5,7,4,6,8 };//计算数组长度:int alength = sizeof(a) / sizeof(int);printf("运用堆排序前的数组:> ");//运用堆排序后前的数组:for (int i = 0; i < alength; i++){printf("%d ", a[i]);}printf("\n");//使用HeapSort函数对未进行排序的堆底层数组进行排序:HeapSort(a, alength);printf("运用堆排序后的数组:> ");//运用堆排序后的数组:for (int i = 0; i < alength; i++){printf("%d ", a[i]);}}//主函数:
int main() 
{//Test0();//Test1();//Test2();Test3();return 0;
}

相关文章:

【数据结构初阶】七、非线性表里的二叉树(堆的实现 -- C语言顺序结构)

相关代码gitee自取&#xff1a; C语言学习日记: 加油努力 (gitee.com) 接上期&#xff1a; 【数据结构初阶】六、线性表中的队列&#xff08;链式结构实现队列&#xff09;-CSDN博客 1 . 非线性表里的 树(Tree) 树的概念及结构&#xff1a; 树的概念 树是一种非线性的数据…...

基于SpringBoot的网上超市系统

基于SpringBoot的网上超市系统的设计与实现 开发语言&#xff1a;Java数据库&#xff1a;MySQL技术&#xff1a;SpringBootMyBatis工具&#xff1a;IDEA/Ecilpse、Navicat、Maven 【主要功能】 角色&#xff1a;用户、管理员 管理员&#xff1a;个人中心、用户管理、商品分类…...

在springboot项目中整合Druid

或 1.导入maven坐标 <dependency><groupId>com.alibaba</groupId><artifactId>druid-spring-boot-starter</artifactId><version>1.2.19</version> </dependency>2.在application.properties中配置连接池 spring:datasource:d…...

微信支付费率降低到0.2%,商家收款开户手续费0.6%降低的操作方法

在如今的数字时代&#xff0c;移动支付已成为人们日常生活中必不可少的一部分。微信支付作为国内最受欢迎的移动支付平台&#xff0c;一直致力于为商家和个人提供最便捷、安全的支付方式。如果可以将微信支付将费率降低到仅为0.2%&#xff0c;这无疑给广大商家带来了巨大的利好…...

计算机毕业设计 基于SSM的民宿推荐系统的设计与实现 Java实战项目 附源码+文档+视频讲解

博主介绍&#xff1a;✌从事软件开发10年之余&#xff0c;专注于Java技术领域、Python人工智能及数据挖掘、小程序项目开发和Android项目开发等。CSDN、掘金、华为云、InfoQ、阿里云等平台优质作者✌ &#x1f345;文末获取源码联系&#x1f345; &#x1f447;&#x1f3fb; 精…...

【机器学习】训练集/验证集/测试集释疑

文章目录 序言1. 训练集、验证集、测试集是什么2. 为什么需要验证集3. 验证集是必须的吗4. 验证集和测试集上的表现会不同吗5. 如何从Train/Test Set划分Validation Set6. 训练集、验证集和测试集的比例怎么设置7. 模型表现不好时测试集可以反复使用来调整模型吗8. 训练集、验证…...

LCR 120.寻找文件副本

​题目来源&#xff1a; leetcode题目&#xff0c;网址&#xff1a;LCR 120. 寻找文件副本 - 力扣&#xff08;LeetCode&#xff09; 解题思路&#xff1a; 使用哈希集合判断是否有元素重复出现即可。 解题代码&#xff1a; class Solution {public int findRepeatDocument(…...

代码随想录算法训练营第44天|动态规划:完全背包理论基础、518.零钱兑换II、377. 组合总和 Ⅳ

动态规划&#xff1a;完全背包理论基础 518.零钱兑换II https://leetcode.cn/problems/coin-change-ii/ 用一个二维dp数组 class Solution { public:int change(int amount, vector<int>& coins) {vector<vector<int>> dp(coins.size(), vector<i…...

309.买卖股票的最佳时机含冷冻期【Java】

309. 买卖股票的最佳时机含冷冻期 - 力扣&#xff08;LeetCode&#xff09; 给定一个整数数组prices&#xff0c;其中第 prices[i] 表示第 i 天的股票价格 。​ 设计一个算法计算出最大利润。在满足以下约束条件下&#xff0c;你可以尽可能地完成更多的交易&#xff08;多次…...

React Promise 中断

需求&#xff1a; 上传文件&#xff0c;但是后端接口不支持多文件上传&#xff0c;但是一次性发出很多请求的话如果有100个文件那对后端的压力又太大了在上传的时候还需要有停止上传的按钮 进程&#xff1a; async await 只能做到第一步&#xff0c;但是无法在上传中的时候关…...

1.填空题 进制转换Oct.2023

原题 部分可能会有用处的知识&#xff1a; p p p进制转十进制&#xff1a; 假设有一个 p p p进制数&#xff0c;个位是 a 0 a_0 a0​&#xff0c;向高位依次是 a 1 , a 2 , . . . , a n a_1,a_2,...,a_n a1​,a2​,...,an​&#xff0c;向低位依次是 b 1 , b 2 , b 3 , . . . …...

node 解决多版本配置 error:03000086:digital 引起的问题 已解决

在日常后端工作中&#xff0c;难免会安装前端的项目&#xff0c;今天有旧项目需要维护&#xff0c;但是 提示 node版本过高&#xff0c;或者不是长维护版本&#xff0c;部分分享说&#xff0c;加 opensll 过滤能解决&#xff0c;但是 还是不行&#xff0c;索性来这个 底朝天的找…...

前端面试题: js中对比两个对象的值是否相等? for..in 和 for...of的区别?

我去面试的时候会问这个问题&#xff0c; 而且发现不管是初级还是工作一段时间的小伙伴 都会说的不是很清晰 比如第一道题哈&#xff1a; 首先大部分人都会想起来 我们用JSON.stringify() 进行转换&#xff0c;查看两个是否相等 你敢说我下面的对象 值不是想等的吗。 但是你用…...

第十七章:Java连接数据库jdbc(java和myql数据库连接)

1.进入命令行&#xff1a;输入cmd&#xff0c;以管理员身份运行 windowsr 2.登录mysql 3.创建库和表 4.使用Java命令查询数据库操作 添加包 导入包的快捷键 选择第四个 找到包的位置 导入成功 创建java项目 二&#xff1a;连接数据库&#xff1a; 第一步&#xff1a;注册驱动…...

Unity基于种子与地块概率的开放世界2D地图生成

public class BuildingGen : MonoBehaviour {public int[] Building;//存储要生成的地块代码public int[] Probability;//存储概率public double seed;public int width 100;public int height 100;public float noiseScale 0.1f; //噪声缩放倍数private int[,] frequencyM…...

5.Vectors Transformation Rules

在上节&#xff0c;有个问题&#xff1a;向量分量的转换方式 与 新旧基底的转换方式相反 用例子来感受一下&#xff0c; 空间中一向量V&#xff0c;即该空间的一个基底&#xff1a;e1、e2 v e1 e2 现把基底 e1 、 e2 放大两倍。变成 基向量放大了两倍&#xff0c; 但对于…...

聊聊httpclient的CPool

序 本文主要研究一下httpclient的CPool ConnPool org/apache/http/pool/ConnPool.java public interface ConnPool<T, E> {/*** Attempts to lease a connection for the given route and with the given* state from the pool.** param route route of the connecti…...

B2主题优化:WordPress文章每次访问随机增加访问量

老站长都知道&#xff0c;一个新站刚开始创建&#xff0c;内容也不多的时候&#xff0c;用户进来看到文章浏览量要么是0&#xff0c;要么是 个位数&#xff0c;非常影响体验&#xff0c;就会有一种“这个网站没人气&#xff0c;看来不行”的感觉。 即使你的内容做的很好&#x…...

大模型部署手记(1)ChatGLM2+Windows GPU

1.简介&#xff1a; 组织机构&#xff1a;智谱/清华 代码仓&#xff1a;https://github.com/THUDM/ChatGLM2-6B 模型&#xff1a;THUDM/chatglm2-6b 下载&#xff1a;https://huggingface.co/THUDM/chatglm2-6b 镜像下载&#xff1a;https://aliendao.cn/models/THUDM/chat…...

Rust Rocket: 构建Restful服务项目实战

前言 这几天我的笔记系统开发工作进入了搬砖期&#xff0c;前端基于Yew&#xff0c;后端基于Rocket。关于Rocket搭建Restful服务&#xff0c;官方也有介绍&#xff0c;感觉很多细节不到位。因此我打算花2到3天的时间来整理一下&#xff0c;也算是对自己的一个交代。 对于有一…...

苹果签名有多少种类之TF签名(TestFlight签名)是什么?优势是什么?什么场合需要应用到?

&#xff08;一&#xff09;TestFlight 能够让您&#xff1a;邀请内部和外部的测试人员为应用程序提供反馈。 跟踪应用程序在测试过程中发现的 bug 和用户体验问题。 收集 Crash 报告&#xff0c;了解应用程序在真实设备上的运行状况。 要使用 TestFlight&#xff0c;您可以按照…...

如何将图片存到数据库(以mysql为例), 使用ORM Bee更加简单

如何将图片存到数据库 1. 创建数据库: 2. 生成Javabean public class ImageExam implements Serializable {private static final long serialVersionUID 1596686274309L;private Integer id;private String name; // private Blob image;private InputStream image; //将In…...

【“栈、队列”的应用】408数据结构代码

王道数据结构强化课——【“栈、队列”的应用】代码&#xff0c;持续更新 链式存储栈&#xff08;单链表实现&#xff09;&#xff0c;并基于上述定义&#xff0c;栈顶在链头&#xff0c;实现“出栈、入栈、判空、判满”四个基本操作 #include <stdio.h> #include <…...

es的nested查询

一、一层嵌套 mapping: PUT /nested_example {"mappings": {"properties": {"name": {"type": "text"},"books": {"type": "nested","properties": {"title": {"t…...

<一>Qt斗地主游戏开发:开发环境搭建--VS2019+Qt5.15.2

1. 开发环境概述 对于Qt的开发环境来说&#xff0c;主流编码IDE界面一般有两种&#xff1a;Qt Creator或VSQt。为了简单起见&#xff0c;这里的操作系统限定为windows&#xff0c;编译器也通用VS了。Qt版本的话自己选择就可以了&#xff0c;当然VS的版本也是依据Qt版本来选定的…...

python:进度条的使用(tqdm)

摘要&#xff1a;为python程序进度条&#xff0c;可以知道程序运行进度。 python中&#xff0c;常用的进度条模块是tqdm&#xff0c;将介绍tqdm的安装和使用 1、安装tqdm: pip install tqdm2、tqdm的使用&#xff1a; &#xff08;1&#xff09;在for循环中的使用&#xff1…...

Java类型转换和类型提升

目录 一、类型转换 1.1 自动类型转换&#xff08;隐式&#xff09; 1.1.1 int 与 long 之间 1.1.2 float 与 double 之间 1.1.3 int 与 byte 之间 1.2 强制类型转换&#xff08;显示&#xff09; 1.2.1 int 与 long 之间 1.2.2 float 与 double 之间 1.2.3 int 与 d…...

C# 读取 Excel xlsx 文件,显示在 DataGridView 中

编写 read_excel.cs 如下 using System; using System.Collections.Generic; using System.ComponentModel; using System.IO; using System.Data; using System.Linq; using System.Text; using System.Data.OleDb;namespace ReadExcel {public partial class Program{static…...

Docker02基本管理

目录 1、Docker 网络 1.1 Docker 网络实现原理 1.2 Docker 的网络模式 1.3 网络模式详解 1.4 资源控制 1.5 进行CPU压力测试 1.6 清理docker占用的磁盘空间 1.7 生产扩展 1、Docker 网络 1.1 Docker 网络实现原理 Docker使用Linux桥接&#xff0c;在宿主机虚拟一个Docke…...

Scala第十章

Scala第十章 章节目标 1.数组 2.元组 3.列表 4.集 5.映射 6.迭代器 7.函数式编程 8.案例&#xff1a;学生成绩单 scala总目录 文档资料下载...