đề thi và đáp án môn cấu trúc dữ liệu và giải thuật

đề thi và đáp án môn CTDL & GT cấu trúc dữ liệu và giải thuật , lập trình c/c++
1. tạo 2 danh sách liên kết đơn l1,l2 với giá trị của các node trong danh sách là số nguyên.việc nhập mỗi danh sách kêt thúc khi nhập vào số 0. in các giá trị l1, l2 ra màn hình
2. viết hàm merge thực hiện việc trộn luân phiên danh sách l2 vào l1 sao cho sau khi trộn l2 rỗng
3. viết hàm sắp xếp danh sách l1 giảm dần theo trường dữ liệu.
4. chèn 1 số nguyên vào danh sách sao cho vẫn đảm bảo tính giảm dần của l1.

code bài làm:

#include<iostream>
using namespace std;
typedef struct tagnode
{
    int x;
    struct tagnode *next;
}node;
typedef struct taglist
{
    node *dau;
    node *cuoi;
}list;
void khoitao(list &l)
{
    l.dau=l.cuoi=NULL;
}
node *taonode(int x)
{
    node *p=new node;
    if(p==NULL) exit(1);
    p->x=x;
    p->next=NULL;
    return p;
}
void themcuoi(list &l,node *p)
{
    if(l.dau==NULL) l.dau=l.cuoi=p;
    else
    {
        l.cuoi->next=p;
        l.cuoi=p;
    }
}
void nhap(list &l)
{
    int x;
    node *p;
    do{
        cin>>x;
        if(x!=0)
        {
            p=taonode(x);
            themcuoi(l,p);
        }
    }while(x!=0);
}
void xuat(list l)
{
    node *p=l.dau;
    while(p!=NULL)
    {
        cout<<p->x<<" ";
        p=p->next;
    }
}
void sapxep(list &l)
{
    node *p1=l.dau,*p2;
    while(p1!=NULL)
    {
        p2=p1->next;
        while(p2!=NULL)
        {
            if(p2->x > p1->x) swap(p1->x,p2->x);
            p2=p2->next;
        }
        p1=p1->next;
    }
}
void xoadau(list &l)
{
    if(l.dau!=NULL)
    {
        node *p=l.dau;
        if(l.dau==l.cuoi)
        {
            l.dau=l.cuoi=NULL;
            delete p;
        }
        else
        {
            l.dau=l.dau->next;
            delete p;
        }
    }
}
void themdau(list &l,node *p)
{
    if(l.dau==NULL) l.dau=l.cuoi=p;
    else
    {
        p->next=l.dau;
        l.dau=p;
    }
}
void themsauQ(list &l,node *Q,node *p)
{
    if(Q==NULL) themdau(l,p);
    else if(Q==l.cuoi) themcuoi(l,p);
    else
    {
        p->next=Q->next;
        Q->next=p;
    }
}
void merge(list &l1,list &l2)
{
    node *p=l1.dau,*p1;
    while(l2.dau!=NULL && p!=NULL)
    {
        p1=taonode(l2.dau->x);
        themsauQ(l1,p,p1);
        xoadau(l2);
        if(p!=l1.cuoi) p=p->next;
        if(p!=l1.cuoi) p=p->next;
    }
}
void insert(list &l,int a)
{
    node *p1=taonode(a);
    node *p=l.dau,*p2=NULL;
    while(p!=NULL)
    {
        if(a>p->x)
        {
            if(p2==NULL) themdau(l,p1);
            else themsauQ(l,p2,p1);
            break;
        }
        p2=p;
        p=p->next;
    }
}
void main()
{
    list l1,l2;
    khoitao(l1);khoitao(l2);
    cout<<"nhap l1:\n";
    nhap(l1);
    cout<<"nhap l2:\n";
    nhap(l2);
    cout<<"\nxuat cac gia tri:\nl1: ";
    xuat(l1);
    cout<<"\nl2: ";
    xuat(l2);
    cout<<"\ncac gia tri l1,l2 sau khi merge:\n";
    merge(l1,l2);
    cout<<"l1: ";xuat(l1);
    cout<<"\nl2: ";xuat(l2);
    cout<<"\nsau khi sap xep giam danh sach l1:\n";
    sapxep(l1);
    xuat(l1);
    cout<<"\nnhap X=";
    int x;cin>>x;
    insert(l1,x);
    cout<<"l1: ";xuat(l1);
    cout<<endl;
    system("pause");
}

