Apr
04
2010

学习,是一辈子的事zz

发信人: OneByOne (。。。。。。), 信区: Triangle
标  题: 学习,是一辈子的事。
发信站: 北大未名站 (2010年04月03日23:41:03 星期六), 转信

我身边的一个光华的保安弟弟对着通知栏专心的拿着本子记录着,我偷偷看了一下他的本
子。上面记满了英文单词。突然激发起我的好奇心,我就开始和他聊天。

我:你的本子上记的是什么呀?

保安弟弟:哦,记下不认识的英文单词,回头去查字典。

我:哦? 你在自己学英语呀?

保安弟弟:是的,基础不太好。

我:没关系,语言要慢慢来的。北大的环境很好的,很适合学习的。你是从哪里来的?

保安:我是从河南来。(停顿两秒)我们河南人在外面,嗯(欲言又止。。)

我打断到:人特别多吧。我就认识很多河南的人,人很好。你来多久了?

保安:我来4个月了,北京很好,北大也很好。

我:嗯,你平时都怎么学英语的呀。

保安:平时我都看China Daily,楼上可以免费拿的。

我:China Daily看起来挺难的。

保安:是呀,好多单词都不认识。查字典要好久。(指着通知上问)这上面的单词你都认
识吧。

我:哦,差不多吧,也不一定。

保安:这个Collaboration是什么意思呀?

我:这个是合作的意思,Col代表和什么一起,labor是劳动的意思。和人一起劳动就是合
作的意思。

保安:哦,和Cooperation一个意思呀。英语里面的同义词太多了,好难。

我:确实,多看看就好了。我要走了,再见. 加油

保安:再见。

在回寝室的路上,我一直在思考。学习是人追求发展的权利。是谁剥夺了那么年轻的保安
学习的权利?年轻保安求知若渴的眼神深深的触动了我。他和校园里的大学生一样的年龄
,一样的求知欲。命运使然,生活的艰辛让他走上了一条不一样的路。他仍然没有放弃自
己的理想。也许有一天他能出人头地。可是现实的社会还会让人有梦想吗?还会让人有着
从鸡窝里飞出凤凰的神话吗?

受教育的权利意味着发展权,在有限的教育资源被更多的分配到城市居民那里。我们广大
的农民儿女们难道就只能通过到北大来当保安来学习吗?也许这并不是某个人可以解决的
问题,但是确实是每个人值得思考的。贫穷不可怕,卑微不可怕。如果当连那一丝的希望
都被扼杀在摇篮当中。那才是真正的可怕。

0403 胡言乱语中

0
Nov
04
2009

使用BoundsChecker(转载)

 http://hi.baidu.com/%D0%C4%D3%EA%D0%C4%C2%B7/blog/item/0937ee07a42d65c87b89479d.html

 

   BoundsChecker是一个Run-Time错误检测工具,它主要定位程序在运行时期发生的各种错误。              

BoundsChecker能检测的错误包括:

     1)指针操作和内存、资源泄露错误,比如:内存泄露;资源泄露;对指针变量的错误操作。
     2)内存操作方面的错误,比如:内存读、写溢出;使用未初始化的内存。平台 n.U3U B C _3S社区&资讯平台!z&v k.U M [8S([
     3)API函数使用错误。

    使用BoundsChecker对程序的运行时错误进行检测,有两种使用模式可供选择。一种模式叫做ActiveCheck,一种模式叫做FinalCheck。下面分别进行介绍。
    1)ActiveCheck是BoundsChecker提供的一种方便、快捷的错误检测模式,它能检测的错误种类有限,只包括:内存泄露错误、资源泄露错误、API函数使用错误。
U `)R4p+~0要想使用ActiveCheck模式来检测程序的运行时错误,只需在VC++集成开发环境中打开BoundsChecker功能,然后从调试状态运行程序即可。此时ActiveCheck会在后台自动运行,随时检测程序是否发生了错误。下面说一下具体的使用步骤。
    首先,在VC++集成开发环境中打开你要对其进行测试的程序,同时保证项目处于Debug编译状态下。

     其 次,确保VC++集成开发环境中[BoundsChecker/Integrated Debugging]菜单项和[BoundsChecker/Report Errors and Events]菜单项处于被选中的状态。只有这两项被选中,BoundsChecker才会在程序运行过程中发挥作用。

 最后,在VC++集成开发环境中选择[Build/ Start Debug/Go]菜单命令,在Debug状态下运行程序,ActiveCheck也在后台开始运行了。
     2)FinalCheck具有BoundsChecker提供的所有检错功能。 FinalCheck 是ActiveCheck的超集,它除了能够检测出ActiveCheck能够检测出的错误,还能发现很多 ActiveCheck 不能检测到的错误,包括:指针操作错误、内存操作溢出、使用未初始化的内存等等,并且,对于ActiveCheck能检测出的错误,FinalCheck 能够给出关于错误更详细的信息。所以,我们可以把FinalCheck认为是ActiveCheck的功能增强版。我们付出的代价是:程序的运行速度会变 慢,有时甚至会变的很慢。

要 想在FinalCheck 模式下测试程序,不能使用VC++集成开发环境提供的编译连接器来构造程序,而必须要使用BoundsChecker提供的编译连接器来编译连接程序。当 BoundsChecker的编译连接器编译连接程序时,会向程序中插装一些错误检测代码,这也就是FinalCheck能够比ActiveCheck找 到更多错误的原因。
下面就介绍一下如何在FinalCheck模式下对程序进行测试:
     1)在VC++集成开发环境中打开你所要测试的项目。

     2)由于要使用BoundsChecker的编译连接器重新编译连接程序,所以我们为BoundsChecker独自构造一个文件夹。在VC++集成开发环境中,具体操作方法是:

A)点击[ Build/Configurations...]菜单命令。

B)在弹出的对话框中点击 Add 按钮。在Configuration 编辑框中添入你为BoundsChecker创建的文件夹的名称,这个名称是任意的,比如我们取名为BoundChecker。
    

C)在 Copy settings from组合框中选中XXX—Win32 Debug项,然后点击OK按钮,接着点击Close按钮。
现在,我们已经为FinalCheck构造好了一个文件夹。

    3) 点击[Build/Set Active Configuration…] 菜单命令,选中你刚才为BoundsChecker建的文件夹,然后点击OK按钮。这样BoundsChecker编译连接程序时生成的中间文件、可执行程序,都会被放到该文件夹下。

    4)选择[BoundsChecker/Rebuild All with BoundsChecker] 菜单命令,对程序重新进行编译连接,也就是在这时,BoundsChecker向被测程序的代码中加入了错误检测码。编译连接完成后, BoundsChecker会在你为BoundsChecker构造的文件夹中生成可执行文件。
      在FinalCheck模式下对程序进行检测的准备工作都已经做好,这时可以启动程序开始测试了,作步骤与在ActiveChecker模式下没什么区别。具体步骤如下:

  • 确保VC++集成开发环境中[BoundsChecker/ Integrated Debugging]菜单项和[BoundsChecker/Report Errors and Events]菜单项处于选中状态。
  • 点击[ Build\Start Debug]菜单,选中“Go” 菜单项。程序开始在Debug状态下运行。
  • 按照你制定好的测试用例,对程序进行操作。
    m8\6V l `"`0
  • 当BoundsChecker 检测到了错误时,会弹出窗口向你汇报,你可以当时就进行处理,也可以等到你的操作全部完成,退出程序之后再对列出的这些错误进行分析。这完全取决于你是否 选中了[BoundsChecker/Report Errors Immediately] 菜单项。
  • 退出程序后,BoundsChecker会给出错误检测结果列表。该错误列表与ActiveChecker给出的错误列表的查看方法完全一样。只不过这个列表中所报告的信息会更多、更详细一些。

     好 了,BoundsChecker在FinalCheck模式下的使用也介绍完了。ActiveChecker、FinalCheck这两种模式,比较而言 各有长短。ActiveChecker使用方便,只需在Debug状态下直接运行程序即可,并且程序的运行速度较快,但检测的错误种类有限; FinalCheck模式下,需要使用BoundsChecker的编译连接器重新编译连接生成可执行程序,并且程序的运行速度比较慢,但检测的错误种 类、提供的错误相关信息要多于ActiveChecker。所以,何时使用何种模式,应根据当时的具体情况而定。

0
Oct
25
2009

关系数据库范式学习手记[1NF 2NF 3NF BCNF] [zz]

zz from http://hi.baidu.com/taotling/blog/item/5c3c5f36f4dda2390a55a990.html

清楚明白,速成。。。

范式:
数据库规范化(Normalization)所采用的规范模式.

首先来看一张订单(表1-1):
供应商号: 234560   
供应商名: XXXXXX
============================================
商品号 商品名 数量 单价(元) 合计(元)
200   A   1000 2.00   2000.00
201   B   600   1.00   600.00
202   C   2000 10.00   20000.00
203   D   5000 20.00   100000.00
204   E   100   5.00   500.00

1. 非关系数据库表
如何通过这个订单来设计一个关系数据库的相关表?
一种最简单的办法就是将所有数据存放在一个表中,并用订单号和商品号做主键(Primary Key),
其中同一商品可以有不同的供应商
如下(表1-2:Order表):
   订单号 商品号 商品名 商品描述 单价 供应商号 供应商名 供应商电话
   000001 200   A   …….. 2.00 234560   XXXXXX   ……….
     201   B   …….. 1.00 234560   XXXXXX   ……….
     202   C   …….. 10.00 234560   XXXXXX   ……….
     203   D   …….. 20.00 234560   XXXXXX   ……….
     204   E   …….. 5.00 234560   XXXXXX   ……….
   ——————————————————————————-
   000002 200   A   …….. 2.00 234561   YYYYYY   ……….
     201   B   …….. 1.00 234561   YYYYYY   ……….
     202   C   …….. 10.00 234561   YYYYYY   ……….
     204   E   …….. 5.00 234561   YYYYYY   ……….
   ——————————————————————————-
   000003 202   C   …….. 10.00 234560   XXXXXX   ……….
     203   D   …….. 20.00 234560   XXXXXX   ……….
     204   E   …….. 5.00 234560   XXXXXX   ……….

2. 满足1NF的关系数据库表(消除重复组)
但上面的这个表不是一个关系数据库表,因为所有的关系数据库表中的每一行必须有主键,
并且这个主键要满足实体完整性(Entity Integrity),实体完整性就是主键不能包含空值(NULL),
并且主键必须能够惟一地标识任一行.根据实体完整性,上表显然不是一个关系数据库的表,
因为在这个表中有些行的主键中的订单号是空.
另外,上表中的000001订单下的
     203   D   …….. 20.00 234560   XXXXXX
     204   E   …….. 5.00 234560   XXXXXX
与000003订单下的
     203   D   …….. 20.00 234560   XXXXXX
     204   E   …….. 5.00 234560   XXXXXX
完全一样,这叫重复组(Repeating Groups),关系数据库表中不能含有重复组.
对上表进行修改,使之实现实体完整,即将相应的订单号补上(表1-3:Order表):
   订单号 商品号 商品名 商品描述 单价 供应商号 供应商名 供应商电话
   000001 200   A   …….. 2.00 234560   XXXXXX   ……….
   000001 201   B   …….. 1.00 234560   XXXXXX   ……….
   000001 202   C   …….. 10.00 234560   XXXXXX   ……….
   000001 203   D   …….. 20.00 234560   XXXXXX   ……….
   000001 204   E   …….. 5.00 234560   XXXXXX   ……….
   ——————————————————————————-
   000002 200   A   …….. 2.00 234561   YYYYYY   ……….
   000002 201   B   …….. 1.00 234561   YYYYYY   ……….
   000002 202   C   …….. 10.00 234561   YYYYYY   ……….
   000002 204   E   …….. 5.00 234561   YYYYYY   ……….
   ——————————————————————————-
   000003 202   C   …….. 10.00 234560   XXXXXX   ……….
   000003 203   D   …….. 20.00 234560   XXXXXX   ……….
   000003 204   E   …….. 5.00 234560   XXXXXX   ……….
上表现在成为一个关系数据库表,这个表满足1NF,即:
   (1) 所有的属性(列)都已定义
   (2) 没有任何重复组,即每行和每列的交汇处可以而且只能包含一个值,而不能包含一组值.
   (3) 所有属性(列)都依赖于主键.

3. 满足2NF的关系数据库表(消除重复组和部分依赖)
但是,上表在实际应用中是存在诸多问题的,比如说供应商XXXXXX的商品A要被分批100次订购,
那么将会在这个表中有100个订单,而关于此商品A的记录会有100行,如:
   订单号 商品号 商品名 商品描述 单价 供应商号 供应商名 供应商电话
   000001 200   A   …….. 2.00 234560   XXXXXX   ……….
   …… …   .   …….. …. …….   ……   ……….
   000002 200   A   …….. 2.00 234560   XXXXXX   ……….
   000003 200   A   …….. 2.00 234560   XXXXXX   ……….
   …   …   …   …    …   …    …    …
   00000n 200   A   …….. 2.00 234560   XXXXXX   ……….
这将使得出现输入错误的可能性大为增加,从而产生相同的商品在同一表中不同的行中记录的
相关信息不一样的错误,即所谓有数据不一致.数据不一致性是由于相同数据的重复存放,
即冗余造成的.数据冗余不但会造成数据不一致,还会使系统的维护更加困难,也会对系统的效率产生冲击.
为了减少这种情况下的数据的冗余需要消除部分依赖.
在表(1-3)中可以看出,我们只要知道某一商品的商品号,就能知道该商品的全部信息,
即商品的其他部分信息只依赖于商品号,也就是说在表1-3的:
   订单号 商品号 商品名 商品描述 单价 供应商号 供应商名 供应商电话
这些字段中,
   商品名 商品描述 单价
这些字段均依赖于
   商品号
字段,
因为"商品号"在表(1-3)中是主键的一部分,
所以"商品名 商品描述 单价"对于"商品号"的这种依赖关系,通常称为部分依赖.
即:部分依赖(Partial Dependency)是指只依赖于部分主键的依赖关系.
我们可以将存在部分依赖关系的列拿出来新生成一个新的表Product,
而原来的Order表中去掉了一些列,形成一个新的Order表,
在Product表中,商品号将作为其主键,同时商品号在新的Order表中将作为外键,
以实现对商品的相关信息的关联.
现在最初的(1-3:Order)表被拆分为两个新的表Order和Product,
它们之间通过商品号来进行连接:
Order表:
   订单号 商品号 供应商号 供应商名 供应商电话 …
Product表:
   商品号 商品名 商品描述 单价 …
现在,一个商品的信息只需要在Product表中存放一次,
而Product表中只有商品号在Order表中可重复存放多次,
这比起最初的Order表(1-3:Order)来说,"商品名 商品描述 单价"这些字段的数据冗余已大大减少.

我们可以看到,在1NF的规范下,我们消除了重复组,
在2NF的规范下,我们消除了部分依赖,
原来的Order表已被拆分为两个表:
   Order表:
    订单号 商品号 供应商号 供应商名 供应商电话 …
   与Product表:
    商品号 商品名 商品描述 单价 …
它们都满足于2NF的条件:
(1) 该表为1NF(无重复组)
(2) 该表不包含部分依赖(存在部分依赖的列已被提出形成另一个表)

4. 满足3NF的关系数据库表
现在我们再来看看满足2NF的Order表:
Order表:
   订单号 商品号 供应商号 供应商名 供应商电话 …
如果供应商的电话现在有了改变,那么在Order的所有有关这个供应商的"供应商电话"的信息将要
被修改,这种工作量是很大的.
再来看看"供应商号 供应商名 供应商电话"之间的依赖关系,
一般来说,我们只要知道了某一供应商的供应商号,就能知道该供应商的全部信息,
即,"供应商名 供应商电话"只依赖于"供应商号",但在这里,"供应商号"并不是主键的组成部分,
所以这种依赖不属于部分依赖,而叫做"传递依赖(Transitive Dependency)",
传递依赖是指一个或多个属性(列)依赖于非主键的属性(列).

现在我们把存在着传递依赖的相关列拿出来,重新生成一个叫Supplier的表,
而把"供应商号"作为Supplier表的主键,同时把供应商号保留在新的Order表中作为外键,
这样,最被的Order表到现在就被拆分为三个表:
   Order表:
     订单号 商品号 供应商号
   Supplier表:
     供应商号 供应商名 供应商电话 …
   Product表:
     商品号 商品名 商品描述 单价 …
这样的三个表,都同时满足于关系数据库表的3NF,即:
(1) 该表满足2NF(无重复组,无部分依赖)
(2) 该表不包含传递依赖(存在传递依赖的列已被提出形成另一个表)

5. 满足BCNF的关系数据库表
BCNF是鲍依斯-科得范式Boyce-Codd Normal Form的简写,
在3NF的基础上,要求表中的所有字段只依赖于关键字段.
在关键字段是组合关键字段的情况下,如:
   假设仓库管理关系表为StorehouseManage(仓库ID, 存储物品ID, 管理员ID, 数量),
   且有一个管理员只在一个仓库工作;一个仓库可以存储多种物品。
   这个数据库表中存在如下依赖关系:
    (仓库ID, 存储物品ID) → (管理员ID, 数量) ["管理员ID, 数量"依赖于组合关键字段(仓库ID, 存储物品ID)]
    (管理员ID, 存储物品ID) → (仓库ID, 数量)   ["仓库ID, 数量"依赖于组合关键字段(管理员ID, 存储物品ID)]
   所以,(仓库ID, 存储物品ID)和(管理员ID, 存储物品ID)都是StorehouseManage的候选关键字,
   表中的唯一非关键字段为数量,这个表是符合第三范式的。
   但是,由于存在如下决定关系:
    (仓库ID) → (管理员ID) ["管理员ID"依赖于"仓库ID"]
    (管理员ID) → (仓库ID) ["仓库ID"依赖于"管理员ID"]
   即存在关键字段决定关键字段的情况,所以其不符合BCNF范式。它会出现如下异常情况:
   (1) 删除异常:
    当仓库被清空后,所有"存储物品ID"和"数量"信息被删除的同时,
    "仓库ID"和"管理员ID"信息也被删除了。
 
   (2) 插入异常:
    当仓库没有存储任何物品时,无法给仓库分配管理员。
  
   (3) 更新异常:
    如果仓库换了管理员,则表中所有行的管理员ID都要修改。
 
   把仓库管理关系表分解为二个关系表:
    仓库管理表:
     StorehouseManage(仓库ID, 管理员ID);
    仓库表:
     Storehouse(仓库ID, 存储物品ID, 数量)。
   即满足BCNF范式.

总结:
规范化是一个过程,该过程决定把哪些属性(列)放在哪些实体(表)中.
规范化可以帮助我们设计好的表结构,因为规范化减少了数据的冗余,
这使得系统更容易维护而且系统效率也会更高.

所谓的关系型数据库的逻辑设计就是数据库的表结构设计.
在关系数据库中,只有表中存有数据.

规范化只减少了数据的冗余而并没有消除冗余.
为了使相关的表连接起来,在规范化过程中不得不引入控制冗余(外键),
不过这种控制冗余与1NF和2NF表的数据冗余相比,
已经少得微不足道了.

0
Oct
04
2009

按字典序打印小于某值的自然数

给定连续的自然数序列1,2,3,…n,按字典序将其打印出来。n的取值范围是[1, 10,000,000,000]
实现函数:void print(int num);
如: print(120),则输出

1
10
100
101
102

109
11
110
111
112

119
12
120
13
..
19
2
20
21

29
3

4

9
90
91

99

————————-code————————–

//int 应该为 long

void display_cur(int cur_num, int num)

{

 

   int i;

   for (i = 0;i<= 9;i++)

   {

      int tmp_num = cur_num * 10 + i;

      if (tmp_num <= num)

      {

        cout<<tmp_num<<endl;

        display_cur(tmp_num, num);

      }

      else

      {

        break;

      }

   }

}

void display(int num)

{

   for (int i = 1;i<= 9;i++)

   {

      cout<<i<<endl;

      display_cur(i, num);

   }

}

 

void display1(int num)

{

   int cur_num = 1;

 

   cout<<cur_num<<endl;

   while (1)

   {

 

      cur_num = cur_num * 10;

      if (cur_num<=num)

      {

        cout<<cur_num<<endl;

      }

      else

      {

        cur_num /= 10;

        while ((cur_num % 10) == 9 || cur_num + 1 > num)

        {

           cur_num /= 10;

        }

        if (cur_num == 0)

        {

           break;

        }

        cur_num ++;

        cout<<cur_num<<endl;

      }

 

   }

}

void main()

{

   /*cout<<sizeof(a)<<endl;*/

   display1(112);

}

0
Oct
04
2009

[zz]关于2进制数求1的个数的扩展

大家踊跃参加,活动非常热烈。下面文章来自读者ZelluX:

 求二进制中1的个数。对于一个字节(8bit)的变量,求其二进制表示中"1"的个数,要求算法的执行效率尽可能的高。

先来看看样章上给出的几个算法:

解法一,每次除二,看是否为奇数,是的话就累计加一,最后这个结果就是二进制表示中1的个数。

解法二,同样用到一个循环,只是里面的操作用位移操作简化了。

   1:  int Count(int v)  
   2:  {  
   3:      int num = 0;
   4:      while (v) {  
   5:          num += v & 0×01;  
   6:          v >>= 1;  
   7:      }  
   8:      return num;  
   9:  }

解法三,用到一个巧妙的与操作,v & (v -1 )每次能消去二进制表示中最后一位1,利用这个技巧可以减少一定的循环次数。

解法四,查表法,因为只有数据8bit,直接建一张表,包含各个数中1的个数,然后查表就行。复杂度O(1)。

   1:  int countTable[256] = { 0, 1, 1, 2, 1, …, 7, 7, 8 };  
   2:     
   3:  int Count(int v) {  
   4:      return countTable[v];  
   5:  }
  
好了,这就是样章上给出的四种方案,下面谈谈我的看法。

首先是对算法的衡量上,复杂度真的是唯一的标准吗?尤其对于这种数据规模给定,而且很小的情况下,复杂度其实是个比较次要的因素。

查表法的复杂度为O(1),我用解法一,循环八次固定,复杂度也是O(1)。至于数据规模变大,变成32位整型,那查表法自然也不合适了。

其次,我觉得既然是这样一个很小的操作,衡量的尺度也必然要小,CPU时钟周期可以作为一个参考。

解法一里有若干次整数加法,若干次整数除法(一般的编译器都能把它优化成位移),还有几个循环分支判断,几个奇偶性判断(这个比较耗时间,根据CSAPP上的数据,一般一个branch penalty得耗掉14个左右的cycle),加起来大概几十个cycle吧。

再看解法四,查表法看似一次地址计算就能解决,但实际上这里用到一个访存操作,而且第一次访存的时候很有可能那个数组不在cache里,这样一个cache miss导致的后果可能就是耗去几十甚至上百个cycle(因为要访问内存)。所以对于这种“小操作”,这个算法的性能其实是很差的。

这里我再推荐几个解决这个问题的算法,以32位无符号整型为例。

   1:  int Count(unsigned x) {  
   2:     x = x – ((x >> 1) & 0×55555555);   
   3:     x = (x & 0×33333333) + ((x >> 2) & 0×33333333);   
   4:     x = (x + (x >> 4)) & 0×0F0F0F0F;   
   5:     x = x + (x >> 8);   
   6:     x = x + (x >> 16);   
   7:     return x & 0×0000003F;   
   8:  }
  
这里用的是二分法,两两一组相加,之后四个四个一组相加,接着八个八个,最后就得到各位之和了。

还有一个更巧妙的HAKMEM算法

   1:  int Count(unsigned x) {
   2:     unsigned n;   
   3:     
   4:     n = (x >> 1) & 033333333333;   
   5:     x = x – n;  
   6:     n = (n >> 1) & 033333333333;  
   7:     x = x – n;   
   8:     x = (x + (x >> 3)) & 030707070707;  
   9:     x = modu(x, 63); 
   10:     return x;  
   11:  }
  
首先是将二进制各位三个一组,求出每组中1的个数,然后相邻两组归并,得到六个一组的1的个数,最后很巧妙的用除63取余得到了结果。

因为2^6 = 64,也就是说 x_0 + x_1 * 64 + x_2 * 64 * 64 = x_0 + x_1 + x_2 (mod 63),这里的等号表示同余。

这个程序只需要十条左右指令,而且不访存,速度很快。

由此可见,衡量一个算法实际效果不单要看复杂度,还要结合其他情况具体分析。

关于后面的两道扩展问题,问题一是问32位整型如何处理,这个上面已经讲了。

问题二是给定两个整数A和B,问A和B有多少位是不同的。

这个问题其实就是数1问题多了一个步骤,只要先算出A和B的异或结果,然后求这个值中1的个数就行了。

总体看来这本书还是很不错的,比较喜欢里面针对一个问题提出不同算法并不断改进的风格。这里提出一点个人的理解,望大家指正 ;-)

 

本文来自CSDN博客,转载请标明出处:http://blog.csdn.net/bvbook/archive/2008/04/15/2292823.aspx

0
Oct
04
2009

非递归后序遍历二叉树

#include <stack>

 

struct TreeNode

{

   int value;

   TreeNode * left;

   TreeNode * right;

};

 

void FreeTree(TreeNode * pNode)

{

   if (pNode == NULL)

   {

      return;

   }

 

   FreeTree(pNode->left);

   FreeTree(pNode->right);

   delete pNode;

   pNode = NULL;

}

 

void DisplayTree(TreeNode * pNode,int level)

{

   if (pNode == NULL)

   {

      return;

   }

 

   int i = 0;

   while ((i++)<level)

   {

      cout<<"\t";

   }

   cout<<pNode->value<<endl;

   DisplayTree(pNode->left,level+1);

   DisplayTree(pNode->right,level+1);

}

 

struct TreeNodeHelp

{

   TreeNode * pNode;

   int flag;

};

 

typedef std::stack<TreeNodeHelp> tStack;

 

void tranvers1(TreeNode * pRoot)

{

   if (pRoot == NULL)

   {

      return;

   }

 

   tStack s;

   TreeNodeHelp sNode;

   sNode.pNode = pRoot;

   sNode.flag = 1;

   s.push(sNode);

 

   while (!s.empty())

   {

      TreeNodeHelp sTopNode = s.top();

      s.pop();

      if (sTopNode.pNode == NULL)

      {

        continue;

      }

 

      if (sTopNode.flag == 1)

      {

        sTopNode.flag = 2;

        s.push(sTopNode);

        sTopNode.flag = 1;

        sTopNode.pNode = sTopNode.pNode->left;

        s.push(sTopNode);

      }

      else if (sTopNode.flag == 2)

      {

        sTopNode.flag = 3;

        s.push(sTopNode);

        sTopNode.flag = 1;

        sTopNode.pNode = sTopNode.pNode->right;

        s.push(sTopNode);

      }

      else

      {

        cout<<sTopNode.pNode->value<<endl;

      }

   }

}

