/********************************************\
|    欢迎转载, 但请保留作者姓名和原文链接, 祝您进步并共勉!     |
\********************************************/

C++对象模型(9) - 3.1 The Binding of a Data Member

作者: Jerry Cat
时间: 2006/11/15
链接:  http://www.cppblog.com/jerysun0818/archive/2006/11/15/15186.html

3.1 The Binding of a Data Member

Consider the following program fragment:.

// A third party foo.h header file
// pulled in from somewhere
extern float x;

// the programmer's Point3d.h file
class Point3d
{
public:
   Point3d( float, float, float );
   // question:  which x is returned and set?
   float X() const { return x; }
   void X( float new_x ) const { x = new_x; }
   // ...
private:
   float x, y, z;
};
If I were to ask which x the Point3d member X() returns—the class instance or the extern instance—everyone today would answer the class instance, and everyone would be right. Most everyone, however, would probably be surprised to learn that this answer was not always correct.

早期的C++将其解析为X()函数引用的是全局数据. 所以早期的C++程序员发明了俩防范写法(至今还有人用):
(1). Placing all data members first in the class declaration to ensure the right binding:

class Point3d
{
   // defensive programming style #1
   // place all data first ...
   float x, y, z;
public:
   float X() const { return x; }
   // ... etc. ...
};

(2). Placing all inline functions, regardless of their size, outside the class declaration:

class Point3d
{
public:
   // defensive programming style #2
   // place all inlines outside the class
   Point3d();
   float X() const;
   void X( float ) const;
   // ... etc. ...
};
inline float
Point3d::
X() const
{
   return x;
}

// ... etc. ...

extern int x;

class Point3d
{
public:
   ...
   // analysis of function body delayed until
   // closing brace of class declaration seen.
   float X() const { return x; }
   ...
private:
   float x;
   ...
};

// in effect, analysis is done here
the analysis of the member function's body is delayed until the entire class declaration is seen. Thus the binding of a data member within the body of an inline member function does not occur until after the entire class declaration is seen.

但是This is not true of the argument list of the member function, however. Names within the argument list are still resolved in place at the point they are first encountered. Nonintuitive bindings between extern and nested type names, therefore, can still occur. In the following code fragment, for example, the type of length in both member function signatures resolves to that of the global typedef—that is, to int. When the subsequent declaration of the nested typedef of length is encountered, the Standard requires that the earlier bindings be flagged as illegal:

typedef int length;

class Point3d
{
public:
   // oops: length resolves to global
   // ok: _val resolves to Point3d::_val
   mumble( length val ) { _val = val; }
   length mumble() { return _val; }
   // ...

private:
   // length must be seen before its first
   // reference within the class.  This
   // declaration makes the prior reference illegal.
   typedef float length;
   length _val;
   // ...
};
This aspect of the language still requires the general defensive programming style of always placing nested type declarations at the beginning of the class. In our example, placing the nested typedef defining length above any of its uses within the class corrects the nonintuitive binding.(数据成员定义还是要放在最前面)

/********************************************\
|    欢迎转载, 但请保留作者姓名和原文链接, 祝您进步并共勉!     |
\********************************************/

C++对象模型(8) - Chapter 3. The Semantics of Data
 

作者: Jerry Cat
时间: 2006/11/15
链接:  http://www.cppblog.com/jerysun0818/archive/2006/11/15/15185.html

;-----------------------------------------------------------------------
;Chapter 3. The Semantics of Data
;-----------------------------------------------------------------------
Chapter 3. The Semantics of Data - 空类不空

class X {};
class Y : public virtual X {};
class Z : public virtual X {};
class A : public Y, public Z {};
None of these classes contains any explicit data—any anything, in fact, except an inheritance
relationship—so he apparently believed the size of each class should be 0. It wasn't,
of course—not even the apparently benign class X:

sizeof X yielded 1
sizeof Y yielded 8
sizeof Z yielded 8
sizeof A yielded 12
Let's look at each declaration in turn and see what's going on. An empty class, such as

// sizeof X == 1
class X {};
in practice is never empty. Rather it has an associated size of 1 byte—a char member inserted
by the compiler. This allows two objects of the class, such as

X a, b;
if ( &a == &b ) cerr << "yipes!" << endl;//to be allocated unique addresses in memory.哈!

// sizeof Y == sizeof Z == 8
class Y : public virtual X{};
class Z : public virtual X{};
On his machine, the size of both classes Y and Z is 8. This size, however, is partially machine dependent. It also depends in part on the compiler implementation being used. The given size of both class Y and class Z on any machine is the interplay of three factors:

(1). Language support overhead. There is an associated overhead incurred in the language support of virtual base classes. Within the derived class, this overhead is reflected as some form of pointer, either to the virtual base class subobject or to an associated table within which either the address or offset to the virtual base class subobject is stored. On my correspondent's machine, the pointer is 4 bytes. (Virtual base classes are discussed in Section 3.4.)

(2). Compiler optimization of recognized special cases. There is the 1 byte size of the virtual base class X subobject also present within Y (and Z). Traditionally, this is placed at the end of the "fixed" (that is, invariant) portion of the derived class. Some compilers now provide special support for an empty virtual base class (the paragraph following item 3 discusses this in more detail). Our correspondent's compiler, however, did not provide this special handling.

(3). Alignment constraints. The size of class Y (and Z) at this point is 5 bytes. On most machines, aggregate structures have an alignment constraint so that they can be efficiently loaded from and stored to memory. On my correspondent's machine, alignment of an aggregate is on a 4-byte boundary. So class Y (and Z) requires 3 bytes of padding. The result is a final size of 8.

The C++ object model representation for nonstatic data members optimizes for space and access time (and to preserve compatibility with the C language layout of the C struct) by storing the members directly within each class object. This is also true for the inherited nonstatic data members of both virtual and nonvirtual base classes, although the ordering of their layout is left undefined. Static data members are maintained within the global data segment of the program and do not affect the size of individual class objects.(静态数据成员被放在全局数据段, 并不影响单个类的大小)
 
Only one instance of a static data member of a class exists within a program regardless of the number of times that class is an object of direct or indirect derivation. (The static data members of a template class behave slightly differently. See Section 7.1 for a discussion.)模板类的静态数据成语有所不同

类的大小让你吃惊地"大"的原因来源于2方面:
(1). Additional data members added by the compilation system to support some language functionality (primarily the virtuals)

(2). Alignment requirements on the data members and data structures as a whole

从笑话中悟出C++开发管理之"道"

1. 程序员写出自认为没有Bug的代码。

2. 软件测试，发现了20个Bug。

3. 程序员修改了10个Bug，并告诉测试组另外10个不是Bug。

4. 测试组发现其中5个改动根本无法工作，同时又发现了15个新Bug。

5. 重复3次步骤3和步骤4。

6. 鉴于市场方面的压力，为了配合当初制定的过分乐观的发布时间表，产品终于上市了。

7. 用户发现了137个新Bug。

8. 已经领了项目奖金的程序员不知跑到哪里去了。

9. 新组建的项目组修正了差不多全部137个Bug，但又发现了456个新Bug。

10. 最初那个程序员从斐济给饱受拖欠工资之苦的测试组寄来了一张明信片。整个测试组集体辞职.

11. 公司被竞争对手恶意收购。收购时，软件的最终版本包含783个Bug。

12. 新CEO走马上任。公司雇了一名新程序员重写该软件。

13. 程序员写出自认为没有Bug的代码。

　　要我说，如果真有这样的公司，不倒闭对不起人民。

　这个笑话从程序员开始，到程序员结束，从头到尾都在说程序员的不是。但是我要说的是，这完全是管理者的失败，从整个过程中，看不到任何管理工作。这种管理者不但无知无能，还很无耻——将自己的失败责任推给程序员。

　1、程序员凭什么证明他的代码没有BUG？有Test case吗？有Code review吗？这个环节管理缺失。

　2、测试发现BUG有进行BUG管理吗？有跟踪吗？这个环节管理缺失。
　3、凭什么证明程序员已经把那10个BUG修改好了？另10个又为什么不是BUG？BUG的评价标准难道是程序员说了算？这个环节管理缺失。

　4、5个不能工作的BUG修改问题有没有追究责任？增加新BUG是修改过程中不可避免的事情，但是如果有有效的单元测试机制，可以大大减少这种情况。这个环节管理缺失。

　5、迭代是正常的，但是问题处理于发散而不是收敛发展，可见没有有效的管理调控。这个环节管理缺失。

　6、过于乐观的时间表和不可能达到的最后期限，都表现出管理者的无知和无能。而在这样的情况下强行推出产品，那就是无知者无畏了。

　7、这是对用户的不负责任，管理者要负最大的责任。

　8、这样的情况还能发项目奖金，只能说管理者不是一般的愚蠢。

　9、管理工作没有任何的改进，问题仍然处于发散迭代状态。管理工作依然没有到位。

　10、拖欠测试部门工资体现出管理者对质量管理工作的忽视以及对人力资源管理方面一无所知。

　11、送被收购者两个字：活该。送收购者两个字：瞎眼。

　12、可见新管理者与原管理者半斤八两，都没有认识到问题的根本所在。不过也只有这样的管理者才会作出收购这种公司的决策。

　13、历史的重演是必然的。

　一个正常的企业或是项目，其运作必须应该是循环向上进行的。而保障这种运行的工作就是管理。而管理工作的主要内容就是控制，包括控制循环的节奏——不能太快也不能太慢，控制发展的方向——只能向上不能向下，控制运作的稳定——不能大起大落或时聚时散等。
　而这一切，在这个例子中都看不到。

