gistfile1.cpp

#include <iostream>
using namespace std;

struct Donthuc
{
    float heso;
    int somu_x;
    int somu_y;
};
struct Node
{
    Donthuc Info;
    Node *pNext;
};
struct Dathuc
{
    Node *pHead;
    Node *pTail;
};
void ListInit(Dathuc &tmp)
{
    tmp.pHead=0;
}
void Add(Dathuc &L, Donthuc t)
{
    Node *tmp = new Node;
    tmp->Info = t;
    //Nếu danh sách rỗng hoặc số mũ đầu danh sách nhỏ hơn số mũ đơn thức thì sẽ thêm vào đầu danh sách
    if (L.pHead == NULL || L.pHead->Info.somu_x+L.pHead->Info.somu_y < t.somu_x+t.somu_y)
    {
        tmp->pNext=L.pHead;
        L.pHead=tmp;
    }
    else
    {
        Node *cur=L.pHead;
        //Tìm vị trí mà đơn thức đứng sau nó có số mũ nhỏ hơn số mũ đơn thức cần thêm
        while (cur->pNext && cur->pNext->Info.somu_x+cur->pNext->Info.somu_y >= t.somu_x+t.somu_y)
        {
            cur=cur->pNext;
        }
            //Nếu vị trí tìm được có số mũ bằng với số mũ đơn thức cần thêm thì chỉ cần cộng hệ số vào đơn thức tại đó
        if (cur->Info.somu_x == t.somu_x && cur->Info.somu_y==t.somu_y)
            cur->Info.heso += t.heso;
        else
        {
            //Thêm vào sau vị trí tìm được
            tmp->pNext = cur->pNext;
            cur->pNext=tmp;
        }
    }
}
void NhapDathuc(Dathuc &tmp)
{
    Donthuc t;
    do
    {
        cout<<endl<<"He so: "; cin>>t.heso;
        cout<<"So mu x: "; cin>>t.somu_x;
        cout<<"So mu y: "; cin>>t.somu_y;
        Add(tmp,t);
    }
    while (t.somu_x+t.somu_y>0);
}
void XuatDathuc(Dathuc L)
{
    Node *cur=L.pHead;
    if (cur)
    {
        cout<<cur->Info.heso<<"X^"<<cur->Info.somu_x<<"Y^"<<cur->Info.somu_y;
        cur=cur->pNext;
    }
    while (cur)
    {
        if (cur->Info.heso)
        {
            if (cur->Info.heso>0) cout<<"+";
                cout<<cur->Info.heso;
            if (cur->Info.somu_x && cur->Info.somu_y) 
                cout<<"X^"<<cur->Info.somu_x<<"Y^"<<cur->Info.somu_y;
        }
    cur=cur->pNext;
    }
}
Dathuc Cong2Dathuc(Dathuc a, Dathuc b)
{
    Dathuc tmp;
    ListInit(tmp);
    Node *cur = a.pHead;
    while (cur)
    {
        Add(tmp,cur->Info);
        cur=cur->pNext;
    }
    cur = b.pHead;
    while (cur)
    {
        Add(tmp,cur->Info);
        cur=cur->pNext;
    }
    return tmp;
}
Dathuc Nhan2Dathuc(Dathuc a, Dathuc b)
{
    Dathuc tmp;
    ListInit(tmp);
    Node *cur_a=a.pHead;
    Node *cur_b;
    Donthuc t;
    while (cur_a)
    {
        cur_b=b.pHead;
        while (cur_b)
        {
            t.heso = cur_a->Info.heso * cur_b->Info.heso;
            t.somu_x = cur_a->Info.somu_x + cur_b->Info.somu_x;
            t.somu_y = cur_a->Info.somu_y + cur_b->Info.somu_y;
            Add(tmp,t);
            cur_b=cur_b->pNext;
        }
        cur_a=cur_a->pNext;
    }
    return tmp;
}
void Rutgon(Dathuc &tmp)
{ 
    Node *cur;
    while (tmp.pHead && tmp.pHead->Info.heso==0)
    {
        cur=tmp.pHead;
        tmp.pHead = tmp.pHead->pNext;
        delete cur;
    }
    if (tmp.pHead)
    {
        cur=tmp.pHead;
        while (cur->pNext)
        {
            if (cur->pNext->Info.heso == 0)
            {
                Node *del = cur->pNext;
                cur->pNext = del->pNext;
                delete del;
            }
            else
                cur=cur->pNext;
        }
    }
}
float TinhGiatri(float X,float Y, Dathuc L)
{
    float Ret=0;
    Node *cur=L.pHead;
    while (cur)
    {
        Ret += (cur->Info.heso * pow(X,cur->Info.somu_x)*pow(Y,cur->Info.somu_y));
        cur=cur->pNext;
    }
    return Ret;
}
void HoanVi ( Donthuc &a, Donthuc &b)
{
    Donthuc temp;
    temp= a;
    a=b;
    b=temp;
}
void Sort (Dathuc &I)
{
/*Node *i,*j,*min;
for (i=I.pHead;i->pNext!=NULL;i=i->pNext)
{
min=i;
for (j=i->pNext;j!=NULL;j=j->pNext)
if (j->Info.somu_x>min->Info.somu_x)
{
HoanVi (min->Info,j->Info);
if (j->Info.somu_y< i->Info.somu_y)
HoanVi (i->Info,j->Info);
}

}*/
    Node *i,*j,*m;
    i=I.pHead;
    while (i!=I.pTail && i!= NULL)
    {
        j=i->pNext;
        m=i;
        /*m->Info.somu_x=i->Info.somu_x;
        m->Info.somu_y=i->Info.somu_y;*/
        while (j!=NULL)
        {
            if (j->Info.somu_x>m->Info.somu_x && j->Info.somu_y<m->Info.somu_y)
            m=j;
            j=j->pNext;
        }
        HoanVi (m->Info,i->Info);
        i=i->pNext;
    }
}

void main()
{
    Dathuc A,B,C,D;
    ListInit(A);
    ListInit(B);
    ListInit(C);
    float X,Y;
    cout<<"Nhap da thuc thu nhat: "<<endl;
    NhapDathuc(A);
    cout<<"Da thuc thu nhat: "<<endl;
    XuatDathuc(A);
    cout<<endl;
    cout<<" Sap xep: ";
    Sort (A);
    XuatDathuc(A);
    cout<<endl<<"Nhap da thuc thu hai: "<<endl;
    NhapDathuc(B);
    cout<<endl<<"Da thuc thu hai: "<<endl;
    XuatDathuc(B);
    C=Cong2Dathuc(A,B);
    cout<<endl<<"Tong hai da thuc: "<<endl;
    Rutgon(C);
    XuatDathuc(C);
    cout<<endl<<"X = ";
    cin>>X;
    cout<<endl<<"Y= ";
    cin>>Y;
    cout<<endl<<"Gia tri da thuc tong: "<<TinhGiatri(X,Y,C)<<endl;
    D=Nhan2Dathuc(A,B);
    cout<<endl<<"Tich hai da thuc: "<<endl;
    Rutgon(D);
    XuatDathuc(D);
    cout<<endl<<"X = ";
    cin>>X;
    cout<<endl<<"Gia tri da thuc tich: "<<TinhGiatri(X,Y,D)<<endl;
}