michael

后序的遞歸算法。
template <class T>
void recposttraverse(struct node<T>* Tree)
{
    if(Tree == NULL) return;
    recposttraverse(Tree->left);
    recposttraverse(Tree->right);
    visitnode(Tree);
}
后序的非遞歸算法要加入tag的實現。
template <class T>
void posttraverse(struct node<T>*tree)
{
    if(tree == NULL) return;
    MyStack<struct node<T> *> treestack;
    treestack.init(20);
    treestack.push(tree);
    struct node<T>* Item;
    while(treestack.gettop()!=0)
    {
        Item  = treestack.pop();
        if(Item&&Item->flag)//true is tree
        {
            Item->flag = false;
            treestack.push(Item);
            if(Item->right)
            treestack.push(Item->right);
            if(Item->left)
            treestack.push(Item->left);
        }
        else
        {
            visitnode(Item);
        }

    }


}

中序遍歷的遞歸算法和非遞歸算法。
template <class T>
void recitraverse(struct node<T>* Tree)
{
    if(Tree == NULL) return;
    itraverse(Tree->left);
    visitnode(Tree);
    itraverse(Tree->right);
}
中序遍歷的非遞歸算法visit節點時與前序不同。
template <class T>
void itraverse(struct node<T>*tree)
{
    if(tree == NULL) return;
    MyStack<struct node<T> *> treestack;
    treestack.init(20);
    while(tree != NULL|| treestack.gettop()!=0)
    {
        if(tree!=NULL)
        {
            treestack.push(tree);
            tree = tree->left;
        }
        else
        {
            tree = treestack.pop();
            visitnode(tree);
            tree = tree->right;

        }
    }

}

動態規劃，基本上就是說：
    你追一個MM的時候，需要對該MM身邊的各閨中密友都好，這樣你追MM這個問題就分解為對其MM朋友的問題，只有把這些問題都解決了，最終你才能追到MM。
    該方法適用于聰明的MM，懂得“看一個人，不是看他如何對你，而是看他如何對他人。”的道理，并且對付這樣的MM總能得到最優解。
    該方法的缺點是開銷較大，因為每個子問題都要好好對待。。。。

////////////////////////////////////////////////////////////////////

    貪心法，基本上就是：
    你追一個MM的時候，從相識到相知，每次都采用最aggressive的方式，進攻進攻再進攻！從不采用迂回戰術或是欲擒故縱之法！目標是以最快的速度確立兩人關系。
    該法優點是代價小，速度快，但缺點是不是每次都能得到最優解。。。。。

////////////////////////////////////////////////////////////////////

    回溯算法，基本上就是：
    追一個MM，但也許你還是情竇初開的新手，不知道如何才能討得MM的歡心，于是你只好一條路一條路的試，MM不開心了，你就回溯回去換另一種方式。當然其 間你也許會從某些途徑得到一些經驗，能夠判斷哪些路徑不好，會剪枝（這就是分支估界了）。你也可以隨機選擇一些路徑來實施，說不定能立桿見影（這就是回溯 的優化了）但總的來說，你都需要一場持久戰。。。。
    該算法一般也能得到最優解，因為大多數MM會感動滴！！但其缺點是開銷大！除非你是非要談一場戀愛不可，否則不推薦使用。特別是你可能還有許多其他的事情要做，比如學習，比如事業。。。。

////////////////////////////////////////////////////////////////////

    老趙提問：假如一個mm對應NP完全問題,老大給個有效解法
    eshow回答：呵呵，那你為什么那么賤，非要去追呢？記住：“天涯何處無芳草！”不過如果你“非如此不可”的話，建議升級你的硬件，好好學習，好好工作，加強實力，人到中年的時候也許你能解開NP難。。。。

    強哥補充：這種MM可遇而不可求了，也就是eshow的終極目標。eshow其實已經開發出了
解決NP完全問題的對數級算法，但是不愿意告訴偶們……
 
  在認真研讀思考之后，calf mm舉一反三，對深度優先和廣度優先也做了總結：深度優先就是追一個mm追到底，直到失敗然后換個mm繼續追……廣度優先就是同時追多個mm，一起發展……

