数据结构上机作业

2020-11-20

1.STL的栈基础（后缀计算）

题目内容:
请采用STL中的stack对象完成如下后缀表达式的计算，输入采用字符串表示，假设输出
是整数。例如输入:”213*+” 输出5

stack 声明例子
#include <stack>
using namespace std;
stack operStack;

C++代码：

#include<iostream>
#include<stack>
#include<string>
using namespace std;
 //判断是不是操作数:
bool isOperands(const char &c)
{
   if(c>='0'&&c<='9')return true;
   return false;
}
//判断是否为操作符:
bool isOperator(const char &c)
{
    if(c=='+'||c=='-'||c=='*'||c=='/')return true;
    return false;
} 
//从栈中取两个操作数:
void get2Operands(stack<int> &st,int& right,int& left)
{
    right=st.top();
    st.pop();
    left=st.top();
    st.pop();
}
//计算两操作数的值: 
int compute(int& right,int& left,char op) 
{
    int res=0;
    switch(op)
    {
        case '+':
            res=left+right;
            break;
        case '-':
            res=left-right;
            break;
        case '*':
            res=left*right;
            break;
        default:
            res=left/right;
    } 
    return res;
}
int main()
{
    stack<int>operStack;
    string expr;
    cin>>expr;
    int right=0,left=0,res=0; 
    for(int i=0;i<expr.size();i++) //从左到右扫描后缀表达式的每一项 
    {
        if(isOperands(expr[i])) //如果是运算数将其推入栈
        {
            operStack.push(expr[i]-'0');
        }
        else if(isOperator(expr[i])) //如果是二元运算符，则出栈两运算数,并计算结果，再把结果压人栈中
        {                                            
            get2Operands(operStack,right,left);
            operStack.push(compute(right,left,expr[i])); 
        }
    }
    res=operStack.top();
    operStack.pop();
    cout<<res<<endl; 
}

2.两个栈stack来实现队列

题目内容：
请采用两个栈stack来实现队列的出队、入队、取队首元素等操作，然后用这个队列实现整数的基数排序，输出结果。

C++代码：

#include <iostream>
#include <stack>
#include <vector>
using namespace std;
class queue{
private:
    stack<int>s1;//插入元素栈
    stack<int>s2;//删除，取值栈
public:
    void enqueue(int n);//插入队列末尾
    int front();//取队头元素
    void dequeue();//删除队头元素
    bool empty();//队列判空
};
bool queue::empty(){
        if (s1.empty() && s2.empty()){
            return true;
        }
        return false;
}
void queue::enqueue(int n){
    s1.push(n);
}
int queue::front(){
    while(!s1.empty())
    {
        s2.push(s1.top());
        s1.pop();
    }
    int a=s2.top();
    while(!s2.empty()){
        s1.push(s2.top());
        s2.pop();
    }
    return a;
}
void queue::dequeue(){
    while(!s1.empty())
    {
        s2.push(s1.top());
        s1.pop();
    }
    s2.pop();
    while(!s2.empty()){
        s1.push(s2.top());
        s2.pop();
    }
}
void distribute(vector<int>&v,queue q[],int power){//把数分配到队列中去
    int i;
    for(i=0;i<v.size();i++)
    {
        q[(v[i]/power)%10].enqueue(v[i]);
    }
}
void collect(queue q[],vector<int>&v)//把队列的数按大小排列好
{
    int i=0,digit;
    for(digit =0;digit<10;digit++)
    {
        while(!q[digit].empty())
        {
            v[i]=q[digit].front();
            q[digit].dequeue();
            i++;
        }
    }
}
void mysort(vector<int>&v,int d)
{
    int i;
    int power=1;
    queue q[10];
    for(i=0;i<d;i++)
    {
        if(i!=0){
        for (int i = 0;i < v.size();i++)
        {
            cout << v[i] << " ";
        }
        cout << endl;
        }
        distribute(v, q, power);
        collect(q,v);
        power*=10;
    }
}
int main() {
    vector<int> v;
    int k;
    for(int i=0;i<5;i++)
    {
        cin>>k;
        v.push_back(k);
    }
    mysort(v,2);
    for(int i=0;i<v.size();i++){
        cout<<v[i]<<" ";
    }
    cout<<endl;
    return 0;
}

3.使用list实现班级成绩管理

