帐前卒专栏

最近帮朋友翻译书籍。朋友最后整合，我只是翻译其中一个章节。因为根本没有看前面的文章，所以难免字词把握不准。当然比Google翻译和金山翻译都强一些。但是难免
还能看出翻译的痕迹。因为时间紧迫，所以只用了2个小时不到的时间就完成了任务。

后来接触到翻译的各种内幕，发现有很多本科生为了生计也接翻译的任务。辛苦而快速的翻译。当然这里不是说本科生翻译的就差。但是我认为看他们翻译的版本还不如自己看英
文版的舒服些。过去我还没有这种思想，现在自己翻译过书之后，发现还是英文版的好。因为如果翻译者像我这样为了完成任务草草的翻译，可能根本没有领悟到每一句话的真正
含义，很有可能错误翻译。计算机的专业文章很多还要看懂代码后做翻译，与其看别人的二义性翻译还不如自己理解下英文原版好。

另外也发现一个问题，很多专业词汇根本不知道中文对应的是什么。但是英文还是好理解的。所以很有可能翻译者会生造出一个词汇。当然看翻译版看久了就会知道这两个中文词
竟然是一个英文词…所以何苦呢？开始看英文不就好了？

google 将7年前的索引拿了出来，现在大家可以输入各种关键字看看过去的互联网世界。

不过google也有没有爬到的地方。不过Google的这个活动还是蛮新奇的。

Hey!everybody, we are looking back the history!

使用GOOGLE 2001的索引，发现7年前的网络是啥样的，来个今昔大对比，对比那可是真是相当惊人呐。
_ http://www.google.co m/search2001.html _

主要是关于树立自信的，其实我也知道很多学生是调剂到湖大软件学院的。这点和我有很大的不同。因为我第一志愿就是软件学院。天知道我当时是怎么想的。估计是感觉计科太
接近硬件了吧。

不过不管怎样，既然进来了就要好好学。否则耽误4年，太不值了。

_ ppt下载地址 _

已经过去半年了，将自己的东西整理整理都贴到网上来吧。

_ 实习总结下载 _

csdn上传文件还是很方便的。

这是自己的毕业设计论文。

其实算法感觉上也没有什么高深的，只是至今还没有用那个算法而已。

前一个算法是导师想到的，后一个算法是自己看了大量的论文发现还为提出的。

这篇论文估计已经存在在湖大的档案室中了。

本来想投稿到某个杂志发表一下。但是自己迟迟未整理文章，没有将文章缩减至7000字一下。所以发表的概率也不大。

而且还要交版面费。索性发表到csdn，供各位做电子地图的人参考一下。

电子地图的前台代码即将开源。但是写的不好，大家也不要有太高的期望。我感觉那javascript运行的太慢了。

也可能是传输和画图的地方没有设计好。另外也使用的开源的javascript画图包。

后台代码的算法部分开源。因为还有一些是阿咪写的。

暂且就写这么多吧。

_ 先把论文挂上。 _
这里资源分是0，所以只要是注册用户都可以下载。

心存叵测之人勿将此文当作自己的毕设论文。因为我会写大量的关键词来让Google索引的。(^__) 嘻嘻……

在暑假里为One编程组设计的logo

里面有One编程组组建宗旨：

Open Share

然后环绕一圈的就是One这个词了

意为统一整体。

编程组成员以后可以使用这个logo，扩大One编程组的影响。呵呵。

![](http://p.blog.csdn.net/images/p_blog_csdn_net/cctt_1/EntryImages/20081006/
OneGroup.png)

Google做图片它也防了一手。

在不同的图层水印不知道是否相同，不过这个图层的水印比较清晰。黑框中的便是。但是缩放后就了无痕迹。

![google 水印图片](http://p.blog.csdn.net/images/p_blog_csdn_net/cctt_1/EntryImage
s/20081004/google.JPG)

这个是美国的硅谷。不远处就是Google的前沿阵地。据说那个地方是用来挖微软墙角用的。

[ ](http://p.blog.csdn.net/images/p_blog_csdn_net/cctt_1/EntryImages/20081004/
google.JPG) [ ](http://p.blog.csdn.net/images/p_blog_csdn_net/cctt_1/EntryImag
es/20081004/google.JPG)

1.首先设置ubuntu中的网络配置,使用ifconfig查看

2.这个已经帮我配好了。但是怎么都ping不通网关。使用network-admin命令调出网络管理界面

