1.4 关于数据结构的学习

计算机发展始终遵循摩尔（1965）法则：“芯片容量每18个月加倍”，新摩尔定理：“计算机性能每18个月提高一倍，价格每半年降低一半”，是否已经到达极限？是否会不再遵循摩尔法则？杨振宁在西安科协2000年会议上，明确地答复了这个问题：是什么原因促使芯片容量长期成倍地增长，新原理、新方法、新道理，是维持创新的源泉，创新是人类知识发展、生产发展的重要因素。

计算机机器性能价格比持续提高，硬件发展如此之快，是否没有必要去追求提高算法的时间复杂度、没有必要去追求节省算法占用存储空间的数目呢？不是没有必要，而是要求越来越高。原因之一是，由于机器性能价格比的提高，人们所面临的处理问题的问题规模越来越大，要把过去不可能解决的问题变得可能，必须要求高性能的算法；另一个原因是，即使在同一问题规模情况下，算法性能好坏差别很大，一个是O(n)数量级，一种是O(2n)数量级，当n=32时，2n的结果都已很大，即使n再增大一倍，2n几乎都已经无法表述，这不是硬件发展速度所能满足的。由此说明，硬件速度的提高决不是人们可以不重视算法性能的理由，而是人们追求高性能算法的动力。图1.8所示为数据结构与其他课程关系图。

1.数据结构课程地位

明确提出数据结构概念不过30多年，“数据结构”作为一门独立课程在国外1968年开始设立，我国从20世纪80年代初才开始正式开设“数据结构”课程。“数据结构”课程较系统地介绍了软件设计中常用数据结构及相应的存储结构和算法，系统地介绍了常用的查找和排序技术，并对各种结构与技术进行分析和比较，内容非常丰富。数据结构涉及多方面的知识，如计算机硬件范围的存储装置和存取方法，软件范围中的文件系统、数据的动态管理、信息检索，以及数学范围中关于集合、逻辑的知识，还有一些综合性的知识（如数据类型、程序设计方法、数据表示、数据运算、数据存取等），是计算机专业一门重要的专业技术基础课程。数据结构的内容将为操作系统、数据库原理、编译原理等后续课程的学习打下良好的基础，数据结构课程不仅讲授数据信息在计算机中的组织和表示方法，还训练高效地解决复杂问题程序设计的能力，因此数据结构是数学、计算机硬件、计算机软件三者之间的一门核心课程，“数据结构”课程是计算机专业提高软件设计水平的一门关键性课程。

数据结构发展趋势包括两个方面：一方面，面向专门领域中特殊问题的数据结构的研究和发展，如图形数据结构、知识数据结构、空间数据结构；另一方面，从抽象数据类型的角度，用面向对象观点来讨论数据结构，已成为新的发展趋势。

2.数据结构课程学习特点

“数据结构”课程教学目标要求学生学会分析数据对象特征，掌握数据组织方法和计算机的表示方法，以便为应用所涉及的数据选择适当的逻辑结构、存储结构及相应算法，初步掌握算法时间、空间分析的技巧，培养良好的程序设计技能。

人类解决问题的思维方式可分为两大类：一类是推理方式，凭借公理系统思维方法，从抽象公理体系出发，演绎、归纳、推理，求证结果，解决特定问题；另一类是算法方式，凭借算法构造思维方式，从具体操作规范入手，通过操作过程的构造和实施解决特定问题。开发一个优秀的软件系统过程中所凭借的思维方法本质上不同于常规数学训练的公理系统思维方法，而是一种算法构造性思维方法。系统开发是创造性思维过程的实现，因而，对于一名开发人员，只知道开发工具的语言规则和简单使用过程是不够的。首先要有科学方法指导开发过程；然后在编程技术应用技能上积累提高。让学生理解、习惯、熟悉这一套算法构造思维方法，是计算机软件课程教学的重要内容和主要难点。

“数据结构”的学习过程是进行复杂程序设计的训练过程。技能培养的重要程度不亚于知识传授。难点在于：理解授课内容与应用知识解答复杂问题之间的素质能力差距。培养优良的算法设计思想、方法技巧与风格，进行构造性思维训练过程，强化程序抽象能力，培养数据抽象能力。从某种意义上说，数据结构是程序设计的后继课程。如同学习英语一样，学习英语不难，学好英语不易，要提高程序设计水平必须经过艰苦的磨炼。因此，学习数据结构，仅从书本上学习是不够的，必须经过大量的实践，在实践中体会构造性思维方法，掌握数据组织与程序设计的技术。

3.关于本书内容编写说明

（1）本书基本结构

基本结构分为如下四大部分。

第一部分：绪论。

第二部分：基本的数据结构。包括：线性结构（第2～4章）——线性表、栈和队列、串和数组；非线性结构（第5、6章）——树、图。

第三部分：基本技术。包括查找与排序（第7、8章）。

第四部分：实验实训。

（2）本书内容编排模式

本书所列出的程序均在Turbo C 2.0下调试通过，所有算法均采用严谨的C语言进行描述，只需加以必要的类型定义与调用，即可上机运行使用。

每章附有习题，以便于读者做配套练习。