　在这个笑话的例子中，一切都是以开发工作在驱动，这首先就是一个方向性错误，产品是为用户服务的，当然应该是以用户和市场作为驱动，并且结合自身的能力最终 确定工作的重点。这一错误折射出管理者对被管理的内容很不了解，只好任由比较了解的程序员摆布——事实上他们除了技术，并不会了解更多。

　一个管理者如果对自己所管理的内容不了解，他就不可能管理得好。

　这是一件毫无疑问的事，可是国内的软件业似乎总是不相信这一点。中国软件业中流毒最深的谎言之一就是：

　管理者只要懂管理就可以，不需要懂技术。

其实这不过是那些无知无能无耻的管理者为了骗钱而编出来的，相信这句话的人必将付出金钱的代价。

　其次是质量管理。基本的质量管理常识告诉我们，每次循环结束前，最重的工作就是总结改进。只有这样才能保证循环运作是向上发展，而不是失去控制地向下发展。 也只有有效的质量管理，才能保证迭代过程是收敛发展，并最终达到目标。但在这个例子中，这个部分显然是缺失的——其中虽然有测试部门，但是他们的作用仅仅 是质量管理中的质量检测环节，管理部分还是缺失的。

　然后是人力资源管理。软件开发是一项劳动密集型的工作，虽然这是脑力劳动，但同样意味着人在因素在其中占有决定性的地位。而例子中未改完BUG的程 序员拿到项目奖金，而同样辛苦工作的测试人员却被拖欠薪资，除了表现出管理者对他们的工作内容的不了解，以及对质量管理工作的不重视以外，还表现出管理者 完全不会管人，这是一种谋杀团队的行为——谋杀一个团队远比建设要容易得多。

　最后，这个失败的管理者把他的经历编成这个笑话，让大家看到他被程序员们害得多惨，把程序员妖魔化为一群骗子。但只要稍懂管理的人简单分析一下就可以看出来，只不过是这个人的无知和无能造成了他现在的结果，而把责任推给别人的行为更是表现出他的无耻。

　作为身居高位的管理者，如果连应该承担的责任都要推卸，他们还能胜任什么事情呢?

函数指针的声明和回调的实现

   程序员常常需要实现回调。本文将讨论函数指针的基本原则并说明如何使用函数指针实现回调。注意这里针对的是普通的函数，不包括完全依赖于不同语法和语义规则的类成员函数（类成员指针将在另文中讨论）。

声明函数指针

   回调函数是一个程序员不能显式调用的函数；通过将回调函数的地址传给调用者从而实现调用。要实现回调，必须首先定义函数指针。尽管定义的语法有点不可思议，但如果你熟悉函数声明的一般方法，便会发现函数指针的声明与函数声明非常类似。请看下面的例子：

void f()；// 函数原型

上面的语句声明了一个函数，没有输入参数并返回void。那么函数指针的声明方法如下：

void (*) ();

   让我们来分析一下，左边圆括弧中的星号是函数指针声明的关键。另外两个元素是函数的返回类型（void）和由边圆括弧中的入口参数（本例中参数是空）。注意本例中还没有创建指针变量-只是声明了变量类型。目前可以用这个变量类型来创建类型定义名及用sizeof表达式获得函数指针的大小：

// 获得函数指针的大小
unsigned psize = sizeof (void (*) ());

// 为函数指针声明类型定义
typedef void (*pfv) ();

pfv是一个函数指针，它指向的函数没有输入参数，返回类行为void。使用这个类型定义名可以隐藏复杂的函数指针语法。

指针变量应该有一个变量名：

void (*p) (); //p是指向某函数的指针

   p是指向某函数的指针，该函数无输入参数，返回值的类型为void。左边圆括弧里星号后的就是指针变量名。有了指针变量便可以赋值，值的内容是署名匹配的函数名和返回类型。例如：

void func()
{
/* do something */
}
p = func;

p的赋值可以不同，但一定要是函数的地址，并且署名和返回类型相同。

传递回调函数的地址给调用者

   现在可以将p传递给另一个函数（调用者）- caller()，它将调用p指向的函数，而此函数名是未知的：

void caller(void(*ptr)())
{
ptr(); /* 调用ptr指向的函数 */
}
void func();
int main()
{
p = func;
caller(p); /* 传递函数地址到调用者 */
}

   如果赋了不同的值给p（不同函数地址），那么调用者将调用不同地址的函数。赋值可以发生在运行时，这样使你能实现动态绑定。

