著名的千千静听音乐播放器，其界面简洁优雅、美观大方，特别是它那种几个窗口像磁石般相互吸引，当拖动主窗口时，粘在一起的其它窗口会跟随着一起移动，当拖动其它窗口时，又能脱离不粘在一起，这种窗口效果让用户操作方便，省心省力。为描述方便，本文称这种效果为多窗口的组合分离，它的主要特点是仅用鼠标任意移动窗口，就可组合或分离，当组合在一起时，移动某窗口（如主窗口，暂称为老板窗口）能整体移动，移动其口窗口（非老板窗口，暂称为工人窗口）又能将自己脱离出来。近来由于工作需要实现了类似于此的窗口效果，经过几天的测试，终于稳定。在开发过程中，考虑了以下几个问题：
     (1)  组合分离的条件如何决定判断。
     (2)  当窗口大小改变时，包括最小化，最大化，缩放窗口等，如何保证不影响组合分离，能正常整体移动。
     (3)  窗口个数是可变的，当新建或销毁窗口时，如何保证不影响组合分离，能正常整体移动(千千静听窗口个数是有限的，而且可能只是隐藏窗口）。
     (4)  采用什么数据结构较好，如何维护任意两个窗口间的距离关系（相交或相切视为组合，相离视为分离）。
     (5)  当拖动老板窗口时，如何拖动与其组合的所有窗口，关键是如何得到所有与其组合的窗口列表。
     (6)  如何针对这种效果设计一个通用的组件类，只需调用几个方法便可搞定。
   
   针对以上问题，主要思路是视屏幕上任意多个窗口为顶点，以其窗口矩形中心点来看待这个窗口，如果任意两个窗口间关系为组合，则视这两个顶点间是相通的，即两个顶点存在边。如果为分离，则视两顶点间是不通的，即两顶点不存边。因此可以用无向图来存储窗口和关系，为简单起见，我用的是邻接矩阵，问题(4)得以解决。既然用邻接矩阵来存储，那么如何得到所有与老板窗口相关的组合窗口呢？由于实际多个窗口在移动过程中，会改变其组合分离关系，这就会得到多个无向图的连通分量，而我们需要的是包含老板窗口的那一个连通分量，因此可以用DFS深度搜索遍历这个无向图连通分量，起始顶点是老板窗口，遍历完后就会得所有与其组合的窗口列表，问题(5)得以解决。现在讨论问题(1)，这里有个细节问题就是组合分离的条件判断有两种情况，一是当移动窗口时的条件，称为条件1，因为实际向一个窗口A移入另一个窗口B时，要达到还没有接近窗口A时便一下子靠近A就像被A吸引的效果，当移出B时还没完全移到A窗口外面时便一下子远离就像被A排斥的效果。二是当大小改变时的条件，称为条件2，这个不同于条件1，因为它不需要那种吸引排斥的效果，也没必要，这个条件2就是简单的判断A和B矩形是否相交，API函数IntersectRect即可完成这一判断。条件1的判断如下图所示：
                                                           
   在B向A移入过程中,当B的中心点在矩形left,top,right,bottom范围内,可认为是发生组合,实现吸引效果；当在center矩形内，认为是已经组合了；同理，B向A移出过程中，当B的中心点在矩形left,top,right,bottom范围内,可认为是发生分离，实现排斥效果。当都不在left,top,right,bottom,center矩形范围时，认为是已经分离了。至此，问题(1)得到解决。当窗口大小改变时，需要更新邻接矩阵反映窗口间关系的变化，而后更新组合窗口列表，组合窗口列表的计算依赖于邻接矩阵，运用DFS算法来更新，这在WM_SIZE消息事件处理内完成，问题(2)得到解决。当新建窗口时，需要向无向图中增加(窗口)顶点，扩充邻接矩阵以备存储与其它窗口的关系；当销毁窗口时，需要从无向图中删除对应的顶点，而后从邻接矩阵中删除对应的关系，问题(3)得到解决。
   上述问题(1)--(5)都已分析并得到解决，总的来说，就是以数据结构中无向图的观点和算法来建模解决这些问题的，特别是运用到了DFS搜索算法来重建已组合的所有窗口列表，只有这样，在移动老板窗口过程中，才能保证其它窗口跟随着一起移动。接下来就是最后一个问题，也就是怎么封装设计组件类，以达到方便应用的目的，综上所述，设计接口方法与以下窗口4种消息相关：
   1) 创建窗口发生的消息,如WM_CREATE,WM_INITDIALOG等。
   2) 关闭或销毁窗口发生的消息，如WM_CLOSE，WM_DESTROY等。
   3) 窗口大小改变后消息，WM_SIZE。
   4) 窗口移动中消息，WM_MOVING。
   
   另外提供一个设置获取老板窗口的方法，在应用程序中，只需在窗口4种消息处理内调用以上对应4个方法即可实现多窗口组合分离的效果，注意该类没有考虑多线程，因此是非安全的，适用于多窗口属于同一线程内的情况。类声明如下 
   这个问题，解法比较多，假设序列X大小为N，一种普通的做法是先设定最大值和最小值都为序列中第一个元素值，在一个循环内，每次循环都和当前最大值和最小值来比较更新，这样就需要2N-2次比较了；再进一步，如果先查找最大值，则需N-1次比较，再查找最小值，则需N-2次比较，总共是2N-3次比较，比上一方法少了1次。这些做法都是每次取1个数来比较，比较次数为O(2N)。接下来，我们把情况扩展到每次取多于1个数，先试试看每次取2个数，即N-2个数的解，对N个数求解。当N=1时，最大值和最小值就是第1个元素值；当N=2时，最大值和最小值就是第1个元素和第2个元素的最大值和最小值；考察X[N-2]和X[N-1]，同时令前N-2个数的解是MAX和MIN，易见，做3次比较便能得出新的最大值和最小值，首先比较X[N-2]和X[N-1]，然后将其中大数同MAX比较，小数同MIN比较，这样一来，大约需O(3N/2)次比较即可，而不是先前的O(2N)次。那么，是不是每次取3个或4个数能更进一步减少总共的比较次数呢？有趣地是，可以证明，每次取多于2个数来比较时，总共所需次数和取2个元素来比较是一样的。本文示例的是每次取2个数比较的实现，C++代码描述如下    对于以上代码的实现，由前面分析可知，当N为奇数时，总共比较次数为3/2*(N-1)；当N为偶数时，总共比较次数为3N/2-1，时间复杂度为0(3N/2)。    原题为某著名软件公司的试题，大意如下：给定一个容器，要求删除容器中重复的元素，并保持剩余元素的顺序不变。在这里，本文为了全面通用考虑，作了扩展，删除vector中的重复元素，从容器中元素顺序上可分为2种情形：1）保持剩余元素顺序不变，特称为稳定删除，对应下面的stable_unique版本函数模板 2）不考虑顺序变化，特称为快速删除。对应下面的quick_unique版本函数模板。从重复的概念定义也可分为2种情况：1）基于简单的相等判断 2）基于谓词的等价判断。因此，由排列组合得知应该有4种版本的实现，下面给出代码描述    以上代码在vc2005环境下编译测试通过，再进一步扩展，问题完全可以归类为删除某容器内重复元素，只要再加一个模板的模板参数即可template <typename T> class Conn;函数的形参类型变为std::Conn<T>就行了，但要注意的是不同平台下对应容器的erase实现所返回的迭代器可能有所差别，比如map要这样写才能在linux上正确工作：conn.erase(it++)。对于特殊的情况，可对以上4个函数作对应的重载（注意，函数模板没有特化的概念）来解决。    原为某著名软件公司试题，大意如下：请实现以下两个函数：char toupper(char c); char tolower(char c); 分别用于将传入的字母转为大写和小写。两个函数传入的参数取值范围都是[a-zA-Z]，并且为ASCII编码，实现时不用检查参数合法性。两个函数的实现不能使用任何形式的分支、跳转等类型的语句或指令（特别说明：C/C++的条件操作符?:也是分支指令的一种形式，故而不能使用）。请尽可能多的写出你知道的办法。   

  分析解决：此题比较特别，限制严格，根据题目要求，排除if else、for、while、do while、switch case、?:外，能使用的语句就只有 =、+=、-=、&、|、^、++、--这些了，想要实现大小写转换，只能从这些语句中进行选择思考，由于字符集为ASCII编码，且范围明确为[a-zA-Z]，我们知道，a-z对应ASCII值为97-122，A-Z对应ASCII为65-90，观察这些数字，可以发现97-122都大于96 ，65-90都大于64且小于96，进一步从二进制上考虑，则发现所有小写字母对应的二进制形式为011XXXXX，大写字母对应的二进制形式为010XXXXX，一到这里，哈哈，答案就出来了，通过位运算&和|就可实现了。代码描述如下

 1 char toupper(char c)
 2 {
 3     return c & 0x5F;
 4 }
 5 
 6 char tolower(char c)
 7 {
 8     //c | 0x60也行,但不太好,因为0x60会改变结果的第7位值,根据题目意思,改变第6位值为1,而其它位保持不变就够了。
 9     return c | 0x20;
10}

   至于其它方法，我就没多想了，还希望各位大侠多多分享一下哈。    原题为某游戏公司试题，大意如下：  对于一个单向链表，试写出找到它的倒序第m个元素(m >= 1)的函数，注意变量命名、注释、时间复杂度、空间复杂度。注：要求写出可编译并可以运行通过的程序代码。

  这道题的常规做法或者说首先想到直觉的方法M1是先求得链表的长度，即元素总个数n，然后问题转化为求顺序第n-m+1个元素。下面给出第2种方法M2：先求得顺序第m个元素，用一指针P指向这个元素，用另一指针PR指向链表的头部，现在好了，P和PR同时向右移动，直到P为空，则PR就是要求的倒序第m个元素，如果因m超越界限，则PR为空，表示没找到，这样一来，只需一次循环就够了。C++代码描述如下

 1 template<typename T>
 2 struct Node
 3 {  
 4     T  data;    /**//**//**////< 数据
 5     Node* next;  ///< 指向下一结点的指针
 6 } ;
 7 
 8 template<typename T>
 9 Node<T>* ReverseFind(Node<T>* head, size_t m)
