第一章 数据结构绪论

从逻辑上可以把数据结构分为线性结构和非线性结构， 主要包括：集合、线性、树和图形结构，其中集合、
树和图形结构都属于非线性结构。
Data structures
常用术语和基本概念
❖数据的逻辑结构(Logic Structure)
根据数据元素之间关系的不同特性，通常有4类基本 数据结构：
(1) 集合(Set)：该结构中的数据元素除了存在“同 属于一个集合”的关系外，不存在任何其它关系。
Data structures
1 数据结构概述 2 常用术语和基本概念 3 数据类型 4 算法和算法分析 5 本章小结
目录
Data structures
1.1 数据结构 概述
数据结构概述
❖ 数据结构与算法
数据结构(Data Structure)+算法 (Algorithm)=程序(Program)
Data structures
数据类型
❖ 抽象数据类型
❖ 3.本书在用C语言描述时的约定
(1) C语言的数组元素的下标从“0”开始，为此，在 表示数据结构时，数据元素的序号也从0开始。
(2) 数据元素的类型约定为ElemType。具体的类型 可以由用户在使用时定义：
typedef int ElemType /*定义数据类型为int*/
(2) 线性结构(Linear Structure)：该结构中的数 据元素存在着一对一的关系。
(3) 树形结构(Tree Structure)：该结构中的数据 元素存在着一对多的关系。
(4) 图状结构(Graphic Structure)：该结构中的 数据元素存在着多对多的关系。
Data structures
讲授常用的算法，程序员也可以直接拿来或经过少许 的修改就可以使用，并且可以通过算法训练来提高程 序设计水平。

1.2 数据结构概述
1.2.2什么是数据结构 例1-1 在八皇后问题中，处理过程不是根据某种确定的 计算法则，而是利用试探和回溯的探索技术求解。为了求 得合理布局，在计算机中要存储布局的当前状态。从最初 的布局状态开始，一步步地进行试探，每试探一步形成一 个新的状态，整个试探过程形成了一棵隐含的状态树。如 图1.1所示（为了描述方便，将八皇后问题简化为四皇后 问题）。回溯法求解过程实质上就是一个遍历状态树的过 程。在这个问题中所出现的树也是一种数据结构，它可以 应用在许多非数值计算的问题。
1.2 数据结构概述
1.2.1 学习数据结构的必要性 因此，掌握好数据结构课程的知识，对于提高解决实际问 题的能力将会有很大的帮助。实际上，一个“好”的程序 无非是选择一个合理的数据结构和好的算法，而好的算法 的选择很大程度上取决于描述实际问题所采用的数据结构 。所以，要想编写出好的程序，仅仅学习计算机语言是不 够的，必须扎实的掌握数据结构的基本知识和基本技能。
1.2 数据结构概述
1.2.2什么是数据结构 一般而言，利用计算机解决一个具体问题时，大致需要经 过如下几个步骤：（1）从具体问题抽象出一个合适的数 学模型；（2）设计一个解此数学模型的算法；（3）编 写出程序，进行测试、调整直到最终解答。寻求数学模型 的实质是分析问题，从中提取操作的对象，并找出这些操 作对象之间含有的关系，然后用数学的语言加以描述。为 了说明这个问题，我们首先举一个例，然后再给出明确的 含义。
1.2 数据结构概述
1.2.1 学习数据结构的必要性 瑞士著名计算机科学家N.Wirth提出了著名公式“程序 =算法+数据结构”，表明了数据结构在程序设计中的重 要地位。在计算机发展的初期，人们使用计算机的目的主 要是处理数值计算问题。由于当时所涉及的运算对象时简 单的整型、实型或布尔类型数据，所以程序设计者的主要 精力都集中在程序设计技巧上，而无需重视数据结构。随 着计算机应用领域的扩大以及软硬件的发展，非数值计算 问题越来越显得重要。这类问题涉及到的数据结构更为复 杂，数据元素之间的相互关系一般无法用数学方程式直接 描述。数学分析和计算方法在解决此类问题时显得力不从 心，而设计出合适的数据结构，才能有效地解决问题。