调用规范

   到目前为止，我们只讨论了函数指针及回调而没有去注意ANSI C/C++的编译器规范。许多编译器有几种调用规范。如在Visual C++中，可以在函数类型前加_cdecl，_stdcall或者_pascal来表示其调用规范（默认为_cdecl）。C++ Builder也支持_fastcall调用规范。调用规范影响编译器产生的给定函数名，参数传递的顺序（从右到左或从左到右），堆栈清理责任（调用者或者被调用者）以及参数传递机制（堆栈，CPU寄存器等）。

   将调用规范看成是函数类型的一部分是很重要的；不能用不兼容的调用规范将地址赋值给函数指针。例如：

// 被调用函数是以int为参数，以int为返回值
__stdcall int callee(int);

// 调用函数以函数指针为参数
void caller( __cdecl int(*ptr)(int));

// 在p中企图存储被调用函数地址的非法操作
__cdecl int(*p)(int) = callee; // 出错

   指针p和callee()的类型不兼容，因为它们有不同的调用规范。因此不能将被调用者的地址赋值给指针p，尽管两者有相同的返回值和参数列。

mutable关键字

关键字mutable是C++中一个不常用的关键字,他只能用于类的非静态和非常量数据成员
我们知道一个对象的状态由该对象的非静态数据成员决定,所以随着数据成员的改变,
对像的状态也会随之发生变化!

如果一个类的成员函数被声明为const类型,表示该函数不会改变对象的状态,也就是
该函数不会修改类的非静态数据成员.但是有些时候需要在该类函数中对类的数据成员
进行赋值.这个时候就需要用到mutable关键字了

例如:
class Demo
{
public:
    Demo(){}
    ~Demo(){}
public:
    bool getFlag() const
    {
        m_nAccess++;
        return m_bFlag;
    }
private:
    int  m_nAccess;
    bool m_bFlag;
};

int main()
{
    return 0;
}

编译上面的代码会出现 error C2166: l-value specifies const object的错误
说明在const类型的函数中改变了类的非静态数据成员.

这个时候需要使用mutable来修饰一下要在const成员函数中改变的非静态数据成员
m_nAccess,代码如下:

class Demo
{
public:
    Demo(){}
    ~Demo(){}
public:
    bool getFlag() const
    {
        m_nAccess++;
        return m_bFlag;
    }
private:
    mutable int  m_nAccess;
    bool m_bFlag;
};

int main()
{
    return 0;
}

这样再重新编译的时候就不会出现错误了!

 

 

volatile关键字

volatile是c/c++中一个鲜为人知的关键字,该关键字告诉编译器不要持有变量的临时拷贝,它可以适用于基础类型
如：int,char,long......也适用于C的结构和C++的类。当对结构或者类对象使用volatile修饰的时候，结构或者
类的所有成员都会被视为volatile.

使用volatile并不会否定对CRITICAL_SECTION,Mutex,Event等同步对象的需要
例如：
int i;
i = i + 3;
无论如何，总是会有一小段时间，i会被放在一个寄存器中，因为算术运算只能在寄存器中进行。一般来说，volatitle
关键字适用于行与行之间，而不是放在行内。

我们先来实现一个简单的函数，来观察一下由编译器产生出来的汇编代码中的不足之处，并观察volatile关键字如何修正
这个不足之处。在这个函数体内存在一个busy loop(所谓busy loop也叫做busy waits,是一种高度浪费CPU时间的循环方法)

void getKey(char* pch)
{
 while (*pch == 0)
  ;
}

当你在VC开发环境中将最优化选项都关闭之后，编译这个程序，将获得以下结果(汇编代码)
;       while (*pch == 0)
$L27
 ; Load the address stored in pch
 mov eax, DWORD PTR _pch$[ebp]
 ; Load the character into the EAX register
 movsx eax, BYTE PTR [eax]
 ; Compare the value to zero
 test eax, eax
 ; If not zero, exit loop
 jne $L28
 ;
 jmp $L27
$L28
;}

这段没有优化的代码不断的载入适当的地址，载入地址中的内容，测试结果。效率相当的低，但是结果非常准确

现在我们再来看看将编译器的所有最优化选项开关都打开以后，重新编译程序，生成的汇编代码，和上面的代码
比较一下有什么不同
;{
 ; Load the address stored in pch
 mov eax, DWORD PTR _pch$[esp-4]
 ; Load the character into the AL register
 movsx al, BYTE PTR [eax]
; while (*pch == 0)
 ; Compare the value in the AL register to zero
 test al, al
 ; If still zero, try again
 je SHORT $L84
 ;
;}

从代码的长度就可以看出来，比没有优化的情况要短的多。需要注意的是编译器把MOV指令放到了循环之外。这在
单线程中是一个非常好的优化，但是，在多线程应用程序中，如果另一个线程改变了变量的值，则循环永远不会
结束。被测试的值永远被放在寄存器中，所以该段代码在多线程的情况下，存在一个巨大的BUG。解决方法是重新
写一次getKey函数，并把参数pch声明为volatile,代码如下：

void getKey(volatile char* pch)
{
 while (*pch == 0)
  ;
}