10{
11    size_t  n = 0;
12    Node<T> *p, *pR = NULL;
13    for (p = head;p;p = p->next)
14    {
15        if (++n == m)
16        {
17            pR = head;
18            continue;
19        }
20        if (pR)
21        {
22            pR = pR->next;
23        }
24    }
25    return pR;
26}

  现在分析这2种方法的时间复杂度，假设链表元素个数为N，所求倒序为第M元素，N>=M，则M1方法为0(N)+0(N-M)=0(2N-M)，M2方法为O(M)+O(N-M)=0(N)，因此M2快于M1。

   原题为某游戏公司的试题，大意如下：写一个千位分隔符算法，函数原型是 char * format_thousands_separator(unsigned long val); 要求实现效果是 1.使用者不需要释放返回的字符串指针 2.支持最多调用16次而不返回相同指针地址。可以用以下方法测试       
    printf("num1(%s), num2(%s), num3(%s)\n", format_thousands_separator(0),format_thousands_separator(123456),format_thousands_separator(23456789)); 
   注：要求写出可编译并可以运行通过的程序代码。

   经过修改后，我目前最简洁的C代码描述如下      摘要:    一般地，泛型容器的设计实现大多只是存储了类型的单个对象，而没有存储类型的多个对象，如果有这样特定的需求，容器内的元素要求都是某个类型的多个对象，那么这时就可以考虑用模板类的数组特化来实现了，作为例程，下面C++代码描述了主模板实现 Code highlighting produced by Actipro CodeHighlighter (freewa...  阅读全文    原为某软件公司试题，大意如下：对于给定的有符号32位整数，写一个函数，当该数为正数时返回1，为负数时返回-1，为零时返回零，要求不能使用任何的条件判断分支跳转语句。在这里，稍微扩展了一下，给出了对应无符号32位整数的情形。解决思路是符号位和值分开处理，对于有符号32位整数，符号位右移31位即得a，若为非负数则a=0x00000000，否则a=0xFFFFFFFF；然后将值部分各位的值（0或1）不断缩小合并到一位中去得到b，这是针对0和正数的情况处理，再将a和b位或即可。C++代码描述如下    若哪位有更好的解法，还望多多分享    WTL是窗口模板库(Windows Library Template)的简称，是一套轻量级C++ GUI库，因为它使用了C++模板封装了窗口界面操作API和消息映射处理，它扩展了ATL中的UI窗口部分，并支持如下更多的功能特性：
    (1)   对话框和通用控件：包括对话框数据交换(DDX)，子类化，控件消息通知与反射等
    (2)   工具栏和状态栏：包括工具条UI状态更新，多窗格状态条及UI状态更新等
    (3)   分隔窗口：包括窗格容器，嵌套分隔，特殊绘制等
    (4)   属性页和向导：包括属性表，普通属性页，向导属性页等
    (5)   GDI类等：包括GDI封装类，通用对话框等
    (6)   使用ActiveX控件：包括使用控件类，调用控件的方法，控件事件映射处理等
    (7)   高级对话框UI类：包括自绘和外观定制类，新控件类，控件UI状态更新，对话框数据验证DDV等
    (8)   支持拖放操作：包括拖放接口实现类，最近使用文件列表等
   综上所述，使用WTL几乎可以实现MFC所能实现的功能与界面，而且生成的执行文件体积更小，不需要动态链接库就可直接快速地执行。

   根据WIN32窗口原理，当事件发生的时候，一般由父窗口接收其子窗口或控件的通知或命令消息，在这里父窗口是消息接收者，子窗口或控件是消息发送者，那么谁是消息处理者呢？实际上由谁来处理消息只是代码上的逻辑，既可以在父窗口的窗口过程回调内处理，也可以在子窗口或控件的窗口过程回调内处理，在哪处理更方便合理就在哪处理，如果是在子窗口或控件窗口过程回调内处理，那么就需要作额外的处理了，也就是在父窗口中将消息反射给发送者，进而再由发送者处理。下面以父窗口为打开文件对话框，双击它的列表视图控件为例，给出运用上面(1)中的控件消息通知与反射来处理NM_DBLCLK消息的两种实现方式。

   继承方式：由控件处理消息
   从CWindowImpl模板基类派生一个子窗口或控件子类即listview子类，添加消息映射项和消息处理函数，消息映射项用REFLECTED_NOTIFY_XXX或REFLECTED_COMMAND_XXX系列反射宏实现，具体使用哪个宏，决定于是否通知或命令消息，及消息对应的ID和通知码。    
   在父窗口类消息映射链中最后添加反射通知宏REFLECT_NOTIFICATIONS()项。                                           
　成员方式：由父窗口处理消息 
   直接使用ATL中的包含窗口模板类CContainedWindowT，参数为子控件的类名即listviewctrl，实例化为父窗口类的一个成员变量，在父窗口类消息映射链中添加ALT_MSG_MAP宏来实现消息分派，其参数为分派ID，这个ID为成员变量初始化时指定的常量；添加反射通知宏REFLECT_NOTIFICATIONS()，注意ALT_MSG_MAP宏必须在反射通知宏REFLECT_NOTIFICATIONS之后。  
   在父窗口内需要初始化m_list_File以指定分派ID号。                                                               

   MFC将windows消息系统进行了高度的抽象和封装，其根本原理是运用C++的高级特性并结合一定的设计模式（如工厂模式，模板方法等）来实现的。一般的windows消息（WM_XXX），则一定是由派生类流向基类，没有旁流的可能。如果是命令消息（WM_COMMAND），那就有比较奇特的路线了。下面就针对多文档/单文档（Document-View）、对话框两种应用程序比较讨论WM_COMMAND消息的传递处理过程。讨论前首先得明确命令消息的来源，命令消息一般是用户选择某个菜单项，或一个加速键被翻译，或一个子控件发送一个通知消息给它的父窗口时产生的。对一个菜单而言，消息接收者是Frame窗口或拥有它的对话框；对一个工具栏而言，消息接收者是它的父窗口。两种应用程序命令消息处理流程如下图所示。                   

   从上图可知，文档视图型的处理路线是先向下再向上，而对话框型的路线是一直向上，消息接收者只有一个，而处理者次序有多个，每个处理者内部首先都是调用根基类CCmdTarget的OnCmdMsg虚函数，在这个函数内逐级向基类遍历消息映射表，根据命令ID和通知码找到对应的消息映射结构体AFX_MSGMAP_ENTRY，如果找到再处理这个命令消息，否则返回FALSE，退回到this对象所在的OnCmdMsg函数进行下一步处理。如果到最后一层都没有找到对应命令的消息映射，则返回到系统的默认处理DefWindowProc。再综合考虑下，如果一个对话框接收到了一个命令消息例如是点击它的子控件工具栏某个按钮发出的，而这个对话框类没有添加相应的ON_COMMAND映射，就会进入到它的父窗口类OnCmdMsg函数进行处理，如果这个父窗口正好是Frame窗口，那么命令消息的处理流程就由上图右边转到左边了。而最终命令消息能否得处理，就看上图5种对象（Frame、View、Document、Dialog、App、Thread）是否添加了对应的ON_COMMAND映射。
   
   到此为止，我们已经明确了WM_COMMAND消息的处理流程，但是发现最终处理却是由收到消息的窗口传递的，不是消息通知者自己处理的，有的时候为了提高代码的封装性，可能需要自己处理这些命令比较方便，比如有一个工具栏CPlayToolBar子类从CToolBar继承，有播放、暂停、停止3个按钮，它的父窗口是CPlayDialog对话框。按照常规，这3个按钮命令事件的处理一般是在CPlayDialog类中3个ON_COMMAND映射宏和处理函数的，但如果在CPlayToolBar类中添加3个ON_COMMAND映射宏和处理函数，是得不到处理的，其原因在于对话框型的路线是一直向上，再者MFC中没有对应的命令反射ON_COMMAND_REFLECT这个宏。为了能使CPlayToolBar类自己处理这3个按钮命令事件，就需要从CPlayDialog类中转移路线，使之流向其子窗口工具栏，这样CPlayToolbar 类就得到了自己处理的机会。具体操作是重载CPlayToolBar和CPlayDialog的OnCommand虚函数,  CPlayDialog代码如下所示：    CPlayToolBar类代码如下所示     现在，3个按钮命令事件能在CPlayToolBar类中独立处理了，这样一来就提高了代码的封装性，简化了父窗口CPlayDialog类的处理。