一级a做爰片免费网站体验,网站备案百度站长提交,wordpress文章数据库位置,网络系统分类上次介绍了树#xff0c;二叉树的基本概念结构及性质#xff1a;二叉树数据结构#xff1a;深入了解二叉树的概念、特性与结构
今天带来的是#xff1a;二叉树顺序结构与堆的概念及性质#xff0c;还会用c语言来实现堆 文章目录 1. 二叉树的顺序结构2.堆的概念和结构3.堆…上次介绍了树二叉树的基本概念结构及性质二叉树数据结构深入了解二叉树的概念、特性与结构
今天带来的是二叉树顺序结构与堆的概念及性质还会用c语言来实现堆 文章目录 1. 二叉树的顺序结构2.堆的概念和结构3.堆的实现(小堆)3.1项目文件规划3.2结构体和各功能一览Heap.h3.3重要函数详解Heap.c3.3.1堆向上调整算法3.3.2堆向下调整算法 3.4各功能实现Heap.c初始化和销毁插入删除堆顶返回根堆顶的存储的数据节点数量是否为空 3.5建堆时间复杂度 1. 二叉树的顺序结构 普通的二叉树是不适合用数组来存储的因为可能会存在大量的空间浪费。完全二叉树就比较适合使用顺序结构存储数组。现实中我们通常把堆(一种二叉树)使用顺序结构的数组来存储 注意此堆非“彼堆”——操作系统虚拟进程地址空间中的堆。二者一个是一个是数据结构一个是操作系统中管理内存的一块区域 2.堆的概念和结构 堆需要满足两点 堆是一个完全二叉树即除了最底层其他层都是完全填满最底层从左到右填充堆中的每个节点的值都必须大于等于最大堆或小于等于最小堆其子节点的值 根据节点值的大小关系堆可以分为最大堆和最小堆。在最大堆中根节点的值最大每个节点的值都大于等于其子节点的值。在最小堆中根节点的值最小每个节点的值都小于等于其子节点的值 3.堆的实现(小堆)
3.1项目文件规划 头文件Heap.h:用来基础准备常量定义typedef链表表的基本框架函数的声明源文件Heap.c:用来各种功能函数的具体实现源文件test.c:用来测试功能是否有问题进行基本功能的使用 3.2结构体和各功能一览Heap.h
typedef int HPDataType;typedef struct Heap//用顺序表来实现跟顺序表的结构一样
{HPDataType* a;int size;//数量int capacity;//容量
}HP;void HeapInit(HP* php);//初始化
void HeapDestroy(HP* php);//销毁void HeapPush(HP* php, HPDataType x);//插入
// 规定删除堆顶根节点
void HeapPop(HP* php);//删除HPDataType HeapTop(HP* php);//返回根堆顶的存储的数据int HeapSize(HP* php);//堆的数据个数bool HeapEmpty(HP* php);//是否为空3.3重要函数详解Heap.c
3.3.1堆向上调整算法
i位置节点的双亲序号(i-1)/2
void Swap(HPDataType* p1, HPDataType* p2)
{HPDataType tmp *p1;*p1 *p2;*p2 tmp;
}void AdjustUp(HPDataType* a, int child)//传入数组和下标索引
{int father (child - 1) / 2;//利用公式来算出父亲节点下标while (child 0){if (a[child] a[father]){Swap(a[child], a[father]);//更新下标child father;father (father - 1) / 2;}else{break;//一旦符合小堆了就直接退出}}
}Swap 函数用于交换两个指针指向的值而 AdjustUp 函数用于通过比较子节点与父节点并在有必要时交换它们来调整堆的结构然后向上移动树直到满足堆的性质 3.3.2堆向下调整算法
i位置的左孩子是 2 ∗ i 1 2*i1 2∗i1右孩子 2 ∗ i 2 2*i2 2∗i2
void AdjustDown(HPDataType* a, int n, int father)
{int child father * 2 1;//假设左孩子小 找出两者较小的来跟父节点比大堆就找二者中较大的了while (child n){if (child 1 n a[child] a[child 1]){child;}if (a[child] a[father]){Swap(a[child], a[father]);father child;child father * 2 1;}else{break;}}
}给定一个数组 a表示堆的结构以及数组的大小 n 和要进行调整的父节点的索引 father计算父节点的左孩子的索引为 father * 2 1进入一个 while 循环只要左孩子的索引小于 n (不会出数组)就会继续在循环内部首先检查右孩子是否存在且右孩子的值是否大于左孩子的值如果是则更新 child 为右孩子的索引。这是为了找出左右孩子中值较大的那个比较左孩子的值和父节点的值如果左孩子的值小于父节点的值则调用 Swap 函数交换这两个索引处的值并更新 father 为 child 的值然后重新计算 child 的索引。这一步的目的是将较大的子节点值向上移动以满足堆的性质如果左孩子的值不小于父节点的值则跳出循环因为堆的性质已经满足 3.4各功能实现Heap.c
初始化和销毁
void HeapInit(HP* php)
{assert(php);php-a NULL;php-size php-capacity 0;
}void HeapDestroy(HP* php)
{assert(php);free(php-a);php-a NULL;php-size php-capacity 0;
}插入
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, newCapacity * sizeof(HPDataType));if (tmp NULL){perror(realloc fail);return -1;}php-a tmp;php-capacity newCapacity;}//开始插入php-a[php-size] x;php-size;//要确保是小堆AdjustUp(php-a, php-size - 1);
}删除堆顶
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);
}返回根堆顶的存储的数据
HPDataType HeapTop(HP* php)
{assert(php);assert(php-size 0);return php-a[0];
}节点数量
int HeapSize(HP* php)
{assert(php);return php-size;
}是否为空
bool HeapEmpty(HP* php)
{assert(php);return php-size 0;
}3.5建堆时间复杂度 建堆的时间复杂度为O(N) 这次就到这里啦下一次就利用这次的对来解决几个问题。感谢大家的支持
