网站排名 优帮云,小规模公司简介怎么写,网站域名怎么设置方法,公众号开发者id详解小白如何使用C语言实现堆数据结构 “痛”撕堆排序~#x1f60e; 前言#x1f64c;什么是堆#xff1f;堆的概念及结构 堆的性质#xff1a;堆的实现堆向下调整算法画图分析#xff1a;堆向下调整算法源代码分享#xff1a;向下调整建小堆向下调整建大堆 堆向上调整算… 详解小白如何使用C语言实现堆数据结构 “痛”撕堆排序~ 前言什么是堆堆的概念及结构 堆的性质堆的实现堆向下调整算法画图分析堆向下调整算法源代码分享向下调整建小堆向下调整建大堆 堆向上调整算法源代码分享画图分析向上调整建小堆向上调整建大堆 C语言整体实现堆数据结构源代码分享堆的插入堆的删除画图分析 头文件(Heap.h)编写功能文件Heap.c编写测试文件test.c编写运行结果测试截图 总结撒花 博客昵称博客小梦 最喜欢的座右铭全神贯注的上吧 作者简介一名热爱C/C算法等技术、喜爱运动、热爱K歌、敢于追梦的小博主 博主小留言哈喽各位CSDN的uu们我是你的博客好友小梦希望我的文章可以给您带来一定的帮助话不多说文章推上欢迎大家在评论区唠嗑指正觉得好的话别忘了一键三连哦 前言 哈喽各位友友们我今天又学到了很多有趣的知识现在迫不及待的想和大家分享一下我仅已此文手把手带领大家追梦之旅【数据结构篇】——详解小白如何使用C语言实现堆数据结构~ 都是精华内容可不要错过哟 什么是堆
堆的概念及结构
如果有一个关键码的集合K { … }把它的所有元素按完全二叉树的顺序存储方式存储在一个一维数组中并满足
父结点的值都大于孩子结点的值则称为大堆父结点的值都小于孩子结点的值则称为小堆 大堆也称为大根堆小堆也叫做小根堆。
堆的性质
堆中某个节点的值总是不大于或不小于其父节点的值堆总是一棵完全二叉树。 堆的实现
堆向下调整算法
现在我们给出一个数组逻辑上看做一颗完全二叉树。我们通过从根节点开始的向下调整算法可以把它调整成一个小堆。向下调整算法有一个前提左右子树必须是一个堆才能调整。
画图分析 堆向下调整算法源代码分享
向下调整建小堆
//向下调整--建小堆
void AdjustDown(int* a, int size, int parent)
{int child parent * 2 1;while (child size){if (child 1 size a[child 1] a[child]){child;}if (a[child] a[parent]){Swap((a[parent]), (a[child]));parent child;child parent * 2 1;}else{break;}}
}
向下调整建大堆
//建大堆
void AdjustDown(int* a, int size, int parent)
{int child parent * 2 1;while (child size){if (child 1 size a[child 1] a[child]){child;}if (a[child] a[parent]){Swap((a[parent]), (a[child]));parent child;child parent * 2 1;}else{break;}}
}
堆向上调整算法源代码分享
画图分析 向上调整建小堆
void AdjustUp(HPDataType* a, int child)
{assert(a);while (child 0){int parent (child - 1) / 2;if (a[child] a[parent]){Swap((a[child]), (a[parent]));child parent;parent (child - 1) / 2;}else{break;}}
}向上调整建大堆
//向上调整建大堆
void AdjustUp(HPDataType* a, int child)
{assert(a);while (child 0){int parent (child - 1) / 2;if (a[child] a[parent]){Swap((a[child]), (a[parent]));child parent;parent (child - 1) / 2;}else{break;}}
}C语言整体实现堆数据结构源代码分享
堆的插入
先插入一个10到数组的尾上再进行向上调整算法直到满足堆。
void HeapPush(HP* php, HPDataType x)
{assert(php);//扩容if (php-capacity php-size){int newcapacity php-capacity 0 ? 4 : php-capacity * 2;HPDataType* tem (HPDataType*)realloc(php-a, sizeof(HPDataType) * newcapacity);if (tem NULL){printf(realloc fail\n);exit(-1);}php-a tem;php-capacity newcapacity;}php-a[php-size] x;//向上调整--建小堆if(php-size 0)AdjustUp(php-a, php-size);php-size;
}堆的删除
删除堆是删除堆顶的数据将堆顶的数据和最后一个数据一换然后删除数组最后一个数据再进行向下调整算法。
画图分析 void HeapPop(HP* php)
{assert(php);assert(!HeapEmpty(php));Swap((php-a[0]), (php-a[php-size - 1]));php-size--;AdjustDwon(php-a, php-size,0);
}头文件(Heap.h)编写
#pragma once#includestdio.h
#includestdlib.h
#includeassert.h
#includestdbool.htypedef int HPDataType;typedef struct Heap
{HPDataType* a;int size;int capacity;
}HP;
void Swap(HPDataType* p1, HPDataType* p2);
// O(logN)
void AdjustDwon(HPDataType* a, int size, int parent);
void AdjustUp(HPDataType* a, int child);void HeapPrint(HP* php);
void HeapInit(HP* php);
void HeapDestroy(HP* php);
void HeapPush(HP* php, HPDataType x);
void HeapPop(HP* php);
HPDataType HeapTop(HP* php);
bool HeapEmpty(HP* php);
int HeapSize(HP* php);
功能文件Heap.c编写
#define _CRT_SECURE_NO_WARNINGS 1#includeHeap.hvoid Swap(HPDataType* p1, HPDataType* p2)
{int tem *p1;*p1 *p2;*p2 tem;
}
// O(logN)
//建小堆
void AdjustDwon(HPDataType* a, int size, int parent)
{assert(a);int child parent * 2 1;while (child size){//选出最小的那个if (child 1 size a[child 1] a[child]){child;}if (a[child] a[parent] ){Swap((a[parent]), (a[child]));parent child;child parent * 2 1;}else{break;}}
}
void AdjustUp(HPDataType* a, int child)
{assert(a);while (child 0){int parent (child - 1) / 2;if (a[child] a[parent]){Swap((a[child]), (a[parent]));child parent;parent (child - 1) / 2;}else{break;}}
}void HeapPrint(HP* php)
{assert(php);for (int i 0; i php-size; i){printf(%d , php-a[i]);}printf(\n);
}
void HeapInit(HP* php)
{assert(php);php-a NULL;php-capacity php-size 0;
}
void HeapDestroy(HP* php)
{assert(php);free(php-a);php-a NULL;php-capacity php-size 0;
}
void HeapPush(HP* php, HPDataType x)
{assert(php);//扩容if (php-capacity php-size){int newcapacity php-capacity 0 ? 4 : php-capacity * 2;HPDataType* tem (HPDataType*)realloc(php-a, sizeof(HPDataType) * newcapacity);if (tem NULL){printf(realloc fail\n);exit(-1);}php-a tem;php-capacity newcapacity;}php-a[php-size] x;//向上调整--建小堆if(php-size 0)AdjustUp(php-a, php-size);php-size;}void HeapPop(HP* php)
{assert(php);assert(!HeapEmpty(php));Swap((php-a[0]), (php-a[php-size - 1]));php-size--;AdjustDwon(php-a, php-size,0);
}HPDataType HeapTop(HP* php)
{assert(php);assert(!HeapEmpty(php));return php-a[0];
}
bool HeapEmpty(HP* php)
{assert(php);return php-size 0;
}
int HeapSize(HP* php)
{assert(php);return php-size;
}
测试文件test.c编写
#define _CRT_SECURE_NO_WARNINGS 1#includeHeap.hvoid HeapTest1()
{HP h;HeapInit(h);HeapPush(h, 15);HeapPush(h, 18);HeapPush(h, 19);HeapPush(h, 25);HeapPush(h, 28);HeapPush(h, 34);HeapPush(h, 65);HeapPush(h, 49);HeapPush(h, 27);HeapPush(h, 37);HeapPush(h, 10);printf(%d\n, HeapSize(h));HeapPrint(h);for (int i 0; i 8; i){printf(%d , HeapTop(h));HeapPop(h);}printf(\n);HeapDestroy(h);printf(%d , HeapTop(h));HeapPop(h);
}int main()
{HeapTest1();return 0;
}运行结果测试截图 总结撒花 本篇文章旨在分享详解小白如何使用C语言实现堆数据结构。希望大家通过阅读此文有所收获 如果我写的有什么不好之处请在文章下方给出你宝贵的意见。如果觉得我写的好的话请点个赞赞和关注哦~