void main()

{

   /*cout<<sizeof(a)<<endl;*/

 

   TreeNode tNode[10];

 

   for (int i = 0; i < 10; i++)

   {

      tNode[i].left = NULL;

      tNode[i].right = NULL;

      tNode[i].value = i+1;

   }

 

   tNode[0].left = &(tNode[1]);

   tNode[0].right = &(tNode[2]);

   tNode[1].left = &(tNode[3]);

   tNode[1].right = &(tNode[4]);

   tNode[2].left = &(tNode[5]);

   tNode[2].right = &(tNode[6]);

   tNode[4].left = &(tNode[7]);

   tNode[4].right = &(tNode[8]);

   tNode[6].left = &(tNode[9]);

 

   DisplayTree(&(tNode[0]),0);

 

   tranvers1(tNode);

}

0
Oct
04
2009

链表翻转code

struct Node

{

   int value;

   Node * next;

};

 

struct Head

{

   Node * next;

};

 

void ReverseList(Head * phead)

{

   if (phead == NULL || phead->next == NULL)

   {

      return;

   }

 

   Node * prev = NULL;

   Node * cur  = phead->next;

   Node * next;

  

   while(cur != NULL)

   {

      next = cur->next;

      cur->next = prev;

      prev = cur;

      cur = next;

   }

 

   phead->next = prev;

}

 