////////////////////////////////////////////////////////////////////

    大家都開始集思廣益……

    老馬：二叉樹的前序、中序和后序周游：

    前序就是直接搞定MM，然后搞定她爸媽（左）和你自己爸媽（右）； 中序就是先搞定未來岳父岳父，然后搞定她，最后告訴你爸媽；后序就是，讓未來的岳父岳母和自己爸媽都覺得你們合適之后，才對MM下手，這個時候，就沒有障礙了啊！
 
****************************************************

    網絡流:

    追MM的時候總避免不了送禮物，但是你老是直接送禮物就會給MM造成很大的壓力，于是你就想到了通過朋友來轉送的方法。你希望送給MM盡可能多的禮物，所 以就是需要找到一中配送方案，就是最大流了。然而你請別人幫忙并不是不要開銷的，你讓A同學拿去給B同學可能需要一些花費，自然你不是一個大款，想最小化
這個花費，那么就是最小費用最大流了……

****************************************************

    在你追了若干美女都失敗告終后，你發現有一批美女追起來是一樣困難的，如果你能追到其中任何一個就能追到其他所有的美女，你把這樣的女人叫作NP- Complete。P=NP：這是一個美好的猜想，追美女和恐龍的難度其實一樣。APX與Random：NP的美女難追，你無法完全占有她。你只好隨機的 去靠近她，裝作若無其事；或者用一種策略，追到她的一個approximation ratio，例如50%。APX-hard：這樣的女人，連一個固定的百分比都不給你，還是另謀高就吧。

****************************************************

    匹配：從初中到高中到大學大家追來追去，就是個二分圖匹配的過程...."和諧社會"應該就一個最大匹配...
可是后來有某些MM同時跟>1個人發展，違背了匹配的基本原則...大家都很BS之...然后最近斷背山很火，人們驚奇得發現原來還可以是 任意圖匹配...

    STL：某位貝爾實驗室的大牛在追了N個MM后，為了造福后來人，總結了自己的經驗，
出了本《 追MM求愛秘笈大全》，英文名叫Standard  courTing  Library，縮寫為
STL廣大同學在使用STL后，驚喜地發現追MM變得異常方便，大大縮短了時間和精力...

為了調試寫關于線程的信息，主要是core dump的信息，可以重載或者代替
malloc
free
realloc
函數，dmalloc 這個便是其這個作用的。但是由于dbmalloc性能影響較大。可以采用輕量級的重載，在malloc free realloc填充字符。最終通過core dump文件可以看到原因。
方案措施開始想到用dlopen,dlsymbol,dlload這種方案，但是這種方案會重復調用。是不可能實現的，最終采用的只能是用宏來代替。基本的方案就是定義一個公用的頭文件，這個頭文件的宏發生了變化，然后每個調用malloc,free等的都要包含頭文件。當然在引用頭文件的時候我們也要定義一個c/c++文件來重新實現，他不需要包含這個頭文件。

在過程中遇到的問題
1、頭文件的包含順序，應該放在后面才會重新定義。
2、C/C++混合，malloc等是C的函數。
3、realloc會重新改變位置，比較容易出錯的。
4、free(0)是可以的，要注意出錯。

遞歸算法和非遞歸算法本質是一樣的。
遍歷時從根節點開始訪問，訪問左子樹，關鍵是把樹的訪問順序搞清楚。
當遍歷完以后又是根節點。

遞歸函數實際上就是棧的操作。
所謂的先根就是先visit完根節點，然后再遍歷左子樹，遍歷右子樹。
 
template <class T>
void recpretraverse(struct node<T>*&Tree)
{
    if(Tree == NULL) return;
    visitnode(Tree);
    recpretraverse(Tree->left);
    recpretraverse(Tree->right);
}

對應的非遞歸算法就是彈出項，看如果是樹，如果右子樹存在則壓入右子樹，左子樹存在則壓入左子樹，最后壓入節點（tag域變化）。
                            看如果是節點，則訪問節點。
可以看出需要一個tag域來表示彈出節點還是樹。但是前序和中序可以通過別的實現辦法避免tag實現。
  template <class T>
void pretraverse(struct node<T>*tree)
{
    if(tree == NULL) return;
    MyStack<struct node<T> *> treestack;
    treestack.init(20);
    while(tree != NULL|| treestack.gettop()!=0)
    {
        if(tree!=NULL)
        {
            treestack.push(tree);
            visitnode(tree);
            tree = tree->left;
        }
        else
        {
            tree = treestack.pop();
            tree = tree->right;

        }
    }

}

