行者无疆 始于足下 - 行走，思考，在路上

打造高效的工作环境(番外篇1): windows/linux钗黛双收

前两篇文章基本上都在对Windows进行各种吐槽，最近Win8消费者预览版的出现更是让我对我的吐槽充满了信心——微软已经堕落到需要靠五颜六色的砖块来吸引眼球的地步了。我虽然没有亲身体验过Metro UI，但是我依然坚持，Metro UI是个无比糟糕的设计，一个彻头彻尾的倒退。颠覆传统、回归本原？是回归到Windows 3.x时代吗？一眼望去，Metro UI似乎很绚烂，像焰火漫天的夜空，但是稍不留意，作为使用者的我们就很容易迷失在图标的海洋里面。在我的印象中，直角化的图案一直是设计里的禁忌之一，而为了弥补这个缺憾（或者说是对传统的颠覆），Metro采用了大量的颜色来填充一个又一个的砖块，使得这些砖块能够不至于“迷失自我”。

我认为一个良好的使用界面应该要有统一的风格，至少不能有太多的颜色，而不是像一个调色版一样令人眼花缭乱；圆角在舒适的用户体验中是不可缺少的，可惜苹果在前，*nix在后，微软在UI设计方面的创新已经没有太多可选的余地，只能走一个极端来玩一场赌博；前两年的Ribbon界面应该是Metro设计的一个铺垫，我认为Ribbon确实是个不错的创新，能够将大量的MS Office小白用户从繁杂的菜单中解放出来，但是Metro实在太过了；最苦的应该是Windows开发者，唉，三年一小改、五年一大改是微软的一贯风格。

不过这些对我都不重要，重要的是我相信，即便我对Windows吐槽了这么多，许多朋友还是小心翼翼，不敢投入Linux的怀抱。正常，因为Linux的门槛确实不低，加上一大堆的概念和思维的转变，再补上如百花从般绚烂多彩的发行版和如满天繁星般闪亮的各种大小bug瑕疵，足以令80%的初学者望而却步。而我又不想让我的文章太过小众（我在开篇中说过，这一系列的文章主要面对以Linux系统为工作环境的初级Coder，兼带高级电脑使用者）。因此，我总结了一些变通的方法，让你可以在你的Windows系统上无痛地尝尝Linux的鲜。

本文主要针对那些想要尝试下Linux但又怕损坏自己Windows的工作平台的同志。当然，本文的重点还是命令行环境的建立，因为熟练掌握命令行是高效使用Linux的必由之路。而至于图形界面，由于Windows Explorer的顽固存在，Windows下的GUI没什么可折腾的。除了虚拟机，似乎没有什么特别完美的办法能够在不切换系统的情况下体验Linux的图形界面。

本文主要介绍一些简单易行的方法手段，能够在Windows下建立一套相对完整的Linux命令行实验环境，为后面系列的文章奠定一个基础，并借此扩大下本系列文章的“打击面”。

1 Cygwin

  • What：通俗的讲，Cygwin是Windows上的一个模拟软件，最初是由Cygnus Solutions公司开发的。
    • Cygwin通过对Windows API的整合封装模拟出一套POSIX API。有了这套基础性的POSIX API（就是Linux C编程的什么fork/wait啊、signal啊、open/close啊这套东西），再加上一套合适的交叉编译器（就是大名鼎鼎的GCC了），就有了在Windows上模拟运行*nix软件的基础。
    • Cygwin本身也包含了很多常用的自由软件，包括核心的bash、coreutils、findutils等，配合Cygwin/X这个东西，甚至可以直接运行许多X Windows上的软件，包括Emacs，gvim等等。
  • How：1
  • Pros：傻瓜式安装；可以和host文件系统方便互通。
  • Cons：没有类似于apt-get这种杀手级的软件包管理工具，安装一些额外的软件颇费周折，而且官方软件库更新较慢。
  • 可用性：3星。
    • 很多以linux为推荐运行平台的软件也支持在Cygwin上开发测试，比如hadoop
  • 结论：如果只是看看Linux的命令行长什么样子，那么本文看到这里就可以了。

2 SUA

  • What：SUA是Windows的一个subsystem，提供一些基本的POSIX API，在此基础上提供一些简单的*nix程序，诸如vi、ksh、csh、ls、cat等。
  • How：@see 这里
  • Pros：SUA是微软自家的东西。
  • Cons：除了Pros之外都是缺点。
    • 软件稀少，版本低无法扩展是致命伤。我只用过一次就甩了。
  • 可用性：1星，玩具而已，未见日常使用
  • 结论：了解即可

3 虚拟机

  • What：虚拟机大概是最常用也最方便的方式了吧，虽然虚拟机本身的水非常深。我第一次接触虚拟机的概念还是在大一上，那个时候自己还在熟悉怎样更好更快地安装Windows操作系统，Virtual PC自然而然就成了我的好伙伴，而我也为能在Virtual PC下顺利安装一个MS DOS 7.1感到欣喜不已。后来接触到了VMware，它有两个显著的特性，一大特性是强，另一大特性就是卡。VirtualBox是我的最爱，轻量快速，乃居家旅行杀人越货必备良品。
  • How：准备10G硬盘空间就OK。
    • VirtualBox有一些非常给力的特性：
  • Pros：虚拟机能够给你100%原生的Linux观感和体验，而且使用过程中无毒无害，更不用担心将系统不小心搞挂，配合上VirtualBox的文件共享功能和全屏功能，再加上一个稍微给力点的电脑2，有时候能够达到以假乱真的效果。
  • Cons：性能上还是有些损失的；除了VMware，其余虚拟机软件好像没有特别方便的方法支持bridge network，有时候很不方便。
  • 可用性：4星
  • 结论：VirtualBox乃居家旅行杀人越货必备良品。