Read More

cộng trừ nhân chia số nguyên lớn không giới hạn

viết chương trình định nghĩa kiểu số nguyên lớn không giới hạn, lập trình thực hiện các phép toán công (+) trừ (-) nhân (*) chia (/) các số nguyên lớn đó. thông thường ta thấy các kiểu float, int có giới hạn của nó, khi vượt quá giớ hạn thì báo lỗi hoặc cho kết quả sai, sau khi học qua danh sách liên kết thì t có thực hiện bài tập giải quyết số nguyên lớn không giới hạn, định nghĩa và thiết kế thuật toán công trừ nhân chia các số nguyên lớn đó. dưới đây là code của chương trình đó, tuy nhiên t không viết chú thích nên có phần khó. dã học qua danh sách liên kết và năm rõ về nó thì sẽ dễ đọc code hơn. mỗi node trong danh sách sẽ lưu 1 chữ só của số nguyên lớn, 1 biến kiểu char trong danh sách để lưu dấu ccủa số là dương hay âm. giá trị của mỗi node trong danh sách theo thứ tự từ đầu đến cuối là giá trị các chữ số của số nguyên lớn. do đó khi công trừ nhân chia, ta duyệt từng node trong danh sách là tiến hành tính toán trên đó, cộng trừ nhân thì thực hiện từ cuối lên đầu, còn chia thì thực hiện duyệt từ đầu đến cuối

#include<iostream>
#include<string>
#include<Windows.h>
using namespace std;
typedef struct tagnode
{
    int x;
    struct tagnode *next;
    struct tagnode *pre;
}node;
typedef struct tagsolon
{
    char c;
    node *dau;
    node *cuoi;
}solon;
void xuat(solon n);
void taosolon(solon &n);
node *taonode(int x);
void themdau(solon &n,node *p);
void nhap(solon &n);
void cong(solon n1,solon n2,solon &n);
void tru(solon n1,solon n2,solon &n);
int sosanh(solon n1,solon n2);
void nhan(solon n1,solon n2,solon &n);
void nhan1so(solon n1,int x,solon &n);
void themcuoi(solon &n,node *p);
void xoa(solon &n);
void xoatruocQ(solon &n,node *Q);
void xoacuoi(solon &n);
void chia(solon n1,solon n2,solon &n);
void xuly(solon &n);

void main()
{
    solon n,n1,n2;
    taosolon(n);taosolon(n1);taosolon(n2);
    cout<<"nhap 2 so nguyen:\n";
    cout<<"a=";nhap(n1);
    cout<<"b=";nhap(n2);
    cout<<"\n1.cong."
        <<"\n2.tru."
        <<"\n3.nhan."
        <<"\n4.chia.\n\n";
    int k;
    cin>>k;
    switch(k)
    {
    case 1:cong(n1,n2,n);cout<<"a+b = ";xuat(n);cout<<endl;break;
    case 2:tru(n1,n2,n);cout<<"a-b = ";xuat(n);cout<<endl;break;
    case 3:nhan(n1,n2,n);cout<<"a*b = ";xuat(n);cout<<endl;break;
    case 4:chia(n1,n2,n);break;
    }
    system("pause");
}


