tree.c
`#define _CRT_SECURE_NO_WARNINGS 1 #include<stdio.h> //如何表示一个树呢（代码实现如何定义结构） //法1.假设说明了树的度是N（最大是这么多） struct treenode { int data; struct treenode*subs[N];//这个数组是一个指针数组，里面存的都是指针，但是有缺陷，问题在于 //1.可能会存在不少空间的浪费，如假设只有一个树的度是8，其余的都是0，1，2……浪费了很多空间 //万一没有给我们树的度为多少呢， }; //法2； //假设我们已经定义了一个顺序表seqlist出来了，数据类型是 //typedef struct treenode* seqdata //这个顺序表里面存的是节点的指针 //struct treenode //{ // int data; // seqlist s;// //}; //法3.结构数组村粗 //struct treenode //{ // int parenti; // int data; // //}; //上面的方式各有优缺点，表示树结构的最优方法， 使用左孩子右兄弟表示法 typedef int datatype; struct node { struct node*firstchild;//第一个孩子节点， 永远指向第一个孩子 struct node*pnextbrother;//指向下一个兄弟节点 指向孩子右边的兄弟 datatype data; //节点中的数据域 }; //二叉树 //不学习他的增删查改，没有意义 //而是去控制一下他的结构（高度，深度） //作用是搜索二叉树：用来进行查找，-》平衡搜索二叉树，（avl树和红黑树，b树）（这些结构才会去学习他的增删查改）
heap.h
#define _CRT_SECURE_NO_WARNINGS 1 #pragma once #include<stdio.h> #include<stdlib.h> #include<assert.h> //堆是一个完全二叉树 //我们已经推导了公式，已知父亲，左为父*2+1，右为父*2+2 //已知孩子，父亲为（子-1）/2 typedef int hpdata; typedef struct heap { //物理结构就是一个顺序表 hpdata *a; int size; int capacity; }heap; //初始化 void heapinit(heap* hp); // 销毁 void heapdestroy(heap* hp); //插入 void heappush(heap *hp, hpdata x); //删除 void heappop(heap*hp); void adjustup(hpdata *a, int n, int child); void heapprint(heap*hp); //判空 bool heapempty(heap*hp); int heapsize(heap*hp); // void swap(hpdata*x, hpdata*y); //向下调 void adjustdown(int *a, int size, int parent);
heap.c
#define _CRT_SECURE_NO_WARNINGS 1 #include"heap.h" //初始化 void heapinit(heap* hp) { assert(hp); hp->capacity =hp->size= 0; hp->a = NULL; } // 销毁 void heapdestroy(heap* hp) { assert(hp); free(hp->a); hp->a = NULL; hp->capacity = hp->size = 0; } //向上调整 void adjustup(hpdata *a, int n, int child)//a就是这数组，n就这个数组右多大 { assert(a); int parent = (child - 1) / 2; //while(parent>=0) while (child >0)//调到根 { if (a[child] > a[parent])//大于就交换 { //交换 hpdata tmp = a[child]; a[child] = a[parent]; a[parent] = tmp; child = parent; parent = (child - 1) / 2; } else { break;//小于就停止 } } } //插入 //假设是大堆 void heappush(heap *hp, hpdata x) { assert(hp); //满了就要先增容 if (hp->size == hp->capacity) { size_t newcapcity = hp->capacity == 0 ? 4 : hp->capacity * 2; hpdata *tmp = (hpdata*)realloc(hp->a, sizeof(hpdata)*newcapcity); if (tmp != NULL) { hp->a = tmp; hp->capacity = newcapcity; } else { perror("realloc"); return; } } hp->a[hp->size] = x; hp->size++; adjustup(hp->a, hp->size, hp->size-1); } void heapprint(heap*hp) { int i = 0; for (i = 0; i < hp->size; i++) { printf("%d ", hp->a[i]); } } ```c bool heapempty(heap*hp) { assert(hp); return hp->size == 0;//为0就是空的，不为0就不是空的 } int heapsize(heap*hp) { assert(hp); return hp->size; } //向上调的时间复杂度是 // //向上调高度次 void adjustdown(int *a, int n, int parent) { int child = parent * 2 + 1; while (child < n)//越界就停止了 { if (child + 1 < n&&a[child + 1] > a[child])//右孩子也不越界，右孩子大于左孩子，在这里之后，不用管谁的下标的大，统一放到左孩子 { ++child;//找大的交换 } if (a[child] > a[parent])//孩子大于父亲，就交换 { swap(&a[child], &a[parent]); parent = child; child = parent * 2 + 1; } else { break; } } } //删除 //再堆里面删除不是随便任意删除什么位置都可以 //而是删除堆顶的数据（根），意义是调整堆，找到次小的值（小堆） //向下调整，把他调整成堆，跟左右孩子中小的那个交换 //结束条件 //1.父亲<=小的那个孩子，则停止 //2.调整到叶子（当父亲走到叶子就停止，叶子是没有左孩子，左孩子下标超出数组范围就不存在） void heappop(heap*hp) { assert(hp); assert(!heapempty(hp));//空了就别删除了 //先把堆顶和底部删掉 swap(&hp->a[0], &hp->a[hp->size - 1]); hp->size--;//删掉了 //交换之后，向下调整，保证不破坏堆,从0开始向下调 adjustdown(hp->a, hp->size, 0); }
#define _CRT_SECURE_NO_WARNINGS 1 #include"heap.h" int main() { int a[] = { 70,56,30,25,15,10,75 };//用数组去给hp值 heap HP;//定义一个堆 heapinit(&HP); for (int i = 0; i < sizeof(a) / sizeof(a[0]); i++) { heappush(&HP, a[i]); } heapprint(&HP); return 0; }
堆的应用
1.topk问题
// 在N个数找出最大的前K个 or 在N个数找出最小的前K个 void PrintTopK(int* a, int n, int k) { heap hp; heapinit(&hp); // 创建一个K个数的小堆 for (int i = 0; i < k; ++i) { heappush(&hp, a[i]);//一个一个入堆 } // 剩下的N-K个数跟堆顶的数据比较，比他大，就替换他进堆 for (int i = k; i < n; ++i) { if (a[i] > heaptop(&hp))//比较，大的就入堆 { heappop(&hp);//把顶补的删掉， heappush(&hp, a[i]);//大的入堆 //hp.a[0] = a[i];//把顶部的换成现在大的 //adjustdown(hp.a, hp.size, 0);//向下调整 } } heapprint(&hp); heapdestroy(&hp); } void TestTopk() { int n = 1000000; int* a = (int*)malloc(sizeof(int)*n); srand(time(0)); for (size_t i = 0; i < n; ++i) { a[i] = rand() % 1000000; } // 再去设置10个比100w大的数 a[5] = 1000000 + 1; a[1231] = 1000000 + 2; a[5355] = 1000000 + 3; a[51] = 1000000 + 4; a[15] = 1000000 + 5; a[2335] = 1000000 + 6; a[9999] = 1000000 + 7; a[76] = 1000000 + 8; a[423] = 1000000 + 9; a[3144] = 1000000 + 10; PrintTopK(a, n, 10); } int main() { TestTopk(); return 0; }
2.堆排序
//堆排序 //首先先建堆，再应用堆进行排序 //升序就建大堆，降序就建小堆 void HeapSort(int* a, int n) { //法1. // 直接把a构建成堆，直接控制a数组，升序，吧 //把a构建成小堆 //第一个数先看做堆，后面的数据依次加入堆，然后向上调整，构建堆,调到根就结束了，保证他还是堆 // if (n <= 1)//第一个就看成堆 // { // return; //} //for (int i = 1; i < n; i++)//后面的数加入进去 //{ // AdjustUp(a,i); //} //法2； //向下调整也可以，保证左子树和右子树都小堆，倒着走最后一个子树进行调整 //叶子所在的子树不需要调，所以倒着走的第一个非子节点的子树，就是最后一个节点的父亲，调完之后--，直到根 //前面的调整为后面做了铺垫，前面调整完之后一定是一个堆 for (int i = (n - 1-1) / 2; i >= 0; i--)//最后一个位置是n-1， { AdjustDown(a, n, i); } //排升序建小堆的分析： //1.选出了最小的数放到第一个位置，如何选出次小的位置，只能从第二个位置开始，剩下的数看成一个堆，但是这样的话所有的关系都乱了，只能重新建堆才可以选出次小的堆 //我们建大堆，最大的数选出来， //最大的数放最后一个位置，交换 //如何选出此校的 数，1.把最后一个数不看做堆里面的了，向下调整就可以选出次小的数，依次内推在重复上面过程，，原本有n个数，现在传n-1个数，就不把他当做堆里面的了 for (int end = n - 1; end > 0; end--) { Swap(&a[end], &a[0]); AdjustDown(a, end, 0);//向下调整，到根部 } }