4 Colinux

  • What：Cooperative Linux, abbreviated as coLinux, is software which allows Microsoft Windows and the Linux kernel to run simultaneously in parallel on the same machine. 简单而言，coLinux和VirtualBox这类虚拟软件最大的区别在于，coLinux运行的linux系统是何Windows宿主系统共享系统资源的3，因此其性能对比VirtualBox这类虚拟机软件要好很多。
  • How：coLinux本身的安装还是要非一番周折的。幸运的是，万能的社区提供了两个打包好的一键安装方案，那就是andLinux和Topologilinux。我只用过andLinux，推荐。
    • coLinux可以通过samba和windows系统共享文件。
    • 可以将coLinux做成随系统启动的一个服务，并且在coLinux里面开始sshd进行，之后用putty这类软件连接ssh，就可以全面享受linux命令行运指如飞的畅快了。
    • 如果你以前没有用过apt-get这个程序，这次不要错过，因为集中化的软件管理机制是linux(debian/ubuntu的apt-get)的杀手级特性，也是我的最爱。
  • Pros：除了Cons都是Pros。
  • Cons：None。
  • 可用性：5星。
  • 结论：这是我大三暑假在华数淘宝实习时跟一位高手偷师过来的，最爱，强烈推荐。

5 其余解决方案

除了以上谈到的，KDE for Windows是在Windows上体验KDE桌面环境的一种可行的方案，虽然其目前bug依然多多；如果你玩腻了以上所有，想装个真家伙，又怕手生一不小心误删重要文件，那么Ubuntu Wubi应该是一个不错的解决方案。如果你已经开始讨厌Ubuntu Wubi了，那么恭喜你，你已经成功地被我忽悠，进入*nix的精彩世界，just enjoy it。

--

Footnotes:

1 什么？你不会问我Cygwin要怎么安装吧？

2 不够2G内存的同志赶紧去花钱加内存吧，当然，有双屏更好。

3 coLinux运行的linux系统需要对内核进行特殊的修改。当然，关于这种修改本身和coLinux背后的原理已经远远超出了本文讨论的内容和本人的技术水平，还请高手不吝赐教。

Linux linux virtualbox windows cygwin colinux Comments(6) Sat, 02 Jun 2012 21:56:33 +0800

打造高效的工作环境(2): 高效的文件管理

1 为什么Windows的文件系统混乱、低效？

让众位久等了！上篇Why Windows Sucks的吐槽文中，我曾谈到，Windows文件系统几点令我非常不喜欢的地方：

  • 文件系统多盘拼，文件命名大小混
  • 权限控制小烦躁，命令终端很废柴

本篇我们稍微深入探讨一下这个话题，并由此引入我们接下来系列文章的主角，*nix。

上小学的时候我们就知道，Windows的第一个盘是C盘。如果你稍微研究下所谓“Windows提速优化”这类的教程，你就会知道C盘是所谓的系统盘，非常重要。如果你足够细心，并且有足够的耐力，那么你可能会学到：

  • 程序尽量不要装在C盘，影响系统运行速度
  • 可以用工具将C盘里的"My Documents"（中文名是“我的文档”）里面的东西转移到别的盘里，这样可以节省很多系统盘的空间，“有可能”使得系统运行更加畅快
  • 定期整理下磁盘碎片，清理下注册表，杀杀毒，可以提高系统运行速度

但是你有没有想过：

  • A盘和B盘哪里去了？
  • 为什么我的系统有C、D、E三个盘而别人的系统除了C、D、E还有F，甚至还有Z盘？
  • 为什么一个电脑的文件系统要分为多个盘呢？
  • 苹果系统需要整理磁盘碎片吗？
  • 注册表到底是干嘛用的？
  • ……

事实上这个世界上本不该有这么多个为什么，一切的一切，源于Windows蹩脚的设计：

  • Windows的文件系统是多根的，这导致你几乎没有办法控制你的移动硬盘的挂载点，几乎没有办法进行chroot高级实验，几乎没有办法制定规范化的类似于*nix下的FHS标准
  • Windows的文件系统目录结构是极其混乱而不统一的，我引用一张表格1来对比说明下*nix和Windows两种文件系统的目录结构，你可以看到，*nix系统目录的命名都非常简洁规律，便于脚本自动化处理，而Windows的文件命名和目录结构像是一层层的石头胡乱堆砌的
     
    Function Linux Microsoft
    Kernel root "WINNT" or "WINDOWS"another page on this site
      /boot  
    Executables /usr/bin "Program Files"
      /usr/lib  
      /usr/share  
      /usr/doc  
      /usr/apps  
    Drivers /dev Win…/System32
    hosts file /etc Win…/System32/Drivers/Etc
    One for each User /usr "Documents and Settings"
      /user  
    Log files /var -
    Temporary work files /tmp Temp
    Optimizing Utilities /opt -
  • Windows的系统文件命名非常混乱，不堪入目，正如“一千个读者心中就有一千个哈姆雷特”一样，一千个Windows C盘就有一千种的文件命名和目录结构，下面是我的正版Windows 7系统下的C盘目录：
    • Windows 7下的C盘：
      • autoexec.bat
      • b7e61efa43ef263f987f6b2dbfe5b362
      • Boot
      • bootmgr
      • BOOTSECT.BAK
      • bootsqm.dat
      • Config.Msi
      • config.sys
      • Documents
      • Download
      • found.000
      • Intel
      • IO.SYS
      • LLabs
      • mfg
      • MSDOS.SYS
      • PerfLogs
      • ppsvodcache
      • ProgramData
      • Program
      • QQDownload
      • $RECYCLE.BIN
      • RRbackups
      • swshare
      • System
      • Temp
      • Users
      • Windows
    • linux下的根目录：
      • bin
      • boot
      • dev
      • etc
      • home
      • lib
      • lib64
      • lost+found
      • media
      • mnt
      • opt
      • proc
      • root
      • run
      • sbin
      • srv
      • sys
      • tmp
      • usr
      • var
  • 合理的文件结构组织和文件命名，对于自动脚本处理是非常重要的，譬如，如果一个文件名称为"My Documents"，那么在脚本处理中，如果不小心编码，这个文件就会被当成"My"和"Documents"两个文件处理。

1.1 历史原因