3.输入密码unlock这个界面。然后选择wired connection。发现也是使用的dhcp。

4.现在仍然没有找到问题。在网络上找了很久依旧没有发现什么启示。无奈只得乱点，在wired connection的property选项卡选中了enable
roaming mode。

5.奇迹呀。竟然可以ping通网关了。

6.然后去掉enable roaming mode，竟然也是可以ping通的。

这个做的实在是太高科技了。

不过这个暂时好像只适合我的机器。不知道别人的机器有没有这个问题。

ubuntu 8.0

VMware 6.0

当你的一个类与某一个类的时候，只需要将你这个类中特有的变量析构就可以了

你不要在关心继承类中的变量。

上午编码

SplayTree继承了BinaryTree

其中没有任何自己特有的成员变量。

然后在~SplayTree()中写到clearSubTree(this->head);

其实这一句已经在~BinaryTree()中写过了。

结果就抛了个exception。

于是刚刚考虑下virtual虚构函数。发现自己没有使用到多态，只是想把代码重用，也就没有再使用virtual的必要。

或许以后在考虑下这几个树之间的错综复杂的关系。

现在把~SplayTree()中的内容清空。

一切恢复正常。

伸展树用于查询结果的概率非平均情况，即起初假设某些要查询的信息偏多，有些信息几乎无人问津。对于平均访问概率来说，使用SplayTree实现并不是一个明智的选
择。

可能会用到此数据结构的程序：词典或者多维搜索树，还有连接/切除树（link/cut tree）（这个树是用于网络优化问题包括最大流和最小代价）

