网站改版 总结,中国核工业第二二建设有限公司招聘,建游戏网站,wordpress标签特效#x1f525;博客主页#xff1a;小王又困了
#x1f4da;系列专栏#xff1a;数据结构
#x1f31f;人之为学#xff0c;不日近则日退
❤️感谢大家点赞#x1f44d;收藏⭐评论✍️ 目录
一、二叉树的顺序结构
#x1f4d2;1.1顺序存储
#x1f4d2;1.2堆的性质…
博客主页小王又困了
系列专栏数据结构
人之为学不日近则日退
❤️感谢大家点赞收藏⭐评论✍️ 目录
一、二叉树的顺序结构
1.1顺序存储
1.2堆的性质
1.3堆的分类
二、堆的实现
2.1堆的创建
2.2堆的初始化
2.3堆的插入
2.4向上调整数据
2.5堆的删除
2.6向下调整数据
2.7堆的销毁 ️前言 在上一期的文章中我们学习了一些二叉树的知识也了解了堆的概念。堆是一颗完全二叉树分为大堆和小堆今天我们将实现堆的各种功能。 一、二叉树的顺序结构
1.1顺序存储
顺序结构存储就是使用数组来存储一般使用数组只适合表示完全二叉树因为不是完全二叉树会有空间的浪费。而现实使用中只有堆才会使用数组来存储。二叉树顺序存储在物理上是一个数组在逻辑上是一颗二叉树。 1.2堆的性质 堆中某个节点的之总是不大于或不小于其父亲节点的值堆是一颗完全二叉树 1.3堆的分类 小堆树中任意一个父亲都小于等于孩子大堆树中任意一个父亲都大于等于孩子 二、堆的实现
2.1堆的创建 堆的逻辑结构是树形结构是我们想象出来的实际上我们操作的数组所以堆的创建和顺序表的结构相同。 typedef int HPDateType;
typedef struct Heap
{HPDateType* a;int size;int capacity;
}HP; 2.2堆的初始化 我们有两种初始化的方式一种是在初始化阶段不开辟空间在插入过程中进行扩容另一种是在初始化阶段就开辟空间。 void HeapInit(HP* php)
{assert(php);php-a NULL;php-size 0;php-capacity 0;
} void HeapInit(HP* php)
{assert(php); php-size 0;php-capacity 5;php-a (HPDateType*)malloc(sizeof(HPDateType) * capacity);if (tmp NULL){perror(malloc);exit(-1);}
} 2.3堆的插入 堆是使用顺序结构的数组来存储的我们使用尾插插入数据更方便然后将数据调整到合适的位置。 void HeapPush(HP* php, HPDataType x)
{assert(php);// 扩容if (php-size php-capacity){int newCapacity php-capacity 0 ? 4 : php-capacity * 2;HPDataType* tmp (HPDataType*)realloc(php-a, sizeof(HPDataType) * newCapacity);if (tmp NULL){perror(realloc fail);exit(-1);}php-a tmp;php-capacity newCapacity;}php-a[php-size] x;php-size;AdjustUp(php-a, php-size - 1);
} 如图在小堆中插入5050比它的父亲小所以要交换两数的位置。我们知道孩子的下标通过 parent(child-1)/2 就可以得到父亲的下标然后交换两数。 2.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){if (a[child] a[parent]){Swap(a[child], a[parent]);child parent;parent (parent - 1) / 2;}else{break;}}
} 2.5堆的删除 我们使用挪动覆盖的方法删除根会使关系混乱剩下的值不一定是堆而且效率很低。这里提供一种更好的方法将根和最后一个值交换然后删除最后调整数据。 void HeapPop(HP* php)
{assert(php);assert(php-size 0);Swap(php-a[0], php-a[php-size - 1]);--php-size;AdjustDown(php-a, php-size, 0);
} 这里要注意有数据的时候才能删除所以要加入 assert(php-size 0) 进行判断。 2.6向下调整数据 如果是小堆存储我们要找到左右孩子中较小的数然后与父亲交换再找到下一层重复步骤直到找到叶节点结束。 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;}}
} 2.7堆的销毁 我们使用动态开辟内存要及时释放空间并置为空指针不然会造成数据泄露。 void HeapDestroy(HP* php)
{assert(php);free(php-a);php-a NULL;php-size php-capacity 0;
} 本次的内容到这里就结束啦。希望大家阅读完可以有所收获同时也感谢各位读者三连支持。文章有问题可以在评论区留言博主一定认真认真修改以后写出更好的文章。你们的支持就是博主最大的动力。
