第3章

结构之法

——字符串及链表的探索

研究院每天下午三点钟有大量新鲜水果供应，这是大家每天盼望的时刻，部分同事还拍了一部叫“三点”的电影，限量发行。

这一章覆盖了常用的数据结构。对字符串、链表、队列和树等数据结构的处理几乎是每个程序中会涉及的问题。同学们在课堂上也学过，这些问题有什么好考的呢？

大家都知道二叉树的前序、中序和后序遍历算法，但是当给出了两个遍历输出的结果，要求还原二叉树的时候，就能考察出大家是否真正掌握了这些不同遍历算法的含义及使用它们的办法。

有些同学对于“指针”比较恐惧，笔者也听说某些大学里“C语言”这门课不讲指针，于是学生和老师在上课的时候都轻松了一阵子，但是在找工作和实际工作中，就不轻松了－“出来混，总是要还的”。事实上指针就是内存中的地址，没什么可怕的。

有不少同学学习了Java、C#，这些现代的语言和运行环境（例如Java VM、CLR）通常把实现的细节给掩盖了。你觉得很方便，例如：要排序，则array.sort()，要新的实体，就new()一个，不用担心什么时候需要释放，多好！但是不要忘了有句谚语：The devil is in the details。

在“操控CPU使用率”这个面试题目中，有一个应聘者的C#代码从逻辑上看都没有任何问题，但是在运行中，CPU的使用率就是不平滑，会突然产生巨大的抖动，然后回归正常。反复研究之后，发现问题原来出自——

TimeSpan ts＝new TimeSpan();

这句话没有错，但是他把这句话放在了一个循环里面，这样在很短的时间内，程序就创建了大量的TimeSpan对象。程序员不管释放，但是CLR要管，所以CLR就要经常进行垃圾清理（GC）工作，导致CPU的使用率急剧上涨。这些details（细节）处理不好，你的程序就会出现你不能理解的奇怪行为。