数据结构的概念中南大学教程.docVIP

数据结构的概念 美国计算机科学家Donald Ervin Knuth首次提出了数据结构和算法的概念，并在他所著的《计算机程序设计艺术第1卷 基本算法》中首次较系统地阐述了数据的逻辑结构、存储结构及其操作。随后，美国的一些大学开始设立与数据结构相关的课程。同时，结构化程序设计逐渐成为当时程序设计的主流方法，人们也越来越重视数据结构。各种版本的数据结构著作也相继出现。 数据结构作为计算机科学的一门分支学科，主要研究非数值计算的程序设计问题中计算机的操作对象、对象之间的关系和操作等。为了编写出“好”的程序，必须分析待处理对象的特性及各处理对象之间存在的关系。 数据结构的内容包括3个层次的5个“要素”，如表1-1所示。其中的3个层次分别为抽象、实现与评价。通过抽象，舍弃数据元素的具体内容，就得到逻辑结构表示，通过分解将处理要求划分成各种功能，再通过抽象舍弃实现细节，就得到基本操作的定义。上述两个方面的结合将问题变换为数据结构，这是一个从具体（即具体问题）到抽象（即数据结构）的过程。最后，通过增加对实现细节的考虑进一步得到存储结构和实现运算，从而完成设计任务，而这是一个从抽象（即数据结构）到具体（即具体实现）的过程。熟练掌握这两个过程是数据结构课程在专业技能培养方面的基本目标。在这个过程中需要对不同结构及其实现的性能进行评价，从而获得最佳实践方案。 表1-1　数据结构课程内容体系 针对要处理的问题，设计最有利于操作系统处理的数据结构时需考虑下列因素。 (1) 数据的数量。 (2) 数据的使用次数和方式。 (3) 数据的性质是动态的还是静态的。 (4) 数据结构化后需要多大的存储空间。 (5) 存取结构化后的数据所需花费的时间。 (6) 是否容易程序化。 目前，“数据结构”已经是计算机科学及相关专业的一门专业基础课。它与数学、计算机硬件和计算机软件之间的关系如图1-1所示。在计算机科学中，数据结构不仅是一般程序设计的基础，而且是设计和实现编译程序、操作系统以及数据库系统等大型程序的基础。所有的计算机系统软件和应用软件都要用到各种类型的数据结构。因此，学好“数据结构”这门课程，对学习计算机专业的其他课程都是十分有益的。 为什么要学习数据结构 在计算机发展的初期，人们使用计算机的主要目的是处理数值计算问题。使用计算机解决具体问题一般需要经过以下几个步骤：首先从具体问题抽象出适当的数学模型，然后设计或选择解此数学模型的算法，接着编写程序并进行调试、测试，直至得到最终的解答。 由于最初涉及的运算对象是简单的整型、实型或布尔型数据，所以程序设计者的主要精力集中于程序设计的技巧上，而无需重视数据结构。随着计算机应用领域的扩大和软硬件的发展，非数值计算问题显得越来越重要。据统计，当今处理非数值计算问题占用了90%以上的机器时间。这类问题涉及的数据结构更为复杂，数据元素之间的相互关系一般无法用数学方程式加以描述。因此，解决这类问题的关键不再是数学分析和计算方法，而是要设计出合适的数据结构。 著名的瑞士计算机科学家沃思（N.Wirth）教授曾提出： 算法 + 数据结构＝程序 程序设计的实质是对实际问题设计/选择好的数据结构和好的算法，而好的算法在很大程度上取决于描述实际问题的数据结构。 例1-1　电话号码查询问题。编写一个查询某个私人电话号码的程序。要求任意给出的一个姓名，若该人有电话号码，则迅速找到其电话号码；否则指出该人没有电话号码。 要解决此问题首先需构造一张电话号码登记表。表中每个结点存放两个数据项：姓名和电话号码。 能否写出好的查找算法，取决于这张表的结构及存储方式。最简单的方式是将表中结点顺序地存储在计算机中。查找时从头开始依次查对姓名，直到找出正确的姓名或是遍历整个表均没有找到为止。这种查找算法对一个有少量私人电话的区域或许是可行的，但对一个有成千上万私人电话的城市就不适用了。若这张表是按姓氏排列的，则可另建一张姓氏索引表，采用如图1-2所示的存储结构。查找时先在左边的索引表中查对姓氏，然后根据索引表中的地址到右边的电话号码登记表中核查姓名，这样查找登记表时就无需查找其他姓氏的名字了。因此，在这种新的结构上产生的查找算法就更加有效。 诸如此类的还有电话自动查号系统、考试查分系统、仓库库存管理系统等。在这类文档管理的数学模型中，计算机处理的对象之间通常存在着一种简单的线性关系。这类数学模型可称为线性的数据结构。 图1-2　电话号码的索引存储 例1-2　四皇后问题，即在一个4′4的棋盘上放置4个皇后，使得任意两个皇后在行、列和斜方向上都不在一条线上。 在四皇后问题中，处理过程不是根据某种确定的计算法则，而是利用试探和回溯的探索技术求解。为了求得合理布局，在计算机中要存储布局的当前状态。从最初的布局状态开始，一步步地进