当然，这种混乱是有一定历史原因的。细细讲来倒是很有意思的一件事情。话说MS80年代初只是主打做Basic语言解释器小的软件公司，后来IBM需要发展PC机，最开始找的是DEC公司的人，但是DEC的老总据说是非常忙，而私人飞机好像出了问题，于是就错过了和IBM的谈判，让MS拣了个大大的便宜。而MS呢，手头是没有成型的操作系统的，就从一个不知名的小公司里面花了5万刀买来了一个系统，并重新命名为MS-DOS，联合Intel和IBM做起了合伙生意，只是IBM没有想到的是，你来我往，几番周折，两个小弟弟MS和Intel成长了起来，在90年代中期其风头甚至盖过了IBM自己。其实谈起计算机的水平和资历，全世界也没有几个敢和IBM叫板的公司，当年IBM 360系统的横空出世，不仅开创了软件工程中众多的“人月神话”，更让无数黑客在360系统的熏陶下成长起来。扯远了，话说回来，MS-DOS呢，是一个非常蹩脚的操作系统，甚至连美国大学里的学生都瞧不惯，说微软是做小儿科系统的公司2。你想一想，90年代的时候，Richard Stevens的APUE都出第一版了，而MS-DOS大概才刚刚摆脱8个字符以下长度文件名的限制。后来呢，苹果抄袭Xerox，搞出了漂亮的GUI，这样一来，微软压力甚大，因为系统底层比不过Unix，表面层GUI又被苹果占了先机，危矣。怎么办好呢？微软开始一面搞Windows，一面联合IBM搞OS/2，同时明修栈道、暗度陈仓，从老的DEC公司挖来一批人开始默默地搞NT（号称"New Technology"的操作系统）。这样一直多战线并存的搞到了Windows 2000的横空出世。话说Windows 2000之所以叫Windows 2000，一方面是因为它是在2000年推出的，另一方面恐怕是搞出Windows 2000确实动用了MS 2000个以上的人力（我猜的，不过几千人的人力是有的）。至此呢，Windows开始一心搞NT。其实这样也好，美中不足的是NT为了兼容以前蹩脚操作系统，背上了很多沉重的历史包袱，这也导致Windows系统更新换代的速度特别的慢。Ubuntu半年推出一个新版本，Mac OS自动X后，10年光景，已经到了X.7的版本，每个版本都有大的提升，而微软闭门造车耗时五年的Vista，还有新进推出的Win7，奋战了这么多年，还是没能将XP第一的宝座纳入囊中，我看MS的系统是江郎才尽，再难突破了3。

而在微软系统的代代更新中，最苦命的算是一直追随MS的程序员了，掏着升级系统和硬件的银子不说，就连自己费尽力气学到的知识，从BASIC、到MS-DOS、到VC++、到MFC，到ASP，到ASP.NET，到C#，也随着微软系统的更新换代灰飞烟灭了……殊不知，*nix下的程序员，纵历风雨，我心永恒。靠着vi+gcc，我就能闯天下。

2 *nix文件系统的优势

相较Windows，*nix的文件系统相对要规范的多，究其根源，在于*nix有一条非常重要的设计哲学，那就是：Everything in Unix is a file：

  • linux的文件系统是单根的，具有一种逻辑意义上的美感。可能有人会问，如果我们新插入一个移动硬盘，我没有盘符，怎么访问？这就是Windows的惯性思维。在Linux中，我们可以随意创建一个目录，然后通过mount命令将起挂载在这个目录点上。事实上有一个叫做fuse4的东西，允许你mount你想得到想不到的很多东西：
    • 见过PB级别的文件系统吗？我见过，在百度，我们通过hadoop的一个fuse模块，将几千台机器组成的PB级的HDFS文件系统挂载到单机硬盘节点上，对外提供ftp服务5
    • 你可以通过SSH挂载远程机器的文件系统6
    • 你还可以挂载一个ftp到本地系统7
    • 你甚至可以将你的Gmail挂载过来，当本地磁盘用8
  • linux的文件命令和文件存放是很有规律的，稍微学习下，你就会知道/bin、/etc、/usr、/home目录的作用，并且，在所有的*nix环境下，都有这些统一规范的目录。
  • linux为每个用户建立一个单独的/home/user主目录，所有用户相关的配置都存放在这个目录下，结合linux下所有几乎所有配置文件都是纯文本这样的特点，带来的好处就是极其简单实用的用户数据迁移过程 ——当你系统崩溃重装的时候，只需要保留/home分区，不用做太多的配置，一切都在：
    • 原先的软件快捷键几乎保持不变
    • vim和emacs的配置不变
    • 甚至连桌面的壁纸都不会变
  • linux中大量采用纯文本的配置文件，相比较于中央集权的注册表方式管理的配置文件， 纯文本文件的好处在于通用性、直观性、可见性和易读性 。虽然文本配置格式多样，但是你已然可以使用你最擅长的工具（哪怕是OpenOffice也行）来查看甚至修改配置文件，并且可以根据个人需要讲这些配置文件放到诸如bitbucket这类SCM系统里面；而对于Windows的注册表，一旦损坏，除了少数几个专有的工具，你就只能双手一撒，重装系统，或者给微软打电话了。

3 一些个人的关于文件组织和管理的Tips

以上，都是关于Windows不好的吐槽以及*nix好的赞扬，没兴趣的看客可以直接忽略，因为下面的内容才是本篇文章的核心所在。

我曾经无数次在学校教室、宿舍和公司的办公桌上，看见各式人等电脑中，一个可怜单薄的桌面上，存放着从txt、doc、docx、ppt，到jpg、png，到rm、mkv，到rar，到"xxxx的快捷方式"等等五花八门的没有八十也有一百个之多的文件。那感觉就像是看到了五湖四海的人们睡到了一张星级宾馆的床上，令人心头一紧、后背发凉。我甚至可以感觉得到他们盯着屏幕、挪着鼠标、眯着双眼寻找某年某月某日的一份word文件的焦躁与辛苦。我甚至还能联想到，这样的人在生活中也多数是邋遢的，他们会随手丢弃东西，经常翻箱倒柜的去寻找某个久远的日子里的一个小物品。

不是这样的，正确高效的文件组织管理绝对不该是这样的。我相信，即便你没有洁癖，但是看着电脑桌面上那么一坨乱糟糟的东西，心情也会不好的。所以我的电脑桌面上向来都是清清爽爽，一个图标都不放。我个人总结了一些粗浅的文件组织管理的小技巧，经过两年多的实战，效果还是不错的：

