行者无疆 始于足下 - 行走，思考，在路上
夜半听歌
歌曲:单行道
歌手:王菲
一路上有人坐在地铁
张望擦身而过的广告
有人怕错过每段躲不过的
新闻报导
一路上有人能白头到老
有人失去青春年少
有人在回忆中微笑
也有人为了明天而烦恼
一路上有人付出虔诚
为不认识的陌生人祈祷
有人过了一辈子只为
一家几口每天都吃饱
一路上与一些拥抱
一边想与一些人绝交
有人背影不断膨涨
而有些情境不断缩小
春眠不觉晓庸人偏自扰
走破单行道
花落知多少跑不掉
每个人都是单行道上的跳蚤
每个人皈依自己的宗教
每个人都在单行道上寻找
没有人相信其实不用找
一路上有人太早看透
生命的线条命运的玄妙
有人太晚觉悟冥冥中
该来则来无处可逃
一路上有人盼望缘份
却不相信缘份的必要
一路上那青春小鸟
掉下长不回的羽毛
春眠不觉晓庸人偏自扰
走破单行道
花落知多少跑不掉
每个人都是单行道上的跳蚤
每个人皈依自己的宗教
每个人都在单行道上寻找
没有人相信其实不用找
每个人都是单行道上的跳蚤
每个人皈依自己的宗教
每个人都在单行道上寻找
没有人相信其实不用找
同样是大学四年，有人出国深造，有人延期毕业。
或许，大学的四年，多点思考，少点盲从，方能收获更多。
常听人说“某某又拿了哪哪的offer”，“某某又拿了啥啥的奖牌”，
渺小的我们只剩下一仰慕二叹息的份，
其实看看雷军的博客，
人因梦想而伟大，
我们会发现，
梦想并不遥远。
其实中国人活的是很累的，
文化传统，社会观念，多年的历练，
多数中国人练就了一身厚黑本领，
厚而无形，黑而无色，
放眼当下，
文华精英、经济精英、政治精英，
中国社会的三足鼎立。
有对比就会有差距，
有差距就会有动力，
有动力就会有进步，
有进步就会有思考，
有思考就会有沉淀。
当我还在这边纠结于学业，
上海交大某大一男生已经拿了acm/icpc世界总冠军；
当我借口说自己大学前基本不懂计算机时，
我昨天逛98却发现同样的条件水平，浙大Zodiac队伍世界第六，
当然这背后包含三年的汗水；
当我豪言“绩点是个屁”时，
有人仗着不算很高的绩点拿了哈佛的offer，
我还在这边浑浑噩噩，每天通宵达旦，日照三杆。
某日，日照三杆，肚中无物，遂出门觅食，
寻寻觅觅，
不知不觉，
至黄龙洞，
遂又寻阶而上，
日暮，
宝石山上，青灯古寺，
昂首望月，
心情大畅。
遂彩信莫莫一条，莫莫大窘：“晗宇你不许出家！想法都不能有！”
笑之。
没有什么能够阻挡，
你对自由的向往，
天马行空的生涯，
你的心了无牵挂，
穿过幽暗的岁月，
也曾感到彷徨，
当你低头的瞬间，
才发现脚下的路，
心中那自由的世界，
如此的清澈高远。
我是一个喜欢放纵，甚至放纵到堕落的人。
“人生得意需尽欢，莫使金樽空对月”，
偶尔的放纵，有时能够让人认清前进的方向。
哼着哼着，
泪水却控制不住，
女人常常抱怨，
说，女人的眼泪不值钱，
男人却被告知，
说，有泪不轻弹。
那是因为，
男人的眼泪，
最具有杀伤性。
寒假回家，
我大哭了一场。
哭后只想着逃离，
想着出去漂泊，
想着给家里留下一封信，
就什么也不管，
出走。
但我还是留下。
我想，
男人成长的痛苦
多半来自于男人的责任感。
人无法选择自己的出身。
更准确的说，人生有很多自己无法选择的东西。
但是可以选择自己的人生之路。
人生是一个时间的函数，
出身、家庭、五官长相是这个函数的参数。
你无法改变外界的输入，
但是你可以改变函数本身，
得到迥异的输出。
马云说，CEO是世界上最孤独的人，
所以时常夜半，马云在街上遛狗。
而孤独，是行者的骨头。
马云说最喜欢笑傲江湖的令狐冲，
我最喜欢令狐的一句话：“大丈夫行事，行云流水，任意所致，什么武林规矩，门派教条，都是他妈的臭狗屁”。
立于天地，
无愧于心。
高中时搞保送竞赛，我对班主任说“我的所作所为，对得起我的良心，对得起我的父母，对得起我的老师”，
我想，现在我的所作所为，对得起我曾经说过的话。
当会长的时候，俱乐部的前辈农民姐姐曾对我说：
“别看我们不逛论坛平时不怎么灌水，其实我们都在默默地看着你们呢”
行者无疆，始于足下。
爱行者，这是我的家，我的归宿。
总结下上半年的课程
好久没有更新了。上次更新还是三个月之前。那时的算法课程，昏天黑地地写了三天的代码，bst, avl, splay，稀里糊涂。
转眼已到春至。回想前面几个月的生活，百感交集。12月份1月份以学习为主。专业课究竟是专业课，颇有力不从心的感觉。好在通过自己努力，成绩还不错 ，这么一来压力少了很多——我可以顺利毕业了，呵呵。
说说去年的课吧。
计算几何：唯一挂掉的课程。54分。主要是自己太过自信，秋学期考试前几天一直在看图形学，忽略了这门课的复习。我想我平时作业交了，期中考的还成，期末再怎么差也不会太难看。但事与愿违，老外的课不留水分。期末考试我觉得很难。很多人都弃考了，我也没有做出来几道题。考完了就有种不详的预感。最终悲剧的挂了。不过还是有所收获。除了一些入门知识，了解了latex tikz/pgf宏包的使用，还有geogebra软件。
计算理论：学过的所有课程中最为抽象的一门课程。半年就讲四章，中文书100页的内容，第四章图灵机的很多内容到现在还是不太明白，什么NP，原始递归，判定性等等。DFA，NDFA，CFG等，也是费了好大的力气才理解的差不多。作业占10%，期中占20%，期末70%。算上期中考试，我就上过3次课。作业最后补了不少，打算考试时候交给老师，可惜老师没有收。这么算了我作业分0分了。最后的几天都在复习，期末感觉还不错。最后总分80。比较满意了。现在想想这门课应该是蛮优美的一门理论，尤其是又穷自动机和正则语言、下推自动机和上下文无关文法、图灵机和文法之间的对应和转换关系，以及图灵机对很多问题的判定，都是非常抽象非常晦涩但是理解后又会使人感叹的东西。由此可见，本门课程的祖师爷Alan Turing先生的伟大之处。他在人们还没有搞懂什么是计算机的时候就发明了这套理论。
操作系统：78。比预期的要低。大概是自己太过自信，没有复习的缘故。14次小作业完成的都不错，presentation满分，期末考的不咋样。客观的说，这门课只能算作科普课程。通过这门课学习，知道了进程、线程、DMA、MMU、死锁、进程同步、CPU调度、文件系统、磁盘结果等概念。主要收获还是自己参与的三次Presentation。第一次写了基于浏览器的操作系统，第二次写了二十页英文的关于进程和线程的论述，第三次是linux系统调用深入研究。
汇编与接口，重点了解了x86 intel 汇编，我对接口部分没啥兴趣。大一时买的清华那本《IBM-PC汇编语言程序设计》总算派上了用场。最后自己编了一个200多行浮点数运算四则运算模拟的汇编程序，深入研究了IEEE 754浮点数标准，了解了汇编程序的结构，一些重要的指令和伪指令。最后考试不咋样。没怎么复习，接口部分不熟，总成绩66。
汇编与接口实验，多数实验是糊弄的……人家前脚做完实验，我后脚开机，开始“做实验”，最后参考别人程序，修修改改，蒙混过关……整个过程极其痛苦……发誓以后打死也不过电路芯片等硬件相关的东西。最后糊弄个80分了事。
计算机图形学，科普课程。课上只讲原理，不讲编程，作业却是用OpenGL编程，编六个大程序。结果考试却又完全不考OpenGL，真是无语的一门课程。最后考试题目大体如下：
- 扫描线填充和种子填充算法概述，优缺点比较。
- Phong模型和Gouraud模型概述，比较。
- 画家算法和z-buffer消隐算法概述，比较。
- 光线跟踪算法和辐射度方法。
- 如何用深度缓存生成影子。
我答的还不错。最大的收获是OpenGL编程、OpenGL Pipeline、3D几何变换，还有一些常用算法。不过说来容易做起来难，本身图形学对数学的要求极高，我这种水平也只能高山仰止，调调OpenGL函数糊弄了事。最后的程序搞了600多行，很是崩溃。尽管学的比较辛苦，但是成绩只有72分。大概是自己没上过几次课点名没到的缘故吧。
数值分析：很难的一门课。当然如果你有好的数学基础和扎实的编程基础，学起来还是蛮又收获的。讲到切比雪夫多项式的时候大家都晕了，只有老师一个人在台上无奈的叹气。实验要求是8个大程序，网址在这里，共30分。坦白的说，我一个人搞不定。最后的办法是借来了别人的程序，参考课本仔细研读，加上自己创造，终于在deadline之前搞定。考试也不简单，最后老师特地延长了时间。总成绩80。比较满意了。收获是以后遇到此类问题知道去哪里查书了。
高级数据结构和算法：8次课，在zjg，去了3次。和两位大二的学弟组了队。编了大程序——见我前一篇日志。最后80左右。收获：没啥收获。这么短的时间，所谓高级算法，就是一个噱头。
逻辑与计算机基础：极其痛苦的一门课。本身对电类课程过敏。而这么课又是讲什么全加器、选择器、译码器等数字电子电路相关的东西，加上课程在zjg，所以我也没怎么上。最后和别人组队，弄个文职，长者自己latex略有小成，弄了份精美的文档过去。四次quiz也是糊弄，期末考试也是糊弄，老师照顾，60分。总算过了。
逻辑与计算机基础实验：极其痛苦的一门课。13次实验+期末考试，只给一个学分。其实关于Verilog，大家都不会，也没几个感兴趣的。实验课就是前人栽树后人乘凉，好在我们在下午上课，上课的内容就是找到别人编好的程序，鼠标点点，运行下，最后糊弄下老师，签字走人。收获：看过了FPGA开发板，知道了XILINX这个软件bug多多，比较恶心。
操作系统实验：就是linux的相关操作。四次实验，依次是Linux API，编译内核，系统调用，文件系统改造。收获不小。看了部分《Unix环境高级编程》，亲自动手编译了内核——以前不敢的。进一步熟悉了Emacs、latex，还有强大的cscope的初步使用。最后91分。
马克思主义原理：没怎么去。只有60多分。收获：基本上复习了初中政治的内容，觉得资本主义本质、商品使用价值和价值的分析是最精彩的。课比较恶心，分比较低，老师比较不厚道。
游泳：60分。其实本不该这样。理论考考试系统出问题，一分钟刷出来一道题，做不完。体质测试又出问题，本来由于场地原因，我们这半年就上前面几周的课程，最后老师说我的体质测试成绩没有给他。可是我根本不知道那个时候该到哪里上课。结果60分。令人愤慨。
工程训练：暑假上的，科普课程。最令我感到震惊的是学医学的也要学这么课程，和我们这些工科男一起去打铁。最后自己做了个小锤子，送给mm了。82分。收获：开阔了眼界。
Linux程序设计：77分。作业都是在贵州做的，点名没到，貌似扣了5分。收获：进一步熟悉了各种命令。
还有一门弃考的计算机组成实验，今年再修。两门补考没去，分别是计算机组成和线性代数，都是大二挂的课程。大四再说了。这半年课程也不少，开学两周我还没怎么去上过课，惭愧。
今天先写到这里。去吃饭了。昨天搞gentoo到四点多，今天中午才起，午饭还没有吃。肚子饿了。以后把一些重要的资料传上来。^_^
bst, avl, c++, inheritance, template, two days
鉴于大二上年幼无知加上某些特殊的原因，导致我大三才开始修读高级数据结构。同一屋子大二的小朋友们上课，百般滋味，心中自知。第一次课迟到了，下课的时候随便找了两个学弟，算是组了个队，并申请做Project1(因为开始的Project)会比较简单。
实践起来也不是很难，就是让你比较下BinarySearchTree, AVL Tree和Splay Tree的插入删除效率的问题。两个学弟看样子都不愿意编码，于是乎，编码的重担就落在了我这个学长身上。可是只有我自己知道，我数据结构学的实在不咋的，C++又是个半吊子。唉，谁让咱是学长呢？
学长嘛，自然要有个学长的样子。于是乎，C++、Template、Inheritance、Polymorphism，能用上的都用上……呵呵。不过主要是想练一下手。C++ Primer虽然看了大半，却没有多少应用的机会。这也算是一个练习吧。
写着写着就知道，C++的强大是一把双刃剑，强大到你无法驾驭，尤其是应用了模板后，各种小问题，都是以前闻所未闻的。比如模板的分离编译问题，看书，查资料就花了两个小时。加上昨天下午吐血恶心的同步时序电路的逻辑实验，做的我都想哭了。所以这么看上去很简单的project，我竟然写了接近两天，倍感惭愧。
不过总算出来了。但是有个瑕疵，avl的删除功能有些小问题，可能跟Balance函数和指针的引用问题有关。gdb我用的不熟，转到强大的windows下的visual studio 2008下，调试了3个小时，找到错误所在，但是却不知道怎么改正。泪奔。
计算几何最终还是低空坠毁，唉，不提也罢，看来以后不能乱选课，选了课不能随便混混。混不好就低空坠毁。你说你没事选这么一门前沿课程干嘛，你是这块料嘛……
计算几何过后开始准备计算理论的期中考试。什么有穷自动机，正则语言，上下文无关文法，等等，计算理论基础的中文版，每个小时3页，龟速前进，发现还是太抽象，看不大懂，又找来一本计算理论导引，两本结合着看，顿觉顺畅很多，看来计算机的书还是要原汁原味的英文啊。
感觉计算理论期中还不错。周一被导师叫去公司，让我参加项目，大意是让我写一个TextArea。项目代码有四万左右，光理清这个体系，补windows编程的基础知识就花了我三四天的时间。终于搞明白了什么叫windows ce，什么叫GDI，学会了windows下svn的基本用法。可是看windows ce的书还是一头雾水，什么HINSTANCE，WINAPI WinMain()，叉叉的。基本流程我还不懂。于是去找windows经典书目的书单，看到多人推荐Charles Petzold的windows程序设计，吐血买了下来，花了150元。Microsoft的书真tn的贵。
不过书是好书。周六周日周一断续看了三天，看了四章，120页，顿时明白了很多。个人windows的技术更新太快，不想unix，二十年前的vim、emacs、grep，等，万古不变。掌握win32 API才是一切的根本。永远不要指望跟上Microsoft的脚步。
只不过到现在导师的项目还没有开工，我还夸下海口自不量力要一周写出来。这可如何是好。还有图形学作业，操作系统作业，实验的作业，呃……少壮不努力，老大做it，大二不学习，大三干苦力。要努力。恩。
BinarySearchTree.h:
#define _BINARYSEARCHTREE_H_
#include <iostream>
#include <stack>
using namespace std;
/// 三种遍历方式
#define PREORDERTRAVERSE 0
#define INORDERTRAVERSE 1
#define POSTORDERTRAVERSE 2
/// 求两个元素的最大值
#define max(x, y) ((x > y) ? (x) : y)
/**
* @class BinaryNode
* @brief 树的结点，为了方便BST和AVL用了同一种结构。BST中所有结点的height域为默认值
*/
template<typename Comparable>
struct BinaryNode
{
Comparable element;
BinaryNode* left;
BinaryNode* right;
int height;
BinaryNode(const Comparable &theElement, BinaryNode *lt, BinaryNode *rt, const int theHeight = 0)
: element(theElement), left(lt), right(rt), height(theHeight) {}
};
/**
* @class BinarySearchTree
* @brief 实现了常见的删除，插入功能。并作为AVL树的基类
*/
template<typename Comparable>
class BinarySearchTree
{
public:
BinarySearchTree();
~BinarySearchTree();
BinaryNode<Comparable>*& GetRoot();
void BuildBinaryTree(Comparable *x, int length);
const Comparable& FindMin() const;
const Comparable& FindMax() const;
bool Contains(const Comparable &x) const;
bool IsEmpty() const;
void TraverseTree(int type);
void MakeEmpty();
virtual void Insert(const Comparable &x);
virtual void Remove(const Comparable &x);
private:
BinaryNode<Comparable> *root;
virtual void Insert(const Comparable &x, BinaryNode<Comparable> *&t) const;
virtual void Remove(const Comparable &x, BinaryNode<Comparable> *&t) const;
BinaryNode<Comparable>* FindMin(BinaryNode<Comparable> *&t) const;
BinaryNode<Comparable>* FindMax(BinaryNode<Comparable> *&t) const;
bool Contains(const Comparable &x, BinaryNode<Comparable> *&t) const;
void MakeEmpty(BinaryNode<Comparable> *&t);
void PreOrderTraverse(BinaryNode<Comparable> *&t);
void InOrderTraverse(BinaryNode<Comparable> *&t);
void PostOrderTraverse(BinaryNode<Comparable> *&t);
};
/**
* 构造函数，默认root=NULL
*
*
* @return
*/
template<typename Comparable>
BinarySearchTree<Comparable>::BinarySearchTree() : root(NULL){}
/**
* 析构函数
*
*
* @return
*/
template<typename Comparable>
BinarySearchTree<Comparable>::~BinarySearchTree()
{
MakeEmpty();
}
/**
* 得到根节点的引用
*
*
* @return 返回根节点的引用
*/
template<typename Comparable>
BinaryNode<Comparable>*& BinarySearchTree<Comparable>::GetRoot()
{
return root;
}
/**
* 建立BST树，通过数组的方式传入元素，调用Insert(x)函数
*
* @param x
* @param length
*/
template<typename Comparable>
void BinarySearchTree<Comparable>::BuildBinaryTree(Comparable *x, int length)
{
for (int i = 0; i < length; ++i)
{
Insert(x[i]);
}
}
/**
* @return BST中的最小值
*/
template<typename Comparable>
const Comparable& BinarySearchTree<Comparable>::FindMin() const
{
return FindMin(root)->element;
}
/**
* @return BST中的最大值
*/
template<typename Comparable>
const Comparable& BinarySearchTree<Comparable>::FindMax() const
{
return FindMax(root)->element;
}
/**
* 测试x是否在BST中，调用私有函数Contains(x, root)
*
* @param x
*
* @return
*/
template<typename Comparable>
bool BinarySearchTree<Comparable>::Contains(const Comparable &x) const
{
return Contains(x, root);
}
/**
* 测试树是否为空
*
*
* @return
*/
template<typename Comparable>
bool BinarySearchTree<Comparable>::IsEmpty() const
{
if (root == NULL)
{
return true;
}
return false;
}
/**
* 以三种方式遍历树
*
* @param type 遍历树的方式
*/
template<typename Comparable>
void BinarySearchTree<Comparable>::TraverseTree(int type)
{
if (type == PREORDERTRAVERSE)
{
cout << "PreOrderTraverse the tree:" << endl;
PreOrderTraverse(root);
cout << endl << "PreOrderTraverse ends." << endl;
}
if (type == INORDERTRAVERSE)
{
cout << "InOrderTraverse the tree:" << endl;
InOrderTraverse(root);
cout << endl << "InOrderTraverse ends." << endl;
}
if (type == POSTORDERTRAVERSE)
{
cout << "PostOrderTraverse the tree:" << endl;
PostOrderTraverse(root);
cout << endl << "InOrderTraverse ends." << endl;
}
}
/**
* 清空BST树
*
*/
template<typename Comparable>
void BinarySearchTree<Comparable>::MakeEmpty()
{
MakeEmpty(root);
}
/**
* 向BST中插入一个元素
*
* @param x 待插入的元素
*/
template<typename Comparable>
void BinarySearchTree<Comparable>::Insert(const Comparable &x)
{
Insert(x, root);
}
/**
* 从BST中删除一个元素
*
* @param x 被删除的元素
*/
template<typename Comparable>
void BinarySearchTree<Comparable>::Remove(const Comparable &x)
{
Remove(x, root);
}
/**
* 向树根为t的树中插入一个元素
*
* @param x 待插入的元素
* @param t 树根
*/
template<typename Comparable>
void BinarySearchTree<Comparable>::Insert(const Comparable &x, BinaryNode<Comparable> *&t) const
{
if (t == NULL)
{
t = new BinaryNode<Comparable>(x, NULL, NULL, -3);
}
else if (x < t->element)
{
Insert(x, t->left);
}
else if (x > t->element)
{
Insert(x, t->right);
}
else
; //dupicate; you can do something, of course
}
/**
* 从树根为t的树中删除元素
*
* @param x 被删除的元素
* @param t 树根
*/
template<typename Comparable>
void BinarySearchTree<Comparable>::Remove(const Comparable &x, BinaryNode<Comparable> *&t) const
{
if (t == NULL)
{
return;
}
else if (x < t->element)
{
Remove(x, t->left);
}
else if (x > t->element)
{
Remove(x, t->right);
}
else if (t->left != NULL && t->right != NULL)
{
t->element = FindMin(t->right)->element;
Remove(t->element, t->right);
}
else
{
BinaryNode<Comparable> *oldNode = t;
t = (t->left != NULL) ? t->left : t->right;
delete oldNode;
}
}
template<typename Comparable>
BinaryNode<Comparable>* BinarySearchTree<Comparable>::FindMin(BinaryNode<Comparable> *&t) const
{
if (t != NULL)
{
while(t->left != NULL)
t = t->left;
}
return t;
}
template<typename Comparable>
BinaryNode<Comparable>* BinarySearchTree<Comparable>::FindMax(BinaryNode<Comparable> *&t) const
{
if (t != NULL)
{
while(t->right != NULL)
t = t->right;
}
return t;
}
template<typename Comparable>
bool BinarySearchTree<Comparable>::Contains(const Comparable &x, BinaryNode<Comparable> *&t) const
{
if (t == NULL)
{
return false;
}
else if (x < t->element)
{
return Contains(x, t->left);
}
else if (x > t->element)
{
return Contains(x, t->right);
}
else
return true;
}
template<typename Comparable>
void BinarySearchTree<Comparable>::MakeEmpty(BinaryNode<Comparable> *&t)
{
if (t != NULL)
{
MakeEmpty(t->left);
MakeEmpty(t->right);
delete t;
}
t = NULL;
}
/**
* 前序遍历
*
* @param t
*/
template<typename Comparable>
void BinarySearchTree<Comparable>::PreOrderTraverse(BinaryNode<Comparable> *&t)
{
if (t != NULL)
{
cout << t->element << " ";
PreOrderTraverse(t->left);
PreOrderTraverse(t->right);
}
}
/**
* 中序遍历
*
* @param t
*/
template<typename Comparable>
void BinarySearchTree<Comparable>::InOrderTraverse(BinaryNode<Comparable> *&t)
{
if (t != NULL)
{
InOrderTraverse(t->left);
cout << t->element << " ";
InOrderTraverse(t->right);
}
}
/**
* 后序遍历
*
* @param t
*/
template<typename Comparable>
void BinarySearchTree<Comparable>::PostOrderTraverse(BinaryNode<Comparable> *&t)
{
if (t != NULL)
{
PostOrderTraverse(t->left);
PostOrderTraverse(t->right);
cout << t->element << " ";
}
}
/**
* @class AVLTree
* @brief 由于AVLTree本身是一种改进的BST树，所以绝大多数特性继承自BST树。其中的Insert()和Remove方法和BST树中不同，因此在BST类中将此方法声明为virtual function
*/
template<typename Comparable>
class AVLTree : public BinarySearchTree<Comparable>
{
public:
AVLTree();
~AVLTree();
int GetHeight();
void Insert(const Comparable &x);
void Remove(const Comparable &x);
protected:
int GetHeight(BinaryNode<Comparable> *&t);
void Insert(const Comparable &x, BinaryNode<Comparable> *&t);
void Remove(const Comparable &x, BinaryNode<Comparable> *&t);
void SingleRotateLeftChild(BinaryNode<Comparable> *&k2);
void SingleRotateRightChild(BinaryNode<Comparable> *&k2);
void DoubleRotateLeftChild(BinaryNode<Comparable> *&k3);
void DoubleRotateRightChild(BinaryNode<Comparable> *&k3);
void Balance(BinaryNode<Comparable> *&t);
};
/**
* 构造函数，调用BST基类的构造函数
*
*
* @return
*/
template<typename Comparable>
AVLTree<Comparable>::AVLTree() : BinarySearchTree<Comparable>::BinarySearchTree()
{
// BinaryNode<Comparable>* root = BinarySearchTree<Comparable>::GetRoot();
// root = NULL;
}
/**
* 析构函数，调用基类的BST::MakeEmpty()
*
*
* @return
*/
template<typename Comparable>
AVLTree<Comparable>::~AVLTree()
{
BinarySearchTree<Comparable>::MakeEmpty();
}
/**
* 得到整棵AVL树的高度
*
*
* @return
*/
template<typename Comparable>
int AVLTree<Comparable>::GetHeight()
{
BinaryNode<Comparable>*& root = BinarySearchTree<Comparable>::GetRoot();
return GetHeight(root);
}
/**
* 向AVL中插入元素x
*
* @param x 待插入的元素
*/
template<typename Comparable>
void AVLTree<Comparable>::Insert(const Comparable &x)
{
BinaryNode<Comparable>*& root = BinarySearchTree<Comparable>::GetRoot();
Insert(x, root);
}
/**
* 从AVL中删除元素x
*
* @param x 被删除的元素
*/
template<typename Comparable>
void AVLTree<Comparable>::Remove(const Comparable &x)
{
BinaryNode<Comparable>*& root = BinarySearchTree<Comparable>::GetRoot();
Remove(x, root);
}
/**
* 得到结点t的高度
*
* @param t
*
* @return
*/
template<typename Comparable>
int AVLTree<Comparable>::GetHeight(BinaryNode<Comparable> *&t)
{
return t == NULL ? -1 : t->height;
}
template<typename Comparable>
void AVLTree<Comparable>::Insert(const Comparable &x, BinaryNode<Comparable> *&t)
{
if (t == NULL)
{
t = new BinaryNode<Comparable>(x, NULL, NULL);
}
else if (x < t->element)
{
Insert(x, t->left);
Balance(t);
// if (GetHeight(t->left) - GetHeight(t->right) == 2)
// {
// if (x < t->left->element)
// {
// SingleRotateLeftChild(t);
// }
// else
// DoubleRotateLeftChild(t);
// }
}
else if (x > t->element)
{
Insert(x, t->right);
Balance(t);
// if (GetHeight(t->right) - GetHeight(t->left) == 2)
// {
// if (t->right->element < x)
// {
// SingleRotateRightChild(t);
// }
// else
// DoubleRotateRightChild(t);
// }
}
else
;
t->height = max(GetHeight(t->left), GetHeight(t->right)) + 1;
}
/**
* 有个小bug，弄了一天也没弄出来，可能问题在Balance()和指针的引用上
*
* @param x
* @param t
*/
template<typename Comparable>
void AVLTree<Comparable>::Remove(const Comparable &x, BinaryNode<Comparable> *&t)
{
static stack<BinaryNode<Comparable>*> tStack;/// 定义一个静态堆栈，存储访问结点的路径
int tSize = tStack.size();/// 得到栈的大小
if (t == NULL)
{
return;
}
else if (x < t->element)
{
tStack.push(t);
cout << "traverse through " << t->element << endl;
Remove(x, t->left);
}
else if (x > t->element)
{
tStack.push(t);
cout << "traverse through " << t->element << endl;
Remove(x, t->right);
}
else if (t->left != NULL && t->right != NULL)
{
tStack.push(t);
cout << "traverse through " << t->element << endl;
BinaryNode<Comparable>*& oldT = t->right;
while (oldT->left != NULL)
{
tStack.push(oldT);
cout << "traverse through " << oldT->element << endl;
oldT = oldT->left;
}
t->element = oldT->element;
Remove(t->element, t->right);
}
else
{
BinaryNode<Comparable>*& oldNode = t;
t = (t->left != NULL) ? t->left : t->right;
delete oldNode;
}
BinaryNode<Comparable>* tempStack;
tSize = tStack.size(); /// 更新堆栈大小
for (int i = 0; i < tSize; i++)
{
tempStack = tStack.top();/// 回溯访问结点
Balance(tempStack);/// 对每个结点做Balance处理
tStack.pop();/// 已经做过Balance处理的结点出栈
}/// 此处可以进一步优化
return ;
}
template<typename Comparable>
void AVLTree<Comparable>::SingleRotateLeftChild(BinaryNode<Comparable> *&k2)
{
BinaryNode<Comparable> *k1 = k2->left;
k2->left = k1->right;
k1->right = k2;
k2->height = max(GetHeight(k2->left), GetHeight(k2->right)) + 1;
k1->height = max(GetHeight(k1->left), k2->height) + 1;
k2 = k1;
}
template<typename Comparable>
void AVLTree<Comparable>::SingleRotateRightChild(BinaryNode<Comparable> *&k1)
{
BinaryNode<Comparable> *k2 = k1->right;
k1->right = k2->left;
k2->left = k1;
k1->height = max(GetHeight(k1->left), GetHeight(k1->right)) + 1;
k2->height = max(k1->height, GetHeight(k2->right)) + 1;
k1 = k2;
}
template<typename Comparable>
void AVLTree<Comparable>::DoubleRotateLeftChild(BinaryNode<Comparable> *&k3)
{
SingleRotateRightChild(k3->left);
SingleRotateLeftChild(k3);
}
template<typename Comparable>
void AVLTree<Comparable>::DoubleRotateRightChild(BinaryNode<Comparable> *&k1)
{
SingleRotateLeftChild(k1->right);
SingleRotateRightChild(k1);
}
/**
* 计算t的平衡因子，分为四种不同情况分别调用不同函数处理
*
* @param t 树根
*/
template<typename Comparable>
void AVLTree<Comparable>::Balance(BinaryNode<Comparable> *&t)
{
if (GetHeight(t->left) - GetHeight(t->right) == 2)
{
if (GetHeight(t->left->left) > GetHeight(t->left->right))
{
SingleRotateLeftChild(t);
}
else if (GetHeight(t->left->left) < GetHeight(t->left->right))
{
DoubleRotateLeftChild(t);
}
else
;
}
if (GetHeight(t->left) - GetHeight(t->right) == -2)
{
if (GetHeight(t->right->right) > GetHeight(t->right->left))
{
SingleRotateRightChild(t);
}
else if (GetHeight(t->right->right) < GetHeight(t->right->left))
{
DoubleRotateRightChild(t);
}
else
;
}
}
#endif /* _BINARYSEARCHTREE_H_ */
main.cpp:
#include "BinarySearchTree.h"
using namespace std;
int main(int argc, char *argv[])
{
int a[10] = {5, 9, 10, 1, 3, 6, 4, 7, 8, 2};
AVLTree<int> avl;
avl.BuildBinaryTree(a, 10);
avl.Insert(11);
avl.TraverseTree(0);
avl.Remove(9);
avl.TraverseTree(0);
avl.Remove(10);
avl.TraverseTree(0);
return 0;
}
计算几何悲剧归
计算几何悲剧归……
感觉考试很难。当然与自己复习不当也有关系。昨天从hjc冰窖一般的图书馆回到温暖的寝室后身体就一直没缓过劲，感觉有些胸闷气短，看书愣是看不下去，虽然我明知道考试在即，而自己还没怎么复习。觉得自己平时的assignment交了，midterm考的个人感觉也还行，怎么着也不会挂。结果今天看了考卷就知道悲剧了。midterm都是书上的概念，考卷却都是乱七八糟没怎么见过的东西。也罢，东拼拼西凑凑，蒙了不少。但愿老师宽宏大量，我给您烧高香了。
看来，以后不能乱选课，选了课以后不能随便跷课。
而且我也发现，学术这条路我差不多走到尽头了。尽管这两个月自己很努力，但是似乎成效不大。而我对每周按部就班的上课又提不起兴趣，一门普通的如计算几何，计算机组成等课程就把我搞的焦头烂额，叫苦不迭。呃……
我的学习基本属于兴趣驱动。兴趣来了，就会去看很多很多的东西，哪怕它与课程不相关，甚至因此耽误了复习，导致成绩低下等等。算了，还是尽快毕业吧。
考试周几日一直在hjc，奈何遇上冰冻天气，在hjc图书馆冻的不行，叫苦不迭，不过大概低温使人清醒，使人难于犯困，所以效率还是有保障的。第一天复习了汇编语言，看的是清华大学那本经典的《IBM PC机汇编语言教程》，基本熟悉了程序的结构，各种模式。但是让我写一个象样的程序还有些小困难。汇编很难，难就难在将人脑变成电脑来使用。对此我兴趣不大。希望课程能够得过且过吧。
后三天主攻图形学，看opengl。三天的研究颇有成效，一股成就感油然而生，上几张图吧：
这张图看上去很炫，其实是在GL_SINGLE单缓冲模式下让一个三角形以一定的速率旋转而成。在这个过程中不要清除GL_COLOR_BUFFER_BIT就行了。
一个三角形的三个顶点绕v=(1,1,1)旋转而成。不要清除GL_COLOR_BUFFER_BIT。
加了小虫子的纹理填充（不知道这样说是不是正确）。
一个三维的立体cube。我觉得很漂亮。呵呵。
球体和正方体都可以旋转并且同时放大或者缩小。键盘控制旋转方向。
图形学第三次作业，我自己加了个功能，就是可以让茶壶跳起来，呵呵。也是由键盘控制的。蛮有趣的。顺便把源码发上来，做个备份好了：
* @file opengl_exp3.c
* @author <lox@freelox>
* @date Wed Nov 18 18:01:43 2009
*
* @brief This program illustrate the opengl 3d transformation, such as modelview transformation, projection
* transformation, and some opengl animation skills
*
*
*/
#include <GL/glut.h>
#include <stdlib.h>
#include <math.h>
#include <stdio.h>
#define PERS 0 /**< define the perspecive projection method */
#define ORTHO 1 /**< define the orthogonal projection method */
#define WIRE 0 /**< draw the object with wire */
#define SOLID 1 /**< draw the object with solid fill color */
static int winWidth = 0; /**< the new view width */
static int winHeight = 0; /**< the new view height */
static int projection = PERS; /**< determine whether perspective or orthogonal */
static int drawMethod = 1; /**< determine the draw method */
static float cameraX = 0; /**< the x position of the camera */
static float cameraY = 1.0; /**< the y position of the camera */
static float cameraZ = 10; /**< the z position of the camera */
static float teapotX = 0.0; /**< the x position of the teapot */
static float teapotY = 1.2; /**< the y position of the teapot */
static float teapotZ = 0.0; /**< the z position of the teapot */
static float teapotRotateY = 0.0; /**< the rotation degree of the teapot along y axis */
/**
* I myself add a jump function to the teapot use i and ty[15]
*/
int i = 0;
float ty[15] = {1.3, 1.4, 1.6, 1.9, 2.3, 3.0, 3.3, 3.4, 3.42, 3.4, 3.3, 3.0, 2.3, 1.5, 1.2};
/**
* @brief just init the background color
*
*/
void init()
{
glClearColor(0.0, 0.0, 0.0, 0.0);
}
/**
* @brief draw one leg of the Desk
*
*/
void drawLeg()
{
glPushMatrix();
glScalef(1.0, 3.0, 1.0);
glutSolidCube(1.0);
glPopMatrix();
}
/**
* @brief draw the desktop
*
*/
void drawDesktop()
{
glPushMatrix();
glScalef(5.0, 1.0, 4.0);
glutSolidCube(1.0);
glPopMatrix();
}
/**
* @brief draw the whole desk through drawing four legs and one desktop
*
* @see drawDesktop
* @see drawLeg
*/
void drawDesk()
{
glPushMatrix();
drawDesktop();
glPopMatrix();
glPushMatrix();
glTranslatef(-1.5, -2, -1);
drawLeg();
glPopMatrix();
glPushMatrix();
glTranslatef(1.5, -2, -1);
drawLeg();
glPopMatrix();
glPushMatrix();
glTranslatef(1.5, -2, 1);
drawLeg();
glPopMatrix();
glPushMatrix();
glTranslatef(-1.5, -2, 1);
drawLeg();
glPopMatrix();
}
/**
* @brief draw the whole scene
*
* @see drawDesk()
*/
void drawScene()
{
drawDesk();
glPushMatrix();
glTranslatef(teapotX, teapotY, teapotZ);
glRotatef(teapotRotateY, 0.0, 1.0, 0.0);
glutSolidTeapot(1.0);
glPopMatrix();
}
/**
* @brief display the three sides of the desktop
*
* @see drawScene();
*/
void display()
{
glClear(GL_COLOR_BUFFER_BIT | GL_DEPTH_BUFFER_BIT);
glColor3f(1.0, 1.0, 1.0);
glLoadIdentity();
gluLookAt(cameraX, cameraY, cameraZ, 0.0, 1.0, 0.0, 0.0, 1.0, 0.0);
if(drawMethod == SOLID)
{
glPolygonMode(GL_FRONT_AND_BACK, GL_FILL);
}
else
{
glPolygonMode(GL_FRONT_AND_BACK, GL_LINE);
}
glEnable(GL_DEPTH_TEST);
glEnable(GL_LIGHTING);
GLfloat white[] = {1.0, 1.0, 1.0, 1.0};
GLfloat light_pos[] = {3,5,5,1};
glLightfv(GL_LIGHT0, GL_POSITION, light_pos);
glLightfv(GL_LIGHT0, GL_AMBIENT, white);
glEnable(GL_LIGHT0);
drawScene();
glFlush();
glutSwapBuffers();
}
/**
* @brief update the viewport of the whole scene when press a special key
*
* @param width the width of the new viewport
* @param height the height of the new viewport
*/
void updateView(int width, int height)
{
glViewport(0, 0, (GLint)width, (GLint)height);
glMatrixMode(GL_PROJECTION);
glLoadIdentity();
if (projection == PERS)
{
glFrustum(-1.0, 1.0, -1.0, 1.0, 0.5, 40.0);
}
else if (projection == ORTHO)
{
glOrtho(-10.0, 10.0, -10.0, 10.0, 0.5, 40.0);
}
else
{
projection = PERS;
}
glMatrixMode(GL_MODELVIEW);
}
/**
* @brief glut reshape function
*
* @param width
* @param height
* @see updateView()
*/
void reshape(int width, int height)
{
if (height == 0)
{
height = 1;
}
winWidth = width;
winHeight = height;
updateView(winWidth, winHeight);
}
/**
* @brief glut idle function
*
*/
void idle()
{
glutPostRedisplay();
}
/**
* @brief control the keyboard interactive actions
*
* @param key the key which pressed
* @param x the x mouse position
* @param y the y mouse position
*/
void keyboard(unsigned char key, int x, int y)
{
switch(key)
{
case 27:
case 'q': /**< press q or ESC to quit this program */
{
exit(0);
break;
}
case 'p': /**< press x to switch between perspective and oothogonal view */
projection = (projection + 1) % 2;
updateView(winWidth, winHeight);
break;
case 't':
drawMethod = (drawMethod + 1) % 2;
break;
case 'a': /**< press a to adjust camera position along negative x axis */
cameraX--;
break;
case 'd':
cameraX++;
break;
case 'w':
cameraY++;
break;
case 's':
cameraY--;
break;
case 'z':
cameraZ++;
break;
case 'c':
cameraZ--;
break;
/**
* operations about teapot
*
*/
case 'l': /**< move the teapot along positive x axis */
if (teapotX >= 2.5) /**< the teapot cannot be moved out of the desktop */
{
teapotX -= 2.5;
}
teapotX += 0.1;
break;
case 'j':
if (teapotX <= -2.5)
{
teapotX += 2.5;
}
teapotX -= 0.1;
break;
case 'i':
if (teapotZ >= 2.0)
{
teapotZ -= 2.0;
}
teapotZ += 0.1;
break;
case 'k':
if (teapotZ <= -2.0)
{
teapotZ += 2.0;
}
teapotZ -= 0.1;
break;
case 'e':
teapotRotateY ++;
break;
case 'o': /**< make the teapot jump on the desktop */
teapotY = ty[i++];
if (i >= 15)
{
i -= 15;
}
}
glutPostRedisplay();
}
/**
* @brief main function
*
* @param argc
* @param argv
*
* @return 0
*/
int main(int argc, char** argv)
{
glutInit(&argc, argv);
glutInitDisplayMode(GLUT_DOUBLE | GLUT_RGB | GLUT_DEPTH);
glutInitWindowSize(500, 500);
glutInitWindowPosition(100, 100);
glutCreateWindow("Simple opengl 3d modelview program");
init();
glutDisplayFunc(display);
glutReshapeFunc(reshape);
glutKeyboardFunc(keyboard);
glutIdleFunc(idle);
glutMainLoop();
return 0;
}
思路还是蛮清晰的。理解起来也不是很难。这三天看了很多的资料，觉得自学的好处就是可以接触大量的资料，从多方面对同一个问题有更好的理解，但是缺点就是太耗费时间了。有些问题老师一句话就可以点明白，但是自己探索却要好长时间。不过我很享受这种探索的乐趣。
前几日耗费了一天多的时间看完了开复自传《世界以你不同》，感慨颇多。毫无疑问，开复是幸运的，他有着良好的家庭条件，及早的接受了美国先进的教育，在那里又碰到了很多对他未来起着决定性作用的好老师，如教他英语的中学老师，他的大学课上说了那句“make a difference"的哲学老师，“不同意却支持他”的博士导师。正是这些人将开复推向了人生的顶峰。最喜欢的是开复的座右铭：
用勇气去改变那些可以改变的事情，用胸怀来接纳那些不能改变的事情，用智慧来辨别两者的不同“
说的非常好。开复精彩的一生就是这句话的写照。做任何事情总是"lead my heart"，这样的人活的潇洒、惬意。
但是并不是所有人都能像开复一样。所以我觉得人生二字，唯机遇与奋斗两字。机遇是先天的，可遇而不可求，奋斗是后天的，自己可以掌控。你不可能指望偏远山区一个放牛的娃子去做科学研究，也不能指望有了机遇坐山吃空就能如何如何。哪些是机遇哪些需要奋斗，这需要用智慧来辨别。
每次去88逛work、careerlife版块，就会给自己点压力。我告诉自己，要通过自己的努力，找到一份自己喜欢的工作，可能的话开创一片属于自己的事业。在海边有自己的一幢房子，落地大窗，听着海浪的声音入睡。四十岁之前赚足够多的钱，留下一部分，剩下的捐给需要钱的人，然后辞职，追随我心，去做自己想做的事情。这件事情可能是旅行，可能是慈善，可能是教育，或者是自己的事业。等等。
网上有句话，当今的中国是政治精英、文化精英、经济精英三足鼎立，想想还是蛮形象的。自己该选择那个呢？政治自己是干不来了。对所谓的马列毛邓着实感到恶心。文化，经济，如果二者选一，我还是选择后者吧。我已经失去了对学术探索的热情和雄心了。
两个月之前，浙大海归博士涂序新跳楼自杀，引起来学术界的轩然大波。越长大越孤单，随着年龄的增大，社会也在逐渐掀开那层层的面纱。当代中国人活的太辛苦了。我只能这么说，这么说是因为我只知道中国。我觉得中国人活的很辛苦。别的国家我没有去过，没有切身感受。所以我喜欢旅行，我想要看看这大千世界。
又罗嗦了这么多。吃饭去了。
草泥马的中国移动
仗着智商高就推出使出各种手段忽悠，各种套餐咋呼，各种**通，各种sp乱收费，糊弄群众。
我不就是随便上上网么，干嘛每个月扣我几十块钱的sp费用？
我不电话告诉你把sp业务关了嘛，怎么这个月还有？
收费起码也让我明白一点，给我条短信通知下啊？
再说什么狗屁漫游，凭啥从这个省跨到那个省就要多收几倍的价钱啊？那卫星不都是围着地球转么？那土地不都是中国的嘛？不就是几个计算机之间相互交流了点1011，你想钱想疯了啊？
马云说企业应该有种社会责任感，你的社会责任感在哪里？我看中国的垄断国有企业都是一个揍性。据说今年五百强的利润比美国还高，好像多骄傲似的。我说你们移动银行能不能改善下对firefox的网页支持啊？嗯？人家美国企业赚的是世界人民的钱，你们这些垄断剥削的全部是中国老百姓的血汗钱。有本事你们也去国外闯荡闯荡，赚赚美国佬的钱？靠垄断在国内剥削算什么本事。中石油，中石化，中移动，中联通，**的代名词。