数据结构(C语言版)第1章

1、2第1章 绪 论学习目标与要求：了解数据、数据元素、数据项、数据对象、数据类型及抽象数据类型等基本概念。掌握数据结构和算法的概念。掌握数据结构的逻辑结构、存储结构和数据操作(运算)3个方面的概念及其相互之间的关系。掌握算法的评价标准。分析算法的时间复杂度，评价一个算法的好坏。31.1 引 言1968年美国唐年美国唐欧欧克努特克努特(Donald E.Knuth)开开创了数据结构的最初体系。创了数据结构的最初体系。 数据结构是一门介于数学、计算机硬件和计算数据结构是一门介于数学、计算机硬件和计算机软件三者之间的核心课程机软件三者之间的核心课程(如图如图1.1所示所示)。 数学 代数系统 编译理论

2、 存储装置 硬件(计算机系统设计) 算子关系 数据 类型 数据表示法 数据的操作 数据结构 数据存取 机器组织 文件系统 数据组织 信息检索 软件(计算机程序设计) 41.1 引 言为了使读者对数据结构有一个感性的认识，为了使读者对数据结构有一个感性的认识，下面给出几个数据结构的示例，读者可以下面给出几个数据结构的示例，读者可以通过这些示例去理解数据结构的概念。通过这些示例去理解数据结构的概念。【示例1】 职工基本情况表。参见教材P2【示例2】 井字棋对弈问题。【示例3】 教学计划编排问题。51.2 基本概念与术语数据数据(Data)是对客观事物的一种符号表示，是指所有能输入到是对客观事物的一

3、种符号表示，是指所有能输入到计算机中并被计算机程序加工处理的符号的总称。计算机中并被计算机程序加工处理的符号的总称。 数据元素数据元素(Data Element)是组成数据的基本单位，在计算机程是组成数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。序中通常作为一个整体进行考虑和处理。 数据项数据项(Data Item)是数据不可分割的、具有独立意义的最小数是数据不可分割的、具有独立意义的最小数据单位，是对数据元素属性的描述。据单位，是对数据元素属性的描述。 数据、数据元素、数据项反映了数据组织的数据、数据元素、数据项反映了数据组织的3个层次，即数据个层次，即数据可以由若干个数据元

4、素组成，数据元素又由若干个数据项组成。可以由若干个数据元素组成，数据元素又由若干个数据项组成。数据对象数据对象(Data Object)是性质相同的数据元素的集合。是性质相同的数据元素的集合。 数据类型数据类型(Data Type)是指一组结构相同的值构成的值集是指一组结构相同的值构成的值集(类型类型)和定义在这个值集和定义在这个值集(类型类型)上的操作集。上的操作集。 数据结构数据结构(Data Structure)是指数据元素之间的逻辑关系和这是指数据元素之间的逻辑关系和这种关系在计算机中的存储表示，以及在这种结构上定义的运算。种关系在计算机中的存储表示，以及在这种结构上定义的运算。 61

5、.2 基本概念与术语1. 逻辑结构 (1)线性结构。 (2)集合结构。 (3)树形结构。 (4)图状结构。数据的四种基本逻辑结构如图1.4所示。 71.2 基本概念与术语2. 存储结构(1) 顺序存储结构是指把逻辑上相邻的结点存储在物理上相邻的存储单元里，结点之间的逻辑关系由存储单元位置的邻接关系来体现。 (2) 链式存储结构是把逻辑上相邻的结点存储在物理上任意的存储单元里，结点之间的逻辑关系由附加的指针域来体现。 (3) 索引存储结构是用结点的索引号来确定结点的存储地址。 81.2 基本概念与术语3. 数据的运算对几种常用的运算进行简要介绍。(1)检索：即在数据结构里查找满足一定条件的结点，

6、一般是给定某字段的值，找具有该字段值的结点。(2)插入：即往数据结构里增加新的结点。(3)删除：把指定的结点从数据结构里去掉。(4)更新：改变指定结点的一个或多个字段的值。91.3 抽象数据类型首先我们了解一下在程序设首先我们了解一下在程序设计语言中出现的各种数据类计语言中出现的各种数据类型。型。101.3.1 数据类型数据类型是一个值的集合和定义在这个值集上数据类型是一个值的集合和定义在这个值集上的一组操作的总称。的一组操作的总称。在高级程序设计语言中，数据类型可分为两类：在高级程序设计语言中，数据类型可分为两类：一类是原子类型，另一类则是结构类型。一类是原子类型，另一类则是结构类型。 在某

7、种意义上，数据结构可以看成是在某种意义上，数据结构可以看成是“一组具一组具有相同结构的值有相同结构的值”，而数据类型则可被看成是，而数据类型则可被看成是由一种数据结构和定义在其上的一组操作所组由一种数据结构和定义在其上的一组操作所组成的。成的。111.3.2 抽象数据类型概述抽象数据类型抽象数据类型(Abstract Data Type，ADT)，是指一个数学模型以及定义在此数学模型上的是指一个数学模型以及定义在此数学模型上的一组操作。一组操作。 抽象数据类型是与表示无关的数据类型，是一抽象数据类型是与表示无关的数据类型，是一个数据模型及定义在该模型上的一组运算。个数据模型及定义在该模型上的一

