下载掌阅APP，畅读海量书库
立即打开
数据结构是计算机相关专业的核心课程 。数据结构的知识为后续专业课程的学习提供了必要的知识基础和技能准备，打好“数据结构”这门课程的基础，对于学习计算机专业的其他课程，如操作系统、编译原理、数据库管理系统、软件工程、人工智能等都是十分有益的。而且，所有的计算机系统软件和应用软件都要用到各种类型的数据结构，因此要想更好地运用计算机来解决实际问题，仅掌握几种计算机程序设计语言是远远不够的，要想有效地使用计算机、充分发挥计算机的性能，还必须学习和掌握好数据结构的有关知识。
在计算机发展的初期，人们使用计算机的目的主要是处理数值计算问题。使用计算机来解决一个具体问题时，一般需要经过下列几个步骤：首先要从该具体问题抽象出一个适当的 数学模型 ，然后设计或选择一个解此数学模型的 算法 ，最后编写出程序进行调试和测试，直至得到最终的解答。由于当时所涉及的运算对象是简单的整型、实型或布尔类型数据，数据量小而且结构简单，所以程序设计者的主要精力集中于程序设计的技巧上，而无须重视如何组织数据。
随着计算机应用领域日益广泛和软/硬件技术的发展，非数值计算问题越来越重要。据资料统计，目前处理非数值计算性问题占用了90%以上的机器时间。这类问题涉及的数据结构更为复杂，数据元素之间的相互关系一般无法用数学方程式加以描述。因此，解决这类问题的关键不再是数学分析和计算方法的应用，而是要设计出合适的数据结构，才能有效解决问题。下面就是这一类问题的几个具体事例。
【例1-1】成绩检索系统。要求计算机提供自动查询的功能，如查找某个学生的单科成绩或平均成绩，查询某门课程的最高分等。
实现这个系统首先需要考虑如何组织数据，然后按照相应的算法编写程序以便实现计算机自动检索功能。例如，可以将每个学生的各项信息（学号、姓名、各项成绩等）用某种构造的数据类型表示，全部学生信息按学号次序排列，组织成一个线性表格（见表1-1）。根据查询需要可以设计出各种查询算法。
表1-1 学生成绩表
类似的计算机应用还有电话号码自动查询系统、图书信息检索系统、仓库库存管理系统等。在这类文档管理的数学模型中，计算机处理对象之间通常存在着一种简单的线性关系，这类数学模型可称为线性数据结构。
【例1-2】教学计划编排问题。一个教学计划包含许多课程，课程之间，有些必须按规定的先后次序进行，有些则没有次序要求。也就是说，有些课程之间有先修和后续的关系，有些课程可以任意安排次序，见表1-2。
表1-2 计算机专业的课程设置
【例1-3】棋盘布局问题。要求将4个棋子布在4×4的棋盘上，任意两个棋子既不在同一行或同一列，也不在同一对角线上。
此问题的处理过程不是根据某种确定的计算法则，而是利用试探和回溯的探索技术求解。为了求得合理布局，在计算机中要存储布局的当前状态。从最初的布局状态开始，一步步地进行试探，每试探一步形成一个新的状态，整个试探过程形成了一棵隐含的状态树，如图1-1所示。回溯法求解过程实质上就是一个遍历状态树的过程。在这个问题中所出现的树也是一种数据结构，它可以应用在许多非数值计算问题中。
图1-1 棋盘布局问题中隐含的状态树
计算机专业各门课程之间的次序关系可用一个称作图的数据结构来表示。如图1-2所示，有向图中的每个顶点表示一门课程，如果从顶点c i 到c j 之间存在有向边＜c i ，c j ＞，则表示课程c i 必须先于课程c j 进行。
图1-2 表示课程之间优先关系的有向图
由以上三个例子可见，描述这类非数值计算问题的数学模型不再是数学方程，而是诸如 表、树、图之类的数据结构 。非数值计算问题在计算机应用中体现出越来越重要的价值。数据结构即为主要研究非数值计算的程序设计问题中所出现的操作对象及它们之间存在关系和操作的一门学科。
学习数据结构是为了了解计算机处理对象的特性，能将实际问题中所涉及的处理对象在计算机中表示出来并对它们进行处理。与此同时，通过算法训练来提高逻辑思维能力，通过程序设计的技能训练来提高综合应用能力和专业素质。
数据结构与数学、计算机硬件和软件有十分密切的关系。 数据结构是介于数学、计算机硬件和计算机软件之间的一门计算机科学与技术专业的核心课程，是高级程序设计语言、编译原理、操作系统、数据库、人工智能等课程的基础 。同时，数据结构技术也广泛应用于信息科学、系统工程、应用数学及各种工程技术领域。
数据结构课程主要与软件开发过程中的设计阶段有关，同时涉及编码和分析阶段的若干基本问题。此外，为了构造出好的数据结构及其实现，还需 考虑数据结构及其实现的评价与选择 。因此，数据结构课程的内容体系包括三个层次的五个“要素”，见表1-3。
表1-3 数据结构课程的内容体系
数据结构的核心技术是 分解与抽象 。通过分解将处理要求划分成各种功能，再通过抽象舍弃实现细节，就得到了运算的定义。上述两个方面的结合使我们将问题变换为数据结构。这是一个从具体（即具体问题）到抽象（即数据结构）的过程。然后，通过增加对实现细节的考虑进一步得到 存储结构和实现算法 ，从而完成设计任务。这是一个从抽象（即数据结构）到具体（即具体实现）的过程。熟练掌握这两个过程是数据结构课程在专业技能培养方面的基本目标。
数据结构作为一门独立的课程在国外是从1968年才开始的，在此之前其有关内容已散见于编译原理及操作系统之中。20世纪60年代中期，美国的一些大学开始设立相关课程，但当时的课程名称并不叫数据结构。1968年，美国的唐·欧·克努特教授开创了数据结构的最初体系，他所著的《计算机程序设计技巧》第一卷《基本算法》是第一本较系统地阐述数据的逻辑结构和存储结构及其操作的著作。从20世纪60年代末到70年代初，出现了大型程序，软件也相对独立，结构程序设计成为程序设计方法学的主要内容，人们越来越重视数据结构。从20世纪70年代中期到80年代，各种版本的数据结构著作相继出现。目前，数据结构的发展并未终结：一方面，面向各专门领域中特殊问题的数据结构得到研究和发展，如多维图形数据结构等；另一方面，从抽象数据类型和面向对象的观点来讨论数据结构已成为一种新的趋势，越来越被人们所重视。