学步园

　　　　该题目的出处是：“一道比较刁的面试题”，http://www.cnblogs.com/tandly/archive/2010/01/08/1642609.html　　

　　　　要求：

　　　　1.任何语言 任何形式（web,winform,flash,flex,silverlight）等等。。

　　　　2.实现内容

　　　　　　a.初始化一个面板，面板内随机分布着一些按钮  按钮上有一些随机的数字。

　　　　　　b.有一个按钮 名字叫“新增节点” 点击 该按钮后 可以向面板内随机添加新的 按钮。

　　　　　　c.任意顺序点击面板内的按钮。按顺序将所点按钮用线条连接。并且将按钮的 数值进行累加 显示到 文本框。

　　　　　　d.回放 功能。 有一个名叫 “回放的按钮” 点击该按钮后 将所有操作慢动作回放。包括增加节点 和 连接 的一切操作。完整再现。

 

　　　　我在前几天看到这个题目，自觉是不难，也有一些人说到用到链表，这是不错的。而且这些实现起来并不是那么难，只是需要一定的耐心。而吸引我要把它用VC实现出来的，并不是这几个功能本身，而是如何在两个按钮之间绘制一个箭头型的连线，吸引了我的兴趣。为什么这么说呢，因为按钮随机出现，因此最简单的方法，我在两个按钮的中心点绘制一条线段就可以了，这样当然是最简单的。不过我还想让显示效果更理想化一点，也就是在被指向按钮的线段端点绘制一个三角形的箭头，并且：这个箭头不能覆盖到按钮上，也就是我希望箭头连接到按钮的矩形边框上面，做好的程序如下图所示：

 

　　　　

 

　　　　在上图中，可以看到实际上每个箭头都是连接按钮的中心点的，而且箭头被准确的绘制在合适的位置（上图的按钮有些小，所以效果不够明显）。因此，这里的关键是要计算出连接线和按钮边框的交点。我是这样来做的：首先，在创建按钮时，我以按钮的中心点为圆点，计算出中心点到四个顶点的四条射线的角度，由于我是使用 atan 函数来计算两个按钮连线的角度，因此射线的角度也使他落在（-90~270）范围。如下图示意：

 

　　　　

 

　　　　上图的圆周范围是从-90到270度，采用的坐标都是计算机的屏幕坐标为准（Y正方向向下，和数学中的笛卡尔坐标的Y轴方向相反），角度的正方向也是顺时针（也是和数学中的方向反向）。为了简单直观，上面的角度都使用角度表示，在实际代码中都是采用弧度。大致方法是：

　　　　（1）首先计算出两个按钮中心连线的夹角（-90~270）；

　　　　（2）根据夹角和按钮信息中的 四个对角线射线角 （angle[4]）的大小关系，判断出连线和按钮相交与哪一个边缘。

　　　　（3）由于按钮边缘上的x，y至少有一个是可知的，因此根据 alpha 角度计算出交点坐标的位置。

 

　　　　大概过程如上，因此代码也就会很直观了：

 

//描述一个按钮
class CNumButton
{
public:
    int left,top,right,bottom;
    //按钮的对角线的4个角度
    double angle[4];
...
    //指定按钮的中心点和高度，宽度，数字
    void Init(int cx, int cy, int width, int height, int number)
    {
        double a;
        left = cx - width/2;
        top = cy - height/2;
        right = cx + width/2;
        bottom = cy + height/2;
        num = number;
        //计算对角线角度
        a = atan(((double)height)/width);
        angle[0] = -a;
        angle[1] = a;
        angle[2] = M_PI - a;
        angle[3] = M_PI + a;
    }
};
//描述两个按钮的连接线
class CLine
{
private:
    int x0, y0; //From，出发点
    int x1, y1; //To，指向点
    //三角箭头的点数组
    POINT ptsArrow[3];
private:
    //计算角度 from POINT0 -> to POINT1
    double GetAngle(int x0, int y0, int x1, int y1)
    {
        double angle;
        if(x1==x0)
        {
            if(y1>=y0) return M_PI_2; //90 度
            else return (3 * M_PI_2); //270
        }
        angle = atan(((double)(y1-y0))/(x1-x0));
        if(x1 < x0) angle += M_PI; //如果to在from左侧，则需要增加180度
        return angle;
    }
    //获取连线与按钮边缘相交的点坐标
    void GetSidePoint(CNumButton* btn, double angle, int *pX, int *pY)
    {
        if( angle < btn->angle[0] || angle > btn->angle[3]) //上边缘
        {
            *pY = btn->top;
            *pX = btn->GetCX() - (int)(btn->GetHeigth()/2 * tan(M_PI_2-angle) + 0.5);
        }
        else if(angle < btn->angle[1]) //右边缘
        {
            *pX = btn->right;
            *pY = btn->GetCY() + (int)(btn->GetWidth()/2 * tan(angle) + 0.5);
        }
        else if(angle < btn->angle[2]) //下边缘
        {
            *pY = btn->bottom;
            *pX = btn->GetCX() + (int)(btn->GetHeigth()/2 * tan(M_PI_2-angle) + 0.5);
        }
        else if(angle < btn->angle[3]) //左边缘
        {
            *pX = btn->left;
            *pY = btn->GetCY() - (int)(btn->GetWidth()/2 * tan(angle) + 0.5);
        }
    }
    