这次的修改对于非最优化的版本没有任何影响，下面请看最优化后的结果：

;{
 ; Load the address stored in pch
 mov eax, DWORD PTR _pch$[esp-4]
;       while (*pch == 0)
$L84:
 ; Directly compare the value to zero
 cmp BYTE PTR [eax], 0
 ; If still zero, try again
 je SHORT $L84
 ;
;}

这次的修改结果比较完美，地址不会改变，所以地址声明被移动到循环之外。地址内容是volatile,所以每次循环
之中它不断的被重新检查。

把一个const volatile变量作为参数传递给函数是合法的。如此的声明意味着函数不能改变变量的值，但是变量的
值却可以被另一个线程在任何时间改变掉。

explicit关键字

我们在编写应用程序的时候explicit关键字基本上是很少使用,它的作用是"禁止单参数构造函数"被用于自动型别转换,
其中比较典型的例子就是容器类型,在这种类型的构造函数中你可以将初始长度作为参数传递给构造函数.
例如:
你可以声明这样一个构造函数
class Array
{
public:
 explicit Array(int size);
 ......
};
在这里explicit关键字起着至关重要的作用,如果没有这个关键字的话,这个构造函数有能力将int转换成Array.一旦这种
情况发生,你可以给Array支派一个整数值而不会引起任何的问题,比如:
Array arr;
...
arr = 40;
此时,C++的自动型别转换会把40转换成拥有40个元素的Array,并且指派给arr变量,这个结果根本就不是我们想要的结果.如果
我们将构造函数声明为explicit,上面的赋值操作就会导致编译器报错,使我们可以及时发现错误.
需要注意的是:explicit同样也能阻止"以赋值语法进行带有转型操作的初始化";
例如:
Array arr(40);//正确
Array arr = 40;//错误

看一下以下两种操作:
X x;
Y y(x);//显式类型转换
另一种
X x;
Y y = x;//隐式类型转换

这两种操作存在一个小小的差别,第一种方式式通过显式类型转换,根据型别x产生了型别Y的新对象;第二种方式通过隐式转换
产生了一个型别Y的新对象.
explicit关键字的应用主要就是上面所说的构造函数定义种,参考该关键字的应用可以看看STL源代码,其中大量使用了该关键字

 

__based关键字

该关键字主要用来解决一些和共享内存有关的问题,它允许指针被定义为从某一点开始算的32位偏移值,而不是内存种的绝对位置
举个例子:

typedef struct tagDEMOSTRUCT {
 int a;
 char sz[10];
} DEMOSTRUCT, * PDEMOSTRUCT;

HANDLE hFileMapping = CreateFileMapping(...);
LPVOID lpShare = (LPDWORD)MapViewOfFile(...);

DEMOSTRUCT __based(lpShare)* lpDemo;

上面的例子声明了一个指针lpDemo,内部储存的是从lpShare开始的偏移值,也就是lpHead是以lpShare为基准的偏移值.
上面的例子种的DEMOSTRUCT只是随便定义的一个结构,用来代表任意的结构.

虽然__based指针使用起来非常容易,但是,你必须在效率上付出一定的代价.每当你用__based指针处理数据,CPU都必须
为它加上基地址,才能指向真正的位置.

在这里我只是介绍了几个并不时很常见的关键字的意义即用法,其他那些常见的关键字介绍他们的文章已经不少了在这里
就不再一一介绍了.希望这些内容能对大家有一定的帮助!

方兴东抨击博客实名制 称此举将摧毁中国博客 出处：TOM科技| 2006年10月20日 14:51           现在还不清楚博客实名制的实际情况，所以简单评论还为时过早。但是，可以肯定的是，如果违背博客本质，违背全球互联网基本规则，推进不合理的实名制，那么，这项政策的直接后果就是对国内博客服务造成明显的FUD效应（担心、疑虑和怀疑），犯下中国互联网有史以来最大的错误！也是难以挽回的错误。 博客用户在失去基本安全感的情况下，首先选择千百万家国外的博客网站。因为，未来任何一个大型网站都将提供博客服务。除非中国全面封闭互联网，否则选择国外的博客服务成为中国网民的必然。 这种不合理政策将直接摧毁中国新兴的博客服务网站，成为国外博客网站市场推广最好的方式。将造成中国博客全面向国外服务商迁移，失去一个产业的发展机会。目前，拥有千万级博客用户的国外博客网站，已经有10家左右。百万级用户的国外博客网站在数十家之多。加上各大网站都已经或者很快提供博客服务。国外博客网站将是中国实名制政策的最大赢家。变相为它们做最强有力的推广。 因为中国不可能让全世界的博客网站都接受中国特色的实名制，所以国内博客网站将受到摧毁性的打击（除非中国互联网与世隔绝）。而更大的损失还不仅仅在于几家博客网站本身。 中国的博客用户如果全面迁移到国外博客网站，被迫流浪，那么，中国互联网将成为一座空城，中国2.0应用将失去真正用户的家，那时候，不要说控制，就是基本的管理和引导都无从谈起。未来中国的网络社会将失去自己的网络国民。博客在国外安家落户，要再迁移回来其难度就不可同日而语，成本巨大！所以，今后连纠错的机会都很难！ 所以，不符合博客发展的内在规律，不与全世界互联网发展接轨，而出台不合理的实名制，损害的将不仅仅是博客行业和互联网行业，而是断送中国整个社会和未来。 建设好中国互联网和博客，很不容易，但是要毁掉却很容易。所以，我始终坚信，中国互联网发展十年，成绩辉煌。不可能会有人要苦心积虑把它摧毁掉，不可能让发展开倒车。所以，在这个简单的逻辑下，在实名制风雨欲来的舆论中，我始终保持乐观心态：不合理的实名制不可能实行。 也就是说，这个问题的本质在于：谁敢摧毁中国互联网的发展？！其用意和出发点何在？！ (此文来自方兴东的博客)

