michael

后序的遞歸算法。
template <class T>
void recposttraverse(struct node<T>* Tree)
{
    if(Tree == NULL) return;
    recposttraverse(Tree->left);
    recposttraverse(Tree->right);
    visitnode(Tree);
}
后序的非遞歸算法要加入tag的實(shí)現(xiàn)。
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節(jié)點(diǎn)時(shí)與前序不同。
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;

        }
    }

}

動(dòng)態(tài)規(guī)劃，基本上就是說(shuō)：
    你追一個(gè)MM的時(shí)候，需要對(duì)該MM身邊的各閨中密友都好，這樣你追MM這個(gè)問(wèn)題就分解為對(duì)其MM朋友的問(wèn)題，只有把這些問(wèn)題都解決了，最終你才能追到MM。
    該方法適用于聰明的MM，懂得“看一個(gè)人，不是看他如何對(duì)你，而是看他如何對(duì)他人。”的道理，并且對(duì)付這樣的MM總能得到最優(yōu)解。
    該方法的缺點(diǎn)是開(kāi)銷較大，因?yàn)槊總€(gè)子問(wèn)題都要好好對(duì)待。。。。

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

    貪心法，基本上就是：
    你追一個(gè)MM的時(shí)候，從相識(shí)到相知，每次都采用最aggressive的方式，進(jìn)攻進(jìn)攻再進(jìn)攻！從不采用迂回戰(zhàn)術(shù)或是欲擒故縱之法！目標(biāo)是以最快的速度確立兩人關(guān)系。
    該法優(yōu)點(diǎn)是代價(jià)小，速度快，但缺點(diǎn)是不是每次都能得到最優(yōu)解。。。。。

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

    回溯算法，基本上就是：
    追一個(gè)MM，但也許你還是情竇初開(kāi)的新手，不知道如何才能討得MM的歡心，于是你只好一條路一條路的試，MM不開(kāi)心了，你就回溯回去換另一種方式。當(dāng)然其 間你也許會(huì)從某些途徑得到一些經(jīng)驗(yàn)，能夠判斷哪些路徑不好，會(huì)剪枝（這就是分支估界了）。你也可以隨機(jī)選擇一些路徑來(lái)實(shí)施，說(shuō)不定能立桿見(jiàn)影（這就是回溯 的優(yōu)化了）但總的來(lái)說(shuō)，你都需要一場(chǎng)持久戰(zhàn)。。。。
    該算法一般也能得到最優(yōu)解，因?yàn)榇蠖鄶?shù)MM會(huì)感動(dòng)滴！！但其缺點(diǎn)是開(kāi)銷大！除非你是非要談一場(chǎng)戀愛(ài)不可，否則不推薦使用。特別是你可能還有許多其他的事情要做，比如學(xué)習(xí)，比如事業(yè)。。。。

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

    老趙提問(wèn)：假如一個(gè)mm對(duì)應(yīng)NP完全問(wèn)題,老大給個(gè)有效解法
    eshow回答：呵呵，那你為什么那么賤，非要去追呢？記住：“天涯何處無(wú)芳草！”不過(guò)如果你“非如此不可”的話，建議升級(jí)你的硬件，好好學(xué)習(xí)，好好工作，加強(qiáng)實(shí)力，人到中年的時(shí)候也許你能解開(kāi)NP難。。。。

    強(qiáng)哥補(bǔ)充：這種MM可遇而不可求了，也就是eshow的終極目標(biāo)。eshow其實(shí)已經(jīng)開(kāi)發(fā)出了
解決NP完全問(wèn)題的對(duì)數(shù)級(jí)算法，但是不愿意告訴偶們……
 
  在認(rèn)真研讀思考之后，calf mm舉一反三，對(duì)深度優(yōu)先和廣度優(yōu)先也做了總結(jié)：深度優(yōu)先就是追一個(gè)mm追到底，直到失敗然后換個(gè)mm繼續(xù)追……廣度優(yōu)先就是同時(shí)追多個(gè)mm，一起發(fā)展……

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

    大家都開(kāi)始集思廣益……

    老馬：二叉樹(shù)的前序、中序和后序周游：

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

    網(wǎng)絡(luò)流:

    追MM的時(shí)候總避免不了送禮物，但是你老是直接送禮物就會(huì)給MM造成很大的壓力，于是你就想到了通過(guò)朋友來(lái)轉(zhuǎn)送的方法。你希望送給MM盡可能多的禮物，所 以就是需要找到一中配送方案，就是最大流了。然而你請(qǐng)別人幫忙并不是不要開(kāi)銷的，你讓A同學(xué)拿去給B同學(xué)可能需要一些花費(fèi)，自然你不是一個(gè)大款，想最小化
這個(gè)花費(fèi)，那么就是最小費(fèi)用最大流了……

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

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

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

    匹配：從初中到高中到大學(xué)大家追來(lái)追去，就是個(gè)二分圖匹配的過(guò)程...."和諧社會(huì)"應(yīng)該就一個(gè)最大匹配...
可是后來(lái)有某些MM同時(shí)跟>1個(gè)人發(fā)展，違背了匹配的基本原則...大家都很BS之...然后最近斷背山很火，人們驚奇得發(fā)現(xiàn)原來(lái)還可以是 任意圖匹配...

    STL：某位貝爾實(shí)驗(yàn)室的大牛在追了N個(gè)MM后，為了造福后來(lái)人，總結(jié)了自己的經(jīng)驗(yàn)，
出了本《 追MM求愛(ài)秘笈大全》，英文名叫Standard  courTing  Library，縮寫(xiě)為
STL廣大同學(xué)在使用STL后，驚喜地發(fā)現(xiàn)追MM變得異常方便，大大縮短了時(shí)間和精力...

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

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