Node* ReverseListRecurHelp(Node * pNode, Node *& pHead)

{

   if (pNode == NULL || pNode->next == NULL)

   {

      pHead = pNode;

      return pNode;

   }

 

   Node * prev = ReverseListRecurHelp(pNode->next,pHead);

   prev->next = pNode;

   return pNode;

}

 

void ReverseListRecur(Head * pHead)

{

   if (pHead == NULL || pHead->next == NULL)

   {

      return;

   }

 

   Node * pTail = ReverseListRecurHelp(pHead->next, pHead->next);

   pTail->next = NULL;

}

 

void DisplayRecur(Node * pNode)

{

   if (pNode->next == NULL)

   {

      cout<<pNode->value<<endl;

   }

   else

   {

      cout<<pNode->value<<endl;

      DisplayRecur(pNode->next);

   }

}

void DisplayList(Head * phead)

{

   if (phead == NULL || phead->next == NULL)

   {

      return;

   }

 

   DisplayRecur(phead->next);

}

void FreeListRecur(Node * pNode)

{

   if (pNode == NULL)

   {

      return;

   }

   if (pNode->next == NULL)

   {

      delete pNode;

      pNode = NULL;

   }

   else

   {

      FreeListRecur(pNode->next);

      delete pNode;

      pNode = NULL;

   }

}

 

