Từ 1 tới 3 trên tổng số 3 kết quả

Đề tài: Topological sort | Cài đặt trên C++ như thế nào?

  1. #1
    Ngày gia nhập
    12 2007
    Bài viết
    3

    Mặc định Topological sort | Cài đặt trên C++ như thế nào?

    Mình học môn cấu trúc dữ liệu và giải thuật ở trường có đụng đến vấn đề Topological sort ở trong phần đồ thị. Thực ra thì tư tưởng của nó không có gì quá phức tạp nhưng cái khó là làm thế nào viết được một chương trình C để demo cái kiểu sort này. Có anh em nào đã từng làm qua cái này hoặc có ý kiến gì thì làm ơn đóng góp (nếu có source code thì càng hay),

  2. #2
    Ngày gia nhập
    10 2006
    Nơi ở
    In Your Bugs
    Bài viết
    823

    Ý cậu là thế nào nhỉ ? Có phải là viết 1 chương trình giúp người học về mạng topo ko ?

  3. #3
    Ngày gia nhập
    07 2010
    Bài viết
    8

    Wink Lời giải bài toán Topo

    Mình mới "săn" được đoạn code Topo Logical sorting này,share cho bạn:
    Để chạy được file này cần có file note pad để trong thư mục Visual C của bạn với input như sau:
    1 2
    2 4
    2 10
    4 8
    6 3
    1 3
    3 5
    5 8
    7 5
    7 9
    9 4
    9 10

    #include "iostream"
    #include "fstream"
    #include "sstream"
    #include "conio.h"
    using namespace std;

    typedef struct leader* lref;
    typedef struct trailer* tref;
    struct leader{
    int key;
    int count;
    lref next;
    tref trail;
    };
    struct trailer{
    lref id;
    tref next;
    };

    //prototypes
    int readData(lref&, lref&, int&);
    void topoSort(lref&, lref&, int&);

    int main(){
    lref head = NULL, tail = NULL;
    int z;
    if(readData(head, tail, z))
    topoSort(head, tail, z);
    else
    cout << "Ko doc duoc file topo.inp!" << endl;
    _getch();
    }

    lref addList(lref head, lref &tail, int w, int &z){
    lref h = head;
    tail->key = w;
    while(h->key != w) h = h->next;
    if(h==tail){
    tail = new leader;
    z++;
    h->count = 0;
    h->trail = NULL;
    h->next = tail;
    }
    return h;
    }

    int readData(lref &head, lref &tail, int &z){
    ifstream f;
    int x, y;
    lref p, q;
    tref t;

    head = new leader;
    tail = head;
    z = 0;
    f.open("topo.inp");
    if(f.is_open()){
    f >> x;
    while(!(f.eof())){
    f >> y;

    // tạo 2 leader
    p = addList(head, tail, x, z);
    q = addList(head, tail, y, z);

    // thêm trailer cho p
    t = new trailer;
    t->id = q;
    t->next = p->trail;
    p->trail = t;
    q->count ++;
    f >> x;
    }
    return 1;
    }
    return 0;
    }

    void topoSort(lref &head, lref &tail, int &z){
    lref p, q;
    tref t;

    p = head;
    head = NULL;
    while(p!=tail){
    q = p;
    p = p->next;
    if(q->count == 0){
    q->next = head;
    head = q;
    }
    }

    q = head;
    while(q){
    cout << q->key << endl;
    --z;
    t = q->trail;
    q = q->next;
    while(t){
    p = t->id;
    p->count --;
    if(p->count == 0){
    p->next = q;
    q = p;
    }
    t = t->next;
    }
    }
    if(z) cout << "\n Khong the sap topo tren day nay!\n";
    getch();
    }
    Giải thích:VD:1 2 tức là 1 liên thông với 2(nhưng chưa chắc có đường đi từ 2 đến 1).Nhớ kĩ đây là ma trận kề của đồ thị liên thông không có trọng số có hướng Còn của đồ thị có trọng số thì tui chưa tìm ra.Có bác nào cao tay thì viết nốt code cho đồ thị có trọng số nhé( nhớ giải thích ma trận trọng số nhé
    Kết quả sẽ là 7 ->9->1->2->4->6->3->5->8->10.
    Đã được chỉnh sửa lần cuối bởi huydaibang : 26-07-2010 lúc 03:47 PM.

Các đề tài tương tự

  1. Thuật toán C++ Ưu nhược điểm các kiểu sort Interchange sort, Selection sort, Insertion sort, Sharke sort , Quick sort, Heap sort
    Gửi bởi duythanhnguyen trong diễn đàn Thắc mắc CTDL & Giải thuật
    Trả lời: 7
    Bài viết cuối: 23-09-2013, 01:16 AM
  2. Thuật toán C++ Bubble Sort trên danh sách liên kết đơn thì xử lý như thế nào?
    Gửi bởi giacmo1612 trong diễn đàn Thắc mắc CTDL & Giải thuật
    Trả lời: 12
    Bài viết cuối: 16-10-2012, 08:52 PM
  3. Lập trình C Cách hoạt động của thuật toán Selection Sort và Bubble Sort như thế nào?
    Gửi bởi kuin0903 trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 4
    Bài viết cuối: 26-07-2011, 10:39 AM
  4. Các thuật toán sắp xếp mảng | Bubble sort, Shak sort, Insertion sort, Selection, ...
    Gửi bởi kids trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 2
    Bài viết cuối: 11-04-2009, 10:05 PM
  5. Thuật toán Flash sort, Shear Sort cụ thể như thế nào?
    Gửi bởi tun_tun trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 1
    Bài viết cuối: 16-05-2008, 01:43 PM

Quyền hạn của bạn

  • Bạn không thể gửi đề tài mới
  • Bạn không thể gửi bài trả lời
  • Bạn không thể gửi các đính kèm
  • Bạn không thể chỉnh sửa bài viết của bạn