首页 > 其他分享 >数据结构——堆(C语言版)

数据结构——堆(C语言版)

时间:2024-07-22 21:56:51浏览次数:16  
标签:结点 孩子 位置 C语言 二叉树 数组 数据结构 节点

        树的概念:

        树(Tree)是一种抽象数据结构,它由节点(node)的集合组成,这些节点通过边相连,把

节点集合按照逻辑顺序抽象成图像,看起来就像一个倒挂着的树,也就是说数据结构中的树是根成朝上,叶子朝下。

        树形结构中,⼦树之间不能有交集,否则就不是树形结构 ,就不能称之为树

        ⾮树形结构:        

        像上图,子节点与子节点会相交,这种就不能称之为树。

        树的专业术语

⽗结点/双亲结点:若⼀个结点含有⼦结点,则这个结点称为其⼦结点的⽗结点 ⼦结点/孩⼦结点:⼀个结点含有的⼦树的根结点称为该结点的⼦结点;   结点的度:⼀个结点有⼏个孩⼦,他的度就是多少; 叶⼦结点/终端结点:度为 0 的结点称为叶结点;  分⽀结点/⾮终端结点:度不为 0 的结点;   兄弟结点:具有相同⽗结点的结点互称为兄弟结点(亲兄弟); 树的高度或深度:树中结点的最⼤层次;  结点的祖先:从根到该结点所经分⽀上的所有结点; 路径:⼀条从树中任意节点出发,沿⽗节点-⼦节点连接,达到任意节点的序列; ⼦孙:以某结点为根的⼦树中任⼀结点都称为该结点的⼦孙。 森林:由 m(m>0) 棵互不相交的树的集合称为森林;

