王道数据结构第三章习题笔记

• 目录
• • 栈的典型应用
  • • 中缀表达式的计算
    • 递归
    • 进制转换
  • 课后习题记录
  • • 3.利用一个栈实现递归函数的非递归计算
• 结语

• 中缀表达式转后缀表达式的手算
  

• 中缀表达式转后缀表达式的机算
  

• 以斐波那契数列为例

#include
using namespace std;
typedef long long int ll;
const ll inf=0x3f3f3f3f3f;
const ll maxn=2e5+10;
const ll mod=998244353;

int f(int n){
    if(n<=2){
        return 1;
    }else{
        return f(n-1)+f(n-2);
    }
}
int main()
{
    int n;
    cin>>n;
    cout< 
进制转换 
实现十进制数转化为radix进制数
 
#include
using namespace std;
typedef long long int ll;
const ll inf=0x3f3f3f3f3f;
const ll maxn=2e5+10;
const ll mod=998244353;

void change(int n,int radix){
    if(n!=0){
        change(n/radix,radix);
        cout<
        return ;
    }

}
int main()
{
    int n,radix;
    cin>>n>>radix;
    change(n,radix);
    return 0;
}



 
课后习题记录 
3.利用一个栈实现递归函数的非递归计算 
 
#include
using namespace std;
typedef long long int ll;
const ll inf=0x3f3f3f3f3f;
const ll maxn=2e5+10;
const ll mod=998244353;
struct node{
    int num;
    double val;
};
stack st;
double p[maxn];
void f(int n,double x){
    if(n==0){
        printf("1n");
        return ;
    }else if(n==1){
        printf("%.2fn",x*2);
        return ;
    }
    while(n>=2){
        st.push({n,0.0});
        n--;
    }
    double f1=1,f2=2*x;
    while(!st.empty()){
        node nd=st.top();
        st.pop();
        p[nd.num]=2*x*f2-2*(nd.num-1)*f1;
        f1=f2;
        f2=p[nd.num];
        //cout<
    int n;
    double x;
    cin>>n>>x;
    f(n,x);
    return 0;
}
 
结语 
遇事不决 可问春风
春风不语 即随本心
我若本心能定 怎会遇事不决 春风亦有春风愁 不劳春风为我忧。
自此春风盈满袖，只为一解平安愁。