帐前卒专栏

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;
}

创造练习——自适应树(Self-Adjusting Tree)

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

这个树的定义的确很有问题。其实AVLTree和SplayTree以及RedBlackTree都是self-adjusting Tree

因为如果是树做索引那么大部分的时间将用来查找。这个树在查找上可以将查找的节点提升到树根，插入时也是一样。这样提高了查找的效率。并且操作系统有一种说法是近来用
到的，将来用到的几率也会很大（LRU原理）。删除，既然删除对于此树来说再也没有什么，那就直接删除算了。

根据这几点想法。自己做一个self-adjusting Tree。但是还没有验证是否能达到实际水平的O（nlogn）。虽然理论上这个树并不能达到这样一个时间
复杂度。但是对于实际数据来说，还是有可能达到的。不知道有没有这么lucky。

因为对于这个树来说插入和查找操作其实差不多。

所以下面只介绍插入操作。找到要插入的地方，反遍历单旋转（这里和SplayTree不同一点是只使用单旋转）

TreeNode* insertNode(TreeNode* subroot,TreeNode* prev,T& data)

返回值为当前子树根节点

1.subroot是否为空,创建新的节点，并返回subroot

2.如果不为空

A.subroot中的值 < data中的值,对subroot右子树调用insertNode()，subroot
与当前右子树根节点采用旋转操作。将两个节点位置对换。

B.subroot中的值 > data中的值，对subroot左子树调用insertNode()，subroot
与当前左子树根节点采用旋转操作。将两个节点位置对换。

C.subroot中的值 == data中的值，do nothing

3.查看该节点是否已成为根节点。如果是的话，调整根节点的值。

下面给出代码。

template < class T>
class SelfTree: public BinaryTree
{
private :
// return the sub tree root
// a b
// / -> /
// b a
TreeNode* sLeftRotate(TreeNode* a,TreeNode* b)
{
a->setLeft(b->getRight());
b->setRight(a);
return b;
}
1. 1. // return the sub tree root
// a b
// / -> /
// b a
TreeNode* sRightRotate(TreeNode* a, TreeNode* b)
{
a->setRight(b->getLeft());
b->setLeft(a);
return b;
}
1. 1. 1. TreeNode* insertNode(TreeNode* subroot,TreeNode* prev,T& data)
{
if (subroot == NULL)
{
subroot = new TreeNode(data);
return subroot;
}
else
{
TreeNode* tempNode = NULL;
TreeNode* tempRoot = NULL;
if (subroot->getData() > data)
{
1. tempNode = insertNode(subroot->getLeft(),subroot,data);
tempRoot = sLeftRotate(subroot,tempNode);
1. }
else if (subroot->getData() < data)
{
tempNode = insertNode(subroot->getRight(),subroot,data);
tempRoot = sRightRotate(subroot,tempNode);
}
else
{
throw “the same key” ;
}
1. if (prev == NULL)
{
this ->head = tempRoot;
}
else
{
if (prev->getData() > tempRoot->getData())
{
prev->setLeft(tempRoot);
}
else
{
prev->setRight(tempRoot);
}
}
return tempRoot;
}
}
public :
SelfTree(T& data):BinaryTree(data)
{
1. }
1. ~SelfTree()
{
1. }
1. void insertNode(T& data)
{
insertNode( this ->head,NULL,data);
}
1. };