1. /*
2. * create by chico chen
3. * date: 2008/10/02
4. */
5. template < class T>
6. class SplayTree: public BinaryTree
7. {
8. 9. public :
9. explicit SplayTree(T& data):BinaryTree(data)
10. {
11. 13. }
12. 15. explicit SplayTree(TreeNode* root):BinaryTree(root)
13. {
14. 18. }
15. ~SplayTree()
16. {
17. 22. }
18. public :
19. 25. void insertNode(T& data)
20. {
21. 28. if (NULL == this ->head)
22. {
23. this ->head = new TreeNode(data);
24. return ;
25. }
26. 34. splay( this ->head,data);
27. if ( this ->head->data > data)
28. {
29. //     A     B                 A
30. //            / /     ->         / /
31. //         C   D             C   B
32. //                                /
33. //                                 D
34. TreeNode* node = new TreeNode(data);
35. node->left = this ->head->left ;
36. node->right = this ->head;
37. this ->head->left = NULL;
38. this ->head = node;
39. }
40. else if ( this ->head->data < data)
41. {
42. //     A     B                 A
43. //            / /     ->         / /
44. //         C   D             B   D
45. //                              /
46. //                            C
47. TreeNode* node = new TreeNode(data);
48. node->right = this ->head->right;
49. node->left = this ->head;
50. this ->head->right = NULL;
51. this ->head = node;
52. 61. }
53. else
54. {
55. // insert the same key
56. // throw exception
57. throw “the same key” ;
58. }
59. }
60. 70. // use the data as key to splay the tree
61. // then we can get the structures of the tree like the following:
62. //     (1)  A             (2)   A
63. //              /                    / /
64. //               B               C   B
65. // the difference between the two structures is whether the root has left child
66. // In case (1), we can simpliy make the root right child instead the root.
67. // In case (2), we should splay the root left subtree and then it will be
68. // changed like case (1), and we make the splayed left subtree root instead
69. // the root.
70. void deleteNode(T& data)
71. {
72. 83. if (NULL == this ->head)
73. {
74. return ;
75. }
76. splay( this ->head, data);
77. if ( this ->head->data != data)
78. {
79. // not found the key to delete
80. return ;
81. }
82. TreeNode* newRoot;
83. if (NULL == this ->head->left)
84. {
85. newRoot = this ->head->right;
86. }
87. else
88. {
89. newRoot = this ->head->left;
90. splay(newRoot,data);
91. newRoot->right = this ->head->right;
92. }
93. delete this ->head;
94. this ->head = newRoot;
95. 107. }
96. 109. 110. TreeNode* searchNode(T& data)
97. {
98. if (NULL == this ->head)
99. {
100. return NULL;
101. }
102. splay( this ->head, data);
103. if ( this ->head->data == data)
104. {
105. return this ->head;
106. }
107. return NULL;
108. }
109. 124. private :
110. // use top-down splay method,
111. 127. // you should make the suitable final step
112. // according to the situation, such as “insert”, “delete”, “search”.
113. // And what’s the top-down method?
114. // now we should add LeftMaxRoot as L and RightMinRoot as R
115. // 1. L  A  R         2. L  A  R        3. L   A   R
116. //         /                        /                      /
117. //        B                     B                     B
118. //                               /                          /
119. //                              C                          C
120. //
121. // 1.->L  B  R      2.->L  C   R        3.L   C    R
122. //        /                     /                          /      /
123. //     A                    B                         B    A
124. //                             /
125. //                              A
126. // but in case 3. we can simplified case 3 rotate as
127. // 3. L   B      R
128. //            /      /
129. //            C  A
130. // and we must integrate the LeftMaxRoot and RightMinRoot together,
131. // then we have final step to do this. And L is left tree, and R is right tree.
132. // L     A     R               A
133. //         / /         ->         /   /
134. //       B   C                L     R
135. //                                 /   /
136. //                                B C
137. void splay(TreeNode* &subRoot,T& data)
138. {
139. if (NULL == subRoot)
140. {
141. return ;
142. }
143. TreeNode* leftRoot;
144. TreeNode* rightRoot;
145. // here some code use static member, if you promise you have sync-control
146. // or you don’t use this code in thread or process, you could choose static
147. // member to accelerate your program.
148. // It means the following code is thread-safe.
149. TreeNode head(data);
150. leftRoot = rightRoot = &head;
151. while ( true )
152. {
153. 170. if (data < subRoot->data)
154. {
155. if (NULL == subRoot->left)
156. {
157. break ;
158. }
159. else if (data < subRoot->left->data)
160. {
161. // Left rotate
162. TreeNode* tempLeft = subRoot->left;
163. subRoot->left = tempLeft->right;
164. tempLeft->right = subRoot;
165. subRoot = tempLeft;
166. 184. }
167. else
168. {
169. // do nothing
170. }
171. // split the tree with right root
172. if (NULL == subRoot->left)
173. break ;
174. rightRoot->left = subRoot;
175. rightRoot = subRoot;
176. subRoot = subRoot->left ;
177. 196. }
178. else if (data > subRoot->data)
179. {
180. if (NULL == subRoot->right)
181. {
182. // need not to rotate
183. break ;
184. }
185. else if (data > subRoot->right->data)
186. {
187. // right rotate
188. TreeNode* tempRight = subRoot->right;
189. subRoot->right = tempRight->left;
190. tempRight->left = subRoot;
191. subRoot = tempRight;
192. }
193. else
194. {
195. // do nothing
196. }
197. // split the tree by left root
198. if (NULL == subRoot->right)
199. break ;
200. leftRoot->right = subRoot;
201. leftRoot = subRoot;
202. 222. subRoot = subRoot->right;
203. }
204. else
205. {
206. // the same key
207. break ;
208. }
209. 230. }
210. 232. // the final step
211. // we have find the last node, ant then we should
212. // integrate the left root, the right root and the root into One tree.
213. // head.right is left root
214. // head.left is right root
215. leftRoot->right = subRoot->left;
216. rightRoot->left = subRoot->right;
217. subRoot->left = head.right;
218. subRoot->right = head.left;
219. 242. 243. }
220. 245. 246. 247. 248. };

发现CSDN的代码编辑器还是有些问题，空格处理不好，导致我注释中的树形错乱了…

不过没有大关系，应该抓起旁边的纸边看边画就能明白。

在网上找splayTree的源码学习，发现凭自己的实力还真的看不懂…

幸好在家里翻到了古老的数据结构教材。这才明白。

至于不使用添加父节点或者采用递归栈等方式的原因在于：空间消耗太大。

另外递归栈也不好调试

这个top-down splay的方法消耗空间为O(1)，带来的效果却和添加父节点类似，没有使用递归的方法。

至于具体的方法，在代码的注释里。

这里为了编代码方便就没有将treeNode 类中的成员变量私有化。

另外的BinaryTree的代码在 _ 以前的blog中 _
。

这个splayTree还是较为完整的，至少比Apache中的splayTree完整些。现在我依旧不明白为什么Apache中的内存管理使用的是splayTre
e,而且splayTree还没有delete函数。难道内存管理的东西没有必要删除吗？

思考中…