C语言数据结构堆的基本操作实现是怎样的

本篇文章为大家展示了C语言数据结构堆的基本操作实现是怎样的，内容简明扼要并且容易理解，绝对能使你眼前一亮，通过这篇文章的详细介绍希望你能有所收获。

1.基本函数实现

a.代码1(向下调整)

void AdjustDown(DateType*a, int n, int parent){        int child = parent * 2 + 1;        while (child a[child + 1])                {                        ++child;                }                if (a[parent] > a[child])                {                        Swap(&a[parent], &a[child]);                        parent = child;                        child = parent * 2 + 1;                }                else                {                        break;                }        }}

注意:if里面的条件语句(child +1)

b.代码2(向上调整)

void AdjustUp(DateType*a , int child){        int parent = (child - 1) / 2;        while (child > 0)        {                if (a[child] < a[parent])                {                        Swap(&a[child], &a[parent]);                        child = parent;                        parent = (child - 1) / 2;                }                else                {                        break;                }        }}

注意:while里面的条件语句是不能够写成(parent<0)，因为当child==0时，parent=(child - 1) / 2,parent==0,再次进入循环不满足a[child] < a[parent]，恰好跳出循环。如果写成(a[child] <= a[parent])就死循环了

c.代码3(交换）

void Swap(DateType*p1, DateType*p2){        DateType tmp = *p1;        *p1 = *p2;        *p2 = tmp;}

2.建堆

void CreatHeap(Heap*p,DateType*num,int n){        assert(p);        p->a = (DateType*)malloc(n * sizeof(DateType));        if (p->a == NULL)        {                printf("malloc failed\n");                exit(-1);        }        memcpy(p->a, num, n * sizeof(DateType));        p->size = n;        p->capacity = n;        //建小堆        for (int i = (n - 1 - 1) / 2; i >= 0; i--)        {                AdjustDown(p->a, p->size, i);        }}

3.插入数据

void HeapPush(Heap*p, DateType x){        assert(p);        if (p->size == p->capacity)        {                DateType*tmp = (DateType*)realloc(p->a, (p->capacity) * 2 * sizeof(DateType));                if (tmp == NULL)                {                        printf("realloc  failed\n ");                        exit(-1);                }        }        (p->capacity) *= 2;        p->a[p->size] = x;        ++(p->size);        //向上调整        AdjustUp(p->a, p->size-1);}

4. 删除数据

void HeapPop(Heap*p, DateType x){        assert(p);        Swap(&p->a[0], &p->a[p->size-1]);        --(p->size);        AdjustDown(p->a, p->size, 0);        //左右子树还是小堆，直接调整行了}

把堆顶的数据与最后一个数据交换，再次调整size-1个数据。

5.获取堆顶的数据

DateType HeapTop(Heap*p){        assert(p);        return p->a[0];}

6.堆的数据个数

int HeapSize(Heap*p){        assert(p);        return p->size;}

7.判空

bool HeapIsEmpty(Heap*p){        assert(p);        return p->size == 0;}

8.打印

void Print(Heap*p){        assert(p);        for (int i = 0; i < p->size; i++)        {                printf("%d ", (p->a)[i]);        }        printf("\n");        int count = 0;//计数        int levelsize = 1;        for (int i = 0; i < p->size; i++)        {                printf("%d ", p->a[i]);                ++count;                if (count == levelsize)                {                        printf("\n");                        levelsize *= 2;                        count = 0;//重新计数                }        }        printf("\n");}

9.销毁

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

10.测试

int main(){        int num[] = { 12,15,17,23,10,25 };        int n = sizeof(num) / sizeof(num[0]);         Heap a;   //创建小堆        CreatHeap(&a,num, n);        Print(&a);        printf("\n");         //插入数据        HeapPush(&a, 1);        Print(&a);   //删除对顶的数据        HeapPop(&a);        Print(&a);        printf("\n");         //获取堆顶数据        int ret=HeapTop(&a);        printf("The top date is %d\n",ret);         //堆的数据个数        int number=HeapSize(&a);        printf("The number of heap is %d\n", number);         //销毁        HeapDestory(&a);         return 0;}

11.测试结果

12.用堆排序(降序)

a.代码1

int main(){        DateType num[] = { 12,15,17,23,10,25 };        int n = sizeof(num) / sizeof(num[0]);        HeapSort(num, n);        for (int i = 0; i < n; i++)        {                printf("%d ", num[i]);        }        printf("\n\n");        return 0;}

void HeapSort(int*num, int n){        //建小堆        for (int i = (n - 1 - 1) / 2; i >= 0; i--)        {                AdjustDown(num, n, i);        }        int end = n - 1;        while (end>0)        {                Swap(&num[0], &num[end]);                AdjustDown(num, end, 0);                --end;        }}

运行结果

上述内容就是C语言数据结构堆的基本操作实现是怎样的，你们学到知识或技能了吗？如果还想学到更多技能或者丰富自己的知识储备，欢迎关注行业资讯频道。