【数据结构】C语言实现堆(附完整运行代码)

简介: 【数据结构】C语言实现堆(附完整运行代码)

一.了解项目功能

在本次项目中我们的目标是实现一个使用顺序结构存储:

使用动态内存分配空间,可以用来存储任意数量的同类型数据.

需要包含三个要素:存储数据的数组a,堆的当前存储容量capacity,堆当前的长度size.

结构的图示如下:

堆程序提供的功能有:

  1. 堆的初始化.
  2. 数据元素入堆.
  3. 数据元素出堆.
  4. 数据元素向上调整.
  5. 数据元素向下调整.
  6. 取堆顶元素.
  7. 堆判空.
  8. 打印大堆.
  9. 堆的元素个数.
  10. 堆销毁.

二.项目功能演示(以大堆为例)

要编写一个堆项目,首先要明确我们想要达到的效果是什么样,下面我将用vs2022编译器来为大家演示一下堆程序运行时的样子:

堆程序演示


这是演示过程中程序生成的堆数组,我们将数组构建成堆验证一下:

可以看到,程序生成的大堆是符合堆的特性的.


三.逐步实现项目功能模块及其逻辑详解

通过第二部分对项目功能的介绍,我们已经对  的功能有了大致的了解,虽然看似需要实现的功能很多,貌似一时间不知该如何下手,但我们可以分步分模块来分析这个项目的流程,最后再将各部分进行整合,所以大家不用担心,跟着我一步一步分析吧!


!!!注意,该部分的代码只是为了详细介绍某一部分的项目实现逻辑,故可能会删减一些与该部分不相关的代码以便大家理解,需要查看或拷贝完整详细代码的朋友可以移步本文第四部分。


1.实现堆程序主函数

由于我们要实现堆的功能可以反复使用的逻辑,且至少在一开始执行一次,因此我们选择do...while的循环语句来实现这一部分的逻辑.

该部分功能实现代码如下:

int main()
{
    HP hp;
    HeapInit(&hp);
 
    int swi = 0;//创建变量swi作为do...while循环的终止条件,以及switch语句的运行条件
    do          //使用do...while实现
    {
 
        HeapMenu();
        scanf("%d", &swi);
 
        switch (swi)
        {
        case 0:
            // 释放堆内存
            HeapDestory(&hp);
            printf("您已退出程序:>\n");
 
            break;
 
        case 1:
            printf("请输入要入堆的数据:>");
            HPDataType push_data = 0;
            scanf("%d", &push_data);
 
            HeapPush(&hp, push_data);
 
            printf("已成功入堆:>\n");
            break;
 
        case 2:
            HeapPop(&hp);
            printf("出堆成功:>\n");
 
            break;
 
        case 3:
            printf("堆顶元素为:");
            HPDataType e = HeapTop(&hp);
            printf("%d\n", e);
 
            break;
 
        case 4:
            if (!HeapEmpty(&hp))
            {
                printf("当前堆不为空:>\n");
            }
            else
            {
                printf("当前堆为空\n");
            }
 
            break;
 
        case 5:
            printf("当前堆长度为:");
            int size = HeapSize(&hp);
            printf("%d\n", size);
 
            break;
 
        case 6:
            HeapPrint(&hp);
            
            break;
 
        default:
            printf("输入错误,请重新输入\n");
            break;
        }
    } while (swi);
 
    return 0;
}

2.创建堆结构

创建堆结构成员的结构体应该包括:存储数据的数组a,堆的当前存储容量capacity,堆当前的长度size.

因此我们创建Heap结构体类型时应一个数组两个整型组成.

堆结构图示如下:

这里的第一行使用的typedef类定义的作用是方便我们后续在使用堆时对存储的数据类型做更改,比如后续我们不想在堆中存储int类型数据了,就可以很方便的在这里对数组类型做更改.

实现代码逻辑如下:

typedef int HPDataType;
 
//堆的结构存储结构很像顺序表
 
typedef struct Heap
{
  HPDataType* a;
  int size;
  int capacity;
}HP;

3.堆的初始化