C++面试题集4

一. 华为一道面试题-1-n排序

有N个大小不等的自然数（1--N），请将它们由小到大排序。
要求程序算法：时间复杂度为O(n)，空间复杂度为O(1)。

网上转的，一开始也没有注意到最开始的半句。

算法：N个不等的自然数1~N，排序完成后必然为1~N。所以可以一次遍历，遇到a[i]!=i的就把a[i]和a[a[i]]交换。

void sort(int a[], int n)
{
 int i;
 int t; /*临时变量：空间复杂度O(1)*/

 for (i=1; i<n+1; i++) /*时间复杂度O(n)*/
 {
 while(a[i]!=i)
  {
 t = a[a[i]];
 a[a[i]] = a[i];//排好一个元素
 a[i] = t;
  }
 }
}

二. 一次遍历 找 链表倒数第n个节点

 一道面试题目，阿明和晨晨看到并且告诉我答案的。要求通过一次遍历找到链表中倒数第n个节点，链表可能相当大，可使用辅助空间，但是辅助空间的数目必须固定，不能和n有关。
算法思想：两根指针，第一根先出发，相距n步后第二根出发。然后同时步进，直到第一根指针达到末尾。

struct iNode {
int value;
iNode * next;
};
iNode * getresult(iNode * head,int n)
{

iNode *pfirst;
iNode *psecond;

pfirst=head;
int counter;

for(counter=0;counter<n;counter++) {
 pfirst=pfirst->next;
}

psecond=head;

while(pfirst!=NULL) {
 pfirst=pfirst->next;
 psecond=psecond->next;
}

return psecond;

}

三. VC++学习笔记

1.       日期转成字符串：

   COleDateTime    ww;
ww=COleDateTime::GetCurrentTime();
AfxMessageBox(ww.Format("%Y-%m-%d %H:%M:%S"));

2.       字符串转成日期：

COleDateTime dt;

       dt.ParseDateTime(“2006-08-08 08:08:08”);

3.       资源文件

资源文件名:xxx.rc,其中要包含的主要文件:resource.h和afxres.h

4.       vc开发环境没有自动提示时:

   删除 目录下的ncb文件 ，再打开一般就ok了

5.       利用_variant_t 取数据库数据的方法:

   _variant_t ibb;

       ibb=(_variant_t)rs->GetCollect("inta");

       if(ibb.vt!=VT_NULL)

       {

              m_b=ibb.lVal;

       }

6.       平时取记录集字段值的方法:

   (LPCTSTR)(_bstr_t)rs->GetCollect("datea")

7.       DoModal()可以返回两个结果 IDOK,IDCANCEL,他们都是int型，分别是：1,2。通过EndDialog(IDOK)的方式返回。

8.       一般将数据库连接方面的信息放到app中。则AfxGetApp()非常重要，如；

   CAdo2App* mapp=（CAdo2App*）AfxGetApp();

   Map->conn->Execute(sql,NULL,adCmdText);

9.       DECLARE_DYNCREATE（类名）,IMPLEMENT_DYNCREATE(类名，基类名)  使得由CObject继承来的类在程序运行的时候能够动态的创建。

10.   DECLARE_DYNAMIC（类名）,IMPLEMENT_DYNAMIC(类名，基类名)  可以在运行时获得该类的信息

11.   DECLARE_SERIAL（类名）,IMPLEMENT_SERIAL(类名，基类名,0)为一个可以串行化的CObject派生类产生必要的C++标题代码

12.   获得文档的方法： CMainFrame * pFrame=(CMainFrame *) AfxGetMainWnd();

CPClientDoc * pDoc =(CPClientDoc *) pFrame->GetActiveDocument();
 