题目内容:
编写一个程序，从文件 StudentFile中读入记录（在第4章末尾描述），构建 5个记 录链表，使得每个班都有一个列表。记录中存放着学生的名字、学号、累计 GPA。把这些记录存储在 list 向量中。在构建这些列表之后，对每个列表进行排序，并使用不同的题头打印出来。注意∶如果 aList是 list对象，则 aistsort）;将根据在类型T的对象上定义的<来对 aList排序。在本题中，你必须重载 operator<（）来定义一个学生记录比另一个小的意思。

C++代码：

#include<iostream>
#include<fstream>
#include<list>
#include<iomanip>
#include<algorithm>
using namespace std;
class student{
public:
    int num;
    string xing;
    string ming;
    char middle;
    string city;
    string state;
    string phone;
    char sex;
    int grade;
    int fraction;
    double GPA;
    string pro;
    /*10103 Johnson, James L
    Waupun, Wisconsin 7345229 M
    1 15 3.15 ENGR*/
    student(int n=0, string x="null", string m="null", char zhongjian='0', string ci="null", string sta="null", string dianhua="null", char xingbie='M', int nianji=1, int fenshu=0, double jidian=0, string zhuanye = "null"):num(n), xing(x), ming(m), middle(zhongjian), city(ci), state(sta), phone(dianhua), sex(xingbie), grade(nianji), fraction(fenshu), GPA(jidian), pro(zhuanye) {}
    friend bool operator < (const student& other,const student& other2);//重载<为友元函数
};
bool operator < (const student& stu,const student& stu2)
    {
        return(stu.GPA < stu2.GPA);
    }//重载小于号，使sort函数能够对student类型的链表进行排序。
ostream& operator<<(ostream& mout, student x){
    mout << x.num << " "<< setw(15) << x.xing << setw(15) << x.ming<<" "<< setw(2) << x.middle << setw(17) << x.city << setw(15) << x.state << setw(8) << x.phone << setw(5) << x.sex << setw(6) << x.grade << setw(6) << x.fraction << setw(7) << x.GPA << setw(7) << x.pro;
    return mout;//重载输出符号，对student类型的对象进行输出。为了保持格式的美观这里控制了行距
}
int main() {
    int n,nianji,fenshu;
    string x,m,ci,sta,dianhua,zhuanye;
    char zhongjian='0',xingbie;
    double jidian;
    ifstream infile("/Users/apple/Desktop/c++作业/StudentFile.txt");//输入流，从文本文件输入，xcode中使用文件流用绝对路径
    list<student> Class[5];//创建5个班级
    while (infile >> n >> x >> m >>zhongjian>> ci >> sta >> dianhua>>xingbie>>nianji>>fenshu>>jidian >> zhuanye) {
        student rea(n, x, m,zhongjian,ci, sta, dianhua,xingbie,nianji,fenshu,jidian, zhuanye);
        for(int i=0;i<5;i++)
        {
            if(rea.grade==i+1)Class[i].push_back(rea);//把对应的班级的学生加入各自链表
        }
    }
    for(int i=0;i<5;i++)
    {
        Class[i].sort();//对每个班级根据GAP排序
    }
    for(int i=0;i<5;i++)
    {
        cout<<i+1<<"班级的学生GPA排名为:"<<endl;
        cout<< "学号" << " "<<setw(15) << "姓" << setw(20) << "名" << " "<< setw(8) << "中间字" << setw(15) << "城市" << setw(15) << "州" << setw(13) << "电话" << setw(10) << "性别" << setw(8) << "年级" << setw(8) << "分数" << setw(10) << "绩点" << setw(8) << "专业"<<endl;
        list<student>::iterator t1;//使用迭代器进行对每个元素输出
        for (t1=Class[i].begin(); t1 != Class[i].end(); t1++)
        cout << *t1 << endl;//遍历链表，输出链表。
    }
}

实验总结:

文件流输入格式为：

ifstream infile("/Users/apple/Desktop/c++作业/StudentFile.txt");//输入流，从文本文件输入，xcode中使用文件流用绝对路径
    while (infile >> n >> x >> m >>zhongjian>> ci >> sta >> dianhua>>xingbie>>nianji>>fenshu>>jidian >> zhuanye) 
    {
        student rea(n, x, m,zhongjian,ci, sta, dianhua,xingbie,nianji,fenshu,jidian, zhuanye);//将赋予一个类对象
    }