二叉树

        二叉树的概念:

        在树形结构中,我们最常⽤的就是⼆叉树,⼀棵⼆叉树是结点的⼀个有限集合,该集合由⼀个根结点 加上两棵别称为左⼦树和右⼦树的⼆叉树组成或者为空。

        

        二叉树的特征:

                从上图可以看出⼆叉树不存在度⼤于 2 的结点 ,并且⼆叉树的⼦树有左右之分,次序不能颠倒,因此,二叉树又是一个有序树。

        

        以上均为二叉树可能出现的情况。

                满二叉树与完全二叉树

                        满二叉树:

        满二叉树是一种特殊的完全二叉树。⼀个⼆叉树,如果每⼀个层的结点数都达到最⼤值,则这个⼆叉树就是满⼆叉树。也就是说,如果⼀ 个⼆叉树的层数为 K ,且结点总数是 2 k − 1 ,则它就是满⼆叉树。

        从上图可以看出,满二叉树属于一个等比数列,通过等比数列求和公式可以计算出满二叉树的节点总数。    

                        完全二叉树

        完全二叉树(Complete Binary Tree)是一种特殊的二叉树,其所有节点按照从上到下、从左到右的顺序填充,除了最后一层可能不是满的,其他所有层都必须是满的

        根据上图示例,只有左边是完全二叉树,而右边不是,因为完全二叉树要保证k-1层是满的,而第l层要保证顺序必须一次按照从左到右,不能中间断开。同时也可以推断出完全二叉树的节点范围为[2^(h-1),2^h-1].

        2^(h-1)  是高度为 ( h ) 的二叉树最少的节点数。它表示二叉树的最底层可能是单侧排列的最小节点数,即最小深度。

         2^h - 1  是高度为 ( h ) 的二叉树的最大节点数。它表示如果二叉树是满二叉树,所有层都是满的情况下的节点数。

                        二叉树的性质:
        若规定根结点的层数为 1 ,则⼀棵⾮空⼆叉树的第i层上最多有 2^(k−1) 个结点                                             若规定根结点的层数为 1 ,则深度为 h 的⼆叉树的最⼤结点数是 2^h-1(最大节点数情况为满二叉树,上图证明过了)                  若规定根结点的层数为 1 ,具有 n 个结点的满⼆叉树的深度 ( log 以2为底, n+1 为对数) h = log (n + 1)

                        二叉树的存储结构:

        ⼆叉树⼀般可以使⽤两种结构存储,⼀种顺序结构,⼀种链式结构,而在这篇文章,小编主要说的是顺序存储。

                                顺序存储:
        顺序结构存储就是使⽤数组来存储,⼀般使⽤数组只适合表⽰完全⼆叉树。

        

        从上图可以看出,二叉树使用顺序存储时,在物理结构上就是一个数组,而拆解成逻辑结构就是一个二叉树,而用顺序表存储二叉树时,只适用于完成二叉树与满二叉树,因为不是完全⼆叉树会有空间的浪费,完全⼆叉树更适合使⽤顺序结构存储。现实中我们通常把堆(⼀种⼆叉树)使⽤顺序结构的数组来存储,需要注意的是这⾥的堆和操作系统 虚拟进程地址空间中的堆是两回事,⼀个是数据结构,⼀个是操作系统中管理内存的⼀块区域分段。

    用堆实现二叉树

            小根堆:

        从上图可以发现,在堆顶(数组下标为0)的位置中存放的数据,是这个堆中最小的值,并且堆中某个结点的值总是不⼩于其⽗结点的值,我们将这种堆称之为小根堆。

            大根堆:

                

        从上图可以发现,在堆顶(数组下标为0)的位置中存放的数据,是这个堆中最大的值,并且堆中某个结点的值总是不大于其⽗结点的值,我们将这种堆称之为大根堆。

            堆的实现

                堆的结构:

        

        根据上图结构可以得知,堆的底层为一个顺序表,那么顺序表里存的数值不一定是整型,所以这里用typedef命名变量类型,这样后期改的话也方便,接着就是定义一个size用来存储堆的有效数据,capaticy用来存储堆的容量。

                初始化堆:

                入堆

        第一步:先进行断言,判断传入是指针是否为NULL。

        第二步:再次判断size是否等于capaticy,如果等于就进行扩容。

       第三步:接着将数组a的size(尾部)下标位置插入x值,并将size++指向有效数值的下一个位置。最后通过向上调整算法,维护堆里的数据。

                向上调整算法:

        假设这里假设此时为大堆,大堆堆顶为最大值,其父节点都不会小于它们的孩子节点。

        这里先定义一个Swap(交换函数),为后续的交换做准备。向上调整函数定义了两个参数,第一个为指向堆的指针,第二个为child(孩子)位置。这里需要知道一个公式,父亲节点位置=(孩子节点位置-1)/2。

        第一步:定义一个parent变量,用于保存父亲节点位置

        第二步创建while循环,因为是向上调整,所以起始位置会在数组末尾,当孩子节点为0的时候表示已经达到了堆顶的位置则就不需要进行调整,循环结束。

        第三步:在循环里创建一个if语句,如果父亲节点的值小于孩子节点,那么就进行向上交换,孩子变父亲,父亲变孩子,然后将父亲位置赋值给孩子,继续向上找父亲节点位置进行循环判断是否交换,如果不需要交换(父亲节点>孩子节点)就直接退出循环。

                出堆

        出堆一般是在堆顶进行弹出数据,因为要么是取最大值要么是取最小值,在堆底出堆并没有任何的意义所在。

        第一步:先判断传进来的指针是否为NULL,并且保证堆里有数据才能进行出堆操作。

        第二步:交换堆顶和堆底的值,并将堆的有效数据位置size--。

        第三步:进行向下调整。

                向下调整算法:

假设这里假设此时为大堆,大堆堆顶为最大值,其父节点都不会小于它们的孩子节点。

        向下调整函数定义了三个参数,第一个为指向堆的指针,第二个为parent(父亲)位置,第三个为堆的长度。

        第一步:先定义child(孩子)变量,这里只需要计算出左孩子的位置,根据数组的特性,数组为一块连续的内存地址,所以计算出左孩子的位置再加一就是右孩子的位置。根据公式:父亲节点位置=(孩子节点位置-1)/2,得出左孩子位置=parent*2+1。

        第二步:创建whil循环,当孩子值大于size长度说明循环走完了一个堆则直接退出循环否则会下标越界。

        第三步:先建立第一个if语句,先判断chid+1是否小于size,为了确保数组不会越界访问接再判断左右孩子的值哪一个更大,因为弹出了最大的值,所以要将第二大的值变成堆顶数据。如果右孩子的值比左边孩子大那么就++child。

        第四步:建立第二个if语句如果此时孩子节点的值会大于我的父亲节点,那么就交换孩子节点与父亲节点,并重新将child(孩子)位置赋值给parent(父亲),孩子位置再次等于parent*2+1,向下进行循环调整。

        

                取堆顶数据