初始化堆的逻辑不难,但代码编写的细节上可能会需要多注意一些:

首先在进入初始化函数后,我们应当对函数传进来的参数做一个检验,即检验php指针是否为空指针,如果该指针为空的话,那么指针变量就没有指向任何有效的内存地址,即指针变量的值为0NULL。这时我们再进入下一步强行开辟内存空间就很可能会导致程序出现一些问题:

tips:

   用空指针接收malloc函数返回值的危害是非常严重的,因为它会导致程序出现未定义的行为,甚至可能会导致程序崩溃

   当我们调用malloc函数时,它会在堆上分配一块指定大小的内存,并返回指向该内存的指针。如果我们用空指针来接收malloc函数返回的指针,那么就相当于没有为分配的内存分配任何指针变量,这意味着我们无法访问该内存块,也无法释放该内存块,因为我们没有指向它的指针。

   这种情况下,如果我们试图访问该内存块,就会发生未定义的行为,也可能会导致程序崩溃。此外,如果我们忘记释放该内存块,就会导致内存泄漏,这会导致程序消耗大量的内存资源,最终导致程序崩溃或者系统变慢。

   因此,我们应该始终使用有效的指针变量来接收malloc函数返回的指针,以确保我们能够正确地访问和释放动态分配的内存块。

因此,我们可以使用assert来对函数传进来的参数php进行检验,如果php为空,那么立刻终止程序,并抛出异常警告程序员.

https://blog.csdn.net/weixin_72357342/article/details/133822893?spm=1001.2014.3001.5502

检验参数指针没有问题后,我们就可以开始进行初始化相关操作了:

  1. 首先,我们为数组a动态开辟一块空间.
  2. 然后,给size赋值为0
  3. 最后,给capacity赋值为前面动态开辟的数组容量

至此,和顺序表初始化一模一样的堆初始化就完成了,该部分代码如下:

void HeapInit(HP* php)
{
  assert(php);
 
  php->a = (HPDataType*)malloc(sizeof(HPDataType) * 4);
  if (php->a == NULL)
  {
    perror("malloc fail::\n");
    return;
  }
 
  php->size = 0;
  php->capacity = 4;
}

4.数据元素入堆

入堆的物理逻辑是:

  • 先判断当前堆长度是否满了,如果满了要对堆的容量进行扩容.
  • 然后的入堆逻辑和顺序表插入元素相同,都是直接按下标给堆尾赋值就行.
  • 赋值结束后同样需要给堆长度+1.
  • 随后将新入堆的元素向上调整.

入堆逻辑结构图示如下(大堆):

入堆的物理结构如下:

该部分代码实现如下:

void HeapPush(HP* php, HPDataType x)
{
  assert(php);
  //查满扩容
  if (php->size == php->capacity)
  {
    HPDataType*tmp = (HPDataType*)realloc(php->a, sizeof(HPDataType) * php->capacity * 2);
    if (tmp == NULL)
    {
      perror("realloc fail::\n");
      return;
    }
    php->a = tmp;
    php->capacity *= 2;
  }
 
  //入数据
  php->a[php->size] = x;
  php->size++;
  
  //向上调整建堆
  AdjustUp(php->a, php->size - 1);
}

5.数据元素向上调整

入堆部分其实我们的逻辑还没有结束,因为堆和顺序表不同的点就在于,顺序表插入元素后就没有别的事了,但堆中元素入堆后需要进行向上调整,因为我们不能保证新入的元素一定完全符合堆定义的要求,为了防止新插入的元素破坏堆的性质,因此我们需要对新入堆的元素进行向上调整,直到调整到其满足堆排序的性质为止.

为了方便理解,我们拿刚才的大堆做一下演示,逻辑图示如下:

此时我们对于新入结点的向上调整就结束了,可以发现,在向上调整结束后,我们的堆就又重新符合大堆的特性了.

搞清楚逻辑结构,我们再来看一下在存储逻辑上这个调整是如何实现的:

首先,我们要知道顺序存储结构存储完全二叉树时双亲结点和左右孩子的下标关系:

  • parent=(child-1)/2
  • leftchild=parent*2+1
  • rightchild=parent*2+2

