宁夏交通厅建设局网站,织梦怎么做的网站,线上分销的三种模式,17.zwd一起做网站目录
一.堆的概念及结构
二.接口实现
A.初始化 Heapinit 销毁 Heapdestroy
B.插入 Heappush 向上调整 AdjustUp
1.Heappush
2.AdjustUp
C.删除 Heappop 向下调整 AdjustDown
D.堆的判空 Heapempty 堆顶数据 Heaptop 堆的大小 Heapsize
三.源码
Heap.h
He… 目录
一.堆的概念及结构
二.接口实现
A.初始化 Heapinit 销毁 Heapdestroy
B.插入 Heappush 向上调整 AdjustUp
1.Heappush
2.AdjustUp
C.删除 Heappop 向下调整 AdjustDown
D.堆的判空 Heapempty 堆顶数据 Heaptop 堆的大小 Heapsize
三.源码
Heap.h
Heap.c
test.c 一.堆的概念及结构 1.概念 如果有一个关键码的集合K { … }把它的所有元素按完全二叉树的顺序存储方式存储在一个一维数组中并满足 且 ( 且 ) i 012…则称为小堆(或大堆)。将根节点最大的堆叫做最大堆或大根堆根节点最小的堆叫做最小堆或小根堆。 2.堆的性质 A.堆中某个节点的值总是不大于或不小于其父节点的值 B.堆总是一棵完全二叉树。 其实堆是一种二叉树通常我们都是用数据表实现也就是说堆的底层是数组数组中的小标表示二叉树的节点所以在实现堆之前我们有必要了解完全二叉树中节点之间的关系。 1.理解父节点 parent 和子节点 child 2.了解父节点与子节点之间的关系 A.parentchild-1/2 B.左孩子child2*parent1 C.右孩子child2*parent2。 二.接口实现
A.初始化 Heapinit 销毁 Heapdestroy 这里的初始化和销毁都很简单相信这对学到堆的人并不是什么难事和顺序表的操作是一样的如果实在不理解的话请看 - 顺序表 B.插入 Heappush 向上调整 AdjustUp
1.Heappush 插入数据很简单直接对数组赋值然后 size 再加加就行了但是在插入完数据后我们得保证它是堆所以这就需要用到向上调整这个函数。 2.AdjustUp 假设我们建的是大堆我们将新插入的节点与它的父节点比较 1.如果比它的父节点大则与其交换所以交换后的父节点就成为了子节点再与其父节点比较以此类推 2.如果child0 则结束循环。 void Swap(HPdatatype* p1, HPdatatype* p2) //交换函数
{HPdatatype tmp *p1;*p1 *p2;*p2 tmp;
}void AdjustUp(HPdatatype* arr, int child) //向上调整
{assert(arr);int parent (child - 1) / 2;while (child 0){if (arr[child] arr[parent]){Swap(arr[child], arr[parent]);child parent;parent (child - 1) / 2;}elsebreak;}
}void Heappush(Heap* php, HPdatatype x)
{assert(php);if (php-size php-capacity){HPdatatype* tmp (HPdatatype*)realloc(php-arr, 2 * sizeof(HPdatatype) * php-capacity);if (tmp NULL){perror(realloc fail);exit(-1);}php-arr tmp;php-capacity * 2;}php-arr[php-size] x;php-size;AdjustUp(php-arr, php-size - 1); //注意这里要传size-1因为size表示的是下一个位置
}
C.删除 Heappop 向下调整 AdjustDown 1.删除的话我们是要删除堆顶的数据因为删除堆尾的数据并没有什么实际意义删除就是让size--但是堆顶数据的下标是0所以在删除前应先交换堆顶和堆尾的数据 2.删除完后还要保持它还是个堆不能把后面的顺序搞乱了要想达到这个目的就需要使用到向下调整这个函数 3.假设是大堆向下调整是父节点与其较大的子节点比较如果较大的那个子节点大于父节点则二者交换然后较大的子节点成为了新的父节点当子节点的下标大于或是等于节点总数也就是size时就结束循环。 D.堆的判空 Heapempty 堆顶数据 Heaptop 堆的大小 Heapsize 这些接口的实现都非常简单博主就不在这里讲述了可以参考后面的源码。 三.源码
Heap.h
#include stdio.h
#include stdlib.h
#include assert.h
#include stdbool.h
#include time.h#define MAX_MIN //通过改变这里的符号可以决定是建大堆还是小堆typedef int HPdatatype;typedef struct Heap
{HPdatatype* arr;int size;int capacity;
}Heap;void Heapinit(Heap* php);void Swap(HPdatatype* p1, HPdatatype* p2);void AdjustUp(HPdatatype* arr, int child); //向上调整void Heappush(Heap* php, HPdatatype x);void AdjustDown(HPdatatype* arr, int parent, int n); //向下调整void Heappop(Heap* php);HPdatatype Heaptop(Heap* php);int Heapsize(Heap* php);bool Heapempty(Heap* php);void Heapdestroy(Heap* php);Heap.c
#include Heap.hvoid Heapinit(Heap* php)
{assert(php);php-arr (HPdatatype*)malloc(sizeof(HPdatatype) * 4);if (php-arr NULL){perror(malloc fail);exit(-1);}php-size 0;php-capacity 4;
}void Swap(HPdatatype* p1, HPdatatype* p2)
{HPdatatype tmp *p1;*p1 *p2;*p2 tmp;
}///Сvoid AdjustUp(HPdatatype* arr, int child)
{assert(arr);int parent (child - 1) / 2;while (child 0){if (arr[child] MAX_MIN arr[parent]){Swap(arr[child], arr[parent]);child parent;parent (child - 1) / 2;}elsebreak;}
}void Heappush(Heap* php, HPdatatype x)
{assert(php);if (php-size php-capacity) //插入前判断数组是否已满{HPdatatype* tmp (HPdatatype*)realloc(php-arr, 2 * sizeof(HPdatatype) * php-capacity);if (tmp NULL){perror(realloc fail);exit(-1);}php-arr tmp;php-capacity * 2;}php-arr[php-size] x;php-size;AdjustUp(php-arr, php-size - 1); //这里要传size-1
}void AdjustDown(HPdatatype* arr, int parent, int n)
{assert(arr);int child 2 * parent 1;while (child n){//判断较大较小的子节点if ((child 1) n arr[child 1] MAX_MIN arr[child]) {child;}if (arr[child] MAX_MIN arr[parent]){Swap(arr[child], arr[parent]);parent child;child 2 * parent 1;}elsebreak;}
}void Heappop(Heap* php)
{assert(php);assert(php-size);Swap(php-arr[0], php-arr[php-size - 1]);php-size--;AdjustDown(php-arr, 0, php-size);
}HPdatatype Heaptop(Heap* php)
{assert(php);assert(php-size); //为空时不能取数据return php-arr[0];
}int Heapsize(Heap* php)
{assert(php);return php-size;
}bool Heapempty(Heap* php)
{assert(php);return php-size 0; //size0即为空
}void Heapdestroy(Heap* php)
{assert(php);free(php-arr);php-arr NULL;php-size 0;php-capacity 0;
}
test.c
#include Heap.hvoid testHeap()
{Heap hp;Heapinit(hp);int i 0, n 10;int x 0;while (n){x rand() % 100 1;Heappush(hp, x);n--;}while (!Heapempty(hp)){printf(%d , Heaptop(hp));Heappop(hp);}printf(\n);Heapdestroy(hp);
}int main()
{srand((unsigned int)time(NULL));testHeap();return 0;
} 这循环队列的讲解就到这里了若有错误或是建议欢迎小伙伴们指出。 希望小伙伴们可以多多支持博主哦。 谢谢你的阅读。