3.1 规范同一的文件命名

  • 尽量使用小写的文件命名
  • 尽量使用英文单词命名（良好的英文水平是优秀Coder的必要条件）
  • 如果文件名是多个单词，用下划线_将多个单词连接起来，千万不要留有空格，对脚本化的文档处理非常不利

3.2 良好和谐的目录结构

  • documents：主要存放各种文档，包括但不限于各种工作简历啊、考试进度啊、学校通知啊，诸如此类，定期删除过期文档，将有学习价值的文件转移到study文件夹下
  • downloads：主要存放Firefox等Internet软件的下载资源，有价值的资源及时转移，没有价值的资源及早删除
  • media：主要存放各种多媒体资源，重点用户轻松娱乐，三个子文件夹：
    • musics: 存放喜欢的音乐，将这个文件夹导入Amarok或者你喜欢的播放器软件即可
    • pictures：主要存放个人照片和网上的一些有趣有意义的图片
    • videos：各种电影，我非常喜欢看电影哈，可惜电脑硬盘空间不够，加上我决定要逐步完善自己的版权意识，所以存量有限
  • mnt：用于临时挂载一些U盘的目录
  • programming：用于自己学习编程的目录，我现在用BitBucket管理自己的代码，每个bitbucket上的repository都对应于这个文件夹下的一个子目录
  • software：用于存放一些有用的软件，其实这个没啥必要，因为linux主流distribution的软件库一般都非常完善，只要有好的网络环境，想装什么软件（哪怕同时装几十个软件）只是一条命令或者一次鼠标点击的事情
  • study：存放自己有电脑以来收集到的各种学习资料和自己大学里的各种作业、ppt、文档等等，分门别类，定期整理删除
  • tmp：我自己的tmp目录，用于临时创建一些不重要的测试文件，常见场景是我需要测试一些C语言或者TeX或者Python里面的某个特性，因此临时创建一个小文件，编译运行下，看看效果
  • tools：用于存放自己写的一些系统管理的小工具，比如我自己写的SSH翻墙脚本、设定笔记本电池充电阀值的脚本等等

4 接下来

按照原本的写作计划，在本篇文章的基础之上，我将在接下来的三篇文章中谈到三个主题：

  • Just Find it: Findutils，介绍*nix的小工具，帮助你在文件的海洋中傲游穿梭，包括但不限于：
    • 如何迅速而准确的定位你想要的寻找的文件
    • 如何迅速而准确的在历史的目录树中进行切换穿梭
    • 如何仅仅借助Shell工具，在一个Open Source的代码库中，寻找一个变量的出现位置，并且能够找出到底是哪个文件包含了这个变量的使用
    • 如何删除某个目录下所有以.bak结尾并且修改时间在n天内的所有文件
  • 细谈文本配置，文本配置是"Everything in Unix is a file"的一个重要体现，对应于Windows的注册表，文本化的配置文件大大简化了*nix系统管理工作，这篇主要会介绍：
    • *nix系统中一些重要的配置文件
    • 以及相关的配置文件的配置格式
    • 配置文件跨系统的迁移和保存
    • 以XML/JSON/YAML为例介绍下常见的几种文件配置格式，有可能的话，初步介绍下Lisp中"Code is Data"的扩展概念
  • Shell之道，初步介绍下*nix Shell编程的一些入门要点，并直接转入Shell编程的精华——管道。可能的话，会在此基础上展开探讨下进程间通信的一些思考。

敬请期待！

--

Footnotes:

1 参考Operating Systems & Commands，这篇文章详细对比了*nix和Windows两种系统之间的差异。

2 参考《软件随想录》（阮一峰译），P65，《在耶鲁大学的演讲》。

3 以上言论，多有戏谑成分，众位看官一笑而过，切莫当真。

4 关于Linux中FUSE模块的设计思路，可以参考徐宥写的编程珠玑番外篇-K. Plan 9 的故事（修订版），徐宥写的这一系列文章水平很高，趣味盎然，强烈推荐。

5 参考MountableHDFS

6 参考sshfs。

7 参考curlftpfs

8 参考GmailFS。

 

Linux linux windows fuse Comments(23) Mon, 27 Feb 2012 01:40:25 +0800

打造高效的工作环境(1)：Why Windows Sucks

1 缘起

这两天我的ArchLinux系统碰到了一个十分诡异的问题，就是电脑无法待机、关机，也无法重启，更令人拍案叫绝的是，电脑在关机重启的过程中，当硬盘停止转动后，整个系统就Hang住了，而屏幕终端还在，只是不再响应任何请求。解决这个问题的唯一办法就是强制关机，但是这种方法实在有失水准，有伤大雅。在尝试了增删内核模块、更新驱动的等多种方法后，我终于在ArchLinux BBS上找到了解决方案。

Google了几个来回，再看一些关于操作系统IT历史的八卦，半个下午就耗掉了，从某种意义上来说，这是在浪费时间。而事实上，如果不算辞掉工作更换电脑被迫地系统调优的那次，我已经至少半年没有进行过OS和软件层面的Tweak工作了。这其中的缘由，大概是由于电脑折腾久了，就会折腾出一套适合自己口味的解决方案，这套解决方案，就是接下来一系列文章的主题——打造高效的工作环境。

打造高效的工作环境，Wow，多么宏大的一个主题啊，不过我见识有限，就这个话题，我只能谈谈电脑相关的知识，和我个人的理解，我不会讲到：

  • 桌上要放几盆草
  • 要不要听轻音乐
  • 开放式的办公空间

等与电脑毫不相关的话题。除此之外，还有一个前提，那就是我的文章主要针对Linux和Mac用户，对Windows用户的参考价值不大。

Why Not Windows？Why Linux？Why Mac？

我100%地相信，在中国，100%的人是通过Windows系统进入电脑的世界的，我也是。但是我也100%地相信，如果你是一个程序员Geek，用Linux或者Mac，会让你的生活变得更美好；如果你只是一个普通的电脑使用者，用Mac或者Linux，至少不会让你的生活变得更差。

说到这里，很多人会跳出来争辩，多数论调是：

  • Linux的驱动如何如何不好
  • Linux的桌面如何如何烂
  • Linux下的软件如何如何不完善
  • Linux下的游戏如何如何匮乏

