数据结构--绪论（From：数据结构 C语言描述）

前言

“数据结构”是计算机程序设计的重要理论技术基础，是计算机学科的核心课程。“数据结构”是一门专业技术基础课。要求：学会分析研究计算机加工的数据结构的特性，以便为应用涉及的数据选择适当的逻辑结构、存储结构及其相应的算法，并初步掌握算法的时间分析和空间分析技术。

 

“数据结构”的学习过程也是复杂程序设计的训练过程，数据结构主要是培养数据抽象能力。

第1章 绪论

为了编写出一个“好”的应用程序，必须分析待处理的对象的特性以及各处理对象之间存在的关系。

1-1 什么是数据结构

具体问题 -> 数学模型 -> 算法（解此数学模型 -> 编写程序 -> 测试、调整 -> 最终解答

数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等的学科。

1-2基本概念和术语

数据：对客观事物的符号表示，在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。

数据元素：数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。有时，数据元素可由若干个数据项组成，数据项是数据的不可分割的最小单位。

例如：书的书目信息为一个数据元素，而书目信息中的每一项（如书名、作者名等）为一个数据项。

数据对象：性质相同的数据元素的集合，是数据的一个子集。

例如：整数数据对象是集合 N = {0, +/-1, +/-2…}

数据结构：相互之间存在一种或多种特定关系的数据元素的集合。数据元素之间存在着某种关系，这种数据元素相互之间的关系成为结构。通常有下列4类基本结构：

1）集合 结构中的数据元素之间除了“同属于一个集合”的关系外，别无其他关系。

2）线性结构 结构中数据元素之间存在一对一的关系

3）树形结构 结构中的数据元素之间存在一对多的关系

4）图状结构或网状结构 结构中的数据元素之间存在多对多关系

 

数据结构的形式定义为：数据结构是一个二元组

    Data_Structure = (D, S)

其中：D是数据元素的有限集，S是D上关系的有限集。

 

结构定义中的“关系”描述的是数据元素之间的逻辑关系，因此又称为逻辑关系。数据结构在计算机中的表示成为数据的物理结构，又称存储结构。在计算机中表示信息的最小单位是位，用一个由若干位组成起来的一个位串表示为一个数据元素，通常称这个位串为元素（Element）或节点（Node）。当数据元素由若干数据项组成时，位串中对应于各个数据项的子位串成为数据域（Data Field）。

 

数据元素之间的关系在计算机中有两种不同的表示方法：顺序映像和非顺序映像。并因此得到两种不同的存储结构：顺序存储结构和链式存储结构。任何一个算法的设计取决于选定的数据逻辑结构，而算法的实现依赖于采用的存储结构。

 

数据类型是一个值的集合和定义在这个值集合上的一组操作的总称。

抽象数据类型（ADT）是指一个数学模型以及定义在该模型上的一组操作。一个含ADT的软件模块通常应包含定义、表示和实现3部分。ADT的定义由一个值域和定义在值域上的一组操作完成。若按其值的不同特性，分为3种：

1）原子类型：原子类型的值是不可分解的。一般情况下，已有的固有数据类型足以满足需求。但有时也需要定义新的原子数据类型，例如：数位为100的整数。

2）固定聚合类型：属该类型的变量，其值由确定数目的成分按某种结构组成。

3）可变聚合类型：和固定聚合类型比较，构成可变聚合类型“值”的成分的数目不确定。

后两种成为结构类型，ADT可用以下三元组表示：

（D,S,P）

其中，D是数据对象，S是D上的关系集，P是对D的基本操作集。参考：

ADT 抽象数据类型名 {

    数据对象：<数据对象的定义>

    数据关系：<数据关系的定义>

    基本操作：<基本操作的定义>

} ADT 抽象数据类型名

基本操作名（参数表）

    初始条件：<初始条件描述>

    操作结构：<操作结果描述>

1-3 算法和算法分析

1-3-1算法

算法是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每一条指令表示一个或多个操作。一个算法有下列5个重要特性：

1)有穷性

2)确定性

3)可行性

4)输入

5)输出

1-3-2算法设计的要求

1)正确性

2)可读性

3)健壮性

4)效率与低存储量要求

1-3-3算法效率的度量

1)事后统计的方法：计时。缺点：一是必须先运行依据算法编写的程序，二是所得时间的统计量依赖于计算机的硬件、软件等环境因素。人们常常采用事前分析估算的方法。

2)事前分析估算的方法：

    1依据的算法选用何种策略；

    2问题的规模；

    3书写程序的语言，对于同一个算法，实现语言级别越高，执行效率越低；

    4编译程序锁产生的机器代码的质量；

    5机器执行指令的速度。

为了便于比较同一问题的不同算法，通常做法是，从算法中选取一种对于所研究的问题（算法类型）来说是基本操作的原操作，以该基本操作重复执行的次数作为算法的时间复杂度。

 

一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数f(n)，算法的时间量度记作：

T（n） = O(f(n))

它表示随问题规模n的增大，算法执行时间的增长率和f(n)的增长率相同，称作算法的渐进时间复杂度，简称时间复杂度。

O（1）、O(n)、O（n2）分别称为常量阶、线性阶、平方阶。算法还可能呈现的时间复杂度有对数阶O（logn）、指数阶O(2n)等。

时间复杂度均指最坏情况下的时间复杂度。