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

Đề tài: Trộn 2 danh sách liên kết có thứ tự thành 1 danh sách liên kết có thứ tự

  1. #1
    Ngày gia nhập
    01 2010
    Bài viết
    7

    Angry Trộn 2 danh sách liên kết có thứ tự thành 1 danh sách liên kết có thứ tự

    Trộn 2 danh sách liên kết có thứ tự thành 1 danh sách liên kết có thứ tự như thế nào?
    -----Học, học nữa, học mãi. Đuổi thì nghỉ!-----------

  2. #2
    Ngày gia nhập
    09 2009
    Nơi ở
    205Bee
    Bài viết
    231

    bạn làm trên mảng thế nào thì bạn cố gắng làm i như vậy trong danh sách liên kết. Theo mình bạn nối hai dslk lại với nhau dau đó sắp xếp lại. Vậy là ok. Good luck!

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

    vd sau khi em nhập 2 ds có thứ tự, sau đó em phải làm thía nào để duyệt từng phần tử trong 2 ds đó rùi so sánh, nối lại thành 1 ds có thứ tự. Chỉ em các bước cụ thể với
    -----Học, học nữa, học mãi. Đuổi thì nghỉ!-----------

  4. #4
    Ngày gia nhập
    09 2009
    Nơi ở
    205Bee
    Bài viết
    231

    C++ Code:
    1. #include<iostream>
    2.  
    3. using namespace std;
    4.  
    5.  
    6. struct so
    7. {
    8.     int giatri;
    9.     so *tiep;
    10. };
    11.  
    12. void nhap(int n, so *&dau)
    13. {
    14.     int i, x;
    15.     so *cuoi = new so;
    16.     so *hientai = new so;
    17.     cout << "x1: ";
    18.     cin >> x;
    19.     hientai->giatri = x;
    20.     hientai->tiep = NULL;
    21.     cuoi = dau = hientai;
    22.     for (i = 2; i <= n; i++){
    23.         cout << "x" << i << ": ";
    24.         hientai = new so;
    25.         cin >> hientai->giatri;
    26.         hientai->tiep = NULL;
    27.         cuoi->tiep = hientai;
    28.         cuoi = hientai;
    29.     }
    30. }
    31.  
    32. so* nhan_giatri(int i, so *dau){
    33.     so *p = dau;
    34.     int k = 1;
    35.     while(k < i){
    36.         k++;
    37.         p = p->tiep;
    38.     }
    39.     return p;
    40. }
    41.  
    42. void nhapgiatri(so *dau, int vitri, int giatri){
    43.     so *p = dau;
    44.     int k = 1;
    45.     while(k < vitri){
    46.         k++;
    47.         p = p->tiep;
    48.     }
    49.     p->giatri = giatri;
    50. }
    51. void gan2dayso(int n1, so *dau1, so* dau2){
    52.     so *p1 = nhan_giatri(n1, dau1);
    53.     p1->tiep = dau2;
    54. }
    55.  
    56. void sapxep(so *dau, int n){
    57.     for (int i = 0; i < n - 1; ++i){
    58.         so *soi = nhan_giatri(i+1, dau);
    59.         for (int j = i + 1; j < n; ++j){
    60.             so *soj = nhan_giatri(j+1, dau);
    61.             if (soi->giatri > soj->giatri){
    62.                 int tg;
    63.                 tg = soi->giatri;
    64.                 nhapgiatri(dau, i+1, soj->giatri);
    65.                 nhapgiatri(dau, j+1, tg);
    66.             }
    67.         }
    68.     }
    69. }
    70.  
    71. void inso(so *dau){
    72.     so *p = dau;
    73.     do{
    74.         cout << p->giatri << ' ';
    75.         p = p->tiep;
    76.     }while(p!=NULL);
    77. }
    78. int main()
    79. {
    80.     int n1, n2;
    81.     so *sodau_day1 = new so, *sodau_day2 = new so;
    82.     cout << "Nhap so phan tu cua day 1";
    83.     cin >> n1;
    84.     nhap(n1, sodau_day1);
    85.     cout << "Nhap so phan tu cua day 2";
    86.     cin >> n2;
    87.     nhap(n2, sodau_day2);
    88.     gan2dayso(n1, sodau_day1, sodau_day2);
    89.     sapxep(sodau_day1, n1+n2);
    90.     inso(sodau_day1);
    91.     free(sodau_day1);
    92.     free(sodau_day2);
    93.     system("pause");
    94. }
    Bạn poka xem thử code mình xem. Rất lộn xộn.bạn có thể nhập 2 dãy số bất kỳ sau đó sẽ có hàm nối hai dslk lại, có 1 hàm sắp xếp.

  5. #5
    Ngày gia nhập
    09 2009
    Bài viết
    240

    Trích dẫn Nguyên bản được gửi bởi poka Xem bài viết
    cái này tổ chức trên danh sách liên kết. em có 2 cái danh sách lk chứa số nguyên có thứ tự, làm sao nối lại thành 1 danh sách có thứ tự?. giúp em đi
    Giải thuật của mình là cho các con trỏ next của chúng thay đổi địa chỉ, nên không cần xin cấp phát thêm bộ nhớ. Lại sử dụng đệ quy nên khá đơn giản, bạn đọc code hiểu liền. Để thuận tiện cho việc test, mình code luôn cả đoạn nhập danh sách. Nhập xong là đã có thứ tự tăng dần rồi đó.
    C++ Code:
    1. #include <stdio.h>
    2.  
    3. struct NODE
    4. {
    5.     int x;
    6.     NODE* next;
    7. };
    8.  
    9. typedef NODE * PNODE;
    10.  
    11. void input(PNODE &ptr)
    12. {
    13.     printf("\nDe ket thuc, nhaptr gia tri 0\n");
    14.     int temp;
    15.     ptr = NULL;
    16.  
    17.     do
    18.         {
    19.             printf("\nx = "); scanf("%d",&temp);
    20.             if(temp)
    21.                 {
    22.                     PNODE q = new NODE;
    23.                     q->x = temp; q->next = NULL;
    24.                     if (ptr==NULL) ptr = q;
    25.                     else
    26.                         if (ptr->x > temp)
    27.                             {
    28.                                 q->next = ptr;
    29.                                 ptr = q;
    30.                             }
    31.                         else
    32.                             if (ptr->next == NULL) ptr->next = q;
    33.                             else
    34.                                 {
    35.                                     PNODE t = ptr;
    36.                                     while (t->next->next != NULL && t->next->x < temp) t = t->next;
    37.                                     if (t->next->x > temp)
    38.                                         {
    39.                                             q->next = t->next;
    40.                                             t->next = q;
    41.                                         }
    42.                                     else
    43.                                         {
    44.                                             q->next = t->next->next;
    45.                                             t->next->next = q;
    46.                                         }
    47.                                 }
    48.                 }
    49.         }   while (temp);
    50. }
    51.  
    52. PNODE merge(PNODE p, PNODE q)
    53. {
    54.     if (p == NULL) return q;
    55.     if (q == NULL) return p;
    56.     if (p->x < q->x)
    57.         {
    58.             p->next = merge(p->next,q);
    59.             return p;
    60.         }
    61.     else return merge(q,p);
    62. }
    63.  
    64. void display(PNODE p)
    65. {
    66.     PNODE q = p;
    67.     printf("\n");
    68.     while (q)
    69.         {
    70.             printf("%d\t",q->x);
    71.             q = q->next;
    72.         }
    73. }
    74.  
    75. void release(PNODE &ptr)
    76. {
    77.     PNODE q;
    78.     while (ptr)
    79.         {
    80.             q = ptr->next;
    81.             delete ptr;
    82.             ptr = q;
    83.         }
    84. }
    85. void main()
    86. {
    87.     PNODE p, q, r;
    88.     input(p);   display(p);
    89.     input(q);   display(q);
    90.     r = merge(p,q);
    91.     display(r);
    92.     release(r);
    93. }

  6. #6
    Ngày gia nhập
    06 2007
    Nơi ở
    C:\WINDOWS\system32\dllcache\
    Bài viết
    3,007

    Mặc định Trộn 2 danh sách liên kết có thứ tự thành 1 danh sách liên kết có thứ tự

    hàm đệ quy của thầy onminh :

    C Code:
    1. PNODE merge(PNODE p, PNODE q)
    2. {
    3.     if (p == NULL) return q; // nếu 1 trong 2 cái bằng NULL thì
    4.     if (q == NULL) return p; // ta sẽ trả lại cái còn lại
    5.                                     // trong quá trình đệ quy, nếu mà việc dịch đi đến NULL cũng có nghĩa là việc ghép đã kết thúc
    6.     if (p->x < q->x) //nếu x của p lớn x của q
    7.         {
    8.                           // thì bỏ qua nút p hiện tại đang xét đi đến nút tiếp theo,
    9.             p->next = merge(p->next,q);         //next tại nút hiện tại == đệ quy
    10.                                                            // đệ quy chỗ này sẽ trả về kết quả của việc so sánh lần tiếp, tại lần đệ quy tiếp, sẽ trả về node
    11.                                                            //  nào có giá trị lớn hơn, như thế sẽ bảo đảm rằng việc trộn chúng luôn giữ chiều hướng tăng giảm của các node
    12.  
    13.  
    14.             return p; // trả về p
    15.         }
    16.     else return merge(q,p);
    17. }

    của mình là ăn cắp ý tưởng của thầy thôi........................................
    Đã được chỉnh sửa lần cuối bởi langman : 12-04-2010 lúc 11:50 PM.
    ^_,^

    Facebook : https://www.facebook.com/langmaninternet

    Bùi Tấn Quang

  7. #7
    Ngày gia nhập
    01 2010
    Bài viết
    7

    thật tình cảm ơn các sư huynh rất nhìu, em học hỏi dc nhìu lắm.
    -----Học, học nữa, học mãi. Đuổi thì nghỉ!-----------

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

    Trích dẫn Nguyên bản được gửi bởi onminh Xem bài viết
    Giải thuật của mình là cho các con trỏ next của chúng thay đổi địa chỉ, nên không cần xin cấp phát thêm bộ nhớ. Lại sử dụng đệ quy nên khá đơn giản, bạn đọc code hiểu liền. Để thuận tiện cho việc test, mình code luôn cả đoạn nhập danh sách. Nhập xong là đã có thứ tự tăng dần rồi đó.
    C++ Code:
    1. #include <stdio.h>
    2.  
    3. struct NODE
    4. {
    5.     int x;
    6.     NODE* next;
    7. };
    8.  
    9. typedef NODE * PNODE;
    10.  
    11. void input(PNODE &ptr)
    12. {
    13.     printf("\nDe ket thuc, nhaptr gia tri 0\n");
    14.     int temp;
    15.     ptr = NULL;
    16.  
    17.     do
    18.         {
    19.             printf("\nx = "); scanf("%d",&temp);
    20.             if(temp)
    21.                 {
    22.                     PNODE q = new NODE;
    23.                     q->x = temp; q->next = NULL;
    24.                     if (ptr==NULL) ptr = q;
    25.                     else
    26.                         if (ptr->x > temp)
    27.                             {
    28.                                 q->next = ptr;
    29.                                 ptr = q;
    30.                             }
    31.                         else
    32.                             if (ptr->next == NULL) ptr->next = q;
    33.                             else
    34.                                 {
    35.                                     PNODE t = ptr;
    36.                                     while (t->next->next != NULL && t->next->x < temp) t = t->next;
    37.                                     if (t->next->x > temp)
    38.                                         {
    39.                                             q->next = t->next;
    40.                                             t->next = q;
    41.                                         }
    42.                                     else
    43.                                         {
    44.                                             q->next = t->next->next;
    45.                                             t->next->next = q;
    46.                                         }
    47.                                 }
    48.                 }
    49.         }   while (temp);
    50. }
    51.  
    52. PNODE merge(PNODE p, PNODE q)
    53. {
    54.     if (p == NULL) return q;
    55.     if (q == NULL) return p;
    56.     if (p->x < q->x)
    57.         {
    58.             p->next = merge(p->next,q);
    59.             return p;
    60.         }
    61.     else return merge(q,p);
    62. }
    63.  
    64. void display(PNODE p)
    65. {
    66.     PNODE q = p;
    67.     printf("\n");
    68.     while (q)
    69.         {
    70.             printf("%d\t",q->x);
    71.             q = q->next;
    72.         }
    73. }
    74.  
    75. void release(PNODE &ptr)
    76. {
    77.     PNODE q;
    78.     while (ptr)
    79.         {
    80.             q = ptr->next;
    81.             delete ptr;
    82.             ptr = q;
    83.         }
    84. }
    85. void main()
    86. {
    87.     PNODE p, q, r;
    88.     input(p);   display(p);
    89.     input(q);   display(q);
    90.     r = merge(p,q);
    91.     display(r);
    92.     release(r);
    93. }
    May quá tìm được cái thread này, mình là Designer ko phải Coder nhưng vẫn phải học lập trình ở trường, hôm nọ thầy giáo giao cho làm bài như của chủ thớt nên cũng muốn hỏi chút là bài của thầy onminh mình chạy bài này thì ok nhưng mà chỉ thấy mỗi nhập dãy số sau đó sắp xếp và in ra có thứ tự chứ ko thấy nhập 2 dãy sau đó sắp xếp, gộp lại rồi in ra có thứ tự như của chủ thread, mong thầy onminh có thể giải đáp và giúp mình được ko vậy, thanks trước.

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

Tags của đề tài này

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