树的储存形势&代码实现(跑路人笔记2)

2022-06-22 97

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 树的储存形势&代码实现(跑路人笔记)

main.c

#define _CRT_SECURE_NO_WARNINGS 1
#include"Heap.h"
//堆的测试
void HeapTest()
{
  Heap hp = {0};
  HeapCreat(&hp);
  HeapPush(&hp, 10);
  HeapPush(&hp, 18);
  HeapPush(&hp, 19);
  HeapPush(&hp, 25);
  HeapPush(&hp, 28);
  HeapPush(&hp, 43);
  HeapPush(&hp, 65);
  HeapPush(&hp, 49);
  HeapPush(&hp, 27);
  HeapPush(&hp, 37);
  HeapPop(&hp);
  HeapPrint(&hp);
  HeapDestory(&hp);
}
//堆排序
void HeapSort(int* a, int size)
{
  Heap hp;
  HeapCreat(&hp);
  for (int i = 0; i < size; ++i)
  {
    HeapPush(&hp, a[i]);
  }
  size_t j = 0;
  while (!HeapEmpty(&hp))
  {
    a[j] = HeapTop(&hp);
    j++;
    HeapPop(&hp);
  }
  HeapDestory(&hp);
}
int main()
{
  //TestHeap();
  int a[] = { 4, 2, 7, 8, 5, 1, 0, 6 };
  HeapSort(a, sizeof(a) / sizeof(int));
  for (int i = 0; i < sizeof(a) / sizeof(int); ++i)
  {
    printf("%d ", a[i]);
  }
  printf("\n");
  return 0;
}

咱主要讲Heap.c所需要讲解的部分

主要讲解部分

下方是结构题的内容

typedef struct Heap
{ 
  HPDataType* data;//用于储存数据
  size_t size; //大小
  size_t capacity;//容量
}Heap;

实话实说需要重点讲解的主要是两个函数.

其中

void AdJustUp(Heap* obj)
{
  size_t child = obj->size-1;
  size_t parent = (child - 1) / 2;
  while (child)
  {
    if (obj->data[parent] > obj -> data[child])
    {
      HPDataType tmp = obj->data[child];
      obj->data[child] = obj->data[parent];
      obj->data[parent] = tmp;
      child = parent;
      parent = (child - 1) / 2;
    }
    else
    {
      break;
    }
  }
}

这个函数是嵌套在HeapPush中的一个用于调整数据位置的函数,我们在HeapPush的时候是将数据直接放在我们顺序表的末尾处,然后通过AdJustUp函数对数据进行调整.将本来插入后可能不是堆情况调整成堆的格式.

我们通过图来了解这种情况: 比如我们的数值原来有着: 2 3 5 6 7 8

这时我们插入一个1来看看我们的AdJustUp函数是如何将顺序表的储存情况重新换成堆形势.

其实很简单我们通过while循环和if语句来判断末尾部的父亲是否大于我们要改变位置的节点如果大于就交换他们的位置如果小于就直接进行break语句跳出循环即可.

然后使我们的向下调整函数.

void AdJustDown(Heap* obj)
{
  size_t father = 0;
  size_t child = father*2+1;//得到的是左孩子
  while (child < obj->size)
  {
    //选出最小的孩子
    if (child+1<obj->size&&obj->data[child] > obj->data[child + 1])
    {
      child++;
    }
    if (obj->data[child] < obj->data[father])
    {
      HPDataType tmp = obj->data[child];
      obj->data[child] = obj->data[father];
      obj->data[father] = tmp;
      father = child;
      child = father * 2 + 1;
    }
    else
    {
      break;
    }
  }
}
void HeapPop(Heap* obj)
{
  assert(obj);
  assert(obj->size > 0);
  obj->data[0] = obj->data[obj->size - 1];
  obj->size--;
  AdJustDown(obj);
}