堆的实现（C语言）-创新互联

数据结构的一点练习~~~~该堆借助数组实现

😋😋😋😋😂

目录

一、需要实现的函数接口 

二、函数各接口的具体实现

#include#include 
#includetypedef int  type;
typedef struct Heap
{
    type* a;
    int size;
    int capacity;
}Heap;


void HP_initial(Heap* php);//堆的初始化
void HP_push(Heap* php,type x);//堆的插入
void HP_destory(Heap* php);//堆的销毁
void HP_pop(Heap* php);//堆的删除
void HP_craet(Heap* php,type * arr ,int n);//堆的创建
int HP_size(Heap* php);//堆的数据个数
type HP_top(Heap * php;//取堆顶的数据
void HP_print(Heap* php);//堆的打印

1.首先是一些需要的工具型函数

void SpaceCreat(type** pa,int n)
{
    type* temp=(type*)realloc(*pa,sizeof(type)*n);
    if(temp==NULL)
    {
        printf("开辟空间失败");
        exit(-1);
    }
    *pa=temp;
}//开辟type型数组的空间

void swap(type* a, type* b)
{
    type t=*a;
    *a=*b;
    *b=t; 
}//交换两数的值

void SortUp(type* a,int child)
{
    int parent=(child-1)/2;
    while(child)
    {
        if(a[parent]

2.接口函数的实现

void HP_initial(Heap* php)
{
    php->a=NULL;
    php->capacity=0;
    php->size=0;
}//堆的初始化


void HP_push(Heap* php,type x)
{
    if(php->capacity==0)
    {
        php->capacity=4;
        SpaceCreat(&(php->a), php->capacity);
    }
    if(php->capacity==php->size)
    {
       php->capacity=2*php->capacity;
       SpaceCreat(&(php->a), php->capacity);
    }
    php->a[php->size]=x;

    SortUp(php->a,php->size);
    php->size++;
}//堆的插入


void HP_print(Heap* php)
{
    for(int i=0;isize;i++)
    {
        printf("%d ",php->a[i]);
    }
}//堆的打印


void HP_destory(Heap* php)
{
    free(php->a);
    php->a=NULL;
    php->capacity=0;
    php->size=0;
}//堆的销毁


void HP_pop(Heap* php)
{
    if(php->size<=1)
    {
        php->size=0;
        return;
    }
    swap(&php->a[php->size-1],&php->a[0]);
    php->size--;
    int parent=0;
    int child=1;
    while(1)
    {
        if(php->a[child]>php->a[parent])
        {
            swap(&php->a[child],&php->a[parent]);
        }
        parent=child;
        child=2*child+1;
        if(child>php->size-1)
        {
            break;
        }
        if(php->a[child]a[child+1]&&child!=php->size-1)
        {
            child++;
        }
    }
}//堆的删除


void HP_craet(Heap* php,type * arr ,int n)//n为所传数组的元素个数
{
    for(int i=0;isize;
}//堆的数据个数


type HP_top(Heap * php)
{
    return php->a[0];
}//取堆顶的数据

欢迎指正😘😘😘😘😘

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