void FreeList(Head * pHead)

{

   if (pHead == NULL || pHead->next == NULL)

   {

      return;

   }

   FreeListRecur(pHead->next);

}

 

void main()

{

   /*cout<<sizeof(a)<<endl;*/

 

   int i ;

   Node * prev = NULL;

   Head * pHead = new Head;

 

   for (i = 0;i<10;i++)

   {

      Node * pNode = new Node;

      pNode->value = i;

      pNode->next = prev;

      prev = pNode;

   }

   pHead->next = prev;

 

   DisplayList(pHead);

 

   ReverseList(pHead);

 

   DisplayList(pHead);

 

   ReverseListRecur(pHead);

 

   DisplayList(pHead);

 

   FreeList(pHead);

}

0
Oct
03
2009

[原创]中秋偶做

写月一首

—————————————–

似送残霜灯明暗

如洒碎玉水知凉

中元独登照千里

半照游子半照乡

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

自写一首

——————————————-

骐骥空作乐

骈死槽枥间

男儿如有志

驽马可万里

——————————————-

1
Aug
31
2009

最被中国人误读的33个消费符号(zz)

 

Backpackers 背包旅行
背包旅行变成一种时尚,有人把它当成了炫耀的资本,更奇怪的是,在国外背包客都是穷人,参

