1.1 引言

• 数据结构的含义：简答地说，数据结构(Data Structure)是计算机组织数据和存储数据的方式。更进一步地说，数据结构是指一组相互之间存在一种或多种特定关系的数据的组织方式和他们在计算机内的存储方式，以及定义在该组数据上的一组操作。合理的数据结构可降低程序设计的复杂性，提高程序执行的效率。
• 计算机解决一个具体问题时，一般需要经过以下几个步骤：
  • 1.从具体的问题抽象出一个适当的数学模型；
  • 2.设计一个求解该数学模型的算法；
  • 3.用某种计算机语言编写实现该算法的程序，调试和运行程序直至最终得到问题的解答。
• 1976 年瑞士计算机科学家尼克劳斯·维尔特(Niklaus Wirth)曾提出一个著名公式：算法+数据结构=程序。

1.2 基本概念和术语

1. 数据、数据元素和数据项

   • 数据：所有被计算机存储、处理的对象。
   • 数据元素：数据的基本单位，在程序中作为一个整体而加以考虑和处理。
   • 数据项：数据元素由数据项组成。在数据库中数据项又称为字段或域。它是数据的不可分割的最小标识单位。

2. 数据的逻辑结构

   • 含义：数据的逻辑结构是指数据元素之间的逻辑关系。所谓逻辑关系是指数据元素之间的关联方式或“邻接关系”。
   • 根据数据组织的形式，分为 4 类：
     • 1.集合。集合中任意两个结点之间都没有邻接关系，组织形式松散。
     • 2.线性结构。线性结构中结点按逻辑关系依次排列形成一条“链”，结点之间一个一个依次相邻接。
     • 3.树形结构。树形结构具有分支、层次特性，其形态像自然界中的树，上层的结点可以和下层多个结点相邻接，但下层结点只能和上层的一个结点相邻接。
     • 4.图结构。图结构最复杂，其中任何两个结点都可以相邻接。
   • 数据的逻辑结构只是一种数学模型，体现了数据的组织方式，要在计算机中实现逻辑结构，还依赖它在计算机中的存储结构。

3. 数据的存储结构

   • 一个存储结构包括两个部分：1.存储数据元素；2.数据元素之间的关联方式。
   • 表示关联方式主要有顺序储存方式和链式储存方式。
     • 顺序储存，是指所有存储结点存放在一个连续的存储区里。
     • 链式存储，是指每个存储结点除了含有一个数据元素外，还包含指针，每个指针指向一个与本结点有逻辑关系的结点，用指针表示数据元素之间的逻辑关系。
   • 除了上诉两种存储方式之外，还有索引存储方式和散列存储方式。
   • 一种逻辑结构可以采用一种或几种存储方式来表达数据元素之间的逻辑关系，相应的存储结构称为给定逻辑结构的存储实现或存储映像。存储结构可以分别在机器级和语言级别上讨论。
   • 数据的逻辑结构和数据的存储结构

4. 运算

   • 运算是指在某种逻辑结构上施加的操作，即对逻辑结构的加工。这种加工以数据的逻辑结构为对象。
   • 数据结构的三要素是：逻辑结构、存储结构、数据运算。

1.3 算法及描述

• 概念： 运算的实现是指该运算的算法。算法是计算机科学的一个基本概念，也是程序设计的一个核心概念。一个算法规定了求解给定问题所需的处理步骤及其执行顺序，使得给定问题能在有限时间内被求解。
• 算法可以用某种语言加以描述。本书采用类 C 语言来描述算法。

1.4 算法分析

• 一个问题可以有多种不同的求解算法，这就产生了如何评价这些算法的问题。通过评价算法好坏的因素包括：
  • 1.正确性。
  • 2.易读性。
  • 3.健壮性。即使输入非法数据，算法也能适当地做出反应或处理，不会产生预料不到的运行结果。
  • 4.时空性。是指算法的时间性能和空间性能，前者是算法包含的计算量，后者是算法需要的存储量。

