江门建站模板搭建,网站开发者常见问题,服务网络是什么,四川seo选哪家利用C语言模拟实现堆的基本操作和调堆算法 文章目录 利用C语言模拟实现堆的基本操作和调堆算法前言一、堆的基本原理大根堆和小根堆的比较 二、实现堆的基本操作1#xff09;结构定义2#xff09;初始化堆#xff08;HeapInit#xff09;3#xff09;销毁堆#xff08;He…利用C语言模拟实现堆的基本操作和调堆算法 文章目录 利用C语言模拟实现堆的基本操作和调堆算法前言一、堆的基本原理大根堆和小根堆的比较 二、实现堆的基本操作1结构定义2初始化堆HeapInit3销毁堆HeapDestroy4堆的调整算法1向上调堆算法2向下调堆算法 5堆的插入操作HeapPush6堆的删除操作HeapPop7获取堆顶元素HeapTop8获取堆的大小HeapSize9判断堆是否为空HeapEmpty10打印堆HeapPrint 三、测试堆的功能总结 前言
堆是一种重要而高效的数据结构广泛应用于各种算法和数据处理场景。本篇博客将介绍如何使用C语言模拟实现堆的基本操作包括初始化、插入、删除等并通过回调函数和函数指针的灵活运用实现大根堆和小根堆的不同调堆算法。 一、堆的基本原理
堆是一种特殊的树形数据结构具有以下基本特点 完全二叉树的结构即除了最底层其他层都是满的。堆中的每个节点的值都必须大于等于或小于等于其子节点的值根据此条件分为大根堆和小根堆。 堆常被用来实现优先队列等数据结构其中最值的快速访问是堆的主要优势。
大根堆和小根堆的比较
大根堆和小根堆的不同之处在于调堆算法中的比较条件。在大根堆中父节点的值必须大于子节点的值而在小根堆中父节点的值必须小于子节点的值。通过函数指针我们可以根据用户的选择动态切换调堆算法使代码更加灵活。
二、实现堆的基本操作 声明 此处采用动态数组模拟实现堆完全二叉树 1结构定义
定义了堆的结构包括元素数组、大小、容量和标识是大根堆还是小根堆的字符。
typedef int HPDataType;typedef struct Heap {HPDataType* a;size_t size;size_t capacity;char RootBigOrSmall;
} HP;2初始化堆HeapInit
通过 HeapInit 函数初始化堆结构用户可以选择大根堆‘B’或’b’或小根堆‘S’或’s’。
void HeapInit(HP* php)
{assert(php);printf(请挑选大根堆big - B或小根堆small - S: 【输入首字母大小写】);char choose ;choose getchar();if (choose B || choose S || choose b || choose s) { php-RootBigOrSmall choose; }else { printf(输入有误); return; }php-a NULL;php-capacity php-size 0;
}3销毁堆HeapDestroy
释放堆内存和相关资源的 HeapDestroy 函数。
void HeapDestroy(HP* php)
{assert(php);free(php-a);php-a NULL;php-capacity php-size 0;
}4堆的调整算法
1向上调堆算法
void adjustUpHeap(HPDataType* a, size_t child, bool (*cmp)(HPDataType _parent, HPDataType _child))
{size_t parent (child - 1) / 2;if (child 0) { parent 0; }while (child 0){if (cmp(a[parent], a[child])){HPDataType tmp a[parent];a[parent] a[child];a[child] tmp;}child parent;parent (parent - 1) / 2;}
}2向下调堆算法
void adjustDownHeap(HPDataType* a, HPDataType size, HPDataType parent,bool (*cmp)(HPDataType _parent, HPDataType _child))
{HPDataType child parent * 2 1;while (child size){if (child 1 size cmp(a[child], a[child 1])){child;}if (cmp(a[parent], a[child])){HPDataType tmp a[parent];a[parent] a[child];a[child] tmp;parent child;child child * 2 1;}else { break; }}
}这里采用函数指针作为两种调堆算法的参数是因为通过此方法可实现运行后指定大根堆或小根堆从而影响相关控制堆的操作比如 HeapPush和 HeapPop等操作。
5堆的插入操作HeapPush
通过 HeapPush 函数插入元素并通过向上调堆算法保持堆的性质。
void HeapPush(HP* php, HPDataType x)
{assert(php);// 检查扩容if (php-capacity php-size){size_t new_capacity (php-capacity 0 ? 4 : php-capacity * 2);HPDataType* tmp (HPDataType*)realloc(php-a, new_capacity * sizeof(HPDataType));if (!tmp) { perror(realloc of HeapPush); return; }php-a tmp;php-capacity new_capacity;}php-a[php-size] x;// 调堆bool (*cmp)(HPDataType _parent, HPDataType _child) NULL;if (php-RootBigOrSmall B || php-RootBigOrSmall b){cmp bigRootHeap_cmp;}else{cmp smallRootHeap_cmp;}adjustUpHeap(php-a, php-size - 1, cmp);
}注意 这里使用动态数组存储堆的节点所以需要考虑空间扩容问题当容量不足时利用 realloc() 函数从堆区申请额外空间。
6堆的删除操作HeapPop
通过 HeapPop 函数删除堆顶元素并通过调堆算法保持堆的性质。
void HeapPop(HP* php)
{assert(php);assert(php-a php-size 0);bool (*cmp)(HPDataType _parent, HPDataType _child) NULL;if (php-RootBigOrSmall B || php-RootBigOrSmall b){cmp bigRootHeap_cmp;}else{cmp smallRootHeap_cmp;}// 去顶节点HPDataType tmp php-a[0];php-a[0] php-a[php-size - 1];php-a[php-size - 1] tmp;php-size--;// 调堆adjustDownHeap(php-a, php-size, 0, cmp);
}7获取堆顶元素HeapTop
通过 HeapTop 函数获取堆顶元素。
HPDataType HeapTop(const HP* php)
{assert(php);assert(php-a php-size 0);return php-a[0];
}8获取堆的大小HeapSize
通过 HeapSize 函数获取堆的大小。
size_t HeapSize(const HP* php)
{assert(php);return php-size;
}9判断堆是否为空HeapEmpty
通过 HeapEmpty 函数判断堆是否为空。
bool HeapEmpty(const HP* php)
{assert(php);return php-size 0;
}10打印堆HeapPrint
通过 HeapPrint 函数输出堆的内容。测试时避免代码冗杂
void HeapPrint(const HP* php)
{assert(php);for (int i 0; i php-size; i){std::cout php-a[i] \t;}std::cout \n;
}三、测试堆的功能
测试代码
int main()
{HP hp;HeapInit(hp);HeapPush(hp, 15);HeapPush(hp, 18);HeapPush(hp, 19);HeapPush(hp, 25);HeapPush(hp, 28);HeapPush(hp, 34);HeapPush(hp, 65);HeapPush(hp, 49);HeapPush(hp, 27);HeapPush(hp, 37);HeapPrint(hp);HeapPush(hp, 30);HeapPrint(hp);HeapPop(hp);HeapPrint(hp);HeapDestroy(hp);return 0;
}通过 HeapPrint可以将上面代码分为三部分第一次 HeapPrint时对应数组内元素为 树状图 第二次HeapPrint时
经历了HeapPush功能对应数组内元素为 树状图 第三次HeapPrint时
经历HeapPop功能向下调整算法 所得对应数组内元素为 运行结果 无内存泄漏HeapDestroy符合设计需求。 总结
本文详细介绍了使用C语言模拟实现堆的基本操作和调堆算法。通过回调函数和函数指针实现了大根堆和小根堆的灵活切换。堆是一种强大的数据结构能够在很多应用中提供高效的解决方案。在实际编程中理解和掌握堆的实现原理对于优化算法和提高代码效率至关重要。