13.   获得视图的方法：CMainFrame * pFrame=(CMainFrame *) AfxGetMainWnd();

myView =(CPClientView*) pFrame->GetActiveView();

14.   如果要引用全局变量或者全局方法，须在当前类中引入：extern 名字;

     摘要: 上一篇中我介绍了一种通过封闭Critical Section对象而方便的使用互斥锁的方式，文中所有的例子是两个线程对同一数据一读一写，因此需要让它们在这里互斥，不能同时访问。而在实际情况中可能会有更复杂的情况出现，就是多个线程访问同一数据，一部分是读，一部分是写。我们知道只有读-写或写-写同时进行时可能会出现问题，而读-读则可以同时进行，因为它们不会对数据进行修改，所以也有必要在C++中封装一种方...  阅读全文      摘要: 线程同步是多线程程序设计的核心内容，它的目的是正确处理多线程并发时的各种问题，例如线程的等待、多个线程访问同一数据时的互斥，防死锁等。Win32提供多种内核对象和手段用于线程同步，如互斥量、信号量、事件、临界区等。所不同的是，互斥量、信号量、事件都是Windows的内核对象，当程序对这些对象进行控制时会自动转换到核心态，而临界区本身不是内核对象，它是工作在用户态的。我们知道从用户态转换到核心态是需...  阅读全文

int Strcmp(char *str1, char *str2)
{
   int i=0;
   int b=0;
   while(str1[i]||str2[i])
   {
      if(str1[i]>str2[i])
      {
         b=1;break;
      }
      else if(str1[i]<str2[i])
      {
         b=-1;break;
      }
      i++;
   }
   return b;
}

***************************************************************************************************************
1.说出下面这个程序的运行结果，并简要叙述其理由：

char buf1[10]="hello";
char buf2[10]="hello";
if (buf1==buf2)
printf("equal!");
else printf("not equal!");
因为buf1,buf2分配了不同的内存块，而比较的是数组名，实际上是两个分别指向数组起始元素地址的指针。

2.指出下面这段程序中存在一些什么问题：

int loop,a[5];
int* p=a;
for (loop=0;loop<5;loop++)
{ p++;
*p=loop;
}

数组a[5]在创建时没有初始化， 在for循环里也没有起到完全初始化数组的作用，而且对一块未知内存赋值。在最后一轮循环
结束时p指向了数组a[5]的最后一个元素的下一个地址。

string 系列

char * strcpy( char *strDest, const char *strSrc )
{
　assert( (strDest != NULL) && (strSrc != NULL) );
char *address = strDest;
　while( (*strDest++ = * strSrc++) != ‘\0’ );
return address;
}

char* strncpy(char* strdest, const char* strsrc, int n)
{
   assert((strdest != NULL) && (strsrc != NULL));
   char* address = strdest;
   while(n-- > 0)
      *strdest++ = *strsrc++;
   return address;
}

int strcmp(const char* str1, const char* str2)
{
   assert((str1 != NULL) && (str2 != NULL);
   int ret = 0;
   while (!(ret = (unsigned char*)*str1 - (unsigned char*)*str2) && (*str2))
   {
      str1++;
      str2++;
   }
   if (ret > 0)
      ret = 1;
   else if (ret < 0)
      ret = -1;
   return ret;
}

int strlen(const char* str)
{
   assert(str != NULL);
   int len = 0;
   while ('\0' != *str++)
      len++;
   return len;
}
类string的构造函数
string::string(const char* str)
{
   if(str == NULL)
   {
      m_data = new char[1];
      *m_data = '\0';
    }
    else
    {
       int length = strlen(str);
       m_data = new char[str + 1];
       strcpy(m_data, str);
     }
}

string 的析构函数
string::~string()
{
   delete [] m_data;
}

string 的拷贝构造函数
string ::string(const string& other)
{
   int len = strlen(other.m_data);
   m_data = new char[len + 1];
   strcpy(m_data, other.m_data);
}

string 的赋值函数
string& string::operator=(const string& other)
{
   if (this == &other)
      return *this;
   delete [] m_data;
   int len = strlen(other.m_data);
   m_data = new char[len + 1];
   strcpy(m_data, other.m_data);
   return *this;
}  

不用任何局部和全局变量实现int strlen(char *a)

int strlen(char *a) {
    if('\0' == *a)
        return 0;
    else
        return 1 + strlen(a + 1);
}

1)sizeof相关系列问题
2)const相关系列问题
3)大量林锐书的习题，以及各种变种
这三个几乎是每次必出现
下面的这些是程序相关题,很多都是以前有讨论过的,还请各位大侠能整理个比较适合做面试时答案的解答,多谢了.最好能给出
讨论链接,让我等后辈有学习的机会.
1)求出相似度的算法.
2)写出二分查找的代码.
int binary_search(int* arr, int key, int n)
{
   int low = 0;
   int high = n - 1;
   int mid;
   while (low <= high)
   {
      mid = (high + low) / 2;
      if (arr[mid] > k)
         high = mid - 1;
      else if (arr[mid] < k)
         low = mid + 1;
      else
         return mid;
   }
   return -1;
}
  
3)写出在母串中查找子串出现次数的代码.
*4)写出快速排序或者某种排序算法代码
出现次数相当频繁
5)写出查找从一个集合中输出所有子集合的算法.
*6)实现strcpy函数
char* strcpy(char* dest, const char* src)
{
   assert((dest != NULL) && (src != NULL));
   char* address = dest;
   while ('\0' != (*dest++ = *src++));
   return address;
}
出现次数相当频繁
*7)实现strcmp函数
int mystrcmp(const char* str1, const char* str2)
{
   assert((str1 != NULL) && (str2 != NULL));
   int ret = 0;
   while (!(ret = *(unsigned char*)str1 - *(unsigned char*)str2) && *str2)
   {
      str1++;
      str2++;
   }
   if (ret > 0)
      ret = 1;
   else if (ret < 0)
      ret = -1;
   return ret;
}
  
出现次数相当频繁
8)将一个单链表逆序
struct test
{
   int number;
   double score;
   test* next;
}
void reverse(test*& head)
{
   test* pe = head;
   test* ps = head->next;
   while(ps != NULL)
   {
      pe->next = ps->next;
      ps->next = head;
      head = ps;
      ps = pe->next;
    }
} 
  
     
     
9)循环链表的节点对换和删除。
*10)将一个数字字符串转换为数字."1234" -->1234
＃i nclude<iostream>
using namespace std;

int f(char* s)
{
   int k = 0;
   while (*s)
   {
      k = 10 * k + (*s++)- '0';
     
   }
   return k;
}

int main()
{
   int digit = f("4567");
   cout<<digit<<endl;
   cin.get();
}
出现次数相当频繁
11)实现任意长度的整数相加或者相乘功能。
*12)写函数完成内存的拷贝
一个内存拷贝函数的实现体

void *memcpy(void *pvTo,const void *pvFrom,size_t size)

{

assert((pvTo!=NULL)&&(pvFrom!=NULL));

byte *pbTo=(byte*)pvTo; //防止地址被改变

byte *pbFrom=(byte*)pvFrom;

while (size-- >0)

*pbTo++ = *pbForm++;

return pvTo;

}

出现次数相当频繁

 

.笔试:
1)写一个内存拷贝函数,不用任何库函数.就是前些时候本版讨论的那个问题.
 void* memcpy(void* pvTo, const void* pvFrom, size_t size)
 {
    assert((pvTo != NULL) && (pvFrom != NULL));
    byte* pbTo = pvTo;
    byte* pbFrom = pbFrom;
    while (size-- > 0)
    {
       *pbTo++ = *pbFrom++;
    }
    return pvTo;
 }
2)将一个单链表逆序.(这个问题是个常规的数据结构问题.不过不小心时会损失效率)
3)客房预定的问题.根据客户报的人数,客房等级来从预备的客房中选择出所有符合要求的

客房号.客户没有要求等级时,只考虑人数因素就可以了.要考虑有些客房已经预定的情况.

(写代码是要考虑好彼此的效率)
4)对于一个无序序列进行二分查找
线排序再查找

5)将一个数字字符串转换为数字."1234" -->1234
int convert(char* str)
{
   int k = 0;
   while (*str != '\0')
   {
      k = k * 10 + *s++ - '0';
   }
   return k;
}
6)在文件(调用库函数创建的,不用考虑数据库的方式)中读入信息(包括职工号,职工产量)

.根据输入的信息(包括职工号,职工产量)..检测是否有相同的职工号记录,如有,则增加其

产量.如没有,则创建新的记录.最后的记录排序的依据是职工产量(降序),如果产量相同,则

按职工号(升序). (具体的题目记不太清了,这个题目有点长.哪位也去笔试了.请修正一下

子)
.
2.面试
1)找出两个中文句子的相似度.(例如"中国江苏南京" "江苏省中国南京市".实际上是指的

同一个地方.面试官的要求是一分钟给出求相似度的算法.)(幸好听老师讲过中文分词,要不

然当场就挂了)
2)写出二分查找的代码.
3)将上述代码通用化.(在 C 的规范内.就是我前面所的那个问题)
4)写出在母串中查找子串出现次数的代码.(不顾及效率时好说.当时一不留神把 KMP 说了

出来,结果又让我描述整个过程.汗..只好从头又学了.不过没有冷场,边学边说.hoho)
5)如何看待在函数中定义很多静态变量.
6)写出quick_sort
7)写出查找从一个集合中输出所有子集合的算法.
8)有关于各种类型指针.各种数据类型的 sizeof 运算结果( 在 C 中)