容器‎ > ‎

cxxlAvl_Tree

AVL Tree 是一種平衝樹,搜尋次數維時在 O(logN) 之內,很適合作為以搜尋物件為主要目的的容器,cxxlAVL_Tree 也是為 cxxlObject 量身訂做的容器。

cxxlAvl_Tree 是虛擬 class,所以不能直接使用,cxxlAvl_Tree 類別宣告如下:

/*
  T = 要包裝的物件型別,須是 cxxlObject 的延伸類別
  K = Key 值,作為識別用
  isUnique = Key 值若不可重複設為 true,否則為 false
*/
template <typename T, typename K, bool isUnique>
class cxxlAVL_Tree:virtual public cxxlObjec

cxxlAvl_Tree 建構函數宣告如下:

cxxlAVL_Tree(ISpirit *spirit = Spirit_Easy)
以下列出 cxxlAvl_Tree 提供的功能:
 

基本功能

GetCount() 取得物件的個數
ClearAll() 放棄持有所有物件
Add(const Smart_Ptr<T> &addObj, K addKey) 放入一個物件,回傳值只對 Unique Tree 才有用,若這是 Unique Tree 且 addKey 已有存在則會回復 false
Delete(K delKey) 刪除(放棄持有)指定的物件,找不到 或 空的 傳回 false
Pump(K findKey) 取回並移除指定的物件,找不到 或 空的 傳回的智慧指標包裹的是 NULL,可用 Smart_Ptr::isNULL() 檢查
GetObj(K findKey) 取得含指定的物件的智慧指標,找不到 或 空的 傳回的智慧指標包裹的是 NULL,可用 Smart_Ptr::isNULL() 檢查
isLeftAt(K O_Key,K addKey) 虛擬函數,排序檢測,延伸類別須實作此函數,要讓 O_Key 鍵值所代表的物件排在 左 回答 true,否則 false
isEqual(K O_Key,K findKey) 虛擬函數,延伸類別須實作此函數,用來決定在容器中 O_Key 鍵值所代表的物件,是不是 findKey 所要尋找的,是 回答 true,否則 false

巡行功能

cxxlAVL_Tree 在搜尋上是個很棒的容器,但用在巡行上就不見得那麼有效率,尤其 cxxlAVL_Tree 可用在多執行緒上就更行複雜。與其直接對 cxxlAVL_Tree 巡行,不如把物件另外包裹到 cxxlList 來得簡單,由於採用此策略,這個巡行用的 cxxlList 和來源 cxxlAVL_Tree 便成為兩個各自獨立的容器,各別對容器增刪物件皆互不影響,不過內含的物件還是共享的(即相同的物件),還有包裹到 cxxlList 的物件是從 cxxlAVL_Tree 中由左而右依序取得(即已經排序好的)。

cxxlList_Create() 將所有物件放入一個串列物件後傳回
cxxlList_Create(K filterKey) 將符合過濾條件的物件放入一個串列物件後傳回
cxxlList_CreateFilter(K O_Key, K filterKey) 虛擬函數,若會被叫用有過濾的 cxxlList_Create() 須覆載此函數,條件符合 回答 true,否則 false

自我複製

Clone() 自我複製,傳回相同內容的同類形容器物件
CreateSelf(ISpirit *spirit) 虛擬函數,Clone() 時用來產生延伸類別的物件,所以會被用到 Clone(),延伸類別就必須覆載此函數

 

範例一

#include <iostream>
#include <time.h>
#include <CXXLAVLTREE.HPP>
using namespace std;
using namespace CxxlMan; 
class A:virtual public cxxlObject
{ 
  int m_i;
public:
  A(int i)
    : cxxlObject(Spirit_Urgent),
  {
    m_i = i;
  }
  virtual ~A()
  {
  }
  int Get() const
  {
    return m_i;
  }
};
// 包裹 A 物件,採用 int 為 key,key 值可重複
class MyTree:public cxxlAVL_Tree<A,int,false>
{
  // 排序檢測,延伸類別須實作此函數
  // 要讓 O_Key 鍵值所代表的物件排在 左 回答 true,否則 false
  bool cxxlFASTCALL isLeftAt(int O_Key,int addKey) const
  {
    return O_Key <= addKey;
  } 
   
  // 這函數用來決定在容器中 O_Key 鍵值所代表的物件,是不是 findKey 所要尋找的 
  // 是 回答 true,否則 false,延伸類別須實作此函數
  bool cxxlFASTCALL isEqual(int O_Key,int findKey)  const
  {
    return O_Key == findKey;
  } 
   
  // cxxlList_Create(K filterKey) 要用的過濾條件,延伸類別須覆寫此函數
  // 條件符合 回答 true,否則 false
  bool cxxlFASTCALL cxxlList_CreateFilter(int O_Key,int filterKey) const
  {
    return O_Key > filterKey;
  } 
   
  // Clone() 時用來產生延伸類別的物件
  // 所以延伸別必須覆載
  MyTree *cxxlFASTCALL CreateSelf(ISpirit *spirit) const
  {
    return new MyTree;
  }
public:
  MyTree(ISpirit *spirit = Spirit_Easy)  // Constructor
   :cxxlObject(spirit)
  {
  }
};
int main(int argc, char* argv[])
{
  srand((unsigned)time(NULL));
   
  Smart_Ptr<cxxlAVL_Tree<A,int,false> > A_Tree1(new MyTree); 
   
  for(int i = 0;i < 20; i++)
  {
    int n = rand()%1000; 
    A_Tree1->Add(new A(n),n);
  }
  Smart_Ptr<cxxlAVL_Tree<A,int,false> > A_Tree2 = A_Tree1->Clone(); // 複製一份 
   
  A_Tree2->Add(new A(600),600); // A_Tree2 多加一個物件
  Smart_Ptr<cxxlList<A> > A_List1 = A_Tree1->cxxlList_Create(); 
  Smart_Ptr<cxxlList<A> > A_List2 = 
A_Tree2->cxxlList_Create(400); // A_Tree2 只取大於 400 的物件
  cout << "A_List1 的內容:" << endl;
  A_List1->ResetPT(toHead);
  for(Smart_Ptr<A> A_Ptr = (*A_List1)++; !A_Ptr.isNULL(); A_Ptr = (*A_List1)++)
    cout << A_Ptr->Get() << " "; 
   
  cout << endl;
  cout << endl;
  cout << "A_List2 的內容:" << endl;
  A_List2->ResetPT(toHead);
  for(Smart_Ptr<A> A_Ptr = (*A_List2)++; !A_Ptr.isNULL(); A_Ptr = (*A_List2)++)
    cout << A_Ptr->Get() << " "; 
   
  cout << endl;
  cout << endl;

  system("pause");
}

 


 

引入檔

CXXLAVLTREE.HPP

 

程式庫

 

 
 
 
 
 
 
 
 
 
Comments