Công cụ bảo vệ mã nguồn .NET mạnh nhất, không thể unpack, miễn phí cho các khách hàng đầu tiên đăng ký.
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ố 18 kết quả

Đề tài: nạp chồng toán tử [] - binary search tree

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

    Mặc định nạp chồng toán tử [] - binary search tree

    chào mọi người, mọi người cho mình hỏi ai đã từng làm nạp chồng toán tử [] trong cây nhị phân tìm kiếm chưa ạ, chỉ cho mình với. Ví dụ:
    A 5 6 8 2 3 4 (key)
    0.1 4.5 2.3 5.2 1.8 (data)

    bây giờ mình cần:
    int x;
    nếu x = key thì in ra A[x] = data;
    còn x != key thì thông báo lỗi
    phần code khai báo của mình như sau:
    class Tree {
    private:
    struct node {
    int key;
    float data;
    node* left;
    node* right;
    };
    node* root;
    Công cụ bảo vệ mã nguồn .NET mạnh nhất hiện tại, miễn phí cho các khách hàng đầu tiên đăng ký.

  2. #2
    Ngày gia nhập
    01 2008
    Nơi ở
    Rất đông người
    Bài viết
    586

    Mình chỉ có operator[] cho cây 26-phân, mời bạn tham khảo:

    http://diendan.congdongcviet.com/threads/t8546::tu-dien-anh-viet-dung-cay-26-phan.cpp

    Nhân tiện, overload nghĩa không phải là "nạp chồng", mà là "quá tải" nhé. Tất nhiên, "quá tải" cũng là dịch gần đúng thôi.
    -...- -.- .. .-.. .-.. - .... . -... . .- ... - .-.-.

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

    bạn xem chương trình này giúp mình với, hàm main giờ viết sao?

    #include<iostream>
    using namespace std;

    class Tree {
    private:
    struct node {
    int key;
    float data;
    node* left;
    node* right;
    };
    node* root;

    node* makeEmpty(node* t);
    node* insertprivate(int x, float y, node* t);
    node* findMin(node* t);
    node* removeprivate(int x, float y, node* t);
    void inorderprivate(node* t);
    node* findprivate(node* t, int x);
    int countprivate(node* t);
    node* findNodeWithKey(int index, node* t);

    public:
    Tree();
    ~Tree();
    void insert(int x, float y);
    void remove(int x, float y);
    void inorder();
    void find(int x);
    int count();
    float& operator[](int index);

    };

    Tree::Tree() {
    root = NULL;
    }

    Tree::~Tree() {
    root = makeEmpty(root);
    }

    Tree::node* Tree::makeEmpty(node* t) {
    if (t == NULL)
    return NULL;
    {
    makeEmpty(t->left);
    makeEmpty(t->right);
    delete t;
    }
    return NULL;
    }

    void Tree::insert(int x, float y) {
    root = insertprivate(x, y, root);
    }

    Tree::node* Tree::insertprivate(int x, float y, node* t)
    {
    if (t == NULL)
    {
    t = new node;
    t->key = x;
    t->data = y;
    t->left = t->right = NULL;
    }
    else if (x < t->key)
    t->left = insertprivate(x, y, t->left);
    else if (x > t->data)
    t->right = insertprivate(x, y, t->right);
    return t;
    }

    void Tree::remove(int x, float y) {
    root = removeprivate(x, y, root);
    }

    Tree::node* Tree::removeprivate(int x, float y, node* t) {
    node* temp;
    if (t == NULL)
    return NULL;
    else if (x < t->key)
    t->left = removeprivate(x, y, t->left);
    else if (x > t->key)
    t->right = removeprivate(x, y, t->right);
    else if (t->left && t->right)
    {
    temp = findMin(t->right);
    t->key = temp->key;
    t->right = removeprivate(t->key, t->data, t->right);
    }
    else
    {
    temp = t;
    if (t->left == NULL)
    t = t->right;
    else if (t->right == NULL)
    t = t->left;
    delete temp;
    }

    return t;
    }

    void Tree::inorder() {
    inorderprivate(root);
    cout << endl;
    }

    void Tree::inorderprivate(node* t) {
    if (t == NULL)
    return;
    inorderprivate(t->left);
    cout << t->key << "( " << t->data << " )\t";
    inorderprivate(t->right);
    }

    void Tree::find(int x) {
    root = findprivate(root, x);
    }

    Tree::node* Tree::findprivate(node* t, int x) {
    if (t == NULL)
    return NULL;
    else if (x < t->data)
    return findprivate(t->left, x);
    else if (x > t->data)
    return findprivate(t->right, x);
    else
    return t;
    }

    Tree::node* Tree::findMin(node* t)
    {
    if (t == NULL)
    return NULL;
    else if (t->left == NULL)
    return t;
    else
    return findMin(t->left);
    }

    int Tree::countprivate(node* t)
    {
    if (t == NULL)
    return 0;
    else
    return (countprivate(t->right) + countprivate(t->left)) + 1;
    }

    int Tree::count()
    {
    cout << "Count = " << countprivate(root);
    cout << endl;
    return 0;
    }

    float& Tree::operator[](int index) {
    node* t = findNodeWithKey(index, root);
    if (t) return t->data;
    }

    Tree::node* Tree::findNodeWithKey(int index, node* t) {
    if (!t || t->key == index) return t;
    return findNodeWithKey(index, index < t->key ? t->left : t->right);
    }

    int main() {

    Tree* bst = new Tree();
    bst->insert(20, 0.1);
    bst->insert(25, 0.2);
    bst->insert(10, 0.5);
    bst->inorder();
    bst->count();
    bst->remove(20, 0.1);
    bst->inorder();
    bst->count();
    //Tree A;
    //cout << "A[key] = " << ;
    return 0;
    }

  4. #4
    Ngày gia nhập
    01 2008
    Nơi ở
    Rất đông người
    Bài viết
    586

    Sau đây là code của bạn, không thay đổi gì, chỉ định dạng lại cho dễ xem.

    C++ Code:
    1. #include<iostream>
    2. using namespace std;
    3.  
    4. class Tree {
    5. private:
    6.     struct node {
    7.         int key;
    8.         float data;
    9.         node* left;
    10.         node* right;
    11.     };
    12.     node* root;
    13.  
    14.     node* makeEmpty(node* t);
    15.     node* insertprivate(int x, float y, node* t);
    16.     node* findMin(node* t);
    17.     node* removeprivate(int x, float y, node* t);
    18.     void inorderprivate(node* t);
    19.     node* findprivate(node* t, int x);
    20.     int countprivate(node* t);
    21.     node* findNodeWithKey(int index, node* t);
    22.  
    23. public:
    24.     Tree();
    25.     ~Tree();
    26.     void insert(int x, float y);
    27.     void remove(int x, float y);
    28.     void inorder();
    29.     void find(int x);
    30.     int count();
    31.     float& operator[](int index);
    32. };
    33.  
    34. Tree::Tree() {
    35.     root = NULL;
    36. }
    37.  
    38. Tree::~Tree() {
    39.     root = makeEmpty(root);
    40. }
    41.  
    42. Tree::node* Tree::makeEmpty(node* t) {
    43.     if (t == NULL)
    44.         return NULL;
    45. {
    46. makeEmpty(t->left);
    47. makeEmpty(t->right);
    48. delete t;
    49. }
    50. return NULL;
    51. }
    52.  
    53. void Tree::insert(int x, float y) {
    54.     root = insertprivate(x, y, root);
    55. }
    56.  
    57. Tree::node* Tree::insertprivate(int x, float y, node* t)
    58. {
    59.     if (t == NULL)
    60.     {
    61.         t = new node;
    62.         t->key = x;
    63.         t->data = y;
    64.         t->left = t->right = NULL;
    65.     }
    66.     else if (x < t->key)
    67.         t->left = insertprivate(x, y, t->left);
    68.     else if (x > t->data)
    69.         t->right = insertprivate(x, y, t->right);
    70.     return t;
    71. }
    72.  
    73. void Tree::remove(int x, float y) {
    74.     root = removeprivate(x, y, root);
    75. }
    76.  
    77. Tree::node* Tree::removeprivate(int x, float y, node* t) {
    78.     node* temp;
    79.     if (t == NULL)
    80.         return NULL;
    81.     else if (x < t->key)
    82.         t->left = removeprivate(x, y, t->left);
    83.     else if (x > t->key)
    84.         t->right = removeprivate(x, y, t->right);
    85.     else if (t->left && t->right)
    86.     {
    87.         temp = findMin(t->right);
    88.         t->key = temp->key;
    89.         t->right = removeprivate(t->key, t->data, t->right);
    90.     }
    91.     else
    92.     {
    93.         temp = t;
    94.         if (t->left == NULL)
    95.             t = t->right;
    96.         else if (t->right == NULL)
    97.             t = t->left;
    98.         delete temp;
    99.     }
    100.     return t;
    101. }
    102.  
    103. void Tree::inorder() {
    104.     inorderprivate(root);
    105.     cout << endl;
    106. }
    107.  
    108. void Tree::inorderprivate(node* t) {
    109.     if (t == NULL)
    110.         return;
    111.     inorderprivate(t->left);
    112.     cout << t->key << "( " << t->data << " )\t";
    113.     inorderprivate(t->right);
    114. }
    115.  
    116. void Tree::find(int x) {
    117.     root = findprivate(root, x);
    118. }
    119.  
    120. Tree::node* Tree::findprivate(node* t, int x) {
    121.     if (t == NULL)
    122.         return NULL;
    123.     else if (x < t->data)
    124.         return findprivate(t->left, x);
    125.     else if (x > t->data)
    126.         return findprivate(t->right, x);
    127.     else
    128.         return t;
    129. }
    130.  
    131. Tree::node* Tree::findMin(node* t)
    132. {
    133. if (t == NULL)
    134.     return NULL;
    135. else if (t->left == NULL)
    136.     return t;
    137. else
    138.     return findMin(t->left);
    139. }
    140.  
    141. int Tree::countprivate(node* t)
    142. {
    143.     if (t == NULL)
    144.         return 0;
    145.     else
    146.     return (countprivate(t->right) + countprivate(t->left)) + 1;
    147. }
    148.  
    149. int Tree::count()
    150. {
    151.     cout << "Count = " << countprivate(root);
    152.     cout << endl;
    153.     return 0;
    154. }
    155.  
    156. float& Tree::operator[](int index) {
    157.     node* t = findNodeWithKey(index, root);
    158.     if (t) return t->data;
    159. }
    160.  
    161. Tree::node* Tree::findNodeWithKey(int index, node* t) {
    162.     if (!t || t->key == index)
    163.         return t;
    164.     return findNodeWithKey(index, index < t->key ? t->left : t->right);
    165. }
    166.  
    167. int main()
    168. {
    169.     Tree* bst = new Tree();
    170.     bst->insert(20, 0.1);
    171.     bst->insert(25, 0.2);
    172.     bst->insert(10, 0.5);
    173.     bst->inorder();
    174.     bst->count();
    175.     bst->remove(20, 0.1);
    176.     bst->inorder();
    177.     bst->count();
    178.     //Tree A;
    179.     //cout << "A[key] = " << ;
    180.     return 0;
    181. }

    Đề nghị bạn giải thích ý nghĩa của hàm thành viên

    C++ Code:
    1. node* findNodeWithKey(int index, node* t);

    Hàm này làm gì? Hai tham số indext có ý nghĩa gì? Kết quả trả lại, kỳ vọng là gì?

    Và đề nghị bạn xem lại đoạn code này.
    C++ Code:
    1. Tree::node* Tree::makeEmpty(node* t) {
    2.     if (t == NULL)
    3.         return NULL;
    4. {
    5. makeEmpty(t->left);
    6. makeEmpty(t->right);
    7. delete t;
    8. }
    9. return NULL;
    10. }

    - - - Nội dung đã được cập nhật ngày 26-03-2020 lúc 08:51 PM - - -

    Và xem lại đoạn này nữa.

    C++ Code:
    1. float& Tree::operator[](int index) {
    2.     node* t = findNodeWithKey(index, root);
    3.     if (t) return t->data;
    4. }
    -...- -.- .. .-.. .-.. - .... . -... . .- ... - .-.-.

  5. #5
    Ngày gia nhập
    12 2017
    Bài viết
    5

    node* findNodeWithKey(int index, node* t); -- cái này là hàm tìm kiếm nút (đề bài yêu cầu in ra A[key] = data)
    float& Tree::operator[](int index) {
    node* t = findNodeWithKey(index, root); -- vậy nên nếu index = key thì in ra data
    if (t) return t->data;

  6. #6
    Ngày gia nhập
    01 2008
    Nơi ở
    Rất đông người
    Bài viết
    586

    Mặc định nạp chồng toán tử [] - binary search tree

    Trích dẫn Nguyên bản được gửi bởi Tai2 Xem bài viết
    node* findNodeWithKey(int index, node* t); -- cái này là hàm tìm kiếm nút (đề bài yêu cầu in ra A[key] = data)
    Mình hỏi bạn 4 câu, bạn mới trả lời 1. Xem lại 3 câu hỏi còn lại của mình. Chúng không làm nên giải pháp, nhưng làm nên yêu cầu. Và yêu cầu thì mình không nghĩ ra hộ cho bạn được. Không ai nghĩ ra được, trừ chính bạn.

    Trích dẫn Nguyên bản được gửi bởi Tai2 Xem bài viết
    float& Tree::operator[](int index) {
    node* t = findNodeWithKey(index, root); -- vậy nên nếu index = key thì in ra data
    if (t) return t->data;
    Đó là phần bạn đã viết ra. Nhưng ý mình là bạn nên xem lại cái mà bạn không viết ra cơ.

    Nếu (t) thì trả lại t->data. Thế còn nếu (!t) thì sao?
    -...- -.- .. .-.. .-.. - .... . -... . .- ... - .-.-.

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

    float& Tree::operator[](int index) {
    node* t = findNodeWithKey(index, root);
    if (t) return t->data;
    else throw std::runtime_error("Invalid key");
    }
    thì thông báo lỗi

    - - - Nội dung đã được cập nhật ngày 27-03-2020 lúc 02:57 AM - - -

    nhưng khi xuống hàm main, mình không biết viết sao, chạy kết quả ra toàn Invalid key

  8. #8
    Ngày gia nhập
    01 2008
    Nơi ở
    Rất đông người
    Bài viết
    586

    Trích dẫn Nguyên bản được gửi bởi Tai2 Xem bài viết
    node* findNodeWithKey(int index, node* t); -- cái này là hàm tìm kiếm nút
    Bạn vẫn chưa trả lời các câu hỏi của mình để làm rõ mục đích của hàm này. Bạn hãy làm rõ hơn. "Nút" là gì? Có phải "nút" là "node" không? Tìm kiếm "nút" nào? Có quan hệ gì giữa "nút" cần tìm với các tham số index, t và giá trị return của hàm? Nếu tìm thấy thì phải làm sao? Và nếu không tìm thấy thì phải làm sao?

    Ngoài hàm này ra, hàm main() còn gọi nhiều hàm khác. Nhưng nguyên tắc kiểm tra là đi từ cuối truy ngược lại đầu, từ hiện tượng truy ngược lại bản chất, nên bạn hãy bắt đầu từ hàm này trước khi xem đến các hàm còn lại.
    -...- -.- .. .-.. .-.. - .... . -... . .- ... - .-.-.

  9. #9
    Ngày gia nhập
    12 2017
    Bài viết
    5

    hàm tìm kiếm trước đó của mình không ổn đúng không?
    nút ở đây là node, hàm tìm kiếm node có giá trị index theo khóa key, t là một node gốc, nếu node cần tìm là node gốc thì return trả về node gốc, nếu không phải node gốc thì so sánh index với giá trị key tại node gốc, nếu nhỏ hơn thì tìm theo nhánh bên trái, ngược lại nhỏ hơn thì tìm theo bên phải, return trả node tìm được, không tìm được trả lại null

  10. #10
    Ngày gia nhập
    01 2008
    Nơi ở
    Rất đông người
    Bài viết
    586

    Trích dẫn Nguyên bản được gửi bởi Tai2 Xem bài viết
    hàm tìm kiếm trước đó của mình không ổn đúng không?
    nút ở đây là node, hàm tìm kiếm node có giá trị index theo khóa key, t là một node gốc, nếu node cần tìm là node gốc thì return trả về node gốc, nếu không phải node gốc thì so sánh index với giá trị key tại node gốc, nếu nhỏ hơn thì tìm theo nhánh bên trái, ngược lại nhỏ hơn thì tìm theo bên phải, return trả node tìm được, không tìm được trả lại null
    Được rồi. Vậy bạn tìm node theo key, chứ không tìm theo data, và index là giá trị của key, đúng không nào.

    Đây là 1 đoạn code của bạn mà mình đã chữa.

    C++ Code:
    1. Tree::node* Tree::insertprivate(int x, float y, node* t)
    2. {
    3.     if (t == NULL)
    4.     {
    5.         t = new node;
    6.         t->key = x;
    7.         t->data = y;
    8.         t->left = t->right = NULL;
    9.     }
    10.     else if (x < t->key)
    11.         t->left = insertprivate(x, y, t->left);
    12.     else if (x > t->key)
    13.         t->right = insertprivate(x, y, t->right);
    14.     return t;
    15. }

    Khi chạy, chương trình sẽ in ra màn hình như sau.
    Code:
    10( 0.5 )       20( 0.1 )       25( 0.2 )
    Count = 3
    10( 0.5 )       25( 0.1 )
    Count = 2
    Công cụ bảo vệ mã nguồn .NET mạnh nhất hiện tại, miễn phí cho các khách hàng đầu tiên đăng ký.
    -...- -.- .. .-.. .-.. - .... . -... . .- ... - .-.-.

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