帐前卒专栏

比如我在工程文件夹下放了一个svm-train.exe的文件

这个exe文件调用后有输出信息。我很想知道这个exe调用过程中到底发生了什么事情。

在java中这样写

Runtime run = Runtime.getRuntime();
Process child = null;
InputStream is = null;

File env = new File(System.getProperty(“user.dir”));
child = run.exec(cmd,null,env);

这个env是用于找到工程的当前目录，相当于进入Dos后先cd到目录，cmd就是你在dos窗口那里打的命令。

run.exec(cmd,null,env);这句就开始执行了。并创建一个Process给child

网上有很多代码有这句：

while(true)
{
if(child.waitFor() == 0)
{
break;
}

}

但是注意如果进入 if(child.waitFor() == 0)
那这个程序就会卡死在这里，直到exe进程结束。这样如果你的exe会运行很长时间，那么在这段时间内就不能打印任何输出信息。

全代码如下：

1. private static boolean CallSVM(String cmd)
2. {
3. Runtime run = Runtime.getRuntime();
4. Process child = null ;
5. InputStream is = null ;
6. 7. try
7. {
8. File env = new File(System.getProperty( “user.dir” ));
9. 11. child = run.exec(cmd, null ,env);
10. 13. String out = null ;
11. 15. 16. // nomal process
12. is = child.getInputStream();
13. FileWriter fw = new FileWriter(env.getAbsolutePath()+ “//log.txt” );
14. BufferedReader br = new BufferedReader( new InputStreamReader(is));
15. 21. 22. while ((out = br.readLine())!= null )
16. {
17. fw.write(out+ “/r/n” );
18. System.out.println(out);
19. }
20. while ( true )
21. {
22. if (child.waitFor() == 0 )
23. {
24. break ;
25. }
26. 34. }
27. 36. 37. fw.write( “-----------------/r/n” );
28. 39. 40. fw.close();
29. br.close();
30. 43. }
31. catch (IOException ioe)
32. {
33. System.err.println( “cmd error:” +cmd);
34. System.err.println(ioe.getMessage());
35. return false ;
36. } catch (InterruptedException e) {
37. // TODO Auto-generated catch block
38. if (child != null )
39. child.destroy();
40. e.printStackTrace();
41. }
42. return true ;
43. }

这里一定要输出放前，waitFor放后

while((out = br.readLine())!=null)
{
fw.write(out+“/r/n”);
System.out.println(out);
}

while(true)
{
if(child.waitFor() == 0)
{
break;
}

}

另外程序在执行过程中while((out =
br.readLine())!=null)这里也会卡住，所以不用担心，调用的dos程序还没有输出，就已经执行到waitFor()那里去了。

这里犯得错误是使用c++的预编译头去编译c语言。

如果解决C1853这个错误呢？

其实就是对每一个.c文件加上

#include “stdafx.h”

然后把.c文件改为.cpp文件

然后在把工程属性中的

configuration properties中的c/c++中的Precompiled Header中的Create / use Precompile
Header 中的User precompile Header 改为

Create precompile Header

How to compile C programs with Microsoft Visual C++ 2005

By default, new _ applications _
created in
Microsoft Visual C++ 2005 Express edition create _ C++ _
_ source code _
.

Here is how to compile _ C _
code. Launch ** Visual C++
2005 Express Edition ** and create a new project. Choose _ Win 32 _
and Win
32 _ Console _
Application. Enter a name in the ** Name ** box below.

Now press the ** Next ** button and then the ** Finish ** button. This will
generate a file called _ name _ .cpp where _ name _ is your entered project
name. Now look to the Solution Explorer (if you can’t see it, click View on
the menu then Solution Explorer), click _ name _ .cpp and press F2. Now press
** backspace ** twice so you end up with _ name _ .c.

Press ** F7 ** To _ compile _
. If you get an error
that say “fatal error C1853: ‘Debug/name.pch’ precompiled header file is from
a previous version of the compiler, or the precompiled header is C++ and you
are using it from C (or vice versa)” then just click the project menu,
properties and change ** Create/Use Precompiled Header ** from _ Use
Precompiled Header _ to _ Create Precompoiled Header _ . Press the ** Apply **
button. It should now compile successfully when you press ** F7 ** .

Using Existing Code

Create an empty project as above and remove all lines except

#include “stdafx.h”

Then paste in your existing code after this include and save it. You should
now be able to compile (press ** F7 ** ) and run your application.

微软的研究方向：

多媒体，自然人机交互，Data-intensive computing(包括数据挖掘，检索等) ,search and online AD(广告),
Compute Science 基础

然后展示了几个很有趣的Demo：

Deblurred image（处理模糊数码照片）

Remote
Computer(这个项目的名字记不得了，不过是在局域网内2M带宽情况下，可以使用web浏览器remote几台机器的试验，据演示效果说：比过去remote
desktop 要好很多。)

Gigapixel image（这个图片像素很高，可以任意缩放，然后主要工作就是在拉近一个图片位置，例如拉近餐馆，就能听到关于餐馆的广告，其他的地方还有很多
声音和人为标注。）不过这个项目个人认为是AD方面的事情，背后需要大量的人力物力。不过是一个很好的AD创新。

为啥要research呢？1.为新产品，2为解决问，3早期系统预警。(Demo原型)

21的计算可能要服务的方面：health,Environment,Education, compute technology integrate .

搜索个性化，自然语言理解和识别，这里演示一个Automatic receptionist

云计算会带来很多问题：资源管理，访问权限，调度协作等。

Semantic and future of search

Search past        current            future

Directories          keyword       sematics

New                  Experienced    Sophisticated

content ---- user ---- action   -------->        sematics—>people—>intent

微软收购了一个PowerSet这个网站使用语义搜索的。

也就是使用多句话代替一句话。

The science of programming

computer software contains no more errors. programmer make no more mistakes.

programming is an Engineering discipline.

Semantics is the science of programming.

Software Engineering Toolset

computer science small ---->BIG

operating system run on the multicore

Horizon is "unlimited ", it is limited by our own imagination.

computer technology is used to computer technology.

what’s past is merely prologue.

认为发展的三个方向：

simulation

communication

_ Embodiment _

_ _

_ many problems: _

Deal with physical world , natural language is not avoided.

teach as wll as a person.

The machine can guass

明白Moore’s law, Aim for mass markets, learn how to deal with uncertainty, learn
how to advoid catastorphes.

这些获得图灵奖的家伙们，当时从来就未曾想过自己有获得图灵奖的那天。只是想知道问题的答案。不是辛勤于工作，也不是想做好什么事情，只是想做点有趣的事情。另外关键
是lucky。

Base rule do base.偶然听到这句话。莫非是越低级的规则改能做好底层工作吗？

计算新视野，21世纪的计算混了顿不错的午餐，发现北大的饭就是比中科院的饭菜好.这是为啥么。国家部门不发钱吗？
另外自己英语的确不怎么好，只有第一个上场的Butler LAMPSON和洪小文，沈向阳的讲话听懂了。其他听的云里雾里中。不过Tony
Hoare的慢速英语也听的差不多。另外，那个同声翻译真的是差…嗯嗯哦哦的讲话…所以索性关掉，听正版英语了。

午饭之时碰到了过去的学长，现在在做Web Search。聊了几句。往前走了几步发现了疯子，然后发现疯子对另外一个男的有莫大的兴趣，可惜那个男的只对另外两个女
的感兴趣。于是上前打声招呼，踹了疯子一脚，急急忙忙的回到讲堂。

按我的这篇文章所写：

http://blog.csdn.net/cctt_1/archive/2008/11/02/3206314.aspx

这里这里读出写入英文是没有问题的。

但是我们需要读出写入中文。我在mysql的表有一项设置字符集，改为了GBK编码。

但是还是使用了我上篇文章所写的编码，结果发现插入中文时变为：？？？

插入中英文结合时，全部的中文变为？？英文不变。

在网上搜了下，然后将上篇文章的编码改为：

1. private SqlAccess sqlAccess = new SqlAccess();
2. private void button1_Click( object sender, EventArgs e)
3. {
4. DataSet ds = sqlAccess.SelectDataSet( “select * from users” );
5. 6. label1.Text = “” ;
6. Array alist = ds.Tables[0].Rows[0].ItemArray;
7. foreach ( object o in alist)
8. {
9. label1.Text += o.ToString();
10. }
11. UpdateName();
12. }
13. private const string sql = “UPDATE USERS SET userName=@userName  WHERE userID=@userID” ;
14. private const string userName = “@userName” ;
15. private const string userID = “@userID” ;
16. private void UpdateName()
17. {
18. int i = 1;
19. string name = GB2312_ISO8859( “和好多岁收到暗示” );
20. MySqlParameter[] my =
21. {
22. new MySqlParameter(userName,MySqlDbType.String),
23. new MySqlParameter(userID,MySqlDbType.Int32)
24. };
25. my[0].Value = name;
26. my[1].Value = i;
27. label2.Text = sqlAccess.EXESql(sql, my).ToString();
28. }
29. 31. //写入数据库时要进行gb2312转换到iso8895
30. public string GB2312_ISO8859( string srcString)
31. {
32. //字符集gb2312转为iso8859
33. System.Text.Encoding iso8859=System.Text.Encoding.GetEncoding( “iso8859-1” );
34. System.Text.Encoding gb2312=System.Text.Encoding.GetEncoding( “gb2312” );
35. return iso8859.GetString(gb2312.GetBytes(srcString));
36. }

发现还是原来的问题。然后又搜了搜mysql的中文文档。发现好像column还是有字符集属性的…怎么不知道为啥这样做…太麻烦了。于是改了每一个表中需要中
文的列都改为了gbk，在mysql图形界面的字段详细资料中。但是如果你是使用的mysql非图形界面…那就要辛苦的alter
吧.改完后，运行成功，再也没有？？了。

发现windowsApplication使用的string是gb2312编码，但是显示的时候gb2312和iso8895-1都可以。

所以在写入数据库时要转换为iso8895-1编码。注意这里如果转为System.Text.Encoding.GetEncoding(“GBK”)是不可以的。

首先去mysql网站下载一个mysql非安装版本

_ http://dev.mysql.com/downloads/mysql/5.0.html _

如果你感觉使用dos命令行不方便的话，可以顺便也下载一个GUI客户端：

_ http://dev.mysql.com/downloads/gui-tools/5.0.html _

然后打开vs…这个版本必须是2003以上。

然后呢，建立一个windowsApplication工程，然后在里面的app.config

如果你想把连接字符串写在程序里的话：将下面的代码改为 ** string ** strConn =  “server=localhost;user
id=root;password=;database=test;allow zero datetime= ** true ** ;”

这里与sqlserver连接字符串相区别的是：

user->user id,

当然估计没有下载MySql.Data.dll所以在

_ http://dev.mysql.com/downloads/connector/net/5.2.html _
下载

然后在net工程里添加引用，找到刚才你下载MySql.Data.dll的压缩包，解压后，在bin目录下有MySql.Data.dll.

添加成功后，在你的代码里添加一个

using MySql.Data.MySqlClient;

然后下面的和SqlClient的效果是一样的。只不过前面多了"My"

下面看具体的代码：

1. using System;
2. using System.Collections.Generic;
3. using System.Text;
4. using System.Data;
5. using MySql.Data.MySqlClient;
6. 7. 8. namespace SqlConnect
7. {
8. /// 
9. /// author: chico chen
10. /// date: 2008-11-02
11. /// 
12. public class SqlAccess
13. {
14. private MySqlConnection conn = null ;
15. private MySqlCommand cmd = null ;
16. /// 
17. /// 建立与数据库的连接
18. /// 
19. /// 
20. private MySqlConnection CreateConn()
21. {
22. string strConn = System.Configuration.ConfigurationSettings.AppSettings[ “Restaurant” ].ToString();
23. // SqlConnection 对象
24. conn = new MySqlConnection(strConn);
25. try
26. {
27. conn.Open();
28. return conn;
29. }
30. catch (Exception e)
31. {
32. Console.WriteLine( “sql 连接未打开” );
33. return null ;
34. }
35. }
36. /// 
37. /// 关闭与数据库的连接
38. /// 
39. private void CloseConn()
40. {
41. try
42. {
43. conn.Close();
44. }
45. catch (Exception e)
46. {
47. Console.WriteLine( “sql 连接未关闭” );
48. }
49. }
50. 53. /// 
51. /// 查询数据库
52. /// 
53. /// 类似于SELECT * FROM [User];
54. /// 
55. public DataSet SelectDataSet( string sql)
56. {
57. CreateConn();
58. MySqlDataAdapter sda = new MySqlDataAdapter(sql, conn);
59. DataSet ds = new DataSet();
60. sda.Fill(ds);
61. CloseConn();
62. return ds;
63. }
64. /// 
65. /// 执行无返回值的sql语句，如果成功返回true，失败返回false；
66. /// 
67. /// 类似于UPDATE [USER] SET userID=@userIDC  WHERE userID=@userID
68. /// 或delete from [user] where userID=@userID;
69. /// 或者insert into [user] (userID, password, name) values (@userID,@password,@Name) ;
70. /// 
71. ///  SqlParameter[] sp = new SqlParameter[3];
72. ///  sp[0] = new SqlParameter(user, SqlDbType.VarChar, 50);
73. /// sp[0].Value = “www”;
74. /// 
75. /// 
76. public bool EXESql( string sqlcmd, MySqlParameter[] sqlPara)
77. {
78. try
79. {
80. CreateConn();
81. cmd = new MySqlCommand();
82. cmd.Connection = conn;
83. cmd.CommandType = CommandType.Text;
84. cmd.CommandText = sqlcmd;
85. foreach (MySqlParameter sp in sqlPara)
86. {
87. cmd.Parameters.Add(sp);
88. }
89. cmd.ExecuteNonQuery();
90. CloseConn();
91. return true ;
92. }
93. catch (Exception e)
94. {
95. return false ;
96. }
97. }
98. 102. }
99. }

这里调用的代码这样写：

DataSet ds = sqlAccess.SelectDataSet(“select * from user”);

当然如果你使用DataSet还要加using System.Data;

连接字符串中为什么要加Allow Zero datetime  = true是因为在添加数据库数据时，

添加了错误的dateTime数据，所以mysql自动将其转为0000-00-00 00:00:00,所以在

DataSet ds = new DataSet();
sda.Fill(ds);

这里就会报异常，原因是不支持这种Date/Time。

要使用刚才的接口的话：

1. {
2. DataSet ds = sqlAccess.SelectDataSet( “select * from user” );
3. 4. 5. Array alist = ds.Tables[0].Rows[0].ItemArray;
4. foreach ( object o in alist)
5. {
6. label1.Text += o.ToString();
7. }
8. UpdateName();
9. }
10. 13. 14. private const string sql = “UPDATE USER SET userName=@userName  WHERE userID=@userID” ;
11. private const string userName = “@userName” ;
12. private const string userID = “@userID” ;
13. private void UpdateName()
14. {
15. int i = 1;
16. string name = “xxxx” ;
17. MySqlParameter[] my =
18. {
19. new MySqlParameter(userName,MySqlDbType.String),
20. new MySqlParameter(userID,MySqlDbType.Int32)
21. };
22. my[0].Value = name;
23. my[1].Value = i;
24. label2.Text = sqlAccess.EXESql(sql, my).ToString();
25. }

刚才不久百度给我打了电话。我没有接到。之后拨通电话，发现是百度的总机。不知道要拨哪个分机，所以就挂掉了。
因为我参加了百度的笔试。所以认为可能是百度让我去参加面试。欣喜的将此事告诉了别人。
我：“我没有接起百度给我的面试电话。”
A:“你怎么知道百度是让你去面试？”
我：“我猜的。”
A:“那是百度看你的卷子看的崩溃了，他是想通知你以后不要浪费别人公司的草稿纸，不会答就不要去做！…”
我：“你的观点很有新意，我要写成blog!”
。。于是就有了这篇blog。据说blog是采用了传说中杀人于无形的流水帐式文笔。不知看过此blog的各位小同学中有没有谁吐血身亡。

主要是为了件T恤和免费的东西吃才去的。

不过在听别人的讲的过程中也有点点滴滴的体会,同时也扩展了自己的知识面。

RSpec这个是可以将文本语言转换为代码的工具。感觉挺新奇的。于是有了些想法:编程语言->中间语言->自然语言。似乎必须经历这一个过程。所以人们一味的创建自
然语言到程序代码的强制转换，似乎有些勉强。之所以是编程语言->中间语言->自然语言而不是编程语言<-中间语言<-自然语言.是因为其实有很多自然语言连人类自己
的都很难识别。所以更别说机器了。所以机器能识别的语言应该是自然语言的子集，而不是全集。

从Testing Scenario(测试场景)->自动化测试，其实我认为这里还是单箭头。利用刚才的RSpec这个工具，似乎可以达到这个效果。RSpec做的事
情说的直白点就是从文档到软件是转换。千古难题呀！

DW2的CEO的一句话“without software, we are
nothing.”细细想来，感触很多。感觉自己应该有第二门手艺，一门完全脱离计算机还能养活自己的手艺。

CISCO的人很想把Network与Application融合到一起。然后说了一句话：“Network is always in the middle.”

听了一个创业人所讲的创业经历：

1.做产品还是做开发。（其实这两者是不一样的，很多人都会编码，但是不会写文档，不会做界面。）

2.让少量的人做大量的事。这是一个产品化的过程。也是一个开始盈利的过程。

3.知道自己擅长什么。这个很关键。不过入行才几年的人的确不知道自己擅长什么。

这个类的名字叫huffman Tree，但是不仅仅是生成huffman Tree，因为Huffman树的生成要使用优先队列，也就是堆。stl中其实有这个的实
现。但是我机器里的vs2005这个堆的使用有点小bug（估计是stl中使用的就是数组存储，而且数组一旦固定大小，就再也无法改变，其实这样实现失去了堆的某些特
性。 _ 所以我还是自己实现了一下 _
。顺便练习下。）。刚开始的时候
就采用int作为编码的存储单元。后来发现huffman是可变长编码。所以使用int作为编码单元就失去了huffman的特性。于是寻找bit数组。找到了bit
set这个stl类，却发现这个是不可变的。无语。只得自己实现一个可变大小的 _ bit vector _

。然后近乎重写了这个Huffman的编码和解码。不过也不是很难。在这之间又陆陆续续的发现了一系列的bug和编译错误。对以后的编程大有启发。

1. /* created by chico chen
2. *  date 2008/10/25
3. */
4. 5. 6. #ifndef HUFFMAN_TREE
5. #define HUFFMAN_TREE
6. #include “Heap.h”
7. #include “TreeNode.h”
8. #include “BinaryTree.h”
9. #include 
10. #include “…/…/ArithmeticTest/ArithmeticTest/BITVector.h”
11. using namespace std;
12. 15. // this class is used for the combin function in huffmanTree class.
13. class IntCombin
14. {
15. public :
16. static int Add( int i, int j)
17. {
18. return i+j;
19. }
20. };
21. 25. // this class for compare tree node
22. template < class T>
23. class TreeNodeCompare
24. {
25. public :
26. static bool Up(TreeNode* d1, TreeNode* d2)
27. {
28. return Lt(d1->getData(),d2->getData());
29. }
30. 35. static bool Eq(T& d1, T& d2)
31. {
32. if (d1 == d2)
33. return true ;
34. return false ;
35. }
36. 42. static bool Gt(T& d1, T& d2)
37. {
38. if (d1 > d2)
39. return true ;
40. return false ;
41. }
42. 49. static bool Lt(T& d1, T& d2)
43. {
44. if (d1 < d2)
45. return true ;
46. return false ;
47. }
48. };
49. 57. // this class is for storing huffman code.
50. // bits and the length of bits
51. class HuffmanCode
52. {
53. public :
54. BITVector bits;
55. int len;
56. HuffmanCode()
57. {
58. len = 0;
59. }
60. 69. HuffmanCode( const HuffmanCode & codes):bits(codes.bits)
61. {
62. len  = codes.len;
63. 73. }
64. 75. const HuffmanCode& operator=( const HuffmanCode & codes)
65. {
66. if ( this != &codes)
67. {
68. this ->len = codes.len;
69. this ->bits = codes.bits;
70. }
71. return * this ;
72. }
73. 85. ~HuffmanCode()
74. {
75. 88. }
76. };
77. 91. template < class T, class Cmp, class Combin>
78. class HuffmanTree: public BinaryTree
79. {
80. private :
81. // store the data, and sort it, then for building a huffman tree
82. Heap<TreeNode* ,Cmp> huffmanQueue;
83. 98. const unsigned int mask;
84. // the max number can be shifted, if it is unsigned int then it will be 32.
85. const int maxShiftNum;
86. 102. 103. TreeNode* initTree()
87. // init the huffman tree
88. {
89. TreeNode * combinNode = NULL;
90. T tempData;
91. while (! this ->huffmanQueue.IsEmpty())
92. {
93. // fetch two small data and generate a large data
94. TreeNode * node1 = this ->huffmanQueue.Top();
95. combinNode = node1;
96. this ->huffmanQueue.RemoveTop();
97. if (! this ->huffmanQueue.IsEmpty())
98. {
99. TreeNode * node2 = this ->huffmanQueue.Top();
100. this ->huffmanQueue.RemoveTop();
101. tempData =  Combin::Add(node1->getData(),node2->getData());
102. 120. 121. if (Cmp::Lt(node1->getData(),node2->getData()))
103. {
104. // here is comparing the data1 of node1 and the data2 of node2
105. //  Cmp:Lt means ‘<’ and Cmp:Gt means ‘>’
106. 126. combinNode = new TreeNode(tempData,node1,node2);
107. }
108. else
109. {
110. combinNode = new TreeNode(tempData,node2,node1);
111. }
112. this ->huffmanQueue.Insert(combinNode);
113. }
114. else
115. {
116. break ;
117. }
118. 139. }
119. return combinNode;
120. }
121. 143. 144. 145. // the final huffman code
122. map<T,HuffmanCode> huffmanTable;
123. 148. 149. void SelfEncode(TreeNode* subRoot,unsigned int bitcode, int num,map<T,HuffmanCode > &ht)
124. // encoding the data from a huffman tree.
125. // The left branch is 0, and the right branch is 1
126. {
127. 154. if (subRoot != NULL)
128. {
129. 157. if (subRoot->left == NULL && subRoot->right==NULL)
130. {
131. HuffmanCode hc;
132. hc.bits.SetInt(bitcode,0,maxShiftNum-num);
133. hc.len = maxShiftNum-num;
134. ht[subRoot->getData()] = hc;
135. return ;
136. }
137. else
138. {
139. if (num<=0)
140. {
141. throw “the huffman is too deep!” ;
142. }
143. 172. 173. SelfEncode(subRoot->left,bitcode,num-1,ht);
144. bitcode = bitcode | (0x80000000 >> (maxShiftNum-num));
145. SelfEncode(subRoot->right,bitcode,num-1,ht);
146. }
147. }
148. 179. 180. }
149. 182. 183. void DecodeFromTree(TreeNode* subRoot,BITVector& bits, int index, const int & len,vector& decode)
150. // decoding the code. use the code to search the data from the huffmanTree.
151. // here you can create you own map<code,data> deHuffmanTable.
152. // but I can not analyze the space the table will use,
153. // so I find the data by searching huffman tree
154. {
155. if (index == len)
156. {
157. if (subRoot->getLeft()==NULL && subRoot->getRight() == NULL)
158. {
159. 194. decode.push_back(subRoot->getData());
160. return ;
161. }
162. throw “code length is not match the bits length. Huffman Tree construct error.” ;
163. }
164. if (subRoot == NULL)
165. {
166. throw “decode error!” ;
167. 203. }
168. else if (subRoot->getLeft() == NULL && subRoot->getRight() == NULL)
169. {
170. 207. decode.push_back(subRoot->getData());
171. return DecodeFromTree( this ->root,bits,index,len,decode);
172. }
173. 211. if (bits.Get(index) == 0)
174. {
175. return DecodeFromTree(subRoot->getLeft(),bits,index+1,len,decode);
176. }
177. else if (bits.Get(index)==1)
178. {
179. 218. return DecodeFromTree(subRoot->getRight(),bits,index+1,len,decode);
180. }
181. else
182. {
183. throw “code error!” ;
184. }
185. 225. 226. }
186. 228. 229. unsigned int FindCodeFromTable(T& data)
187. // find the data code from huffman table
188. // may be not efficient.
189. {
190. return this ->huffmanTable[data];
191. }
192. 236. public :
193. 238. HuffmanTree(T t[], int n):
194. BinaryTree(),mask(0x80000000),maxShiftNum( sizeof (unsigned int )*8)
195. // the array t type is T, and the number is n
196. {
197. if (n == 0)
198. return ;
199. TreeNode* node;
200. for ( int i = 0; i < n; i++)
201. {
202. node = new TreeNode(t[i]);
203. this ->huffmanQueue.Insert(node);
204. }
205. this ->root = initTree();
206. }
207. 253. ~HuffmanTree()
208. {
209. // destroy
210. 257. }
211. 259. 260. void SelfEncode()
212. // convert the huffmanTree into huffmanTable
213. // unsigned int code is 32 bits, so the huffman tree has only less than 33 layer.
214. {
215. string s= “” ;
216. 266. SelfEncode( this ->root,0,maxShiftNum, this ->huffmanTable);
217. 268. }
218. 270. 271. 272. void Decode(HuffmanCode& huffmanCode,vector& decode)
219. // use bit to find the data node.
220. {
221. 276. return DecodeFromTree( this ->root,huffmanCode.bits,0,huffmanCode.len,decode);
222. 278. }
223. 280. HuffmanCode Encode(T info[], int n)
224. // n is size
225. {
226. HuffmanCode hc;
227. 285. for ( int i = 0; i < n; i++)
228. {
229. 288. hc.bits.SetBitVector(((HuffmanCode) this ->huffmanTable[info[i]]).bits,hc.len,((HuffmanCode) this ->huffmanTable[info[i]]).len);
230. hc.len +=((HuffmanCode) this ->huffmanTable[info[i]]).len;
231. }
232. 292. return hc;
233. }
234. 295. 296. void PrintHuffmanTable()
235. // print the huffman table
236. // print the pair data<->code
237. {
238. int len = this ->huffmanTable.size();
239. cout << “i/tdata/tcode/n” ;
240. int count = 0;
241. map<T,HuffmanCode>::iterator i= this ->huffmanTable.begin();
242. for (; i != this ->huffmanTable.end(); i++)
243. {
244. cout << count++<< “/t” <<(*i).first<< “/t” ;
245. (*i).second.bits.PrintfZeroOne(0,(*i).second.len);
246. cout<<endl;
247. }
248. 311. }
249. 313. };
250. 315. 316. #endif

这个类设计方面还有些不足之处。比如encode方法

测试一下：

1. int a[10] = {12,224,33,32,1,91,35,34,36,291};
2. HuffmanTree< int ,TreeNodeCompare< int >,IntCombin> ht(a,10);
3. ht.SelfEncode();
4. ht.PrintHuffmanTable();
5. ht.printTree();
6. cout << endl;
7. int info[] = {33,34,33};
8. HuffmanCode hc = ht.Encode(info,3);
9. hc.bits.PrintfZeroOne(0,hc.len);
10. vector< int > code;
11. ht.Decode(hc,code);
12. ** for ** ( int i = 0; i != code.size();i++)
13. {
14. 15. cout<<code[i]<<endl;
15. }
16. 18. ** return ** 0;

其实c++里有bitset这个类，但是bitset使用时必须给定大小。例如

bitset<8> c;//这里必须在编码里写死，不能使用变量替代

c = 234;

我主要是用这个东西来存储可变长的huffman编码。所以这个类对我根本不能用。除非开始就给一个足够大的bitset。

所以我创建里一个可变长的bit vector用于存放Huffman编码。

在这里内部使用的是__int64,64位。当然根据实际需要可以将这个做为模板传入，不过现在还没有这样编码。

1. /* created by chico chen
2. *  date 2008/10/25
3. */
4. #ifndef BIT_VECTOR
5. #define BIT_VECTOR
6. #include 
7. using namespace std;
8. 9. 10. class BITVector
9. {
10. private :
11. __int64 * bitarray;
12. const int bits;
13. const unsigned __int64 mask ;
14. int size;
15. void SetOne( int index); // x is 0
16. void SetZero( int index); // x is 1
17. void Larger();
18. 21. public :
19. BITVector( void );
20. void Set( int index, int x); // x is 0 or 1
21. int Get( int index);
22. int Size();
23. void SetInt(unsigned int integer, int start, int len);
24. void PrintfZeroOne( int start , int len); // print the unsigned it as 0 or 1
25. void SetBitVector(BITVector & c, int start, int len);
26. const BITVector& operator=( const BITVector& bitVector);
27. explicit BITVector( const BITVector & bitVector);
28. 32. public :
29. ~BITVector( void );
30. };
31. #endif

然后是bitVector.cpp文件

1. /* created by chico chen
2. *  date 2008/10/25
3. */
4. #include “StdAfx.h”
5. #include “BITVector.h”
6. 7. BITVector::BITVector( void ):mask(0x8000000000000000),bits( sizeof ( __int64 )*8)
7. {
8. bitarray = new __int64 [1];
9. memset(bitarray,0, sizeof ( __int64 ));
10. size = 1;
11. }
12. 14. BITVector::~BITVector( void )
13. {
14. size = 0;
15. delete [] bitarray;
16. }
17. 20. void BITVector::Set( int index, int x)
18. {
19. if (x == 0)
20. {
21. return SetZero(index);
22. }
23. else
24. {
25. return SetOne(index);
26. }
27. }
28. 32. void BITVector::SetZero( int index)
29. {
30. int innIndex = index/bits;
31. int bitPos = index & (bits-1); // innIndex % 8
32. if ( innIndex < size)
33. {
34. // vector maybe has enough space to store this .
35. this ->bitarray[innIndex] = this ->bitarray[innIndex] & ~(mask >> bitPos);
36. }
37. else if (innIndex == size)
38. {
39. // should larger the size of bitarray
40. // and innIndex must be the first bit of last char
41. 46. if (bitPos == 0)
42. {
43. // correct
44. this ->Larger();
45. this ->bitarray[innIndex] = this ->bitarray[innIndex] & ~(mask >> bitPos);
46. 52. }
47. else
48. {
49. // error
50. 57. }
51. }
52. else
53. {
54. // there may be something error, or some code missing
55. 63. }
56. }
57. 66. 67. void BITVector::Larger()
58. {
59. __int64 * tempArray = new __int64 [size];
60. memcpy(tempArray, this ->bitarray, sizeof ( __int64 )*size);
61. delete [] this ->bitarray;
62. 73. this ->bitarray = new __int64 [size*2]; // may be error
63. memset(bitarray,0, sizeof ( __int64 )size2);
64. memcpy( this ->bitarray,tempArray, sizeof ( __int64 )*size);
65. size = size*2;
66. delete [] tempArray;
67. 79. 80. }
68. 82. void BITVector::SetOne( int index)
69. {
70. int innIndex = index/bits; // you can use >>(bits-1)
71. int bitPos = index % bits; // innIndex & (bits-1)
72. if ( innIndex < size)
73. {
74. // vector maybe has enough space to store this .
75. this ->bitarray[innIndex] = this ->bitarray[innIndex] | (mask >> bitPos);
76. }
77. else if (innIndex == size)
78. {
79. // should larger the size of bitarray
80. // and innIndex must be the first bit of last char
81. 96. if (bitPos == 0)
82. {
83. // correct
84. this ->Larger();
85. this ->bitarray[innIndex] = this ->bitarray[innIndex] | (mask >> bitPos);
86. 102. }
87. else
88. {
89. // error
90. 107. }
91. }
92. else
93. {
94. // there may be something error, or some code missing
95. 113. }
96. 115. }
97. 117. int BITVector::Get( int index)
98. {
99. if (index < size*bits)
100. {
101. int position = index & (bits-1); // % bits
102. int innIndex = index/bits;
103. __int64 i = this ->bitarray[innIndex] & (mask >> position);
104. if (i == 0)
105. {
106. return 0;
107. }
108. else
109. {
110. return 1;
111. }
112. }
113. throw “access out of the array” ;
114. }
115. 136. int BITVector::Size()
116. {
117. return size*bits;
118. }
119. 141. // int integer is 0x01010111
120. // start is the start position of bitvector, and start starts zero
121. // len is length of the number of bits you want set into bit array
122. void BITVector::SetInt(unsigned int integer, int start, int len)
123. {
124. int finalPos = start + len;
125. int i=start;
126. int j = 0;
127. int temp = 0;
128. for (;i < finalPos; i++,j++)
129. {
130. temp = integer & (0x80000000 >> j);
131. this ->Set(i,temp);
132. }
133. }
134. 157. 158. void BITVector::PrintfZeroOne( int start, int len)
135. {
136. int finalPos = start+len;
137. int temp = 0;
138. for ( int i = start; i < finalPos; i++)
139. {
140. printf( “%d” , this ->Get(i));
141. }
142. }
143. 168. // start is where to insert bit vector c
144. // len is the length of bits inserted
145. // “start” is of this, and “len” is of c;
146. void BITVector::SetBitVector(BITVector & c, int start, int len)
147. {
148. 174. for ( int i = 0; i < len; i++)
149. {
150. this ->Set(start+i,c.Get(i));
151. }
152. 179. }
153. 181. // copy construct
154. BITVector::BITVector( const BITVector & bitVector):mask(0x8000000000000000),bits( sizeof ( __int64 )*8)
155. {
156. this ->size = bitVector.size;
157. this ->bitarray = new __int64 [ this ->size];
158. memcpy( this ->bitarray,bitVector.bitarray, sizeof ( __int64 )*bitVector.size);
159. }
160. 189. const BITVector& BITVector::operator=( const BITVector& bitVector)
161. {
162. if ( this != &bitVector)
163. {
164. this ->size = bitVector.size;
165. delete [] this ->bitarray;
166. this ->bitarray = new __int64 [ this ->size];
167. memcpy( this ->bitarray,bitVector.bitarray, sizeof ( __int64 )* this ->size);
168. }
169. return * this ;
170. }

因为vs2005中c++的Heap构造 _ 有些问题 _
，所以才重写了heap类。

不知道vs2008中这个是不是个bug。

1. /* created by chico chen
2. *  date 2008/10/25
3. */
4. template< class T, class Cmp>
5. class Heap
6. {
7. private :
8. vector heap;
9. void ShiftDown( int index)
10. {
11. while (!IsLeaf(index))
12. {
13. int l = Lchild(index);
14. int r = Rchild(index);
15. if (r != -1)
16. {
17. if (Cmp::Up(heap[r],heap[l]))
18. {
19. // put the up node to the left
20. swap(heap[l],heap[r]);
21. }
22. }
23. if (Cmp::Up(heap[l],heap[index]))
24. {
25. // up the left child
26. swap(heap[l],heap[index]);
27. index = l;
28. }
29. else
30. {
31. break ;
32. }
33. }
34. 35. }
35. void ShiftUp( int index)
36. {
37. int parent = -1;
38. while (index != 0)
39. {
40. parent = Parent(index);
41. if (Cmp::Up(heap[index],heap[parent]))
42. {
43. swap(heap[index],heap[parent]);
44. index = parent;
45. }
46. else
47. {
48. break ;
49. }
50. }
51. 53. }
52. void ReHeapAll()
53. {
54. for ( int i=Parent(heap.size()-1); i>= 0; i–)
55. {
56. ShiftDown(i);
57. }
58. }
59. void ReHeapOne( int index)
60. // set one prior and re-position the index node
61. {
62. T data = heap[index];
63. ShiftDown(index);
64. if (Cmp::Eq(data,heap[index]))
65. {
66. ShiftUp(index);
67. }
68. }
69. int Parent( int index)
70. // parent node of the index node
71. {
72. return (index-1)/2;
73. }
74. int Lchild( int index)
75. // Left child of the index node
76. {
77. if (!IsLeaf(index))
78. return index*2+1;
79. return -1;
80. }
81. int Rchild( int index)
82. // Right child of the index node
83. {
84. if (!IsLeaf(index))
85. {
86. int r= index*2+2;
87. if (r<heap.size())
88. return r;
89. }
90. return -1;
91. }
92. 95. int IsLeaf( int index)
93. {
94. assert(index < heap.size());
95. if (heap.size() == 1)
96. return true ;
97. int lastNode = Parent(heap.size()-1);
98. return lastNode < index;
99. }
100. 104. int FindData(T& data)
101. {
102. int len = heap.size();
103. for ( int i = 0; i < len; i++)
104. {
105. if (Cmp::Eq(data,heap[i]))
106. {
107. return i;
108. }
109. }
110. return -1; // can not find the data
111. }
112. 117. void printTree( int index, int count)
113. {
114. if (index < heap.size() && index >=0)
115. {
116. 122. printTree(Rchild(index),count+4);
117. for ( int i = 0; i < count; i++)
118. {
119. cout << " " ;
120. }
121. cout <<heap[index]<<endl;
122. printTree(Lchild(index),count+4);
123. }
124. }
125. public :
126. Heap()
127. {
128. heap = vector();
129. }
130. ~Heap()
131. {
132. // heap destroyed
133. }
134. bool IsEmpty()
135. {
136. return heap.size() == 0;
137. }
138. 145. 146. 147. void Insert(T& data)
139. {
140. heap.push_back(data);
141. ShiftUp(heap.size()-1);
142. }
143. void Delete( int index)
144. {
145. int last = heap.size()-1;
146. if (index>=0 && index <= last)
147. {
148. 158. swap(heap[index],heap[last]);
149. heap.pop_back();
150. ReHeapOne(index);
151. }
152. }
153. void Delete(T& data)
154. {
155. int index = FindData(data);
156. if (index != -1)
157. Delete(index);
158. }
159. 170. 171. void RemoveTop()
160. {
161. 174. if (!IsEmpty()&&heap.size()>1)
162. {
163. swap(heap[0],heap[heap.size()-1]);
164. heap.pop_back();
165. ShiftDown(0);
166. }
167. else if (heap.size() == 1)
168. {
169. heap.pop_back();
170. }
171. 185. }
172. T& Top()
173. {
174. return heap[0];
175. }
176. 191. void Print()
177. {
178. printTree(0,1);
179. }
180. 196. 197. 198. };