光辉 的个人资料胡言乱语照片日志列表更多 工具 帮助
2006/10/28

常数附加空间的非递归方法遍历二叉树

class TreeNode
{
    TreeNode* leftchild;
    TreeNode* rightchild;
    TreeNode* parent;
    T  data;
}
 
//前序遍历
PreOrder(TreeNode* root)
{
    TreeNode* t = root;
    while(1)   
    {
        visit(t);
        if (null != t->leftchild) {
            t = t->leftchild;
        } else if (null != t->rightchild) {
            t = t->rightchild; 
        } else {
            while (t->parent && ( null == t->parent->rightchild || t == t->parent->rightchild) )
                   t  = t->parent;
 
            if (null == t->parent) 
                break;
            else
                t = t->parent->rightchild;
        }
    }
}
 
如果要遍历的树有n个节点,则运行时间的上界为3n。
这是因为对于树中的每个节点,最多有3个指针指向它(父节点的指针以及两个孩子的父指针),
所以对于某个给定的节点,最多经过3次。所以对于有n个节点的树来说,遍历时间的上界为3n。
由于根节点和叶子节点的存在,事实上不可能达到3n。
 
2006/10/14

C++中结构的内存结构

1) 无数据成员的结构
struct s_0 { // };
在C++ 中 sizeof(s_0) = 1
在C语言中 sizeof(s_0) = 0

在C++中一个struct中可以有成员函数,例如:
struct s1 { void f(); }  A;
struct s2 { void f(); }  B;
如果 sizeof(s1) = 0,  sizeof(s2) =0, 那么A, B将会有相同的内存地址,所以无数据成员的结构应当拥有最小的非零长度。

2)
struct s_char_int
{
       char a;
       int   b;
}

sizeof(s_char_int) = 8, 而不是sizeof(char) + sizeof(int) = 1 + 4 =5。

3)
struct s_carray_int_char
{
      char     a[3];
      int        b;
      char     c;
}

struct s_carray_char_int
{
      char     a[3];
      char     c;
      int        b;
}

以上两个结构含有相同的数据成员,但是数据成员的先后顺序不同。
sizeof(s_carray_int_char) = 12;
sizeof(s_carray_char_int) = 8;

2006/10/11

C++中浮点变量与零值的比较

今天下午参加了一个笔试,考的题目就是《高质量C/C++编程指南》后面附带的试题。当时感觉还不错,回来后看了一下答案,发现还是很有差距。
其中第一题问道:写出 float x 与 “零值”比较的 if 语句。我当下就写下了 if ( 0.0 == x )可答案是:
 
const float EPSINON = 0.00001;
if ( (x >= -EPSINON) && (x <= EPSINON ) )
 
看完后还不明所以!
 
再看《高质量C/C++编程指南》,有如下解释:
【规则4-3-3】不可将浮点变量用“==”或“!=”与任何数字比较。
千万要留意,无论是float 还是double 类型的变量,都有精度限制。所以一定要避
免将浮点变量用“==”或“!=”与数字比较,应该设法转化成“>=”或“<=”形式。
假设浮点变量的名字为x,应当将
if (x == 0.0) // 隐含错误的比较
转化为
if ((x>=-EPSINON) && (x<=EPSINON))
其中EPSINON 是允许的误差(即精度)。