怎样做淘宝联盟的网站,网站模版如何去除title版权信息,黄骅做网站价格,wordpress 仿花瓣3.4堆的应用
3.4.1 堆排序
堆排序即利用堆的思想来进行排序#xff0c;总共分为两个步骤#xff1a;
1. 建堆 1.升序#xff1a;建大堆#xff1b; 2.降序#xff1a;建小堆。
2. 利用堆删除思想来进行排序
这种写法有两个缺点#xff1a; 1、先有一个堆的数据结构 …3.4堆的应用
3.4.1 堆排序
堆排序即利用堆的思想来进行排序总共分为两个步骤
1. 建堆 1.升序建大堆 2.降序建小堆。
2. 利用堆删除思想来进行排序
这种写法有两个缺点 1、先有一个堆的数据结构 2、空间复杂度复杂度的消耗
void HeapSort(int* a, int n)
{HP hp;HeapInit(hp);for (int i 0; i n; i){HeapPush(hp, a[i]);}int i 0;while (!HeapEmpty(hp)){//printf(%d , HeapTop(hp));a[i] HeapTop(hp);HeapPop(hp);}HeapDestroy(hp);
}
所以我们可以稍微改进一下使得只要有一个数组就可以进行堆排序
假设要排一个升序
先使用向下调整的方式建一个大堆然后再写一个循环当end0时结束循环每次进入循环先交换首尾数据然后从头开始进行向下调整每次end--。
void AdjustDown(int* a,int n, int parent)
{int child parent * 2 1;while(child n){if (a[child] a[child 1] child 1 n){child 1;}if (a[child] a[parent]){Swap(a[parent], a[child]);parent child;child parent * 2 1;}else{break;}}
}
void HeapSort(int* a, int n)
{//向下调整建堆for (int i (n-1-1)/2; i n; i--){AdjustDown(a,n,i);}int end n - 1;while (end 0){Swap(a[0], a[end]);AdjustDown(a, end, 0);end--;}
}
3.4.2 TOP-K问题
TOP-K问题即求数据结合中前K个最大的元素或者最小的元素一般情况下数据量都比较大。 比如专业前10名、世界500强、富豪榜、游戏中前100的活跃玩家等。 对于Top-K问题能想到的最简单直接的方式就是排序但是如果数据量非常大排序就不太可取了(可能数据都不能一下子全部加载到内存中)。最佳的方式就是用堆来解决基本思路如下
1. 用数据集合中前K个元素来建堆 前k个最大的元素则建小堆 前k个最小的元素则建大堆
2. 用剩余的N-K个元素依次与堆顶元素来比较不满足则替换堆顶元素 将剩余N-K个元素依次与堆顶元素比完之后堆中剩余的K个元素就是所求的前K个最小或者最大的元素。 void PrintTopK(const char* filename, int k){// 1. 建堆--用a中前k个元素建堆FILE* fout fopen(filename, r);if (fout NULL){perror(fopen fail);return;}int* minheap (int*)malloc(sizeof(int) * k);if (minheap NULL){perror(malloc fail);return;}for (int i 0; i k; i){fscanf(fout, %d, minheap[i]);}// 前k个数建小堆for (int i (k - 2) / 2; i 0; --i){AdjustDown(minheap, k, i);}// 2. 将剩余n-k个元素依次与堆顶元素交换不满则则替换int x 0;while (fscanf(fout, %d, x) ! EOF){if (x minheap[0]){// 替换你进堆minheap[0] x;AdjustDown(minheap, k, 0);}}for (int i 0; i k; i){printf(%d , minheap[i]);}printf(\n);free(minheap);fclose(fout);}
4.二叉树链式结构的实现
4.1 前置说明
在学习二叉树的基本操作前需先要创建一棵二叉树然后才能学习其相关的基本操作。此处手动快速创建一棵简单的二叉树快速进入二叉树操作学习等二叉树结构了解的差不多时我们反过头再来研究二叉树真正的创建方式。 首先我们手动创建一个链式二叉树链接完后的二叉树大概是这个样子。
再看二叉树基本操作前再回顾下二叉树的概念二叉树是1. 空树2. 非空根节点根节点的左子树、根节点的右子树组成的。
从概念中可以看出二叉树定义是递归式的因此后序基本操作中基本都是按照该概念实现的。 typedef struct BinaryTreeNode
{struct BinaryTreeNode* left;struct BinaryTreeNode* right;int val;
}BTNode;
int main()
{BTNode* node1 BuyListNode(1);BTNode* node2 BuyListNode(2);BTNode* node3 BuyListNode(3);BTNode* node4 BuyListNode(4);BTNode* node5 BuyListNode(5);BTNode* node6 BuyListNode(6);node1-left node2;node1-right node4;node2-left node3;node4-left node5;node4-right node6;
}
4.2二叉树的遍历
4.2.1 前序、中序以及后序遍历
学习二叉树结构最简单的方式就是遍历。所谓二叉树遍历(Traversal)是按照某种特定的规则依次对二叉树中的节点进行相应的操作并且每个节点只操作一次。访问结点所做的操作依赖于具体的应用问题。 遍历是二叉树上最重要的运算之一也是二叉树上进行其它运算的基础。 按照规则二叉树的遍历有前序/中序/后序的递归结构遍历
1. 前序遍历(Preorder Traversal 亦称先序遍历)——访问根结点的操作发生在遍历其左右子树之前。 2. 中序遍历(Inorder Traversal)——访问根结点的操作发生在遍历其左右子树之中间。 3. 后序遍历(Postorder Traversal)——访问根结点的操作发生在遍历其左右子树之后。 由于被访问的结点必是某子树的根所以N(Node、L(Left subtree和R(Right subtree又可解释为根、根的左子树和根的右子树。NLR、LNR和LRN分别又称为先根遍历、中根遍历和后根遍历。
下面主要分析前序递归遍历中序与后序图解类似
前序,中序,后序遍历代码
//前序 根 左子树 右子树
void PrevOrder(BTNode* root)
{if (root NULL){printf(NULL );return;}printf(%d , root-val);PrevOrder(root-left);PrevOrder(root-right);
}//中序 左子树 根 右子树
void InOrder(BTNode* root)
{if (root NULL){printf(NULL );return;}InOrder(root-left);printf(%d , root-val);InOrder(root-right);
}//右序 左子树 右子树 根
void PostOrder(BTNode* root)
{if (root NULL){printf(NULL );return;}PostOrder(root-left);PostOrder(root-right);printf(%d , root-val);
}
前序遍历递归图解
先访问根在访问左子树也就是先访问1再访问1的左子树1的左子树的根是2所以再访问22的左子树还没有访问完所以访问2的左子树的根3再访问3的左子树NULL到这里3的左子树访问完毕开始访问3的右子树NULL到这里3的右子树也访问完毕开始访问2的右子树NULL......以此类推 前序遍历递归展开图 中序和后序都是一样的过程总之就是要把对应的左子树/右子树遍历到NULL才返回上一层。
4.3二叉树节点个数
这里也要把问题转化为递归的子问题使用一个三目操作符差不多是一个后序遍历如果当前节点为NULL则返回0不是NULL则返回他的左子树和右子树的节点个数加1也就是自己这个节点。比方说要求以下二叉树的节点个数后序就是从3的左子树NULL开始节点3的左右子树都为空则节点3返回0011再求节点2节点2的左子树返回了1右子树返回0所以节点2返回1012以此类推1的右子树返回的是3所以1这个根节点的返回值是2316. //节点个数
int TreeSize(BTNode* root)
{//后序return root NULL ? 0 : TreeSize(root-left) TreeSize(root-right) 1;
}
4.4二叉树叶子节点个数
叶子节点就是没有左右子树的节点所以进入函数先判断当前节点是否为NULL如果是则返回0再判断是否为叶子节点左子树和右子树都为NULL才是叶子节点返回1。如果两个if都未进入说明当前节点至少有一个子节点再写一个递归往下找返回左右子树的全部叶子节点。 int TreeLeafSize(BTNode* root)
{//当前节点为空if (root NULL)return 0;//左右子树为空自己就是叶子if (root-left NULL root-right NULL)return 1;//往下找return TreeLeafSize(root-left) TreeLeafSize(root-right);
}
4.5二叉树第k层节点个数
要求第k层的节点个数首先我们要知道一个思路假设要求这个二叉树第3层的节点个数那么第3层就相当于根节点1的第3层根节点1的第三层又相当于2和4的第二层2和4的第二层又相当于356的第一层所以当k1且不为空时返回1即可。递归左右子树每次k-1. int TreeKLevel(BTNode* root, int k)
{assert(k 0);if (root NULL){return 0;}//走到最后一层if (k 1){return 1;}//每次往下找一层return TreeKLevel(root-left, k - 1) TreeKLevel(root-right, k - 1);
}
4.6二叉树查找值为x的节点
查找节点的话首先判断当前节点是否满足valx如果满足直接返回当前节点再判断是否为空如果既不为空也不是要查找的节点则开始往左子树开始找这个时候要创建一个变量tail来保存返回值使用if判断返回值是什么情况如果是空则开始往右子树找如果不为空则说明找到了直接返回tail。右子树也是一样的步骤如果左右子树都没找到说明找不到了返回NULL。
BTNode* TreeFind(BTNode* root,int x)
{if (root-val x)return root;if (root NULL)return NULL;BTNode* tail NULL;tail TreeFind(root-left,x);if (tail)return tail;tail TreeFind(root-right,x);if (tail)return tail;return NULL;
} 今天的分享到这里就结束啦感谢大家的阅读