我的回应是，对于一件事情，对于一件事情，我认为，人的认知有四种状态，分别是：

  • You know you know.
  • You Know you don't know.
  • You don't know you know.
  • You don't know you don't know.

"You know you know"说的是类似于1+1=2这类的常识，首先是你知道"1+1=2"这个知识点，进一步讲，你知道"1+1=2"这个知识点是一个认知事实，而你自己对于这个认知事实也是知晓的，所以归结下来是"You know you know"，说的通俗点，就是“你是知道‘你本人是大学文化，所以会算1+1=2’这个事实的”。

"You know you don't know"说的是我这样的Coder，知道自己水平不够，功力尚浅，不懂得AI，不懂得数据库，不会算法，但好在还有自知之明，所为“吾生而有涯，而知也无涯”，"You know you don't know"，学吧，学到白头学到老。

"You don't know you know"的情况很少见，这种情况常见于某些天赋异禀而不自知的人，就好比练成了九阳神功的张无忌，明明已经武功盖世，却不自知，见到阿猫阿狗也会心底害怕。

"You don't know you don't know"，这句话用来形容那些狂妄自大目中无人之辈真是再合适不过。不过对于常人，我们能否从这句话中得到一些启示呢？当然可以。 事实上，小到一个生活常识，大到一门学科领域，如果你对它不甚了解，甚至完全不知，那么这种"You don't know"有很大的概率是"You don't know you don't know"，而不是"You know you don't know"。仔细想想，这句话揭露了一个可怕的事实，那就是，随着知识爆炸的进行，人类在自己探索创建的辉煌文明成果面前，变得越来越无知；另一方面，人类的的知识再以指数级别的速度增长，但是培养人才的方式却没有本质的进步，这也就意味着现代人才的培养会越来越难1。

扯远了，说了这么多，就一个意思，在你对一个领域、一个知识有充分的调研学习之前，审行慎言。这也是“为什么上帝给了我们两只耳朵却只给了一张嘴巴2”。我个人曾经有过3年的用Linux做主力桌面的经验，其中有50%的时间是整个电脑上只有一个Linux系统，其余双系统并用的时间，98%的时间也是在Linux上，所以对于Linux桌面的情况，我还算有些发言权：

  • Linux的驱动确实是一个软肋，不过情况较2000年左右Redhat 9.0横行的年代已经改善了很多，在这方面，Ubuntu绝对是一个集大成者，现在已经很少找到装上Ubuntu驱动不能用的电脑了，其余的发行版，经过简单配置，也完全可以搞定驱动问题。
  • Linux的桌面已经非常完善了，Linux 并不是只有一个黑黑的令人敬畏的终端。KDE 4.8的设计和整合已经非常完美，各种软件的集成性比Mac有过之而无不及。
  • Linux下的软件如果不比Windows多，至少不会比Windows少。很多优秀的软件诸如Amarok、Digikam、Emacs等等，都是以Linux为首要支持平台的，甚至有的软件只支持Linux，很多工业级别的软件，诸如Hadoop、MySQL、Apache等等，无一不是以Linux为最佳运行平台。
  • Linux下的游戏比较匮乏，这点是不争的事实。

So，说了这么多，信也好，不信也罢，接下来谈谈：

2 Why Not Windows?

作为一个Coder，每次用Windows，我都有一种想要砸掉电脑的冲动。所以毕业设计时，在Windows上运行VMware里面跑着Mac OS X，启动Xcode写Win32 Style风格的程序，那可真是痛不欲生、终身难忘的事前黑暗时代。我搞了首打油诗：

  • 文件系统多盘拼，文件命名大小混 ：Windows是多根文件系统，每个根称作一个盘，而*nix的系统是单根文件系统，新来磁盘只需要在文件系统树上新增个挂载点即可；Windows文件的命名和组织从来没有任何规律，而*nix的文件系统则有一个统一的FHS标准，并且，在Linux下，几乎所有的文件名都是小写字母，并且不含有空格，这对脚本批处理是一个大大的方便之处。
  • 权限控制小烦躁，命令终端很废柴 ：Windows下的文件权限很困惑，我从来没搞明白，好像获得一个文件的某种特殊权限，还要去点击属性窗口；用户权限就更加混乱了，一个Administrator，后来Vista和7又加入了貌似“家长模式”等等，太乱了；*nix下的权限控制则非常简单明了，三条命令如chmod, chgrp, sudo就可以全部搞清楚；Windows下的传统cmd.exe简直废柴的不能再废柴了， 谁能告诉我为什么cmd窗口无法最大化？ 真不明白这到底是哪门子的设计。
  • 弹出窗口满天飞，后台进程到处藏 ：在Windows下还有一点非常让我难受，就是无论是搜狗输入法、迅雷下载，还是QQ、360等，这些软件无一例外，都有一个爱好，就是首先把自己加入系统的启动项，然后呢，在你写代码看片练葵花宝典乾坤大挪移到了关口的时刻，“啪！”的一下给你整几个弹出窗口，放几条八卦新闻……还有那废柴的任务管理器，从来都是杀不掉进程，自己倒先莫名其妙地卡死了，哪里像*nix上的killall -9，手起刀落，快刀展乱麻，痛快痛快。
  • 一家独大搞垄断，格式兼容已败北 ：在格式兼容方面，从来都是*nix下的软件想尽办法兼容Windows的软件，但是Windows一家独大，对于兼容别的系统的软件，从来不屑一顾，举例？OpenOffice，ntfs-3g，数不胜数啊。
  • 病毒木马禁不止，杀毒软件赚钱忙 ：每次我去帮别人修理Windows系统，别人的第一想法都是让我先替他们杀杀毒，可见，病毒和Windows故障一样，在人们的心中难解难分。
  • 硬盘整理除碎片，系统臃肿找管家 ：Windows系统有一个特点，那就是任何系统装好后，都需要“深度优化”，然后才能用得比较舒畅，其中的优化包括但不限于硬盘碎片整理、软件增删、装机必备等等，这也是 为什么各种优化大师、超级兔子、碎片整理等软件“屡禁不止”的原因吧。
  • 万年IE不升级，银行网商耍流氓 ：IE 7.0+新增加了多标签的特性，但是呢，这个多标签特性默认情况下是只启动20%的——除非手工指定，否则点开的链接依然是在新窗口中。退一步讲，就算是手工新开个标签页，但是这个空白标签页的打开简直比乌龟还慢，至少要5秒钟，正是让人“屎可忍，而尿不可忍啊”。至于万年不变的IE6，已经国内众网商网银流氓们的ActiceX插件，我已经无力吐槽了，历史会证明，一个不支持跨平台浏览器的银行网商，绝对会是软件史上的一个笑话，或者说，这是中国银行业的奇耻大辱。
  • 多情自古空余恨，聪明反被聪明误 ：Windows下的很多软件都喜欢自作聪明，典型例子就是Microsoft Word。且不说各种软硬回车，最简单的一个列表，回车之后默认又是一个列表项，但是如果我想新开段落呢？很多人就不知道怎么办了，于是就各种暴力手段地搞排版，排出来的东西，可想而知。我只能说，这种自作聪明，有时候不是真的聪明，是蛮横的自作主张，是对用户意志赤裸裸的强奸啊。