    void Init(CNumButton* fromBtn, CNumButton* toBtn)
    {
        int arrowsize = 20; //箭头大小
        double angle0, angle1;
        int cx0 = fromBtn->GetCX();
        int cy0 = fromBtn->GetCY();
        int cx1 = toBtn->GetCX();
        int cy1 = toBtn->GetCY();
        angle0 = GetAngle(cx0, cy0, cx1, cy1);
        angle1 = GetAngle(cx1, cy1, cx0, cy0);
        //获取线段两个端点
        GetSidePoint(fromBtn, angle0, &x0, &y0);
        GetSidePoint(toBtn, angle1, &x1, &y1);
        //设置箭头
        ptsArrow[0].x = x1;
        ptsArrow[0].y = y1;
        //获取三角形箭头的其他两个端点
        ptsArrow[1].x = x1 + (int)(arrowsize * cos(angle1-M_PI/12) + 0.5);
        ptsArrow[1].y = y1 + (int)(arrowsize * sin(angle1-M_PI/12) + 0.5);
        ptsArrow[2].x = x1 + (int)(arrowsize * cos(angle1+M_PI/12) + 0.5);
        ptsArrow[2].y = y1 + (int)(arrowsize * sin(angle1+M_PI/12) + 0.5);
    }
...
};

 

 

　　

　　　　此外，在题目要求中提到的一些功能，我定义了一个类：CSolution，用它辅助Windows程序完成演示，绘制等大部分功能。在Solution中保存了一个按钮链表，一个动作记录链表。其中按钮链表的每个节点都一定包含一个按钮，每个按钮节点还包含一个连接线的指针（CLine* line，初始为NULL），只有当这个按钮被点击且能和之前的按钮建立连接关系，我们就为这个按钮的CLine*分配指向相应的对象。换句话说，除了第一次点击时，无法建立CLine*的指向，之后的每次点击都能为按钮分配CLine*的指向。

 

 

　　　　在前面讲了太多和这个题考察内容无关的方面，下面还是再说说这道题考察的关键部分吧（尽管问题很直观）。

 

　　　　首先我们需要定义了两个链表来保存信息：

　　　　Buttons链表：实际上保存了窗口上所有的按钮和连接线对象。每个节点都包含一个指向 Button 和一个指向 Line 的指针。注意，每个节点的Button一定存在，而Line可能为NULL。

　　　　Actions链表：保存了当前动作的可重现信息：包括，当前动作类型（增加按钮/点击按钮），当前的Sum值（按钮数字总和）等等。

 

　　　　链表的节点定义如下： 

 

//动作类型
#define    ACTION_ADDBUTTON    0 //增加按钮
#define ACTION_CLICKBUTTON    1 //按按钮
//保存绘制对象的节点
typedef struct _NODE_BUTTON
{
    CLine        *line;        //相关联的线
    CNumButton    *btn;            //按钮
    struct _NODE_BUTTON *prev;    //双向链表
    struct _NODE_BUTTON *next;
} NUMBUTTON, *LPNUMBUTTON;
//记录动作的节点
typedef struct _NODE_ACTION
{
    int            type;        //动作类型
    int            sum;        //回放时应该显示的总和
    CLine        *line;        //相关联的线
    CNumButton *btn;    //相关联的按钮
    struct _NODE_ACTION *prev;
    struct _NODE_ACTION *next;
} NUMACTION;
...
//解决问题
class CSolution
{
private:
    CNumButton *lastBtn;    //最后点击的按钮（连线的尾部节点）
    NumList<NUMBUTTON> buttons;        //保存所有按钮的链表
    NumList<NUMACTION> actions;        //保存所有动作的链表
    int nSum;            //数字的总和

public:
    bool bDrawRegion; //是否绘制region（按钮的可出现位置）
    bool bPlaying;        //是否正在回放？

...
};

 

 

