|
栈：四种类型题 1、进制转换问题 2、括号匹配问题: 左入右出:1353,1354,1355 () 基本操作 []() 升级版：判断类型 <([{ plus版：判断类型判断优先级 3、车厢调度 4、后缀表达式计算 #include <stack> //stack<int> s; int n; cin>>n; int b[1000]={}; for(int i=0;i<n;i++) cin>>b[i]; stack<int> c;//创建栈 int a=1; for(int i=0;i<n;i++){ if(c.empty()) c.push(a++);//先存a，然后a自增1 while(c.top()!=b[i]&&a<=n) c.push(a++); if(c.top()==b[i]) c.pop(); else cout<<"NO"; } if(c.empty()) cout<<"YES"; else cout<<"NO"; c.empty();//判断栈空 空true 不空false c.push(x);//入栈 c.pop();//出栈 c.top();//获取栈顶元素 c.size();//栈内元素的数量 后缀表达式（逆波兰式） 中 前 运算符所在的位置不同 中缀表达式：人类的数学表达式 后：将中缀表达式的括号去掉，运算符后置 1+2*(3-4)/5+6 1、先将运算符的优先级用括号表达出来 1+2*(3-4)/5+6 -> ((1+((2*(3-4))/5))+6) 2、从里到外拆括号，拆的过程，移动运算符位置 ((1+((2*(3-4))/5))+6) ((1+((2*34-)/5))+6) ((1+(234-*/5))+6) ((1+234-*5/)+6) (1234-*5/++6) 1234-*5/+6+ 1+2*(3-4)/5+6 4 2 1 3 5
1 2 3 4-* 5/+ 6+ 1、先把数字抄下来 2、把运算符的先后顺序标出来 3、按照标号顺序，往后写 输入中缀，输出后缀 创建一个符号栈 遇到数字就输出 遇到符号就入栈（前提是栈顶优先级低，否则先出栈后入栈） 遇到左括号，代表一个新的开始，遇到右括号代表当前的结束 string str;//中缀 cin>>str; stack<char> s; for(int i=0;i<str.size();i++){ if(str[i]>=48&&str[i]<=57) cout<<str[i]; else if(str[i]=='(') s.push(str[i]); else if(str[i]==')'){ while(s.top()!='(') { cout<<s.top(); s.pop(); } s.pop();//去掉多余的左括号 } else { while(!s.empty()&&s.top()!='('&&s.top()优先级>=str[i]优先级){ cout<<s.top(); s.pop(); } s.push(str[i]); } } 字符串下标代表优先级 string yxj="+-*/";//yxj.find(s.top())/2 函数 int getyxj(char c){ if(c=='+'||c=='-') return 1; if(c=='*'||c=='/') return 1; } 输入后缀，输出结果 创建一个数字栈 遇到数字进栈（数字如果多余1位，需要拼接） 遇到符号，出栈两个，计算，将结果放回 string s="1353 547 645 35 3254 "; string t=""; for(int i=0;i<s.size();i++){ if(s[i]>=48&&s[i]<=57){ t+=s[i]; } else if(s[i]==' '){ int a=stoi(t); t=""; } } int a=s.top();s.pop(); int b=s.top();s.pop(); s.push(b+a); 输入中缀，输出结果 stack栈 empty(); push(); pop(); size(); top(); stack<int> s; s.push(x); s.pop(); cout<<s.top(); c++中的容器适配器之一，其他两个分别是 queue队列 queue<int> q; q.push(x); q.pop(); cout<<q.front(); cout<<q.back(); empty(); push(); pop(); size(); front(); back(); priority_queue()优先队列(底层是堆) empty(); push(); pop(); size(); top();//堆顶总是最大值 ----------- c++：序列容器，关联容器，容器适配器 ----------- 链表 ：一对一结构，除了链头和链尾，其他的节点都有唯一的前驱和后继 树：一对多结构，除了根和叶子，其他的节点都有唯一的前驱和不唯一的后继 struct node{ char c; node* fat; vector<node*> chi; }; 一维数组存树 邻接表存树 邻接矩阵存树（其实用来存图） 概念： 节点：树上的每个元素 根节点/祖先节点：最高层的节点，没有父节点的节点 叶子节点：没有子节点的节点 父节点，子节点 兄弟节点：同一父节点的节点 子孙节点：子节点以及子节点的子节点等合集 路径：树上的两个节点相连的一系列边 深度：节点到根节点的路径长 子树：某个节点及其所有的子孙节点的集合 度：一个节点的子节点数量 树的度：树上所有节点中，最大的度就是树的度 二叉树：每个节点最多有两个子节点的树 满二叉树：每一层的节点都是满的 完全二叉树：除了最后一层，每一层都是满的，最后一层节点都靠左，没有空隙 堆：每个节点都比它的子节点大（小）的完全二叉树（最小堆，最大堆，小顶堆，大顶堆） 完全二叉树，把节点编号，从上到下，从左到右 如果根序号为1，对于任意节点x，其父节点序号为x/2，左右子节点序号为2*x，2*x+1 如果根序号为0，对于任意节点x，其父节点序号为(x-1)/2，左右子节点序号为2*x+1，2*x+2 下节课代码： 对于树的遍历： 先序遍历、中序遍历、后序遍历、层序遍历 哈夫曼树（哈夫曼编码）、二叉搜索树、二叉堆&堆排序 题目： 栈题，队列题，树：1336 算法：递推递归 (责任编辑：admin) |