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

个人研究《数据结构与算法分析-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);

}

 

阅读全文....

为学习APUE(Unix环境高级编程)偷懒,而写的脚本,基本上相当于一个简单的工程创建脚本了

 首先我单独建了一个目录用来保存学习时需要的目录,将此脚本拷贝到这个目录下面,以后每次以一个参数运行脚本,就会自动创建目录,cpp文件,makefile文件,需要做的就是进入此目录,然后修改cpp文件,然后make,enjoy it!呵呵,说实话,自从学习了bash以后,才越来越觉得linux并不是一个复杂难用的系统。

D:/ubuntu/apue/ctapue.sh.html 1 #!/usr/bin/env bash
 2 dir=apue$1
 3 file=${dir}/apue${1}.cpp
 4
makefile=${dir}/Makefile
 5
 6 if [ -d ${dir} ]
 7 then
 8     echo "the path ${dir} is exist."
 9     exit 1
10 else
11     mkdir ${dir}
12 fi
13
14 # Create the src
file

15 cat >${file} <<end-of-file
16
#include <stdio.h>
17 #include "../apue.h"
18
19
20 int main(int argc, char*
argv[])

21 {
22
23
24     exit(0);
25 }
26
27 end-of-file
28
29 #
Create the makefile

30 cat >${makefile} <<end-of-makefile
31
src=apue${1}.cpp
32 ob=test
33 /${ob} : /${src}
34     g++ -Wall -g -o /${ob} /${src}
35
36 end-of-makefile

阅读全文....

一天一个C Run-Time Library 函数 (11) bsearch

 

一天一个C Run-Time Library 函数  (11)  bsearch

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

 

msdn:

Performs a binary search of a sorted array. A
more secure version is available; see
bsearch_s.

void
*bsearch(

   const void *key,

   const void *base,

   size_t num,

   size_t width,

   int ( __cdecl *compare ) ( const void *, const
void *)

);

 

 

测试程序:(来自MSDN)

#include <search.h>

#include <string.h>

#include <stdio.h>

 

int compare( char **arg1, char **arg2 )

{

    /* Compare all of both strings: */

    return _strcmpi(
*arg1, *arg2
);

}

 

int main( void )

{

    char *arr[]
= {"dog", "pig",
"horse", "cat",
"human", "rat",
"cow", "goat"};

    char **result;

    char *key
= "cat";

    int i;

 

    /* Sort using Quicksort algorithm: */

    qsort( (void *)arr, sizeof(arr)/sizeof(arr[0]), sizeof( char * ), (int (*)(const

       void*, const void*))compare );

 

    for( i
= 0; i < sizeof(arr)/sizeof(arr[0]); ++i
)    /* Output
sorted list */

       printf( "%s ", arr[i] );

 

    /* Find the word "cat" using
a binary search algorithm: */

    result = (char **)bsearch( (char *) &key,
(char *)arr,
sizeof(arr)/sizeof(arr[0]),

       sizeof( char * ), (int (*)(const void*, const void*))compare );

    if( result
)

       printf( "/n%s found at %Fp/n", *result, result
);

    else

       printf( "/nCat not found!/n" );

}

说明:

bsearch又是一个看起来相当有用,但是其实我却一次都没有在实际工作中碰到需要用的函数。。。。二分查找是算法教学的经典内容,呵呵

实际中我还真没有碰到这样的需要,因为碰到需要快速查找的时候一般都用map搞定了。。。人哪。。。才发现用C++也是会越来越懒的。。。。。因为有STL吗,所以map用的不亦乐乎,早完了C语言中该怎么来实现类似效果了。其实就算是想要实现我也很可能是用C++算法库的binary_search吧。

 

 

实现:

MS:

gcc:

对于这样经典的算法好像gccMS终于没有办法不一致了,事实上也是如此,两者几乎没有任何区别,其实现可以在任何关于算法的书籍上找到。

 

效率测试:

见以前有人说过C++的二分查找会比C语言的快,这是很多用C++的人证明C++不比C语言慢的一个例证。但是实际上,我也一直认为,不用其他非C语言特性的东西,为啥C++会比C语言慢呢?除非硬是碰到喜欢用类来描述这样算法的人吧。

 

相关函数:

qsort,不先排序,二分查找可是没有办法进行的

 

个人想法:

非常标准的C语言函数,通用性非常好。最后,我越来越懒了,并且发现这样写下去已经比较脱离我当时的想法了。。。。。现在每天工作回来还真的是很辛苦,脑袋都一直比较痛的感觉。。。。呵呵,郁闷啊。另外,再一次证明了我的恒心和毅力都是很有问题的。于是我找到了又一个来拖延此专题的借口,那就是我发现我现在去学习关于数据结构和算法还有Unix环境高级编程等书的话,实际意义更大。。。。。。。另外,对于多弄弄lua,python也是很有益处,没有想到C语言函数库的函数这么多,这么杂,这么多我完全就没有用过。。。。。用C++的人(比如我),常常将自己使用的语言称为C/C++,似乎表示自己用C++,就一直象在用C一样,自己懂C++也就懂C,不过,其实两者的区别,比我想的要大的多.因为C++有了太多特性,所以很多C语言的相关特性难免都被丢在了被遗忘的角落了.

 

 

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

 

阅读全文....