Trang 1 trên tổng số 2 12 Cuối cùngCuối cùng
Từ 1 tới 10 trên tổng số 13 kết quả

Đề tài: Bubble Sort trên danh sách liên kết đơn thì xử lý như thế nào?

  1. #1
    Ngày gia nhập
    03 2011
    Bài viết
    25

    Mặc định Bubble Sort trên danh sách liên kết đơn thì xử lý như thế nào?

    mình có bài tập về danh sách liên kết đơn. Yêu cầu : sắp xếp nổi bọt ( bubble sort ) tăng dần các số nguyên...các bạn chỉ giúp mình nha

    Còn đây là code mình viết trên mảng còn danh sách liên kết thì chưa làm được
    Code:
    void sapxepnoibot(int a[],int n)
    {
    	for(int i=0;i<n;i++)
    	{
    		for(int j=n-1;j>i;j--)
    		{
    			if(a[j] < a[j-1])
    			{
    				int t=a[j];
    				a[j]=a[j-1];
    				a[j-1]=t;
    			}
    		}
    	}
    }
    mình định nghĩa cấu trúc như thế này :
    Code:
    struct node
    {
          node *next;
          int data;
    };

  2. #2
    Ngày gia nhập
    01 2011
    Nơi ở
    -Mountain-
    Bài viết
    768

    Tham khảo cái này xem nhé

    C++ Code:
    1. void sort (list& first)
    2. {
    3.     list dt;
    4.     int data;
    5.     bool cbit = false;
    6.     while (!cbit)
    7.     {
    8.         cbit = true;
    9.         for (dt = first; dt->next != NULL; dt = dt->next)
    10.             if (dt->data > dt->next->data)
    11.             {
    12.                 data = dt->next->data;
    13.                 dt->next->data = dt->data;
    14.                 dt->data =  data;
    15.                 cbit = false;
    16.             }
    17.     }
    18. }
    Hướng dẫn C++: https://www.youtube.com/watch?v=BwLodoQdoY4&list=PL1c9Uxlo-mplJDRGdONNupgo5OCBTyGGn

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

    Cứ coi danh sach như là 1 mảng, mà truy xuất tuần tự các phần tử thông qua next.
    ví dụ:
    for(int i=0;i<n;i++)
    thì sẽ tương tương ứng
    for (dt = first; dt!= NULL; dt = dt->next)

    Code:
    void sort (list& first)
    {
        list dt;
        list dt2;
        int data;
      
            for (dt = first; dt->next != NULL; dt = dt->next)
              for(dt2=dt->next; d2!=NULL; d2 = d2->next)
                if (dt->data > d2->data)
                {
                    data = dt->data;
                    dt->data = dt2->data;
                    dt2->data =  data;
                }
    }
    Đã được chỉnh sửa lần cuối bởi tungt84 : 22-11-2011 lúc 10:35 AM.

  4. #4
    Ngày gia nhập
    03 2011
    Bài viết
    25

    tks 2 bạn nhiều nha...mình sẽ code lại

  5. #5
    Ngày gia nhập
    10 2011
    Bài viết
    8

    Trích dẫn Nguyên bản được gửi bởi tungt84 Xem bài viết
    Cứ coi danh sach như là 1 mảng, mà truy xuất tuần tự các phần tử thông qua next.
    ví dụ:
    for(int i=0;i<n;i++)
    thì sẽ tương tương ứng
    for (dt = first; dt!= NULL; dt = dt->next)

    Code:
    void sort (list& first)
    {
        list dt;
        list dt2;
        int data;
      
            for (dt = first; dt->next != NULL; dt = dt->next)
              for(dt2=dt->next; d2!=NULL; d2 = d2->next)
                if (dt->data > d2->data)
                {
                    data = dt->data;
                    dt->data = dt2->data;
                    dt2->data =  data;
                }
    }
    Code sắp xếp của bạn hình như là Interchange Sort mà phải không?
    Bạn có thể giúp mình code sắp xếp bằng Bubble Sort được không! Cảm ơn bạn trước nha!

  6. #6
    Ngày gia nhập
    12 2010
    Nơi ở
    Cần thơ
    Bài viết
    273

    Mặc định Bubble Sort trên danh sách liên kết đơn thì xử lý như thế nào?

    Trích dẫn Nguyên bản được gửi bởi nhuvayday Xem bài viết
    Code sắp xếp của bạn hình như là Interchange Sort mà phải không?
    Bạn có thể giúp mình code sắp xếp bằng Bubble Sort được không! Cảm ơn bạn trước nha!
    Theo bạn đúng khuôn của bouble sort thì khó lắm :| ... tại vì bouble bắt đầu từ cuối rồi vọt ngược lên...mà dslkđ thì đâu cho phép chạy ngược lại nên chắc phải chuyển thành dslk kép hoặc thêm 1 mảng phụ lưu địa chỉ rồi chép qua quá :|
    Ai bất tài, tôi nhìn hoài chẳng thấy,
    Đi khắp phòng tôi lấy 1 tấm gương,
    Khẽ đặt lên một góc phía bức tường,
    Nhìn vào đó, tôi tận tường kẻ đó.

  7. #7
    Ngày gia nhập
    04 2012
    Nơi ở
    Bình Định (Đang học ở tphcm)
    Bài viết
    35

    Đây là "bubble sort" mình tự code (mình còn gà lắm) mong các bạn góp ý!!! thanks nhìu
    C Code:
    1. void Sort(Node* &pH)
    2. {
    3.     Node *ph = pH;
    4.     Node *pt = NULL;
    5.     int temp;
    6.     while(pt!=pH)
    7.     {
    8.         while(ph->pNext!=pt)
    9.         {
    10.             if(ph->data>ph->pNext->data)
    11.             {
    12.                 temp = ph->pNext->data;
    13.                 ph->pNext->data = ph->data;
    14.                 ph->data = temp;
    15.             }
    16.             ph = ph->pNext;
    17.         }
    18.         pt = ph;
    19.         ph = pH;
    20.     }
    21. }

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

    C++ Code:
    1. void BubbleSort(LIST &l)
    2. {
    3.  NODE *k1=l.pHead;
    4.  NODE *k2;
    5.  for(NODE *p=l.pHead;p->pNext!=NULL;p=p->pNext)
    6.  {
    7.   while(k1->pNext!=NULL)
    8.   {
    9.    k2=k1;
    10.    k1=k1->pNext;
    11.    if(k1->c < k2->c)
    12.     hoanvi(k1,k2);
    13.   }
    14.   k2=l.pHead;
    15.   k1=l.pHead;
    16.  }
    17. }
    tham khảo nhá...

  9. #9
    Ngày gia nhập
    08 2011
    Bài viết
    117

    Phác cái code ra thế này chưa đúng cú pháp thì tự sửa :

    C Code:
    1. void sort( struct node *root)
    2. {
    3.     struct node *first,*second;
    4.     int temp;
    5.     first= root;
    6.     while(first!=NULL)
    7.     {
    8.         second=first->next;
    9.         while(second!=NULL)
    10.         {
    11.             if(first->data < second->data)
    12.             {
    13.                 temp=first->data;
    14.                 first->data=second->data;
    15.                 second->data=temp;
    16.             }
    17.             second=second->next;
    18.         }
    19.  
    20.         first=first->next;
    21.     }
    22. }

  10. #10
    Ngày gia nhập
    04 2012
    Nơi ở
    Bình Định (Đang học ở tphcm)
    Bài viết
    35

    Trích dẫn Nguyên bản được gửi bởi CIMinuv Xem bài viết
    Phác cái code ra thế này chưa đúng cú pháp thì tự sửa :

    C Code:
    1. void sort( struct node *root)
    2. {
    3.     struct node *first,*second;
    4.     int temp;
    5.     first= root;
    6.     while(first!=NULL)
    7.     {
    8.         second=first->next;
    9.         while(second!=NULL)
    10.         {
    11.             if(first->data < second->data)
    12.             {
    13.                 temp=first->data;
    14.                 first->data=second->data;
    15.                 second->data=temp;
    16.             }
    17.             second=second->next;
    18.         }
    19.  
    20.         first=first->next;
    21.     }
    22. }
    Cái này hình như đâu phải là "bubble sort",hình như nó chỉ là sắp xếp bình thường thôi mà!


    Trích dẫn Nguyên bản được gửi bởi utkung_91 Xem bài viết
    C++ Code:
    1. void BubbleSort(LIST &l)
    2. {
    3.  NODE *k1=l.pHead;
    4.  NODE *k2;
    5.  for(NODE *p=l.pHead;p->pNext!=NULL;p=p->pNext)
    6.  {
    7.   while(k1->pNext!=NULL)
    8.   {
    9.    k2=k1;
    10.    k1=k1->pNext;
    11.    if(k1->c < k2->c)
    12.     hoanvi(k1,k2);
    13.   }
    14.   k2=l.pHead;
    15.   k1=l.pHead;
    16.  }
    17. }
    tham khảo nhá...
    Còn cái này mình không biết có được cho là "bubble sort" hay không, nhưng theo mình hình như nó không thể hiên hết hiệu quả của "bubble sort" vì trong môi lần p tăng thì while có n-1 lần lặp thế thì nó là (n-1)*(n-1) mất rồi còn theo mình biết thì "bubble sort" thì chỉ: (n-1) + (n - 2) + ... + 3 + 2 + 1

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

  1. 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
  2. Bubble sort trong danh sach lien ket don
    Gửi bởi kienchochethahaha trong diễn đàn Nhập môn lập trình C/C++
    Trả lời: 1
    Bài viết cuối: 18-07-2010, 08:44 AM
  3. Bubble sort trong danh sach lien ket doi
    Gửi bởi jahuang trong diễn đàn Nhập môn lập trình C/C++
    Trả lời: 5
    Bài viết cuối: 17-02-2010, 03:42 PM
  4. Cài đặt thuật toán sắp xếp nổi bọt bằng đồ họa trên C ( Bubble Sort)
    Gửi bởi 1412007 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: 07-05-2009, 11:38 PM
  5. 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

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