C++之竹

无论是太阳下，还是风雨中，都要成长！

常用链接

统计

最新评论

2012年5月14日 #

简历——为何真实反而成败笔？！！

近两个月里，又开始了新的跳槽。诚然，我之前跳槽次数确实过多了，但出于在当前公司的工作内容、待遇、职称评定等方面的不满，最终还是下定了跳槽的决心。（当然，也对之前的求职做了回顾，毕竟我也不想再有这种频繁的跳槽了，我也想稳定下来了。）

而在一开始，就已经有朋友劝我，在简历中得弄点虚假和夸张，否则很难找到好的工作。可惜，本人对这种夸大优点，剔除一切不利信息的简历制作实在是难以为之！最终，想而易知，我所投出的简历所得到的回应是少得可怜。期间，我听说了一些通过在简历上的“美化”而取得求职成功的例子，也陆续的有几个朋友劝我在简历上不要太老实，得做些变通，如，“将中间的某两个公司的经历合写成一个公司的经历”、“某些内容可以不要写到简历上”、“某些内容应该再做些扩充，并对某些词替换成更吸引人点的词”等等。我也确有几次去尝试调整简历，可是，以到这弄虚假、夸张、隐瞒时，我却又实在是下不了手。没办法，或许这就是本性难移吧。

还好，回应总算还是有一些，而且目前也拿到了一份还算满意的Offer。在即将进入的新公司里，还是好好干吧！~

哎！~这可怕的求职市场啊，实在太令人心冷了！~

posted @ 2012-05-14 22:15 青碧竹 阅读(534) | 评论 (1) | 编辑 收藏

2012年4月23日 #

Windows 控制台程序的事件捕获

     摘要:       此篇内容属C++控制台编程的一点基础应用，所以嘛，偶就偷个懒，不再做文字的讲解，直接代码。       哦，对了！代码之前，先就代码的组成作个简单说明。代码的内容共分为三块： 以宏RUN_ATEXIT_SAMPLE标识的atexit调用样例以宏RUN_SETC...  阅读全文

posted @ 2012-04-23 00:07 青碧竹 阅读(964) | 评论 (0) | 编辑 收藏

2012年4月5日 #

树中两个结点的最低公共祖先

<本文的样例代码：/Files/qingbizhu/LowestCommonAncestor.zip>
 
这是《剑指Offer——名企面试官精讲典型编程题》一书中的面试题50，此题针对所给条件的不同，将需要截然不同的解题思路和方法。书中给出了针对此题的3种不同条件的解题，本文所要讲解的是对其第3种条件的一个改进解法。具体的题目及条件如下。
 
【题目】：
      输入两个树结点，求它们的最低公共祖先。

【补充条件】：

      树是普通的树，而且树中的结点没有指向父节点的指针。

 

针对上述的题目和条件，书中给出了如下解决方案。

 

【原方案】：

      使用两个链表，对树进行两次遍历以查找两个树结点，并保持路径到两个链表中，从而将问题转化为求两个链表的最后一个公共结点。

 

从该方案中，观察到两次树结点查找的遍历中，其中一个结点的遍历过的树结点序列将完全覆盖查找另一结点时所遍历的树结点序列。由此入手，本文提出了如下的改进解决方案。

【改进方案】：

    深度优先遍历树，并记录路径，当找到第一个结点后，在当前基础上继续遍历搜索第二个结点，并记录第一个结点路径的变化程度，直到找到第二个结点。最后，根据栈信息和记录的结点路径变化程度得到最低公共祖先。如图1，假设输入的两个树结点为D和K，树的根节点为R，则求D和K的最低公共结点的过程如下表： 

步骤

栈

第一个结点

第二个结点

路径变化程度

1

R

—

—

—

2

R，A

—

—

—

3

R，A，F

—

—

—

4

R，A，F，J

—

—

—

5

R，A，F，G

—

—

—

6

R，A，F，K

K

—

0（或K）

7

R，A，C

K

—

1（或A）

8

R，A，C，E

K

—

2（或A）

9

R，A，C，I

K

—

2（或A）

10

R，A，D

K

D

1（或A）

è 得出结果，最低公共祖先结点为A

 

