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ố 12 kết quả

Đề tài: [C++] Cấu trúc dữ liệu với link list

  1. #1
    Ngày gia nhập
    12 2006
    Nơi ở
    US
    Bài viết
    1,917

    Mặc định [C++] Cấu trúc dữ liệu với link list

    Như r2 đã nói, topic này chúng ta sẽ bàn luận cách nào để cài đặt link list với mọi kiểu dữ liệu :
    - Stack
    - Queue
    - Priority Queue
    - Single Link List
    - Double Link List
    - Binary Tree
    - AVL Tree
    - Black Red Tree.

    - Sau đó chúng ta sẽ viết dùng những cài đặt này để viết các ứng dụng cụ thể mà trước mắt là bài tập với số nguyên lớn.
    - Mặt dù những đề tài này đã quá quen thuộc và có thể dễ dàng đối với nhiều bạn nhưng đối với mình thì nó quả là thử thách. Cụ thể viết bài số lớn đã gần 2 ngày rùi mà không có kết quả, nhận xét của mình là cách cài đặt kiểu đơn thuần chỉ có hàm làm cho việc viết ứng dụng trở nên quá khó khăn. Và cá nhân mình nghĩ vì lý do này nên STL nó mới ra đời. Vì vậy mục tiêu sẽ là viết các loại cấu trúc trên dựa vào các thao tác như các container của STL ( có iterator, các hàm chuẩn ) và nếu được thì chúng ta sẽ mở rộng thêm.
    - Mình đã lôi kéo được 1 số bạn kinh nghiệm như : iamtvn, kidkid, comeonebaby và Forlorn_Hope. Đề nghị các bạn không post bài chat chít ở đây vì mình sẽ xoá tất cả. Hi vọng topic này sẽ giúp chúng ta hiểu rõ hơn về vấn đề con trỏ và việc ứng dụng nó thế nào cho hiệu quả.

    - Đầu tiên mình đang viết bài số lớn, và việc truy xuất đến các phần tử dữ liệu trở nên cực kì khó khăn khi không có iterator. Sau đây là bài của mình, các cậu nếu có idea gì hay, algorithm tối ưu thì chúng ta sẽ bàn luận trước khi vào viết lại hoàn chỉnh.
    - Bài đầu tiên mình muốn làm sẽ làm 1 lớp hoàn chỉnh về double link list. Tất cả các class sẽ bắt đầu bằng CV, mang ý nghĩ C việt. Ví dụ class CVDoubleLinkedList {}. ( CV double link list ). Mình sẽ cố gắng đưa các tên hàm cụ thể lên 1 cách sớm nhất để chúng ta có thể bắt đầu công việc !.

    Đã được chỉnh sửa lần cuối bởi rox_rook : 05-04-2008 lúc 07:46 PM.

  2. #2
    Ngày gia nhập
    12 2006
    Nơi ở
    US
    Bài viết
    1,917

    Sau đây là dàn bài sơ khảo, nếu kidkid, forlorn, iamtvn và baby có ý kiến gì thì tranh thủ bổ sung nhé .
    C++ Code:
    1.  
    2. namespace cv{
    3. template <typename T>
    4. class CVDoubleLinkedList{
    5. protected :
    6.   class Node{
    7.   public :
    8.     Node(const T& data = T(), Node* p_left = 0, Node* p_right = 0)
    9.       :data(data), p_left(p_left), p_right(p_right){
    10.     }
    11.     T data;
    12.     Node* p_left;
    13.     Node* p_right;
    14.   }
    15.   Node* iter;
    16.   int size;
    17. public :
    18.   //Các phương thức sẽ ở đây
    19. };

    Ví dụ :
    sau đây là bài r2 đang làm và bị vướng nhiều lỗi rất khó chịu trong khi xử lý thậm chí là phép +, lý do là khó truy xuất đến được phần tử của class Node, dẫn đến buộc phải trả tham chiếu đến private của class HugeInt ( 1 idea hết sức tồi ) nhưng r2 nêu ra để chúng ta có cái nhìn thoáng hơn và có thể cài đặt hiểu quả hơn.
    Node.h
    C++ Code:
    1. #ifndef NODE_H
    2. #define NODE_H
    3.  
    4. #include <iostream>
    5.  
    6. struct Node{
    7.   int data;
    8.   Node* pLeft;
    9.   Node* pRight;
    10.  
    11.   Node(int data, Node* l, Node* r):data(data), pLeft(l), pRight(r){
    12.   }
    13.   Node():data(0), pLeft(0), pRight(0){
    14.   }
    15.     Node(int data):data(data),pLeft(0), pRight(0){
    16.     }
    17. };
    18.  
    19. #endif

    LinkedList.h
    C++ Code:
    1. #ifndef LINKEDLIST_HPP
    2. #define LINKEDLIST_HPP
    3.  
    4. #include "Node.h"
    5. #include <iostream>
    6.  
    7. class LinkedList{
    8. private:
    9.   Node*  pHead;
    10.   Node*  pTail;
    11.   int count;
    12. public:
    13.   LinkedList();
    14.   LinkedList(const LinkedList& x);
    15.     LinkedList& operator = (const LinkedList& x);
    16.   ~LinkedList();
    17.  
    18.   Node* get_head() const;
    19.   Node* get_tail() const;
    20.    
    21.     int get_data_at(const Node*& );
    22.  
    23.   void increase_count();
    24.   void decrease_count();
    25.  
    26.   void delete_at_head();
    27.   void delete_at_tail();
    28.  
    29.   void insert_at_head(int x);
    30.   void insert_at_tail(int x);
    31.  
    32.   void erase_all();
    33.   int get_count() const;
    34.   bool is_empty() const;
    35.  
    36.   void print_test_from_head(std::ostream& ) const;
    37.   void print_test_from_tail(std::ostream& ) const;
    38. };
    39.  
    40. #endif

    LinkedList.cpp
    C++ Code:
    1. #include "LinkedList.h"
    2. #include <iostream>
    3.  
    4. LinkedList::LinkedList():pHead(0), pTail(0), count(0){
    5. }
    6.  
    7. LinkedList::~LinkedList(){
    8.   Node* destroyer = pHead;
    9.   while(destroyer != NULL){
    10.       pHead = destroyer->pRight;
    11.       delete destroyer;
    12.       destroyer = pHead;
    13.   }
    14.   pHead = pTail = NULL;
    15.   std::cout << "Release Memory...\n";
    16. }
    17.  
    18. LinkedList::LinkedList(const LinkedList& x){
    19.   Node* new_copy;
    20.   Node* original = x.pHead;
    21.   if(original == NULL){
    22.     pHead = pTail = NULL;
    23.   }
    24.   else{
    25.     pHead = new_copy = new Node(original->data, 0, original->pRight);
    26.     while(original->pRight != NULL){
    27.         original = original->pRight;
    28.         new_copy->pRight = new Node(original->data, new_copy, original->pRight);
    29.         new_copy = new_copy->pRight;
    30.     }
    31.   }
    32.   pTail = x.pTail;
    33. }
    34.  
    35. LinkedList& LinkedList::operator = (const LinkedList& x){
    36.     this->erase_all();
    37.  
    38.     Node* new_copy;
    39.   Node* original = x.pHead;
    40.   if(original == NULL){
    41.     pHead = pTail = NULL;
    42.   }
    43.   else{
    44.     pHead = new_copy = new Node(original->data, 0, original->pRight);
    45.     while(original->pRight != NULL){
    46.         original = original->pRight;
    47.         new_copy->pRight = new Node(original->data, new_copy, original->pRight);
    48.         new_copy = new_copy->pRight;
    49.     }
    50.   }
    51.   pTail = x.pTail;
    52.     return *this;
    53. }
    54.  
    55. Node* LinkedList::get_head() const{
    56.   return pHead;
    57. }
    58. Node* LinkedList::get_tail() const{
    59.   return pTail;
    60. }
    61.  
    62. int LinkedList::get_count() const{
    63.   return count;
    64. }
    65.  
    66. void LinkedList::increase_count(){
    67.   count++;
    68. }
    69.  
    70. void LinkedList::decrease_count(){
    71.   count--;
    72. }
    73.  
    74. void LinkedList::delete_at_head(){
    75.   if(pHead == 0)
    76.     return;
    77.   else{
    78.       Node* q = pHead;
    79.       pHead = q->pRight;
    80.       pHead->pLeft = 0;
    81.       delete q;
    82.       decrease_count();
    83.   }
    84. }
    85.  
    86. void LinkedList::delete_at_tail(){
    87.   if(pTail == 0)
    88.     return;
    89.   else{
    90.     Node* q = pTail;
    91.     pTail = q->pLeft;
    92.     pTail->pRight = 0;
    93.     delete q;
    94.     count--;
    95.   }
    96. }
    97.  
    98. void LinkedList::insert_at_head(int x){
    99.   Node* new_node = new Node(x);
    100.   if(is_empty()){
    101.     pHead = pTail = new_node;
    102.   }
    103.   else{
    104.     new_node->pRight = pHead;
    105.         pHead = new_node;
    106.   }
    107.   count++;
    108. }
    109.  
    110. void LinkedList::insert_at_tail(int x){
    111.   Node* new_node = new Node(x);
    112.     if(is_empty()){
    113.         pHead = pTail = new_node;
    114.     }
    115.     else{
    116.         Node* old_tail = pTail;
    117.     pTail->pRight = new_node;
    118.         pTail = new_node;
    119.         pTail->pLeft = old_tail;
    120.         old_tail = NULL;
    121.     }
    122.     count++;
    123. }
    124.  
    125. void LinkedList::print_test_from_tail(std::ostream& oss)const{
    126.   Node* q = pHead;
    127.   while(q != 0){
    128.     oss << q->data << " ";
    129.     q = q->pRight;
    130.   }
    131.   std::cout << "\n\n";
    132. }
    133.  
    134. void LinkedList::print_test_from_head(std::ostream& oss)const{
    135.     Node* q = pTail;
    136.     if(q == 0){
    137.         std::cout << "...empty list.\n";
    138.         return;
    139.     }
    140.     else{
    141.         while(q != 0){
    142.             oss << q->data;
    143.             q = q->pLeft;
    144.         }
    145.         std::cout << "\n";
    146.     }
    147. }
    148.  
    149. void LinkedList::erase_all(){
    150.   while(!is_empty()){
    151.     delete_at_head();
    152.   }
    153. }
    154.  
    155. bool LinkedList::is_empty() const{
    156.   return count == 0;
    157. }
    158.  
    159. int LinkedList::get_data_at(const Node*& rhs){
    160.   return rhs->data;
    161. }

    HugeInt.cpp
    C++ Code:
    1. #include <iostream>
    2. #include "LinkedList.h"
    3. #include "Node.h"
    4. #include <cmath>
    5.  
    6. class HugeInt{
    7. private :
    8.   LinkedList numbers;
    9.   int sign;
    10. public :
    11.     HugeInt():sign(0){
    12.     }
    13.   LinkedList& ref_to_private(){
    14.     return numbers;
    15.   }
    16.   void print_private_data(){
    17.         numbers.print_test_from_head(std::cout);
    18.   }
    19.  
    20.   HugeInt& operator = (const HugeInt& rhs){
    21.     numbers = rhs.numbers;
    22.     sign = rhs.sign;
    23.     return *this;
    24.   }
    25.  
    26.   HugeInt operator + (HugeInt &rhs){
    27.     int length_of_left = this->ref_to_private().get_count();
    28.     int length_of_right = rhs.ref_to_private().get_count();
    29.        
    30.         /* Task :
    31.              - the the difference between 2 numbers
    32.              - calculate how many computations which is equal to the
    33.                number have the more digits.
    34.              -
    35.       */
    36.     int difference = abs(length_of_right - length_of_left);
    37.         int computations = length_of_right;
    38.  
    39.     if(difference != 0){
    40.             //if left hand side is longer
    41.             int digit;
    42.       if(length_of_right > length_of_left){
    43.         computations = length_of_right;
    44.         for(digit = 0; digit < difference; ++digit)
    45.           this->ref_to_private().insert_at_head(0);
    46.       }
    47.             //if right hand size is longer
    48.       else{
    49.         computations = length_of_left;
    50.         for(digit = 0; digit < difference; ++digit)
    51.           rhs.ref_to_private().insert_at_head(0);
    52.             }
    53.         }
    54.     /* Task :
    55.              - Calculate from left to right : get_tail take the right
    56.                approach
    57.              - Calculate base on these 2 tail of two number.
    58.              - Store all digits into a temporary call digits_arry[]
    59.              - Create a new HugeInt, inser all these numbers
    60.              - for this object.
    61.       */
    62.  
    63.         Node* left = this->ref_to_private().get_tail();
    64.     Node* right = rhs.ref_to_private().get_tail();
    65.         std::cout << "Computation = " << computations << "\n";
    66.     int* storing_digit = new int[computations + 1];
    67.  
    68.     int position;
    69.     int carry = 0;
    70.     int value;
    71.  
    72.     for(position = 0; position < computations; ++position){
    73.       value = left->data + right->data + carry;
    74.             storing_digit[position] = value;
    75.       if(value > 9){
    76.         value = value % 10;
    77.                 storing_digit[position] = value;
    78.         carry = 1;
    79.       }
    80.       else{
    81.         carry = 0;
    82.       }
    83.             //move to next digit from the right <-
    84.       left = left->pLeft;
    85.       right = right->pLeft;
    86.         }
    87.  
    88.     left = NULL;
    89.     right = NULL;
    90.         std::cout << "TESTING...\n";
    91.         for(int x = 0; x < computations; ++x){
    92.             std::cout << storing_digit[x] << "->";
    93.     }
    94.         std::cout << "\n";
    95.  
    96.     HugeInt result;
    97.     for(int x = 0; x < computations; ++x){
    98.       result.ref_to_private().insert_at_head(storing_digit[x]);
    99.     }
    100.         delete[] storing_digit;
    101.  
    102.         return result;
    103.   }
    104.  
    105.   friend std::istream& operator >> (std::istream& iss, HugeInt& rhs){
    106.     char stroke;
    107.         iss >> stroke;
    108.         if(stroke == '-')  rhs.sign = 1;
    109.         else               iss.get(stroke);
    110.         do{
    111.             rhs.numbers.insert_at_head(stroke - '0');
    112.             iss.get(stroke);
    113.         }while(isdigit(stroke));
    114.     return iss;
    115.   }
    116.   friend std::ostream& operator << (std::ostream& oss, HugeInt& rhs){
    117.         rhs.ref_to_private().print_test_from_head(oss);
    118.         return oss;
    119.   }
    120. };
    Đã được chỉnh sửa lần cuối bởi rox_rook : 05-04-2008 lúc 07:47 PM.

  3. #3
    Ngày gia nhập
    12 2006
    Nơi ở
    US
    Bài viết
    1,917

    T_T, đã có 1 chút ý tưởng, 4 sư phụ vẫn chưa ai lên T_T. Đại khái mình sẽ làm dàn bài thế này, và mai sẽ suy nghĩ kĩ hơn về bài số lớn áp dụng iterator thế nào cho hiệu quả, ai có idea thì cứ nêu ra nhé.

    Ta sẽ có 1 class LinkList tương tự như 1 class vector sau đây :
    vector.hpp
    C++ Code:
    1. namespace cv{
    2.   template <typename T>
    3.   class vector{
    4.   protected:
    5.     int v_size;
    6.     T*  data;
    7.   public:
    8.     class iterator{
    9.     friend class vector;
    10.     private :
    11.       vector<T>& iter;
    12.       int index;
    13.     public :
    14.       iterator(vector<T>& rhs):iter(rhs), index(0){
    15.       }
    16.       iterator(vector<T>& rhs, bool):iter(rhs), index(rhs.size() - 1){
    17.       }
    18.       T operator*()const{
    19.         return iter.vector[index];
    20.       }
    21.       T operator++(){
    22.         if(index > iter.v_size){
    23.           iter.resize(v_size * 2);
    24.         }
    25.         return iter.data[++index];
    26.       }
    27.       T operator++(int ){
    28.         if(index > iter.v_size){
    29.           iter.resize(v_size * 2);
    30.         }
    31.         return iter.data[index++];
    32.       }
    33.       iterator& operator+=(int step){
    34.         if(step > iter.v_size()){
    35.           resize(v_size * 4);
    36.         }
    37.         index += step;
    38.         return *this;
    39.       }
    40.  
    41.       bool operator==(const iterator& rhs) const{
    42.         return index == rhs.index;
    43.       }
    44.       bool operator!=(const iterator& rhs) const{
    45.         return index != rhs.index;
    46.       }
    47.       friend
    48.       std::ostream operator<<(std::ostream& oss, const iterator& iter){
    49.         return oss << *iter;
    50.       }
    51.     };
    52.  
    53.     vector(int v_size = DEFAULT_SIZE);
    54.     virtual ~vector();
    55.     vector& operator=(const vector<T>& );
    56.     int size() const;
    57.     T*  get_data() const;
    58.     void resize(int );
    59.  
    60.     void push_back(const T& x);
    61.     void push_front(const T& x);
    62.     void pop_front();
    63.     void pop_back();
    64.  
    65.     T& operator[](int );
    66.     const T& operator[](int ) const;
    67.  
    68.     iterator begin(){
    69.       return iterator(*this);
    70.     }
    71.     iterator end(){
    72.       return iterator(*this, true);
    73.     }
    74.   };
    75. ...

    vector.cpp
    C++ Code:
    1. template<typename T> vector<T>::vector(int v_size)
    2.     :v_size(v_size),data(new T[v_size]){
    3.   }
    4.  
    5.   template<typename T> vector<T>::~vector(){
    6.     delete[] data;
    7.   }
    8.  
    9.   template<typename T> T* vector<T>::get_data()const{
    10.     return data;
    11.   }
    12.  
    13.   template <typename T> vector<T>& vector<T>::operator=(const vector<T> &rhs){
    14.     resize(rhs.v_size);
    15.     for (int x = 0; x < v_size; ++x)
    16.       data[x] = rhs[x];
    17.     return *this;
    18.   }
    19.  
    20.   template <typename T> void vector<T>::resize(int new_size) {
    21.     if(new_size == v_size)
    22.       return;
    23.     T *arry = new T[new_size];
    24.     if(new_size < v_size){
    25.       for(int x = 0; x < new_size; ++x)
    26.         arry[x] = data[x];
    27.     }
    28.     else if(new_size > v_size){
    29.       for(int x = 0; x < new_size; ++x)
    30.         arry[x] = x < v_size ? data[x] : T();
    31.     }
    32.     delete[] data;
    33.     data = arry;
    34.     v_size = new_size;
    35.   }
    36.   template <typename T> T& vector<T>::operator[](int position) {
    37.     if((position + 1) > v_size)
    38.       resize(v_size * 2);
    39.     return data[position];
    40.   }
    41.   template <typename T> const T& vector<T>::operator[](int position) const{
    42.     assert(position < v_size);
    43.     return data[position];
    44.   }
    45.  
    46.   template <typename T> int vector<T>::size() const{
    47.     return v_size;
    48.   }
    49.  
    50.   template <typename T> void vector<T>::push_back(const T& item){
    51.     resize(v_size + 1);
    52.     data[v_size - 1] = item;
    53.   }
    54.  
    55.   template <typename T> void vector<T>::push_front(const T& item){
    56.     resize(v_size + 1);
    57.     T hold = data[0];
    58.     for(int x = 1; x < v_size - 2; ++x){
    59.       data[x] = data[x + 1];
    60.     }
    61.     data[0] = item;
    62.   }
    63.   //Vẫn còn 2 method chưa viết xong T_T
    64.   //template <typename T> void vector<T>::pop_front(){}
    65.   //template <typename T> void vector<T>::pop_back(){}
    66. }//close namespace cv here !

    main.cpp
    C++ Code:
    1. int main(){
    2.   cv::vector<int> vect;
    3.   cv::vector<int>::iterator it = vect.begin();
    4.   for(int x = 0; x < 5; ++x){
    5.     vect.push_back(x);
    6.   }
    7.   for(int x = 0; x < 5; ++x){
    8.     std::cout << vect[x] << " -> ";
    9.   }
    10.  
    11.   return 0;
    12. }

  4. #4
    Ngày gia nhập
    10 2007
    Nơi ở
    Gameloft studio
    Bài viết
    175

    Đã xem qua bài HugeInt của rook.
    Đúng là thử nhiều cách nhưng ht vẫn bó tay, vẫn chưa tìm cách nào khắc phục với việc không phải sử dụng hàm
    C++ Code:
    1.  LinkedList& ref_to_private(){
    2.     return numbers;
    3.   }
    Nhưng qua bài ông anh, ht có chỉnh sửa hàm tính + cho gọn lại. Nhưng chưa test lại đúng sai thế nào (máy hư vài bữa nay, đang đem đi sửa), cứ post lên đây, có gì ông anh xem lại ha
    C++ Code:
    1. HugeInt operator + (HugeInt &rhs){
    2.     Node* left = this->ref_to_private().get_tail();
    3.     Node* right = rhs.ref_to_private().get_tail();
    4.     int carry = 0;
    5.     int value=0;
    6.  
    7.     HugeInt result;
    8.     while(left!=0 || right!=0){    
    9.         if(left!=0) value+=left->data;
    10.         if(right!=0)value+=right->data;
    11.         value+=carry;
    12.         if(value > 9){
    13.             value = value % 10;
    14.             carry = 1;
    15.         }
    16.         else{
    17.             carry = 0;
    18.         }
    19.         result.ref_to_private().insert_at_head(value);
    20.             //move to next digit from the right <-
    21.         left = left->pLeft;
    22.         right = right->pLeft;
    23.     }
    24.     return result;
    25. }
    Không biết ghi gì luôn ...

  5. #5
    Ngày gia nhập
    12 2006
    Nơi ở
    US
    Bài viết
    1,917

    - Tình hình hiện h là đã đang và viết hết 2 ngày rùi mà chưa xong class LIST T_T. Anh hi vọng tối nay có thể xong dàn bài chi tiết, trước khi anh và em cùng thảo luận về bài số lớn, vì class List ban đầu là quá tồi design.
    - Muốn truy xuất hay lấy link đều trở nên quá khó khăn
    - Dẫn đến có bug thì khóc tiếng tàu.
    - Anh đang cài đặt theo hướng của list STL, tức là ta có 1 friend class iterator -> và anh nghĩ dựa vào thằng này ta có thể dễ dàng xử bài số lớn đó.
    - baby hiện đã rút lui, nên chỉ còn em và iamtvn. Cho nên cứ từ từ cũng được.
    - Em có idea gì thoải mái tung ra, T_T nhé !
    Đã xem qua bài HugeInt của rook.
    Đúng là thử nhiều cách nhưng ht vẫn bó tay, vẫn chưa tìm cách nào khắc phục với việc không phải sử dụng hàm
    1 cách giải quyết vấn đề này anh nghĩ sẽ tạo friend class. Khi xong anh sẽ post dàn bài chi tiết hơn. !

  6. #6
    Ngày gia nhập
    10 2007
    Nơi ở
    Gameloft studio
    Bài viết
    175

    Mặc định [C++] Cấu trúc dữ liệu với link list

    Spam một tí: thấy lâu rồi mà chưa có gì nữa àh.
    Mà hình như chỉ có ht với rook thì phải, kidkidiamtvn đâu mất tăm rồi.
    Không biết ghi gì luôn ...

  7. #7
    Ngày gia nhập
    08 2006
    Nơi ở
    TpHCM
    Bài viết
    202

    Các cấu trúc mà rok_rook xây dựng vẫn còn 1 chỗ dở, đó là rời rạc nhau, ví dụ iterator của linkedlist và vector chẳng liên quan gì với nhau. Nên làm cho chúng có mối liên quan với nhau, ví dụ thừa kế từ cùng 1 class cha chẳng hạn

    Cậu có thể nghĩ thêm 1 chút là làm sao biết được iterator nào là Forward Iterator, và iterator nào là Bidirectional Iterator hay RandomaccessIterator
    Tức là nên nghĩ rộng hơn cho cả library hoặc hơn nữa chứ đừng bó hẹp trong class cậu đang viết, ví dụ như ta có thể làm được điều này

    sort(Iterator iter1, Iterator iter2);
    1 method sort chung cho tất cả. Trong đó iter1, iter2 có thể là iterator của linked list, vector hay bất kể là của cấu trúc gì trong lib

    thay vì phải viết 2 method rời rạc
    method sort cho vector, method sort cho linkedlist

    Ví dụ là thế thôi, cậu có thể tưởng tượng ra nhiều thứ nữa

  8. #8
    Ngày gia nhập
    12 2006
    Nơi ở
    US
    Bài viết
    1,917

    - Thanks ý kiến của anh ạ T_T.
    - Cái bài vector đó thì chẳng có liên quan gì đến linklist anh à em chỉ nghĩ tương tự như vector mà thui T_T. Và dạo này cũng đang bí lù vì cách xử lý template. Viết generic code đúng là chua như dấm.
    Cậu có thể nghĩ thêm 1 chút là làm sao biết được iterator nào là Forward Iterator, và iterator nào là Bidirectional Iterator hay RandomaccessIterator
    Tức là nên nghĩ rộng hơn cho cả library hoặc hơn nữa chứ đừng bó hẹp trong class cậu đang viết, ví dụ như ta có thể làm được điều này
    Thanks anh, em sẽ suy nghĩ thử về idea này.

  9. #9
    Ngày gia nhập
    01 2009
    Bài viết
    201

    Dùng danh sách liên kết mà khong thấy cậu sử dụng thành quả của STL thì hơi phí ,gọn nhẹ,không mất công xây dựng lại ...

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

    mình mới code xong cái AVL template, post vào đây cho hợp chủ đề

    AVL_Node.h
    C++ Code:
    1. ////////////////////////////////////////////////////
    2. #ifndef AVL_NODE_H
    3. #define AVL_NODE_H
    4. ////////////////////////////////////////////////////
    5. //forward declaration
    6. template<class KeyType> class AVL_Tree;
    7. ////////////////////////////////////////////////////
    8. enum NodeStatus
    9. {
    10.     EH, //even high
    11.     LH, //left high
    12.     RH  //right hight
    13. };
    14.  
    15. enum NodeStructure
    16. {
    17.     LO, //left only
    18.     RO, //right only
    19.     LR, //left + right
    20.     NONE
    21. };
    22. ////////////////////////////////////////////////////
    23. template<class KeyType>
    24. class AVL_Node
    25. {
    26. public:
    27.     typedef AVL_Node* PNODE;
    28. private:
    29.     PNODE left;
    30.     PNODE right;
    31.     KeyType key;
    32.     NodeStatus stat;
    33. public:
    34.     AVL_Node();
    35.     AVL_Node(const KeyType&);
    36.     //AVL_Node(const AVL_Node&);
    37.     NodeStructure getStruct()const;
    38.     friend class AVL_Tree<KeyType>;
    39. };
    40. ////////////////////////////////////////////////////
    41. template<class KeyType>
    42. inline AVL_Node<KeyType>::AVL_Node():left(0),right(0),stat(EH)
    43. {   }
    44. ////////////////////////////////////////////////////
    45. template<class KeyType>
    46. inline AVL_Node<KeyType>::AVL_Node(const KeyType& k):left(0),right(0),stat(EH),key(k)
    47. {   }
    48. ////////////////////////////////////////////////////
    49. template<class KeyType>
    50. inline NodeStructure AVL_Node<KeyType>::getStruct()const
    51. {
    52.     if(!left && !right)
    53.         return LR;
    54.     if(!left)
    55.         return LO;
    56.     if(!right)
    57.         return RO;
    58.     return NONE;
    59. }
    60. ////////////////////////////////////////////////////
    61. #endif
    62. ////////////////////////////////////////////////////

    AVL_Tree.h
    C++ Code:
    1. ////////////////////////////////////////////////////
    2. #ifndef AVL_H
    3. #define AVL_H
    4. ////////////////////////////////////////////////////
    5. #include<iostream>
    6. #include<stdarg.h>
    7. #include "AVLNode.h"
    8. ////////////////////////////////////////////////////
    9. template<class KeyType>
    10. class AVL_Tree
    11. {
    12. public:
    13.     typedef typename AVL_Node<KeyType>::PNODE PNODE;
    14. private:
    15.      PNODE root;
    16.      void traverseNLR(const PNODE&) const;
    17.      PNODE searchHelper(const PNODE& ,const KeyType& )const;
    18.      int insertHelper(PNODE& ,const KeyType&);
    19.      int removeHelper(PNODE& ,const KeyType&);
    20.      int searchStandFor(PNODE&,PNODE&);
    21.      void destroyHelper(PNODE&);
    22.      int balanceLeft(PNODE&);
    23.      int balanceRight(PNODE&);
    24.      void rotateLL(PNODE&);
    25.      void rotateRR(PNODE&);
    26.      void rotateLR(PNODE&);
    27.      void rotateRL(PNODE&);
    28.      int computeHeightHelper(const PNODE&)const;
    29.      void copyTree(PNODE&,const PNODE&);
    30.      bool isSameStructure(const PNODE& ,const PNODE&)const;
    31.      bool isTotallySame(const PNODE& ,const PNODE&)const;
    32.  
    33. public:
    34.     AVL_Tree();
    35.     ~AVL_Tree();
    36.     AVL_Tree(const AVL_Tree& );
    37.     const AVL_Tree& operator = (const AVL_Tree&);
    38.     bool operator == (const AVL_Tree& );
    39.     bool operator != (const AVL_Tree& );
    40.     PNODE createNode(const KeyType&);
    41.     void insert(const KeyType&);
    42.     void remove(const KeyType&);
    43.     void traverseNLR() const;
    44.     void destroyTree();
    45.     PNODE search(const KeyType& ) const;
    46.     int computeHeight()const;
    47.     void multiInsert(int,...);
    48. };
    49. ////////////////////////////////////////////////////
    50. template<class KeyType>
    51. inline AVL_Tree<KeyType>::AVL_Tree():root(0)
    52. {   }
    53. ////////////////////////////////////////////////////
    54. template<class KeyType>
    55. inline AVL_Tree<KeyType>::~AVL_Tree()
    56. {
    57.     destroyHelper(root);
    58. }
    59. ////////////////////////////////////////////////////
    60. template<class KeyType>
    61. inline typename AVL_Tree<KeyType>::PNODE            //return type using template typedef require 'typename'
    62. AVL_Tree<KeyType>::createNode(const KeyType& k)
    63. {
    64.     PNODE a = new AVL_Node<KeyType>(k);
    65.     if(!a)
    66.     {
    67.         std::cout<<"Out of memory!";
    68.         exit(1);
    69.     }
    70.     return a;
    71. }
    72. ////////////////////////////////////////////////////
    73. template<class KeyType>
    74. inline int AVL_Tree<KeyType>::insertHelper(PNODE& node,const KeyType& k)
    75. {
    76.     if(!node)
    77.     {
    78.         node = createNode(k);
    79.         return 2;
    80.     }
    81.  
    82.     int result;
    83.    
    84.     if(node->key == k)
    85.         return 0;   //duplicate value
    86.     if(node->key > k)
    87.     {
    88.         result = insertHelper(node->left,k);
    89.         if(result < 2)
    90.             return result;  //success or duplicate
    91.         switch(node->stat)  //the height is increase..
    92.         {
    93.         case RH:
    94.             node->stat = EH;
    95.             return 1;
    96.         case EH:
    97.             node->stat = LH;
    98.             return 2;
    99.         case LH:
    100.             balanceLeft(node);
    101.             return 1;
    102.         }
    103.     }//end if
    104.     else
    105.     {
    106.         result = insertHelper(node->right,k);
    107.         if(result<2)
    108.             return result;
    109.         switch(node->stat)
    110.         {
    111.         case LH:
    112.             node->stat = EH;
    113.             return 1;
    114.         case EH:
    115.             node->stat = RH;
    116.             return 2;
    117.         case RH:
    118.             balanceRight(node);
    119.             return 1;
    120.         }
    121.     }//end else
    122.     return result;//avoid warning
    123. }
    124. ////////////////////////////////////////////////////
    125. template<class KeyType>
    126. inline void AVL_Tree<KeyType>::insert(const KeyType& k)
    127. {
    128.     insertHelper(root,k);
    129. }
    130. ////////////////////////////////////////////////////
    131. template<class KeyType>
    132. inline int AVL_Tree<KeyType>::balanceLeft(PNODE& node)
    133. {
    134.     switch(node->left->stat)
    135.     {
    136.     case LH:
    137.         rotateLL(node);
    138.         return 2;       //when remove a node and the height was decreased
    139.     case EH:
    140.         rotateLL(node);
    141.         return 1;
    142.     case RH:
    143.         rotateLR(node);
    144.         return 2;
    145.     }
    146.     return 0;
    147. }
    148. ////////////////////////////////////////////////////
    149. template<class KeyType>
    150. inline int AVL_Tree<KeyType>::balanceRight(PNODE& node)
    151. {
    152.     switch(node->right->stat)
    153.     {
    154.     case LH:
    155.         rotateRL(node);
    156.         return 2;
    157.     case EH:
    158.         rotateRR(node);
    159.         return 1;
    160.     case RH:
    161.         rotateRR(node);
    162.         return 2;
    163.     }
    164.     return 0;
    165. }
    166. /////////////////////////////////////////////////////
    167. template<class KeyType>
    168. inline void AVL_Tree<KeyType>::rotateLL(PNODE& node)
    169. {
    170.     PNODE leftOfNode = node->left;
    171.     node->left = leftOfNode->right;
    172.     leftOfNode->right = node;
    173.     switch(leftOfNode->stat)
    174.     {
    175.     case LH:
    176.         leftOfNode->stat = EH;
    177.         node->stat = EH;
    178.         break;
    179.     case EH:    //only happen when delete a node
    180.         node->stat = LH;
    181.         leftOfNode->stat = RH;
    182.         break;
    183.     }
    184.  
    185.     node = leftOfNode;
    186. }
    187. ////////////////////////////////////////////////////
    188. template<class KeyType>
    189. inline void AVL_Tree<KeyType>::rotateRR(PNODE& node)
    190. {
    191.     PNODE rightOfNode = node->right;
    192.     node->right = rightOfNode->left;
    193.     rightOfNode->left = node;
    194.     switch(rightOfNode->stat)
    195.     {
    196.     case RH:
    197.         rightOfNode->stat = EH;
    198.         node->stat = EH;
    199.         break;
    200.     case EH:                           
    201.         node->stat = RH;
    202.         rightOfNode->stat = LH;
    203.         break;
    204.     }
    205.  
    206.     node = rightOfNode;
    207. }
    208. ////////////////////////////////////////////////////
    209. template<class KeyType>
    210. inline void AVL_Tree<KeyType>::rotateLR(PNODE& node)
    211. {
    212.     PNODE leftOfNode = node->left;
    213.     PNODE rightOfLeft = leftOfNode->right;
    214.  
    215.     node->left = rightOfLeft->right;
    216.     rightOfLeft->right = node;
    217.  
    218.     leftOfNode->right = rightOfLeft->left;
    219.     rightOfLeft->left = leftOfNode;
    220.  
    221.     switch(rightOfLeft->stat)
    222.     {
    223.     case LH:
    224.         node->stat = RH;
    225.         leftOfNode->stat = EH;
    226.         break;
    227.     case EH:
    228.         node->stat = EH;
    229.         leftOfNode->stat = EH;
    230.         break;
    231.     case RH:
    232.         node->stat = EH;
    233.         leftOfNode->stat = LH;
    234.         break;
    235.     }
    236.    
    237.     rightOfLeft->stat = EH;
    238.     node = rightOfLeft;
    239. }
    240. ////////////////////////////////////////////////////
    241. template<class KeyType>
    242. inline void AVL_Tree<KeyType>::rotateRL(PNODE& node)
    243. {
    244.     PNODE rightOfNode = node->right;
    245.     PNODE leftOfRight = rightOfNode->left;
    246.  
    247.     node->right = leftOfRight->left;
    248.     leftOfRight->left = node;
    249.  
    250.     rightOfNode->left = leftOfRight->right;
    251.     leftOfRight->right = rightOfNode;
    252.  
    253.     switch(leftOfRight->stat)
    254.     {
    255.     case RH:
    256.         node->stat = LH;
    257.         rightOfNode->stat = EH;
    258.         break;
    259.     case EH:
    260.         node->stat = EH;
    261.         rightOfNode->stat = EH;
    262.         break;
    263.     case LH:
    264.         node->stat = EH;
    265.         rightOfNode->stat = RH;
    266.         break;
    267.     }
    268.    
    269.     leftOfRight->stat = EH;
    270.     node = leftOfRight;
    271. }
    272. ////////////////////////////////////////////////////
    273. template<class KeyType>
    274. inline void AVL_Tree<KeyType>::traverseNLR() const
    275. {
    276.     traverseNLR(root);
    277. }
    278. ////////////////////////////////////////////////////
    279. template<class KeyType>
    280. inline void AVL_Tree<KeyType>::traverseNLR(const PNODE& node) const
    281. {
    282.     if(node)
    283.     {
    284.         std::cout<<"Key: "<<node->key<<" Address: "<<node<<"\n";
    285.         traverseNLR(node->left);
    286.         traverseNLR(node->right);
    287.     }
    288. }
    289. ////////////////////////////////////////////////////
    290. template<class KeyType>
    291. inline int AVL_Tree<KeyType>::removeHelper(PNODE& node,const KeyType& k)
    292. {
    293.     int result;
    294.     if(!node)
    295.         return 0;//doesn't exist key k
    296.  
    297.     if(node->key > k)
    298.     {
    299.         result = removeHelper(node->left,k);
    300.  
    301.         if( result < 2 )
    302.             return result;
    303.  
    304.         switch(node->stat)
    305.         {
    306.         case LH:
    307.             node->stat = EH;
    308.             return 2;
    309.         case EH:
    310.             node->stat = RH;
    311.             return 1;
    312.         case RH:
    313.             return balanceRight(node);
    314.         }
    315.     }//end if
    316.  
    317.     if(node->key < k)
    318.     {
    319.         result = removeHelper(node->right,k);
    320.         if(result<2)
    321.             return result;
    322.  
    323.         switch(node->stat)
    324.         {
    325.         case RH:
    326.             node->stat = EH;
    327.             return 2;
    328.         case EH:
    329.             node->stat = LH;
    330.             return 1;
    331.         case LH:
    332.             return balanceLeft(node);
    333.         }
    334.     }//end if
    335.  
    336.     //if node->key == k
    337.     PNODE p = node;
    338.     if(node->left == 0)
    339.     {
    340.         node = node->right;
    341.         result = 2;
    342.     }
    343.     else
    344.         if(node->right == 0)
    345.         {
    346.             node = node->left;
    347.             result = 2;
    348.         }
    349.         else
    350.         {
    351.             result = searchStandFor(p,node->right);
    352.             delete p;
    353.             if(result<2)
    354.                 return result;
    355.             switch(node->stat)
    356.             {
    357.             case RH:
    358.                 node->stat = EH;
    359.                 return 2;
    360.             case EH:
    361.                 node->stat = LH;
    362.                 return 1;
    363.             case LH:
    364.                 return balanceLeft(node);
    365.             }
    366.         }
    367.     delete p;
    368.     return result;
    369. }
    370. ////////////////////////////////////////////////////
    371. template<class KeyType>
    372. inline int AVL_Tree<KeyType>::searchStandFor(PNODE& standFor,PNODE& node)//left-most of node
    373. {
    374.     int result=0;
    375.     if(node->left)
    376.     {
    377.         result = searchStandFor(standFor,node->left);
    378.         if(result < 2)
    379.             return result;
    380.         switch(node->stat)
    381.         {
    382.         case LH:
    383.             node->stat = EH;
    384.             return 2;
    385.         case EH:
    386.             node->stat = RH;
    387.             return 1;
    388.         case RH:
    389.             return balanceRight(node);
    390.         }
    391.     }
    392.     else
    393.     {
    394.         standFor->key = node->key;
    395.         standFor = node;
    396.         node = node->right;
    397.         return 2;
    398.     }
    399.     return result;
    400. }
    401. ////////////////////////////////////////////////////
    402. template<class KeyType>
    403. inline void AVL_Tree<KeyType>::remove(const KeyType& k)
    404. {
    405.     removeHelper(root,k);
    406. }
    407. ////////////////////////////////////////////////////
    408. template<class KeyType>
    409. inline void AVL_Tree<KeyType>::destroyTree()
    410. {
    411.     destroyHelper(root);
    412. }
    413. ////////////////////////////////////////////////////
    414. template<class KeyType>
    415. inline void AVL_Tree<KeyType>::destroyHelper(PNODE& node)
    416. {
    417.     if(node)
    418.     {
    419.         destroyHelper(node->left);
    420.         destroyHelper(node->right);
    421.         delete node;
    422.     }
    423. }
    424. ////////////////////////////////////////////////////
    425. template<class KeyType>
    426. inline typename AVL_Tree<KeyType>::PNODE
    427. AVL_Tree<KeyType>::searchHelper(const PNODE& node,const KeyType& k)const
    428. {
    429.     if(node)
    430.     {
    431.         if(node->key == k)
    432.             return node;
    433.         if(node->key>k)
    434.             return searchHelper(node->left,k);
    435.         else
    436.             return searchHelper(node->right,k);
    437.     }
    438.     return 0;
    439. }
    440. ////////////////////////////////////////////////////
    441. template<class KeyType>
    442. inline typename AVL_Tree<KeyType>::PNODE
    443. AVL_Tree<KeyType>::search(const KeyType& k)const
    444. {
    445.     return searchHelper(root,k);
    446. }
    447.  
    448. ////////////////////////////////////////////////////
    449. template<class KeyType>
    450. inline int AVL_Tree<KeyType>::computeHeightHelper(const PNODE& node)const
    451. {
    452.     if(!node)
    453.         return 0;
    454.     int leftHeight = computeHeightHelper(node->left);
    455.     int rightHeight = computeHeightHelper(node->right);
    456.     return leftHeight>rightHeight?leftHeight+1:rightHeight+1;
    457. }
    458. ////////////////////////////////////////////////////
    459. template<class KeyType>
    460. inline int AVL_Tree<KeyType>::computeHeight()const
    461. {
    462.     return computeHeightHelper(root);
    463. }
    464. ////////////////////////////////////////////////////
    465. template<class KeyType>
    466. inline AVL_Tree<KeyType>::AVL_Tree(const AVL_Tree& copy)
    467. {
    468.     copyTree(root,copy.root);
    469. }
    470. ////////////////////////////////////////////////////
    471. template<class KeyType>
    472. inline void AVL_Tree<KeyType>::copyTree(PNODE& node,const PNODE& copyNode)
    473. {
    474.     if(copyNode)
    475.     {
    476.         node = createNode(copyNode->key);
    477.         copyTree(node->left,copyNode->left);
    478.         copyTree(node->right,copyNode->right);
    479.     }
    480.     else
    481.         node = 0;
    482. }
    483. ////////////////////////////////////////////////////
    484. template<class KeyType>
    485. inline const AVL_Tree<KeyType>& AVL_Tree<KeyType>::operator = (const AVL_Tree<KeyType>& source)
    486. {
    487.     if(this!=&source)
    488.     {
    489.         destroyTree();
    490.         copyTree(root,source.root);
    491.     }
    492.     return *this;
    493. }
    494.  
    495. ////////////////////////////////////////////////////
    496. template<class KeyType>
    497. bool AVL_Tree<KeyType>::isSameStructure(const PNODE& lhs,const PNODE&rhs)const
    498. {
    499.     if(lhs == rhs)
    500.         return true;
    501.     if(lhs != rhs && (lhs == 0 || rhs == 0))
    502.         return false;
    503.     if(lhs->getStruct() == rhs->getStruct() )
    504.         return isSameStructure(lhs->left,rhs->left) && isSameStructure(lhs->right,rhs->right);
    505.     return false;
    506. }
    507. ////////////////////////////////////////////////////
    508. template<class KeyType>
    509. bool AVL_Tree<KeyType>::isTotallySame(const PNODE& lhs,const PNODE&rhs)const
    510. {
    511.     if(lhs == rhs)
    512.         return true;
    513.     if(lhs != rhs && (lhs == 0 || rhs == 0))
    514.         return false;
    515.     if(lhs->getStruct() == rhs->getStruct() && lhs->key == rhs->key )
    516.         return isTotallySame(lhs->left,rhs->left) && isTotallySame(lhs->right,rhs->right);
    517.     return false;
    518. }
    519. ////////////////////////////////////////////////////
    520. template<class KeyType>
    521. inline bool AVL_Tree<KeyType>::operator == (const AVL_Tree<KeyType>& rhs)
    522. {
    523.     return isTotallySame(this->root,rhs.root);
    524. }
    525. ////////////////////////////////////////////////////
    526. template<class KeyType>
    527. inline bool AVL_Tree<KeyType>::operator != (const AVL_Tree<KeyType>& rhs)
    528. {
    529.     return !isTotallySame(this->root,rhs.root);
    530. }
    531. ////////////////////////////////////////////////////
    532. template<class KeyType>
    533. inline void AVL_Tree<KeyType>::multiInsert(int numOfArgs,...)
    534. {
    535.     va_list ap;
    536.     int i;
    537.     va_start(ap,numOfArgs);
    538.         for(i = 0;i<numOfArgs;++i)
    539.             insert(va_arg(ap,KeyType));
    540.     va_end(ap);
    541. }
    542. ////////////////////////////////////////////////////
    543. #endif
    544. ////////////////////////////////////////////////////
    code ra gió bão

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

  1. Bài tập C++ Sử dụng cấu trúc dữ liệu kiểu list trong thư viện chuẩn STL để đọc dữ liệu từ file
    Gửi bởi yeulamvietnam 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: 12-11-2011, 05:33 PM
  2. Hướng dẫn mình code sửa thông tin của 1 nhân viên trog link list cái
    Gửi bởi quicksilver89 trong diễn đàn Nhập môn lập trình C/C++
    Trả lời: 2
    Bài viết cuối: 19-04-2009, 10:18 PM
  3. Hàm sắp xếp trog link list, check dùm mình hàm này với?
    Gửi bởi quicksilver89 trong diễn đàn Nhập môn lập trình C/C++
    Trả lời: 2
    Bài viết cuối: 19-04-2009, 11:19 AM
  4. Danh sách liên kết | bài tập link list có lỗi làm sao sửa?
    Gửi bởi quicksilver89 trong diễn đàn Nhập môn lập trình C/C++
    Trả lời: 6
    Bài viết cuối: 16-04-2009, 04:16 PM
  5. [ Solved ] Cấu trúc dữ liệu và giải thuật-Link List
    Gửi bởi Nemo_wf 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-09-2008, 12:40 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