帐前卒专栏

个人项目总结

Posted on 2008-09-30 Edited on 2023-10-05 Word count in article: 3.6k Reading time ≈ 3 mins.

想想大学来做的项目也做了很多个了。。其中也包括各类课程设计

1.CAI（c语言教学系统）使用C语言开发。功能图形化的界面指导C语言教学。自己认为失败。但是学到C的图形编程
。（成员：剑哥，老万，少博）开发环境：TurboC2.0。职位：组长。自己完成的任务：c教学图形界面。

2.学生机房监控系统（MFC开发）。功能监控各个学生的上机情况，并可以关闭学生的某个进程，锁定或者学生机。失败。
学到团队培训，团队管理的技巧，如何采用其他解决方案解决棘手问题。
（成员：剑哥，阿咪，波波，小李子，小强）开发环境：VC6.0。职位：组长。自己完成的任务：实现MD5c++版，需求和程序大体框架图。

3.多对多聊天系统（java开发）。失败。功能类似于QQ，可以进行公聊私聊。最后只是实现了公聊，没有实现私聊。
学到java多线程和socket编程的一些概念。（成员：晔，武大姐，阿咪）开发环境：eclipse3.0,
jdk1.4。职位：组长。自己完成的任务：公聊模块。

4.实验室管理系统（.net开发）。半失败。功能？？只是将原有的系统更加完善，但我现在仍然不知道那东西扔到什么地方了。学到如何快速的学习一门语言。（
成员：中华兄，小刚，疯子，汤亮学长）开发环境：vs2003。职位：组员。自己的任务：找bug和Sql语句的改动。

5.个性化学习系统（J2EE）。失败。功能可以管理课程，可以对学生进行管理，对学生的选课进行管理。将原系统从Oracle迁移mySql，从WebLogic迁
移至JBoss。学到如何收集资料自己学习，如何利用团队成员的资源。（成员：汤亮学长，浩哥，中华兄，小刚，疯子）开发环境：JBoss4,eclipse
3.0,Jbuilder9,WebLogic8,Oracle9i,mySql,myEclipse,Rational
Rose2003。职位：组员。自己完成的任务：平台迁移工作，用户管理部分的bug修复和程序框架UML图

6.湘钢设备管理系统(.net)。半失败。功能可以对湘钢备件台帐储备系统自动化。
学到如何增强团队凝聚力，团队间如何协作,如何制作模板，如何讲课，如何与人沟通，如何请求别人帮助
。（创新班全体。本组成员：波波，疯子，yaya，小李子，剑哥，中华兄，小刚，广胜，老万）开发环境： vs2005 Team System
，vs2005,Rational Rose2003.职位：组员。自己实现的模块：台帐查询删除回收页面和用户视图订制。

7.咨询投诉系统（.net）.半失败。功能ms是处理投诉。关于学到如何分工，如何独挡一面。有时不能因为组员的不积极而放弃整个项目。（
成员：华仔，菲菲，小可，雪山）开发环境：.net2005,Rational Rose2003.职位：组长。自己实现的部分：页面层和业务逻辑层

8.光盘管理系统(.net).半失败。功能：光盘管理，会员管理。学到如何软件体系结构复用，如何快速的开发软件。
开发环境：.net2005,Rational rose2003.自己完成

9.档案管理系统（J2EE）。成功。功能就是管理档案、管理成员、审批流程。学到如何使团队高效的开发软件，如何采取措施来控制软件进度，如何协调成员。（
成员：兴隆，波～，军～，帅子，睿）开发环境：tomcat5,eclipse3.1,myeclipse,mysql.职位：组长。自己的任务：用户管理非页面的整
个模块，测试文档和测试用例。

10.动态交通网络1.0（MFC）.成功。学到如何在线交流思想，如何在没有代码管理的情况下完成项目，如何配合成员，如何表达自己的想法。
（成员：红亮，阿咪）开发环境：vs2005.职位：无。自己的模块：数据结构层

11.人脸识别系统（Matlab）.正在… 学到如何独立的完成项目，如何通过别人的经验来快速的完成任务,如何写学术报告。（
成员：锦哥）开发环境:MatlabR2006b。自己的任务：除去最后论文剩下的所有工作。

12.Mini数据库管理系统.成功。这个项目后成为下一届以至以后若干届的教学实例项目。
功能：实现数据库表的创建，删除，更新，数据的增，删，查，改，支持表的主键外键，保证数据一致性。采用索引提高查询效率。
学习到如何结对编程，运用快速开发迭代。如何减少风险。如何发挥每一个成员的特长。如何在最短时间获得最大"收益" 这是迄今为止自己领导的最为成功的一个项目。小
宁哥说要推广到北大去。呵呵，如果真是这样，我就出名了。（成员：军~，福勇，圆圆）开发环境：VS2005,rationalRose
2003.自己的任务：数据结构层和核心层，以及界面层的若干行代码。