void chia(solon n1,solon n2,solon &n)
{
    if(n1.c==n2.c) n.c='+';
    else n.c='-';
    int q=sosanh(n1,n2);
    if(q<0)
    {
        cout<<"ket qua = 0 \ndu ";xuat(n1);
    }
    else if(q==0) cout<<"ket qua = 1";
    else
    {
        int i;
        solon a;taosolon(a);
        solon b;taosolon(b);
        solon c;taosolon(c);
        node *p,*p2,*p1;
        p1=n1.dau;
        p2=n2.dau;
        while(p2!=NULL)
        {
            p=taonode(p1->x);
            themcuoi(a,p);
            p1=p1->next;
            p2=p2->next;
        }
        while(p1!=NULL)
        {
            q=sosanh(a,n2);
            if(q<0)
            {
                p=taonode(0);
                themcuoi(n,p);
                p=taonode(p1->x);
                themcuoi(a,p);
            }
            else if(q==0)
            {
                p=taonode(1);
                themcuoi(n,p);
                xoa(a);
                p=taonode(p1->x);
                themcuoi(a,p);
            }
            else
            {
                for(i=1;i<=9;i++)
                {
                    xoa(b);
                    nhan1so(n2,i,b);
                    q=sosanh(a,b);
                    if(q<0)
                    {
                        xoa(b);
                        nhan1so(n2,i-1,b);
                        break;
                    }
                }
                i--;
                p=taonode(i);
                themcuoi(n,p);
                xoa(c);
                tru(a,b,c);
                xoa(a);
                p2=c.dau;
                while(p2!=NULL)
                {
                    p=taonode(p2->x);
                    themcuoi(a,p);
                    p2=p2->next;
                }
                p=taonode(p1->x);
                themcuoi(a,p);
            }
            if(p1!=NULL)p1=p1->next;
        }
        // thuc hien 1 lan nua
        q=sosanh(a,n2);
        if(q<0)
        {
            p=taonode(0);
            themcuoi(n,p);
        }
        else if(q==0)
        {
            p=taonode(1);
            themcuoi(n,p);
        }
        else
        {
            for(i=1;i<=9;i++)
            {
                xoa(b);
                nhan1so(n2,i,b);
                q=sosanh(a,b);
                if(q<0)
                {
                    xoa(b);
                    nhan1so(n2,i-1,b);
                    break;
                }
            }
            i--;
            p=taonode(i);
            themcuoi(n,p);
            xoa(c);
            tru(a,b,c);
            xoa(a);
            p2=c.dau;
            while(p2!=NULL)
            {
                p=taonode(p2->x);
                themcuoi(a,p);
                p2=p2->next;
            }
        }
        if(p1!=NULL)p1=p1->next;
        //end
        xuly(n);xuly(a);
        cout<<"a/b = ";xuat(n);cout<<endl;
        if(a.dau!=NULL)
        {
            cout<<"du ";
            xuat(a);
            cout<<endl;
        }
    }
}
void xoatruocQ(solon &n,node *Q)
{
    if(Q==NULL) xoacuoi(n);
    else
    {
        node *p=Q->pre;
        if(p!=NULL)
        {
            if(p==n.dau)
            {
                n.dau=Q;
                n.dau->pre=NULL;
                delete p;
            }
            else
            {
                p->pre->next=Q;
                Q->pre=p->pre;
                delete p;
            }
        }
    }
}
void xuly(solon &n)
{
    node *p=n.dau;
    while(p!=NULL && p->x==0)
    {
        p=p->next;
        xoatruocQ(n,p);
    }
}
void nhan(solon n1,solon n2,solon &n)
{
    node *p,*p1,*p2;
    long long i,dem=0;
    solon a;taosolon(a);
    solon b;taosolon(b);
    p=n2.cuoi;
    while(p!=NULL)
    {
        xoa(a);
        nhan1so(n1,p->x,a);
        for(i=0;i<dem;i++)
        {
            p1=taonode(0);
            themcuoi(a,p1);
        }
        xoa(b);
        p2=n.cuoi;
        while(p2!=NULL)
        {
            p1=taonode(p2->x);
            themdau(b,p1);
            p2=p2->pre;
        }
        xoa(n);
        cong(a,b,n);
        p=p->pre;
        dem++;
    }
    if(n1.c==n2.c) n.c='+';
    else n.c='-';
    xuly(n);
}
void xoa(solon &n)
{
    while(n.dau!=NULL) xoacuoi(n);
}
void xoacuoi(solon &n)
{
    node *p=n.cuoi;
    if(p!=NULL)
    {
        if(n.dau==n.cuoi)
        {
            n.dau=n.cuoi=NULL;
            delete p;
        }
        else
        {
            n.cuoi=p->pre;
            n.cuoi->next=NULL;
            delete p;
        }
    }
}
void themcuoi(solon &n,node *p)
{
    if(n.dau==NULL)n.dau=n.cuoi=p;
    else
    {
        n.cuoi->next=p;
        p->pre=n.cuoi;
        n.cuoi=p;
    }
}
void nhan1so(solon n1,int x,solon &n)
{
    node *p1,*p;
    int k,m=0;
    p1=n1.cuoi;
    while(p1!=NULL)
    {
        k=p1->x*x+m;
        if(k>=10)
        {
            m=k/10;
            k=k%10;
        }
        else m=0;
        p=taonode(k);
        themdau(n,p);
        p1=p1->pre;
    }
    if(m>0)
    {
        p=taonode(m);
        themdau(n,p);
    }
}
void tru(solon n1,solon n2,solon &n)
{
    int q=sosanh(n1,n2);
    int k,m;
    node *p,*p1,*p2;
    if(q==0) return;
    if(n1.c=='+' && n2.c=='+')
    {
        if(q>0)
        {
            m=0;n.c='+';
            p1=n1.cuoi;p2=n2.cuoi;
            while(p1!=NULL && p2!=NULL)
            {
                if(p1->x < (p2->x + m))
                {
                    k=10+p1->x-p2->x-m;
                    m=1;
                }
                else
                {
                    k=p1->x-p2->x-m;
                    m=0;
                }
                p=taonode(k);
                themdau(n,p);
                p1=p1->pre;
                p2=p2->pre;
            }
            while(p1!=NULL)
            {
                if(p1->x < m)
                {
                    k=10+p1->x-m;
                    m=1;
                }
                else
                {
                    k=p1->x-m;
                    m=0;
                }
                p=taonode(k);
                themdau(n,p);
                p1=p1->pre;
            }
        }
        else
        {
            m=0;n.c='-';
            p1=n1.cuoi;p2=n2.cuoi;
            while(p1!=NULL && p2!=NULL)
            {
                if(p2->x < (p1->x + m))
                {
                    k=10+p2->x-p1->x-m;
                    m=1;
                }
                else
                {
                    k=p2->x-p1->x-m;
                    m=0;
                }
                p=taonode(k);
                themdau(n,p);
                p2=p2->pre;
                p1=p1->pre;
            }
            while(p2!=NULL)
            {
                if(p2->x < m)
                {
                    k=10+p2->x-m;
                    m=1;
                }
                else
                {
                    k=p2->x-m;
                    m=0;
                }
                p=taonode(k);
                themdau(n,p);
                p2=p2->pre;
            }
        }
    }
    else if(n1.c=='-' && n2.c=='-')
    {
        if(q>0)
        {
            m=0;n.c='-';
            p1=n1.cuoi;p2=n2.cuoi;
            while(p1!=NULL && p2!=NULL)
            {
                if(p1->x < (p2->x + m))
                {
                    k=10+p1->x-p2->x-m;
                    m=1;
                }
                else
                {
                    k=p1->x-p2->x-m;
                    m=0;
                }
                p=taonode(k);
                themdau(n,p);
                p1=p1->pre;
                p2=p2->pre;
            }
            while(p1!=NULL)
            {
                if(p1->x < m)
                {
                    k=10+p1->x-m;
                    m=1;
                }
                else
                {
                    k=p1->x-m;
                    m=0;
                }
                p=taonode(k);
                themdau(n,p);
                p1=p1->pre;
            }
        }
        else
        {
            m=0;n.c='+';
            p1=n1.cuoi;p2=n2.cuoi;
            while(p1!=NULL && p2!=NULL)
            {
                if(p2->x < (p1->x + m))
                {
                    k=10+p2->x-p1->x-m;
                    m=1;
                }
                else
                {
                    k=p2->x-p1->x-m;
                    m=0;
                }
                p=taonode(k);
                themdau(n,p);
                p2=p2->pre;
                p1=p1->pre;
            }
            while(p2!=NULL)
            {
                if(p2->x < m)
                {
                    k=10+p2->x-m;
                    m=1;
                }
                else
                {
                    k=p2->x-m;
                    m=0;
                }
                p=taonode(k);
                themdau(n,p);
                p2=p2->pre;
            }
        }
    }
    else if(n1.c=='+' && n2.c=='-')
    {
        n2.c='+';
        cong(n1,n2,n);
    }
    else if(n1.c=='-' && n2.c=='+')
    {
        n2.c='-';
        cong(n1,n2,n);
    }
    xuly(n);
}
void cong(solon n1,solon n2,solon &n)
{
    if(n1.c==n2.c)
    {
        n.c=n1.c;
        int k,m=0;
        node *p1=n1.cuoi,*p2=n2.cuoi,*p;
        while(p1!=NULL && p2!=NULL)
        {
            k=p1->x+p2->x+m;
            if(k>=10)
            {
                m=k/10;
                k=k%10;
            }
            else m=0;
            p=taonode(k);
            themdau(n,p);
            p1=p1->pre;
            p2=p2->pre;
        }
        while(p1!=NULL)
        {
            k=p1->x+m;
            if(k>=10)
            {
                m=k/10;
                k=k%10;
            }
            else m=0;
            p=taonode(k);
            themdau(n,p);
            p1=p1->pre;
        }
        while(p1!=NULL)
        {
            k=p1->x+m;
            if(k>=10)
            {
                m=k/10;
                k=k%10;
            }
            else m=0;
            p=taonode(k);
            themdau(n,p);
            p1=p1->pre;
        }
        if(m>0)
        {
            p=taonode(m);
            themdau(n,p);
        }

    }
    else if(n1.c=='+' && n2.c=='-')
    {
        n2.c='+';
        tru(n1,n2,n);
    }
    else
    {
        n1.c='+';
        tru(n2,n1,n);
    }
    xuly(n);
}
int sosanh(solon n1,solon n2)
{
    node *p1=n1.cuoi,*p2=n2.cuoi;
    while(p1!=NULL && p2!=NULL)
    {
        p1=p1->pre;
        p2=p2->pre;
    }
    if(p1==NULL && p2!=NULL) return -1;
    if(p1!=NULL && p2==NULL) return 1;
    if(p1==NULL && p2==NULL)
    {
        p1=n1.dau;
        p2=n2.dau;
        while(p1!=NULL && p2!=NULL)
        {
            if(p1->x > p2->x) return 1;
            if(p1->x < p2->x) return -1;
            p1=p1->next;
            p2=p2->next;
        }
        return 0;
    }
}
void xuat(solon n)
{
    node *p=n.dau;
    if(p==NULL)
    {
        cout<<0;
        return;
    }
    if(p!=NULL && n.c=='-') cout<<n.c;
    while(p!=NULL)
    {
        cout<<p->x;
        p=p->next;
    }
}
void taosolon(solon &n)
{
    n.c='+';
    n.dau=n.cuoi=NULL;
}
node *taonode(int x)
{
    node *p=new node;
    if(p==NULL) exit(1);
    p->x=x;
    p->next=p->pre=NULL;
    return p;
}
void themdau(solon &n,node *p)
{
    if(n.dau==NULL) n.dau=n.cuoi=p;
    else
    {
        p->next=n.dau;
        n.dau->pre=p;
        n.dau=p;
    }
}
void nhap(solon &n)
{
    string s;
    node *p;
    long long i,j=0;
    getline(cin,s);
    if(s[0]=='-')
    {
        n.c='-';
        j=1;
    }
    else if(s[0]=='+')
    {
        n.c='+';
        j=1;
    }
    else n.c='+';
    for(i=s.size()-1;i>=j;i--)
    {
        switch(s[i])
        {
        case '0':p=taonode(0);break;
        case '1':p=taonode(1);break;
        case '2':p=taonode(2);break;
        case '3':p=taonode(3);break;
        case '4':p=taonode(4);break;
        case '5':p=taonode(5);break;
        case '6':p=taonode(6);break;
        case '7':p=taonode(7);break;
        case '8':p=taonode(8);break;
        case '9':p=taonode(9);break;
        }
        themdau(n,p);
    }
}