个人吐槽到此结束，详情请进一步参考：

3 Save your life

在接下来的系列文章里面，我会分门别类地介绍我在Linux桌面使用上的一些日常经验，分享自己的一些心得。这些经验之谈对于刚刚踏入Linux大门的同志，以及对于初级Mac用户，甚至部分喜爱折腾的Windows用户，都有很大的参考价值。我觉得，在信息时代，电脑将伴随着我们的一生，高效地使用电脑，就能够在更短的时间内处理更复杂的事情，从而为自己节省出宝贵的时间，去做更有意义的事情，这是一种正向循环；而如果每天纠结于杀毒、木马、弹出窗口、软件破解，则会使你的思维受阻、降低你的工作效率，这是一种负向循环。

这一系列的读者群将以Linux用户为主（重点是Coder），高级Mac用户可以作为参考，对于Windows用户，理解起来可能会有些困难。不过话又说回来，“不经一番寒彻骨，哪得梅花扑鼻香”。我给自己定下如下两个目标：

  • 在键盘上舞蹈
  • 思维不会受阻

至于主题，我初步想了分为如下几个

  • 高效的文件管理
  • Just Find it：Findutils
  • 细谈文本配置
  • Shell之魂：管道
  • Screen：it not a screen
  • Zsh：终极Shell
  • VIM：键盘上跳舞
  • CLI Tools：把玩终端
  • 时光机：版本控制
  • 抛弃Office：LaTeX
  • KDE系列：
    • Kwin
    • Dolphin & Konqueror
    • Konsole & Yakuake
    • Krunner

敬请期待！

–

Footnotes:

1 阮一峰博客：什么是博士

2 这是西方的一句谚语，寓意在于告诫人们要多聆听，少说话

 

Linux linux windows Comments(11) Sun, 05 Feb 2012 18:13:49 +0800

Windows mobile开发总结--文本控件篇

 这个项目是在自己已有的代码基础上，在windows mobile 6.x平台下开发出一套商旅个人助理软件，软件主要内容是世博相关的机票、酒店、火车票、行程安排等，界面要求是仿照Iphone风格。因为客户公司有了Iphone和Android平台上的成品，但是可能时间紧急，又缺乏mobile平台上的控件代码基础，所以找到了我们这边。

原来的代码基础是一套GUI的控件引擎。利用GAPI，从最底层写起，包括最基本的画点画线函数、显存操作函数、窗口管理函数、控件类继承体系等等。这套体系的第一个产品是宁波公安的移动警务系统。去年的时候我也曾经有所了解，但是终究因为自己课业繁忙没有真正参与进来。这次是个机会。

开始的时候我对这套东西很是抵触。一来是我本身不太欣赏windows的哲学。在进入实验室之前的半年都在linux下生活；二是我觉得重新写这么一套东西是"reinvent the wheels"的愚蠢做法。我还像导师建议Qt。坦白的说，虽然我从来没有用Qt写过一个像样的东西，但是Qt的信号与槽机制，感觉要优雅的多；三是除了Qt，MiniGUI据说也不错，为什么要自己大费周章地写这么一个东西呢？而且我虽然很菜，但是写这么一坨代码，我还是能看出很多问题的——虽然让我去写我肯定写不出特别好的东西。

事实上：

  • 我很讨厌某些宏。大量的宏让程序显得莫名其妙。Win32 API中有大量的宏，什么handle, hwnd, COLORREF等等，虽然这些宏归根到底不过是个int，但是我觉得很多时候还是KISS原则最重要。直接用int好了。干嘛这么麻烦。
  • 我很讨厌某些typedef。明明有了标准的true和false，为什么还要自己去定义个GTrue、GFalse和GOK呢？还有GRESULT？这大概是受windows编程风格的影响吧。
  • 我很讨厌注释不全、命名风格糟糕的代码。

当然，GUI框架的设计是一件很复杂的事情。具体来说可以分为三层：

  • 底层引擎层：包括基本的显存操作，画点画线，alpha渲染，图片压缩载入，图形学算法、消息事件处理、字体引擎、布局管理器、窗口管理器等等。
  • 控件层：控件继承体系、文本类控件（标签，单行文本编辑，多行文本编辑域），按钮类（button、list等）、滚动条类、光标类、复杂控件类（菜单、表格等等）
  • 应用层：这个算最简单的了。只要前两层足够稳定，应用层是手到擒来的事情。其余的事情如数据库连接、xml解析、网络连接等等，属于额外附加功能。

这里有份GUI系统需求描述，可以参考一下。嵌入式的GUI框架还是要简单一些。当然，这也与嵌入式系统的硬件条件是息息相关的。

实验室的这套框架主要是仿照Windows消息机制写的。很多东西保留了Win32 API的痕迹。事实上底层引擎是不可能脱离具体的操作系统而存在的。跨平台的原理就是在统一的接口下面提供不同的内部系统实现。

最开始接触这个项目的时候我心中很是没底。一来我从来没有接触过4W+行代码的项目，二来我对windows消息机制那一套也不是很了解。所以我就花了将近200大洋买了经典的《windows程序设计》，自己在那里面吭哧吭哧啃了好几天，看了200多页。终于算对windows消息循环机制有了初步的了解。