1.4.2 算法的设计要求
设计一个好的算法可以从以下几个方面考虑： （1）正确性。算法是为了针对解决具体问题而提出的，算法的正确与 否必须满足解决实际问题的需要，要经得起一切可能的输入数据的考验。 （2）可读性。算法要让人阅读得懂，程序要尽可能地简单通俗，当然 也必须有效。 （3）健壮性。当输入数据非法时，算法应能适当地作出反应或进行处 理。 （4）高效率。要求算法的执行时间要尽可能地短，对于存储空间要尽 可能地少，即做到既省时又节省空间。 要设计一个好的算法，必须对这几个方面综合考虑，才可以设计出 较好较优的算法。
– 定义结构体数组或链表以存储学生信息。
– 按照某种算法编写相关程序，实现对学生信 息进行查询、排序等处理操作。
《数据结构》研究什么？
例5 工厂的组织管理。某工厂的 组织机构如下所示。
a data parent 9 0 1 1 2 2 3
0号单元不用或 存结点个数
b
d e
c
f
0 1
0 a
2 g h i 3
……
运算n: } ADT LIST;
例题:线性表抽象数据类型的定义.P7
1.4 算法描述与算法评价
1.4.1 算法描述
算法是对特定问题求解方法和步骤的一种描述，它是指令的一组有限 序列。一个算法必须具备以下五个重要特性： （1）输入：一个算法必须具有零个或多个的外界输入。 （2）输出：一个算法必须有一个或多个的输出。 （3）有穷性：一个算法对任何合法的输入值必须总是在执行有穷步之
空间复杂度
衡量一个算法好坏的另一个因素是程序运行时所占用的存贮空间大小。 度量一个算法在运行或执行过程中所占用的存储空间的大小类似于时间复杂 度，可以用空间复杂度来度量。算法的空间复杂度一般也以相对于问题规模 的数量级的形式给出，如O(1)，O(n)等。

5．数据类型和抽象数据类型
数据类型（Data Type） 自20世纪70年代以来，几乎所有的高级程序设计语言都提供了这一 概念。在用高级语言编写的程序中间，程序中出现的每个变量，常量 或表达式，都必须事先说明它们所属的数据类型，每个类型都明显或 隐含的规定了在程序执行期间它的变量，它的表达式所允许取值的范 围，以及允许进行的操作，因此 所谓数据类型是一个值的集合以及在这些值上定义的一组操作的总称。 通常数据类型可以看作是程序设计语言中已实现的数据结构。 【例1．2】C语言的"整数类型"就定义了一个整数可取值的范围（其 最大值INT-MAX依赖于具体机器）以及对整数可施加的加、减、乘、 除和取模等操作。 按"值"是否可分解，可将数据类型划分为两类： ①原子类型：其值不可分解。通常是由语言直接提供。 【例】C语言的整型、字符型等标准类型及指针等简单的导出类型； ②结构类型：其值可分解为若干个成分（或称为分量）。是用户借助 于语言提供的描述机制自己定义的，它通常是由标准类型派生的，故 它也是一种导出类型。 【例】C的数组、结构等类型。
3．数据的四种基本存储方法
数据的存储结构可用以下四种基本存储方法得到： （1）顺序存储方法 该方法把逻辑上相邻的结点存储在物理位置上相邻 的存储单元里，结点间的逻辑关系由存储单元的邻接 关系来体现。 由此得到的存储表示称为顺序存储结构，通常借助 程序语言的数组描述。 该方法主要应用于线性的数据结构。非线性的数 据结构也可通过某种线性化的方法实现顺序存储。 （2）链接存储方法 该方法不要求逻辑上相邻的结点在物理位置上亦相 邻，结点间的逻辑关系由附加的指针字段表示。由此 得到的存储表示称为链式存储结构（Linked Storage Structure）,通常借助于程序语言的指针类型描述。