1.1　为什么要学习数据结构

1．数据结构的前世今生

数据结构作为一门独立的课程，是从1968年开始在美国设立的。1968年，算法和程序设计技术的先驱，美国的唐·欧·克努特（Donald Ervin Knuth，中文名为高德纳）教授开创了数据结构的最初体系，他所著的《计算机程序设计艺术》第一卷《基本算法》是第一本较系统地阐述数据的逻辑结构和存储结构及其操作的著作。从20世纪60年代末到20世纪70年代初，随着大型程序的出现，软件也相对独立，结构化程序设计成为程序设计方法学的主要内容，数据结构显得越来越重要。

从20世纪70年代中期到20世纪80年代，各种版本的数据结构著作相继出现。目前，数据结构的发展并未就此止步，随着大数据和人工智能时代的到来，数据结构开始在新的应用领域发挥重要作用。面对爆炸性增长的数据和计算机技术的发展，人工智能、大数据、机器学习等应用领域需要处理大量多维的数据，因此需要对数据进行组织和处理，数据结构的重要性不言而喻。

图1-1　高德纳肖像

小知识：Donald Ervin Knuth撰写了计算机科学理论与技术的经典巨著《计算机程序设计艺术》（The Art of Computer Programming）（共5卷），该著作被《美国科学家》杂志列为20世纪最重要的12本物理科学类专著之一，可以与爱因斯坦的《相对论》、狄拉克的《量子力学》、理查·费曼的《量子电动力学》等经典著作相媲美。因此，高德纳在36岁时就荣获ACM 1974年年度的图灵奖，迄今为止，他仍然是最年轻的图灵奖获得者纪录保持者。高德纳肖像如图1-1所示。

此外，高德纳花了整整9年的时间完成了对西文印刷行业具有革命性变革的TeX排版软件和METAFONT字形设计软件，并因此获得了ACM的软件系统奖（Software System Award）。《计算机程序设计艺术》推出之后，真正能读完读懂的人为数不多，据说比尔·盖茨花费了几个月才读完第一卷，然后说，如果你觉得自己是一名优秀的程序员，那就去读《计算机程序设计艺术》吧。对我来说，读完这本书不仅花了好几个月，而且还要求我有极高的自律性。如果你能读完这本书，不妨给我发个简历。

2．数据结构的作用与地位

数据结构是介于数学、计算机硬件和计算机软件三者之间的一门核心课程。数据结构已经不仅仅是计算机相关专业的核心课程，还是其他非计算机专业的主要选修课程之一，其重要性不言而喻。数据结构与计算机软件的研究有着密切的关系，开发计算机系统软件和应用软件都会用到各种类型的数据结构。例如，算术表达式求值问题、迷宫求解、机器学习中的决策树分类等分别利用了数据结构中的栈、树进行解决。因此，要想更好地运用计算机来解决实际问题，使编写出的程序更高效，具有通用性，仅掌握计算机程序设计语言是难以应付众多复杂问题的，还必须学习和掌握好数据结构方面的知识。数据结构是学习操作系统、软件工程、人工智能、算法设计与分析、机器学习、大数据等众多后继课程的重要基础。

在计算机刚出现的那些年，人们使用计算机的主要目的是处理数值计算问题。当时涉及的运算对象是简单的整型、实型或布尔类型数据，程序设计者的主要精力集中于程序设计的技巧上。随着计算机应用领域的扩大和软、硬件的发展，非数值计算问题成为各研究领域要处理的主要对象。这类问题涉及的数据结构更为复杂，数据元素之间的相互关系一般无法用数学方程式描述，解决这类问题的关键不再是数学分析和计算方法，而是要选择恰当的数据结构，然后设计合适的算法。因此，学习数据结构与算法有利于培养我们的逻辑思维能力和解决复杂软件工程问题的能力。