通过这几个公式,我们就可以很方便的在堆里对双亲和孩子结点进行调整.

如图,在存储结构上,我们首先将数据元素进行入堆:

其次,我们找到当前入堆元素的双亲结点,并与之比较:

此时入堆元素大于双亲,我们继续交换:

直到调整到入堆元素比双亲结点小入堆元素成为根节点时,我们结束向上调整:

综上,该部分实现代码如下:

//向上调整
void AdjustUp(HPDataType* a, int child)
{
  int parent = ( child - 1 ) / 2;
  //判断,如果孩子大于双亲,换,否则结束[正因此是大堆]
 
  while (child > 0 && a[child] > a[parent])
  {
    //交换函数
    Swap(&a[child], &a[parent]);
 
    //移动下标,使入堆元素继续向上调整
    child = parent;
    parent = (child - 1) / 2;
  }
 
}

6.数据元素出堆

因为堆的特性使得堆顶元素一定为当前堆中最大/小的值,因此我们出堆操作往往需要出的是堆顶元素.

但是我们不能直接将堆顶元素删除,因为这样会导致堆中剩下的元素关系全部乱掉:

后面剩余的数据也完全不符合大堆/小堆的特性:

因此合理的操作出堆顶就将堆顶元素和堆尾元素交换,然后将新堆顶元素向下调整到合适的位置上:

综上,出堆的逻辑为:

  1. 判空,为空则无法再出堆
  2. 交换堆顶元素与堆尾元素
  3. 将交换后的堆尾元素删除
  4. 将交换后的堆顶元素向下调整
//出堆
void HeapPop(HP* php)
{
  assert(php);
  assert(!HeapEmpty(php));
  //先交换堆顶元素和堆尾元素
  Swap(&php->a[0], &php->a[php->size-1]);
 
  //删除交换后的堆尾元素(即原来的堆顶)
  php->size--;
 
  //将新堆顶元素向下调整
  AdjustDown(php->a, php->size, 0);
}

7.数据元素向下调整

为了方便理解向下调整,我们继续拿之前的大堆做一个演示:

首先是交换堆顶和堆尾元素:

其次将交换后的新堆顶元素和两个孩子做比较,如果是大堆,那么只要孩子比新堆顶元素,二者就交换位置,如果两个孩子都比堆顶元素大,则堆顶元素和较大的那个孩子交换位置.

直到向下调整到叶子结点位置交换到该堆顶元素比两个孩子结点都大停止向下调整:

搞清楚逻辑结构,我们再来看一下在存储逻辑上这个向下调整是如何实现的:

首先,交换堆首和堆尾元素:

还是利用前面提到的两个公式来计算该结点的左孩子结点和右孩子结点,再进行比较:

直到调整到叶子结点交换到该堆顶元素比两个孩子结点都大停止向下调整:

注意:向上调整我们只需要将入堆元素与它的双亲结点比较,而向下调整时我们需要先比较出结点的两个孩子的大小,然后双亲结点与大的/小的(取决于大堆还是小堆)孩子交换位置,直到将该结点交换至叶子结点或比两个孩子结点都大/小为止.

该部分代码逻辑如下:

//向下调整建堆,左右子树必须是大堆或者小堆
void AdjustDown(HPDataType* a, int n, int parent)
{
  int child = parent * 2 + 1;//默认是左孩子
  while (child < n)//孩子走到叶子就不走了
  {
    //选出左右孩子中大的那个
    if (child + 1<n && a[child + 1] > a[child])//如果右孩子存在且大于左孩子
    {
      child++;
    }
    //向下调整重新使堆有序
    if (a[child] > a[parent])
    {
            //交换两个元素
      Swap(&a[child], &a[parent]);
            //继续向后调整
      parent = child;
      child = parent * 2 + 1;
    }
    else
    {
      break;
    }
  }
}

8.取堆顶元素

取堆顶元素在物理结构上看就是访问数组的首元素:

因此该部分的逻辑就是直接访问数组首元素即可.

该部分代码逻辑如下:

HPDataType HeapTop(HP* php)
{
  assert(php);
  return php->a[0];
}

9.堆判空

因为我们在设计堆时有设置变量记录堆内的元素长度,因此在判空时我们只需要判断size是否等于0即可.

该部分代码逻辑如下:

int HeapSize(HP* php)
{
  assert(php);
  return php->size;
}

10.堆的元素个数

和判空部分一样,直接访问size并返回即可.

该部分代码逻辑如下:

int HeapSize(HP* php)
{
  assert(php);
  return php->size;
}

11.打印大堆

因为我们将堆存储在数组中,因此打印逻辑很简单,即遍历打印数组元素即可.

该部分代码实现如下:

void HeapPrint(HP* php)
{
  assert(php);
  //循环打印数组
  int i = 0;
 
  while (i < php->size)
  {
    printf("%d ", php->a[i]);
    i++;
  }
  printf("\n");
}

12.堆销毁

在堆程序使用结束后,我们需要将之前动态开辟的内存还给操作系统,并将其指针置空,size,capacity置为0.

该部分代码如下:

void HeapDestory(HP* php)
{
  assert(php);
 
  free(php->a);
 
  php->a = NULL;
  php->capacity = php->size = 0;
}

四.项目完整代码

我们将程序运行的代码分别在三个工程文件中编辑,完整代码如下:

test.c文件

#include"Heap.h"
 
int main()
{
    HP hp;
    HeapInit(&hp);
 
    int swi = 0;//创建变量swi作为do...while循环的终止条件,以及switch语句的运行条件
    do          //使用do...while实现
    {
 
        HeapMenu();
        scanf("%d", &swi);
 
        switch (swi)
        {
        case 0:
            // 释放堆内存
            HeapDestory(&hp);
            printf("您已退出程序:>\n");
 
            break;
 
        case 1:
            printf("请输入要入堆的数据:>");
            HPDataType push_data = 0;
            scanf("%d", &push_data);
 
            HeapPush(&hp, push_data);
 
            printf("已成功入堆:>\n");
            break;
 
        case 2:
            HeapPop(&hp);
            printf("出堆成功:>\n");
 
            break;
 
        case 3:
            printf("堆顶元素为:");
            HPDataType e = HeapTop(&hp);
            printf("%d\n", e);
 
            break;
 
        case 4:
            if (!HeapEmpty(&hp))
            {
                printf("当前堆不为空:>\n");
            }
            else
            {
                printf("当前堆为空\n");
            }
 
            break;
 
        case 5:
            printf("当前堆长度为:");
            int size = HeapSize(&hp);
            printf("%d\n", size);
 
            break;
 
        case 6:
            HeapPrint(&hp);
            
            break;
 
        default:
            printf("输入错误,请重新输入\n");
            break;
        }
    } while (swi);
 
    return 0;
}

 Heap.c 文件

#include"Heap.h"
 
 
void HeapInit(HP* php)
{
  assert(php);
 
  php->a = (HPDataType*)malloc(sizeof(HPDataType) * 4);
  if (php->a == NULL)
  {
    perror("malloc fail::\n");
    return;
  }
 
  php->size = 0;
  php->capacity = 4;
}
 
void Swap(HPDataType* p1, HPDataType* p2)
{
  HPDataType tmp = *p1;
  *p1 = *p2;
  *p2 = tmp;
}
 
//向上调整
void AdjustUp(HPDataType* a, int child)
{
  int parent = ( child - 1 ) / 2;
  //判断,如果孩子大于双亲,换,否则结束[正因此是大堆]
 
  while (child > 0 && a[child] > a[parent])
  {
    //交换函数
    Swap(&a[child], &a[parent]);
 
    //移动下标,使入堆元素继续向上调整
    child = parent;
    parent = (child - 1) / 2;
  }
}
 