从中，可以看到，改进后的方案，只需对树执行一次遍历。而在辅助空间的需求上， 只需使用一个栈（外加少量结点指针变量和1个表示路径变化程度的整型变量）。而且，如果采用递归的方式实现，该栈所需保存的信息，还可以通过递归时的函数调用栈得以保存。

 

【附注】：

  1. 此处，有如下一个问题：
    假设待查找公共祖先的两树结点，其中一结点在以另一结点为根的子树上（包括两结点相同）时，公共祖先的确定规则——
    “作为子树根结点的那个结点”还是“子树根结点的父节点”？
    例如：对上面图1中的那棵树，如果待查结点为根结点R和结点F，那么最终的查找结果是为R呢，还是因为R是根结点无父结点而得出NULL？
    此问题在书中未提及，但查看书中代码，确认是选择了后者；而在本人的样例代码中则采用了前面的观点。
  2. 在样例代码中，对树结点在栈中的存储方式略有改动。
  3. 样例代码工程所使用的环境为 Visual C++ 2010；
    其中：tree.h/cpp为功能代码文件，TestLowestCommonAncestor.h/cpp为相应的UT代码文件；
    UT采用gtest所编写，编译链接请根据gtest在自己本机的路径状况修改gtest_link.props文件中相应的链接项。

 

posted @ 2012-04-05 23:45 青碧竹 阅读(3058) | 评论 (0) | 编辑 收藏

2012年3月30日 #