1. 时间复杂度

   • 时间复杂度常见的阶数有常数阶 O(1)；对数阶 O(log2n)、线性阶 O(n)、多项式阶 O(n Ｃ)和指数阶 O(Cⁿ)，C 为大于 1 的正整数。
   • 常见的多项式阶有 O(n²)和 O(n³)，常见的指数阶有 O(2ⁿ)。
   • 通常认为，时间复杂度具有指数阶的算法是实际不可计算的，而阶数低于平方阶的算法是高效率的。
   • 时间复杂度与空间复杂度的计算
   • 算法的时间与空间复杂度
   • 时间复杂度和大 O 表示法
   • 

2. 空间复杂度

   • 空间复杂度是对一个算法在运行过程中临时占用存储空间大小的量度。一个算法在执行期间所需要的存储空间量应包括以下三个部分：
     • 1.程序代码所占用的空间
     • 2.输入数据所占用的空间
     • 3.辅助变量所占用的空间

1.5 本书的组织结构

• 第一章讨论问题的求解步骤。讨论数据结构、数据、数据元素、数据项、数据逻辑结构、数据存储结构、运算、算法时间复杂度和空间复杂度等概念。
• 第二、三章讨论线性结构。
• 第四章讨论树形结构。
• 第五章讨论图结构。
• 第六章讨论查找。
• 第七章讨论排序。

1.6 小结

• 数据结构是计算机科学中的一门综合性的专业基础课。
• 了解用计算机解决一个问题的步骤，这是一个渐进的过程，首先对实际问题进行数学建模，描述数据的逻辑结构，将处理要求转换为基本运算，然后建立对应的存储结构，以便能被计算机存储处理，设计出一个算法，最后编写程序。
• 掌握算法分析方法，能分析一个简单算法的时间复杂度和空间复杂度。

思考与练习

1.填空题

1. 从数据结构的观点看，通常所说的“数据”应分为三个不同的层次，即原始数据、数据元素、数据项。
2. 数据项又称为字段或域，它是数据的不可分割的最小标识单位。
3. 根据数据元素之间关系的不同特性，通常有线性结构、图结构、树形结构、集合结构 四类基本逻辑结构，他们反映了四类基本的数据组织形式。
4. 在一般情况下，一个算法的时间复杂度是的函数。
5. 常见算法时间复杂度的阶数有常数阶、对数阶、线性阶、平方阶、和指数阶。通常认为，具有指数阶量级的算法是的，而量级低于平方阶的算法是的。

2.应用题或解答题

1. 什么是数据、数据元素以及数据项？它们有何区别？

   • 数据：所有被计算机存储、处理的对象。
   • 数据元素：数据的基本单位，在程序中作为一个整体而加以考虑和处理。
   • 数据项：数据元素由数据项组成。在数据库中数据项又称为字段或域。它是数据的不可分割的最小标识单位。

2. 什么是数据的逻辑结构？什么是数据的存储结构？

   • 数据的逻辑结构：是指数据元素之间的逻辑关系。数据的逻辑结构分为线性结构和非线性结构，线性表是典型的线性结构；集合、树和图是典型的非线性结构。
   • 数据的存储结构: 存储结构是指数据结构在计算机中的映像，也称物理结构。它包括数据元素的表示和关系的表示，是逻辑结构用计算机语言的实现。数据的存储结构主要有：顺序存储、链式存储、索引存储和散列存储。

3. 数据逻辑结构与存储结构有什么关系？

   • 简述逻辑结构与存储结构的关系

4. 用计算机实现例 1-2 地图的着色问题，需要经过哪些主要步骤？每个步骤的主要工作是什么？

   • C/230420.c
   • 地图染色算法

3.算法设计题

1. 设计算法在整型数组 A[n]中查找值为 K 的元素，若找到，则输出其位置 i(0<=i<=n-1)，否则输出-1 作为标志，并分析算法的时间复杂度。

   • 算法复杂度分析

2. 写出计算方阵 A[n][n]与 B[n][n]乘积 C[n][n]的算法，分析算法的时间复杂度。