void HeapPush(HP* php, HPDataType x)
{
  assert(php);
  //查满扩容
  if (php->size == php->capacity)
  {
    HPDataType*tmp = (HPDataType*)realloc(php->a, sizeof(HPDataType) * php->capacity * 2);
    if (tmp == NULL)
    {
      perror("realloc fail::\n");
      return;
    }
    php->a = tmp;
    php->capacity *= 2;
  }
 
  //入数据
  php->a[php->size] = x;
  php->size++;
  
  //向上调整建堆
  AdjustUp(php->a, php->size - 1);
}
 
//向下调整建堆,左右子树必须是大堆或者小堆
void AdjustDown(HPDataType* a, int n, int parent)
{
  int child = parent * 2 + 1;//默认是左孩子
  while (child < n)//孩子走到叶子就不走了
  {
    //选出左右孩子中大的那个
    if (child + 1<n && a[child + 1] > a[child])//如果右孩子存在且大于左孩子
    {
      child++;
    }
    //向下调整重新使堆有序
    if (a[child] > a[parent])
    {
      Swap(&a[child], &a[parent]);
      parent = child;
      child = parent * 2 + 1;
    }
    else
    {
      break;
    }
  }
}
 
 
//出堆
void HeapPop(HP* php)
{
  assert(php);
  assert(!HeapEmpty(php));
  //先交换堆顶元素和堆尾元素
  Swap(&php->a[0], &php->a[php->size-1]);
 
  //删除交换后的堆尾元素(即原来的堆顶)
  php->size--;
 
  //将新堆顶元素向下调整
  AdjustDown(php->a, php->size, 0);
}
 
 
 
HPDataType HeapTop(HP* php)
{
  assert(php);
  return php->a[0];
}
 
bool HeapEmpty(HP* php)
{
  assert(php);
  return php->size == 0;
}
 
int HeapSize(HP* php)
{
  assert(php);
  return php->size;
}
 
void HeapDestory(HP* php)
{
  assert(php);
 
  free(php->a);
 
  php->a = NULL;
 
  php->capacity = php->size = 0;
 
}
 
 
 
void HeapMenu()
{
  printf("**********************************\n");
  printf("******请选择要进行的操作    ******\n");
  printf("******1.入堆                ******\n");
  printf("******2.出堆                ******\n");
  printf("******3.取堆顶元素          ******\n");
  printf("******4.判断堆空            ******\n");
  printf("******5.查询当前堆长度      ******\n");
  printf("******6.打印大堆            ******\n");
  printf("******0.退出堆程序          ******\n");
  printf("**********************************\n");
  printf("请选择:>");
}
 
void HeapPrint(HP* php)
{
  assert(php);
  //循环打印数组
  int i = 0;
 
  while (i < php->size)
  {
    printf("%d ", php->a[i]);
    i++;
  }
  printf("\n");
}

Heap.h文件

#define _CRT_SECURE_NO_WARNINGS 1
 
#pragma once
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include<stdbool.h>
 
 
typedef int HPDataType;
 
//堆的结构存储结构很像顺序表
typedef struct Heap
{
  HPDataType* a;
  int size;
  int capacity;
}HP;
 
//堆的初始化
void HeapInit(HP* php);
//数据元素入堆
void HeapPush(HP* php,HPDataType x);
//数据元素出堆
void HeapPop(HP* php);
//元素向上调整
void AdjustUp(HPDataType* a, int child);
//元素向下调整
void AdjustDown(HPDataType* a, int n, int parent);
//取堆顶元素
HPDataType HeapTop(HP* php);
//堆判空
bool HeapEmpty(HP* php);
//堆元素个数
int HeapSize(HP* php);
//堆销毁
void HeapDestory(HP* php);
//堆菜单
void HeapMenu();
//堆打印
void HeapPrint(HP* php);

结语

希望这篇堆的C语言实现详解能对大家有所帮助,欢迎大佬们留言或私信与我交流.

学海漫浩浩,我亦苦作舟!关注我,大家一起学习,一起进步!



