kết quả từ 1 tới 11 trên 11

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

  1. #1
    Ðến Từ
    TP. Hồ Chí Minh
    Thành Viên Thứ: 353076
    Giới tính: Nam
    Bài gửi
    45
    Quick reply to this message Trả lời       


  2. #2
    Ðến Từ
    TP. Hồ Chí Minh
    Thành Viên Thứ: 56897
    Giới tính: Nam
    Bài gửi
    881

    Reply: Dung danh sach lien ket de bieu dien 1 tap hop

    Bài này rất là cơ bản. Bạn đã học được gì về linked list rồi?
    LCD: 13.3" 1920x1080 IPS
    CPU: Intel i7 - 4700MQ (2.4 GHz - 3.4 GHz)
    GPU: Nvidia GTX 765m with GDDR5 2GB
    RAM: 2x8GB G.Skill 2133
    HDD: Samsung SSD 850 Pro 512 GB
    2 kg.

  3. #3
    Ðến Từ
    TP. Hồ Chí Minh
    Thành Viên Thứ: 353076
    Giới tính: Nam
    Bài gửi
    45

    Reply: Dung danh sach lien ket de bieu dien 1 tap hop

    moi bat dau hoc thoi ban, nen chua hieu nhieu ve cai nay dc

  4. #4
    Ðến Từ
    TP. Hồ Chí Minh
    Thành Viên Thứ: 56897
    Giới tính: Nam
    Bài gửi
    881

    Reply: Dung danh sach lien ket de bieu dien 1 tap hop

    Nếu vậy, mình khuyến khích bạn nên hiểu cho rõ ràng đã: linked list là gì, cách biểu diễn như thế nào, hình vẽ ra sao,... Mấy cái concept này có hình vẽ là dễ hiểu nhất.

  5. #5
    Ðến Từ
    TP. Hồ Chí Minh
    Thành Viên Thứ: 353076
    Giới tính: Nam
    Bài gửi
    45

    Reply: Dung danh sach lien ket de bieu dien 1 tap hop

    ban co the cho mh biet cach lam bai toan tren khomg, mh se tham khao sach them.

  6. #6
    Ðến Từ
    TP. Hồ Chí Minh
    Thành Viên Thứ: 56897
    Giới tính: Nam
    Bài gửi
    881

    Reply: Dung danh sach lien ket de bieu dien 1 tap hop

    Bài này là về kỹ thuật lập trình nhiều hơn đó bạn. Câu 1 đại khái thế này nhé (chưa test kỹ). Mỗi một số x muốn đưa vào tập hợp thì cần kiểm tra xem nó đã có chưa; nếu chưa mới đc đưa vào.
    Mã:
    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;
    }

  7. Đã cảm ơn tengiday:


  8. #7
    Ðến Từ
    TP. Hồ Chí Minh
    Thành Viên Thứ: 353076
    Giới tính: Nam
    Bài gửi
    45

    Reply: Dung danh sach lien ket de bieu dien 1 tap hop

    loại 1 phần tử trong tập hợp, là kiểm tra trong tập hợp có chứa nó hay không; nếu có loại nó ra khỏi linked list đúng k bạn .

  9. #8
    Ðến Từ
    TP. Hồ Chí Minh
    Thành Viên Thứ: 56897
    Giới tính: Nam
    Bài gửi
    881

    Reply: Dung danh sach lien ket de bieu dien 1 tap hop

    Trích Nguyên văn bởi Organvn Xem bài viết
    loại 1 phần tử trong tập hợp, là kiểm tra trong tập hợp có chứa nó hay không; nếu có loại nó ra khỏi linked list đúng k bạn .
    Đúng rồi. Đầu tiên bạn phải xem có tồn tại phần tử đó hay không, nếu có thì xóa cái node đó ra khỏi list.

  10. #9
    Ðến Từ
    TP. Hồ Chí Minh
    Thành Viên Thứ: 353076
    Giới tính: Nam
    Bài gửi
    45

    Reply: Dung danh sach lien ket de bieu dien 1 tap hop

    Mã:
    #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");
    }
    nho ban xem va chinh giup minh code khuc tinh gia tri da thuc voi, mh lam bi sai. cam on ban nhieu

  11. #10
    Ðến Từ
    TP. Hồ Chí Minh
    Thành Viên Thứ: 56897
    Giới tính: Nam
    Bài gửi
    881

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

    Về tính giá trị của đa thức thì mình thấy đa thức l chưa đc khởi tạo. Mình thử đoạn code đơn giản này thì thấy nó đúng:
    Mã:
    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.

  12. Đã cảm ơn tengiday:


  13. #11
    Ðến Từ
    Hà Nội
    Thành Viên Thứ: 297085
    Bài gửi
    858

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

    Bài này thuộc dạng cơ bản đặc trưng của dslk rồi bạn nên tìm hiểu kiến thức trước sẽ hiểu ngay thôi. Nhưng bài khó rồi hãy hỏi thánh tengiday
    I have nothing...

  14. Đã cảm ơn Ihavenothing: