九天雁翎的博客
如果你想在软件业获得成功,就使用你知道的最强大的语言,用它解决你知道的最难的问题,并且等待竞争对手的经理做出自甘平庸的选择。 -- Paul Graham

《Inside C++ Object 》 阅读笔记(1), NRV(Named Return Value)




Inside C++ Object  阅读笔记(1) NRVNamed Return
Value

 

write by 九天雁翎(JTianLing) --
blog.csdn.net/vagrxie

书其实看完了,因为实在公司抽中午吃饭剩余时间看的,所以其实一直没有好好的试验一下,现在将书带到家里好好的一个一个将感兴趣的测试一下了。

 NRVNamed Return Value)是我阅读《Inside C++ Object》碰到的第一个感兴趣的东西,书上面有Lippman的测试数据和侯捷的测试数据。当然,对于VS的效率一直没有报太大希望,但是不至于这个Lippman所说的编译器的义不容辞的优化都不做吧。可能因为侯捷用的VC5.0实在太老了,于是我自己决定测试一下。

 

首先在Linux,我测试了一下。测试代码书上有,我还是贴一下:

#include <stdio.h>

#include <stdlib.h>

#include <memory>

#ifdef _WIN32

#include jtianling.h

#endif

using namespace std;

 

 

class CTest

{

    friend CTest
foo(double);

public:

    CTest()

    {

       memset(array, 0, 100*sizeof(double));

    }

// 以下面的语句决定是否进行NRV

    CTest(const
CTest&t)

    {

       memcpy(this, &t, sizeof(CTest));

    }

 

private:

    double array[100];

};

 

CTest foo(double val)

{

    CTest local;

 

    local.array[0]
= val;

    local.array[99]
= val;

 

    return local;

}

 

 

int main(int argc, char* argv[])

{

#ifdef _WIN32

    double timenow
= jtianling::GetTime();

#endif

    for(int
i=0; i<10000000;
++i)

    {

       CTest t = foo(double(i));

    }

 

 

#ifdef _WIN32

    timenow = jtianling::GetTime()
- timenow;

 

    cout <<timenow;

#endif

    system("pause");

    exit(0);

}

 

因为在linux下我有sheel下的time可以用,所以不需要自己在程序中计时(实际上这还导致linux下的时间会长一些,因为记上了循环外的部分,包括了main的调用等),windows下用我自己的带有gettime的一个库。

效果是很有意思的,在linux下测试得出不进行NRV优化,进行NRV优化(g++ -O1)和进行NRV优化(g++ -O3)时,在我的P3 800的可怜机器上得出的结果是8.61,5.08,4.67

在我的windows下用VS 2005 SP1编译,跑在E2160的机子上,debug时,没有拷贝构造,即理论上不进行NRV优化时的时间是5.07,加上拷贝构造函数,即理论上进行NRV时的时间的确和侯捷一致,时间增加到了5.55.可见起码在关闭优化的时候,VS2005没有进行优化。

开启优化呢?更绝得事情来了,VS2005将整个循环优化掉了-_-!作弊!时间虽然短到-7e,但是我也不承认:)

罪证拷贝如下:

00401038  call       
edi 

0040103A  fild       
qword ptr [esp+30h]

0040103E  fild       
qword ptr
[___@@_PchSym_@00@UnbLwlxfnvmgUerhfzoLhgfwrlLCAAFUkilqvxghUgvhgxifmgrnvUgvhgkrhzhxrrUivovzhvUhgwzucOlyq@+8
(403390h)]

00401044  fdivp      
st(1),st

     for(int i=0;
i<10000000; ++i)

     {

         CTest t =
foo(double(i));

     }

 

     timenow =
jtianling::GetTime() - timenow;

00401046  mov        
edx,dword ptr
[___@@_PchSym_@00@UnbLwlxfnvmgUerhfzoLhgfwrlLCAAFUkilqvxghUgvhgxifmgrnvUgvhgkrhzhxrrUivovzhvUhgwzucOlyq@+8
(403390h)]

0040104C  fstp       
qword ptr [esp+30h]

00401050  or          edx,dword ptr
[___@@_PchSym_@00@UnbLwlxfnvmgUerhfzoLhgfwrlLCAAFUkilqvxghUgvhgxifmgrnvUgvhgkrhzhxrrUivovzhvUhgwzucOlyq@+0Ch
(403394h)]

00401056  jne        
main+67h (401067h)

00401058  push        offset ___@@_PchSym_@00@UnbLwlx

 

会发现循环完全被抛弃掉了,不过虽然影响了测试,但是这个时候我还得承认这是条还算合理的优化,因为在release时,这个循环不能给我们带来任何我们想要的东西。实际上以前就经常碰到这样的问题,MS老是喜欢将它认为无意义的东西直接优化没有,。。。。常常影响测试。。。。。呵呵,今天我是的确想知道,它到底有没有NRV优化,于是,让这个循环有意义吧。

将程序改成如下状态

#include "jtianling.h"

#include <stdio.h>

#include <stdlib.h>

#include <memory>

using namespace std;

 

int gi = 1;

int gj = 1;

 

class CTest

{

    friend CTest
foo(double);

public:

    CTest()

    {

       gj++;

       memset(array, 0, 100*sizeof(double));

    }

 

    //CTest(const CTest&t)

    //{

    //  gj++;

    //  memcpy(this,
&t, sizeof(CTest));

    //}

 

    double array[100];

};

 

CTest foo(double val)

{

    CTest local;

 

    local.array[0]
= val;

    local.array[99]
= val;

 

    return local;

}

 

 

int main(int argc, char* argv[])

{

    double timenow
= jtianling::GetTime();

    for(int
i=0; i<10000000;
++i)

    {

       CTest t = foo(double(i));

       gi = t.array[99];

    }

 

    timenow = jtianling::GetTime()
- timenow;

 

    cout <<timenow <<"/t"
<<gi <<"/t"
<<gj <<endl;

 

    system("pause");

    exit(0);

}

 

分别测试有copy constructor和没有的情况,结果仍然和以前一致,虽然速度很快,但是,有copy constructor的时候速度还是要慢一些,这点很让人不解,更让人不解的是,既然没有开启NRV,那么应该会有1default constructor的调用用来构建临时变量,然后再有一次copy constructor来返回值,但是实际上gj显示default constructorcopy constructor中只有一个被调用了。说明起码是进行了某种优化了。

难道MS用的是另外一个不同于NRV的优化方案?

于是我还是从汇编来看,再怎么优化它逃不过我的眼睛:)

     for(int i=0;
i<10000000; ++i)

00401337  xor        
esi,esi

00401339  fstp       
qword ptr [esp+38h]

0040133D  add        
dword ptr [gj (403024h)],989680h

00401347  mov        
dword ptr [esp+30h],esi

0040134B  jmp        
main+60h (401350h)

0040134D  lea        
ecx,[ecx]

     {

          CTest t = foo(double(i));

00401350  fild       
dword ptr [esp+30h]

         gi =
t.array[99];

00401354  call       
_ftol2_sse (401BE0h)

00401359  add        
esi,1

0040135C  cmp        
esi,989680h

00401362  mov        
dword ptr [gi (403020h)],eax

00401367  mov        
dword ptr [esp+30h],esi

0040136B  jl         
main+60h (401350h)

     }

Have you seen it?红色部分,当我第一次看到989680h的时候,它的值已经是一千万了,说白了就是MS将原来的废循环中的唯一一条不废的语句抽出来,然后在编译期就算好了这条不废语句应该有的值,然后运行时仅仅进行了一条赋值操作。而且绝的是,编译期的这个值的计算是按NRV优化后的流程进行的,即gj1千万。。。。。。优化成这样,我不知道该怎么说了。。。。。根本就不会有任何的构造函数和拷贝构造函数的调用。

然后我将copy constructor注释掉,再次编译运行,最最让人惊讶的事情发生了,汇编代码完全一样。。。。。不是我眼睛不好使,我用BC对比后结果也是一样的。天哪,这还算优化吗?。。。。简直是恶意篡改代码........呵呵,说严重了。问题是。。。最大的问题是,无论我测多少次,一样的汇编代码,在有copy constructor的版本总会慢一些,数量级在0.0001上,我也曾怀疑可能是偶尔的机器性能波动,但是实际多次测试,有copy constructor的版本就是会慢一些,希望有人能给我解答这个问题。

 

 

write by 九天雁翎(JTianLing) --
blog.csdn.net/vagrxie

 

阅读全文....

漫谈C++中的宏

 

 


漫谈C++中的宏

 

--接近你的朋友,更接近你的敌人

write by 九天雁翎(JTianLing) --
blog.csdn.net/vagrxie

 

为什么宏是敌人:

原谅我将C++中的宏称作敌人,自从看到D&EBjarneCpp(这里指C语言预处理)必须被摧毁后,我就一直尽量避免使用宏,为什么我要去使用一个必须被摧毁的东西?(原谅我脑袋中对名词处理不清,不过“预处理”的主要部分可能就是“宏“)

即便我自己尽量不使用宏了,但是宏依旧给我带来了很多的问题。随便举几个例子,最典型的就是windef.h(包含windows.h也会包含这个文件)中的max,min宏,这两个宏会直接导致C++标准库中的numberlimit使用出现问题,这点我以前已经讲过几次了。上次看到X264的代码前几行就是

#undef
max

#undef
min

的时候我是特别感叹。。。真是害人的东西啊。

还有一个例子,MFC自动生成的文件为了调试方便,所有的newdebug版本下都被宏替换成DEBUG_NEW,实际上被替换成了类似new(void *p,const char* filename,
int line)
这样的形式,为的是跟踪每次的内存分配。这也是为什么MFC程序在出现内存泄露的时候你能在VS output中看到一大堆的memory leak。问题是,因为用了宏。。。带了了很大的副作用。我个人new的时候,有的时候喜欢用new(nothrow)的形式,为的是用老的new,然后判断返回的指针是否为空,这样可以避免使用异常处理,不是我不喜欢catch。。。。公司总监说一般不要用,老是容易出问题。另外,就<<inside C++ object>>中说,就算一个程序从来不抛出异常,加上一个catch语句都会有3%~5%的效率损失。。。。这也不算是小损失了。。。

最近我同事做游戏音效管理的时候也碰到了一个很难以理解的问题。那就是明明正确PlaySound函数,总是报没有实现的编译错误。。。。。最后的问题竟然还是宏的问题。windows下经典的用来实现ansi/unicode通用的方式就是用宏大家都知道吧,因为windowsAPI中也有PlaySound函数,所以我同事程序中因为一边包含了windows的东西,一边没有包含,结果就是一边的PlaySound被替换成PlaySoundW了,而调用的PlaySound就不存在了。。。。这样的问题,真的让人吐血。。。。。。。

宏的无类型检测和随意性导致任何一个本来正确的程序都可以变成错误的。这也就是为什么Bjarne认为它必须被毁灭。这也是为什么我要将宏视为敌人。。。。

接近你的朋友:

宏在C中的这么几个作用在C++中有相应的替代品,并且推荐使用。

1.      #define来定义常量

可以用全局的const变量来代替,永远要知道#define是不带类型检查的,而const变量带。虽然宏的使用可能更节省了一个全局变量,但是除非特殊需求,不值得为这样一个全局变量去牺牲安全性。

2.      #define来定义函数并且使函数扩展,减少运行时消耗

可以用inline函数替换,inline函数带参数类型检查,并且不会无端的将你正常的程序变得不正常(参考上面的例子)

3.      #define来实现类型无关的容器

在没有template之前,这是标准的方法,在有template之后。。。这是废弃的方法。

推荐的方法是你的朋友,宏是你的敌人。

 

更接近你的敌人

首先顺面说说其他的预处理:

1.#include用来包含文件,这点的作用至今无法替代,大家用的也都没有什么问题。在Bjarne引入include关键字之前,我们只能用它。

2.#ifdef

#define

#endif

组合用来防止头文件的重复包含,这个使用C++也没有提供替代方案。也是无法替代。(VS中好像#progra once可以)虽然Bjarne说这是很拙劣很低效的方法,但是在我们没有找到更合理的方式前,也就只能这样使用了。

3.#ifdef #elif #else
#endif
来实现条件编译,这是防止头文件重复包含的泛化版本,这在C++中也没有办法替代。为什么MS只能用这种方式来实现一套源码ANSI/Unicode通用?因为没有其他办法。实际上,用一套源码来维护的可移植性代码通篇的#ifdef #elif #else
#endif
那是太正常的事情了。哪怕像因为哦我们公司将debug版本的程序加上_dbg的后缀这样的工程管理方式,都会导致所有希望以CreateProcess方式调用此程序的程序都加上条件编译。常用的用来实现条件编译的宏有_DEBUG,_RELEASE,_WIN32,_WINVER_LINUX等。。。。。。。。。

4.      __LINE__,__FILE__其实好像一般人都用不着,但是这简直就是调试者的福音,因为你可以简单的将malloc,new等宏扩展成new(size,__LINE__,__FILE__)这样的调用形式,再自己实现之,呵呵,其实这也就是MFC内存管理的原理。另外,我做内存管理模块的时候才知道,原来malloc其实就是一个宏定义,-_-!就我所知,可能是因为在C语言时代,没有重载这一说,但是考虑到总会有人想来自己管理内存,所以才出此一招。。。。

下面是重头戏,宏,#define

除了定义常量,函数等基础功能能够被C++中的某些特性替代以外,更多的特性无法替代。#define就是一把达摩克利斯之剑。除了程序代码我不知道该怎么形容#define可以带来的东西:)几乎可以做到do anything you want? 当和条件编译结合使用的时候,你会发现你几乎就是上帝:)

1.)最简单的情况,节省你敲代码的时间:)

很多时候一个深层的调用是这样子的mpObject->moMap.first->SomeFun()

你一个#define mpObject->moMap.first->SomeFun CallSomeFun

以后所有这样的复杂调用就简单多了:)

 

2.)次最简单的情况,替代函数

很多时候人们说不要让重复的代码出现多次,都是告诉你可以将重复的代码做成函数。但是有的时候几个平行的代码,做成函数不方便的时候,宏就更加适合。举个例子:

++SomeLocalA;

++ SomeLocalB;

++ SomeLocalC;

++ SomeLocalD;

++ SomeLocalE;

当类似这样代码重复出现的时候,确定要用函数吗?后果是,函数要定义成

Increment(int
&a,int &b,int &c, int&d, int&e)

形式,调用起来还得

Increment(SomeLocalA,
SomeLocalB, SomeLocalC, SomeLocalD, SomeLocalE);

你认为任务轻松了?。。。。。。。

#define吧。。。。。。

#define INCREMENT
++SomeLocalA;/

++ SomeLocalB;/

++ SomeLocalC;/

++ SomeLocalD;/

++ SomeLocalE;

 

后,在次使用只需要输入INCREMENT就行了,这才叫简化。

 

3.)次次最简单的应用,版本控制和平台无关性控制。

这也算是一种标准的用法了,特别是库用的特别多,一般和条件编译结合使用,很多常见的宏比如_WINVER就是属于版本控制,_WIN32,_LINUX就是属于平台控制。参考预定义介绍3.

 

4.)简单的应用,方便的调试。。。。

某时也可以和#ifdef综合应用,参看预定义介绍4.

还是举例说明吧,比如断言这样最经典的东西大家都知道吧,assert啊。。。程序中往往插入了成百上千的assert,有一天你不想要了怎么办?编译成release版本?晕,调试呢?简单的解决办法是这样

#define
ASSERT assert

然后你平时使用断言的时候全部用ASSERT,某一天你不想使用了,很简单的一句

#define
ASSERT

然后断言全部取消了。

这一点的应用是很广泛的,比如日志系统在程序版本还不是很稳定的时候是很需要的,当程序已经比较稳定的时候还频繁的输出日志,那就会影响程序的效率,那怎么办?你一条一条将原来的日志删除?OK,你很聪明,我用全局替换成空的。。。。。。呵呵,假设你会用正则表达式是可以做到的:)随便说一句,我很喜欢用:)那么有一天程序出问题,又希望加日志呢?又一条一条加?假如会正则表达式的话还是有解决方案,呵呵,将原有的所有日志前面全部加上//,需要的时候再去掉//就行了。方法倒是可行(说实话可行),就是当工程大的时候,消耗的时间啊。。。。。

其实还是用#define最简单

#define
LOG_OUT(xxxxxxx)

用来输出日志,然后某天你不用了

#define
LOG_OUT

就没有了。。。。。

这点还有个特别的好处:)比如你想在所有的日志前面加上个前缀:)

这时你改变你的LOG_OUT宏就可以了,不用全局去改。

加上__FILE__,__LINE__后对于debug和详细日志输出的帮助是无限大的。当同一个函数在不同的情况下被调用的时候,你希望知道是谁调用了这条函数,你能怎么做?直接的办法是,你改变原有的函数,添加进一个行参数两个新的字符串参数,并且定义你扩展的函数。其实可以直接将原有函数用宏替换走:)这也就是上面提到的new的替换方式,可能带来副作用,但是好用至极。这里不举其他例子了,可以参考MFC DEBUG_NEW的宏。

 

4b)这点有个延生用法,那就是当某个新功能你需要添加进原有的程序,但是你需要先测试和保证不影响原有的程序,你将此功能的代码做成一条宏语句是最简单的方法,不仅节省了你copy大量代码的时间,还能在你不需要的时候直接取消此功能。这种用法也是很广泛的,而且特别实用。

这一点的例子可以参看MFC中定义的FIX_SIZE宏,我将它们贴出来,呵呵,想到侯捷可以将所有的源代码都拿出来剖析,我随便贴一点应该不违法吧-_-!

//
DECLARE_FIXED_ALLOC -- used in class definition

#define DECLARE_FIXED_ALLOC(class_name) /

public: /

    void* operator
new(size_t size) /

    { /

       ASSERT(size == s_alloc.GetAllocSize()); /

       UNUSED(size); /

       return s_alloc.Alloc(); /

    } /

    void* operator
new(size_t, void* p) /

       { return p; } /

    void operator
delete(void* p) { s_alloc.Free(p); } /

    void* operator
new(size_t size, LPCSTR, int) /

    { /

       ASSERT(size == s_alloc.GetAllocSize()); /

       UNUSED(size); /

       return s_alloc.Alloc(); /

    } /

protected: /

    static CFixedAlloc
s_alloc /

 

//
IMPLEMENT_FIXED_ALLOC -- used in class implementation file

#define IMPLEMENT_FIXED_ALLOC(class_name, block_size)
/

CFixedAlloc class_name::s_alloc(sizeof(class_name), block_size)
/

 

//
DECLARE_FIXED_ALLOC -- used in class definition

#define DECLARE_FIXED_ALLOC_NOSYNC(class_name) /

public: /

    void* operator
new(size_t size) /

    { /

       ASSERT(size == s_alloc.GetAllocSize()); /

       UNUSED(size); /

       return s_alloc.Alloc(); /

    } /

    void* operator
new(size_t, void* p) /

       { return p; } /

    void operator
delete(void* p) { s_alloc.Free(p); } /

    void* operator
new(size_t size, LPCSTR, int) /

    { /

       ASSERT(size == s_alloc.GetAllocSize()); /

       UNUSED(size); /

       return s_alloc.Alloc(); /

    } /

protected: /

    static CFixedAllocNoSync
s_alloc /

 

//
IMPLEMENT_FIXED_ALLOC_NOSYNC -- used in class implementation file

#define IMPLEMENT_FIXED_ALLOC_NOSYNC(class_nbame, block_size)
/

CFixedAllocNoSync class_name::s_alloc(sizeof(class_name), block_size)
/

 

#else //!_DEBUG

 

#define DECLARE_FIXED_ALLOC(class_name) // nothing
in debug

#define IMPLEMENT_FIXED_ALLOC(class_name, block_size)
// nothing in debug

#define DECLARE_FIXED_ALLOC_NOSYNC(class_name) // nothing
in debug

#define IMPLEMENT_FIXED_ALLOC_NOSYNC(class_name, block_size)
// nothing in debug

 

#endif //!_DEBUG

 

上边的宏定义出自fixalloc.h文件,详细的意义可以到MFC的源代码中去查,这样的话只要在需要FIXALLOC的地方使用DECLARE_FIXED_ALLOCIMPLEMENT_FIXED_ALLOC宏就可以实现功能了,并且可以很方便的控制,比如上边的代码就让宏在relase版本下才有用,在debug版本下放空了。

 

5.次次复杂应用,自动扩展甚于模板的函数。

这时候需要一个很重要的特性“## :)使用宏定义以后的连接功能。比如我做数据校验器的时候用到nInit。。。和nCxxxCheck类,但是名字都是不一样的,做成模板似乎很适合,其实做不到。因为你甚至没有办法来确定哪个类用哪个mbxxxInit来表示已经初始化的问题。但是宏可以。模板往往也不能详细的分辨出每次调用的具体类型并输出日志,宏也可以。

比如,

#define Init(_CHECK) if(mp##_CHECK->Init())/

                  {/

                     mb##_CHECK = true;/

                  }

                  else

                  {/

                     LOG_OUT("Init" <<#_CHECK
<<"failed" <<endl);/

               }

当然,这有个局限,就是你得将命名规范化,还好这不是什么难事。

 

6.次复杂应用,大家都知道的,消息映射。

其实消息映射可以理解为5b的衍生,但是实际上用途更加强大,MFC的消息映射大家都知道吧:)其实消息映射可以应用到很多方面,除了MFC的例子我多说了,在网络包的分派上应用也是很经常的,起码我就常常用,虽然这个时候使用的方法可能应该不能叫消息映射了,叫包分派更加合适。其实更深一步说,在牵涉到一个一个固定入口值,然后分派到不同的函数的过程,假如数量多的话,都可以使用消息映射的模式,这样最节省代码,也可以省下很多虚接口。唯一的一点是,定好命名规则。。。不要打错字。。。

 

7.复杂应用,工厂模式。

虽然C++中可以不用宏实现工厂模式。但是使用的时候用到宏会方便太多。。。。好像举例子比较复杂。。。。可以参考“四人帮”的书Gof23

比如一个CreateClassclassname)的函数,创建并返回一个你指定的类。你会怎么做?

if (classname == “classa”)
return new CClassA else if (classname == “classb”) return new CClassB else
if........................

别的不说,在我们公司的游戏界面库中的类都有40多个。。。。也就是说,你要创建一个Class40..需要比较40多次。。。。。。效率自然低了。这其实是我在公司解决的一个问题。。。。呵呵,做了很久了,当然我不能将公司的源码贴出来给大家看:)不过CEGUI的例子倒是可以:)

基本原理就是先将所有的可能创建的类的都定义一个对应的工厂类,此类中包含一个成员函数new并返回这个类的一个对象。要生成这个类的时候就找到对应的工厂并调用这个生成函数,实际使用的时候利用##的连接特性,自己拼出需要生成类,然后调用。另外类工厂通常做成单件。以下是代码,呵呵,别的就不多说了,源码能说明问题。想详细看的,可以参考CEGUI源代码的CEGUIWindowFactory.h文件,这个用法其实也和6一样,需要命名规范。说了半天,其实做到的效果就是通过一个字符串来动态创建一个对应的类。在CEGUI中,控件几乎都是通过这种方式来创建的,这样再和XML解析配合,可以达到极大的自由度。这里所谓的自由是指可以达到不修改程序,光修改XML的配置文件,就可以实际修改程序(游戏)的效果。呵呵,扯远了。

#define CEGUI_DECLARE_WINDOW_FACTORY(
T )/

class T ## Factory : public WindowFactory/

{/

public:/

    T ##
Factory() : WindowFactory(
T::WidgetTypeName
) {}/

    Window* createWindow(const
String& name)/

    {/

        return new T (d_type, name);/

    }/

    void destroyWindow(Window*
window)/

    {/

        delete window;/

    }/

};/

T ##
Factory& get
## T ## Factory();

 

/*!

/brief

    Generates code for the constructor for the
instance of the window factory generated

    from the class name /a T

*/

//

#define CEGUI_DEFINE_WINDOW_FACTORY(
T )/

T ##
Factory& get
## T ## Factory()/

{/

    static T
## Factory s_factory;/

    return s_factory;/

}

 

 

/*!

/brief

    Helper macro that return the real factory
class name from a given class name /a T

*/

#define CEGUI_WINDOW_FACTORY(
T ) (get ## T ## Factory())

 


write by 九天雁翎(JTianLing) --
blog.csdn.net/vagrxie

 

阅读全文....

个人研究《数据结构与算法分析-C++描述》Vector实现的问题,new与初始化


 个人研究《数据结构与算法分析-C++描述》Vector实现的问题,new与初始化

write by 九天雁翎(JTianLing) --
blog.csdn.net/vagrxie

 

<<Data Structures and Algorithm Analysis in C++>>

--《数据结构与算法分析c++描述》 Mark Allen Weiss 人民邮电大学出版 中文版第61面, 图3-7,3-8,实现的一个列表Vector类。

原实现大概如下:(我可能修改了一些变量的命名以符合我的习惯)


template<typename T>

class Vector

{

public:

    explicit Vector(unsigned auInitSize
= 0)

       : muSize(auInitSize),muCapacity(auInitSize + SPARE_CAPACITY)

    {

       mpObjects = new T[muCapacity];

    }

 

    Vector(const Vector &aoObject):mpObjects(0)

    {

       *this = aoObject;

    }

 

    ~Vector()

    {

       delete[] mpObjects;

    }

 

    const Vector&
operator= (const
Vector &aoObject)

    {

       if(this
== &aoObject)

       {

           return *this;

       }

      

       delete[] mpObjects;

       muSize = aoObject.size();

       muCapacity = aoObject.capacity();

 

       mpObjects = new T[ capacity() ];

 

       for(unsigned
i=0; i!=muSize; ++i)

       {

           mpObjects[i] = aoObject[i];

       }

 

       return *this;

    }

 

    void resize(unsigned auNewSize)

    {

       if ( auNewSize
> muCapacity )

       {

           reserve(auNewSize * 2 + 1);

       }

    }

 

    void reserve(unsigned auNewCapacity)

    {

       if(auNewCapacity
< muSize)

       {

           return;

       }

 

       T *lpOldArray
= mpObjects;

 

       mpObjects = new T[auNewCapacity];

       for(unsigned
i=0; i!=muSize; ++i)

       {

           mpObjects[i] = lpOldArray[i];

       }

      

       muCapacity = auNewCapacity;

 

       delete[] lpOldArray;

    }

 

    T& operator[](unsigned auIndex)

    {

       return mpObjects[auIndex];

    }

 

    const T&
operator[](unsigned
auIndex) const

    {

       return mpObjects[auIndex];

    }

 

    bool empty()
const

    {

       return (muSize == 0);

    }

 

    unsigned size()
const

    {

       return muSize;

    }

 

    unsigned capacity()
const

    {

       return muCapacity;

    }

 

    void push_back(const T& aoObject)

    {

       if(muSize
== muCapacity)

       {

           reserve(2 * muCapacity + 1);

       }

 

       mpObjects[muSize++] = aoObject;

    }

 

    void pop_back()

    {

       muSize--;

    }

 

    const T&
back() const

    {

       return mpObjects[muSize-1];

    }

 

    typedef T*
iterator;

    typedef const
T* const_iterator;

 

    iterator begin()

    {

       return mpObjects;

    }

 

    const_iterator begin() const

    {

       return mpObjects;

    }

 

    iterator end()

    {

       return mpObjects + muSize;

    }

 

    const_iterator end() const

    {

       return mpObjects + muSize;

    }

 

    enum { SPARE_CAPACITY
= 16 };

 

private:

    unsigned muSize;

    unsigned muCapacity;

    T *mpObjects;

};

 

首先的第一个感觉就是new了以后没有初始化,而且放任其未初始化的值的使用。(说的这么复杂,就是说使用了没有初始化的值贝)

但是实际我在Linux下测试的时候发现,g++是会自动将所有new出来的内存初始化的,事实就是如此,这和我在windows下的常识有冲突,所以特意做了一个测试程序来实验。

 

int main( void )

{

    int *lpi
= new int[100];

 

    for(int
i=0; i<100;
++i)

    {

       printf("%d",lpi[i]);

    }

 

    return 0;

}

 

linux下总是会输出全0,哪怕我怀疑碰巧这段内存没有被使用过,将100变成1000也是全0.只能承认,new以后是自动初始化的了。

我甚至怀疑我的常识是否是错误的(虽然我以前为了保证初始化,认为每次new完以后,哪怕马上要全部的使用这些内存都会先用memset置空一下是个好的习惯)

 

事实上,在VS2005的测试中,结果我的常识一样,在debug版本下,windows会自动置为0xcdcdcdcd等值,release时为随机值。

我只能说,以前我一直没有注意到g++编译下自动初始化的事实。

然后我特意看了一下VSlibstdc++vector实现,在resize(size)的时候都是T()作为第二参数调用重载的另一个函数resize(size,val)来实现的,也就是说,C++标准库的这两个实现还是确保reseize初始化了。

ok,也许Mark Allen WeissVectorLinux下可以不出错。。。但是我还是认为这个程序写的有问题,加上初始化吧。。。。。。

自己Mark一下,原来g++编译的new带初始化的?希望有高人能够给我解答,假如不是g++编译的new带初始化那么是什么情况导致了这样的情况,还有,g++有关掉初始化的选项吗?

 write by 九天雁翎(JTianLing) -- www.jtianling.com

 

阅读全文....

一个无聊男人的疯狂《数据结构与算法分析-C++描述》学习笔记 用C++/lua/python/bash的四重实现(7)习题2.8 随机数组的三种生成算法

 

  一个无聊男人的疯狂《数据结构与算法分析-C++描述》学习笔记
C++/lua/python/bash的四重实现(7)习题2.8 随机数组的三种生成算法

write by 九天雁翎(JTianLing) --
blog.csdn.net/vagrxie

 

<<Data Structures and Algorithm Analysis in C++>>

--《数据结构与算法分析c++描述》 Mark Allen Weiss 人民邮电大学出版 中文版第49面, 一随机数组的三种生成算法

这一次没有截图,因为我受不了让bash运行100次的速度,怎么说来着,还是那句话,Bash根本就不适合也不是设计用来描述算法的语言,我根本就是自讨苦吃。用了最多的时间,得到的是最低的效率。。。。。。还有最扭曲的代码。但是因为工作中不用到bash,不常用用还真怕都忘了。。。现在用python的时候就常有这样的感觉,以前看的书就像白看了一样。

相对于bash来说,python的优雅一次一次的深入我心,每一次它都是代码最短的,最最优雅的,很多便捷的语法都是让人用的很痛快,虽然刚开始用的时候由于没有大括号。。。(我用c++习惯了)感觉代码就像悬在空中一样的不可靠。。。呵呵,习惯了以后,怎么看怎么爽。再加上丰富的库,绝了。

 

write by 九天雁翎(JTianLing)
-- www.jtianling.com

以下为实现部分:

CPP:

  1
#include
<stdio.h>
  2 #include
<stdlib.h>
  3 #include
<algorithm>
  4 #include
<iterator>
  5 #include
<iostream>
  6 using namespace std;
  7
  8 int randInt(int i, int j)
  9 {
 10     if(i > j)
 11     {
 12         int temp = i;
 13         i
= j;
 14         j
= temp;
 15     }
 16
 17     return rand() % (j-i) + i;
 18 }
 19
 20 void randArr1(int arr[], int n)
 21 {
 22     for(int i=0; i<n; ++i)
 23     {
 24         while(true)
 25         {
 26             // some thing don't like py
 27             // because my randInt is create number
 28             // in [0,n) and py is [0,n]
 29             int temp = randInt(0, n);
 30             int j = 0;
 31             while(j < i)
 32             {
 33                 if(arr[j] == temp)
 34                 {
 35                     break;
 36                 }
 37                 ++j;
 38             }
 39             if(j == i)
 40             {
 41                 arr[j]
= temp;
 42                 break;
 43             }
 44         }
 45     }
 46 }
 47
 48 void randArr2(int a[], int n)
 49 {
 50     bool *lpb = new bool[n];
 51     memset(lpb,
0, n);
 52
 53     for(int i=0; i<n; ++i)
 54     {
 55         while(true)
 56         {
 57             int temp = randInt(0, n);
 58             if(!lpb[temp])
 59             {
 60                 a[i]
= temp;
 61                 lpb[temp]
= true;
 62                 break;
 63             }
 64         }
 65
 66     }
 67
 68     delete lpb;
 69     lpb = NULL;
 70 }
 71
 72 void swap(int& a, int&
b)
 73 {
 74     int temp = a;
 75     a = b;
 76     b = temp;
 77 }
 78
 79 // just
for fun,but I like it.

 80 // when py
could have range and bash could have seq

 81 // why cpp
couldn't have a seq like this? lol

 82 template<typename T>
 83 class CFBSeq
 84 {
 85 public:
 86     CFBSeq(const T& aValue) : mValue(aValue) {
}
 87
 88     T operator()()
 89     {
 90         return mValue++;
 91     }
 92
 93 private:
 94     T mValue;
 95 };
 96
 97 void randArr3(int a[], int n)
 98 {
 99     generate(a,
a+n, CFBSeq<int>(0));
100
101     for(int i=1; i<n; ++i)
102     {
103         swap(a[i],
a[randInt(0,i)]);
104     }
105
106 }
107
108
109
110
111
112 int main(int argc, char*
argv[])
113 {
114     const int TIMES=100;
115     srand(time(NULL));
116     int a[TIMES],b[TIMES],c[TIMES];
117     randArr1(a,TIMES);
118     copy(a, a+TIMES,
ostream_iterator<int>(cout," "));
119     printf("/n");
120     randArr2(b,TIMES);
121     copy(b, b+TIMES,
ostream_iterator<int>(cout," "));
122     printf("/n");
123     randArr3(c,
TIMES);
124     copy(c, c+TIMES,
ostream_iterator<int>(cout," "));
125
126
127
128     exit(0);
129 }
130

LUA:

 1
#!/usr/bin/env
lua

 2
 3 math.randomseed(os.time())
 4
 5 function randArr1(a,
n)
 6     for i=1,n
do
 7         while true do
 8             local temp = math.random(1, n)
 9
10             local j = 1
11             while j < i do
12                 if a[j] == temp then 
13                     break
14                 end
15                 -- Again damed that There is no ++
16                 -- and even no composite operator += !
17                 -- No one knows that is more concision
18                 -- and more effective?
19                 j
= j + 1
20             end
21
22             if j == i then
23                 a[i]
= temp
24                 break
25             end
26
27         end
28     end
29 end
30
31
32 function randArr2(a,
n)
33     -- use nil as false as a lua's special hack
34     local bt = {}
35     for i=1,n
do
36         while true do
37             local temp = math.random(1,n)
38             if not bt[temp]
then
39                 a[i]
= temp
40                 bt[temp]
= true
41                 break
42             end
43         end
44     end
45 end
46
47 function randArr3(a,
n)
48     for i=1,n
do
49         a[i]
= i
50     end
51     
52     for i=1,n
do
53         local temp = math.random(1,n)
54         -- one of the most things i like in lua&py
55         a[i],a[temp]
= a[temp],a[i]
56     end
57 end
58
59
60
61 -- Test Code
62
63 times = 100
64 t = {}
65 randArr1(t, times)
66 for i,v in ipairs(t)
do
67     io.write(v .. "
"
)
68 end
69
70
71 t2 = {}
72 randArr2(t2, times)
73 for i,v in ipairs(t2)
do
74     io.write(v .. "
"
)
75 end
76
77
78 t3 = {}
79 randArr3(t3, times)
80 for i,v in ipairs(t3)
do
81     io.write(v .. "
"
)
82 end
83
84
85

PYTHON:

 1
#!/usr/bin/env
python

 2 from random
import randint
 3
 4 def randArr1(a,n):
 5     for i in range(n):
 6         while True:
 7             temp
= randint(0, n-1)
 8
 9             for j in range(i):
10                 if a[j] == temp:
11                     break;
12             # another one of the things I like in py(for else)
13             else:
14                 a.append(temp)
15                 break;
16
17 def randArr2(a,n):
18 #surely it is
not need be a dict but dict is faster then list

19     bd = {}
20     for i in range(n):
21         while True:
22             temp
= randint(0, n-1)
23             if temp not in tl:
24                 a.append(temp)
25                 tl[temp]
= True
26                 break
27
28 def randArr3(a,n):
29      a = range(n)
30      for i in range(n):
31         
temp = randint(0, n-1)
32         
# like in lua
33         
a[i],a[temp] = a[temp],a[i]
34
35 def test():
36     times = 100
37     l = []
38     randArr1(l,
times)
39
40     print l
41     l2 = []
42     randArr1(l2,
times)
43     print l2
44
45     l2 = []
46     randArr1(l2,
times)
47     print l2
48
49
50
51 if __name__ == '__main__':
52     test()

BASH:

  1
#!/usr/bin/env
bash

  2
  3
  4 #
just for a range rand....let me die....

  5 #
what I had said? bash is not a good

  6 #
language for describing algorithms

  7 randInt()
  8 {
  9     local a=$1
 10     local b=$2
 11
 12     if (( a
> b ))
 13     then
 14         local temp
 15         (( temp = a ))
 16         (( a = b ))
 17         (( b = temp ))
 18     fi
 19
 20     local mi
 21     (( mi = b
- a + 1))
 22     local r=$((RANDOM%${mi}+${a}))
 23     echo -n $r
 24 }
 25
 26 randArr1()
 27 {
 28 # only one
argument because I hate the

 29 # bash's
indirect reference

 30 # you can
reference the (4) binarySearch to

 31 # see what
I said

 32     local n=$1
 33     declare -a a
 34     for (( i=1; i<=n; ++i )) 
 35     do
 36         while true
 37         do
 38             temp=`randInt 1 $n`
 39             j=1
 40             while (( j<i ))
 41             do
 42                 if (( a[j] == temp ))
 43                 then
 44                     break
 45                 fi
 46                 (( ++j ))
 47             done
 48             if (( j
== i ))
 49             then
 50                 (( a[j] = temp ))
 51                 break
 52             fi
 53         done
 54     done
 55
 56     echo ${a[*]}
 57 }
 58
 59 randArr2()
 60 {
 61     local n=$1
 62     declare -a a
 63     # used for bool array
 64     declare -a b
 65     for (( i=1; i<=n; ++i ))
 66     do
 67         while true
 68         do
 69             local temp=`randInt 1 $n`
 70             if [ -z ${b[temp]} ]
 71             then
 72                 (( a[i] = temp ))
 73                 (( b[temp] = true ))
 74                 break
 75             fi
 76         done
 77     done
 78
 79     echo ${a[*]}
 80 }
 81
 82 randArr3()
 83 {
 84     local n=$1
 85     for (( i=1; i<=n; ++i ))
 86     do
 87         (( a[i] = i
))
 88     done
 89     for (( i=1; i<=n; ++i ))
 90     do
 91         local temp=`randInt 1 $n`
 92         (( t = a[i] ))
 93         (( a[i] = a[temp] ))
 94         (( a[temp] = t
))
 95     done
 96
 97     echo ${a[*]}
 98 }
 99
100
101 # so slow that
I can't bear it run 100 times

102 randArr1 10
103 randArr2 10
104 randArr3 10
105

 

 

 

write by 九天雁翎(JTianLing) -- www.jtianling.com

 

阅读全文....

一个无聊男人的疯狂《数据结构与算法分析-C++描述》学习笔记 习题2.8 随机数组的三种生成算法(补) 将bash的实现翻译成比较纯正的bash风格


  一个无聊男人的疯狂《数据结构与算法分析-C++描述》学习笔记
7)习题2.8 随机数组的三种生成算法补 将bash的实现翻译成比较纯正的bash风格

write by 九天雁翎(JTianLing) --
blog.csdn.net/vagrxie

 

<<Data Structures and Algorithm Analysis in C++>>

--《数据结构与算法分析c++描述》 Mark Allen Weiss 人民邮电大学出版 中文版第49面, 一随机数组的三种生成算法

由于偷懒我最近老是喜欢用bashC语言(其实好像是csh)中引进的语法,所以感觉都不是那么纯粹的bash风格(但是其实bash的风格我本来就不 喜欢),老是学了不用,有一天写bash都当C语言在写就完了。今天加班比较晚,就不搞什么新内容了,将2.8bash实现翻译成了比较纯粹的bash 风格。。。。对于没有接触过Bash的人来说更加接近天书了,enjoy it......(I hope you can)

 1 #!/usr/bin/env bash
 2
 3 # just for
a range rand....let me die....

 
4 # what I had said? bash is not a
good

 5 # language
for describing algorithms

 6 randInt()
 7 {
 8     local a=$1
 9     local b=$2
10
11     if [ "$a" -gt "$b" ]
12     then
13         local temp=$a
14         a=$b
15         b=$temp
16     fi
17
18     local mi=$(($b-$a+1))
19     local r=$((RANDOM%${mi}+${a}))
20     echo -n $r
21 }
22
23 randArr1()
24 {
25 # only one
argument because I hate the

26 # bash's
indirect reference

27 # you can
reference the (4) binarySearch to

28 # see what I
said

29     local n=$1
30     for i in `seq $n`
31     do
32         while true
33         do
34             temp=`randInt 1 $n`
35             j=1
36             while [ "$j" -lt "$i" ]
37             do
38                 if [ ${a[j]} -eq "$temp" ]
39                 then
40                     break
41                 fi
42                 j=$(($j+1))
43             done
44             if [ "$j" -eq "$i" ]
45             then
46                 a[j]=$temp
47                 break
48             fi
49         done
50     done
51
52     echo ${a[*]}
53 }
54
55 randArr2()
56 {
57     local n=$1
58     # used for bool array
59     for i in `seq $n`
60     do
61         while true
62         do
63             local temp=`randInt 1 $n`
64             if [ -z ${b[temp]} ]
65             then
66                 a[i]=$temp
67                 b[temp]=true
68                 break
69             fi
70         done
71     done
72
73     echo ${a[*]}
74 }
75
76 randArr3()
77 {
78     local n=$1
79     for i in `seq $n`
80     do
81         a[i]=$i
82     done
83     for i in `seq $n`
84     do
85         local temp=`randInt 1 $n`
86         t=${a[i]}
87         a[i]=${a[temp]}
88         a[temp]=$t
89     done
90
91     echo ${a[*]}
92 }
93
94 # so slow that I
can't bear it run 100 times

95 randArr1 10
96 randArr2 10
97 randArr3 10
98

 

 

write by 九天雁翎(JTianLing) -- www.jtianling.com

 

阅读全文....

一个无聊男人的疯狂《数据结构与算法分析-C++描述》学习笔记 用C++/lua/python/bash的四重实现(6)高效率的幂运算


  一个无聊男人的疯狂《数据结构与算法分析-C++描述》学习笔记
C++/lua/python/bash的四重实现(6)高效率的幂运算

write by 九天雁翎(JTianLing) --
blog.csdn.net/vagrxie

 

<<Data Structures and Algorithm Analysis in C++>>

--《数据结构与算法分析c++描述》 Mark Allen Weiss 人民邮电大学出版 中文版第46面,图2-11
一个高效率的幂运算,应该还算不上最高效率的,但是作为一个递归及O(logn)的例子还是很合适的,因为足够的简单。

bash的实现我发现老是用普通程序语言的思想是不行了,麻烦的要死,于是用命令替换实现了一个b版本,明显效果好的多:)用一个语言就是要用一个语言的特性。

来个截图,惯例。我好像喜欢上了这种一下排45个窗口然后照相的方式,呵呵,特有成就感。

从左自右依次是cpp,lua,python,bash,bashb实现)。

write by 九天雁翎(JTianLing)
-- www.jtianling.com

以下为实现部分:

CPP:

 1
#include
<stdio.h>
 2 #include
<stdlib.h>
 3 #include
<math.h>
 4
 5 bool IsEven(int x)
 6 {
 7     return (x % 2 ==
0);
 8 }
 9
10
11 long MyPow(long x, int n)
12 {
13     if( 0 ==
n)
14         return 1;
15     if ( IsEven(n))
16         return MyPow( x * x, n / 2);
17     else
18         return MyPow( x * x, n / 2 ) * x;
19 }
20
21 int main(int argc, char*
argv[])
22 {
23     printf("pow(2,2)=%ld/n",MyPow(2,2));
24     printf("pow(2,3)=%ld/n",MyPow(2,3));
25     printf("pow(2,4)=%ld/n",MyPow(2,4));
26     printf("pow(2,5)=%ld/n",MyPow(2,5));
27     printf("pow(2,6)=%ld/n",MyPow(2,6));
28
29     exit(0);
30 }
31

LUA:

 1
#!/usr/bin/env
lua

 2
 3
 4 function isEven(n)
 5     return n % 2 ==
0
 6 end
 7
 8 function pow(m,
n)
 9     if n == 0 then
10         return 1
11     end
12
13     if isEven(n) then
14         return pow( m * m, n / 2)
15     else
16         return pow( m * m, math.floor(n / 2)
) * m
17     end
18 end
19
20
21 -- Test Code
22 print("pow(2,2)=" .. pow(2,2));
23 print("pow(2,3)=" .. pow(2,3));
24 print("pow(2,4)=" .. pow(2,4));
25 print("pow(2,5)=" .. pow(2,5));
26 print("pow(2,6)=" .. pow(2,6));
27
28

PYTHON:

 1
#!/usr/bin/env
python

 2
 3 def IsEven(n):
 4     return n % 2 == 0
 5
 6 def MyPow(m,n):
 7     if n == 0:
 8         return 1
 9
10     if IsEven(n):
11         return MyPow(m * m, n / 2)
12     else:
13         return MyPow(m * m, n // 2) * m
14
15
16 def test():
17     print "pow(2,2)=" +
str(
MyPow(2,2))
18     print "pow(2,3)=" +
str(
MyPow(2,3))
19     print "pow(2,4)=" +
str(
MyPow(2,4))
20     print "pow(2,5)=" +
str(
MyPow(2,5))
21     print "pow(2,6)=" +
str(
MyPow(2,6))
22
23 if __name__ == '__main__':
24     test()
25

BASH:

 1
#!/usr/bin/env
bash

 2
 3 isEven()
 4 {
 5     local m=$1
 6     if (( m
% 2 == 0))
 7     then
 8         return 1
 9     else
10         return 0
11     fi
12 }
13
14 pow()
15 {
16     local m=$1
17     local n=$2
18
19     if (( n
== 0 ))
20     then
21         return 1
22     fi
23
24     local m2
25     local n2
26     (( m2 = m
* m ))
27     (( n2 = n
/ 2 ))
28
29     isEven n
30     r=$?
31     if (( r
== 1 ))
32     then
33         pow
$m2 $n2 
34         return $?
35     else
36         pow
$m2 $n2 
37         local r2=$?
38         (( r2 *= m ))
39         return $r2
40     fi
41 }
42     
43 echo -n
"pow(2,2)="
44 pow 2 2
45 echo $?
46 echo -n
"pow(2,3)="
47 pow 2 3
48 echo $?
49 echo -n
"pow(2,4)="
50 pow 2 4
51 echo $?
52 echo -n
"pow(2,5)="
53 pow 2 5
54 echo $?
55 echo -n
"pow(2,6)="
56 pow 2 6
57 echo $?

 

 

BASH(b实现):

 1 #!/usr/bin/env bash
 2
 3 isEven()
 4 {
 5     local m=$1
 6     if (( m
% 2 == 0))
 7     then
 8         echo 1
 9     else
10         echo 0
11     fi
12 }
13
14 pow()
15 {
16     local m=$1
17     local n=$2
18
19     if (( n
== 0 ))
20     then
21         echo 1
22         exit 0
23     fi
24
25     local m2
26     local n2
27     (( m2 = m
* m ))
28     (( n2 = n
/ 2 ))
29
30     r=`isEven $n`
31     if (( r
== 1 ))
32     then
33         local r1=`pow $m2 $n2`
34         echo $r1
35     else
36         local r2=`pow $m2 $n2`
37         (( r2 *= m ))
38         echo $r2
39     fi
40 }
41     
42 echo -n
"pow
2 2 =
"
43 pow 2 2
44 echo -n
"pow
2 3 =
"
45 pow 2 3
46 echo -n
"pow
2 4 =
"
47 pow 2 4
48 echo -n
"pow
2 5 =
"
49 pow 2 5
50 echo -n
"pow
2 6 =
"
51 pow 2 6

 

 

 

 

 

write by 九天雁翎(JTianLing) -- www.jtianling.com

 

阅读全文....

一个无聊男人的疯狂《数据结构与算法分析-C++描述》学习笔记 用C++/lua/python/bash的四重实现(5)欧几里得算法欧几里得算法求最大公约数


  一个无聊男人的疯狂《数据结构与算法分析-C++描述》学习笔记
C++/lua/python/bash的四重实现(5)欧几里得算法求最大公约数

write by 九天雁翎(JTianLing) --
blog.csdn.net/vagrxie

 

<<Data Structures and Algorithm Analysis in C++>>

--《数据结构与算法分析c++描述》 Mark Allen Weiss 人民邮电大学出版 中文版第45面,图2-10欧几里得算法

欧几里得算法求最大公约数好像也比较出名,起码各大算法书籍都喜欢用,可能因为说明简单,却能够说明问题。

这里突然想说一句,当bash老是用C语法部分来完成也就没有那么难的变态了,只是,可能多了一点投机的成分。

再来个截图,下次再截就成惯例了。

从左自右依次是cpp,lua,python,bash


write by 九天雁翎(JTianLing)
-- www.jtianling.com

以下为实现部分:

CPP:

 1
#include
<stdio.h>
 2 #include
<stdlib.h>
 3
 4 long gcd(long m, long n)
 5 {
 6     if(m < n)
 7     {
 8         long temp = m;
 9         m
= n;
10         n
= temp;
11     }
12     while( n != 0)
13     {
14         long rem = m % n;
15         m
= n;
16         n
= rem;
17     }
18     
19     return m;
20 }
21
22 int main(int argc, char*
argv[])
23 {
24     printf("gcd(1989,1590)=%ld/n",gcd(1989,1590));
25     printf("gcd(1590,1989)=%ld/n",gcd(1590,1989));
26     exit(0);
27 }
28

LUA:

 1
#!/usr/bin/env
lua

 2
 3
 4 function gcd(m,n)
 5     if m < n then
 6         m,n
= n,m
 7     end
 8
 9     while n ~= 0 do
10         rem
= m % n
11         m
= n
12         n
= rem
13     end
14
15     return m
16 end
17
18 -- Test code
19 print("gcd(1989,1590)=" .. gcd(1989,1590))
20 print("gcd(1590,1989)=" .. gcd(1590,1989))
21

PYTHON:

 1
#!/usr/bin/env
python

 2
 3
 4 def gcd(m,n):
 5     if m < n:
 6         m,n
= n,m
 7     
 8     while n != 0:
 9         rem
= m % n
10         m
= n
11         n
= rem
12
13     return m
14
15 def test():
16     print "gcd(1989,1590)=" +
str(gcd(1989,1590))
17     print "gcd(1590,1989)=" +
str(gcd(1590,1989))
18
19 if __name__ == '__main__':
20     test()
21

BASH:

 1
#!/usr/bin/env
bash

 2
 3
 4 gcd()
 5 {
 6     m=$1
 7     n=$2
 8     if (( m
< n ))
 9     then
10         (( temp = m ))
11         (( m = n ))
12         (( n = temp ))
13     fi
14
15     while (( n
!= 0 ))
16     do
17         (( rem = m
% n ))
18         (( m = n
))
19         (( n = rem
))
20     done
21
22     return $m
23 }
24
25
26 # test code
27 echo -n
"gcd(1989,1590)="
28 gcd 1989 1590
29 echo $?
30 echo -n
"gcd(1590,1989)="
31 gcd 1590 1989
32 echo $?
33
34
35

write by 九天雁翎(JTianLing) -- www.jtianling.com

 

阅读全文....

一个无聊男人的疯狂《数据结构与算法分析-C++描述》学习笔记 用C++/lua/python/bash的四重实现(4)二分搜索算法


一个无聊男人的疯狂《数据结构与算法分析-C++描述》学习笔记 用C++/lua/python/bash的四重实现4)二分搜索算法

write by 九天雁翎(JTianLing) --
blog.csdn.net/vagrxie

 

<<Data Structures and Algorithm Analysis in C++>>

--《数据结构与算法分析c++描述》 Mark Allen Weiss 人民邮电大学出版 中文版第44面,图2-9二分搜索算法

二分搜索是很著名也很实用的算法,在排序中查找的速度从算法分析角度来说已经是最快的了。O(logN)

这里费了点心,将bash都实现了,扭曲啊,扭曲,光是传递一个数组参数都折腾了半天,最后还是通过所谓的间接引用然后用for重新赋值才实现我想要的数组,再次认为bash的算法描述语法混乱不堪。。。。其实bash只有命令调用的语法好用而已(个人见解),但是碰到我这样无聊的人,偏偏要用bash去实现算法。。。那就只能稍微偷点懒了,用了bashC语言语法部分。

以下4个算法都是一样的,测试时为了统一结果,消除因为cpp,python数组从0开始,lua,bash数组从1开始的问题,测试时,cpp,python-1开始测试。最后测试完成的结果完全一致,来个有意思的截图:

我编码的时候平铺4putty窗口,正好占满我的19寸屏:)

从左自右依次是cpp,lua,python,bash

以下是源代码:

CPP:

 1
#include
<stdio.h>
 2 #include
<stdlib.h>
 3 #include
<vector>
 4 #include
<iostream>
 5 using namespace std;
 6 template<typename T>
 7 int binarySearch(const vector<T> &a, const T &x, int& aiTimes)
 8 {
 9     int low = 0;
10     int high = a.size() - 1;
11
12     while(low <= high)
13     {
14         ++aiTimes;
15         int mid = (low + high) / 2;
16         
17         if(a[mid] < x)
18         {
19             low
= mid + 1;
20         }
21         else if(a[mid]
> x)
22         {
23             high
= mid - 1;
24         }
25         else
26         {
27             return mid;
28         }
29     }
30
31     return -1;
32 }
33
34 int main(int argc, char*
argv[])
35 {
36     vector<int> lveci;
37     lveci.resize(100);
38     for(int i
= 0; i < 100;
++i)
39     {
40         lveci[i]
= i;
41     }
42
43     int liTimes = 0;
44     cout <<
binarySearch(lveci, -1, liTimes);
45     cout <<"/tcost:" <<liTimes <<endl;
46     liTimes = 0;
47     cout << binarySearch(lveci,
0, liTimes);
48     cout <<"/tcost:" <<liTimes <<endl;
49     liTimes = 0;
50     cout <<
binarySearch(lveci, 1, liTimes);
51     cout <<"/tcost:" <<liTimes <<endl;
52     liTimes = 0;
53     cout <<
binarySearch(lveci, 2, liTimes);
54     cout <<"/tcost:" <<liTimes <<endl;
55     liTimes = 0;
56     cout <<
binarySearch(lveci, 100, liTimes);
57     cout <<"/tcost:"<<liTimes <<endl;
58
59
60
61     exit(0);
62 }
63

LUA:

 1
#!/usr/bin/env
lua

 2 function binarySearch(a,
v)
 3     low = 1
 4     high = #a
 5
 6     times = 0
 7     while(low <= high) do
 8         times
= times + 1
 9         mid
= math.floor(( low + high) / 2)
10         if a[mid] < v  then
11             low
= mid + 1
12         elseif a[mid] > v then
13             high
= mid - 1
14         else
15             return mid,times
16         end
17     end
18
19     return -1,times
20 end
21
22 -- test code
23 array = {}
24 for i=1,100 do
25     array[i] = i
26 end
27
28 print(binarySearch(array,
0))
29 print(binarySearch(array,
1))
30 print(binarySearch(array,
2))
31 print(binarySearch(array,
3))
32 print(binarySearch(array,
101))
33

PYTHON:

 1
#!/usr/bin/env
python

 2
 3 def binarySearch(a, v):
 4     low = 0
 5     high =
len(a) - 1
 6     times = 0
 7
 8     while low <= high:
 9         times
+= 1
10         mid
= (low + high) // 2
11
12         if v > a[mid]:
13             low
= mid + 1
14         elif v < a[mid]:
15             high
= mid - 1
16         else:
17             return mid,times
18     
19     return -1,times
20
21 array = range(100)
22 print binarySearch(array, -1)
23 print binarySearch(array, 0)
24 print binarySearch(array, 1)
25 print binarySearch(array, 2)
26 print binarySearch(array,
100)
27     
28

BASH:

 1
#!/usr/bin/env
bash

 2
 3
 4 binarySearch()
 5 {
 6     v=$2
 7     an="$1[@]"
 8     a=${!an}
 9     for i in $a
10     do
11         ar[i]=$i
12     done
13     low=1
14     high=${#ar[*]}
15     (( times=0 ))
16
17     while (( low
<= high ))
18     do
19         (( ++times ))
20         (( mid=(low+high)/2 ))
21         #echo -n " mid="$mid
22         #echo -n " ar[mid]="${ar[mid]}
23         if (( v
> ar[mid] ))
24         then
25             (( low = mid + 1 ))
26         elif (( v
< ar[mid] ))
27         then
28             (( high = mid - 1 ))
29         else
30             #echo -e "/nTimes="$times
31             return $mid
32         fi
33     done
34
35     #echo -e "/nTimes="$times
36     return -1
37 }
38
39 for ((i=1; i<= 100; ++i))
40 do
41     (( array[i] = i
))
42 done
43
44 binarySearch array 0
45 echo -e
"$?/t$times"
46 binarySearch array 1
47 echo -e
"$?/t$times"
48 binarySearch array 2
49 echo -e
"$?/t$times"
50 binarySearch array 3
51 echo -e
"$?/t$times"
52 binarySearch array 101
53 echo -e
"$?/t$times"
54
55 exit 0

 

write by 九天雁翎(JTianLing) -- www.jtianling.com

 

阅读全文....

一个无聊男人的疯狂《数据结构与算法分析-C++描述》学习笔记 用C++/lua/python/bash的四重实现(3) 最大子序列和问题

 

 一个无聊男人的疯狂《数据结构与算法分析-C++描述》学习笔记 用C++/lua/python/bash的四重实现(3
最大子序列和问题

write by 九天雁翎(JTianLing) --
blog.csdn.net/vagrxie

 

<<Data Structures and Algorithm Analysis in C++>>

--《数据结构与算法分析c++描述》 Mark Allen Weiss 人民邮电大学出版 中文版第39-43面,图2-52-6,2-7,2-8最大子序列和问题的解

总算有点技术含量了,呵呵,虽然说重复实现一下代码不难(不就是相当于翻译嘛),但是算法4为什么是正确的需要好好理解一下。

以下为实现部分:

CPP:

  1
//
  2 //
Maximum contiguous subsequence sum algorithm 1 - 4, worst to best

  3 //
From <<Data Structures and Algorithm Analysis in C++>> by Mark
Allen Weiss

  4 //
  5 //
  6 #include
<stdio.h>
  7 #include
<stdlib.h>
  8 #include
<vector>
  9 using namespace std;
 10
 11
 12
 13 int maxSubSum1(
const vector<int> &a)
 14 {
 15     int maxSum = 0;
 16
 17     for(int i=0; i<(int)a.size();
++i)
 18         for(int j=i;
j<(int)a.size(); ++j)
 19         {
 20             int thisSum = 0;
 21
 22             for(int k=i;
k<=j; ++k)
 23                 thisSum
+= a[k];
 24
 25             if(thisSum > maxSum)
 26                 maxSum
= thisSum;
 27         }
 28     return maxSum;
 29 }
 30
 31 int maxSubSum2(
const vector<int> &a)
 32 {
 33     int maxSum = 0;
 34
 35     for(int i=0; i<(int)a.size();
++i)
 36     {
 37         int thisSum = 0;
 38         for(int j=i;
j<(int)a.size(); ++j)
 39         {
 40             thisSum
+= a[j];
 41
 42             if( thisSum > maxSum)
 43                 maxSum
= thisSum;
 44         }
 45     }
 46     return maxSum;
 47 }
 48
 49 int max3(int a, int b,
int c)
 50 {
 51     return ((a < b)?((b < c)?c:b):((a
< c)?c:a));
 52 }
 53
 54
 55 int maxSumRec(
const vector<int> &a, int left,
int right)
 56 {
 57     if(left == right)
 58         if( a[left] > 0)
 59             return a[left];
 60         else
 61             return 0;
 62
 63     int center = (left + right) / 2;
 64     int maxLeftSum = maxSumRec(a, left,
center);
 65     int maxRightSum = maxSumRec(a, center + 1, right);
 66
 67     int maxLeftBorderSum = 0;
 68     int leftBorderSum = 0;
 69
 70     for(int i=center;
i >=left; --i)
 71     {
 72         leftBorderSum
+= a[i];
 73         if(leftBorderSum > maxLeftBorderSum)
 74             maxLeftBorderSum
= leftBorderSum;
 75     }
 76
 77     int maxRightBorderSum = 0,rightBorderSum = 0;
 78     for(int j
= center + 1; j <= right; ++j)
 79     {
 80         rightBorderSum
+= a[j];
 81         if(rightBorderSum > maxRightBorderSum)
 82             maxRightBorderSum
= rightBorderSum;
 83     }
 84
 85     
 86     return max3(maxLeftSum, maxRightSum,
maxLeftBorderSum + maxRightBorderSum);
 87 }
 88
 89 int maxSubSum3(const vector<int> &a)
 90 {
 91     return maxSumRec(a, 0, a.size() - 1);
 92 }
 93
 94 int maxSubSum4(
const vector<int> &a)
 95 {
 96     int maxSum = 0,
thisSum = 0;
 97
 98     for( int j
= 0; j< (int)a.size();
++j)
 99     {
100         thisSum
+= a[j];
101
102         if(thisSum > maxSum)
103             maxSum
= thisSum;
104         else if(thisSum
< 0)
105             thisSum

= 0;
106     }
107
108     return maxSum;
109 }
110
111
112
113 int main(int argc, char*
argv[])
114 {
115     // for easy
116     int a[] = { -2,
11, -4, 13, -5, -2};
117     vector<int> lvec(a, a + sizeof(a)/sizeof(int));
118
119     printf("maxSubSum1(lvec)):%d/n",maxSubSum1(lvec));
120     printf("maxSubSum2(lvec)):%d/n",maxSubSum2(lvec));
121     printf("maxSubSum3(lvec)):%d/n",maxSubSum3(lvec));
122     printf("maxSubSum4(lvec)):%d/n",maxSubSum4(lvec));
123
124
125     exit(0);
126 }
127

LUA:

  1
#!/usr/bin/env
lua

  2
  3
  4 function maxSubSum1(a)
  5     assert(type(a) == "table", "Argument
a must be a number array."
)
  6
  7     local maxSum = 0
  8
  9     for i=1,#a
do
 10         for j=i,#a    do
 11             local thisSum = 0
 12             for k=i,j do
 13                 thisSum
= thisSum + a[k]
 14             end
 15
 16             if thisSum > maxSum then
 17                 maxSum
= thisSum
 18             end
 19         end
 20     end
 21
 22     return maxSum
 23 end
 24
 25 function maxSubSum2(a)
 26     assert(type(a) == "table", "Argument
a must be a number array."
)
 27
 28     local maxSum = 0
 29
 30     for i=1,#a
do
 31         local thisSum = 0
 32
 33         for j=i,#a do
 34             thisSum
= thisSum + a[j]
 35
 36             if(thisSum > maxSum) then
 37                 maxSum
= thisSum
 38             end
 39         end
 40     end
 41     return maxSum
 42 end
 43
 44 function max3(n1,
n2, n3)
 45     return (n1 > n2 and ((n1 > n3) and n1 or n3)
or ((n2 > n3) and n2 or n3))
 46 end
 47
 48 -- require
math

 49
 50 function maxSumRec(a,
left, right)
 51     assert(type(a) == "table", "Argument
a must be a number array."
)
 52     assert(type(left) == "number" and type(right) == "number",
 53             "Argument left&right  must be number
arrays."
)
 54
 55     if left == right then
 56         if a[left] > 0 then
 57             return a[left]
 58         else
 59             return 0
 60         end
 61     end
 62
 63     local center = math.floor((left
+ right) / 2)
 64     local maxLeftSum = maxSumRec(a, left,
center)
 65     local maxRightSum = maxSumRec(a, center+1, right)
 66
 67     local maxLeftBorderSum = 0
 68     local leftBorderSum = 0
 69     for i=center,left,-1 do
 70         leftBorderSum
= leftBorderSum + a[i]
 71         if leftBorderSum > maxLeftBorderSum then
 72             maxLeftBorderSum
= leftBorderSum
 73         end
 74         i
= i - 1
 75     end
 76
 77     local maxRightBorderSum = 0
 78     local rightBorderSum = 0
 79     for j=center+1,right
do
 80         rightBorderSum
= rightBorderSum + a[j]
 81         if rightBorderSum > maxRightBorderSum then
 82             maxRightBorderSum
= rightBorderSum
 83         end
 84     end
 85
 86     return max3(maxLeftSum, maxRightSum,
maxLeftBorderSum + maxRightBorderSum)
 87 end
 88
 89 function maxSubSum3(a)
 90     assert(type(a) == "table", "Argument
a must be a number array."
)
 91
 92     return maxSumRec(a, 1, 6)
 93
 94 end
 95
 96 function maxSubSum4(a)
 97     assert(type(a) == "table", "Argument
a must be a number array."
)
 98
 99     local maxSum = 0
100     local thisSum = 0
101
102     for i=1,#a
do
103         thisSum
= thisSum + a[i]
104
105         if thisSum > maxSum then
106             maxSum
= thisSum
107         elseif thisSum < 0 then
108             thisSum
= 0
109         end
110
111     end
112
113     return maxSum
114
115 end
116
117 -- Test Code
118
119 t = {-2, 11, -4, 13, -5, -2 }
120
121 print("maxSubSum1(t):" .. maxSubSum1(t))
122 print("maxSubSum2(t):" .. maxSubSum2(t))
123 print("maxSubSum3(t):" .. maxSubSum3(t))
124 print("maxSubSum4(t):" .. maxSubSum4(t))
125
126
127

PYTHON:

 1
#!/usr/bin/env
python

 2
 3 # How Short
and Clean it is I shocked as a CPP Programmer

 4 def maxSubSum1(a):
 5     maxSum = 0
 6
 7     for i in a:
 8         for j in a[i:]:
 9             thisSum
= 0
10
11             for k in a[i:j]:
12                 thisSum
+= k
13
14             if thisSum > maxSum:
15                 maxSum
= thisSum
16     
17     return maxSum
18
19 def maxSubSum2(a):
20     maxSum = 0
21
22     for i in a:
23         thisSum
= 0
24         for j in a[i:]:
25             thisSum
+= j
26
27             if thisSum > maxSum:
28                 maxSum
= thisSum
29
30     return maxSum
31
32
33 def max3(n1,
n2, n3):
34     return ((n1 if n1
> n3 else n3) if n1 > n2 else (n2
if n2 > n3 else n3))
35
36 def maxSumRec(a,
left, right):
37     if left == right:
38         if  a[left] > 0:
39             return a[left]
40         else:
41             return 0
42
43     center = (left +
right)//2
44     maxLeftSum =
maxSumRec(a, left, center)
45     maxRightSum =
maxSumRec(a, center+1, right)
46
47     maxLeftBorderSum
= 0
48     leftBorderSum = 0
49     for i in a[center:left:-1]:
50         leftBorderSum
+= i
51         if leftBorderSum > maxLeftBorderSum:
52             maxLeftBorderSum
= leftBorderSum
53
54     maxRightBorderSum
= 0
55     rightBorderSum =
0
56     for i in a[center+1:right]:
57         rightBorderSum
+= i
58         if rightBorderSum > maxRightBorderSum:
59             maxRightBorderSum
= rightBorderSum
60     
61     return max3(maxLeftSum,
maxRightBorderSum, maxLeftBorderSum + maxRightBorderSum)
62
63 def maxSubSum3(a):
64     return maxSumRec(a, 0,
len(a)-1    )
65
66 def maxSubSum4(a):
67     maxSum = 0
68     thisSum = 0
69
70     for i in a:
71         thisSum
+= i
72
73         if thisSum > maxSum:
74             maxSum
= thisSum
75         elif thisSum < 0:
76             thisSum
= 0
77
78     return maxSum
79             
80 def test():
81     t = (-2, 11, -4,
13, -5, -2)
82
83     print "maxSubSum1:%d" %
maxSubSum1(t)
84     print "maxSubSum2:%d" %
maxSubSum2(t)
85     print "maxSubSum3:%d" %
maxSubSum3(t)
86     print "maxSubSum4:%d" %
maxSubSum4(t)
87
88 if __name__ == '__main__':
89     test()

BASH:

1 #!/usr/bin/env bash
2
绕了我吧。。。。。特别是算法二。。复杂的递归用bash来写就是自虐。Bash似乎本来就不是用来描述算法用的,呵呵,以后没有什么事一般就不把bash搬出来了。

 

 

 

write by 九天雁翎(JTianLing) -- www.jtianling.com

 

阅读全文....

Windows中多指针输入技术的实现与应用(10 双鼠标五子棋源代码 全系列完)


这是突然看到才想起来发的,发到我常用的地址中:

http://groups.google.com/group/jiutianfile

那时候带着笔记本,台式机上的源码都发不了,直到现在才想起来:)

很多朋友发邮件或者在博客中问过我为什么没有继续对多鼠标这个东西研究下去,呵呵,在此一并答复了,本人实在是工作忙啊。。。。。。。再次说明一下什么叫 忙,每天工作12个小时以上,每周工作6天,再加上你看看我最近学的东西,lua,python,bash....实在没有时间了,呵呵

那个地方现在有两个五子棋的源码了,一个是单鼠标用左右键来玩的,一个是双鼠标都用左键来玩的。你可以对比一下,看看实现多鼠标需要添加些什么,呵呵,其实也不多,这个示例程序虽然简单,但是却实现了想要的基本功能。

图我也贴一个,不偷懒了。。。。呵呵,毕竟这也算是我以前研究比较久的成果。

展示一下:






class CMyApp : public CWinApp

{

public:

    virtual BOOL
InitInstance();

};

 

class CMainWindow : public CMultiMouseWindow

{

protected:

    enum gridState
{ Unputed, PutedWhite,
PutedBlack};   //enum
格子的个状态

    enum Turn
{blackTurn,whiteTurn};   //enum
轮到谁下的状态

    enum winnerLast
{NoOne,WhiteWin,BlackWin};    //enum
有没有胜利者的状态

    Turn m_nextTurn;  //下轮执棋者

    const static
int nClientSize
= 700;    //
客户区大小,可改变

    const static
int nGridNum
= 20;    //
格数,可改变

    int m_countStep;  //目前所下步数

    void DrawBoard(CDC &dc); //画棋盘

    CRect m_rcGrid[nGridNum][nGridNum];    //棋盘的每个格子的矩形范围

    gridState m_stateGrid[nGridNum][nGridNum];    //棋盘每个格子的状态

    void DrawWhite(CDC &dc,int i,int j);   //White

    void DrawBlack(CDC &dc,int i,int j);   //Black

    void ResetGame(); //重新开始游戏

    void CheckForGameOver(Turn thisTurn,int i,int j); //查找需不需要结束游戏

    BOOL IsWinner(Turn thisTurn,int i,int j); //是否有胜利者

    BOOL IsDraw();    //是否平局

 

public:

    CMainWindow();

protected:

    afx_msg void OnPaint();

    afx_msg void OnLButtonDown(UINT nFlags,CPoint point);

    afx_msg void OnNcLButtonDblClk(UINT nHitTest,CPoint point);

    DECLARE_MESSAGE_MAP()

};



#include <afxwin.h>

#include <cmath>

#include <memory>

#include "MultiMouseWindow.h"

#include "resource.h"

#include "gobang.h"

 

CMyApp myApp;

//

//CMyApp的成员函数

//

BOOL CMyApp::InitInstance()

{

    m_pMainWnd = new CMainWindow;

    m_pMainWnd->ShowWindow(m_nCmdShow);

    m_pMainWnd->UpdateWindow();

    return TRUE;

}

//

//CMainWindow的消息映射和成员函数定义

//

BEGIN_MESSAGE_MAP(CMainWindow,CFrameWnd)

    ON_WM_PAINT()

    ON_WM_LBUTTONDOWN()

    ON_WM_NCLBUTTONDBLCLK()

END_MESSAGE_MAP()

 

 

CMainWindow::CMainWindow()

{

    //执黑的先下棋,并定下窗口固定宽度

    CString wndClassStr = ::AfxRegisterWndClass(CS_DBLCLKS);

    Create(wndClassStr,_T("两鼠标五子棋by九天雁翎       (双击标题栏重新开始游戏)"),

       WS_OVERLAPPED | WS_SYSMENU | WS_CAPTION
| WS_MINIMIZEBOX);

    CRect rect(0,0,nClientSize+2,nClientSize+2);

    CalcWindowRect(&rect);

    SetWindowPos(NULL,0,0,rect.Width(),rect.Height(),

       SWP_NOZORDER | SWP_NOMOVE | SWP_NOREDRAW);

    m_hiconCursor[1] = LoadIcon(AfxGetInstanceHandle(),MAKEINTRESOURCE(IDI_CURSOR));

    m_hiconCursor[2] = LoadIcon(AfxGetInstanceHandle(),MAKEINTRESOURCE(IDI_CURSOR2));

    //初始化自定义的成员变量

    m_nextTurn = whiteTurn;

    m_countStep = 0;

   

    if(m_nMouseNumber
!= 3)

    {

       MessageBox(_T("请插入个鼠标"));

       PostQuitMessage (0);

 

    }

    ::ZeroMemory(m_rcGrid,nGridNum
* nGridNum * sizeof(CRect));

    ::ZeroMemory(m_stateGrid,nGridNum
* nGridNum * sizeof(gridState));

   

 

 

 

}

 

void CMainWindow::OnPaint()

{

    CPaintDC dc(this);

    DrawBoard(dc);

    DrawMultiCursor();

}

 

void CMainWindow::DrawBoard(CDC
&dc)

{

    CRect rect;

    GetClientRect(&rect);

 

    //画背景

    CBrush brush(RGB(198,130,66));

    dc.FillRect(rect,&brush);

 

//开始画纵横线,利用rect大小来画线,一是代码重用度高,二是以前做好了

//效率稍微低点,不过将来要是改变客户区大小或用可缩放窗口就可以不改了

   

    //定义画线的画笔并选中

    CPen pen(PS_SOLID,2,RGB(0,0,0));

    CPen *pOldPen
= dc.SelectObject(&pen);

 

    //求方格宽高

    int nGridWidth
= nClientSize / nGridNum  ; 

    int nGridHeight
= nClientSize / nGridNum
;

   

 

    //计算每个方格矩形范围

    for(int
i = 0; i
< nGridNum; ++i)

       for(int
j = 0; j
< nGridNum; ++j)

       {

           m_rcGrid[i][j] = CRect(rect.left + (nGridWidth
* j),

                               rect.top + (nGridHeight * i),

                               rect.left + nGridWidth +(nGridWidth
* j),

                               rect.top + nGridHeight + (nGridHeight
* i));

       }

 

 

    for(int
i = 0; i
<= nGridNum; ++i)   //
画横线

    {

       int y
= (nGridHeight * i)
+ rect.top;

       dc.MoveTo(rect.left,y);

       dc.LineTo(rect.right,y);

    }

 

    for(int
i = 0; i
<= nGridNum; ++i)   //
画竖线

    {

       int x
= (nGridWidth * i)
+ rect.left;

       dc.MoveTo(x,rect.top);

       dc.LineTo(x,rect.bottom);

    }

 

    //画下已经下好的棋

 

    for(int
i=0; i<nGridNum; ++i)

       for(int
j=0; j<nGridNum; ++j)

       {

           if(m_stateGrid[i][j] == Unputed)

           {

              continue;

           }

           else if(m_stateGrid[i][j] == PutedWhite)

           {

              DrawWhite(dc,i,j);

           }

           else if(m_stateGrid[i][j] == PutedBlack)

           {

              DrawBlack(dc,i,j);

           }

       }

 

}

 

//左键下黑

void CMainWindow::OnLButtonDown(UINT
nFlags, CPoint
point)

{

    if(m_pSiRawMouse[1].usButtonFlags & RI_MOUSE_LEFT_BUTTON_DOWN)

    {

           //若本轮不属黑,即不响应

       if(m_nextTurn
!= blackTurn)

           return;

       for(int
i = 0; i<nGridNum; ++i)

           for(int j = 0; j<nGridNum;
++j)

           {

              CPoint pt(m_pSiRawMouse[1].X,m_pSiRawMouse[1].Y);

              ScreenToClient(&pt);

              if(m_rcGrid[i][j].PtInRect(pt) && m_stateGrid[i][j] == Unputed)

              {

                  CClientDC dc(this);

                  m_nextTurn = whiteTurn;

                  m_stateGrid[i][j] = PutedBlack;

                  DrawBlack(dc,i,j);

                  CheckForGameOver(blackTurn,i,j);

              }

           }

      

       m_pSiRawMouse[1].usButtonFlags &= ~RI_MOUSE_LEFT_BUTTON_DOWN;

 

    }

    if(m_pSiRawMouse[2].usButtonFlags & RI_MOUSE_LEFT_BUTTON_DOWN)

    {

           //若本轮不属白,即不响应

       if(m_nextTurn
!= whiteTurn)

           return;

       for(int
i = 0; i<nGridNum; ++i)

           for(int j = 0; j<nGridNum;
++j)

           {

              CPoint pt(m_pSiRawMouse[2].X,m_pSiRawMouse[2].Y);

              ScreenToClient(&pt);

              if(m_rcGrid[i][j].PtInRect(pt) && m_stateGrid[i][j] == Unputed)

              {

                  CClientDC dc(this);

                  m_nextTurn = blackTurn;

                  m_stateGrid[i][j] = PutedWhite;

                  DrawWhite(dc,i,j);

                  ++m_countStep;

                  CheckForGameOver(whiteTurn,i,j);

              }

           }

      

       m_pSiRawMouse[2].usButtonFlags &= ~RI_MOUSE_LEFT_BUTTON_DOWN;

    }

 

}

 

void CMainWindow::DrawBlack(CDC
&dc, int
i, int j)

{

    CRect rect(m_rcGrid[i][j]);

    rect.DeflateRect(1,1);

    dc.SelectStockObject(BLACK_BRUSH);

    dc.Ellipse(rect);

}

 

void CMainWindow::DrawWhite(CDC
&dc, int
i, int j)

{

    CRect rect(m_rcGrid[i][j]);

    rect.DeflateRect(1,1);

    dc.SelectStockObject(WHITE_BRUSH);

    dc.Ellipse(rect);

 

}

 

void CMainWindow::CheckForGameOver(Turn
thisTurn,int
i,int j)

{

    if(IsWinner(thisTurn,i,j))

    {

       if(thisTurn
== blackTurn)

       {

           CString string;

           string.Format(_T("GOOD! Black Wins in %d steps."),m_countStep);

           MessageBox(string,_T("Game Over!"));

           ResetGame();

       }

       else if(thisTurn == whiteTurn)

       {

           CString string;

           string.Format(_T("GOOD! White Wins in %d steps."),m_countStep);

           MessageBox(string,_T("Game Over!"));

           ResetGame();

       }

      

    }

    else if(IsDraw())

    {

       MessageBox(_T("OK,It's
draw."
),_T("Draw Game!"));

       ResetGame();

    }

 

}

 

//此为本软件最主要的部分,即检测是否有五个棋连在一起

//以横纵和两条对角线的方向分别检测,感觉比较笨

//暂时不知道有没有更好的办法,望来信赐教

BOOL CMainWindow::IsWinner(Turn thisTurn,int i,int j)

{

    int count
= 1;

    gridState checkFor; //状态对比值

    if(thisTurn
== blackTurn)

       checkFor = PutedBlack;

    else if(thisTurn == whiteTurn)

       checkFor = PutedWhite;

 

    //横方向检测

    for(int
m=1; m<5;
++m)

    {

       if(j
- m > 0 && m_stateGrid[i][j-m] == checkFor)

           ++count;

       else

           break;

    }

    for(int
m=1; m<5;
++m)

    {

       if(j
+ m < nGridNum
&& m_stateGrid[i][j+m] == checkFor)

           ++count;

       else

           break;

    }

    if(count
>=5)

       return TRUE;

    count = 1;

 

    //竖方向检测

    for(int
m=1; m<5;
++m)

    {

       if(i-m>0 && m_stateGrid[i-m][j] == checkFor)

           ++count;

       else

           break;

    }

    for(int
m=1; m<5;
++m)

    {

       if(i+m<nGridNum
&& m_stateGrid[i+m][j] == checkFor)

           ++count;

       else

           break;

    }

    if(count
>=5)

       return TRUE;

    count = 1;

 

    //左上至右下方向检测

    for(int
m=1; m<5;
++m)

    {

       if(i-m>0 && j-m>0 && m_stateGrid[i-m][j-m] == checkFor)

           ++count;

       else

           break;

    }

    for(int
m=1; m<5;
++m)

    {

       if(i+m<nGridNum
&& j+m<nGridNum && m_stateGrid[i+m][j+m] == checkFor)

           ++count;

       else

           break;

    }

    if(count
>=5)

       return TRUE;

    count = 1;

 

    //右上至左下方向检测

    for(int
m=1; m<5;
++m)

    {

       if(i-m>0 && j+m<nGridNum
&& m_stateGrid[i-m][j+m] == checkFor)

           ++count;

       else

           break;

    }

    for(int
m=1; m<5;
++m)

    {

       if(i+m<nGridNum
&& j-m>0
&& m_stateGrid[i+m][j-m] == checkFor)

           ++count;

       else

           break;

    }

    if(count
>=5)

       return TRUE;

    return FALSE;

}

 

//BOOL
CMainWindow::OnSetCursor(CWnd *pWnd, UINT nHitTest, UINT message)

//{

//  if(nHitTest == HTCLIENT)

//  {

//     if(m_nextTurn == blackTurn)

//     {

//         ::SetCursor(::AfxGetApp()->LoadCursor(IDC_black));

//         return TRUE;

//     }

//     else if(m_nextTurn == whiteTurn)

//     {

//         ::SetCursor(::AfxGetApp()->LoadCursor(IDC_white));

//         return TRUE;

//     }

//  }

//  return
CFrameWnd::OnSetCursor(pWnd,nHitTest,message);

//}

 

//当都下满了,即为平局

BOOL CMainWindow::IsDraw()

{

    int i,j;

    for(i=0;
i<nGridNum;
++i)

       for(j=0;
j<nGridNum;
++j)

       {

           if(m_stateGrid[i][j]==Unputed)

              break;

       }

    if(i==nGridNum && j==nGridNum)

       return TRUE;

    else

       return FALSE;

}

 

void CMainWindow::ResetGame()

{

    m_nextTurn = whiteTurn;

    m_countStep = 0;

    ::ZeroMemory(m_stateGrid,nGridNum
* nGridNum * sizeof(gridState));

    Invalidate();

}

 

void CMainWindow::OnNcLButtonDblClk(UINT
nHitTest, CPoint
point)

{

    if(nHitTest
== HTCAPTION)

    {

       ResetGame();

    }

 

    return CFrameWnd::OnNcLButtonDblClk(nHitTest,point);

}

 

#ifndef ___MULTI_MOUSE_WINDOW_H__

#define ___MULTI_MOUSE_WINDOW_H__

 

class CMultiMouseWindow :
public CFrameWnd

{

typedef struct SiRawMouse

{

    long X;

    long Y;

    USHORT usButtonFlags;

    HANDLE hDevice;

}SiRawMouse,*pSiRawMouse;       //输入设备鼠标的自定义类型数组

 

//判定是否为系统鼠标的函数

private:

    void InitRawInput();

    bool IsRootMouse(TCHAR cDeviceString[]);

    void CheckBound(long &x,long &y);

protected:

    pSiRawMouse m_pSiRawMouse;

    TCHAR m_mousePostion[256];  // 鼠标位置缓存

    HICON  m_hiconCursor[10];
//
绘制的鼠标

    int m_nMouseNumber;
//
鼠标数量

    void DrawMultiCursor();

public:

    CMultiMouseWindow();

protected:

    DECLARE_MESSAGE_MAP()

public:

 

protected:

    virtual LRESULT
WindowProc(UINT
message, WPARAM
wParam, LPARAM
lParam);

public:

    afx_msg void OnDestroy();

};

 

 

#endif // ___MULTI_MOUSE_WINDOW_H__

 

#include <afxwin.h>

#include <cmath>

#include "MultiMouseWindow.h"

#include "resource.h"

#include <Windows.h>

 

 

BEGIN_MESSAGE_MAP(CMultiMouseWindow,CFrameWnd)

    ON_WM_DESTROY()

END_MESSAGE_MAP()

 

 

CMultiMouseWindow::CMultiMouseWindow():m_nMouseNumber(0)

{

    Create(NULL,_T("Hello"),WS_OVERLAPPEDWINDOW);

    for(int
i=0; i
< 10; ++i)

    {

       m_hiconCursor[i]  = LoadIcon(AfxGetInstanceHandle(),MAKEINTRESOURCE(IDI_CURSOR));

    }

    ShowCursor(false);

    InitRawInput();  

}

 

void CMultiMouseWindow::InitRawInput()

{

    UINT nDevices;       //输入设备的数量

 

    //第一次调用GetRawInputDeviceList获得输入设备的数量

    GetRawInputDeviceList(NULL, &nDevices,
sizeof(RAWINPUTDEVICELIST));

    //第二次调用GetRawInputDeviceList获得RawInputDeviceList数组

    PRAWINPUTDEVICELIST pRawInputDeviceList;// =
new RAWINPUTDEVICELIST[nDevices];

    pRawInputDeviceList = (RAWINPUTDEVICELIST *)calloc(nDevices,sizeof(RAWINPUTDEVICELIST));

    GetRawInputDeviceList(pRawInputDeviceList, &nDevices,
sizeof(RAWINPUTDEVICELIST));

 

    //获得输入设备中鼠标的数量

    for(int
i=0; i
< static_cast<int>(nDevices); ++i)

    {

       if(pRawInputDeviceList[i].dwType == RIM_TYPEMOUSE)

       {

           ++m_nMouseNumber;

       }

    }

   

    //获得输入设备鼠标的自定义类型数组,其中索引为的为系统鼠标

    m_pSiRawMouse = (SiRawMouse *)calloc(m_nMouseNumber,sizeof(SiRawMouse));

    LPVOID lpb;

    UINT dwSize;

 

    for(int
i=0,j=1; i < static_cast<int>(nDevices)
&& j < m_nMouseNumber;
++i)

    {

       if(pRawInputDeviceList[i].dwType == RIM_TYPEMOUSE)

       {

           //连续两次调用GetRawInputDeviceInfo以读取RIDI_DEVICENAME

           //并通过此值判断是否为系统鼠标

           GetRawInputDeviceInfo(pRawInputDeviceList[i].hDevice,RIDI_DEVICENAME,NULL,&dwSize);

           lpb = malloc(sizeof(LPVOID) * dwSize);

           GetRawInputDeviceInfo(pRawInputDeviceList[i].hDevice,RIDI_DEVICENAME,lpb,&dwSize);

           TCHAR *deviceName = (TCHAR*)lpb;

          

           //将系统鼠标的保存在索引中,其他依次列在后面

           if(IsRootMouse(deviceName))

           {

              m_pSiRawMouse[0].hDevice = pRawInputDeviceList[i].hDevice;

              m_pSiRawMouse[0].X = 0;

              m_pSiRawMouse[0].Y = 0;

              m_pSiRawMouse[0].usButtonFlags = 0;

           }

           else

           {

              m_pSiRawMouse[j].hDevice = pRawInputDeviceList[i].hDevice;

              m_pSiRawMouse[j].X = 0;

              m_pSiRawMouse[j].Y = 0;

              m_pSiRawMouse[j].usButtonFlags
= 0;

              ++j;

           }

           free(lpb);

       }

    }

 

    free(pRawInputDeviceList);

    pRawInputDeviceList = NULL;

 

    //初始化个RawInput设备

    RAWINPUTDEVICE Rid[1]; //分配RawInput设备的空间

    Rid[0].usUsagePage = 0x01;

    Rid[0].usUsage = 0x02;

    Rid[0].dwFlags = 0;

    Rid[0].hwndTarget = NULL;

   

    //注册RawInput设备

    if (RegisterRawInputDevices(Rid, 1, sizeof (Rid [0])) == FALSE)
{

       MessageBox(_T("RawInput
Register Error."
));

    }

 

    return ;

}

bool CMultiMouseWindow::IsRootMouse(TCHAR
cDeviceString[])

{

    //一般系统鼠标DeviceName的前字节

    TCHAR cRootString[]
= _T("//??//Root#RDP_MOU#0000#");

   

    //通过比较前个字节判断是否为系统鼠标

    if (wcslen(cDeviceString) < 22)

    {

       return false;

    }

    for (int
i = 0; i
< 22; i++)

    {

       if (cRootString[i] != cDeviceString[i])

       {

       return false;

       }

    }

    return true;

}

 

void CMultiMouseWindow::CheckBound(long
&x,long
&y)

{

    CClientDC dc(this);

    if(x<0)

       x = 0;

    if(y<0)

       y = 0;

 

    //最大值由GetDeviceCaps函数获取以适应不同系统设置

    if(x>(long)dc.GetDeviceCaps(HORZRES))

       x = (long)dc.GetDeviceCaps(HORZRES);

    if(y>(long)dc.GetDeviceCaps(VERTRES))

       y = (long)dc.GetDeviceCaps(VERTRES);

}

 

//CMainWindow
mesage map and member functions

 

void CMultiMouseWindow::DrawMultiCursor()

{

    CClientDC dc(this);

    for(int
i=1; i<m_nMouseNumber; ++i)

    {

       POINT pt = { m_pSiRawMouse[i].X, m_pSiRawMouse[i].Y };

       ScreenToClient(&pt);

       dc.DrawIcon(pt, m_hiconCursor[i]);

    }

 

}

 

LRESULT CMultiMouseWindow::WindowProc(UINT
message, WPARAM
wParam, LPARAM
lParam)

{

    // TODO: 在此添加专用代码和/或调用基类

    LPVOID lpb;

    UINT dwSize;

    RAWINPUT *raw;

 

    switch (message)

    {

       //响应WM_INPUT消息为本程序的主要部分

       case WM_INPUT:

       {

           ::GetRawInputData((HRAWINPUT)lParam,
RID_INPUT, NULL,
&dwSize,

                         sizeof(RAWINPUTHEADER));

 

           lpb = malloc(sizeof(LPVOID) * dwSize);

           if (lpb == NULL)

           {

              return 0;

           }

 

           ::GetRawInputData((HRAWINPUT)lParam,
RID_INPUT, lpb,
&dwSize,

               sizeof(RAWINPUTHEADER));

 

           raw = (RAWINPUT*)lpb;

 

           if (raw->header.dwType == RIM_TYPEMOUSE)
//
判断是否为鼠标信息

           {

              raw->data.mouse.usFlags = MOUSE_MOVE_ABSOLUTE;

              for(int i=1; i<m_nMouseNumber;
++i)

              {

                  if(m_pSiRawMouse[i].hDevice == raw->header.hDevice)

                  {

 

                     POINT pt = {m_pSiRawMouse[i].X,m_pSiRawMouse[i].Y};

                     ScreenToClient(&pt);

                     CRect rect;

                     rect.left = pt.x - 30;

                     rect.right = pt.x + 30;

                     rect.top = pt.y - 30;

                     rect.bottom = pt.y + 30;

 

                     m_pSiRawMouse[i].X += raw->data.mouse.lLastX;

                     m_pSiRawMouse[i].Y += raw->data.mouse.lLastY;

 

                     InvalidateRect(&rect,TRUE);

                     CheckBound(m_pSiRawMouse[i].X,m_pSiRawMouse[i].Y);

                     m_pSiRawMouse[0].X = m_pSiRawMouse[i].X;

                     m_pSiRawMouse[0].Y = m_pSiRawMouse[i].Y;

                     if(raw->data.mouse.usButtonFlags
!= 0)

                     {

                         m_pSiRawMouse[i].usButtonFlags
= raw->data.mouse.usButtonFlags;

                     }

                    

                  }

                  ::SetCursorPos(m_pSiRawMouse[0].X,
m_pSiRawMouse[0].Y);

 

 

              }

           }

 

           free(lpb);  

           return 0;

       }

    }

    return CFrameWnd::WindowProc(message,
wParam, lParam);

}

 

void CMultiMouseWindow::OnDestroy()

{

    CFrameWnd::OnDestroy();

    // TODO: 在此处添加消息处理程序代码

    if(m_pSiRawMouse
!= NULL)

    {

       free(m_pSiRawMouse);

    }

 

    for(int
i=0; i
< 10; ++i)

    {

       DestroyIcon(m_hiconCursor[i]);

    }

    PostQuitMessage (0);

}

 

阅读全文....