做外贸营销网站明星百度指数排行

当前位置： 首页 > news >正文

做外贸营销网站,明星百度指数排行,外网访问群晖wordpress,asp.net网站开发全过程目录 一、树概念及结构 二、二叉树树概念及结构 特殊的二叉树 三、堆的概念及结构 四、堆的创建 1、声明结构体 2、初始化
3、销毁 4、添加新元素 5、交换元素
6、向上调整 7、判断堆是否为空 8、移除堆顶元素 9、向下调整 10、获取堆元素个数
五、使用堆排序…目录 一、树概念及结构 二、二叉树树概念及结构 特殊的二叉树 三、堆的概念及结构 四、堆的创建 1、声明结构体 2、初始化  3、销毁 4、添加新元素 5、交换元素  6、向上调整 7、判断堆是否为空 8、移除堆顶元素 9、向下调整 10、获取堆元素个数  五、使用堆排序 排降序建小堆 完整版 Heap.h声明部分 Heap.c函数部分 text.c使用及测试部分 一、树概念及结构 树是一种非线性的数据结构它是由nn0个有限结点组成一个具有层次关系的集合。把它叫做树是因 为它看起来像一棵倒挂的树也就是说它是根朝上而叶朝下的。 有一个特殊的结点称为根结点根节点没有前驱结点。除根节点外其余结点被分成M(M0)个互不相交的集合T1、T2、……、Tm其中每一个集合Ti(1 i m)又是一棵结构与树类似的子树。每棵子树的根结点有且只有一个前驱可以有0个或多个后继。因此树是递归定义的注意树形结构中子树之间不能有交集否则就不是树形结构 节点的度一个节点含有的子树的个数称为该节点的度 如上图A的为6 叶节点或终端节点度为0的节点称为叶节点 如上图B、C、H、I…等节点为叶节点 非终端节点或分支节点度不为0的节点 如上图D、E、F、G…等节点为分支节点 双亲节点或父节点若一个节点含有子节点则这个节点称为其子节点的父节点 如上图A是B的父节点 孩子节点或子节点一个节点含有的子树的根节点称为该节点的子节点 如上图B是A的孩子节点 兄弟节点具有相同父节点的节点互称为兄弟节点 如上图B、C是兄弟节点 树的度一棵树中最大的节点的度称为树的度 如上图树的度为6 节点的层次从根开始定义起根为第1层根的子节点为第2层以此类推 树的高度或深度树中节点的最大层次 如上图树的高度为4 堂兄弟节点双亲在同一层的节点互为堂兄弟如上图H、I互为兄弟节点 节点的祖先从根到该节点所经分支上的所有节点如上图A是所有节点的祖先 子孙以某节点为根的子树中任一节点都称为该节点的子孙。如上图所有节点都是A的子孙 森林由mm0棵互不相交的树的集合称为森林
二、二叉树树概念及结构 二叉树是一个由n(n0)个结点构成的有限集合其中该集合可以为空这时称其为空二叉树或者由一个根结点以及两个互不相交的左子树和右子树组成且左右子树均为二叉树。在二叉树中子树被明确区分为左子树和右子树且它们的顺序不可颠倒。 值得注意的是二叉树的定义具有递归性质因为二叉树本身可以为空根结点可以有空的左子树或空的右子树。这使得二叉树与普通树有明显的区别即使只有一棵子树存在也需要明确指定它是左子树还是右子树。这是二叉树与树最主要的区别之一。请注意二叉树不同于一般的树因为它的子树具有左右之分并且顺序不能颠倒。因此“二叉树是结点度为2的树”的说法是不正确的。 二叉树的基本形态包括以下五种 特殊的二叉树 当涉及到二叉树的特殊类型时有两个主要概念需要了解满二叉树和完全二叉树。 满二叉树满二叉树是一种特殊的二叉树其特点是每个层级的结点数都达到最大值。具体来说如果一个二叉树的深度为K且结点总数为2^K - 1那么它就是一个满二叉树。满二叉树的每一层都包含最大数量的结点使得它具有很特殊的结构。完全二叉树完全二叉树是一种高效的数据结构与满二叉树相关。一个二叉树如果在深度为K的情况下其结点都与深度为K的满二叉树中的编号从1到n的结点一一对应那么它就被称为完全二叉树。需要注意的是满二叉树是完全二叉树的一个特殊情况。 性质 若规定根节点的层数为1则一棵非空二叉树的第i层上最多有个结点。若规定根节点的层数为1则深度为h的二叉树的最大结点数是。对任何一棵二叉树, 如果度为0其叶结点个数为 n0 , 度为2的分支结点个数为 n2 ,则有 n0 n2 1。若规定根节点的层数为1具有n个结点的满二叉树的深度hlog以2为底n1的对数。对于具有n个结点的完全二叉树如果按照从上至下从左至右的数组顺序对所有节点从0开始编号则对于序号为i的结点有 若i0i位置节点的双亲序号(i-1)/2i0i为根节点编号无双亲节点 若2i1n左孩子序号2i12i1n否则无左孩子 若2i2n右孩子序号2i22i2n否则无右孩子 三、堆的概念及结构 堆Heap是一种特殊的树状数据结构通常用于实现优先队列和对数据进行排序。堆的主要特点是它是一棵树其中每个节点的值满足特定的堆属性。在堆中通常有两种主要类型最大堆和最小堆。 最大堆Max Heap在最大堆中每个节点的值都不小于其子节点的值即根节点的值最大。这意味着最大堆的最大元素总是位于根节点而子树中的值递减。 最小堆Min Heap在最小堆中每个节点的值都不大于其子节点的值即根节点的值最小。这意味着最小堆的最小元素总是位于根节点而子树中的值递增。 堆的常见用途包括 优先队列堆可以用来实现高效的优先队列使得可以快速访问和删除具有最高或最低优先级的元素。 堆排序堆排序是一种高效的排序算法它利用堆的性质来进行排序。它的时间复杂度为O(n log n)。 堆通常是以数组的形式来表示其中父节点和子节点之间的关系通过数组索引来建立。具体来说对于一个具有n个元素的堆节点的索引从1到n编号其中 父节点的索引为i则它的左子节点的索引为2i右子节点的索引为2i 1。子节点的索引为i则其父节点的索引为i/2。 这种数组表示方法使得堆的操作更加高效因为它不需要使用额外的指针来表示树的结构。 四、堆的创建 本次以小堆举例进行讲解  1、声明结构体 typedef int HPDataType; typedef struct Heap {HPDataType* a;int size;int capacity; }HP; HPDataType 被定义为 int 类型表示堆中存储的数据类型。创建堆的结构体Heap定义别名为HP。指针a指向堆的数组size为堆的当前大小capacity为堆的容量 2、初始化  void HeapInit(HP* php) {assert(php);php-a NULL;php-size 0;php-capacity 0; } assert 判断指针是否合法。指向数组的指针 a 初始化为 NULL。size 和 capacity 初始化为0。 3、销毁 void HeapDestroy(HP* php) {assert(php);free(php-a);php-a NULL;php-capacity php-size 0; } assert 判断指针是否合法。释放数组空间将 a 指针置空同时将 capacity 和 size 设置为0。 4、添加新元素 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 (tmpNULL) {perror(realloc fail);return;}php-a tmp;php-capacity newCapacity;}php-a[php-size] x;php-size;AdjustUp(php-a, php-size - 1); } assert 判断指针是否合法。判断当前是否需要扩容初始堆的容量为0则为堆开辟四个HPDataType类型大小的空间如果当前堆的大小size等于容量capacity则将堆扩容为两倍原来大小的空间。扩容失败打印错误信息结束函数将扩容的空间赋值给指针a更新容量capacity的大小。将要增加的元素插入数组a中更新size大小。每次在堆中添加新元素时小堆可能会被破坏所以我们再添加新元素后要在AdjustUp函数中判断是否需要进行向上调整。 5、交换元素  后续函数会经常用到同一串代码放到函数里供其使用者调用比较好。  void Swap(HPDataType* p1, HPDataType* p2) {HPDataType tmp *p1;*p1 *p2;p2 tmp; } 6、向上调整 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;}} } 首先通过当前的孩子节点child找到父节点parent。当child大于0时进行判断当前chilid是否需要调整如果child位置元素小于parent位置元素则通过Swap进行交换然后新的孩子节点更新为parent位置通过孩子节点更新新的父节点位置然后继续比较和交换直到不再需要交换为止。如果当前孩子节点不小于当前的父节点则结束循环当前节点不需要向上调整。 7、判断堆是否为空 bool HeapEmpty(HP* php) {assert(php);return php-size 0; } 8、移除堆顶元素 一般来说堆的移除操作通常是移除堆顶元素这样大堆小堆的性质保持不变如果移除堆底会破坏堆的性质。 void HeapPop(HP* php) {assert(php);assert(!HeapEmpty(php));Swap(php-a[0], php-a[php-size - 1]);php-size–;AdjustDown(php-a, php-size, 0); } assert 判断指针是否合法。检查堆是否为空为空则报错。移除堆顶元素有两种方法首选第二种方法不需要重新建堆节约时间。首先交换堆顶堆尾然后size减一完成删除后续不会访问删除位置的元素所以不释放内存空间也可以。然后进行向下调整。 9、向下调整 向下调整是从第一个节点父节点开始向下调整传入参数命名为parent  void AdjustDown(HPDataType* a, int size, int parent) {int child parent * 2 1;while (child size) {if (child 1 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;}} } 通过传入参数获取到当前的左子节点的位置。当child位置小于数组元素个数时进行判断。进入循环首先判断检查右子节点是否存在并且比左子节点的值小如果是将 child 更新为右子节点的索引以确保选择更小的子节点进行比较。比较选定的子节点的值与父节点的值如果子节点的值小于父节点的值就交换它们。更新parent为新的子节点位置更新child为新的左子节点位置然后继续比较和交换直到不再需要交换为止。如果当前子节点不小于当前父节点则停止循环。 10、获取堆元素个数  int HeapSize(HP* php) {assert(php);return php-size; } 五、使用堆排序 void HeapSort(int* a, int n) {HP hp;HeapInit(hp);// 时间复杂度N*logNfor (int i 0; i n; i){HeapPush(hp, a[i]);}// 时间复杂度NlogNint i 0;while (!HeapEmpty(hp)){int top HeapTop(hp);a[i] top;HeapPop(hp);}HeapDestroy(hp); } 可以使用这种方式但有诸多弊端  要先有一个堆,太麻烦。空间复杂度拷贝数据 排降序建小堆 所以我们要在传入的原数组上排降序需要使用建小堆的方式向上调整。 void HeapSort(int a, int n) {// 建堆–向上调整建堆for (int i 1; i n; i){AdjustUp(a, i);}int end n - 1;while (end 0){Swap(a[0], a[end]);// 再调整选出次小的数AdjustDown(a, end, 0);–end;} }从根节点的子节点开始向上建堆除了根节点以外每个节点都进行向上调整。定义堆的最后一个节点end为n-1我们将堆的根节点也就是最小值与堆的最后一个元素交换即将最小值放到排序尾部即为好的部分。接下来通过调用AdjustDown函数将堆的大小减一再次将堆调整为最小堆。重复while循环内部操作直到整个数组排序完成。每次交换和堆的调整都会将最小的元素添加到已排序的部分直到整个数组都有序。 HeapSort的时间复杂度为O(nlog(n))它不需要额外的空间来存储数据所以是一种原地排序算法。它在最坏情况下的性能仍然是O(nlog(n))因此相对稳定适用于大规模数据的排序。  我们也可以向下建堆 倒着调整叶子节点不需要处理从倒树第一个非叶子节点开始即最后一个节点的父节点开始调整。 void HeapSort(int* a, int n) {for (int i (n - 1 - 1) / 2; i 0; –i){ AdjustDown(a, n, i);}int end n - 1;while (end 0){Swap(a[0], a[end]);// 再调整选出次小的数AdjustDown(a, end, 0);–end;} }完整版 Heap.h声明部分 #include stdio.h #include stdlib.h #include assert.h #include stdbool.htypedef int HPDataType; typedef struct Heap {HPDataType* a;int size;int capacity; }HP;void HeapInit(HP* php); void HeapDestroy(HP* php);void AdjustUp(HPDataType* a, int child); void HeapPush(HP* php, HPDataType x); bool HeapEmpty(HP* php); void AdjustDown(int* a, int n, int parent); void HeapPop(HP* php);HPDataType HeapTop(HP* php); int HeapSize(HP* php); Heap.c函数部分 #include Heap.hvoid 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-capacity php-size 0; }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 (child0) {if (a[child] a[parent]) {Swap(a[child], a[parent]);child parent;parent (child - 1) / 2;}else {break;}} }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 (tmpNULL) {perror(realloc fail);return;}php-a tmp;php-capacity newCapacity;}php-a[php-size] x;php-size;AdjustUp(php-a, php-size - 1); }bool HeapEmpty(HP* php) {assert(php);return php-size0; } void AdjustDown(HPDataType* a, int size, int parent) {int child parent * 2 1;while (child size) {if (child 1 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;}} }void HeapPop(HP* php) {assert(php);assert(!HeapEmpty(php));Swap(php-a[0], php-a[php-size - 1]);php-size–;AdjustDown(php-a, php-size, 0); }HPDataType HeapTop(HP* php) {assert(php);assert(!HeapEmpty(php));return php-a[0]; }int HeapSize(HP* php) {assert(php);return php-size; } text.c使用及测试部分 #define _CRT_SECURE_NO_WARNINGS 1 #include Heap.hvoid HeapSort(int* a, int n) {// 建堆–向上调整建堆for (int i 1; i n; i){AdjustUp(a, i);}// 建堆–向下调整建堆//for (int i (n - 1 - 1) / 2; i 0; –i)//{// AdjustDown(a, n, i);//}int end n - 1;while (end 0){Swap(a[0], a[end]);// 再调整选出次小的数AdjustDown(a, end, 0);–end;} }int main() {int a[] { 7,8,3,5,1,9,5,4 };HeapSort(a, sizeof(a) / sizeof(int));for (int i 0; i 8; i) {printf(%d , a[i]);}return 0; }//—测试堆函数功能— //int main() //{ // HP hp; // HeapInit(hp); // int a[] { 65,100,70,32,50,60 }; // for (int i 0; i sizeof(a) / sizeof(int); i) // { // HeapPush(hp, a[i]); // } // // while (!HeapEmpty(hp)) // { // int top HeapTop(hp); // printf(%d\n, top); // HeapPop(hp); // } // // return 0; //}