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