3月28号开会，3月29号熟悉整个系统体系。开始做控件。我被安排的任务是做文本类的控件：

  • ILabel：静态文本标签。
  • ITextField：单行文本编辑框。
  • ITextArea：多行文本编辑框。

三个文本控件统一要求：

  • 支持png图片载入
  • 支持字体类型和大小，
  • 字体颜色，
  • 背景颜色，
  • 圆角透明。
  • 支持编辑锁定和光标定位。

说起来容易做起来难。底层控件的开发往往比上层应用的开发要难的多。写到现在，代码总量写了180k，估摸着6000行应该有的（虽然有很多框架性copy&paste的东西）。总共写了3个文本空间和8个窗口界面。3:8，由此可见一个小小的文本编辑框并不是我们想象中的那么容易。具体来讲，在画点画线画矩形这写仅有的GDI函数的基础上，你需要实现：

  • 如何支持不同的风格（字体颜色，大小，背景颜色，alpha渲染风格）；
  • 如何支持png图片的载入（我设计的单行文本框支持一张mainPng和两张leftPng、rightPng的载入，并根据鼠标是否点击在leftPng和rightPng图片上进行不同的处理，如清空文本，确定查询等等，载入png事件简单的事情，但是由此引发的光标定位问题却让我无比头疼）；
  • 如何支持光标定位（这是文本框设计中非常复杂的一个问题。可能你不相信，等宽字体(monospace)的发明就是因为早期的电脑画面显示、打字机，由于技术的局限，无法进行字母宽度的比例调整，因此将每个字元都制作成一样的宽度）。说到这里应该明白了吧。当你点击光标的时候，需要根据你的光标的坐标，判断在整个字符串中最合适的位置。总不能让光标在一个字体的中间闪烁吧……原理也是很简单的，无非就是建立个链表，每个node的结构如下： 
struct char_node
{
    wchar_t * ch;
    int ch_width;
    int ch_height;
}

        然后根据光标的位置从头开始遍历链表，最终确定光标位置。但是，当你面对一个1k行的代码基，里面按照原来的机器写死了各种可恶的绝对坐标的时候，你想对 它进行改进，就不是说说那么简单的事情了。

  • 如何支持字体的滚动（当文本输入到边缘时——拿单行编辑框为例，正常情况下文本应该向左滚动，光标始终在最右端的边缘闪烁）。老的平台控件是支持这个功能的，这让我很开心，但是开心了没多久，我发现了一个很严重的bug，就是在整个文本字符串在向左滚动的时候，文本字符会画到整个文本控件的左边……这显然是一个不可饶恕的bug，但是到现在我仍然没有搞定。因此现在我的ITextField，当你的文字字符串输到文本框右边的时候，光标仍然继续向右移动——于是就会消失不见了。
  • 如何支持不同的字体大小（我发现在原来的代码基础上改造而来的ITextField对光标的定位简直是一塌糊涂。经过我一番实验，发现当用29号字体的时候光标的定位效果是最好的，于是我统一把我的文本控件的字体改成了默认的29号大小。陈老师告诉我们说“软件软件，越软越好……”，我当然明白这个道理，但是，写“软”是需要时间的。某些时候，为了赶进度，我们不得不牺牲某些扩展性来追求暂时的能用性。所以我的东西到现在，光标定位依然是很大的问题）
  • 如何支持不同字体载入？据我所知，字体有点阵字体和矢量字体，矢量字体又有OpenType和TrueType等，这些字体的内在原理是什么？什么叫衬线字体？什么叫非衬线字体？为什么一般文章排版正文都要用宋体？等等，这是非常有研究的一个话题。
  • 如何支持文字选块？
  • 如何支持多行文本域的文字折行？
  • 进一步，如何支持标点压缩和头尾压缩（这是一般字处理软件的事情了……）。
  • 再进一步，我们只知道英语和汉语，陈老师说阿拉伯文的文字连着写和分着写也是不一样的，有特殊的规则，我们又该如何支持？

由此可以看出，文本编辑框虽然看似简单，实现起来却要涉及到很多很多的知识和细心斟酌。

当然，以我的水平是不可能在这么短的时间内写出一个完备的文本编辑框的。可取的方法就是模仿、修改。老的单行文本编辑框叫做GTextField，GTextField的邻居如下所示：

我呢，则丝毫没有客气，仿照主要的函数接口，框架代码，对GTextField做起了外科手术。一个好的医生应该是内外兼修。做这么一个东西自然需要对底层的东西有比较深入的了解。可是一来这一套东西是我们实验室自己yy出来的，很多尚达不到工业标准，也没有现成的教程指南，代码注释又不是特别完备，所以自己理解起来颇有些困难；二来很多东西急于求成，所以有非常多莫名其妙的1、2、3、4、5，只有通过自己的实验看效果，将这些12345变成const int default_xx_margin = 3……

经过我的改造，除了光标定位和字体大小，其余功能基本实现，只是代码写的比较恶心，自己都不忍去看了。

无怪乎，Knuth大人一个TeX系统写了十年时间，经过别人改造成LaTeX、ConTeXt、Omega、LuaTeX等等至今尚未完善；无怪乎求伯君大神当年十万行汇编代码的WPS1.0使他成为了全中国程序员的偶像。

当我们费了九牛二虎之力做出来一个可以用的东西时，却发现那个东东是如此的丑陋，以至于连自己都不敢去看它。有了这样的经历，再去使用Windows 7，Compiz Fusion，会多一份敬重之情。简洁优美的背后，隐藏着多少心思和功力。

这是我现在写出来的最终效果：

样式还不错，点击右边小按钮的时候还能清空文本。当然，更灵活的设计时发送个消息，让用户自己处理决定该做什么。

这是头文件，单行文本编辑框的类定义： 

/**************************************************
ITextField: 单行文本编辑框
功能描述：至此png图片载入。支持单行文本编辑。支持锁定操作。但是光标定位和字体大小还存在问题。
作者：Xiao Hanyu <xiaohanyu1988@gmail.com>
参考：GTextEdit
**************************************************/