　　　　此外剩余的主要技巧基本都是使用 Platform SDK 的传统Windows 开发技术。特别的，这个例子最初的目的如其名称，它也展示和练习了 Rebar ，ToolBar, StatuBar 等 CommonCtrl 的使用。在工具栏上使用了 CHEVRON （“>>”）按钮。该按钮的显示控制是由系统的Rebar窗口已经实现的。当Rebar的Band小于它的理想宽度时，ReBar就会在这个Band的边缘显示“>>"按钮。点击“>>”按钮时应用程序需要弹出一个上下文菜单来显示那些显示不完全的项目。在这里为了给菜单项目显示左侧的图标，我又对上下文菜单使用了自定义绘制（菜单和工具栏使用的是同一个ImageList）。效果如下图所示：

 

　　　　

 

　　　　有一点不是很好的是，当我对客户区整个刷新时，我发现 Rebar 的显示同时也失效了（Rebar上的Bands会显示不正常），为了不强制rebar重绘，我只好把客户区的画布的顶端向下增加足够的高度。

 

　　　　最后任务栏上有一个按钮，是“显示Region”，它是CSolution内维护的一个HRGN（区域），主要目的，是我在添加一个按钮后，在画布中把这个按钮占据的区域删去，这样尽可能使增加按钮时，他们不至于很快重叠在一起。

 

　　　　当（元素）按钮重叠时，这里又有一个小的技巧。即，我们按照 Z 次序 绘制他们，但是在鼠标点击去尝试捕获对象时，则要沿着和绘制相反的顺序捕获。例如，我在这里绘制按钮，是从链表头部 绘制到 链表的尾部，（按照添加顺序），但是在尝试捕获时，则需要从链表尾部检索到头部，这是因为位于最上面的元素是最后绘制的，但是也是最可能被最首先点击到的。

 

 

　　　　最后是源代码的下载链接（修复了NumList模板类定义中的一个BUG，该BUG导致获取List的元素个数不正确）：

　　　　http://files.cnblogs.com/hoodlum1980/Rebar3.rar

 

　　　　BUG修复：

　　　　（1）修复了NumList模板类定义中的一个BUG，该BUG导致获取List的元素个数不正确。

　　　　（2）修复在回放过程中，有些动作中，记录Sum值 的TextBox没有及时刷新的 BUG。

 

 

　　　　【附加另一道题目】：为了防止影响对方公司的面试，这里就隐去该题目的出处。这道题目非常基础和简单，这里作为一种练习。题目要求是：

　　　　使用Win32 ( 不用MFC )，写一个Windows程序，实现功能:

　　　　(1) 窗口启动时最大化 ；(2) 窗口的背景色为指定颜色；(3) 左上角显示鼠标客户区坐标；(4) 显示一张牌, 按方向键随之一动，每次移动1像素，并保证不移出窗口。(5) 点击换牌。

　　　　程序运行效果截图是：

　　　　

　　　　这个程序的关键是在于如何防止卡片移动时的闪烁，实际上这里我采用了一种不能应用于普通情况，而仅适用与该题题意的比较投机的方法去防闪烁（因为这个题目中窗口背景是纯色的，在实际应用中未必有这么好的条件）。“闪烁”是windows程序在绘制方面（GDI）的一个经典话题了。当你使用GDI，（而非DirectX，OPENGL之类），那么不可能不接触到它。当然，如何防止闪烁主要取决于开发人员对窗口绘制的相关消息和过程的理解和掌握，也就是首先要弄清楚闪烁是如何引起的，然后有针对性的尽最大可能减少闪烁的发生。而不应该仅只知道一些 double buffer 之类的术语（却不知所以）。

 

　　　　原代码：http://files.cnblogs.com/hoodlum1980/ShowPokeCard.rar