数据结构必做题参考:实验一T1-20,实验2 T1

实验一T1-10

#include <bits/stdc++.h>

using namespace std;

const int N=;

struct Book

{

    string isbn;

    string name;

    double price;

}b[N],r[N];

class book

{

private:

    string isbn;

    string name;

    double price;

    int length;

    book *next;

    static book *head;

    static book *tail;

public:

    book():next(NULL)

    {

        head=tail=this;

    }

    book(string a,string b,double c):isbn(a),name(b),price(c),next(NULL){}

    void Input()

    {

        head->next=new book("","",-);

        tail=head->next;

        string a,b;

        double c;

        /*length=0;//T1-3

        while(cin>>a>>b>>c)

        {

            if(a=="0"&&b=="0"&&c==0)return;

            tail->next=new book(a,b,c);

            tail=tail->next;

            length++;

        }*/

        /*cin>>length;//T4-9

        for(int i=0;i<length;++i)

        {

            cin>>a>>b>>c;

            tail->next=new book(a,b,c);

            tail=tail->next;

        }*/

    }

    void Output()

    {

        cout<<length<<endl;//T1,10

        book *now=head->next;

        while(now->next)

        {

            now=now->next;

            cout<<now->isbn<<" "<<now->name<<" "<<now->price<<endl;

        }

    }

    void BubbleSort()

    {

        book *now;

        book *tmp1;

        book *tmp2;

        double temp1;

        string temp2,temp3;

        for(int i=;i<length;++i)

        {

            now=head->next->next;

            for(int j=;j<length-i;++j)

            {

                tmp1=now;

                tmp2=now->next;

                if(tmp1->price<tmp2->price)

                {

                    temp1=tmp1->price;

                    tmp1->price=tmp2->price;

                    tmp2->price=temp1;

                    temp2=tmp1->isbn;

                    tmp1->isbn=tmp2->isbn;

                    tmp2->isbn=temp2;

                    temp3=tmp1->name;

                    tmp1->name=tmp2->name;

                    tmp2->name=temp3;

                }

                now=now->next;

            }

        }

    }

    void Sort(int s,int t)

    {

        if(s==t)return;

        int m=s+(t-s)/;

        Sort(s,m);

        Sort(m+,t);

        int i=s,j=m+,k=s;

        while(i<=m&&j<=t)r[k++]=b[i].price>=b[j].price?b[i++]:b[j++];

        while(i<=m)r[k++]=b[i++];

        while(j<=t)r[k++]=b[j++];

        for(int ii=s;ii<=t;++ii)b[ii]=r[ii];

    }

    void MergeSort()

    {

        int i=;

        book *now=head->next;

        while(now->next)

        {

            now=now->next;

            b[i].isbn=now->isbn;

            b[i].name=now->name;

            b[i++].price=now->price;

        }

        Sort(,length-);

        now=head->next;

        i=;

        while(now->next)

        {

            now=now->next;

            now->isbn=b[i].isbn;

            now->name=b[i].name;

            now->price=b[i++].price;

        }

    }

    void Update()

    {

        double sum=;

        book *now=head->next;

        while(now->next)

        {

            now=now->next;

            sum+=now->price;

            if(now->next==NULL)break;

        }

        sum/=length;

        cout<<sum<<endl;

        now=head->next;

        while(now->next)

        {

            now=now->next;

            now->price*=now->price<sum?1.2:1.1;

            if(now->next==NULL)break;

        }

    }

    void Inverse()

    {

        book *p=head->next;//头结点

        book *q=p->next;//首元节点

        book *t;

        while(q!=NULL)

        {//依次调整链表指针指向

            t=q->next;

            q->next=p;

            p=q;

            q=t;

        }

        head->next->next->next=NULL;//调整链表尾和头

        head->next->next=p;//

    }

    void inverse()