8、组运算。 抽象数据类型的描述包括给出抽象数据类型的抽象数据类型的描述包括给出抽象数据类型的名称、数据的集合、数据之间的关系和操作的名称、数据的集合、数据之间的关系和操作的集合等方面的描述。集合等方面的描述。 121.3.2 抽象数据类型概述抽象数据类型的形式化定义如下：抽象数据类型的形式化定义如下：ADT=(D,S,P)D=数据对象S=D上的关系集P=对D的基本操作集定义形式：定义形式：ADT 抽象数据类型名称 数据对象： 数据关系： 基本操作： 操作名1： 操作名n：ADT抽象数据类型名称 131.4 算法和算法分析在计算机领域，一个算法实质上是针对所处理问题的在计算机领域，一个算法实质上是

9、针对所处理问题的需要，在数据的逻辑结构和存储结构的基础上实施的需要，在数据的逻辑结构和存储结构的基础上实施的一种运算。一种运算。由于数据的逻辑结构和存储结构不是唯一的，所以处由于数据的逻辑结构和存储结构不是唯一的，所以处理同一个问题的算法也不是唯一的；即使对于具有相理同一个问题的算法也不是唯一的；即使对于具有相同逻辑结构和存储结构的问题而言，由于设计思想和同逻辑结构和存储结构的问题而言，由于设计思想和设计技巧不同，编写出来的算法也不大相同。设计技巧不同，编写出来的算法也不大相同。学习数据结构这门课程的目的，就是要学会根据实际学习数据结构这门课程的目的，就是要学会根据实际问题的需要，为数据选择合

10、适的逻辑结构和存储结构，问题的需要，为数据选择合适的逻辑结构和存储结构，进而设计出合理和实用的算法。进而设计出合理和实用的算法。141.4.1 算法的基本概念1. 算法2. 算法的特征(1)有穷性。 (2)确定性。 (3)可行性。 (4)有输入。 (5)有输出。 3. 算法与程序的区别(1)一个算法必须在有穷步之后结束，一个程序不一定满足有穷性。 (2)程序中的指令必须是机器可执行的，而算法中的指令则无此限制。(3)算法代表了对问题的求解过程，而程序则是算法在计算机上的实现。(4)算法和数据结构是相辅相成的。151.4.1 算法的基本概念4. 算法的设计目标(1) 正确性。 (2) 可读性。

11、(3) 健壮性。 (4) 高效率。 (5) 低存储量需求。 161.4.1 算法的基本概念5. 算法的描述(1) 自然语言 (2) 流程图 (3) 高级程序设计语言 (4) 类语言 定义变量 x 结束 输入 x x0 d=x%10; 输出 d; x=x/10; 否 是 171.4.2 算法的时间复杂度一个程序的时间复杂度一个程序的时间复杂度(Time Complexity)是指程序是指程序运行从开始到结束所需要的时间。运行从开始到结束所需要的时间。一个算法是由控制结构和原操作构成的，其执行时间一个算法是由控制结构和原操作构成的，其执行时间取决于两者的综合效果。取决于两者的综合效果。 定义定义(

12、大大O记号记号)：如果存在两个正常数：如果存在两个正常数c和和n0，使得对，使得对所有的所有的n, nn0，有：，有：f(n) cg(n)则有：则有：f(n) (g(n)使用大使用大O记号表示的算法的时间复杂度，称为算法的记号表示的算法的时间复杂度，称为算法的渐近时间复杂度渐近时间复杂度(Asymptotic Complexity)。181.4.3 算法的空间复杂度算法的空间复杂度算法的空间复杂度(Space Complexity)是指算是指算法从开始运行到运行结束所需的存储空间，即法从开始运行到运行结束所需的存储空间，即算法执行过程中所需的最大存储空间。算法执行过程中所需的最大存储空间。类似

13、于算法的时间复杂度，算法的空间复杂度类似于算法的时间复杂度，算法的空间复杂度通常也是采用一个数量级来度量。记作：通常也是采用一个数量级来度量。记作：S(n)=O(g(n)，称，称S(n)为算法的渐近空间复杂为算法的渐近空间复杂度。度。算法运行所需的存储空间包括以下两部分：算法运行所需的存储空间包括以下两部分：(1)固定部分。 (2)可变部分。 19本 章 小 结(1) 数据结构研究的三方面内容是数据的逻辑结构、数据结构研究的三方面内容是数据的逻辑结构、数据的存储结构和对数据的运算。数据的逻辑结构可数据的存储结构和对数据的运算。数据的逻辑结构可分为集合、线性、树和图四种基本结构。数据的存储分为集合、线性、树和图四种基本结构。数据的存储结构有顺序、链式、索引和散列四种存储结构。结构有顺序、链式、索引和散列四种存储结构。(2) 算法是对特定问题求解步骤的一种描述，是指令算法是对特定问题求解步骤的一种描述，是指令的有限序列。算法具有有穷性、确定性、可行性、输的有限序列。算法具有有穷性、确定性、可行性、输入、输出特性。入、输出特性。(3) 一个好的算法应该达到正确性、可读性、健壮性、一个好的算法应该达到正确性、可读性、健