下载
第2章 算法与数据结构
总而言之，只有熟悉了这个领域的工具和技术才能对特殊的问题提供正确解答，
只有丰富的经验才能提供坚实的专业性结果。
Raymond Fielding，《特殊效果立体电影的技术》
算法和数据结构的研究是计算机科学的重要基石。这是一个富集优雅技术和复杂数学分
析结果的领域。这个领域并不是理论嗜好者们的乐园和游戏的场所：一个好的算法或数据结
构可能使某个原来需要用成年累月才能完成的问题在分秒之中得到解决。
在某些特殊领域，例如图形学、数据库、语法分析、数值分析和模拟等等，解决问题的
能力几乎完全依赖于最新的算法和数据结构。如果你正要进入一个新领域去开发程序，那么
首先需要弄清楚在这里已经有了些什么，以免无谓地把时间浪费在别人早已做好的东西上。
每个程序都要依靠算法与数据结构，但很少有程序依赖于必须发明一批全新的东西。即
使是很复杂的程序，比如在编译器或者网络浏览器里，主要的数据结构也是数组、表、树和
散列表等等。如果在一个程序里要求某些更精巧的东西，它多半也是基于这些简单东西构造
起来的。因此，对大部分程序员而言，所需要的是知道有哪些合适的、可用的算法和数据结
构，知道如何在各种可以互相替代的东西之中做出选择。
这里要讲的是一个核桃壳里的故事。实际上基本算法只有屈指可数的几个，它们几乎出
现在每个程序中，可能已经被包含在程序库里，这就是基本检索和排序。与此类似，几乎所
有的数据结构都是从几个基本东西中产生出来的。这样，本章包含的材料对于每个程序员都
是熟悉的。我们写了些能够实际工作的程序，以使下面的讨论更具体。如果需要，你可以抄
录这些代码，但要事先检查用的是哪种语言，你是否有它所需要的库。
2.1 检索
要存储静态的表格式数据当然应该用数组。由于可以做编译时的初始化，构建这种数组
非常容易( J a v a 的初始化在运行中进行。只要数组不是很大，这就是一个无关紧要的实现细节 )。
要检查学生练习中是否对某些废话用得太多，在程序里可能会定义：
检索程序必须知道数组里有多少元素。对这个问题的一种处理方法是传递一个数组长度参数。
这里采用的是另一种方法，在数组最后放一个 N U L L 作为结束标志。
评论0