#pragma once
#include "SimpleCtrl.h"
#include "TwoWayLinkList.h"
#include "DataTypeDef.h"  //-------------
#include "string"
#include "ThTimer.h"
#include "IStyle.h"
#include "TextArea.h"
#include "MCaret.h"
#include "WndContainer.h"
#include "GDIFactory.h"
#include "DrawDevice.h"
#include "GDIPen.h"
#include "GDIBrush.h"
#include "CombinedCtrl.h"
#include "AllCtrlManager.h"
#include "BaseWnd.h"

#define	ITF_TXT_CHANGED		(MD_USER_BEGIN + 1)			// 只要文字输入改变，就发送该消息
#define	ITF_LEFT_PNG_CLICKED	(MD_USER_BEGIN+2)		// 只要设置mainPng和leftPng，如果点击leftPng，就发送该消息
#define ITF_RIGHT_PNG_CLICKED	(MD_USER_BEGIN+3)		// 只要设置mainPng和rightPng，如果点击rightPng，就发送该消息

const int ITEXTFIELD_MAX_LEN = 300;
//设置边距，即绘制光标和文字时，距离边缘的最小值
const int ITF_EDGE_BORDER = 2;

class MCaret;

class ITextField : public SimpleCtrl
{
public:
	ITextField(GisHWND pBWnd, ControlID id);
	virtual ~ITextField();
	Boolean ShowCaret();
	Boolean HideCaret();

public:
	//父类继承需要重写函数
	virtual GRESULT Init(int cx, int cy, int nWidth, int nHeight);
	virtual GRESULT UnInit();
	virtual void Redraw();
	virtual Boolean setDisabled(Boolean b);
	//Mouse Msg Action
	virtual GRESULT OnMouseDown(MouseButtons mbtn,int x,int y);
	virtual GRESULT OnMouseUp(MouseButtons mbtn,int x,int y);
	virtual GRESULT OnMouseDBClick(MouseButtons mbtn,int x,int y);
	virtual void SetFocus(Boolean bFocus);//设置本文本框为鼠标焦点
	virtual void SetVisable(Boolean bVisable);		//重载 当不可见时，失去焦点
	//Msg proc
	virtual GRESULT ProcCharMsg(WPARAM wParam, LPARAM lParam);
	//控件文本内容操作
	//获得当前文本
	wchar_t* GetText();
	//设置文本内容
	void SetText(const wchar_t *content);
	//清空文本内容
	Boolean ResetText();
	static void CALLBACK DoTimer(UINT uTimerID,DWORD dwUser,DWORD dw);
public:
	bool getCharVisable();	//输出文本框字符是否可见
	bool setCharVisable(bool p);//设置文本框字符是否可见
	void SetAutoOpenSip(bool p);//设置是否自动打开键盘
protected:
	//根据传入的x,y判断在字符串中的具体位置
	//x,y，在控件中的相对坐标
	int GetPosInString(int x,int y);
	//通过字符序号活得光标偏移位置长度
	int GetCaretFromCharIndex(int nCharIndex);	
	//获取当前整个字符串的长度
	int GetStringLength();

	//pos:在m_szText中的位置
	Boolean InsertCharInString(wchar_t cdata,int pos);
	Boolean DeleteCharInString(int pos, wchar_t* pCharOut);
	ThTimer m_Timer;	//光标显示定时器

public:
	IStyle GetStyle();
	void SetStyle(wchar_t* fontType, COLORREF fontColor, int iMode, int fontSize, UINT textAlignment, COLORREF bgColor, int alpha, bool round);
	Boolean ResetStyle();
	
	virtual GRESULT SetPngImage(wchar_t* main_png, wchar_t* left_png = NULL, wchar_t * right_png=NULL);
	GRESULT SetEditable(bool editable);

private:
	bool isCharVisable;		//决定文本框字符是否可见的变量，值为true，则输入的字符都可见，
	//值为false，则输入的字符均显示为*号，一般用来输入密码使用
	MCaret* m_pCaret;
	
	//保存文本框字符内容的数组，容量有限，依据ITEXTFIELD_MAX_LEN的值来决定容量
	wchar_t m_szText[ITEXTFIELD_MAX_LEN];
	//根据输入的字符串长度来填充适量的*号，这个变量就是一串*号的首地址
	wchar_t s_szText[ITEXTFIELD_MAX_LEN];
	
	//字符串显示开始位置
	GRect m_rcText;
	
	//字符串链表，因为不仅要保存字符本身，还要保存字符的显示宽度等信息，因此需要用到链表存储
	TwoWayLinkList m_CharList;
	
	//当前光标对应的字符串中的字符位置
	int m_nCurCharPos;
	//当前字符串的字符总数
	int m_nCharNum;
	bool m_bAutoOpenSip;
	
	bool i_tfEditable;					// 是否可编辑
	
protected:
	IStyle i_tfStyle;					// 控制textfield的文字风格
	enum
	{
		i_mainPng = 0,
		i_leftPng,
		i_rightPng,
		StateCount
	};
	
	GImage	i_tfArrPng[StateCount];		        // textfield目前支持三张png图片
	Boolean i_tfSetMainImg;				// 是否设置mainPng?
	Boolean i_tfSetLeftImg;				// 是否设置leftPng?
	Boolean i_tfSetRightImg;			// 是否设置rightPng?
	//HFONT	i_tfFont;				// 保存控件的字体信息，用于光标定位和字体大小
};

多行文本域的设计还要复杂一点。所以这个控件至今有很多的bug，有非常多的改进之处。

除了控件层开发，到现在为止我还写了行程业务的8个窗口页面。在写的过程中思考了很久“如何把软件写软的问题”。但是由于没有系统了解过设计模式，对c++强大的继承用的又不熟，因此现在无法做出自我满意的总结。

还打算总结下这一个月来用VS2008及相关软件的一些小技巧。毕竟磨刀不误砍柴工。

水平有限、敬请批评指正。 

Windows windows Mobile Comments(0) Sat, 24 Apr 2010 09:34:12 +0800

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:

#ifndef _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 <iostream>
#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;
}

Algorithm c++ windows bst avl Comments(1) Thu, 03 Dec 2009 06:03:53 +0800




Host by is-Programmer.com | Power by Chito 1.3.3 beta | © 2007 LinuxGem | Design by Matthew "Agent Spork" McGee