Trang 1 trên tổng số 3 123 Cuối cùngCuối cùng
Từ 1 tới 10 trên tổng số 26 kết quả

Đề tài: Cài đặt cấu trúc dữ liệu cây kiểu con trỏ

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

    Mặc định Cài đặt cấu trúc dữ liệu cây kiểu con trỏ

    Bài này chắt có nhiều người làm rùi. Mem nào biết rùi thì củng xem giúp mình để đóng góp ý kiến nha.
    Cây là một tập hợp các phần tử, mổi phần tử mình gọi là 1 node nhé. Trong đó nó có 1 node gốc, từ node gốc, nó phân nhánh ra các node con, các node con lại có thể tiếp tục phân nhánh ra nữa.
    Một node phân nhánh từ node cấp trên nó, node cấp trên nó gọi là node cha.

    Một node con có thể xác định được cha của nó.
    Một node cha có thể biết được các con của mình.

    Ý tưởng:
    Node cha trỏ tới con trái nhất trong danh sách các con của nó. Mổi node con thì luôn trỏ về cha và anh em ruột phải của nó.
    Xóa 1 node:
    - Nếu node cần xóa là con trái nhất của node cha, ta cho node cha của nó trỏ đến anh em phải của node cần xóa (cha bỏ nó)
    - Nếu node cần xóa không phải là con trái của nó ta cho anh em trái của nó trỏ đến anh em phải của nó (anh em bỏ nó).
    Như vậy khi duyệt cây ta sẻ không thấy nó.

    Vì đây là cây bất kì nên ta có thể xây dựng cấu trúc dữ liệu như sau

    C Code:
    1. #include<stdio.h>
    2. #include<conio.h>
    3. #include<malloc.h>
    4. #include<iostream>
    5. using namespace std;
    6. //struct RECORD dùng để lưu trữ thông tin các trường của một node
    7. struct RECORD{
    8.     RECORD *PARENT;           //tro den node cha
    9.     RECORD *RIGHT_NEXT;       //tro den node anh em phai
    10.     RECORD *LEFTMOST_CHILD;   //tro den con trai nhat
    11.     int LABEL;
    12. };
    13. //Khai báo con trỏ node để ta có thể trỏ tới các node khác.
    14. typedef RECORD* NODE;
    15. //Khai báo con trỏ cây, thật ra tree củng là 1 con trỏ node dùng để tạo node root.
    16. typedef NODE TREE;
    17. //tao cay
    18. void MAKENULL_TREE(TREE &ROOT){
    19.     ROOT=(RECORD*)malloc(sizeof(RECORD));
    20.     ROOT->PARENT=NULL;
    21.     ROOT->RIGHT_NEXT=NULL;
    22.     ROOT->LEFTMOST_CHILD=NULL;
    23.     ROOT->LABEL=0;
    24. }
    25. //them mot node vao cay
    26. void INSERT_NODE(int label,NODE N,TREE &T){
    27.     NODE L=(RECORD*)malloc(sizeof(RECORD));
    28.     L->LABEL=label;
    29.     L->PARENT=N;
    30.     //neu node cha la node la thi
    31.     if(N->LEFTMOST_CHILD==NULL){
    32.         L->RIGHT_NEXT=NULL;
    33.         L->LEFTMOST_CHILD=NULL;
    34.         N->LEFTMOST_CHILD=L;
    35.     }
    36.     //nguoc lai cha khong phai la node la thi
    37.    
    38.     else{
    39.         NODE temp=N->LEFTMOST_CHILD;
    40.         while(temp->RIGHT_NEXT!=NULL){
    41.             temp=temp->RIGHT_NEXT;
    42.         }
    43.         temp->RIGHT_NEXT=L;
    44.         L->RIGHT_NEXT=NULL;
    45.         L->LEFTMOST_CHILD=NULL;
    46.     }
    47. }
    48. //xoa mot node ra khoi cay
    49. void DELETE_NODE(NODE N,TREE &T){
    50.     if(N->PARENT->LEFTMOST_CHILD==N){
    51.         N->PARENT->LEFTMOST_CHILD=N->RIGHT_NEXT;
    52.     }
    53.     else{
    54.         if(N->RIGHT_NEXT==NULL){
    55.             NODE T=N->PARENT->LEFTMOST_CHILD;
    56.             while(T->RIGHT_NEXT->RIGHT_NEXT!=NULL){
    57.                 T=T->RIGHT_NEXT;
    58.             }
    59.             T=NULL;
    60.         }
    61.         else{
    62.             NODE T=N->PARENT->LEFTMOST_CHILD;
    63.             while(T->RIGHT_NEXT!=N){
    64.                 T=T->RIGHT_NEXT;
    65.             }
    66.             T->RIGHT_NEXT=N->RIGHT_NEXT;
    67.         }
    68.     }
    69. }
    70. //hien thi danh sach cac node bao gom node cha tham so dau vao va cac node con cua no
    71. void VIEWNODE_CHILD(NODE N,TREE &T){
    72.     cout<<N->LABEL;
    73.     if(N->LEFTMOST_CHILD!=NULL){
    74.         NODE temp=N->LEFTMOST_CHILD;
    75.         cout<<temp->LABEL;
    76.         while(temp->RIGHT_NEXT!=NULL){
    77.             temp=temp->RIGHT_NEXT;
    78.             cout<<temp->LABEL;
    79.         }
    80.     }
    81. }
    82. int main(){
    83.     TREE T;
    84.     MAKENULL_TREE(T);
    85.     INSERT_NODE(1,T,T);
    86.     INSERT_NODE(2,T,T);
    87.     INSERT_NODE(3,T,T);
    88.     INSERT_NODE(14,T->LEFTMOST_CHILD,T);
    89.     INSERT_NODE(25,T->LEFTMOST_CHILD->RIGHT_NEXT,T);
    90.     DELETE_NODE(T->LEFTMOST_CHILD->RIGHT_NEXT->RIGHT_NEXT,T);//node la
    91.     VIEWNODE_CHILD(T,T);
    92.     VIEWNODE_CHILD(T->LEFTMOST_CHILD->RIGHT_NEXT,T);
    93.     getch();
    94.     return 0;
    95. }
    hôi mệt rùi chuyển qua học anh văn đây, bữa khác viết tiếp....
    Đã được chỉnh sửa lần cuối bởi naknah : 22-12-2011 lúc 01:48 PM.

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

    Code mình chưa xem nhưng ý tưởng về thuật giải bị sai mất rồi

    Xóa 1 node:
    - Nếu node cần xóa là con trái nhất của node cha, ta cho node cha của nó trỏ đến anh em phải của node cần xóa (cha bỏ nó)
    Note: sorry lúc đó chắc đãng trí mất rồi mới trích dẫn câu trên
    Đã được chỉnh sửa lần cuối bởi beautifulsoul84hung : 03-01-2012 lúc 07:17 PM.
    Hướng dẫn C++: https://www.youtube.com/watch?v=BwLodoQdoY4&list=PL1c9Uxlo-mplJDRGdONNupgo5OCBTyGGn

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

    Trích dẫn Nguyên bản được gửi bởi beautifulsoul84hung Xem bài viết
    Code mình chưa xem nhưng ý tưởng về thuật giải bị sai mất rồi

    nhấp vào đây xem hình nếu hình không hiển thị
    Tức quá hu hu. mất cả tiếng upload hình.

    Chắt tại bạn chưa hiểu về ý tưởng của mình.
    Ta có hình cây ban đầu như hình (1). Từ hình 1 ta xóa node B tức là cái cây mà ta muốn có được là cây hình (3) đúng không nào.
    Vậy là bây giờ mình làm sao đây.
    Mình có 1 câu hỏi là ở hình (2) có cách nào xác định được node B trên cây không? Câu trả lời là không.
    Giả sử mình duyệt cây theo phân cấp tức là duyệt node cha trước rùi tới các con của nó. Ta có con trỏ trỏ tới node gốc, từ node gốc ta duyệt con trái nhất của nó (nó trỏ tới con trái nhất của nó). Từ node con trái nhất đó ta duyệt node anh em phải liền kề với nó. cứ tiếp tục như vậy mà duyệt hết cây.
    Trở lại với câu hỏi ở hình 2 có cách nào xác định được node B hay không, ta thấy không có node nào trỏ tới nó nên ta không thể xác định được nó. vậy thì có thể xem nó đã bị xóa mặc dù nó còn trỏ tới node cha.
    Vậy xóa 1 node trong cây thì ta làm gì đây.
    Ta phải làm sao mà không có node nào trong cây trỏ tới node cần xóa, vậy là node đó bị xóa.

    Tức là:
    Nếu node cần xóa là con trái nhất của node cha thì ta cho cha của nó bỏ nỏ, trỏ sang anh phải liền kề với nó mà nó trỏ tới. (cập nhật con trái nhất).
    Còn nếu mà node cần xóa là node bình thường thì ta chỉ cần cho anh trái của nó trỏ qua anh phải của nó (không anh em nào trỏ tới nó) thì nó bị xóa.
    Trời tốn hết 5000 đồng net..
    ---------------------------------------------Hít------------------------------------------
    Đã được chỉnh sửa lần cuối bởi naknah : 03-01-2012 lúc 06:27 PM.

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

    Hix. Sao mình thấy nó giống Đồ thị thế nhỉ, chả nhìn ra cái cây gì hết luôn :( Sau 1 hồi đọc đọc xem xem mới thấy là cái cây
    Ở trường hợp 2 tihf theo mình Nút gốc A phải trỏ đến con trái nhất là nút B chứ sao lại trỏ đến C nhỉ @@ ? . Nếu xem C là trái nhất thì D phải trỏ đến B chứ @@ ??
    Trường hợp này sao có được ? Mà nếu lỡ để xảy ra cái đó thì làm sao mà xóa nó đây ? chỉ có nước Mem leak thôi (:(. Ngắt liên kết mà chưa chịu delete. Xem ra có vẻ nguy hiểm

    Thêm nữa: Mình ko hiểu nếu trường hợp nút cần xóa là 1 nút nhánh. Thì các con của nút đó ta giao cho ai nuôi ??
    Xóa nút chỉ áp dụng dc với nút lá thôi chứ nhỉ

    Mình có nhận xét này
    Nếu ngắt các liên kết từ con trỏ ngược về cha thì cái cây đó lại trở thành cây nhị phân trong Phép biểu diễn cây tổng quát = cây nhị phân
    Đã được chỉnh sửa lần cuối bởi clchicken : 04-01-2012 lúc 01:37 PM.
    Um Mani Padme Hum...!!

  5. #5
    Ngày gia nhập
    01 2012
    Bài viết
    24

    @naknah: Code cậu theo cái convention gì sida thế. Đừng viết HOA như thế, convention của C++ thông thường chỉ có const mới viết kiểu đấy thôi. C++, Java.

    Lười xem code (đau mắt) nhưng đại khái cũng hiểu ý tưởng của cậu, được cái không phải lưu previous link nhưng mà overhead lúc insert vs remove thì kinh quá, nhất là những node có nhiều element.

    Branching hơi lắm, may mà CPU của PC nó khôn, không có ý định target mấy cái hardware sida như embed hay console, handheld etc. thì cũng được.

    @clchicken: Cây nhị phân mỗi node chỉ có tối đa hai cái lá thôi, nó optimize để search cho nhanh.

    Kiểu thiết kế này là intrusive tree, node không chứa copy của element mà bản thân nó là element luôn. Element có thể inherit từ node hoặc là POD thì field đầu tiên là node cũng được. Được cái là không phải malloc node riêng nên tránh được fragment vs copy. Khi remove thì không cần thiết phải delete bởi vì bây giờ node cũng là element luôn rồi. Trừ trường hợp muốn cái tree nó own luôn thì mới cần delete thôi.

    Nhưng mà vẫn nên thêm remove policy, hoặc là sử dụng reference counting để tránh leak.
    Đã được chỉnh sửa lần cuối bởi Jangdeon : 04-01-2012 lúc 02:53 PM.
    Tuesday 03 January 2012
    Battery Level, 69%

  6. #6
    Ngày gia nhập
    01 2012
    Bài viết
    24

    Mặc định Cài đặt cấu trúc dữ liệu cây kiểu con trỏ

    Nếu order không quan trọng thì chỉ cần push_front thôi sẽ tránh được overhead lúc insert.
    Tuesday 03 January 2012
    Battery Level, 69%

  7. #7
    Ngày gia nhập
    12 2011
    Bài viết
    15

    Trích dẫn Nguyên bản được gửi bởi clchicken Xem bài viết
    Hix. Sao mình thấy nó giống Đồ thị thế nhỉ, chả nhìn ra cái cây gì hết luôn :( Sau 1 hồi đọc đọc xem xem mới thấy là cái cây
    Ở trường hợp 2 tihf theo mình Nút gốc A phải trỏ đến con trái nhất là nút B chứ sao lại trỏ đến C nhỉ @@ ? . Nếu xem C là trái nhất thì D phải trỏ đến B chứ @@ ??
    Trường hợp này sao có được ? Mà nếu lỡ để xảy ra cái đó thì làm sao mà xóa nó đây ? chỉ có nước Mem leak thôi (:(. Ngắt liên kết mà chưa chịu delete. Xem ra có vẻ nguy hiểm

    Thêm nữa: Mình ko hiểu nếu trường hợp nút cần xóa là 1 nút nhánh. Thì các con của nút đó ta giao cho ai nuôi ??
    Xóa nút chỉ áp dụng dc với nút lá thôi chứ nhỉ

    Mình có nhận xét này
    Nếu ngắt các liên kết từ con trỏ ngược về cha thì cái cây đó lại trở thành cây nhị phân trong Phép biểu diễn cây tổng quát = cây nhị phân
    Trã lời bạn clchicken.

    Câu 1: "Sao mình thấy nó giống Đồ thị thế nhỉ?"
    Hình vẻ thì có giống đồ thị có hướng thật nhưng bài mình đang làm là cây tổng quát. Thực ra mình củng có thể xem nó là đồ thị có hướng nếu cần. Thực ra mình có cách cài đặt cấu trúc đồ thị bằng con trỏ luôn, cái này thì không ai dạy hít, đặc điểm của cài đặt bằng con trỏ là cấu trúc dữ liệu dể thêm, dễ xóa không cần phải duyệt tất cả các phần tử nếu đã xác định được con trỏ trỏ tới nó.

    Câu 2: "Ở trường hợp 2 thì theo mình Nút gốc A phải trỏ đến con trái nhất là nút B chứ sao lại trỏ đến C nhỉ @@ ? . Nếu xem C là trái nhất thì D phải trỏ đến B chứ @@ ??".
    Ta có hình bên hình vẽ của mình có 3 nhóm hình nếu bạn quan sát kỹ.
    Hình (1) là trạng thái ban đầu của cây.
    Hình (2),(3) là trạng thái xóa node B
    Hình (4), (5) thay vì xóa B, từ trạng thái ban đầu ta xóa C. Hình 5 là cái hình mình quên để tên đó.
    Ở câu hỏi thứ 2 này ta tiến hành xóa node B, tức là ta phải cách ly thằng B, tức là làm cho không có thằng nào nhìn thấy nó kể cả cha nó củng như anh em của nó. Nếu ta đã cách ly nó sao phải trỏ tới B bạn, node cha phải trỏ tới C mới đúng chớ.

    Câu 3: Bạn hỏi là khi ta xóa một node mà nó không phải là node lá tức là nó còn 1 ề con thì phải làm sao?
    Câu trả lời kệ nó, nó muốn sao thì mặc nó. Mình ở đây chỉ quan tâm đến cây chính của mình, làm sao mà khi duyệt cây mình không thấy cái thằng cần xóa nữa.

    Câu 4: "Nếu ngắt các liên kết từ con trỏ ngược về cha thì cái cây đó lại trở thành cây nhị phân trong Phép biểu diễn cây tổng quát = cây nhị phân "
    Phát biểu này của bạn không đúng. Cây nhị phân thì chắt chắn 1 node sẻ có số con là 0,1 hoăc là 2 con. Trong cây nhị phân node cha là 1 con trỏ trỏ tới node con là con trỏ. Bạn chắt biết khái niệm con trỏ trỏ con trỏ mà. Còn ở cây của mình thì cha chỉ trỏ tới con trái nhất. Thằng cha không có con trỏ trực tiếp đến mấy anh em của nó, nhưng lại có con trỏ gián tiếp vì vậy từ cha có thể xác định được mấy anh em của nó.

    Mình cố tình không viết hàm duyệt cây để tìm 1 node trong cây là có lý do chứ.
    Trong hàm main các bạn có thấy mấy hàm
    INSERT_NODE(1,T,T);
    ....
    Cho hỏi mấy câu coi.
    Câu 1: INSERT_NODE(1,T,T); T đầu tiên trong hàm này là gì, T thứ 2 trong hàm này là gì? Nó khác nhau hay không giống nhau.
    Câu 2: T->LEFTMOST_CHILD->RIGHT_NEXT->RIGHT_NEXT // cái thằng này là cái gì đây?
    Câu 3: theo hình này A->LEFTMOST_CHILD->RIGHT_NEXT->RIGHT_NEXT->PARENT->LEFTMOST_CHILD; với thằng A có khác nhau không?
    Suy nghỉ đi mấy câu hỏi không đơn giản đâu. Học cấu trúc dữ liệu kĩ lắm mới hiểu những vấn đề này.
    ....
    DELETE_NODE(T->LEFTMOST_CHILD->RIGHT_NEXT->RIGHT_NEXT,T);
    Đã được chỉnh sửa lần cuối bởi naknah : 04-01-2012 lúc 11:13 PM.

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

    Trích dẫn Nguyên bản được gửi bởi Jangdeon Xem bài viết
    @naknah: Code cậu theo cái convention gì sida thế. Đừng viết HOA như thế, convention của C++ thông thường chỉ có const mới viết kiểu đấy thôi. C++, Java.

    Lười xem code (đau mắt) nhưng đại khái cũng hiểu ý tưởng của cậu, được cái không phải lưu previous link nhưng mà overhead lúc insert vs remove thì kinh quá, nhất là những node có nhiều element.

    Branching hơi lắm, may mà CPU của PC nó khôn, không có ý định target mấy cái hardware sida như embed hay console, handheld etc. thì cũng được.

    @clchicken: Cây nhị phân mỗi node chỉ có tối đa hai cái lá thôi, nó optimize để search cho nhanh.

    Kiểu thiết kế này là intrusive tree, node không chứa copy của element mà bản thân nó là element luôn. Element có thể inherit từ node hoặc là POD thì field đầu tiên là node cũng được. Được cái là không phải malloc node riêng nên tránh được fragment vs copy. Khi remove thì không cần thiết phải delete bởi vì bây giờ node cũng là element luôn rồi. Trừ trường hợp muốn cái tree nó own luôn thì mới cần delete thôi.

    Nhưng mà vẫn nên thêm remove policy, hoặc là sử dụng reference counting để tránh leak.
    Hjx, tại đây là phong cách lập trình của trường đại học cần thơ. Bạn comment mà mình ko hiểu gì hít nên không biết đường trã lời.
    Đã được chỉnh sửa lần cuối bởi naknah : 04-01-2012 lúc 11:14 PM.

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

    Câu 4: "Nếu ngắt các liên kết từ con trỏ ngược về cha thì cái cây đó lại trở thành cây nhị phân trong Phép biểu diễn cây tổng quát = cây nhị phân "
    Phát biểu này của bạn không đúng. Cây nhị phân thì chắt chắn 1 node sẻ có số con là 0,1 hoăc là 2 con. Trong cây nhị phân node cha là 1 con trỏ trỏ tới node con là con trỏ. Bạn chắt biết khái niệm con trỏ trỏ con trỏ mà. Còn ở cây của mình thì cha chỉ trỏ tới con trái nhất. Thằng cha không có con trỏ trực tiếp đến mấy anh em của nó, nhưng lại có con trỏ gián tiếp vì vậy từ cha có thể xác định được mấy anh em của nó.
    Theo như mình dc biết thì cây nhị phân biểu diễn cây tổng quát tương ứng đều hội đủ những tính chất bạn vừa nêu.
    Sao lại bảo phát biểu của mình ko đúng ?
    Câu 3: Bạn hỏi là khi ta xóa một node mà nó không phải là node lá tức là nó còn 1 ề con thì phải làm sao?
    Câu trả lời kệ nó, nó muốn sao thì mặc nó. Mình ở đây chỉ quan tâm đến cây chính của mình, làm sao mà khi duyệt cây mình không thấy cái thằng cần xóa nữa.
    Cái này liệu có an toàn ko ?
    Giả sử bạn có 1 cây dài ơi là dài, nhiều tầng. trong khi đó bạn muốn xóa nút ở mức 2.
    Vậy 1 đống con của nút này ai nuôi chúng? hay để chúng vật vờ trong Ram vậy ko nơi nương tựa ?
    Vấn đề ở chỗ là lấy cái gì để trỏ vào toàn bộ con của chúng ?
    Mình chưa hiểu ý tưởng xóa của bạn lắm. Xóa mà chỉ ngắt liên kết, ko xóa hẳn trên ram là sao nhỉ ?
    Um Mani Padme Hum...!!

  10. #10
    Ngày gia nhập
    01 2012
    Bài viết
    24

    Trích dẫn Nguyên bản được gửi bởi naknah Xem bài viết
    Hjx, tại đây là phong cách lập trình của trường đại học cần thơ. Bạn comment mà mình ko hiểu gì hít nên không biết đường trã lời.
    Chắc tại mình dùng hơi nhiều TA, thông cảm tại mình không quen lắm với ngôn ngữ IT của VN. Muốn tìm từ tương ứng cũng khó, hơn nữa dùng TV nếu bạn không hiểu hoặc muốn tìm thêm thông tin thì sẽ rất khó google.

    Trích dẫn Nguyên bản được gửi bởi clchicken Xem bài viết
    Theo như mình dc biết thì cây nhị phân biểu diễn cây tổng quát tương ứng đều hội đủ những tính chất bạn vừa nêu.
    Sao lại bảo phát biểu của mình ko đúng ?
    Cái này không phải cây nhị phân.

    Cây nhị phân là cái cây mà mỗi nút của nó chỉ có tối đa là 2 cái lá thôi, thế mới gọi là nhị phân. Người ta dựa vào đặc điểm đó để tạo ra cây tìm kiếm nhị phân, là một cái cây đã được sort. Tuy insert và remove bị overhead do phải sort và balance nhưng tốc độ tìm kiếm sẽ nhanh hơn là tìm kiểu tuyến tính (linear search).

    Cái cây của naknah, mỗi node có một list vô hạn (single linked list) các childs, nó chỉ là cái cây bình thường thôi.

    C++ Code:
    1. struct Node
    2. {
    3.     Node* Parent;
    4.     List<Node*> Childs;
    5. };

    Trích dẫn Nguyên bản được gửi bởi clchicken Xem bài viết
    Cái này liệu có an toàn ko ?
    Giả sử bạn có 1 cây dài ơi là dài, nhiều tầng. trong khi đó bạn muốn xóa nút ở mức 2.
    Vậy 1 đống con của nút này ai nuôi chúng? hay để chúng vật vờ trong Ram vậy ko nơi nương tựa ?
    Vấn đề ở chỗ là lấy cái gì để trỏ vào toàn bộ con của chúng ?
    Mình chưa hiểu ý tưởng xóa của bạn lắm. Xóa mà chỉ ngắt liên kết, ko xóa hẳn trên ram là sao nhỉ ?
    Cây là một kiểu cấu trúc dùng để lưu dữ liệu thôi, thông thường bạn học ở trường thì cấu trúc một của một liên kết trong danh sách liên kết như sau.

    C++ Code:
    1. struct Link
    2. {
    3.     Link* Next;
    4.     void* Data;
    5. };
    6.  
    7. struct DoubleLink
    8. {
    9.     Link* Next;
    10.     Link* Prev; // previous link
    11.     void* Data;
    12. };

    Đó là danh sách bình thường, khi thêm data vào thì một liên kết mới sẽ được tạo ra, thiết lập liên kết với các liên kết khác và set data. Khi xóa thì liên kết đó sẽ bị ngắt và hủy nhưng không có nghĩa là data phải bị hủy theo. Data vẫn có thể được tiếp tục sử dụng thậm chí thêm lại vào danh sách đó hoặc danh sách khác. Cách này có nhược điểm là overhead khi xóa, chỉ xóa được bằng liên kết, khi xóa bằng giá trị thì phải search ra được liên kết có giá trị đó. Ngoài ra còn phải cấp phát một phần bộ nhớ khá nhỏ để tạo liên kết gây chậm chương trình và phân mảnh bộ nhớ.

    Còn cái tree của naknah là intrusive tree, bản thân dữ liệu nó đã chứa liên kết rồi, hay nó cách khác nó chính là liên kết.

    C++ Code:
    1. struct Link
    2. {
    3.     Link* Next;
    4. };
    5.  
    6. struct DoubleLink
    7. {
    8.     Link* Next;
    9.     Link* Prev;
    10. };
    11.  
    12. struct Data
    13. {
    14.     Link link;
    15.     // DoubleLink link;
    16. };
    17.  
    18. // Nếu OOP thì class Data có thể kế thừa trực tiếp từ class Link

    Cách này có ưu điểm là không bị overhead khi xóa do Data cũng là liên kết luôn, cũng không phải cấp phát bộ nhớ khi thêm vào (có cấp đâu mà phải free) nên tốc độ cao hơn và tránh được phân mảnh bộ nhớ.

    Cây của naknah mỗi nút sử dụng danh sách liên kết đơn (single linked list), chỉ có liên kết theo một chiều nên chỉ có thể thêm và xóa hai đầu của danh sách. Thêm và xóa ở giữa là overhead do phải duyệt tìm liên kết theo chiều ngược lại. Ưu điểm là đỡ dc tý memory thôi. Nếu không có nhu cầu thêm với xóa ở giữa danh sách thì dùng cách này là tốt.

    Nên thêm remove policy bởi vì nhiều trường hợp users cũng muốn cái tree nó own luôn data, remove cái là chém luôn.

    P/S: Đổi tên cái deleteNode thành removeNode đi thì hơn, insert nó match với remove, delete user nó lại tưởng chém luôn thì leak thật đấy.
    Tuesday 03 January 2012
    Battery Level, 69%

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

  1. Trả lời: 0
    Bài viết cuối: 07-07-2013, 07:29 PM
  2. Bài tập về cấu trúc trong c | Cấu trúc sinh viên???
    Gửi bởi dddzzzjjjiii trong diễn đàn Nhập môn lập trình C/C++
    Trả lời: 14
    Bài viết cuối: 21-07-2012, 05:06 PM
  3. Chiếu trúc, Chiếu trúc cao cấp, Hàng Sản xuất tại Việt Nam: Giá rẻ nhất thị trường
    Gửi bởi tqt.tranquoctuan trong diễn đàn Giới thiệu website, sản phẩm của bạn
    Trả lời: 0
    Bài viết cuối: 13-05-2012, 08:33 PM
  4. cấu trúc bảng băm là cấu trúc như thế nào?
    Gửi bởi minh_quang1202 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: 06-01-2011, 07:03 PM
  5. Cấu trúc file excel | Cấu trúc file xls. Giúp mình với?
    Gửi bởi knightofit 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: 02-04-2009, 10:44 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