博文
平衡二叉树源码(2007-10-11 21:59:00)
摘要：
#include <stdio.h>
typedef struct bitreetype { int item; int bdegree;/*平衡因子,左子树深度-右子树深度*/ struct bitreetype *lchild; struct bitreetype *rchild; }bitree;
typedef struct treequeuetype { int head; int tail; bitree *items[1000]; }treequeue;/*定义一个队列,后面的平衡调整要用层序遍历,于是要用这个队列*/
void resetqueue(treequeue *queue) { queue->head=-1; queue->tail=-1; return; }/*把队列清空*/void inqueue(treequeue *queue,bitree *element) { queue->tail++; queue->items[queue->tail]=element; }/*入队列*/bitree *outqueue(treequeue *queue) { queue->head++; return queue->items[queue->head]; }/*出队列*/int isqueueempty(treequeue *queue) { if(queue->head==queue->tail) return 1; else return 0; }/*判断队列是否为空*/void fillmemory(char *source,int len,char content) { while(len) { source=source+len;......
从Cache学习卓越编程 (2007-10-11 21:37:00)
摘要：不了解计算机系统，就不能写出卓越程序！”这是《编程卓越之道》系列丛书的主要思想。实际上也是如此！那么，怎么去了解系统呢？我是从缓存（cache，发音同cash）这个概念入手的。之前看到个经典的程序：libsvm。其中使用了cache，于是就对它产生浓厚的兴趣。
CPU-Z是一款免费绿色软件，用于测量CPU、缓存、内存、主板等核心硬件的参数！我们要看的是CPU和缓存，因为我最关心的cache在这里嘛。先看看CPU页的时钟-核心速度，它就是通常说的 CPU 的主频了，多为 2.4GHz、1.4GHz。这里要说明的是，主频并不直接代表CPU的运算速度，但和运算速度有关。主频= 倍频 x 外频。外频是CPU和主板之间的同步运行的速度，此时可以理解为CPU的外频直接与内存相通，目前以133MHz外频的CPU为主流。前端总线一般被认为是外频的另一个名字，其实它是数据传输的速度。如果数据传输的极限速度不能满足CPU的运算速度，则过度提高倍频是没有意义的，一般倍频在5~8倍之间CPU的性能会得到充分发挥，极限为10倍。
寄存器 -> 一级Cache -> 二级Cache -> 主存 -> 磁盘。这是现代计算机的存储层次。寄存器和一级（L1）Cache都在CPU上，大多数奔腾2、3、4 CPU 都提供二级（L2）Cache，但是有些赛扬芯片没有，访问他们所需时钟周期（主频的倒数）的个数分别为2~3，7~10，70~100，10e6~10e7。每个时钟周期内CPU处理的指令数目根据数据依赖关系和资源约束而变化。关于CPU-Z中的Cache，L1有数据和跟踪两项，前者叫数据Cache，用于存储数据，一般的Intel CPU 该值为4~32 KB（一般为8 KB），后者用于存储指令，所以也叫指令Cache。针对Cache的访问决定程序的速度，如果频繁调用其中的数据（叫Cache命中，Cache Hit），则程序速度较快，否则造成Cache缺失（Cache Miss），到二级Cache甚至是主存和磁盘存取数据，则速度大打折扣，这就是上文说的数据传输的问题。
想给个例子：C语言实现1000 x 1000的两个double矩阵相乘。目前正在研究“分块（blocking）”，我还不知如何控制数据存储在L1/L2，欢迎大家探讨。
参考资料
1、CP......
平衡树与非平衡树(2007-10-11 21:33:00)
摘要：左子节点与右子节点对称的树就是平衡树，否则就是非平衡树。非平衡树会影响树中数据的查询，插入和删除的效率。比如当一个二叉树极不平衡时，即所有的节点都在根的同一侧，此时树没有分支，就变成了一个链表。数据的排列是一维的，而不是二维的。在这种情况下，查找的速度下降到O(N)，而不是平衡二叉树的O(logN)。为了能以较快的时间O(logN)来搜索一棵树，需要保证树总是平衡的（或者至少大部分是平衡的）。这就是说对树中的每个节点在它左边的后代数目和在它右边的后代数目应该大致相等。几种主要的二叉平衡树：红黑树的平衡是在插入和删除的过程中取得的。对一个要插入的数据项，插入程序要检查不会破坏树一定的特征。如果破坏了，程序就会进行纠正，根据需要更改树的结构。通过维持树的特征，保持了树的平衡。红黑树有两个特征：(1) 节点都有颜色(2) 在插入和删除过程中，要遵循保持这些颜色的不同排列的规则。红黑规则：1. 每一个节点不是红色的就是黑色的2. 根总是黑色的3. 如果节点是红色的，则它的子节点必须是黑色的（反之不一定成立）4. 从根到叶节点或空子节点的每条路径，必须包含相同数目的黑色节点。（空子节点是指非叶节点可以接子节点的位置。换句话说，就是一个有右子节点的节点可能接左子节点的位置，或是有左子节点的节点可能接右子节点的位置）AVL树，它或者是一颗空二叉树，或者是具有下列性质的二叉树：(1) 其根的左右子树高度之差的绝对值不能超过1；(2) 其根的左右子树都是二叉平衡树。AVL树查找的时间复杂度为O(logN)，因为树一定是平衡的。但是由于插入或删除一个节点时需要扫描两趟树，依次向下查找插入点，依次向上平衡树，AVL树不如红黑树效率高，也不如红黑树常用。AVL树插入的C++代码：
template <class T>ResultCode AVLTree<T>::Insert(AVLNode<T> * &p,T &x,bool &unBalanced)...{ ResultCode result=Success;&nbs......
Hash_Table（散列表）(2007-10-05 16:14:00)
摘要： 最近在学习散列。学的很迷糊。我就找了个别人编的程序看看。
以下代码仅在 g++ 3.4.2中编译通过，令人惊奇的是VC 2005竟然编译出错，看来以后用VC 2005还得小心才行。
//结点类型template <typename T, typename Tar>struct node...{ T data; Tar value; node* next; //初始化为空 node() : value(0), next(NULL) ...{}};//Hash表//第一个类型参数的类型可以是：int, long, char, string//第二个类型参数的类型可以是：int, bool, char//此Hash表支持的操作有：//insert(T x)：将类型为T的元素插入hash表中，如果已存在则直接退出//search(T x)：查找是否存在值为x的元素（返回bool型）//remove(T x)：将值为x的元素从表中删除//对于[]的重载：返回value域的引用template <typename T, typename Tar>class Hash_Table...{private: static const int size......
正则表达式30分钟入门教程(2007-10-04 20:21:00)
摘要：正则表达式30分钟入门教程
作者：deerchao 来源:unibetter大学生社区 转载请注明来源
本文已更新，推荐您查看第二版。
本文目标
30分钟内让你明白正则表达式是什么，并对它有一些基本的了解，让你可以在自己的程序或网页里使用它。一旦入门后，你可以从网上找到更多更详细的资料来继续学习。
别被下面那些复杂的表达式吓倒，只要跟着我一步一步来，你会发现正则表达式其实并不像你想像中的那么困难。当然，如果你看完了这篇教程之后发现自己明白了很多，却又几乎什么都记不得，那也是很正常的--其实我认为没接触过正则表达式的人在看完这篇教程后能把提到过的语法记住80%以上的可能性为零。这里只是让你明白基本道理，以后你还需要多练习，多查资料，才能熟练掌握正则表达式。
说明
正则表达式是用于进行文本匹配的工具，所以本文里多次提到了在字符串里搜索/查找，这种说法的意思是在给定的字符串中，查找与给定的正则表达式相匹配的部分。有可能字符串里有不止一个部分满足给定的正则表达式，这时每一个这样的部分被称为一个匹配。匹配在本文里可能会有三种意思：一种是形容词性的，比如说一个字符串匹配一个表达式；一种是动词性的，比如说在字符串里匹配正则表达式；还有一种是名词性的，就是刚刚说到的“字符串中满足给定的正则表达式的一部分”。
文本格式约定：专业术语 特殊代码/语法格式 正则表达式 正则表达式中的一部分(用于分析) 用于在其中搜索的字符串 对正则表达式或其中一部分的说明
什么是正则表达式？
很可能你使用过Windows/Dos下用于文件查找的通配符，也就是*和?。如果你想查找某个目录下的所有的Word文档的话，你会搜索*.doc。在这里，*会被解释成任意的字符串。和通配符类似，正则表达式也是用来进行文本匹配的工具，只不过比通配符更能精确地描述你的需求--当然，代价就是更复杂。比如你可以编写一个正则表达式来查找所有以0开头，后面跟着2-3个数字，然后是一个连字号“-”，最后是7或8位数字的字符串(像010-12345678或0376-7654321)。
入门
在编写处理字符串的程序或网页时，经常会有查找符合某些复杂规则的字符串的需要。正则表达式就是用于描述这些规则的工具。换句话说，正则表达式就是记录文本规则的代码。例如，\d+就是......
如何阅读源代码(转)(2007-10-03 14:05:00)
摘要：作者：ariesram 来源：不详 写在前面的话： 自从我在linuxaid.com.cn上发表一些文章开始，就不断的有网友发来电子邮件，或者是就其中某些问题进行探讨，或者是查询其他文章的地址（往往这些网友看的是其他网站转载的我的文章），我很高兴自己写出的文章有这么多人回应，因为这是对我最好的赞赏，也很高兴有这么多人对我的文章感兴趣。但是常常因为工作关系。有很多邮件是询问我的其他文章在哪里能够找到，我不一定能够及时回复，也觉得回复同样的问题比较麻烦，所以在这里重复一下，我为linuxaid.com.cn写的文章都能在www.linuxaid.com.cn的应用开发栏目中找到，我的一部分文章收集在bambi.may10.ca/~ariesram/articles下面（这是一个很简陋的网页，只有文本格式的文章，也欢迎有兴趣的网友帮我设计一下网页），我的邮件地址：ariesram@linuxaid.com.cn, 或者ariesram@may10.ca。请转载文章的网站保留这一说明，欢迎网友写email给我探讨问题，虽然我不能保证能及时回复。 正文： 由于工作的关系，我常常需要读一些源代码，并在上面做一些修改并且拿来使用，或者是借鉴其中的某些部分。可以说，open source对于程序员来说，是很有意义的事情。根据我的经验，读源代码，至少有3个好处。第一个好处是可以学习到很多编程的方法，看好的源代码，对于提高自己的编程水平，比自己写源代码的帮助更大。当然不是说不用自己写，而是说，自己写代码的同时，可以从别人写的好的源代码中间学习到更多的编程方法和技巧。第二个好处是，可以提高自己把握大规模源代码的能力。一个比较大型的程序，往往都是经过了很多个版本很长的时间，有很多人参与开发，修正错误，添加功能而发展起来的。所以往往源代码的规模都比较大，少则10-100多k, 多的有好几十个MB. 在阅读大量源代码的时候，能够提高自己对大的软件的把握能力，快速了解脉络，熟悉细节，不仅仅是编程技巧，还能在程序的架构，设计方面提高自己的能力。（这里说一句题外话，<<设计模式>>这本书相信很多人都看过，而且很多人对它推崇备至，奉为经典。现在也出了不少书，都是冠以"设计模式"这一名称。在书中就提到，设计模式并不是一本教材，不是教你如何去编程序，而是把平时编程中一些固定的模式......
“快速排序算法”问题的分而治之算法(2007-09-30 21:40:00)
摘要：/* 标题：<<系统设计师>>应试编程实例-[分治法程序设计] 作者：成晓旭 时间：2002年09月18日(21:43:00-22:03:00) 实现“快速排序算法”问题的分而治之算法函数*/#include "stdio.h"#include "stdlib.h"
//:============================“快速排序算法”问题的分而治之算法===========================/* 时间：2002年09月18日(21:43:00-22:03:00) 实现“快速排序算法”问题的分而治之算法函数 问题描述: 用分治法的思想实现快速排序算法。 编程思想: 快速排序算法的基本思想本身就是分治法。通过分割，将无序序列分成两部分， 其中前一部分的元素值都小于后一部分的元素值。然后每一部分再各自递归进行上 述过程，直到每一部分的长度为1为止。 首先，在序列的第一个，中间一个，最后一个元素中选取中项，设为p[middle], 并作temp = p[middle](保存中项); 其次，将序列中的第一个元素移到p[middle]的位置上； 然后，设两个指针i,j分别指向将排序序列的第一个元素和最后一个元素； 重复以上两步，直到i = j为止； 最后，将array[i] = temp(将tmep移到array[i])。*/#define MAXN 20
void Carve_up(int array[],int number,int *m){ int i,j,k,middle,temp; i = 0; j = number - 1; k = (i + j) / 2; //在下标i,j,k的数组元素......
影响大学生就业的几个关键问题(2007-09-19 00:54:00)
摘要：影响大学生就业的几个关键问题
小序：
回到公司总部做技术培训和人员招募有一段时间了，心中感慨万千。回顾一下自己的学习历程，首先应该认真检讨一下自己：从小学开始，学习就一直不是很好——浮浮躁躁、欠缺扎实。很幸运，我借助小时候被父亲培养出来的求知欲加上物理老师在探索、研究方面的启蒙以及朋友父亲在计算机方面的启蒙进入了心仪的计算机行业发展，并且有机会在这个行业中从事一些与招聘和培训相关的工作。目前，我工作中最重要的两个topic就是：“什么样的人是可以招进公司的”和“什么样的人是可以培训出来的”。很遗憾，我没有专业HR的经验，对于如何识别一个人的人品、性格、职业发展的前景等不太在行，我的责任仅体现在技术与专业知识方面。
与我的大多数技术文章不同，本篇文章的议题和内容是比较严肃的（尽管也会忍不住调侃两句），因为它牵扯到当代大学教育、学生就业、企业招聘等重要的话题。正因为这个话题是严肃的，所以我在写这篇文章的时候，也尽可能地保持了客观的视角和中立的心态——时刻劝告自己不要像个愤青一样攻击社会和教育、不要小人得志般地针砭大学生（说实话，大学生是有自己的一些缺点，但也有自己的难处，而且，大学生中也有很多好样的！）。
本来这篇文章早就写出来了，之所以没有挂出来是因为我一直在想这样一个问题——这篇文章挂出来的目的是什么？现在，我似乎找到了答案，那就是：真诚地帮助目前在校的学生瞄准企业需求、修正自己的学习轨迹、顺利进入企业工作；同时帮助公司招聘和培训越来越多的优秀人才。
最后恳请大家在看完文章后，留下您的宝贵意见——为了中国的IT教育、IT企业，也为了你自己。
正文：
相信大家都听说过建国初期、赶上自然灾害那阵子，曾经出现过有人饿死的情况——那是因为物资太匮乏了。现在已经不会再有这样的消息了——因为物质水平上来了。呵呵，你可能会问：怎么今天提起这个来了？事情是这样的——最近被调回总部搞招......
算法为王--正本溯源系列之一 (2007-09-19 00:38:00)
摘要： 算法 为王--正本溯源系列之一
以前曾旁观过一些软件工程师们争论, 当然也包括很多大学里的学生和朋友, 常见的一种是为谁的技术高, 谁懂的技术深刻较劲, 用C++的朋友很看不起用VB的, 精通操作系统的人看不起精通Excel的人, 精通编译原理的人看不起培训Dot Net的, 用UNIX的看不起Windows编程的人, 程序员相轻, 比文人更甚, 这样歧视的话语和语调流行很广. 可能有老师或者所谓资深专家对一个初学者这样说，你要想成为高手, 必须要扎实的学好操作系统，编译原理, 数据结构等等一大堆的科目.
我在想, 公司里有一个文员, 每天和Excel报表打交道, 非常的熟悉,并且很聪明, 用VB Script写了很多自动化的功能，使自己的工作效率成倍的增长, 这样的人也许不懂计算机的原理, 不懂什么操作系统，c++语言等，你能说她很低级吗? 你能不为她而投去敬佩的目光吗? 她和精通操作系统的你区别有多大? 天上与地下, 你说，那好，我们现在就谈论这个问题.
计算机原理, 操作系统, 编译原理, 编程语言这些东西, 说到底其实都是知识, “知其然”是知识, “知其所以然”也是知识. 这些书本上的知识是前人智慧的结晶, 里面充斥着天才的思想和绝妙的算法, 是很长时间内科学家们不断的创新和试错, 才能得到今天的地步, 典型的一个例子是操作系统，一个控制硬件系统的软件，里面每一个章节都是算法或者逻辑的汇总, 每一页枯燥的文字背后的目的就是介绍一个算法, 这些算法慢慢成为思想, 成为体系结构, 然后成为规则, 成为你必须记忆的知识. 你学习的时候感觉很难掌握, 是啊，你一节课学习的东西其实是前人几个月甚至几年想到的解决办法, 你如果要切实的理解，就必须顺着计算机科技发展的历史, 每一阶段出现的困难和怎么去解决它这个思路的角度去理解.
这些课程你学的很好，都知道是怎么回事了，它只是表明你知道了前辈们的劳动成果, 也学会了很多成熟的思维和算法, 给自己写程序很多的启发, 其他并没有多大的意义, 它和公司里的文员精通Excel的意义一样, 你的优越感只是你自己幻想的......
如何编写代码才能使得效率高(2007-09-19 00:31:00)
摘要： 如何编写代码才能使得效率高
一、排版： 1.关键词和操作符之间加适当的空格。 2.相对独立的程序块与块之间加空行 3.较长的语句、表达式等要分成多行书写。 4.划分出的新行要进行适应的缩进，使排版整齐，语句可读。 5.长表达式要在低优先级操作符处划分新行，操作符放在新行之首。 6.循环、判断等语句中若有较长的表达式或语句，则要进行适应的划分。 7.若函数或过程中的参数较长，则要进行适当的划分。 8.不允许把多个短语句写在一行中，即一行只写一条语句。 9.函数或过程的开始、结构的定义及循环、判断等语句中的代码都要采用缩进风格。 10.C/C++语言是用大括号‘{’和‘}’界定一段程序块的，编写程序块时‘{’和 ‘}’应各独占一行并且位于同一列，同时与引用它们的语句左对齐。在函数体 的开始、类的定义、结构的定义、枚举的定义以及if、for、do、while、 switch、case语句中的程序都要采用如上的缩进方式。
二、注释 1.注释要简单明了。 2.边写代码边注释，修改代码同时修改相应的注释，以保证注释与代码的一致性。 3.在必要的地方注释，注释量要适中。注释的内容要清楚、明了，含义准确，防止 注释二义性。保持注释与其描述的代码相邻，即注释的就近原则。 4.对代码的注释应放在其上方相邻位置，不可放在下面。 5.对数据结构的注释应放在其上方相邻位置，不可放在下面；对结构中的每个域 的注释应放在此域的右方；同一结构中不同域的注释要对齐。 6.变量、常量的注释应放在其上方相邻位置或右方。 7.全局变量要有较详细的注释，包括对其功能、取值范围、哪些函数或过程存取它 以及存取时注意事项等的说明。 8.在每个源文件的头部要有必要的注释信息，包括：文件名；版本号；作者；生成 日期；模块功能描述（如功能、主要算法、内部各部分之间的关系、该文件与其 它文件关系等）；主要函数或过程清单......