严蔚敏《数据结构（C语言版）》讲义

数据结构是计算机科学中的一个重要分支，它研究的是如何合理组织和存储数据，以及如何高效地处理这些数据。数据结构不仅关注数据的逻辑结构，即数据元素之间的关系，而且还关注数据的物理结构，即数据在计算机内存中的存储方式。下面详细阐述数据结构的基础知识点。 我们要明确什么是数据结构。数据结构可以理解为一组数据元素的集合，这些元素之间存在着一种或多种特定的关系。为了更好地理解数据结构，我们需要先了解一些基本概念和术语，包括数据、数据元素、数据项、数据对象以及数据结构本身。 数据（Data）是信息的一种符号表示，是能被计算机处理的所有符号的总称。数据元素（DataElement）是数据的基本单位，是数据集合中的单个实体，通常在程序中作为一个整体考虑和处理。数据项（DataItem）是数据元素的不可分割的最小单位，是构成数据元素的成分。数据对象（DataObject）是性质相同的数据元素的集合，是数据的一个子集。 数据结构（DataStructure）不仅包含数据元素的集合，还包含它们之间的关系。逻辑结构是指数据元素之间的抽象关系，物理结构是指数据结构在计算机内存中的表示。数据结构的物理存储方式也称为存储结构。数据结构通常分为以下四种基本逻辑结构：集合结构、线性结构、树型结构和图状结构或网状结构。集合结构中的数据元素之间没有特定的关系；线性结构中的数据元素是一对一的关系；树型结构中的数据元素是一对多的关系；图状结构或网状结构中的数据元素是多对多的关系。 抽象数据类型（Abstract Data Type，ADT）是对数据结构的数学模型和定义在此模型上的一组操作的描述。它是一种抽象概念，与具体的数据类型和存储结构无关，仅描述数据的逻辑结构及在此结构上的一组算法。抽象数据类型的三元组形式为（D，S，P），其中D是数据元素的集合，S是定义在D上的关系的集合，P是定义在D上的操作的集合。 在数据结构的研究中，算法是解决问题的步骤描述，它们对数据结构的效率至关重要。算法设计时要考虑到多个方面的要求，如正确性、可读性、健壮性等。算法效率的度量通常涉及时间复杂度和空间复杂度，时间复杂度反映算法运行时间随输入规模增长的变化趋势，空间复杂度则反映算法执行过程中所需额外空间随输入规模增长的变化趋势。 数据结构是编程和软件开发中不可或缺的一部分，它直接关联到程序的效率和质量。通过设计合适的数据结构，我们可以为数据处理算法提供良好的基础，使得算法能够更加高效地运行。在学习和应用数据结构时，理解这些基本概念和术语至关重要。严蔚敏的《数据结构（C语言版）》讲义为我们提供了一个入门和复习数据结构知识的良好平台，尤其适合初学者进行系统学习。