​​​​​​​        

                销毁堆

       

标签:结点,孩子,位置,C语言,二叉树,数组,数据结构,节点
From: https://blog.csdn.net/2301_80894970/article/details/140591333

相关文章

  • C语言指针易混淆知识点总结
    指针定义指针是一个变量,存储另一个变量的内存地址,它允许直接访问和操作内存中的数据,使得程序能够以更灵活和高效的方式处理数据和内存。获取变量地址:使用取地址符&。访问地址上的数据:使用解引用符*。例子1指针是存储另一个变量地址的变量。通过使用取地址符&和解引用符......
  • 【C语言】Linux 飞翔的小鸟
    【C语言】Linux飞翔的小鸟零、环境部署安装Ncurses库sudoapt-getinstalllibncurses5-dev壹、编写代码代码如下:bird.c#include<stdio.h>#include<time.h>#include<stdlib.h>#include<signal.h>#include<curses.h>#include<sys/time.h>#include<u......
  • 片集 - 数据结构 - 1
    欢迎来看“片”(的简介)由于-\(看片\)-生涯转瞬即逝,于是我选择对“\(片\)”进行一定的总结:相信你一定看懂了由于开始的时间有一点晚,就姑且认为我以后会慢慢补充吧......\(CF1270H\)\(Number\)\(of\)\(Components\)解:线段树首先我们可以发现连通块都是以区间的形式存在的......
  • 7.22数据结构
    笔记链表一.链表的引入1.1总结顺序表的优缺点    1)优点:能够直接通过下表进行定位元素,访问效率高,对元素进行查找修改比较快    2)不足:插入和删除元素需要移动大量的元素,效率较低    3)缺点:存储数据元素有上限,当达到MAX后,就不能再添加元素了、1.2链......
  • ##笔记day06-C语言基础:随机数、一维、二维数组、字符数组
    day07笔记1)rand生成随机数1)rand()随机函数头文件:#include<stdlib.h>函数原型:intrand(void);函数功能:生成大于等于0的随机整数参数:void返回值:生成的随机整数2)srand更新随机数种子(srand()函数用于给rand()函数设定种子)头文件:......
  • 20-c语言main函数参数`argc` 和 `argv[]` 解析
    argc和argv[]解析argc和argv[]是main函数的参数,用于处理命令行参数。一、示例命令行调用./a.out123345解释:./a.out是程序名,也是第一个参数。123和345是运行时传递的额外参数。二、main函数定义intmain(intargc,charconst*argv[]){re......
  • 【数据结构】:链表实现洗牌功能
    此操作包含的基本功能有:组牌:组建52张扑克牌四种花色:“♥️”,“♠️”,“⬛️”,“♣️”每种花色13张牌:1~13洗牌:将52张扑克牌打乱顺序发牌:给三个人每人发5张牌扩展功能:清牌:将每人手中牌按照面值进行从大到小排序Card类在此类中,我们将完成对每一张牌的构造类......
  • 数据结构与算法总结——线性表
    目录2线性表2.1线性表的定义2.2线性表的基本操作2.2顺序表2.2.1顺序表的定义2.2.2顺序表的基本操作2.3链式表2.3.1链表的定义2.3.2链表的分类2.3.3单向链表2.3.3.1结点设计2.3.3.2链表的初始化2.3.3.3数据的插入2.3.3.4数据的删除2.3.3.5销毁链......
  • 手撕数据结构01--单链表(附源码)
    目录1.链表的概念和结构1.1链表的概念1.2单链表结构2.实现单链表2.1节点定义2.2链表功能2.3 创建节点2.4尾插2.5头插2.6打印2.7尾删2.8头删2.9查找2.10指定位置插入2.11指定位置之后插入2.12删除pos节点2.13删除pos之后的节点2.14销毁链表......
  • C语言结构体及位域
    一.结构体1.定义和声明结构体是由不同数据类型数据构成的组合型的数据结构,是用户自定义的数据类型。2.结构体类型的声明格式:struct结构体名{   成员列表};举个例子,写一个用来放学生信息的结构体structSTU{    charname[20];  //用来放学生姓名的数组......