    {

        book *pre=NULL;

        book *cur=head->next->next;

        book*curnext=cur->next;

        while(cur!=NULL)

        {//依次调整链表指针指向

            cur->next=pre;

            pre=cur;

            cur=curnext;

            if(curnext!=NULL)curnext=curnext->next;

        }

        head->next->next=pre;//调整头结点

    }

    void QueryMax()

    {

        book *now=head->next;

        double mmax=;

        int num=;

        while(now->next)

        {

            now=now->next;

            if((now->price)>mmax)

            {

                mmax=now->price;

                num=;

            }

            else if(now->price==mmax)

            {

                num++;

            }

        }

        now=head;

        cout<<num<<endl;

        while(now->next)

        {

            now=now->next;

            if(now->price==mmax)

            {

                cout<<now->isbn<<" "<<now->name<<" "<<now->price<<endl;

            }

        }

    }

    void findfond()

    {

        int m;

        cin>>m;

        for(int i=;i<m;++i)

        {

            string name;

            cin>>name;

            book *now=head->next;

            int num=;

            while(now->next)

            {

                now=now->next;

                if(now->name==name)num++;

            }

            if(num==)

            {

                cout<<"Sorry，there is no your favourite!"<<endl;

            }

            else

            {

                cout<<num<<endl;

                now=head->next;

                while(now->next)

                {

                    now=now->next;

                    if(now->name==name)

                    {

                        cout<<now->isbn<<" "<<now->name<<" "<<now->price<<endl;

                    }

                }

            }

        }

    }

    void Query()

    {

        int m;

        cin>>m;

        for(int i=;i<m;++i)

        {

            int num;

            cin>>num;

            if(num<||num>length)

            {

                cout<<"Sorry，the book on the best position doesn't exist!"<<endl;

            }

            else

            {

                book *now=head->next;

                while(num--)

                {

                    now=now->next;

                }

                cout<<now->isbn<<" "<<now->name<<" "<<now->price<<endl;

            }

        }

    }

    void Insert()

    {

        int pos;

        string a,b;

        double c;

        cin>>pos>>a>>b>>c;

        if(pos<||pos>length+)

        {

            cout<<"Sorry，the position to be inserted is invalid!"<<endl;

        }

        else

        {

            book *now=head->next;

            while(--pos)now=now->next;

            book *t=new book(a,b,c);

            t->next=now->next;

            now->next=t;

            length++;

            Output();

        }

    }

    void Delete()

    {

        int pos;

        cin>>pos;

        if(pos<||pos>length)

        {

            cout<<"Sorry，the position to be deleted is invalid!"<<endl;

        }

        else

        {

            book *now=head->next;

            while(--pos)now=now->next;

            book *t=now->next->next;

            delete now->next;

            now->next=t;

            length--;

            Output();

        }

    }

    void Unique()

    {

        head->next=new book("","",-);

        tail=head->next;

        string a,b;

        double c;

        cin>>length;

        int num=;

        for(int i=;i<length;++i)

        {

            cin>>a>>b>>c;

            int flag=;

            book *now=head->next;

            while(now->next)

            {

                now=now->next;

                if(now->isbn==a)

                {

                    flag++;

                    num++;

                    break;

                }

            }

            if(flag)continue;

            tail->next=new book(a,b,c);

            tail=tail->next;

        }

        length-=num;

        Output();

    }

}List;

book *book::head;

book *book::tail;

int main()

{

    cout<<fixed<<setprecision();

    //List.Input();//T1-9

    //List.BubbleSort();//T2

    //List.MergeSort();//T2

    //List.Update();//T3

    //List.Inverse();//T4

    //List.inverse();//T4

    //List.Output();//T1-4

    //List.QueryMax();//T5

    //List.findfond();//T6

    //List.Query();//T7

    //List.Insert();//T8

    //List.Delete();//T9

    //List.Unique();//T10

    return ;

}

实验一T11-20

#include <bits/stdc++.h>

using namespace std;

struct Stack1