1、提供了一個全局的聲明，全局函數、變量的一致性。
2、如果要修改功能僅僅需要簡單修改頭文件。

博客開張，記錄技術點點滴滴。





文章來源:http://www.cnblogs.com/michael-gao/archive/2008/06/05/1214090.html

1、new和malloc()有什么區別；
a. new 是 C++ 中的東西，而 malloc 是 C 中的東東
b. new 是操作符，而 malloc 是函數(?不記得是函數還是宏了)
c. new 可以對變量初始化，調用構造函數，而 malloc 沒有這個功能
d. new 是異常安全的，分配失敗可以捕獲到 std::bad_alloc 異常

2、ASSERT和VERIFY有什么區別；
a. ASSERT 宏的作用在于檢查表達式是否為假或為 NULL，如果為假則會引發異常，ASSERT 宏只在調試版本中才會有作用
b. VERIFY 宏與 ASSERT 宏的 VERIFY 的不同在與 VERIFY 在發行版本中同樣會起作用，但是使用 VERIFY 會導致非常不友好的用戶界面

3、模式對話框與非模式對話框有什么區別；
a. 模式對話框總是獨占的，而非模式對話框不是獨占的

4、SendMessage()與PostMessage()有什么區別；
a. SendMessage() 會等到返回才往下走，而 PostMessage 則不管

5、在繼承類中，子類是如何構造的？又是如何析構的？
a. 子類構造：先調用基類的構造函數(按繼續表順序)，然后調用類成員的構造函數，最后調用執行自己的構造函數
   析構通常情況下是相反的

6、什么是虛函數？
在 C++ 中，用 virtual 標識的函數

7、什么是多態？
多態指發出同樣的消息被不同類型的對象接收時導致完全不同的行為

8、socket編程，如何處理阻塞？
a. 設置超時時間

9、靜態變量的作用是什么？靜態成員變量有什么優缺點？
a. 控制存儲方式
b. 控制可見性與連接類型


文章來源:http://www.cnblogs.com/michael-gao/archive/2008/06/05/1214180.html

new 實現？
1、調用 void * operator new(size_t size);
      表示其返回的是一個未經處理（raw）的指針，指向未初始化的內存。參數size_t確定分配多少內存。你能增加額外的參數重載函數operator new，但是第一個參數類型必須是size_t
2、調用類的構造函數。
在第一步，operator new是怎么申請內存的？ 是調用的 malloc來申請內存嗎？

operator new和delete函數的實現

下劃線表示不一定準確，需要重新確認。

    operator new實際上總是以標準的C malloc()完成，雖然并沒有規定非得這么做不可。同樣，operator delete也總是以標準得C free()來實現，不考慮異常處理的話他們類似下面的樣子：

　　　　　extern void* operator new( size_t size )
{
    if( size == 0 )
        size = 1;       // 這里保證像 new T[0] 這樣得語句也是可行的
   
  　　　　　  void *last_alloc;
  　　　　　  while( !(last_alloc = malloc( size )) )
  　　　　　  {
    　　　　　    if( _new_handler )
    　　　　　        ( *_new_handler )();
    　　　　　    else
    　　　　　        return 0;
  　　　　　  }
  　　　　　  return last_alloc;
}

　　　　　extern void operator delete( void *ptr )
{
  　　　　　  if(ptr)  // 從這里可以看出，刪除一個空指針是安全的
  　　　　　      free( (char*)ptr );
}


new和malloc區別兩個  
   
  1   new是操作符  
      malloc是庫函數  
   
  2   new可以調用構造函數，malloc不可以  




文章來源:http://www.cnblogs.com/michael-gao/archive/2008/06/05/1214226.html

Operator new allocates memory from the heap, on which an object is constructed. Standard C++ also supports placement new operator, which constructs an object on a pre-allocated buffer. This is useful when building a memory pool, a garbage collector or simply when performance and exception safety are paramount (there's no danger of allocation failure since the memory has already been allocated, and constructing an object on a pre-allocated buffer takes less time):

 void placement() {



char *buf  = new char[1000];   //pre-allocated buffer



string *p = new (buf) string("hi");  //placement new



string *q = new string("hi");  //ordinary heap allocation



cout<<

c_str()


<

<c_str();



}

：

placement new 表達式只是定位，不存在與其相對應的delete，如果delete則選擇

delete[] buf。

文章來源:http://www.cnblogs.com/michael-gao/archive/2008/06/05/1214239.html