郑州网站建设专注乐云seo,网站举报查询进度,wordpress 无法发送邮件,燕郊网站开发相关代码gitee自取#xff1a;
C语言学习日记: 加油努力 (gitee.com)
接上期#xff1a;
【数据结构初阶】六、线性表中的队列#xff08;链式结构实现队列#xff09;-CSDN博客 1 . 非线性表里的 树(Tree) 树的概念及结构#xff1a; 树的概念 树是一种非线性的数据…
相关代码gitee自取
C语言学习日记: 加油努力 (gitee.com) 接上期
【数据结构初阶】六、线性表中的队列链式结构实现队列-CSDN博客 1 . 非线性表里的 树(Tree) 树的概念及结构 树的概念 树是一种非线性的数据结构它是由 n(n0) 个有限节点组成一个具有层次关系的集合。 把它叫做树是因为它看起来像一棵倒挂的树也就是说它是根朝上而叶朝下的。 jie点线性结构 -- 结点 非线性结构 -- 节点 树的结构 有一个特殊的节点称为根节点根节点没有前驱节点 除根节点外其余节点被分成 M(M0) 个互不相交的集合 T1 、T2 、……、Tm 其中每一个集合 Ti(1 i m) 又是一棵结构与树类似的子树。每棵子树的根节点有且只有一个前驱节点可以有零个或多个后继节点 树是递归定义的 树形结构中子树之间不能有交集否则就不是树形结构 图示 树的其它相关概念 (有些概念对应意思不好理解可以结合看下列示例图的例子) 概念名称对应意思下图中例子节点的度一个节点含有的子树个数 称为 该节点的度节点A的度为6叶节点 (终端节点)度为0的节点 称为 叶节点节点B、C、H……为叶节点 分支节点 (非终端节点) 度不为0的节点 称为 分支节点节点D、E、F……为分支节点父节点 (双亲节点)若一个节点含有子节点则这个节点 称为 其子节点的父节点节点A是节点B的父节点子节点 (孩子节点)一个节点含有的子树的根节点 称为 该节点的子节点节点B是节点A的子节点兄弟节点具有相同父节点的节点 互称为 兄弟节点节点B、C是兄弟节点树的度一棵树中最大的节点的度 称为 树的度下图中树的度为6节点的层次从根开始定义起根为第一(零)层根的子节点为第二(一)层以此类推建议从第一层起算空树可用零层表示节点A所在层为第一层节点B所在层为第二层……树的高度 (树的深度)树中节点的最大层次下图中树的高度(深度)为4堂兄弟节点父节点(双亲节点)在同一层的节点 互称为 堂兄弟节点H、I互为兄弟节点节点的祖先从根到该节点上的所有的分支节点 都是 祖先节点A是所有节点的祖先子孙以某节点为根的子树中任一节点都称为 该节点的子孙所有节点都是节点A的子孙森林由m(m0)棵互不相交的树组成的集合 称为 森林 示例图 树的存储表示 树的表示方式 树结构相对线性表就比较复杂了要存储表示起来就比较麻烦了既要保存值域也要保存节点和节点之间的关系 实际中树有很多种表示方式如双亲表示法、孩子表示法、孩子双亲表示法以及孩子兄弟表示法等 我们这里就简单了解其中最常用的左孩子右兄弟表示法 树结构的最优设计 左孩子右兄弟表示法结构 //树中各节点数据域存储数据的类型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) 堆的概念及结构 堆的概念 如果有一个关键码的集合 把它的所有元素按完全二叉树的顺序存储方式存储在一个一维数组中并满足 且 且 其中 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);//将堆根节点指针置为NULLphp-a NULL;//将堆当前节点个数置为0php-size 0;//将堆当前开辟的空间单位置为0php-capacity 0;
}//堆销毁函数 -- 对堆类型进行销毁
//接收 堆类型指针php
void HeapDestroy(HP* php)
{//assert断言接收的堆类型指针不为空//确保有堆类型可以被销毁assert(php);//释放堆类型中以a为头开辟的动态空间free(php-a);//将堆当前节点个数和堆当前开辟的空间单位置为0php-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);}//成功开辟空间后将开辟空间的头指针赋给aphp-a tmp;//将新容量单位赋给原容量单位php-capacity newCapacity;}//在堆中进行插入操作//堆
//物理结构是个数组逻辑结构是个树
//树就没有头插和尾插的概念了
//节点具体插入哪个位置要看情况
//只要插入值足够大或足够小就可以一直往上一层替换
//节点插入堆后要保持还是一个堆是从左到右连续的树//不论什么情况先默认插入最尾部//即堆底层数组的末尾//因为数组下标从0开始//所以size即末尾插入节点下标php-a[php-size] x;//插入后堆当前节点个数sizephp-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);}//将堆当前节点个数置为nphp-size n;//将堆当前开辟的空间单位置为nphp-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]) //大堆的向下调整// child1 即右子节点的下标/* 左右子节点都存在才用比较出较小节点 防止不存在的右子节点越界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(N1)//因此建堆的时间复杂度为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;
}
