第六章 数据结构基础

aoapc_2nd C++ 所有文稿

6.1 再谈栈和队列

看不懂就背吧 结构体构造函数

struct Point{
    int x,y;
    Point(int x=0,int y=0):x(x),y(y){}
}

声明Point a,b(1,2)时分别调用了Point()和Point(1,2)

例题 6-3 矩阵链乘

例题代码运用了结构体

struct Matrix{
    int a,b;
    Matrix(int a=0,int b=0):a(a),b(a){}
}m[26];
for(int i=0;i<n;i++){
    cin>>str;
    int k=name[0]-'A';
    cin>>m.[k].a>>m[k].b;
}

自己的代码则用pair来表示矩阵的行数和列数，用set存储矩阵

int n;
string str;
stack<char> cacu;
map<char,pair<int,int> > ma;
cin>>n;
for(int i=0; i<n; i++){
    char x;
    int a,b;
    cin>>x>>a>>b;
    ma[x]=make_pair(a,b);
}
while(cin>>str){
    bool flag=true;
    int row=0,col=0;
    long int tot=0,mul=1;
    for(int i=0; i<str.length(); i++) {
        cout<<"i="<<i<<endl;
        if (str[i]==')'){
            if (row==0&&col==0) {
                row=ma[cacu.top()].first;
                col=ma[cacu.top()].second;
                printf("row=%d col=%d mul=%d\n",row,col,mul);
                cacu.pop();
            }
            if (ma[cacu.top()].second!=row){
                flag=false;
                break;
            }
            mul=ma[cacu.top()].first*row*col;
            row=ma[cacu.top()].first;
            cacu.pop();//弹出矩阵
            cacu.pop();//弹出（
            tot+=mul;
        }
        else cacu.push(str[i]);
        printf("row=%d col=%d\n",row,col);
    }
    if(flag) cout<<tot<<endl;
    else cout<<"error"<<endl;
}

6.2 链表

在数组中频繁移动元素是很低效的，如果可能，可以用链表替代。

2019.3.2