{

    double a[];

    int top;

    void init(){top=;}

    void push(double x){a[++top]=x;}

    void pop(){top--;}

    int Size(){return top;}

    double query(){return a[top];}

}opnd;

struct Stack2

{

    char a[];

    int top;

    void init(){top=;}

    void push(char x){a[++top]=x;}

    void pop(){top--;}

    int Size(){return top;}

    char query(){return a[top];}

}optr;

inline bool isnum(char a)

{

    if((a>=''&&a<='')||a=='.')return true;

    else return false;

}

inline double cal(char a,double b,double c)

{

    if(a=='+')return b+c;

    else if(a=='-')return b-c;

    else if(a=='*')return b*c;

    else return b/c;

}

inline void opt()//从符号栈弹出一个数,数栈弹出两个数进行计算，将得到的数重新压回数栈

{

    char a=optr.query();

    optr.pop();

    double c=opnd.query();

    opnd.pop();

    double b=opnd.query();

    opnd.pop();

    opnd.push(cal(a,b,c));

}

char s[];

int main()

{

    cout<<fixed<<setprecision();

    while(~scanf("%s",s))//将整个字符串读入方便处理

    {

        optr.init();//栈初始化

        opnd.init();

        if(s[]=='=')break;

        int len=strlen(s);

        for(int i=;i<len;++i)

        {

            if(isnum(s[i]))//如果读到数字，将其拼成一个double类型的数,如果是一位数可直接入栈

            {

                double tmp1=,tmp2=,t=;

                int flag=;

                for(int j=i;j<len;++j)

                {

                    if(isnum(s[j]))

                    {

                        if(s[j]=='.')

                        {

                            flag=;

                            continue;

                        }

                        if(flag==)

                        {

                            tmp1*=;

                            tmp1+=(s[j]-'');

                        }

                        else

                        {

                            t*=0.1;

                            tmp2+=(s[j]-'')*t;

                        }

                    }

                    else

                    {

                        i=j-;

                        break;

                    }

                }

                opnd.push(tmp1+tmp2);

            }

            else if(s[i]=='+'||s[i]=='-')//读入的符号为+-

            {

                if(optr.Size())//如果符号栈不为空才能从数栈弹出2个数进行运算

                {

                    char a=optr.query();

                    while(a=='+'||a=='-'||a=='*'||a=='/')//将将高于*/优先级的符号(即先压入符号栈的+-*/)全部弹出进行计算

                    {

                        opt();

                        if(optr.Size())a=optr.query();

                        else break;//符号栈为空跳出

                    }

                }

                optr.push(s[i]);

            }

            else if(s[i]=='*'||s[i]=='/')//读入的符号为*/

            {

                if(optr.Size())//如果符号栈不为空才能从数栈弹出2个数进行运算

                {

                    char a=optr.query();//将高于*/优先级的符号(即先压入符号栈的*/)全部弹出进行计算

                    while(a=='*'||a=='/')

                    {

                        opt();

                        if(optr.Size())a=optr.query();

                        else break;//符号栈为空跳出

                    }

                }

                optr.push(s[i]);

            }

            else if(s[i]=='(')optr.push(s[i]);//左括号直接压入栈中

            else if(s[i]==')')//右括号不入栈,一直弹出运算直到弹出左括号

            {

                while(optr.query()!='(')opt();

                optr.pop();//弹出左括号

            }

        }

        while(optr.Size())opt();//将符号栈全部弹出,此时数栈应只剩一个数

        cout<<opnd.query()<<endl;//输出中缀算术表达式的结果

    }

    return ;

}//程序默认输入的是正确的中缀算术表达式,如果要判断是否错误,可以通过检查栈是否越界来实现

实验二T1

上述代码已全部在OJ上编译通过。有不足或者不懂的地方可以留言交流。

巴特西

数据结构必做题参考:实验一T1-20,实验2 T1

最新文章

热门文章