今天介绍一种我刚刚学到的新的数据结构.二叉树 详情如下:
二叉树的概念:二叉树是一种有限节点的集合,也就是说它的节点个数是有限的. 二叉树的分类:二叉树分为 完全二叉树和满二叉树 二叉树的存储结构:顺序存储结构和链式存储结构
这次主要介绍二叉树的顺序存储结构 ,顺序存储结构主要介绍完全二叉树,完全二叉树是按照一维数组的形式进行存储的,因此是非常适合顺序存储这种存储方式的.而堆是完全二叉树的一个具体的应用. 堆又分为:大堆和小堆. 大堆指的是任意双亲节点都大于其左右节点,因此大堆是降序的顺序 堆顶元素最大 小堆指的是任意双亲节点都小于其左右节点,因此小堆是升序的顺序 堆顶元素最小 堆的具体实现代码如下: 首先第一部分我们来新建一个源文件,“heap.h”,在这里我们定义一下堆的结构,以及关于堆的一系列操作函数 代码如下
#pragma once typedef int HPDataType; typedef struct Heap{ HPDataType *_array;//指向一段连续的空间 int _capacity; int _size; } Heap; void InitHeap(Heap*hp,HPDataType*array, int size); void InsertHeap(Heap*hp, HPDataType data); void EraseHeap(Heap*hp); int HeapSize(Heap*hp); int HeapEmpty(Heap*hp); HPDataType HeapTop(Heap*hp); void DestoryHeap(Heap*hp); void TestHeap(); void HeapSort(int *array, int size);第二部分新建一个头文件:"heap,c"这部分我们来具体实现一下堆的函数操作细节 代码如下
if (hp->_size == hp->_capacity){ int newcapacity = hp->_capacity * 2; HPDataType*pTmp = (HPDataType*)malloc(sizeof(HPDataType)*newcapacity); if (NULL == pTmp){ assert(0); return; } //拷贝元素 for (int i = 0; i < hp->_size; ++i){ pTmp[i] = hp->_array[i]; } //释放原空间 free(hp->_array); //更新参数 hp->_array = pTmp; hp->_capacity = newcapacity; } } //初始化堆 void InitHeap(Heap*hp, HPDataType*array, int size){ assert(hp); //开辟空间 hp->_array = (HPDataType*)malloc(sizeof(HPDataType)*size); if (hp->_array == NULL){ assert(0); return; } hp->_capacity = size; //将数组中的元素搬移到堆中 for (int i = 0; i < size; ++i){ hp->_array[i] = array[i]; } hp->_size = size; // 将该完全二叉树调整使其满足堆的性质 //找完全二叉树中的倒数第一个非叶子节点 int root = ((size - 2) >> 1); for (; root >= 0; --root){ AdjustDown(hp->_array, size, root); } } //向堆中插入元素 void InsertHeap(Heap*hp, HPDataType data){ //先判断是否需要扩容 CheckCapacity(hp); //将元素放入堆中 hp->_array[hp->_size] = data; hp->_size++; //放入之后有可能破坏堆的性质,如果 破坏了则需要调整 AdjustDown(hp->_array, hp->_size, hp->_size - 1); } //删除堆中元素 void EraseHeap(Heap*hp){ if (HeapEmpty(hp)){ return; } //先交换 再删除 再调整 swap(&hp->_array[0], &hp->_array[hp->_size-1]); hp->_size--; AdjustDown(hp->_array, hp->_size, 0); } //获取堆中元素个数 int HeapSize(Heap*hp){ assert(hp); return hp->_size; } //检查堆是否为空 int HeapEmpty(Heap*hp){ assert(hp); return 0 == hp->_size; } //获取堆顶元素 HPDataType HeapTop(Heap*hp){ assert(hp); return hp->_array[0]; } //摧毁堆 void DestoryHeap(Heap*hp){ assert(hp); if (hp->_array){ free(hp->_array); hp->_capacity = 0; hp->_size = 0; } } //测试堆的相关操作函数 void TestHeap(){ Heap hp;//定义一个堆 int array[] = { 2, 3, 8, 0, 9, 1, 7, 4, 6, 5 }; InitHeap(&hp, array, sizeof(array) / sizeof(array[0])); printf("%d ", HeapSize(&hp)); printf("%d ", HeapTop(&hp)); EraseHeap(&hp); printf("%d ", HeapTop(&hp)); InsertHeap(&hp, 0); printf("%d ", HeapTop(&hp)); DestoryHeap(&hp); } //调整数组中元素使其成为堆 void HeapAdjust(int *array, int size, int parent){ int child = parent * 2 + 1; while (child < size){ //找到左右孩子中较大的孩子 if (child + 1 < size && array[child + 1] > array[child]){ child += 1; } //找到了较大的孩子,然后与双亲比较, if (array[child]>array[parent]){ swap(&array[child], &array[parent]); parent = child; child = parent * 2 + 1; } else { return; } } } //利用删除堆中元素的思想,对 堆进行排序 void HeapSort(int *array, int size){ //:建堆-----大堆 // 找到倒数第一个非叶子节点 int root = ((size - 2) >> 1) ; for (; root >= 0 ;--root){ HeapAdjust(array, size, root); } //2.排序:用堆删除的思想 int end = size - 1; while (end){ swap(&array[0],&array[end]); HeapAdjust(array, end, 0); end--; } } //测试堆的排序情况 void testheap(){ int array[] = { 2, 3, 8, 0, 9, 1, 7, 4, 6, 5 }; HeapSort( array, sizeof(array) / sizeof(array[0])); }第三部分,创建一个头文件:“test.c” 在此定义函数的入口main函数 代码如下:
#include"heap.h" #include<stdio.h> #include<stdlib.h> int main(){ //TestHeap(); testheap(); system("pause"); return 0; }.