加旅行团的是有钱人;在中国则正好相反。

Bohemia 波希米亚风

人们常常把"一切看上去疯疯癫癫的打扮"称为波希米亚风。在中国,波希米亚这个概念被无限放大,就连房地产商都在叫卖"波希米亚建筑风格",令人汗颜。

Bordeaux 法国葡萄酒(波尔多 )

在国外,只有少数人可以享受葡萄酒的刺激,而大多数的人只能喝啤酒。在国内,有着无数的文人墨客赞美葡萄洒的雍容华贵。

Broadway 百老汇

因而情节极其简单,场面极其华丽,表演非常夸张,假唱无所不在,在纽约或伦敦取得成功后,便开始全球走穴,大赚其钱,这一点又和《同一首歌》何其相像。

Che Guevara 切·格瓦拉
以贩卖纪念品为生的切·格瓦拉和那个理想主义的战斗者切·格瓦拉未必是同一个人,前者是流

行旗帜,后者是精神导师。

Chivas 芝华士
在国外,威士忌被认为是一种老头子酒,很难想象,会有大学生的毕业派对选择威士忌。

Christmas、Valentine"s day 圣诞节,情人节
圣诞节到底是什么?是圣洁?信仰?欢乐?家庭?爱?毫无疑问,首先是消费。

Cigar 雪茄:是享受,不是做秀
这些中国人眼里的奢侈品,不过是另一个社会主义国家的重要创汇产品罢了。

Credit card 信用卡
中国人支付着全世界最高的信用卡贷款利息(年利率高达18%),却浑然不知危险正在来临。

中国人更热衷于消费文凭 EMBA
比起西方人,中国人更热衷于消费文凭,这背后包含着中国几千年来对教育的热
爱,对学而优则仕的推崇。

Evian 依云水 (一种产自法国的矿泉水,中国是50元一瓶.新加坡6-7新币一瓶)

当被问道"喝点什么"的时候,很多人习惯淡淡地说一句:"我只要依云水。"声音里有掩饰不住的优越感。

Golf 高尔夫

高尔夫既不是贵族运动,也不是平民运动,它是一种健康运动,是一种礼仪,一种素质和一种审美、生活准则。

Haagen-Dazs 哈根达斯

中国被当成奢侈品的哈根达斯在其发源地美国是个极普通的品牌,就如同和路雪之于中国,主要在超市和自动售货机售卖,很少有专门店。

IKEA 宜家

以其DIY的设计风格及昂贵的售价,一时成为小资理想的高端家居品牌。而美国人的评论是"cheapIKEA",他们买家具就像买衣服,好看就买,买来就用,腻了就换。

Lisa Ono 小野丽莎

她不是爵士女伶中最大牌的,但无疑是最具群众基础的,她是小众爵士圈里的"大众歌手",是一道献给大众的"心灵鸡汤"。

Marketplace 大卖场

便宜、甩卖、方便、快捷,大卖场以这样的面目出现在我们面前。我们相信了,但实际上我们感受到了吗?

NM 纳米
纳米是高科技,你不懂科学,就只能相信科学的无所不能。

Olympics 奥运
奥运精神叫做"友谊第一,比赛第二"。但现在,已经被叫卖声淹没了。

无处不在的Paris 巴黎

巴黎到底是什么东西?是艺术,是享受生活,是阳光普照的下午,是优雅的生活模板,其实在我们这里,依然是消费。

Pasta 意粉
意粉于西方人之意义,如同方便面之于东方人。

Resort 度假酒店

一个入住了三亚希尔顿酒店的人,第一感觉是"奢华到令人窒息",而不是度假酒店应有的"轻松和舒适"。

Sex Toy 情趣玩具
情趣玩具是十恶不赦、放荡与色情的淫具吗?在西方,没有人会在意你是否在用
它,有时有人反而会因此认为你是个很注重品质的人。

中国人崇尚Skyscraper 摩天大楼
中国人崇尚摩天大楼,很多时候是因为面子问题。越来越多的外国人感觉到,摩天大楼并不经济。

Snooker 斯诺克

