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

Đề tài: Đồ thị: Cài đặt bằng danh sách liên kết + DFT + BFT

  1. #1
    Ngày gia nhập
    06 2007
    Nơi ở
    SN06 - 70 Trương Định - HBT - HN
    Bài viết
    36

    Mặc định Đồ thị: Cài đặt bằng danh sách liên kết + DFT + BFT

    Đây là bài đồ thị, được mình cài đặt bằng danh sách liên kết.
    Có hai hàm duyệt đồ thị bằng phương pháp đệ qui:
    -DFT (Depth First Traverse): Duyệt theo chiều sâu
    -BFT (Breadth First Traverse): Duyệt theo chiều rộng
    Code viết bằng borland C++.
    C++ Code:
    1. #include <iostream.h>
    2. #include <conio.h>
    3. #include <stdio.h>
    4. #include <stdlib.h>
    5.  
    6. #define max_member 100
    7. class graph;
    8. class list;
    9. class node
    10. {
    11.         int data; // chua vi tri cua dinh lien ket thu data tren mang cac danh sach head
    12.         node *next;
    13.     public:
    14.         node(int a=-1)
    15.             {
    16.                 data = a;
    17.                 next = 0;
    18.             }
    19.         friend class list;
    20.         friend class graph;
    21. };
    22.  
    23. class list
    24. {
    25.         node *head;
    26.     public:
    27.         list()
    28.             {
    29.                 head = 0;
    30.             }
    31.         ~list()
    32.             {
    33.                 while(head)
    34.                     {
    35.                         node *temp= head;
    36.                         head = head->next;
    37.                         delete temp;
    38.                     }
    39.             }
    40.         bool set_contact(int a)
    41.             {
    42.                 node *p= new node(a);
    43.                 if(!p)
    44.                     return false;
    45.                 if(!head)
    46.                     head = p;
    47.                 else
    48.                     {
    49.                         node *temp = head;
    50.                         while(temp->next&&temp->next->data>a)
    51.                             {
    52.                                 if(temp->data == a)
    53.                                     return false;
    54.                                 temp = temp->next;
    55.                             }
    56.                         p->next = temp->next;
    57.                         temp->next = p;
    58.                     }
    59.                 return true;
    60.             }
    61.         bool remove_contact(int a)
    62.             {
    63.                 if(head)
    64.                 {
    65.                     node *temp = head;
    66.                     if(temp->data == a)
    67.                         {
    68.                             head = head->next;
    69.                             delete temp;
    70.                             return true;
    71.                         }
    72.                     else
    73.                         while(temp)
    74.                             {
    75.                                 if(temp->next->data ==a)
    76.                                     {
    77.                                         node *p = temp->next;
    78.                                         temp = temp->next->next;
    79.                                         delete p;
    80.                                         return true;
    81.                                     }
    82.                                 temp = temp->next;
    83.                             }
    84.                 }
    85.                 return false;
    86.             }
    87.         void view_contact()const
    88.             {
    89.                 if(head)
    90.                 {
    91.                     node *temp = head->next;
    92.                     cout<<"Dinh : "<<(head->data+1)<<"\t";
    93.                     while(temp)
    94.                     {
    95.                         cout<<(head->data+1)<<"-"<<(temp->data+1)<<"     ";
    96.                         temp = temp->next;
    97.                     }
    98.                     cout<<endl;
    99.                 }
    100.             }
    101.         friend class graph;
    102.         list operator = (const list &a)
    103.             {
    104.                 if(head)
    105.                 {
    106.                     while(head)
    107.                     {
    108.                         node *temp= head;
    109.                         head = head->next;
    110.                         delete temp;
    111.                     }
    112.                     head = 0;
    113.                 }
    114.                 if(a.head)
    115.                 {
    116.                     head = new node(a.head->data);
    117.                     node *p =head, *q=a.head->next;
    118.                     while(q)
    119.                         {
    120.                             p->next = new node(q->data);
    121.                             p=p->next;
    122.                             q=q->next;
    123.                         }
    124.                 }
    125.                 return *this;
    126.             }
    127. };
    128.  
    129. class graph
    130. {
    131.         list rank[max_member];
    132.         int member;
    133.     public:
    134.         graph()
    135.             {
    136.                 member = -1;
    137.             }
    138.         void set_member(int a)
    139.             {
    140.                 member = a;
    141.                 for(int i=0;i<a;i++)
    142.                     {
    143.                         rank[i].head= new node(i);
    144.                     }
    145.             }
    146.         void insert_member()
    147.             {
    148.                 member++;
    149.             }
    150.         void remove_member(int a)
    151.             {
    152.             a--;
    153.                 if(a<=member&&a>=0)
    154.                 {
    155.                     for(int i=0;i<=member;i++)
    156.                         if(i!=a)
    157.                             rank[i].remove_contact(a);
    158.                     for(int i=a;i<member;i++)
    159.                         rank[i]=rank[i+1];
    160.                     rank[member].~list();
    161.                     member--;
    162.                 }
    163.             }
    164.         void add_contact(int a,int b)
    165.             {
    166.             a--;b--;
    167.                 if(a<=member&&a>=0)
    168.                 {
    169.                     rank[a].set_contact(b);
    170.                 }
    171.             }
    172.         void remove_contact(int a,int b)
    173.             {
    174.             a--;b--;
    175.                 if(a<=member&&a>=0)
    176.                 {
    177.                     rank[a].remove_contact(b);
    178.                 }
    179.             }
    180.         void view_graph()const
    181.             {
    182.                 if(member>=0)
    183.                     {
    184.                         for(int i = 0;i<=member;i++)
    185.                         {                      
    186.                             rank[i].view_contact();
    187.                         }
    188.                     }
    189.             }
    190.         void dft_graph()const
    191.             {
    192.                 bool check[max_member];
    193.                 for(int i=0;i<=member;i++)
    194.                     check[i]=false;
    195.                 for(int i=0;i<member;i++)
    196.                     {
    197.                         if(!check[i])
    198.                             {
    199.                                 if(i<member&&i>0)cout<<" -> ";cout<<(i+1);
    200.                                 dft_func(i,check);
    201.                             }
    202.                     }
    203.             }
    204.         void dft_func(int i,bool check[])const
    205.             {
    206.                 check[i] = true;
    207.                 node *temp = 0;
    208.                 if(rank[i].head->next)
    209.                     temp = rank[i].head->next;
    210.                 else
    211.                     return;
    212.                 while(temp)
    213.                     {
    214.                         if(!check[temp->data])
    215.                             {
    216.                                 cout<<" -> "<<(temp->data+1);
    217.                                 dft_func(temp->data,check);
    218.                             }
    219.                         temp = temp->next;
    220.                     }
    221.             }
    222.         void bft_graph()const
    223.             {
    224.                 bool check[max_member],read[max_member];
    225.                 for(int i=0;i<=member;i++)
    226.                     check[i]=read[i]=false;
    227.                 for(int i=0;i<member;i++)
    228.                     {
    229.                         if(!check[i])
    230.                             {
    231.                                 if(i<member&&i>0)cout<<" -> ";cout<<(i+1);
    232.                                 check[i]=true;
    233.                                 node *temp = rank[i].head->next;
    234.                                 while(temp)
    235.                                     {
    236.                                         cout<<" -> "<<(temp->data+1);
    237.                                         read[temp->data]=true;
    238.                                         temp = temp->next;
    239.                                     }
    240.                                 temp = rank[i].head->next;
    241.                                 while(temp)
    242.                                     {
    243.                                         if(!check[temp->data])
    244.                                             bft_func(temp->data,check,read);
    245.  
    246.                                         temp=temp->next;
    247.                                     }
    248.                             }
    249.                     }
    250.             }
    251.         void bft_func(int i,bool check[],bool read[])const
    252.             {
    253.                 check[i] = true;
    254.                 node *temp = 0;        
    255.                 if(rank[i].head->next)
    256.                     temp = rank[i].head->next;
    257.                 else
    258.                     return;
    259.                 while(temp)
    260.                     {
    261.                         if(!check[temp->data]&&!read[temp->data])
    262.                             {
    263.                                 cout<<" -> "<<(temp->data+1);
    264.                                 bft_func(temp->data,check,read);
    265.                             }
    266.                         temp = temp->next;
    267.                     }
    268.             }
    269. };
    270.  
    271. void main()
    272. {
    273.     graph a;
    274.     int n,m;
    275.     /*cout<<"\n Moi nhap so dinh cua do thi: ";cin>>n;
    276.     a.set_member(n);
    277.     cout<<"\n Nhap vao -1 de thoat.\n";
    278.     while(1)
    279.     {
    280.         cout<<"\n Nhap vao dinh xet moi quan he:";cin>>n;
    281.         cout<<" Co quan he voi dinh: "; cin>>m;
    282.         if(n<0||m<0)
    283.             break;
    284.         else
    285.             a.add_contact(n,m);
    286.     }
    287.     clrscr();*/
    288.     a.set_member(7);
    289.     a.add_contact(1,5);
    290.     a.add_contact(1,2);
    291.     a.add_contact(2,5);
    292.     a.add_contact(2,4);
    293.     a.add_contact(5,3);
    294.     a.add_contact(4,3);
    295.     a.add_contact(5,7);
    296.     a.add_contact(5,6);
    297.     a.add_contact(7,6);
    298.     a.add_contact(6,3);
    299.    a.add_contact(3,4);
    300.    a.add_contact(5,2);
    301.     a.add_contact(5,4);
    302.    a.add_contact(4,2);
    303.    a.add_contact(1,7);
    304. /*  a.set_member(5);
    305.     a.add_contact(1,2);
    306.     a.add_contact(1,4);
    307.     a.add_contact(1,5);
    308.     a.add_contact(2,1);
    309.     a.add_contact(2,3);
    310.     a.add_contact(2,4);
    311.     a.add_contact(2,5);
    312.     a.add_contact(3,2);
    313.     a.add_contact(3,4);
    314.     a.add_contact(4,1);
    315.     a.add_contact(4,2);
    316.     a.add_contact(4,3);
    317.     a.add_contact(4,5);
    318.     a.add_contact(5,1);
    319.     a.add_contact(5,2);
    320.     a.add_contact(5,4);*/
    321.    
    322.     cout<<"\n Cac moi quan he tren do thi vua nhap la: \n\n";
    323.     a.view_graph();
    324.     cout<<"\n\n Duyet DFT \n";
    325.     a.dft_graph();
    326.     cout<<"\n\n Duyet BFT \n";
    327.     a.bft_graph();
    328.     getch();
    329. }

    Và ví dụ kèm theo ( +code)
    Attached Files Attached Files


    =====================================
    XWAYSTYLE ---------> Brings joy to milions.....
    Intel(R) Pentium 4(R) 2.8GHz Main IntelD845Pemy (Socket 478) RAM 1024Mb VGAFX5200 128Mb 128Bit HDD Maxtor 160Gb PATA Sound Blaster live 5.1 Gamer

    Windows Vista Ultimate Sp1 (activated)
    Rating : 2.5 Mark
    Theme: Windows Aero (very nice!)

  2. #2
    Ngày gia nhập
    10 2008
    Bài viết
    1

    Em đang làm bài tập này , lên mạng kiếm thử thì tìm dc. kết quả này ^^ , anh ơi , anh vui lòng giải thích thêm để em hiểu về các hàm với :"> thanks anh !

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

    hiểu rồi không hỏi nữa nên em edit lại ^^
    Đã được chỉnh sửa lần cuối bởi teenylove : 26-11-2008 lúc 10:14 PM. Lý do: hiểu rồi không hỏi nữa ^^

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

  1. Hướng dẫn Biểu diễn thích hợp bằng danh sách liên kết đơn hoặc danh sách liên kết kép
    Gửi bởi maitrung trong diễn đàn Thủ thuật, Tutorials CTDL & Giải thuật
    Trả lời: 3
    Bài viết cuối: 04-08-2012, 08:01 PM
  2. Cấu trúc dữ liệu Cách tạo danh sách liên kết mới từ danh sách liên kết đã cho 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: 2
    Bài viết cuối: 30-11-2011, 04:43 PM
  3. Nhập và xuất danh sách liên kết lồng danh sách liên kết?
    Gửi bởi nvluong_it 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: 22-04-2011, 11:30 AM
  4. Lập trình C Danh sách liên kết - Xử lý danh sách liên kết trong lập trình C
    Gửi bởi phucduan 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: 08-11-2010, 10:25 PM
  5. Danh sách liên kết, code nhập danh sách sinh viên có lỗi làm sao sửa?
    Gửi bởi acmilan 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: 10-04-2009, 08:24 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