Dùng danh sách liên kết để biểu diễn 1 tập hợp

struct Node {
    int val;
    Node * next;
    
    Node(int v) : val(v), next(0) {}
};

void insert(Node * &head, int x) {
    if (!head)   // Nếu linked list chưa có gì thì tạo node mới chứa x là xong.
        head = new Node(x);
    else if (head->val != x) {
        // Kiểm tra coi x có trong list chưa. Đoạn này có thể viết thành hàm để dùng cho câu sau.
        Node * prev = 0;
        for (prev = head; prev->next && prev->next->val != x; prev = prev->next);

        if (!prev->next)   // x chưa có trong list thì thêm vào cuối dãy
            prev->next = new Node(x);
    }
}

int main() {
    Node * head = 0;
    insert(head, 3);   // 3
    insert(head, 4);   // 3 4
    insert(head, 5);   // 3 4 5
    insert(head, 3);   // 3 4 5

    delete head;
    head = 0;
    return 0;
}

#include <iostream.h>
#include <math.h>
using namespace std;
typedef struct tagnode
{
    float heso,somu; 
    struct tagnode *next,*pre;
}node;
node *taonode(float heso,float somu)
{
    node *p=new node;
    if(p==NULL) exit(1);
    p->heso=heso;
    p->somu=somu;
    p->next=p->pre=NULL;
    return p;
}
typedef struct tagdathuc
{
    node*dau,*cuoi; 
}dathuc;
void taodathuc(dathuc &l)
{
    l.dau=l.cuoi=NULL;
}
void themcuoi(dathuc &l,node *p)
{
    if(l.dau==NULL) l.dau=l.cuoi=p;
    else
    {
        l.cuoi->next=p;
        p->pre=l.cuoi;
        l.cuoi=p;
    }
}
void nhap(dathuc &l)
{
    node *p;
    float heso,somu;
    cout<<"Nhap so da thuc, nhap he so = 0 khi xong 1 da thuc\n";
    do{
        cout<<"he so = ";cin>>heso;
        if(heso!=0)
        {
            cout<<"so mu = ";cin>>somu;
            p=taonode(heso,somu);
            themcuoi(l,p);
        }
        cout<<endl;
    }while(heso!=0);
}
void xuat(dathuc l)
{
    node *p=l.dau;
    if(p==NULL)
    {
        cout<<0;
        return;
    }
    while(p!=NULL)
    {
        if(p==l.dau)
        {
            if(p->somu==0) cout<<p->heso;
            else if(fabs(p->heso)!=1 && p->somu!=1) cout<<p->heso<<"X^"<<p->somu;
            else if(fabs(p->heso)!=1 && p->somu==1) cout<<p->heso<<"X";
            else if(fabs(p->heso)==1 && p->somu!=1) cout<<(p->heso==1?"X^":"-X^")<<p->somu;
            else cout<<(p->heso==1?"X":"-X");
        }
        else
        {
            if(p->somu==0) cout<<(p->heso<0?" - ":" + ")<<fabs(p->heso);
            else if(fabs(p->heso)!=1 && p->somu!=1) cout<<(p->heso<0?" - ":" + ")<<fabs(p->heso)<<"X^"<<p->somu;
            else if(fabs(p->heso)!=1 && p->somu==1) cout<<(p->heso<0?" - ":" + ")<<fabs(p->heso)<<"X";
            else if(fabs(p->heso)==1 && p->somu!=1) cout<<(p->heso==1?" + X^":" - X^")<<p->somu;
            else cout<<(p->heso==1?" + X":" - X");
        }
        p=p->next;
    }
}
void sapxep(dathuc &l)
{
    node *p1=l.dau,*p2;
    while(p1!=NULL)
    {
        p2=p1->next;
        while(p2!=NULL)
        {
            if(p2->somu>p1->somu)
            {
                swap(p1->heso,p2->heso);
                swap(p1->somu,p2->somu);
            }
            p2=p2->next;
        }
        p1=p1->next;
    }
}
void xoatruocQ(dathuc &l,node *Q)
{
    node *p;
    if(Q==NULL)
    {
        p=l.cuoi;
        if(l.dau==l.cuoi)
        {
            l.dau=l.cuoi=NULL;
            delete p;
        }
        else if(p!=NULL)
        {
            l.cuoi=l.cuoi->pre;
            l.cuoi->next=NULL;
            delete p;
        }
    }
    else
    {
        p=Q->pre;
        if(p!=NULL)
        {
            if(p==l.dau)
            {
                l.dau=l.dau->next;
                l.dau->pre=NULL;
                delete p;
            }
            else
            {
                p->pre->next=Q;
                Q->pre=p->pre;
                delete p;
            }
        }
    }
}
void rutgon(dathuc &l)
{
    node *p1=l.dau,*p2;
    while(p1!=NULL)
    {
        p2=p1->next;
        while(p2!=NULL)
        {
            if(p2->somu==p1->somu)
            {
                p1->heso+=p2->heso;
                p2=p2->next;
                xoatruocQ(l,p2);
            }
            else p2=p2->next;
        }
        p1=p1->next;
    }
}
void themtruocQ(dathuc &l,node *Q,node *p)
{
    if(Q==l.dau)
    {
        l.dau->pre=p;
        p->next=l.dau;
        l.dau=p;
    }
    else
    {
        p->pre=Q->pre;
        p->next=Q;
        Q->pre->next=p;
        Q->pre=p;
    }
}
void insert(dathuc &l,node *p)
{
    node *p1=l.dau;
    while(p1!=NULL && p1->somu > p->somu) p1=p1->next;
    if(p1!=NULL)
    {
        if(p1->somu == p->somu) p1->heso += p->heso;
        else themtruocQ(l,p1,p);
    }
    else themcuoi(l,p);
}
void xuly(dathuc &l)
{
    node *p=l.dau;
    while(p!=NULL)
    {
        if(p->heso==0)
        {
            p=p->next;
            xoatruocQ(l,p);
        }
        else p=p->next;
    }
}
int cong(dathuc l1,dathuc l2,dathuc &l)
{
    node *p=l1.dau,*a;
    while(p!=NULL)
    {
        a=taonode(p->heso,p->somu);
        themcuoi(l,a);
        p=p->next;
    }
    p=l2.dau;
    while(p!=NULL)
    {
        a=taonode(p->heso,p->somu);
        insert(l,a);
        xuly(l);
        p=p->next;
    }
    xuly(l);
    if(l.dau==NULL) return 0;
    return 1;
}
int tru(dathuc l1,dathuc l2,dathuc &l)
{
    node *p=l2.dau;
    while(p!=NULL)
    {
        p->heso=-p->heso;
        p=p->next;
    }
    cong(l1,l2,l);
    p=l2.dau;
    while(p!=NULL)
    {
        p->heso=-p->heso;
        p=p->next;
    }
    if(l.dau==NULL) return 0;
    return 1;
}
int nhan(dathuc l1,dathuc l2,dathuc &l)
{
    node *p,*p1,*p2;
    p2=l2.dau;
    while(p2!=NULL)
    {
        p1=l1.dau;
        while(p1!=NULL)
        {
            p=taonode(p2->heso*p1->heso,p2->somu+p1->somu);
            insert(l,p);
            p1=p1->next;
        }
        p2=p2->next;
    }
    xuly(l);
    if(l.dau==NULL) return 0;
    return 1;
}
void xoacuoi(dathuc &l)
{
    node *p=l.cuoi;
    if(p==NULL) exit(1);
    if(l.dau==l.cuoi)
    {
        l.dau=l.cuoi=NULL;
        delete p;
    }
    else
    {
        l.cuoi=p->pre;
        l.cuoi->next=NULL;
        delete p;
    }
}
double giatridathuc(dathuc l, double x)
{
 node *p=l.dau;
 int s=0;
 while(p!=NULL)
 {
  s+=p->heso*pow(x,p->somu);
  p=p->next;
 }
 return s;
}
void xoa(dathuc &l)
{
    while(l.dau!=NULL) xoacuoi(l);
}
int main()
{
    dathuc l1,l2,l;
    taodathuc(l1);taodathuc(l2);taodathuc(l);
    nhap(l1);nhap(l2);
    rutgon(l1);sapxep(l1);
    cout<<"\nda thuc 1 = ";xuat(l1);cout<<endl;
    rutgon(l2);sapxep(l2);
    cout<<"\nda thuc 2 = ";xuat(l2);cout<<endl;
    int k,x;
    cout<<"\n\n1.cong da thuc 1+2"
        <<"\n2.tru da thuc 1-2"
        <<"\n3.nhan da thuc 1*2"
        <<"\n4.Tinh gia tri da thuc tai X:"<<endl;
    cin>>k;
    switch(k)
    {
    case 1:cong(l1,l2,l);xuat(l);break;
    case 2:tru(l1,l2,l);xuat(l);break;
    case 3:nhan(l1,l2,l);xuat(l);break;
    case 4:cin>>x;cout<<giatridathuc(l,x); break;
    }
    cout<<endl;
    system("pause");
}

dathuc l1;
nhap(l1); taodathuc(l1);
xuat(l1);
std::cout << std::endl << giatridathuc(l1, 3);   // tính giá trị của đa thức l1 tại x = 3.