关于com的网站,如何把网站做成软件,中国制造网外贸平台app,免费下载百度app最新版本专栏引入 哈喽大家好#xff0c;我是野生的编程萌新#xff0c;首先感谢大家的观看。数据结构的学习者大多有这样的想法#xff1a;数据结构很重要#xff0c;一定要学好#xff0c;但数据结构比较抽象#xff0c;有些算法理解起来很困难#xff0c;学的很累。我想让大家…专栏引入 哈喽大家好我是野生的编程萌新首先感谢大家的观看。数据结构的学习者大多有这样的想法数据结构很重要一定要学好但数据结构比较抽象有些算法理解起来很困难学的很累。我想让大家知道的是数据结构非常有趣很多算法是智慧的结晶我希望大家在学习数据结构的过程是一种愉悦的心情感受。因此我开创了《数据结构》专栏在这里我将把数据结构内容以有趣易懂的方式展现给大家。 1.二叉树的顺序存储结构
之前我们谈过了树的存储结构并且谈到了顺序存储结构对树这种一对多的关系结构实现起来还是比较困难的。但二叉树是一种特殊的树由于二叉树的特殊性使得它可以使用顺序存储结构来实现二叉树的顺序存储结构就是使用一维数组存储二叉树中的节点并且节点的存储位置也就是数组的下标要能体现出来节点之间的逻辑关系比如双亲和孩子的关系、左孩子右兄弟的关系等。先来看看完全二叉树的顺序存储就用下面这棵二叉树为例 将这棵二叉树存入数组中相应的下标对应其同样的位置很多数据结构相关书籍上下标都是将0空置从1开始存储其实下标0的位置是否存放数据对堆的实现的难度没有影响为了节省空间我对下标为0的位置进行了存储如下图 这下我们可以看出来完全二叉树的优越性了吧由于它严格的定义所以用顺序结构也可以表现出二叉树的结构来当然对于一般的二叉树尽管层序编号不能反映出来逻辑关系但是可以将其按完全二叉树来编号只不过把不存在的节点设置为NULL而已就像下面的图中虚线部分表示不存在 我们再考虑一种极端的情况一颗深度为h的右斜树。它只有h个节点却要分配个存储单元空间这显然是对存储空间的浪费如下图所示 所以二叉树的顺序存储结构一般只适用于完全二叉树。上一篇中我们提到了堆是一个特殊的完全二叉树所以这篇我们就以堆为例子来实现二叉树的顺序存储。
2.堆
2.1堆的概念
堆是具有下列性质的完全二叉树每个结点的值都大于或等于其左右孩子节点的值称为大顶堆或者每个结点的值都小于等于其左右孩子结点的值称为小顶堆。如下图所示 从堆的定义可以知道根节点一定是堆中所有结点的最大小值 。在上一篇堆二叉树的性质介绍时有一个性质还没和大家介绍因为这个性质就仿佛是为堆量身定制的所以我计划在介绍堆时再介绍它
如果一棵有n个节点的完全二叉树其深度为的节点按层序编号从第一层到第层每层从左到右对任一节点i1≤i≤n有
如果i1则节点i是二叉树的根无双亲如果i1,则双亲是节点。如果2in则节点i没有左孩子节点i为叶子节点否则其左孩子是节点2i。如果2i1n则节点i没有右孩子否则其右孩子是节点2i1。
在这个性质第二、三条也就是说明下标i与2i和2i1的双亲子女的关系双亲结点子节点-1/2。
2.2堆的实现
我们先来定义一下堆的结构
typedef int HPDataType;
typedef struct Heap
{HPDataType* a;int size;int capacity;
}HP;
2.2.1堆的创建和销毁
堆的创建我们使用顺序存储来实现所以它的创建和销毁的实现代码和顺序表的实现的相同。首先是堆的创建函数
void HeapInit(HP* php)
{assert(php);php-a NULL;php-size 0;php-capacity 0;
}
接着是堆的销毁函数
void HeapDestroy(HP* php)
{assert(php);free(php-a);php-a NULL;php-size php-capacity 0;
}
2.2.2堆的向上调整
一说到调整我们肯定会对两个数据进行交换我们先来写一个交换函数
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 (){if (a[child] a[parent]){Swap(a[child], a[parent]);child parent;parent (child - 1) / 2;}else{break;}}
}
既然我们要用循环来实现那么使用while()语句的循环条件是什么呢最坏的情况就是将新插入的节点经过调整变成根节点那条件是parent≥0吗parent是不会小于0的当parent0时插入的数据还要接着向上调整交换此时child变为0parent(0-1)/2我们计算出来的parent时-0.5但是要取整所以parent还是0此时循环还是没结束会再次进入循环此时childparent经过判断语句会侥幸跳出循环这样是不严谨的。我们将循环条件设为child大于0就可以完美解决这个问题。此时这个向上调整的操作完整代码为
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 (child - 1) / 2;}else{break;}}
}
2.3堆的插入 堆的插入操作和顺序表的插入操作相似其具体步骤为
首先函数开始时先进行一些边界判断确保堆的指针有效。如果堆的当前元素数量等于堆的容量即堆已满需要进行动态扩容。这里使用realloc函数对堆的数组进行扩容新的容量为原来容量的两倍。将待插入的元素x放到堆数组的最后一个位置并将堆的元素数量递增。调用AdjustUp函数对刚插入的元素进行向上调整保持堆的性质。
我们来实现一下这个操作
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);exit(-1);}php-a tmp;php-capacity newCapacity;}php-a[php-size] x;php-size;AdjustUp(php-a, php-size - 1);
}
2.4堆的向下调整
堆的向上调整是为了让堆在插入数据时能够保持堆的性质而堆的向下调整操作是在删除根节点后为了维护堆的性质而进行的操作。该操作的目的是将新的根节点下沉到合适的位置使得根节点的值不大于它的左右子节点的值。堆的向下调整具体步骤为
初始化子节点的索引child设为父节点的左孩子节点的索引即parent*21。进入一个循环判断当前节点是否有左孩子节点如果有则执行循环体。在循环体内先假设左孩子节点的值最小将child设为左孩子节点的索引。检查右孩子节点是否存在即child1size如果存在且右孩子节点的值小于左孩子节点的值则将child更新为右孩子节点的索引。检查当前节点的值是否大于最小的子节点的值如果是则交换当前节点和最小子节点的值将当前节点的索引设为子节点的索引child并更新子节点的索引为新的左孩子节点的索引childparent*21。如果当前节点的值不大于最小子节点的值即a[child]a[parent]则跳出循环。重复之前的步骤直到当前节点没有左孩子节点为止。
我们来具体实现一下这个操作
void AdjustDown(int* a, int size, int parent)
{int child parent * 2 1;while (child size){// 假设左孩子小如果解设错了更新一下if (child1 size 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.5堆的删除
堆的删除具体操作步骤为
调用Swap函数来交换小堆根节点php-a[0]和最后一个节点php-a[php-size - 1]的值。这样就将要删除的根节点移到了最后一个位置。将小堆的大小减1即php-size--表示删除了一个节点。最后调用AdjustDown函数来对小堆进行向下调整以维护小堆的性质。这样就完成了小堆的删除操作。
我们来实现一下这个操作
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);
}