相关文章
|
15天前
|
C语言
【数据结构】栈和队列(c语言实现)(附源码)
本文介绍了栈和队列两种数据结构。栈是一种只能在一端进行插入和删除操作的线性表,遵循“先进后出”原则;队列则在一端插入、另一端删除,遵循“先进先出”原则。文章详细讲解了栈和队列的结构定义、方法声明及实现,并提供了完整的代码示例。栈和队列在实际应用中非常广泛,如二叉树的层序遍历和快速排序的非递归实现等。
90 9
|
12天前
|
存储 算法 Java
散列表的数据结构以及对象在JVM堆中的存储过程
本文介绍了散列表的基本概念及其在JVM中的应用,详细讲解了散列表的结构、对象存储过程、Hashtable的扩容机制及与HashMap的区别。通过实例和图解,帮助读者理解散列表的工作原理和优化策略。
26 1
散列表的数据结构以及对象在JVM堆中的存储过程
|
14天前
|
存储 搜索推荐 算法
【数据结构】树型结构详解 + 堆的实现(c语言)(附源码)
本文介绍了树和二叉树的基本概念及结构,重点讲解了堆这一重要的数据结构。堆是一种特殊的完全二叉树,常用于实现优先队列和高效的排序算法(如堆排序)。文章详细描述了堆的性质、存储方式及其实现方法,包括插入、删除和取堆顶数据等操作的具体实现。通过这些内容,读者可以全面了解堆的原理和应用。
57 16
|
14天前
|
C语言
【数据结构】二叉树(c语言)(附源码)
本文介绍了如何使用链式结构实现二叉树的基本功能,包括前序、中序、后序和层序遍历,统计节点个数和树的高度,查找节点,判断是否为完全二叉树,以及销毁二叉树。通过手动创建一棵二叉树,详细讲解了每个功能的实现方法和代码示例,帮助读者深入理解递归和数据结构的应用。
63 8
|
16天前
|
C语言
【数据结构】双向带头循环链表(c语言)(附源码)
本文介绍了双向带头循环链表的概念和实现。双向带头循环链表具有三个关键点:双向、带头和循环。与单链表相比,它的头插、尾插、头删、尾删等操作的时间复杂度均为O(1),提高了运行效率。文章详细讲解了链表的结构定义、方法声明和实现,包括创建新节点、初始化、打印、判断是否为空、插入和删除节点等操作。最后提供了完整的代码示例。
37 0
|
1月前
|
C语言 C++
C语言 之 内存函数
C语言 之 内存函数
34 3
|
机器学习/深度学习 人工智能 固态存储
C语言决赛代码
#include #include #include struct book { int num; char bname[50]; char wname[20]; char press[50]; char sort[50]; int time; float p...
853 0
|
7天前
|
C语言
c语言调用的函数的声明
被调用的函数的声明: 一个函数调用另一个函数需具备的条件: 首先被调用的函数必须是已经存在的函数,即头文件中存在或已经定义过; 如果使用库函数,一般应该在本文件开头用#include命令将调用有关库函数时在所需要用到的信息“包含”到本文件中。.h文件是头文件所用的后缀。 如果使用用户自己定义的函数,而且该函数与使用它的函数在同一个文件中,一般还应该在主调函数中对被调用的函数做声明。 如果被调用的函数定义出现在主调函数之前可以不必声明。 如果已在所有函数定义之前,在函数的外部已做了函数声明,则在各个主调函数中不必多所调用的函数在做声明
22 6
|
27天前
|
存储 缓存 C语言
【c语言】简单的算术操作符、输入输出函数
本文介绍了C语言中的算术操作符、赋值操作符、单目操作符以及输入输出函数 `printf` 和 `scanf` 的基本用法。算术操作符包括加、减、乘、除和求余,其中除法和求余运算有特殊规则。赋值操作符用于给变量赋值,并支持复合赋值。单目操作符包括自增自减、正负号和强制类型转换。输入输出函数 `printf` 和 `scanf` 用于格式化输入和输出,支持多种占位符和格式控制。通过示例代码详细解释了这些操作符和函数的使用方法。
34 10
|
20天前
|
存储 算法 程序员
C语言:库函数
C语言的库函数是预定义的函数,用于执行常见的编程任务,如输入输出、字符串处理、数学运算等。使用库函数可以简化编程工作,提高开发效率。C标准库提供了丰富的函数,满足各种需求。