输入一个十进制数N与需要转换的进制d
输出转换后的d进制数
转换进制其实就是用短除法不停地除以d求余数,直到剩下的N比d小为止,倒着把余数从左到右写一遍的过程。因为这个“倒着取余数”的操作,让我们想到可以将计算过程在栈中顺序进行,然后弹出顺序就是倒序。
top并不会弹出栈顶元素,pop并不会返回栈顶元素,所以经常top过后就pop,并且要pop或者top之前务必确认!empty()
一个带括号的四则运算表达式
表达式的计算结果
建两个栈,一个数字栈,一个符号栈。 从左到右读,遇到符号时先判断与栈顶符号的优先级顺序,如果入栈元素比栈顶元素优先级低,就弹出数字栈栈顶元素与符号栈栈顶符号计算,直到入栈元素优先级不低于栈顶元素为止。 原理就是保证符号栈中优先级始终从高到低,优先级高的永远比优先级低的先算。 处理括号:左括号优先级最低,右括号优先级最高,遇到右括号就一直弹出计算直到弹出第一个左括号为止。
小晨的电脑上安装了一个机器翻译软件,他经常用这个软件来翻译英语文章。 这个翻译软件的原理很简单,它只是从头到尾,依次将每个英文单词用对应的中文含义来替换。对于每个英文单词,软件会先在内存中查找这个单词的中文含义,如果内存中有,软件就会用它进行翻译;如果内存中没有,软件就会在外存中的词典内查找,查出单词的中文含义然后翻译,并将这个单词和译义放入内存,以备后续的查找和翻译。 假设内存中有M个单元,每单元能存放一个单词和译义。每当软件将一个新单词存入内存前,如果当前内存中已存入的单词数不超过M-1,软件会将新单词存入一个未使用的内存单元;若内存中已存入M个单词,软件会清空最早进入内存的那个单词,腾出单元来,存放新单词。 假设一篇英语文章的长度为N个单词。给定这篇待译文章,翻译软件需要去外存查找多少次词典?假设在翻译开始前,内存中没有任何单词。
输入文件共2行。每行中两个数之间用一个空格隔开。 第一行为两个正整数M和N,代表内存容量和文章的长度。 第二行为N个非负整数,按照文章的顺序,每个数(大小不超过1000)代表一个英文单词。文章中两个单词是同一个单词,当且仅当它们对应的非负整数相同。
包含一个整数,为软件需要查词典的次数。
对于一颗满二叉树(除了最底层节点以外,每个节点都有左右儿子),容易得到左儿子编号是父亲编号的2倍,右儿子为2n+1,所以把任意二叉树补成一颗满二叉树(没有的点就赋初值)即可。
前序遍历:根子树——左节点——右子树 中序遍历:左节点——根子树——右子树 后序遍历:左子树——右子树——根节点 下面是三种知二求一的算法…
前序遍历中第一个字母就是根节点,在中序遍历中找到这个字母,左边就是左子树的中序遍历,右边就是右子树的中序遍历;前序遍历紧接着的是左子树的前序遍历,然后是右子树的前序遍历,所以又变成了左右子树分别已知前序中序遍历求后序遍历的问题——递归。
举个栗子:已知 前序遍历为ABDEFGCH 中序遍历为DFEGBAHC A把中序遍历分为了 左子树中序:DFEGB 右子树中序:HC 左子树前序:BDEFG 右子树前序:CH
和求后序的思路一毛一样
#include <cstdio> #include <cstring> #define RES(a,b) memset(a,b,sizeof(a)) using namespace std; char in[20],post[20]; int len; void print_pre(int inl, int inr, int pol, int por){ if(inl>inr||pol>por) return; printf("%c",post[por]); int pos; for(int i=inl;i<=inr;i++) if(in[i]==post[por]) {pos=i; break;} print_pre(inl,pos-1,pol,pol+pos-inl-1); print_pre(pos+1,inr,pol+pos-inl,por-1); return; } int main(){ RES(in,0); RES(post,0); scanf("%s",in); scanf("%s",post); len=strlen(in)-1; print_pre(0,len,0,len); return 0; }已知: 前序ABDEFGCH 后序FGEDBHCA
最开始用链表建树的时候你发现了它已经是一颗二叉查找树了吗?二叉查找树满足如下三点性质:
左子树中的节点小于根节点右子树中的节点大于根节点左右子树仍是二叉平衡树要实现以下三种操作
查找插入删除因为二叉查找树可能会因为数据的原因退化成一条链,查找效率变低,所以Treap的原理就是给每一个节点分配一个随机的关键词,对于关键词Treap要满足堆的性质,对于权值要满足二叉搜索树的性质——构造了一个随机平衡的二叉查找树。
六个参数:左儿子、右儿子、权值key、用来平衡的随机数fix、该节点重复的数据cnt、以该节点为根节点的子树大小size
struct Node{ Node *left, *right;//左右儿子递归定义 int key,fix,cnt,size; Node (int i) : key(i),fix(rand()),size(1),cnt(1) {}//初始化函数 }*root,*null;//根节点和空节点先做二叉查找树的插入,然后再调整使其满足堆的性质
左旋:右节点到根节点,根节点到左节点(当前结点是根的右儿子)即右节点提升左旋操作:要旋转的子树根节点编号为a void left_rotate(node* &a){ node *b=a->right; a->right=b->left; b->left=a; a=b; } 右旋:左节点到根节点,根节点到右节点(当前结点是根的左儿子)即左节点提升右旋操作:要旋转的子树根节点编号为a void right_rotate(node* &a){ node* b=a->left; a->left=b->right; b->right=a; a=b; }插入操作O(logn),旋转操作最坏O(h)
把待删除节点旋转到只有一个子节点的地方删除即可。正如上一小节提到的一样,左旋可以使右节点提升而右旋可以使左节点提升,引出如下两种操作。 - 当当前结点的左节点小于右节点时,右旋 - 当当前结点的右节点小于左节点时,左旋 - 直到当前结点子节点个数小于等于一时,直接删除即可
就当二叉搜索树查找就好了
如果当前结点大于查找值,在左子树中查找如果当前结点小于查找值,在右子树中查找方法(以前驱为例):
以根节点为当前结点,最优值设为空如果当前结点不大于该元素,更新最优值(如果该节点更接近该元素就更新,否则不做变动),访问当前结点的右子树如果当前结点大于该元素,访问当前结点的左子树直到当前结点是空节点为止下面都需要维护子树的大小 对于旋转、插入、删除三种操作
旋转:插入:删除:有时间了搞这道题
带权路径长度:从根结点到叶子结点的长度与叶子结点数据的乘积 对一一些给定权值的节点,具有最小带权路径长度的二叉树叫做哈夫曼树
权值越大的叶子结点越靠近根节点
生成树的集合(裸的只有一个节点的树)在集合中选取根节点最小和次小的两棵二叉树分别作为左右子树,根节点权值为左右子树根节点权值之和在二叉树集合中删除左右两子树,将新生成的二叉树加入集合重复2、3直到剩下一颗二叉树即为所求的哈夫曼树转载于:https://www.cnblogs.com/leotan0321/p/6081368.html