在英国,斯诺克是一项需要西装革履打领结的绅士运动,但在中国,从上世纪80年代至今,是光着膀子在街边打台球。斯诺克的中国特色。

SPA
中国大街小巷里的SPA已经没有等级之分了,云南悦榕庄酒店里的高级水疗被称作SPA,巷子口五

金店旁边的美容院也挂个"SPA"的牌子。好像只要躺在漂着花瓣的木制澡盆里,谁都成了杨贵妃。

SOHO
全称Small Office Home Office,指小型家庭办公室,也指在家里办公的自由职业者。他们没有固定的工作,没有稳定的收入。

Starbucks 星巴客 :卖咖啡到卖情调

星巴客在美国是很物美价廉的大众饮料,算是咖啡中的快餐,但移民到了中国,却成了时尚、优雅情调的元素之一。

Surburbs 郊区生活

家在郊区的好处是,新鲜空气,远离喧闹,但是想在中国过郊区生活,还请做好以下准备:交通、购物,医疗设施等。

The World is Flat《世界是平的》

中国的企业家们也不厌其烦地提起《世界是平的》,何以一本书会受到如此多商界领袖人物的推荐和欣赏?"因为他说出了那些具有影响力的人不能或不便说出的’心里话’。

USA美国

百威啤酒在美国的宣传一直是将百威作为美国男性工人创造的英雄产品,将产品与美国工人的形象及美国传统美德统一在一起。但是在中国,百威是都市泡吧族的最爱,他们大多刚刚从格子间里出来,连西装都来不及换。

Vitamin 维生素

美国人热衷的维E,500粒一瓶价格不到10美元,算下来一天只要人民币1角6分钱,便宜得像白送。虽然国内药房里也有几十元一瓶的维生素,但人们推崇的始终是平均每瓶在300元以上的国外品牌

Whiskey in Green Tea 威士忌兑绿茶

苏格兰人发明了威士忌,中国人发明了威士忌兑绿茶。一位苏格兰记者报道说:"威士忌酒商做梦也没想到,他们的酒会被人这么饮用。"

Yoga 瑜珈

70%的印度人练瑜珈,却很少人去瑜珈馆,因为这是他们日常生活的一部分。我们以为可以用钱来消费健康追随时尚.

1
Aug
30
2009

[求职日记]bebeyond求职讲座心得

今天怀着比较激动的心情,参加了在知春路盈都大厦的beBeyond求职免费讲座,以前一直觉得这类求职讲座挺2的,没什么信息,无非是宣传自己公司的培训,类似于考研班性质。结果发现这次还是有些收获和启示的。撰此短文以记之。

找工作的三个过程:认识自我,认识工作,坚持和信念。

首先,讲认识自我,找工作绝不是说谁来学校招聘了就扔个简历给ta,至于成败利钝,听天由命吧。这一点的主要的意思是认清自己的优势在那里。而优势不光来自于大学4年,研究生3年;人生活在这世上的几十年,都是你的性格上的优势积累的过程。从这几十年的积累来看你自己的性格和优势,会更加准确的把握自己适合哪种类型的工作。这里一个发掘自我的trick就是历数自己从小到大认为比较得意的一些事情,从这些事情中提炼出自己性格方面的优势。例如:虽然平时成绩不是很优秀,但是大考中会有比较好的发挥,这说明你抗压能力比较好,心理调节的能力比较强。如果通过自己的努力成功的协调了某个事情,那么可以在其中发掘自己沟通方面的闪光点。hr面试绝不是想跟你对简历,而是想知道简历之外的故事,简历只是一个基础。有了这些思考,相信可以在跟hr的沟通中有更多的话可以说。

其次,讲认识工作,也就是认识工作本身的性质,对于人的能力的要求,主要看自己是不是匹配。包括行业、公司、职位等。什么样的工作适合什么样的人,所以对自己适合的工作投简历准备,成功率会更高,自己工作了也会更happy。这个就是主要要多做一些了解,了解不同的行业、公司、职位的情况和要求。

最后,讲坚持和信念,成功有时候就在于再坚持那么一小下。一个同学,经过自我发觉,觉得自己有很好的抗拒无聊的工作的能力,适合于做审计类的工作,就去参加pwc的面试,在群面中就被pass掉了,但是在收回小身份牌的时候,他坚持要求hr将小身份牌送给他留作纪念,经过跟hr的长时间argue,虽然没有成功,但是给hr留下了很深刻的印象,在下次的霸王面中,终于还是起到了作用。另外一个同学,在hr电话他面试失败的时候,跟hr长聊了一个多小时,虽然这样很不人道,但是还是争取到了一个offer。还有的同学霸王面了40多次。我们应该从这些坚持中有所体悟。

其实,找工作面试就是一个推销自己的过程,跟卖东西也没什么区别,无非是说明这东西多么好,多么适合你的需求。千言万语汇成一句话:我就是你们想要的。

另附一个简单的时间表:

知名外企:  9月中旬 —- 10月底
一般外企私企:  10月初  —- 年底
国企:  11月份 —- 来年3月份
公务员: 11月份 —- 来年

1