搭一个网站卖设计图的网站

搭一个网站,卖设计图的网站,网络运维工程师有前途吗,最近中文字幕2018免费版2019目录 前言 树 非树 树的相关术语 二叉树 二叉树的分类 计算完全二叉树和满二叉树的高度和结点数 二叉树的存储结构 顺序结构 链式结构 实现顺序结构二叉树 堆的概念与结构 堆的实现 堆的初始化 堆的值交换 获取堆顶元素、堆的数据个数、堆的判空、堆的销毁 *建…目录前言树非树树的相关术语二叉树二叉树的分类计算完全二叉树和满二叉树的高度和结点数二叉树的存储结构顺序结构链式结构实现顺序结构二叉树堆的概念与结构堆的实现堆的初始化堆的值交换获取堆顶元素、堆的数据个数、堆的判空、堆的销毁*建堆向上调整法向上调整建堆代码向上调整法的时间复杂度向下调整法向下调整法建堆向下调整建堆的时间复杂度堆插入堆删除堆排序Top K 问题总结前言在数据结构的知识体系里二叉树是承载递归思维与分层遍历的核心结构而堆作为完全二叉树的典型应用更是将 “优先级筛选” 的能力发挥到了极致。在面试与工程实战中TopK 问题找前 K 大、前 K 高频元素等一直是高频考点暴力排序的思路往往因时间复杂度过高被淘汰而堆结构正是解决这类问题的最优解之一。本文将从二叉树的底层逻辑出发拆解堆的构建与调整过程再结合经典 TopK 例题带你吃透从原理到代码的完整链路。本文中log都是以2为底的log如果标注了的没事看到logn希望大家可以知道什么意思这篇文章主要介绍树二叉树的分类常用的二叉树树不同的二叉树的存储方式每种存储方式带来的优缺点树我们先看一下官方的说法什么是树看不懂没事我来给大家用通俗的话说一遍假设A为爷爷辈B、C、D为爸爸辈E、F、G、H、I为我这辈J、K、L为我孩子这辈-------------------------------------------------------------------------------------------------------------------------那么树的概念就是爷爷辈的结点可以链接爸爸辈的结点爸爸辈结点可以链接我这辈的结点。爷爷辈结点、爸爸辈结点又可以通过我找到我孩子这辈结点但是爷爷辈结点和爸爸辈结点不能直接越过中间结点直接连接我的孩子结点上一辈的可以连接多个下一辈的结点下一辈的结点只能有一个上一辈的结点连接同辈的结点不能互连而且上一辈的结点不能连接同一个下一辈结点就和我们的血缘关系一样我们的直系亲属只能是我们的父母总不能大伯也是我们的直属亲戚叭他只是爸爸的兄弟但是和我们没有直接关系只是通过爸爸产生了间接关系因为他和爸爸是兄弟非树先看非树的结构大家可以对照我刚刚上面说的树的结构来对比一下为什么他是非树结构同辈结点相连同辈结点连接到同一个下一辈结点上一辈的结点只能连接到下一辈的结点不能直接略过下一辈的节点直接连接树的相关术语概念名称定义示例对应题干中的树父结点 / 双亲结点若一个结点含有子结点则这个结点称为其子结点的父结点。A 是 B 的父结点E 是 J 的父结点J 是 Q 的父结点。子结点 / 孩子结点一个结点含有的子树的根结点称为该结点的子结点。B 是 A 的孩子结点J 是 E 的孩子结点Q 是 J 的孩子结点。结点的度一个结点拥有的子结点的数量即有几个孩子度就是多少。A 的度为 6F 的度为 2K 的度为 0E 的度为 1D 的度为 1。树的度一棵树上所有结点中最大的结点度数即为树的度。树的度为 6因 A 结点的度最大为 6。叶子结点 / 终端结点度为 0 的结点没有任何子结点的结点。B、C、H、I、K、L、M、N、O、P、Q 等结点均无子女。分支结点 / 非终端结点度不为 0 的结点至少有一个子结点的结点。A、D、E、F、G、J 等结点均有子女。兄弟结点具有相同父结点的结点互称为兄弟结点亲兄弟。B 和 C 是兄弟结点父结点均为 AK 和 L 是兄弟结点父结点均为 F。结点的层次从根结点开始定义根为第 1 层根的子结点为第 2 层依次递增。A 是第 1 层B、C、D、E、F、G 是第 2 层H、J、K、L、M、N 是第 3 层Q 是第 4 层。树的高度 / 深度树中所有结点的最大层次即最深结点的层次。树的高度为 4最深结点 Q 处于第 4 层。结点的祖先从根结点到该结点所经过分支上的所有结点包括根和父结点。A 是所有结点的祖先A、E、J 是 Q 的祖先A、D 是 H 的祖先。路径从树中任意一个结点出发沿 “父结点→子结点” 的连接到达另一个任意结点的序列路径上的结点不重复。A 到 Q 的路径A→E→J→QH 到 Q 的路径H→D→A→E→J→QF 到 L 的路径F→L。子孙以某结点为根的子树中所有的结点都称为该结点的子孙包括直接子结点和间接子结点。所有结点都是 A 的子孙J、Q 是 E 的子孙K、L 是 F 的子孙。森林由 mm0棵互不相交的树组成的集合多棵独立的树放在一起即为森林。若将题干中的树拆分为 3 棵互不相交的小树如以 B 为根的树、以 C 为根的树、以 D 为根的树这 3 棵树组成的集合就是森林。原先我们说的上一辈结点就是父节点同辈节点就是兄弟结点下一辈结点就是子结点二叉树在树形结构中我们最常⽤的就是⼆叉树⼀棵⼆叉树是结点的⼀个有限集合该集合由⼀个根结点加上两棵别称为左⼦树和右⼦树的⼆叉树组成或者为空。从上图可以看出⼆叉树具备以下特点1. ⼆叉树不存在度⼤于 2 的结点2. ⼆叉树的⼦树有左右之分次序不能颠倒因此⼆叉树是有序树注意对于任意的⼆叉树都是由以下⼏种情况复合⽽成的二叉树的分类树有三种非完全二叉树、完全二叉树、满二叉树三者的关系前者包含后者完全二叉树所有的子结点都是连续的这种结构也是我们二叉树经常用到的逻辑结构因为这种结构用顺序表来存储空间的利用率高非完全二叉树在子结点里你发现第3层的结点里有一个没有子节点但是他右边的兄弟结点却都有子结点所以他是不连续的是非完全二叉树满二叉树这种是二叉树的理想结构除最后一层结点每一个父节点都有俩个孩子计算完全二叉树和满二叉树的高度和结点数满二叉树高度h总结点数N根据满二叉树的特点可以得出公式F(N) 2^0 2^1 2^2 2^3 ... 2^(h-2) 2^(h-1)2F(N) 2^1 2^2 2^3 2^4 ... 2^(h-2) 2^h2F(N)-F(N) F(N)2^h - 1F(h) log (N1)----log以2为底的N1(2)高度公式h log (N1)----log以2为底的N1(2)总结点公式N 2^h - 1第h层的结点数n 2^(h - 1)完全二叉树高度h总结点数N完全二叉树不同于满二叉树它的最后一层结点不是满的但是他的h-1层一定是满的所以我们可以先利用满二叉树的公式取一个值范围N的取值范围2^(h-1) N 2^h - 1我来解释这个公式因为完全二叉树的h层必须最少有1个叶子结点按照这个逻辑来说那么前h-1层的总结点数是不就为2^(h-1) - 1个结点嘛但是这是前h-1层的第h层最少还有1个叶子结点所以加起来不就等于2^(h-1)嘛完全二叉树的最大情况就是满二叉树的情况所以就是2^h - 1h最小高度公式log (N h log (N1)(2) (2)我们取log (N1)(2)二叉树的存储结构二叉树我们一般分为2种存储结构顺序表的连续存储、链表的链式存储顺序结构其实我们之前也讲了完全二叉树的逻辑结构上所有的子结点都是相邻的而这种相邻的结构就非常适合用顺序表数组来存储反观非完全二叉树因为子结点存在不相邻的情况所有在顺表数组中存储就会导致空间的浪费当我们只是把左图的数据从逻辑结构的数存储到物理结构的数组里的时候那么恭喜你解锁了在二叉树的逻辑结构和物理结构之间转换的能力链式结构二叉树的链式存储结构是通过链表来表示二叉树利用指针来体现节点间的逻辑关系。在具体实现中每个链表节点包含三个部分数据域存储节点值左右指针域分别指向该节点的左孩子和右孩子的存储地址。根据指针数量不同链式结构可分为二叉链含左右两个指针和三叉链在今天我们主要使用二叉链结构。这种链式存储就非常的适合存储非完全二叉树很好的解决了父节点左右子树为空的情况更大程度上减少了空间的浪费实现顺序结构二叉树当我们的思维可以把完全二叉树的逻辑结构转化为物理结构的时候那么我就可以想想怎么去实现这个顺序结构的二叉树了实现顺序结构的二叉树必须要知道堆堆的概念与结构这个堆和内存里面的对可不一样内存的堆是物理器件上的一部分而我们说的这个堆是一种存储方式堆分为大堆小堆大堆就是每个父结点都大于自己的子结点小堆就是每个父结点都小于自己的子结点存储的方式大家也可以参考这俩张图里的无论大堆还是小堆都是从根结点开始存储接下来再和大家说一下堆的性质堆的实现先看一下实现堆的整体代码板块typedef int HPDataType; typedef struct Heap { //堆的首元素地址 HPDataType* a; //堆当前存储的元素个数 int size; //堆可存储的最大个数 int capacity; }HP; //堆排序 void HeapSort(int* a, int n); //交换 void Swap(HPDataType* a, HPDataType* b); //堆的初始化 void HeapInit(Heap* php, HPDataType* a, int n); // 堆的销毁 void HeapDestory(Heap* hp); // 堆的插入 void HeapPush(Heap* hp, HPDataType x); // 堆的删除 void HeapPop(Heap* hp); //堆的向上调整 void HeapJustUp(HPDataType* a, int n); //堆的向下调整 void HeapJustDown(HPDataType* a,int n); // 取堆顶的数据 HPDataType HeapTop(Heap* hp); // 堆的数据个数 int HeapSize(Heap* hp); // 堆的判空 int HeapEmpty(Heap* hp);老样子我们还是在VS2022的环境下执行分别创建三个文件Heap.h函数声明、heap.c函数实现、test.c代码测试堆的初始化//参数Heap结构体的地址一个数组地址数组的元素个数 void HeapInit(Heap* php, HPDataType* a,int n) { assert(php); assert(a); php-_a NULL; php-_capacity 0; php-_size 0; //后续会用HeapPush函数直接在初始化这一步就把堆建好 for (int i 0; i n; i) { HeapPush(php, a[i]); } }堆的值交换//交换后续会用到很多的的交换部分所有就单独拿出来 void Swap(HPDataType* a, HPDataType* b) { HPDataType swap *a; *a *b; *b swap; }获取堆顶元素、堆的数据个数、堆的判空、堆的销毁因为这几个比较简单所有我就拿出来放一起了// 取堆顶的数据 HPDataType HeapTop(Heap* hp) { assert(hp); return hp-_a[0]; } // 堆的数据个数 int HeapSize(Heap* hp) { assert(hp); return hp-_size; } // 堆的判空 int HeapEmpty(Heap* hp) { assert(hp); if (hp-_size 0) { return 0; } else { return hp-_size; } } // 堆的销毁 void HeapDestory(Heap* hp) { assert(hp); free(hp-_a); hp-_a NULL; hp-_capacity 0; hp-_size 0; }*建堆首先先介绍一下向上调整法和向下调整法向上调整法从后往前依次比较自己的父结点看谁大谁小符合条件就交换使用前提父结点及以上为堆大堆小堆都可以这就是一个利用向上调整法的插入建堆当数组里面为空时我们插入的第一个元素就是堆因为只有一个元素//向上调整 //参数数组首元素地址、数组元素个数、要插入堆的位置 void HeapJustUp(HPDataType* a, int size, int sub) { int child sub; 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; } } }sub尾元素的下标child就指向了尾元素parent指向了child的父结点child为什么小于等于0就接受呢因为当尾部元素反复与自己的父结点比较交换以后最后如果到达了根结点那么就说明该元素此时是堆里最大的元素了就可以结束循环了如果在到达根节点之前child就小于parent那么就退出循环说明此时child已经达到了可以维持堆性质的位置本来再堆尾拆入一个数就破坏了堆的性质要维护堆的性质就必须让这个新元素来到适合的位置比如在说在根的左右树的任意一边中比新元素小的就变成新元素的子结点大堆小堆父结点大于子结点/父结点小于子结点重点被插入的数组必须得是堆每次对比交换就是向上走的所以你要对比交换的父结点必须是堆子结点可以不是向上调整建堆代码//向上调整:建堆 void HeapUpPileup(HPDataType* a, int size, int sub) { //为什么要放在一个循环里面 //因为你每调用一次HeapUp就只会插入一个元素 for (int i sub; i size; i) { HeapUp(a, size, i); } }我知道可能很多人在看那个向上调整法的时候里面那个sub还能理解到了这里就有点理解不了了没事我画一张图你就理解了向上调整法的时间复杂度分析第1层 2^0 个结点需要向上移动0层第2层 2^1 个结点需要向上移动1层第3层 2^2 个结点需要向上移动2层第4层 2^3 个结点需要向上移动3层......第h层 2^(h−1) 个结点需要向上移动h-1层向下调整法接下来思考一下删除根节点怎么删除这个时候聪明的小牛肯定会说我们刚刚不是学了向上调整法嘛我们重新插入一边就好了确实这个方法确实可行但是既然我们现在学了数据结构那么不是所有可执行可达到目的的代码就是好代码了我们计算一下刚刚说的那种时间的复杂度删除根的元素后面元素往前移n个数据移动n-1次每一移动一次用向上调整建堆而它的时间复杂度是俩者相乘就是O(n^2 log n)是不是一下子感觉这个方法很挫了我直接向后遍历也就O(n^2)所以这个办法是行不通的办法呢还是有的看一张图你就悟了这个流程就是向下调整法每次都要将首尾元素交换然后删除尾部即可重点向下调整算法有⼀个前提左右子树必须是⼀个堆才能调整。将堆顶元素与堆中最后⼀个元素进行交换删除堆中最后⼀个元素将堆顶元素向下调整到满足堆特性为止我主要实现的就是第二张图里的步骤往下对比交换的过程先讲一下思路首尾交换元素这一步可以在外部完成不需要放在HeapDown函数中我们写的函数应该只处理接收到的下标数据然后从接收到的下标数据依次往下比较满足条件就交换比较完就退出还要再处理就在调用该函数其实就是父结点在俩个子结点里对比这个和向上调整相反它是子结点和父结点对比接下来看代码//向下调整 //参数数组首元素地址、数组元素个数、要向下调整的父结点的下标 void HeapJustDown(int* a, int size, int parent) { //先假设左节点是最大的/小 int child parent * 2 1; while (child size) { //预防非法访问 在俩个子结点里选出最大的 if (child 1 size a[child] a[child 1]) { child; } //大于 大堆 //小于 小堆 if (a[child] a[parent]) { Swap(a[child], a[parent]); } //以上条件都不满足的话说明已经符合大/小堆 else { break; } parent child; child parent * 2 1; } }为什么会有一个child 1 size 这个条件就是为了防止非法访问如果该完全二叉树最后一个叶子节点是左节点呢你直接a[child] a[child1]不就非法访问了while的结束条件也是因为该方法是向下调整的所以child的值元素个数的时候说明child已经比较完了向下调整法建堆接下来再讲一下向下调整法建堆首先我们先理一下向下建堆的前提是什么左右树为堆对这是很重要的一点那么我们拿到一个数组怎么把它里的数据整理成堆呢我们想象一下只有一个结点的时候既可以是大堆也可是是小堆那么如果是最后这一层的叶子结点呢我们是不是也可以将最后一层看作一个堆呢因为我们用向下调整只要保证左右子树是堆就可以了这样子的话我们就可以将最后一个元素的下标传过去然后让他的父结点和俩个子节点对比符合条件的就交换接下来我就画一个流程图所以我们这里如果用向下调整建堆的话还是会用到for循环//向下调整:建堆 void HeapDownPileup(int* a,int size) { //每次传入的都是子节点的父节点size为元素个数 //为什么是size-1-1呢size-1是定位到最后一个元素的下标 //在-1除2就是为了拿到该下标元素的父结点下标 for (int i (size - 1 - 1) / 2; i 0; i--) { HeapDown(a, size, i); } }向下调整建堆的时间复杂度分析第1层 20 个结点需要向下移动h-1层第2层 21 个结点需要向下移动h-2层第3层 22 个结点需要向下移动h-3层第4层 23 个结点需要向下移动h-4层......第h-1层 2h−2 个结点需要向下移动1层当n非常非常大的时候logn是可以忽略不计的不信可以计算看一下~堆插入有了以上的基础在来写堆插入就很简单了// 堆的插入(向上调整建堆) void HeapPush(Heap* hp, HPDataType x) { assert(hp); //判断此时的capacity是否初始化过 if (hp-capacity hp-size) { int new_capacity hp-capacity 0 ? 4 : hp-capacity * 2; HPDataType* tmp (HPDataType*)realloc(hp-a, sizeof(HPDataType) * new_capacity); if (tmp NULL) { perror(malloc fail); exit(-1); } hp-capacity new_capacity; hp-a tmp; } //赋值 hp-a[hp-size] x; hp-size; HeapJustUp(hp-a, hp-size); }这里用的就是向上调整法的插入思维可以做到边存变建堆如果是向下调整法建堆的话就得等所有的数据都已经入到数组以后你在用一个for循环来建堆堆删除堆删除的话主要就是用向下调整的方法来实现// 堆的删除 void HeapPop(Heap* hp) { assert(hp); HeapJustDown(hp-a, hp-size,hp-capacity); hp-size--; }堆排序其实有了前面那些理解堆排序也是很简单的就是利用了堆删除的思想但是要注意的是必须有现成的堆升序 --- 建大堆降序 --- 建小堆我们想想堆删除的思想是什么把根和尾结点交换对吧然后再利用向下调整法把次大的元素弄到根的位置然后我们在交换但是注意这次的交换就不是和尾结点交换了而是尾结点-1的位置交换然后在向下调整直到根和要交换的位置重叠就可以退出循环了这里的循环指的是for大循环不是HespJustDown中的while但是我们每次传入的数组元素个数也要减1不然你往后放的最大值都会被调整上去导致整个堆的性质丢失void HeapSort(int* a, int size, int parent) { assert(a); for (int i size - 1; i 0; i--) { parent 0; Swap(a[0], a[i]); int child parent * 2 1; while (child i) { //预防非法访问 在俩个子结点里选出最大的 if (child 1 i a[child] a[child 1]) { child; } //大于 大堆 //小于 小堆 if (a[child] a[parent]) { Swap(a[child], a[parent]); } //以上条件都不满足的话说明已经符合大/小堆 else { break; } parent child; child parent * 2 1; } } }Top K 问题有了以上基础Top K问题对我们来说就是小caseTOP-K问题即求数据结合中前K个最⼤的元素或者最⼩的元素⼀般情况下数据量都⽐较⼤。⽐如专业前10名、世界500强、富豪榜、游戏中前100的活跃玩家等。对于Top-K问题能想到的最简单直接的⽅式就是排序但是如果数据量⾮常⼤排序就不太可取了(可能数据都不能⼀下⼦全部加载到内存中)。最佳的⽅式就是⽤堆来解决基本思路如下1⽤数据集合中前K个元素来建堆前k个最⼤的元素则建⼩堆因为要堆内最小的元素先替换出然后再把次小的放在堆顶前k个最⼩的元素则建⼤堆2⽤剩余的N-K个元素依次与堆顶元素来⽐较不满⾜则替换堆顶元素将剩余N-K个元素依次与堆顶元素⽐完之后堆中剩余的K个元素就是所求的前K个最⼩或者最⼤的元素总体的思想就是先从文档中按顺序拿取k个数据然后用向下调整法建小堆当然这个看你取k个是最大值还是最小值最后接着拿文档内剩余的数据和堆顶比较符合条件的就入堆void CreateNDate() { //先创建一个存有1000000个随机数据的文档 int n 1000000; FILE* file fopen(data.txt, w); if (file NULL) { perror(file fail); exit(-1); } srand((unsigned)time(NULL)); for (int i 0; i n; i) { // 生成-50000到49999的随机数 int x (rand() % 100000) - 50000i; fprintf(file, %d\n, x); } fclose(file); file NULL; }void PrintTopK(const char* file, int k) { //先建立k个元素的堆 FILE* f fopen(file, r); if (f NULL) { perror(f fail); exit(-1); } //建立一个k大小的数组 int* arr (int*)malloc(sizeof(int) * k); if (arr NULL) { perror(malloc fail); exit(-1); } //先将文档中的k个数值存入数组中 for (int i 0; i k; i) { fscanf(f, %d, arr[i]); } //将数组中的数据用向下调整的方法整理成小堆因为我们这里Top k 求的是最大值 HeapDownPileup(arr, k); //将文档中剩余的第k1个与小堆的堆顶去比较大于就入堆顶 for (int i 0; i 1000000 - k; i) { int tmp 0; fscanf(f, %d, tmp); if (tmp arr[0]) { arr[0] tmp; HeapDown(arr, k, 0); } } //将堆里的数据整理成降序的 HeapSort(arr, k, 0); //打印前k个值 for (int i 0; i k; i) { printf(%d , arr[i]); } fclose(f); free(arr); }其实你了解了思路以后再去看代码真的是非常好的一种学习方式总结向上调整法适用场景边存边建堆动态插入如优先级队列、数据流 TopK。调整方向自下而上新元素和父节点比较交换。核心前提父结点所在子树满足堆性质。操作特点针对单一元素调整多元素需外层循环构建堆时间复杂度向下调整法适用场景已存完数据的静态数组建堆如堆排序初始堆、批量数据建堆。调整方向自上而下当前节点和左右子节点比较交换。核心前提左右子树均满足堆性质。操作特点针对单一元素调整多元素需从最后一个非叶子节点往前循环构建堆时间复杂度 O(n)效率更优。