不使用 ＋－×÷ 运算符来实现 加减乘除 四项运算

     摘要: 最近，在看《剑指Offer——名企面试官精讲典型编程题》一书，当看到“面试题47：不用加减乘除做加法”时，经过一分钟左右思考后，得出了思路，跟书上一对照，基本一致，呵呵O(∩_∩)O~。于是，随即又开始思考：加法是实现了，那么减法、乘法还有除法又该怎么实现呢？一番思考与分析后，得出算法，写出代码，测试通过，Happy！！\(^...  阅读全文

posted @ 2012-03-30 01:30 青碧竹 阅读(4944) | 评论 (7) | 编辑 收藏

2012年3月17日 #

关于数值的整数次方的计算

在计算一个浮点数（双精度或单精度）的整数次方时，一般的，我们会直接使用 C++ 本身所提供的 pow 函数，事实上也推荐直接使用 pow 函数（为了称呼简便，后面称该 pow 函数为系统 pow 函数）。

但是，当我们准备写一个自己的 pow 时，我们又会怎么写呢？一般的，我们会写上一个 for 循环来循环幂的指数次，而且每次循环都会去执行一次浮点数的乘法操作。但是，当我们拿这个 pow 函数来跟系统 pow 函数作一运行比较时，就会发现，我们的 pow 实在是太低效了。那么怎么样才能使我们自己写的 pow 也能有系统函数那样的时间效率呢？

仔细分析，我们用的那个求幂值的循环过程，就能发现，其实我们还是做了很多不必要的浮点数乘法炒作。整个计算过程太过按步就班了。譬如说在计算 val（待传入pow 函数求幂的浮点数，下同） 的4次方，我们总是先计算出3次方的值，然后再根据3次方的值和原始值来求4次方的值；然而，我们其实本可以在计算出2次方值后，平方2次方值来得到4次方的值的。接下来，就是探索算法，以减少浮点数乘法的事了。

通过所学的指数函数的知识，我们知道指数函数有着这样的性质：

  • V(a+b) = Va * Vb
  • Va*b = (Va)b             ；这里 * 为乘法运算符

另外，对于整数，有如下性质：

  1.  2n = (1 << n)         ;这里 << 是向左移位的操作符。
  2. C++中的任何一个正整数（负整数同，但须处理好符合位）都可以表示为以下形式：
    n = 2a1 + 2a2 + ... + 2ak
    (其中，a1, a2, ... , ak 为闭区间 [0, 30] 上的整数值，且互不相同。)

由此，我们就可以事先依次计算出 val, val2, val4, ... , val30 预存备用，然后再根据 val 相应 bit 上是 1 还是 0，来选取相应的预存数据进行相乘，从而得到最终的结果。当然，合理设计逻辑，还可以减少所需的预存数据。下面是我的Pow 代码，欢迎点评。

 

#define INTBITS_WITHOUT_SIGN 31 // the bit-size of type int with the sign bit being excluded.


bool IsZero(double val, double precision /*= DEFAULT_PRECISION*/)
{
    if (precision >= 0) {
        return (-precision <= val) && (val <= precision);
    } else {
        return (precision <= val) && (val <= -precision);
    }
}

double Pow(double val, int exponent)
{
    if (IsZero(val)) {
        return 0.0;
    }

    if (0 == exponent) {
        return 1.0;
    }

    bool bIsExponentMinus = false;
    if (exponent < 0) {
        exponent = -exponent;
        bIsExponentMinus = true;
    }

    double tempVal[INTBITS_WITHOUT_SIGN];
    memset(tempVal, 0, INTBITS_WITHOUT_SIGN);
    tempVal[0] = val;

    double result = 1.0;
    int index = 0;
    while (exponent != 0) {
        if ((exponent & 1) != 0) {
            result *= tempVal[index];
        }

        exponent >>= 1;
        if (exponent != 0) {
            tempVal[index + 1] = tempVal[index] * tempVal[index];
            ++index;
        }
    }

    if (bIsExponentMinus) {
        result = 1.0 / result;
    }

    return result;
}

 
【补充】：

1. 在指数中，0的负数次方和0的0次方，都是没有意义的，所以对“if (IsZero(val))”分支内的处理如果能加上一些异常的输出就更好了，如：

   在Widows下，可通过 SetLastError(...) 来设置错误码。

2. Pow中的 “double tempVal[INTBITS_WITHOUT_SIGN];” 一句，改写为

   double * pTempVal = new double[sizeof(int) * 8 - 1];

(当然，后面代码中的tempVal 也都要改为相应的 pTempVal，同时须记得在return 前把delete [] pTempVal)

就可以使代码也能够适应于64位系统的处理。对于无符号整数的为指数的情况，则辅助值空间应为“sizeof(unsigned int) * 8”，同时，无需再考虑负指数的情况。

(这里，很感谢春秋十二月的补充。)
 

posted @ 2012-03-17 04:01 青碧竹 阅读(2947) | 评论 (4) | 编辑 收藏

2012年3月14日 #

Singleton模式——C++应用（四）

     摘要:  在前面的例子中，我们看到：采用 new 来为单件对象分配空间，如果采用手动调用 delete 或封装了 delete 的 Release 操作，一旦遇到全局对象的析构有调用单件对象，就会使得无法在代码中找到适合释放单件对象的时机。那么，是否可以让系统来自动选择时机，调用释放呢？如果可以，又该怎么在代码中构建单件对象的自动释放机制呢? 对这两个问题，在进行了一番思考和尝试后，终于找到了答...  阅读全文

posted @ 2012-03-14 01:07 青碧竹 阅读(329) | 评论 (0) | 编辑 收藏

2012年3月13日 #

Singleton模式——C++应用（三）

     摘要: 前面对C++的Singleton模式的探讨还都是针对通过静态变量来创建对象。但学习嘛，多走点总不是坏事。 接下来就来看看通过 new 来创建单件对象的单件类设计。既然是用 new 来创建了，那自然就不能忽略需要用 delete 来释放。 好了，先来看看代码： Code highlighting produced by Actipro CodeHighlighter (freeware)htt...  阅读全文

posted @ 2012-03-13 00:55 青碧竹 阅读(241) | 评论 (0) | 编辑 收藏

2012年3月12日 #

Singleton模式——C++应用（二）

看了通过静态成员实现的惰性单件，虽说构件简单且线程安全，但在被全局变量（包括静态全局变量）的构造或析构调用时，会存在着那样的缺陷毕竟还是很让人不爽。那么，是否存在保持上面的优点同时剔除了上面的缺陷的C++单件呢？

 

我们知道，定义于函数内部的静态局部变量，有着

  • 定义的实时性，即只在函数第一次被调用时才被定义
  • 线程安全性
  • 生命期直到程序结束

的特点。那么，通过这个局部静态变量来创建的单件又会是什么样呢？贴上我的Demo代码，这就来看看吧。

  1// Singleton demo_1: Singleton instance is a local static varible of class.
  2
  3#include <Windows.h>
  4#include <iostream>
  5
  6class A 
  7{
  8public:
  9    static A& GetInstance();
 10
 11private:
 12    A() : m_nStat1(-1), m_nStat2(-1) {
 13        m_nStat1 = 0;
 14        std::cout << "Construct A" << std::endl;
 15        m_nStat2 = 0;
 16    }
 17    A(const A&);
 18
 19public:
 20    ~A() {
 21        m_nStat1 = 0;
 22        std::cout << "Destruct A" << std::endl;
 23        m_nStat2 = 0;
 24    }
 25
 26    void Do() {
 27        ++m_nStat1;
 28        ++m_nStat2;
 29        std::cout << "Called Do() by object of A. [" 
 30                  << m_nStat1 << ", " 
 31                  << m_nStat2 << "]" 
 32                  << std::endl;
 33    }
 34
 35private:
 36    int m_nStat1;
 37    int m_nStat2;
 38};
 39
 40class B
 41{
 42public:
 43    B(int nID) : m_nID(nID) {
 44        std::cout << "Construct B: " << m_nID << std::endl;
 45        A::GetInstance().Do();
 46    }
 47    ~B() {
 48        std::cout << "Destruct B: " << m_nID << std::endl;
 49        A::GetInstance().Do();
 50    }
 51
 52private:
 53    int m_nID;
 54};
 55
 56class C
 57{
 58public:
 59    static C& GetInstance();
 60
 61private:
 62    C() : m_nStat(-1) {
 63        std::cout << "Construct C" << std::endl;
 64        m_nStat = 0;
 65    }
 66    C(const C&);
 67
 68public:
 69    ~C() {
 70        std::cout << "Destruct C" << std::endl;
 71        m_nStat = 0;
 72    }
 73
 74    void Do() {
 75        ++m_nStat;
 76        std::cout << "Called Do() by object of C. [" 
 77            << m_nStat << "]" 
 78            << std::endl;
 79    }
 80
 81private:
 82    int m_nStat;
 83};
 84
 85static B gs_B0(0);
 86B g_B1(1);
 87
 88A& A::GetInstance()
 89{
 90    static A s_instance;
 91    
 92    return s_instance;
 93}
 94
 95C& C::GetInstance()
 96{
 97    static C s_instance;
 98
 99    return s_instance;
100}
101
102static B gs_B2(2);
103B g_B3(3);
104
105int main(int argc, char * argv[])
106{
107    std::cout << "Enter main" << std::endl;
108    A::GetInstance().Do();
109    C::GetInstance().Do();
110
111    system("pause");
112    return 0;
113}
114

 接下来，自然就是执行结果：

哟吼~，这不正是自己想要的结果么，Perfect！！

构建简单，创建具有实时性（在且只在第一次用到时创建），线程安全，可以被全局变量的构造和析构正常调用，就是它了，极力推荐！O(∩_∩)O~

 

posted @ 2012-03-12 02:08 青碧竹 阅读(227) | 评论 (0) | 编辑 收藏

Singleton模式——C++应用（一）

     前天，在看了《剑指Offer》中关于Singleton模式的一段内容后，就按耐不住对其在C++上完美实现的思考。书中这一讲是针对C#的实现来讲解的，因为C#的垃圾回收机制，其中那些个显眼的[new]已无需程序员去手动释放。但是，C++上确并不存在垃圾回收机制，程序员得手动[delete] [new]出来的内容，这就有了以下两问：
  1. 何时释放通过new所创建的Singleton对象？
  2. 如果不通过new、malloc等操作，是否能做到在第一次使用时才创建Singleton对象。

     在针对以上两个问题做了一番思考和尝试之后，终于有了成果。现呈现出来，供大家参考，也希望有更好妙招的朋友能不吝赐教。碍于连代码带文字，篇幅较长，所以我将分为四篇来讲。那么，开始咯！^_^

 

     一开始，我先拿使用静态成员变量的来实现的惰性单件来进行尝试，写了个Demo，一运行，O(∩_∩)O哈哈~，还真有意外的收获呢！嗯~，抓紧时间，先把我的Demo上来给大家瞧瞧！~

  1// Singleton demo_0: Singleton instance is a static member of class.
  2
  3#include <Windows.h>
  4#include <iostream>
  5
  6class A 
  7{
  8private:
  9    static A ms_instance;
 10
 11public:
 12    static A& GetInstance() {
 13        return ms_instance;
 14    }
 15
 16private:
 17    A() : m_nStat1(-1), m_nStat2(-1) {
 18        m_nStat1 = 0;
 19        std::cout << "Construct A" << std::endl;
 20        m_nStat2 = 0;
 21    }
 22    A(const A&);
 23
 24public:
 25    ~A() {
 26        m_nStat1 = 0;
 27        std::cout << "Destruct A" << std::endl;
 28        m_nStat2 = 0;
 29    }
 30
 31    void Do() {
 32        ++m_nStat1;
 33        ++m_nStat2;
 34        std::cout << "Called Do() by object of A. [" 
 35                  << m_nStat1 << ", " 
 36                  << m_nStat2 << "]" 
 37                  << std::endl;
 38    }
 39
 40private:
 41    int m_nStat1;
 42    int m_nStat2;
 43};
 44
 45class B
 46{
 47public:
 48    B(int nID) : m_nID(nID) {
 49        std::cout << "Construct B: " << m_nID << std::endl;
 50        A::GetInstance().Do();
 51    }
 52    ~B() {
 53        std::cout << "Destruct B: " << m_nID << std::endl;
 54        A::GetInstance().Do();
 55    }
 56
 57private:
 58    int m_nID;
 59};
 60
 61class C
 62{
 63private:
 64    static C ms_instance;
 65
 66public:
 67    static C& GetInstance() {
 68        return ms_instance;
 69    }
 70
 71private:
 72    C() : m_nStat(-1) {
 73        std::cout << "Construct C" << std::endl;
 74        m_nStat = 0;
 75    }
 76    C(const C&);
 77
 78public:
 79    ~C() {
 80        std::cout << "Destruct C" << std::endl;
 81        m_nStat = 0;
 82    }
 83
 84    void Do() {
 85        ++m_nStat;
 86        std::cout << "Called Do() by object of C. [" 
 87            << m_nStat << "]" 
 88            << std::endl;
 89    }
 90
 91private:
 92    int m_nStat;
 93};
 94
 95static B gs_B0(0);
 96B g_B1(1);
 97A A::ms_instance;
 98C C::ms_instance;
 99static B gs_B2(2);
100B g_B3(3);
101
102int main(int argc, char * argv[])
103{
104    std::cout << "Enter main" << std::endl;
105    A::GetInstance().Do();
106    C::GetInstance().Do();
107
108    system("pause");
109    return 0;
110}

为了能够分析得细致些，Demo写得长了点，见谅咯！~

    嗯，对了，还有运行结果：

仔细看看结果，有没觉得这结果很出乎意料啊？！！（顺便提下，我用的编译工具是Visual C++ 2010）

从这个运行结果，对通过静态成员实现的惰性单件，我得到了以下两点：

  1. 对于定义在单件对象之前的全局或静态全局对象，虽然单件对象还是会在调用前及时构造，但构造函数内的初始化操作却可能在需要使用时还未能执行完全。
    如：std::cout 就会使得单件对象的构造函数调用被暂停（单件的其他操作还能继续调用），直到单件之前的全局或静态全局的构造函数全执行完了，才能继续执行。【*这个原因还请有知道的高手能赐教。】
  2. 对于定义于单件对象之后的全局或静态全局对象，如果在析构中调用了单件，就会使得单件在释放后又被再次重新创建使用。当然，这时单件内所存的数据已跟之前毫无关联了。

因此，我要奉劝各位开发者，如果在你的全局或静态全局对象的构造或析构方法中调用某个单件，那么对该单件的实现就不要以静态成员来惰性地实现。

 

posted @ 2012-03-12 02:04 青碧竹 阅读(271) | 评论 (0) | 编辑 收藏

仅列出标题