13.VisualDiff图片自动对比系统(C#，javascript)。成功。功能：差异图片人工对比后当作bug上传到Product
Studio。运用在Taipan项目测试阶段。支持图像部分掩盖和图像版本的历史记录。学会如何在未知的领域独立完成任务。
这是当微软实习生时完成的项目。这个项目导师给我5个月，后来1个月完成了。令导师吃惊不已，由于这个原因获得微软FTE面试机会。开发环境vs2005。

14.PSSP同步工具(C#)。成功。功能：ProductStudio到SharePoint上的内容同步工具。学会如何看微软文档以及别人的API文档。
开发环境vs2005。自己完成。

15.自动化压力测试工具(C#,dos
script).成功。功能：运用在微软Taipan项目发布测试阶段。产生大量用户，自动执行程序主要路径，用log记录这些用户的活动。
学会如何自己找任务，如何在别人任务繁忙无法全局考虑的时候，站出来指出团队还有啥事没有做。开发环境：VS2005。自己完成。

16.公交车查询系统web版(C#,javascript)。成功/不成功。功能：类似于动态交通网络1.0，但是迁移到web平台。
学会如何写大规模javascript代码。如何对比结果。如何查阅大量文献提出自己的想法。这个系统的 javascript代码几乎是我崩溃。幸好全是我写
的。成功是因为毕业论文因此得优。不成功是因为自己认为这个系统的构建公交车网络的页面无法容纳大量数据。（成员：阿咪）职务：无。自己的任务：自己的论文写作，ja
vascript页面层代码的开发，公交选路算法的实现，算法的对比。

17.数字签名工具(c++)。成功。功能：防止学生伪造分数，要求改分。学到如何考虑自己身边的小事，用程序改善自己的生活学习工作状态。
用于我当数据结构课程助教时期。这个不能称上项目应该叫做程序。因为代码量在千行以下，但是这个工具非常实用。所以这里提及。自我完成。

18.计算器工具(c++)，其实微软自带了计算器，但是每按一个数就要再按一次运算符。我认为这是失败的一次迁移。因为算式较长，我很难记得自己按到那个地方了。所
以实现了可以计算字符串算式的计算器。当然google的文本框也可以计算字符串算式。但是我和它的相比较，发现精度比它稍高些。不过怎么说也只是个计算器，用于偶尔
无聊的时候炫耀一下。功能用于计算字符串算式。

19.分类器（java）.成功。功能：用于网页中的文本分类。可以自动的判断类别。使用的是搜狗的新闻库。bayes正确率高达83%~85%左右，另外还有svm
分类（可惜大规模的时候最多达到30%），knn分类（支持多类）。界面华丽适合自娱自乐。学会看别人的代码（类似于看完后，全部重写）。
成功是因为这个项目提前做完，而且分类效果也不错，另外结交了不错的朋友。（成员：振华，牛mm）职务：组长。这个项目的缺点在于没有合理的架构的时候就提前动工
。所以最后的整合至少花掉了9*3个人时。我从下午一直整合到凌晨。痛不欲生，下次再做项目，谁要敢在没有架构的时候就编代码，一定饶不了他！

20.中文分词(python).成功。功能：将一篇文章中的句子进行分词。使用的是人民日报词库。最后分词中未登录词处理使用的是相同词性词合并原则。因为使用这一
原则使得最后的分词数大大减少。最后发现，其实动宾短语，动名词短语等还可以再细处理。分词采用的是FMM和一元非统计nbest算法进行粗分。后采用二元模型得到最
好的结果。然后使用此结果在对词性进行标注。最后根据词性再合并分词。发现python确实好用。
成功是因为这个项目在短短的不到一周的时间内搞定。而且效果不错。分词正确率80%以上，词性标注正确率和北大的分词系统不相上下。（成员:牛mm）.这个项目的
缺点在于最后使用一个python文件。另外也没有很好的分词和标注的标准答案。所以只能根据北大的分词来统计最后的结果。这个项目因为较小，而且属于摸着石头过河。
所以没有进行架构。的确不符合第19个项目得出的结论。并且因为牛mm的缘故，所以不能计入一般的软件工程方法论。

Explicit C++ 关键词

Posted on 2008-09-30 Edited on 2023-10-05 Word count in article: 665 Reading time ≈ 1 mins.

近来看到有书上的构造函数上写有explicit的关键词，出于好奇查个究竟，why？

原因很简单：

当构造函数的参数只有一个的时候，编译器会默认将

Type obj=0转换为Type obj(0)

或者obj = Type(0)

当然这还不局限于整数等情况

错误例子1：

class MyClass

{

MyClass();//这个是必须的

MyClass (int a);

};

在其他函数中这样调用

{

MyClass a; //如果没有默认构造函数这里就会出错

int ac = 3;

a = 4;//这里想写ac=4

}

那么这里就会有问题，因为编译器隐式转换为a = MyClass(4);记住这里的=可是基于bit的赋值，也是编译器默认提供的

当然如果你有写operator =()这个函数，那就另当别论。

错误例子2：

class MyClass

{

MyClass (int a);

};

其他函数里这样调用

{

MyClass a =4;//这里隐式转换为MyClass a(4)

}

所以很容易照成错误。而且这个错误不是编译错误，而是运行时可能的bug。

所以为了避免让大家犯错误，我们只有小心的设计自己的类

class MyClass

{

explicit MyClass (int a);

};

这样如果程序中再调用MyClass a =4;这样语句，程序就会报编译错误。

其实我们写程序不光为了让别人看懂，程序运行正确，还要想方设法的让大家少犯错误。

当然如果你的构造函数必须多于一个参数，其实就没有必要用explicit关键字了。

explicit的关键字只构造函数中带一个参数的情况起作用。其书面语的作用为：禁止单参构造函数的隐式转换。

机器人总动员 Wall-E 人工智能启示

Posted on 2008-09-30 Edited on 2023-10-05 Word count in article: 471 Reading time ≈ 1 mins.

机器人是作为单一个体还是有统一精神？

和“I robot”影片不同是，此片中的机器人都有自己独立的性格。可以完全不服从最高领导机器的统治。而I
robot中的不同，只有偶尔的一个机器人变异才使得机器拥有丰富的表情和情感。

另外发现Wall-E的鲁棒性非常好。在经历短路，压挤之后，换个主板仍能很好的工作。不过各个机器人的主板都不相同，看来各个机器人都有自己的用途。

Wall-E的目标更正和情感驱动做得很好。Wall-
E是700年前古老的机器人，竟然进化到能够明白自己想要做什么。这和一般的机器人不同。其他的机器人的指令要求输入，机器人才知道要干什么。Wall-
E已经强大到可以自我更改程序目标，做自己想做的事情。这比Captain机器人还要高级。因为Captain机器人竟然还遵循着700年前的决定。

一定要给机器人做一个停止按钮，一旦它不能正常工作，马上可以通过此按钮将它终止掉。

有情感不服从命令的机器人，我想大概都是因为程序bug导致的。正常的机器人循规蹈矩，只有少数编码不正确的机器人才能打破思维定势。难道人工智能质的突破要靠程序的
中的bug吗？

文雀

Posted on 2008-09-29 Edited on 2023-10-05 Word count in article: 266 Reading time ≈ 1 mins.

每个人都是文雀。

停留这里，是因为想呆在这里，

飞离这里，是因为想去其他地方，

不要限制自由，想去那里就应该能去哪里，

不论现在的生活是安逸还是贫苦。

我不清楚盗亦有道要不要提倡，因为盗已经偏离了道德准则。

盗亦有道这个很搞笑的成语，是老祖宗提出的悖论。

幸好林熙蕾是个ppmm，如果换成恐龙妹，我不认为那群小偷也会有“盗亦有道”。

这说明美人计是一个很好用的计策，放之四海皆成功。（当然这要排除断背和女子这两种情况）

江山代有才人出，过去的盗圣，现在可不一定是。

所以好汉不提当年勇。

提当年勇的好汉当然也是好汉，不过是当年的好汉，不一定是现在的好汉。

十全九美也不错

Posted on 2008-09-21 Edited on 2023-10-05 Word count in article: 406 Reading time ≈ 1 mins.

几乎没有人能够做到十全十美，正如标题一样

其实十全九美已经是较完美的结局了。

影片结局有些让人遗憾，但是不能奢求每一个电影的结局都是大圆满。传说悲剧的结局远比喜剧结局给人留下的印象要深。喜剧往往一笑而过，隔日或许只能记得最搞笑的情节。

但是这影片也算不上悲剧，只是略有悲情而已。

最后合棺一幕有些意思，不管平民还是皇帝，最后还不都是枯尸一具。

下面摘录主题曲《梨花香》，歌词写得不错，很有诗意。

笑看世间痴人万千
白首同倦实难得见
人面桃花是谁在扮演

事过境迁故人难见
旧日黄昏映照新颜
相思之苦谁又敢直言

梨花香却让人心感伤
愁断肠千杯酒解思量
莫相望旧时人新模样思望乡

事过境迁故人难见
旧日黄昏映照新颜
相思之苦谁又敢直言

为情伤世间事皆无常
笑沧桑万行泪化寒窗
勿彷徨脱素裹着春装忆流芳

笑我太过痴狂相思夜未烊
独我孤芳自赏残香

梨花香却让人心感伤
愁断肠千杯酒解思量
莫相望旧时人新模样思望乡
为情伤世间事皆无常
笑沧桑万行泪化寒窗
勿彷徨脱素裹着春装忆流芳

青苔

Posted on 2008-09-19 Edited on 2023-10-05 Word count in article: 146 Reading time ≈ 1 mins.

生活在最底层的人们，不被人关注，貌似柔弱，但是有顽强的生命力。

不论自己如何，总有比自己更弱小的人需要保护。

不论如何，顽强的生存下去，总是会有希望。

生命中与很多人相遇相离，每个人都有自己的方向。

一起上路还是分手离别，本无需在意太多。

青苔是不开花的。流浪者对小女孩的那句话意味深长：“你是花！”。

在Ubuntu 8.04上安装postgresql 8.3核心

Posted on 2008-09-18 Edited on 2023-10-05 Word count in article: 1.8k Reading time ≈ 2 mins.

我的系统是虚拟机上的ubuntu8

1。先去 http://www.postgresql.org 那里下个postgreSQL
core 8.3.
2.使用命令tar -xvf postgreSQL-8.3.3.tar.bz2 解压

3.去那个解压的文件夹,使用./configure 命令，它将自动检查系统配置

4.很不幸得是报了一个"c cannot output the executable file"

5.然后在网上找了找资料，发现没有升级libc所以使用命令:sudo apt-get install libc6-dev gcc g++

6再运行"./configure"，却报了readline library is not found，如果这个错误你能解决最好，还有可能报zlib is
not found

7.不幸的是我找了2个多小时，下载了无数相关的包，最后以readline5-dev包不能正常安装告终。

8.所以没有办法，只好这样运行./configure --without-readline --without-zlib

9然后make

10下面命令是要加sudo的
make install
adduser postgres
mkdir /usr/local/pgsql/data
chown postgres /usr/local/pgsql/data
到了这里，我们要创建logfile 文件然后把它拷贝到 /usr/local/pgsql/data/ （好像不拷贝也可以，大家可以试试）
然后切换用户sudo - postgres
/usr/local/pgsql/bin/initdb -D /usr/local/pgsql/data
/usr/local/pgsql/bin/postgres -D /usr/local/pgsql/data >logfile 2>&1 &
/usr/local/pgsql/bin/createdb test
/usr/local/pgsql/bin/psql test

最后，你能看到sql 交互界面…大功告成…

下面是自己写的英文安装手册, 英语语法错误多多指正(非大小写)。

how to install pgSQL in ubuntu

I installed Ubuntu 8.04 in VMMachine.
1. goto the http://www.postgresql.org to
download postgreSQL core 8.3.
2. tar -xvf postgreSQL-8.3.3.tar.bz2 (I don’t know your downloaded file
name. You can change it)
3. go the unpacked folder then “./configure”
4. it will check the environment of your computer.
5. Unluck, it showed error to me. IF it report like “c cannot output the
executable file”, then "sudo apt-get install

libc6-dev gcc g++
6. The run “./configure” again. It report “readline library is not found.”.
7. ./configure --without-readline --without-zlib
8. make

sudo
make install
adduser postgres
mkdir /usr/local/pgsql/data
chown postgres /usr/local/pgsql/data
create a file called logfile and copy it to /usr/local/pgsql/data/
sudo - postgres
/usr/local/pgsql/bin/initdb -D /usr/local/pgsql/data
/usr/local/pgsql/bin/postgres -D /usr/local/pgsql/data >logfile 2>&1 &
/usr/local/pgsql/bin/createdb test
/usr/local/pgsql/bin/psql test

编程练习——红黑树（RedBlackTree）

Posted on 2008-09-09 Edited on 2023-10-05 Word count in article: 10k Reading time ≈ 9 mins.

在网上搜索了很多红黑树的资源，发现自己看代码的能力还是有些欠缺。很多都看不懂，后来找到一篇英文红黑树文献，终于弄明白了红黑树的删除插入是怎么做的。但是那片文
献好像还有些漏洞，其中有一种删除情况，他并没有考虑到。如果大家想看的话可以搜索下 “red-black trees” ,由 prof. Lyn
Turbak所写。因为时间关系，插入算法只是实现了非CLR算法。删除算法我也不知道叫什么名字(文献里没有讲)。但是删除结果依旧符合红黑树。

建立红黑树节点的时候，考虑到因为经常要和一个节点的父亲节点打交道，所以采用了在节点里添加父亲节点的指针的方法。这样即方便也提高效率。另外也好调试。如果一味采
用递归…估计人会看疯掉的。插入的时候，采用的是先插入删除的时候红色节点，然后在判断是否违反红红条件。违反的话就左旋右旋进行调整。否则就插入成功。删除的时候
先删除节点，这个过程和删除二叉查找树节点一致。删除时要看真正要删除的节点是否是根节点，是否是黑色节点。因为红色节点和根节点删除不会调整树形。如果删除的是黑色
节点，那么要看替换他的节点（这里的替换一定是左子树树根，因为如果有右子树，那么被删除的也不会是这个节点，记住二叉查找树的删除过程）是否是黑色节点（这里如果左
子树为空，那他也是黑色节点）。如果是黑色节点，那么一定要调整树的结构，否则就直接染色。调整树结构时要考虑的情况就非常多了。一共有9种情况需要考虑。

下面是代码部分，删除时如何调整在代码注释中。至于insert操作，看看文献就应该会做了。

/*
* create RBNode class for construction RBTree
* create by chico chen
* date: 2008/09/04
* 如需转载注明出处
*/
1. template< class T>
#define RED 0
#define BLACK 1
class RBNode
{
public :
1. T data;
RBNode* left;
RBNode* right;
RBNode* parent;
int color;
1. RBNode(T& data)
{
this ->data = data;
left = NULL;
right = NULL;
parent = NULL;
color = RED;
}
RBNode(T& data, RBNode* left, RBNode* right, RBNode* parent)
{
this ->data = data;
this ->left = left;
this ->right = right;
this ->parent = parent;
color = RED;
}
1. ~RBNode()
{
this ->left = this ->right = this ->parent = NULL;
color = RED;
}
};

下面是红黑树代码

/*
* this is red-black-tree code
* this code is not efficent in inserting
* create by chico chen
* date: 2008/09/04
* 如需转载注明出处
*/
1. #include “RBNode.h”
1. template< class T>
class RBTree
{
1. private :
RBNode* root;
public :
RBTree()
{
this ->root = NULL;
}
~RBTree()
{
clearTree( this ->root);
}
1. 1. 1. void print()
{
print( this ->root,0);
}
1. 1. 1. 1. void insert(T& data)
{
1. RBNode* node = new RBNode(data);
insertNode(node);
}
1. void deleteKey(T& data)
{
deleteNode(data);
}
1. 1. bool RBTreeTest()
{
try
{
getBlackNum( this ->root);
1. }
catch (…)
{
return false ;
}
return true ;
}
1. private :
1. 1. void print(RBNode* subRoot, int num)
{
if (subRoot != NULL)
{
print(subRoot->right,num+3);
for ( int i = 0; i < num; i++)
{
cout << " " ;
}
cout << subRoot->data<< “(” <color<< “)” <<endl;
print(subRoot->left,num+3);
}
}
1. void clearTree(RBNode* subRoot)
{
if (subRoot == NULL)
return ;
clearTree(subRoot->left);
clearTree(subRoot->right);
delete subRoot;
}
1. RBNode* deleteMin(RBNode* subRoot,RBNode** parent)
{
1. while (subRoot != NULL)
{
parent = &subRoot;
if (subRoot->right != NULL)
{
subRoot = subRoot->right;
}
else
{
break ;
}
}
return subRoot;
}
1. void deleteNode(T& data)
{
if (root == NULL)
{
throw “Empty tree” ;
}
RBNode* subRoot = root;
while (subRoot != NULL)
{
if (subRoot->data > data)
{
subRoot = subRoot->left;
}
else if (subRoot->data < data)
{
subRoot = subRoot->right;
}
else
{
// find the data
// use the midOrder last one which is before the data node to replace
RBNode* inParent = subRoot;
RBNode* deleteNode = deleteMin(subRoot->left,&inParent);
RBNode* realDelete = NULL;
if (deleteNode != NULL)
{
subRoot->data = deleteNode->data; // copy
realDelete = deleteNode;
//real delete
}
else
{
realDelete = subRoot;
//real delete
}
if (realDelete->parent == NULL)
{
// delete root
delete realDelete;
}
else
{
// nothing at realDelete->right
RBNode* parent = realDelete->parent;
RBNode* subATree = NULL;
if (parent->left == realDelete)
{
parent->left = realDelete->left;
}
else
{
parent->right = realDelete->left;
}
subATree = realDelete->left;
if (realDelete->left != NULL)
{
realDelete->left->parent = parent;
}
int color = realDelete->color;
delete realDelete;
if (color == BLACK &&
(subATree == NULL || subATree->color == BLACK))
{
1. 1. deleteRebuild(subATree,parent);
}
else if (color == BLACK && subATree->color == RED)
{
subATree->color = BLACK;
}
else
{
// do nothing
}
break ;
}
1. }
}
}
1. 1. /* delete them if you want
// x® c®
// / / / /
// `a(b) b(b) --> x(b) b(b)
// / /
// c® a(b)
// LRL means L-> double black is at left, and rotate is RL
RBNode* LRLCaseA(RBNode* x)
{
RLRotate(x,x->right,x->right->left);
x->color = BLACK;
return x->parent;
1. }
1. 1. // x® b®
// / / / /
// `a(b) b(b) --> x(b) c(b)
// / /
// c® a(b)
RBNode* LLLCaseA(RBNode* x)
{
RRRotate(x,x->right);
x->color = BLACK;
x->parent->color = RED;
x->parent->right->color = BLACK;
return x->parent;
}
1. // x® b®
// / / / /
// b(b) `a(b)–> c(b) x(b)
// / /
// c® a(b)
RBNode* RLLCaseA(RBNode* x)
{
LLRotate(x,x->left);
x->color = BLACK;
x->parent->color = RED;
x->parent->left->color = BLACK;
return x->parent;
}
1. 1. // x® c®
// / / / /
// b(b) `a(b)–> b(b) x(b)
// / /
// c® a(b)
RBNode* RLRCaseA(RBNode* x)
{
LRRotate(x,x->left,x->left->right);
x->color = BLACK;
1. return x->parent;
}
1. 1. // x® x(b)
// / / / /
// `a(b) c(b) -> a(b) c®
// / / / /
// d(b) e(b) d(b) e(b)
RBNode* LCaseB(RBNode* x)
{
x->color = BLACK;
x->right->color = RED;
}
1. // x® x(b)
// / / / /
// c(b) `a(b) -> c® a(b)
// / / / /
// d(b) e(b) d(b) e(b)
RBNode* RCaseB(RBNode* x)
{
x->color = BLACK;
x->left->color = RED;
}
1. // x(b) c(b)
// / / / /
// `a(b) c® -> x® e(b)
// / / / /
// d(b) e(b) `a(b) d(b)
RBNode* LCaseC(RBNode* x)
{
RRRotate(x,x->right);
x->color = RED;
x->parent->color = BLACK;
return x->parent;
}
1. // x(b) c(b)
// / / / /
// c® `a(b) -> d(b) x®
// / / / /
// d(b) e(b) e(b) `a(b)
RBNode* RCaseC(RBNode* x)
{
LLRotate(x,x->left);
x->color = RED;
x->parent->color = BLACK;
return x->parent;
}
*/
1. bool isBlack(RBNode* node)
{
1. if (node == NULL || node->color == BLACK)
return true ;
return false ;
}
1. void rebuild(RBNode* node)
{
if (node->parent->data > node->data)
{
node->parent->left = node;
}
else
{
node->parent->right = node;
}
}
1. 1. /*
* There are 9 cases we will meet. The cases of the double black node at the right is ignored.
* (b) means black node, (db) means double black node, ® means red node
* 1. (b) 2 (b) 3 (b)
* / / / / / /
* (db) (b) (db) (b) (db) (b)
* / / / / / /
* (b) (b) ® (b) (b) ®
* 4. (b) 5 (b) 6 ®
* / / / / / /
* (db) (b) (db) ® (db) (b)
* / / / / / /
* ® ® (b) (b) (b) (b)
* 7. ® 8 ® 9 ®
* / / / / / /
* (db) (b) (db) (b) (db) (b)
* / / / / / /
* ® (b) (b) ® ® ®
* case 1,6: up the black, if the parent is black then call the function again until the
* double black node is root, else blacken the parent.
* case 2,4,7,9: call the RLRotate, if the parent of the double
* node is black, up the black and call the function again, else
* blacken the parent.
* case 3,8: call the LLRotate, the same as case 2.
* case 5: call LLRotate, change as (b) then end.
* / /
* (b) (b)
* / /
* (b) ®
*/
void deleteRebuild(RBNode* node,RBNode* parent)
{
if (parent == NULL)
{
// root, delete the black
return ;
}
if (parent->left == node)
{
RBNode* brother = parent->right;
RBNode* nephewA = brother->left;
RBNode* nephewB = brother->right;
1. if (isBlack(nephewA) && isBlack(nephewB) && isBlack(brother))
{
// case 1,6
brother->color = RED;
if (parent->color == BLACK)
{
deleteRebuild(parent,parent->parent);
}
else
{
parent->color = BLACK;
return ;
}
1. }
1. else if (!isBlack(nephewA))
{
// case 2,4,7,9
RBNode* tempRoot = RLRotate(parent,brother,nephewA);
// rebuild
rebuild(tempRoot);
1. }
else if (!isBlack(nephewB))
{
// case 3,8
RBNode* tempRoot = RRRotate(parent,brother);
rebuild(tempRoot);
nephewB->color = BLACK;
brother->color = RED;
}
else if (!isBlack(brother))
{
// case 5
RBNode* tempRoot = RRRotate(parent,brother);
rebuild(tempRoot);
brother->color = BLACK;
nephewA->color = RED;
return ;
}
else
{
// unknown
throw “none excption, about there is no red or black” ;
}
1. if (parent->color == BLACK)
{
// case 2,3,4
deleteRebuild(parent,parent->parent);
}
else
{
// case 7,8,9
parent->color = BLACK;
}
1. }
else
{
RBNode* brother = parent->left;
RBNode* nephewA = brother->right;
RBNode* nephewB = brother->left;
1. if (isBlack(nephewA) && isBlack(nephewB) && isBlack(brother))
{
brother->color = RED;
if (parent->color == BLACK)
{
deleteRebuild(parent,parent->parent);
}
else
{
parent->color = BLACK;
return ;
}
}
else if (!isBlack(nephewA))
{
RBNode* tempRoot = LRRotate(parent,brother,nephewA);
// rebuild
rebuild(tempRoot);
1. }
else if (!isBlack(nephewB))
{
RBNode* tempRoot = LLRotate(parent,brother);
rebuild(tempRoot);
nephewB->color = BLACK;
brother->color = RED;
}
else if (!isBlack(brother))
{
RBNode* tempRoot = LLRotate(parent,brother);
rebuild(tempRoot);
nephewA->color = RED;
brother->color = BLACK;
return ;
}
else
{
throw “none excption, about there is no red or black” ;
}
1. if (parent->color == BLACK)
{
deleteRebuild(parent,parent->parent);
}
else
{
parent->color = BLACK;
}
1. }
1. }
1. 1. void insertNode(RBNode* node)
{
1. if (root == NULL)
{
root = node;
node->color = BLACK;
return ;
}
RBNode* subRoot = root;
RBNode* insertPoint = NULL;
while (subRoot!=NULL)
{
insertPoint = subRoot;
if (subRoot->data > node->data)
{
// insert left
subRoot = subRoot->left;
1. }
else if (subRoot->data < node->data)
{
subRoot = subRoot->right;
}
else
{
throw “same key” ;
}
}
1. 1. if (insertPoint->data > node->data)
{
insertPoint->left = node;
}
else
{
insertPoint->right = node;
}
node->parent = insertPoint;
1. 1. insertRebuild(node);
1. }
1. // return the subRoot
// a b
// / / /
// b -> c a
// /
// c
RBNode* LLRotate(RBNode* a, RBNode* b)
{
if (b->right != NULL)
{
b->right->parent = a;
1. }
a->left = b->right;
b->right = a;
b->parent = a->parent;
a->parent = b;
return b;
}
1. // return the subRoot
// a b
// / / /
// b -> a c
// /
// c
RBNode* RRRotate(RBNode* a, RBNode* b)
{
if (b->left != NULL)
{
b->left->parent = a;
1. }
a->right = b->left;
b->left = a;
b->parent = a->parent;
a->parent = b;
1. 1. return b;
}
1. 1. // return the subRoot
// a c
// / / /
// b -> a b
// / /
// c d
// /
// d
RBNode* RLRotate(RBNode* a, RBNode* b, RBNode* c)
{
1. if (c->right != NULL)
{
c->right->parent = b;
1. }
b->left = c->right;
c->right = b;
b->parent = c;
if (c->left != NULL)
{
c->left->parent = a;
1. }
a->right = c->left;
c->left = a;
c->parent = a->parent;
a->parent = c;
1. return c;
}
1. // return the subRoot
// a c
// / / /
// b -> b a
// / /
// c d
// /
// d
RBNode* LRRotate(RBNode* a, RBNode* b, RBNode* c)
{
if (c->left != NULL)
{
c->left->parent = b;
1. 1. }
b->right = c->left;
c->left = b;
b->parent = c;
if (c->right!= NULL)
{
c->right->parent = a;
1. }
a->left = c->right;
c->right = a;
c->parent = a->parent;
a->parent = c;
1. return c;
}
1. // node is not the root
void insertRebuild(RBNode* node)
{
RBNode* parent = NULL;
RBNode* grandParent = NULL;
while (node->parent != NULL)
{
parent = node->parent;
1. if (parent->color == RED) // here means there must be a grandparent
{
grandParent = parent->parent;
grandParent->color = BLACK;
1. if (grandParent->left == parent)
{
if (parent->left == node)
{
//LLRotate
node->color = BLACK;
node = LLRotate(grandParent,parent);
1. }
else
{
//LRRotate
parent->color = BLACK;
node = LRRotate(grandParent,parent,node);
1. }
1. }
else
{
1. if (parent->left == node)
{
//RLRotate
parent->color = BLACK;
node = RLRotate(grandParent,parent,node);
}
else
{
//RRRotate
node->color = BLACK;
node = RRRotate(grandParent,parent);
}
}
}
else
{
break ;
}
}
1. if (node->parent == NULL)
{
node->color = BLACK;
this ->root = node;
}
else
{
rebuild(node);
/*if(node->parent->data > node->data)
{
node->parent->left = node;
}
else
{
node->parent->right = node;
}*/
}
}
1. 1. 1. 1. int getBlackNum(RBNode* subRoot)
{
if (subRoot == NULL)
{
return 1;
}
int left = getBlackNum(subRoot->left);
int right = getBlackNum(subRoot->right);
if (left != right)
{
throw “wrong” ;
}
if (subRoot->color == BLACK)
{
1. return 1+left;
}
else
{
return left;
}
1. }
};

返回值优化问题

Posted on 2008-08-27 Edited on 2023-10-05 Word count in article: 1.2k Reading time ≈ 1 mins.

近来看到小李子写了篇blog，题目为返回值优化。

文章如下。

return Integer(left.i+right.i); //创建一个临时对象并返回他，不会调用析构函数，效率高。
Interger tmp(left.i+right.i);
return tmp; //创建了局部对象，有析构函数。

————————————————————————————————

这里感觉有些诡异。

于是编写了简单的程序

// TempClassDestroy.cpp : Defines the entry point for the console application.
//
1. #include “stdafx.h”
#include
using namespace std;
class A
{
private :
int a;
public :
A( int a)
{
this ->a = a;
}
~A()
{
cout << “AA:” <<a<<endl;
}
};
1. 1. A& foo1( int c)
{
return A©;
}
1. 1. A foo2( int c)
{
return A©;
}
1. A foo3( int c)
{
A a©;
return a;
}
A& foo4( int c)
{
A a©;
return a;
}
int _tmain( int argc, _TCHAR* argv[])
{
foo1(1);
cout << “foo1” <<endl;
foo2(2);
cout << “foo2” <<endl;
foo3(3);
cout << “foo3” <<endl;
foo4(4);
cout << “foo4” <<endl;
1. 1. 1. A& a = foo1(1);
A& b = foo2(2);
A& c = foo3(3);
A& d = foo4(4);
return 0;
}
1. 最后的运行结果是：

AA:1
foo1
AA:2
foo2
AA:3
AA:3
foo3
AA:4
foo4
AA:1
AA:3
AA:4
AA:3
AA:2

当然前面的内容：

AA:1
foo1
AA:2
foo2
AA:3
AA:3
foo3
AA:4
foo4

第二个函数与第三个函数可以很明显的看到效率的差异。因为foo3函数中析构函数出现了两次。

（这里第一和第四个函数有明显错误，可以根据后面的测试程序看出）

但是第一个函数也恰恰说明 return Integer(left.i+right.i); //创建一个临时对象并返回他，不会调用析构函数，效率高。
这句话有些问题。因为在调试的时候可以看出有调用析构函数。并且结果

AA:1
AA:3
AA:4
AA:3
AA:2

也能说明问题。

由于第一个函数和第四个函数产生的效果一样。

所以我提出一个可能的假设：

return Integer(left.i+right.i);
只有当返回值为Integer，而非Integer&才能有创建一个临时对象并返回他，不会调用析构函数。

当然因为程序的正确性要求，我们不可能编写类似于foo1的函数。

快速排序其他实现代码

Posted on 2008-08-19 Edited on 2023-10-05 Word count in article: 480 Reading time ≈ 1 mins.

int hoare_partition( int a[], int low, int high)
{
int x=a[low];
int i=low-1;
int j=high+1;
while (1)
{
do {j–;}
while (a[j]>x);
do {i++;}
while (a[i]<x);
if (i<j)
swap(a[i],a[j]);
else return j;
}
}
1. void hoare_quicksort( int a[], int low, int high)
{
int q;
if (low<high)
{
q=hoare_partition(a,low,high);
hoare_quicksort(a,low,q);
hoare_quicksort(a,q+1,high);
}
}
1. 1. int _tmain( int argc, _TCHAR* argv[])
{
int a[9]={45,32,1,5,34,2,4,32,2};
hoare_quicksort(a,0,8);
for ( int i = 0; i< 9; i++)
cout << a[i]<< " " ;
return 0;
}