trên đây là toàn bộ code của chương trình cộng trừ nhân chia số nguyên lớn không giới hạn. code hơi dài, t mất 10 tiếng đồng hồ để suy nghĩ cách làm và cài đặt code, pro đọc qua thấy hay thì like và cải tiến code hoặc gởi form liên hệ code hay hơn để t học hỏi nhé!

Read More

cộng trừ nhân chia đa thức bậc n bất kỳ

viết chương trình c/c++ thực hiện định nghĩa đa thức bậ n bất kỳ và cộng trừ nhân chia trên đa thức. cách làm của Toàn dưới đây là dùng danh sách liên kết đôi để làm. mỗi node sẽ lưu 1 số hạng gồm 2 thông tin là hệ số và số mũ, ngoài thông tin còn có 2 con trỏ của danh sách liên kết. cộng trừ nhân chia đa thức theo kiểu này gây khó khăn cho lập trình nhưng chương trình được tối ưu và chạy nhanh.

#include<iostream>
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, ket thuc khi nhap he so = 0\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;
    }
}
void xoa(dathuc &l)
{
    while(l.dau!=NULL) xoacuoi(l);
}
void chia(dathuc l1,dathuc l2)
{
    node *p,*p1;
    dathuc a,b,du;
    taodathuc(a);taodathuc(b);taodathuc(du);
    p1=l1.dau;
    while(p1!=NULL)
    {
        p=taonode(p1->heso,p1->somu);
        themcuoi(du,p);
        p1=p1->next;
    }
    while(du.dau!=NULL && du.dau->somu >= l2.dau->somu)
    {
        p=taonode(du.dau->heso / l2.dau->heso,du.dau->somu - l2.dau->somu);
        themcuoi(a,p);
        xoa(b);
        if(nhan(l2,a,b)==0) break;
        xoa(du);
        if(tru(l1,b,du)==0) break;
    }
    xuat(a);
    if(du.dau!=NULL)
    {
        cout<<"\n du ";
        xuat(du);
    }
}
void 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;
    cout<<"\n\n1.cong da thuc 1+2"
        <<"\n2.tru da thuc 1-2"
        <<"\n3.nhan da thuc 1*2"
        <<"\n4.chia da thuc 1/2\n";
    cin>>k;
    cout<<"ket qua = ";
    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:chia(l1,l2);break;
    }
    cout<<endl;
    system("pause");
}

trên đây là toàn bộ code của chương trình c/c++ cộng trù nhân chia đa thức bậc n bất kỳ bằng phương pháp sử dụng danh sách liên kết đôi.

Read More

danh sách liên kết kép

danh sách liên kết kép, định nghĩa struct và các hàm thành phần có trong danh sách kép

Read More

danh sách liên kết đơn

Mỗi phần tử liên kết với phần tử đứng liền sau trong danh sách
Mỗi phần tử trong danh sách liên kết đơn là một cấu trúc có hai thành phần
Thành phần dữ liệu: Lưu trữ thông tin về bản thân phần tử
Thành phần liên kết: Lưu địa chỉ phần tử đứng sau trong danh sách hoặc bằng NULL nếu là phần tử cuối danh sách.

Read More