遞歸算法和非遞歸算法本質(zhì)是一樣的。
遍歷時(shí)從根節(jié)點(diǎn)開(kāi)始訪問(wèn)，訪問(wèn)左子樹(shù)，關(guān)鍵是把樹(shù)的訪問(wèn)順序搞清楚。
當(dāng)遍歷完以后又是根節(jié)點(diǎn)。

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

對(duì)應(yīng)的非遞歸算法就是彈出項(xiàng)，看如果是樹(shù)，如果右子樹(shù)存在則壓入右子樹(shù)，左子樹(shù)存在則壓入左子樹(shù)，最后壓入節(jié)點(diǎn)（tag域變化）。
                            看如果是節(jié)點(diǎn)，則訪問(wèn)節(jié)點(diǎn)。
可以看出需要一個(gè)tag域來(lái)表示彈出節(jié)點(diǎn)還是樹(shù)。但是前序和中序可以通過(guò)別的實(shí)現(xiàn)辦法避免tag實(shí)現(xiàn)。
  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、提供了一個(gè)全局的聲明，全局函數(shù)、變量的一致性。
2、如果要修改功能僅僅需要簡(jiǎn)單修改頭文件。

extern "C"

extern "C" 鏈接指示符不能在函數(shù)體內(nèi)定義。
extern "Fortran"
等等。

extern"C"為了混合聯(lián)編而出現(xiàn)的。
1、
C++中引用C的頭文件，然后包括library和dll動(dòng)態(tài)和靜態(tài)的加載了。例如：
extern "C"
{
    #include  "Cheader.h"
}
 #pragment mylib等。
/*引用Cheader中的函數(shù)了*/
或者可以extern "C"的函數(shù)。

所以標(biāo)準(zhǔn)的頭文件中就會(huì)出現(xiàn)：
#ifdef __cplusplus
extern "C" {
#endif
/*...*/
#ifdef __cplusplus
}
#endif
這樣是為了使得C++引用頭文件不用再添加這個(gè)extern "C" {...}

2、C引用C++的函數(shù)的時(shí)候要注意,此時(shí)C++的頭文件應(yīng)該包含著extern "C"，但是在C語(yǔ)言中不能直接引用聲明了extern "C"的該頭文件，應(yīng)該僅將C文件中將C++中定義的extern "C"函數(shù)聲明為extern類型。


文章來(lái)源:http://www.cnblogs.com/michael-gao/archive/2008/06/05/1214470.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 表達(dá)式只是定位，不存在與其相對(duì)應(yīng)的delete，如果delete則選擇

delete[] buf。

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

new 實(shí)現(xiàn)？
1、調(diào)用 void * operator new(size_t size);
      表示其返回的是一個(gè)未經(jīng)處理（raw）的指針，指向未初始化的內(nèi)存。參數(shù)size_t確定分配多少內(nèi)存。你能增加額外的參數(shù)重載函數(shù)operator new，但是第一個(gè)參數(shù)類型必須是size_t
2、調(diào)用類的構(gòu)造函數(shù)。
在第一步，operator new是怎么申請(qǐng)內(nèi)存的？ 是調(diào)用的 malloc來(lái)申請(qǐng)內(nèi)存嗎？

operator new和delete函數(shù)的實(shí)現(xiàn)

下劃線表示不一定準(zhǔn)確，需要重新確認(rèn)。

    operator new實(shí)際上總是以標(biāo)準(zhǔn)的C malloc()完成，雖然并沒(méi)有規(guī)定非得這么做不可。同樣，operator delete也總是以標(biāo)準(zhǔn)得C free()來(lái)實(shí)現(xiàn)，不考慮異常處理的話他們類似下面的樣子：

　　　　　extern void* operator new( size_t size )
{
    if( size == 0 )
        size = 1;       // 這里保證像 new T[0] 這樣得語(yǔ)句也是可行的
   
  　　　　　  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)  // 從這里可以看出，刪除一個(gè)空指針是安全的
  　　　　　      free( (char*)ptr );
}


new和malloc區(qū)別兩個(gè)  
   
  1   new是操作符  
      malloc是庫(kù)函數(shù)  
   
  2   new可以調(diào)用構(gòu)造函數(shù)，malloc不可以  




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

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

2、ASSERT和VERIFY有什么區(qū)別；
a. ASSERT 宏的作用在于檢查表達(dá)式是否為假或?yàn)?NULL，如果為假則會(huì)引發(fā)異常，ASSERT 宏只在調(diào)試版本中才會(huì)有作用
b. VERIFY 宏與 ASSERT 宏的 VERIFY 的不同在與 VERIFY 在發(fā)行版本中同樣會(huì)起作用，但是使用 VERIFY 會(huì)導(dǎo)致非常不友好的用戶界面

3、模式對(duì)話框與非模式對(duì)話框有什么區(qū)別；
a. 模式對(duì)話框總是獨(dú)占的，而非模式對(duì)話框不是獨(dú)占的

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

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

6、什么是虛函數(shù)？
在 C++ 中，用 virtual 標(biāo)識(shí)的函數(shù)

7、什么是多態(tài)？
多態(tài)指發(fā)出同樣的消息被不同類型的對(duì)象接收時(shí)導(dǎo)致完全不同的行為

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

9、靜態(tài)變量的作用是什么？靜態(tài)成員變量有什么優(yōu)缺點(diǎn)？
a. 控制存儲(chǔ)方式
b. 控制可見(jiàn)性與連接類型


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