数据结构

一、数据结构及其概念

（一）、基本概念和术语

1.数据：是所有能被输入到计算机中，且能被计算机处理的符号(数字、字符等)的集合，它是计算机操作对象的总称。

2.数据元素：是数据(集合)中的一个"个体"，在计算机中通常作为一个整体进行考虑和处理，是数据结构中讨论的"基本单位"

（1）一类是不可分割的“原子”型数据元素，如：整数“5”，字符 “N” 等

（2）另一类是由多项构成的数据元素，其中每项被称为一个“数据项”。（数据项是数据结构中讨论的"最小单位"。）在由多个数据项构成的数据元素中必定存在关键字（能识别一个或多个数据元素的数据项。若能起唯一识别作用，则称之为 “主” 关键字，否则称之为 “次” 关键字）

例如：描述一个学生的信息的数据元素可由下列6个数据项组成。

3.数据对象：是具有相同特性的数据元素的集合，如：整数、实数等。它是数据的一个子集。在同一个数学模型中的数据元素必然具有相同特性。

4.数据结构：若在特性相同的数据元素集合中的数据元素之间存在一种或多种特定的关系，则称该数据元素的集合为“数据结构”。（“结构”即指数据元素之间存在的关系。数据结构是一堆数据元素和这些数据元素之间的关系的总和）

（二）、数据结构的形式定义

1.数据结构是一个二元组Data_Structures = ( D,S )（其中：D是数据元素的有限集，S是D上关系的有限集。）

2. 按关系或结构分，数据结构可归结为以下四类：

3.数据结构的两个方面：包括数据的“逻辑结构”和数据的“物理结构”两个方面。

（1）数据逻辑结构是对数据元素之间存在的逻辑关系的描述，它可以用一个数据元素的集合和定义在此集合上的若干关系表示。

（2）数据物理结构是数据逻辑结构在计算机中的表示和实现，故又称数据"存储结构"。

数据的逻辑结构和物理结构是密不可分的两个方面，一个算法的设计取决于所选定的逻辑结构，而算法的实现依赖于所采用的存储结构。

在C语言中，用一维数组表示顺序存储结构；用结构体类型表示链式存储结构。

4.存储结构：

（1）存储结构是逻辑结构在存储器中的映象，它包含数据元素的映象和关系的映象。

（2）有两种表示方法：以<x,y>的有序对为例,即x和y在逻辑上有先后关系

a.一为“顺序映象”。以 “y 相对于 x 的存储位置” 表示 “y是x的后继”，(即x和y在存储位置上是有先后关系的)由此得到的数据存储结构为“顺序存储结构”。(数据元素存放的地址是连续的)

b.二为“链式映象”。以和x绑定在一起的附加信息(指针)表示后继关系， (即x和y在存储位置上是没有先后关系的)这个指针即为 y 的存储地址，由此得到的数据存储结构为"链式存储结构"。(数据元素存放的地址是否连续没有要求)

5. 数据结构的三个组成部分：

逻辑结构： 数据元素之间逻辑关系的描述D_S=（D，S）

存储结构： 数据元素在计算机中的存储及其逻辑关系的表现称为数据的存储结构或物理结构。

数据操作： 对数据要进行的运算。

本课程中将要讨论的三种逻辑结构及其采用的存储结构.

（三）、数据类型

1. 数据类型(Data Type)：指的是一个值的集合和定义在该值集上的一组操作的总称。

2.数据类型是和数据结构密切相关的一个概念。 在C语言中数据类型有：基本类型和构造类型。

3.数据结构不同于数据类型，也不同于数据对象，它不仅要描述数据类型的数据对象，而且要描述数据对象各元素之间的相互关系

（四）、数据结构的运算

数据结构的主要运算包括：

二、抽象数据类型

1．抽象数据类型（Abstract Data Type 简称ADT）是指一个数学模型以及定义在此数学模型上的一组操作。

2. 抽象数据类型的形式描述为：

ADT = ( D，S，P )

其中：D 是数据对象，

S 是 D 上的关系集，

P 是 D 的基本操作集。

3.ADT 抽象数据类型名 {

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

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

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

} ADT 抽象数据类型名

4.常见的特殊约定

（1）

#define TRUE 1

#define FALSE 0

#define OK 1

#define ERROR 0

#define OVERFLOW -1

（2）赋值参数只为操作提供输入值；

（3）引用参数以&打头， 除可提供输入值外，还将返回操作结果。

（4）成组赋值 （变量名1，...，变量名n）=（表达式 1 ， ...，表达式n）；

（5）结构赋值 结构名1 = 结构名2；

结构名 =（值1，值2，...，值n）；

（6）条件赋值 变量名 = 条件表达式 ? 表达式1：表达式2；

（7）交换赋值 变量名1ßà变量名2；

三、算法初步分析

（一）、算法

1. 算法(Algorithm)：是对特定问题求解方法(步骤)的一种描述，是指令的有限序列，其中每一条指令表示一个或多个操作。

2. 算法必须满足五个重要特性

(1) 有穷性 对于任意一组合法的输入值，在执行有穷步骤之后一定能结束。即算法中的操作步骤为有限个，且每个步骤都能在有限时间内完成。

(2) 确定性 对于每种情况下所应执行的操作，在算法中都有确切的规定，使算法的执行者或阅读者都能明确其含义及如何执行。并且在任何条件下，算法都只有一条执行路径。表现在对算法中每一步的描述都没有二义性，只要输入相同，初始状态相同，则无论执行多少遍，所得结果都应该相同。

(3) 可行性 算法中的所有操作都必须足够基本，都可以通过已经实现的基本操作运算有限次实现之。指的是，序列中的每个操作都是可以简单完成的，其本身不存在算法问题。

(4) 有输入 ： 一个算法有零个或多个输入，这些输入取自于某个特定的对象集合。

(5) 有输出：一个算法有一个或多个输出，这些输出是同输入有着某些特定关系的量。

3.算法和程序：一个计算机程序是对一个算法使用某种程序设计语言的具体实现，不是所有的计算机程序都是算法。

（二）、算法的评判标准

评价一个好的算法有以下几个标准

① 正确性(Correctness )： 算法应满足具体问题的需求。

② 可读性(Readability)： 算法应容易供人阅读和交流。可读性好的算法有助于对算法的理解和修改。

③ 健壮性(Robustness)： 算法应具有容错处理。当输入非法或错误数据时，算法应能适当地作出反应或进行处理，而不会产生莫名其妙的输出结果。

④ 通用性(Generality)： 算法应具有一般性 ，即算法的处理结果对于一般的数据集合都成立。

⑤ 效率与存储量需求： 效率指的是算法执行的时间；存储量需求指算法执行过程中所需要的最大存储空间。一般地，这两者与问题的规模有关。

（三）、算法效率的度量

1.算法执行时间需通过依据该算法编制的程序在计算机上运行所消耗的时间来度量。其方法通常有两种：

事后统计：计算机内部进行执行时间和实际占用空间的统计

事前分析：求出该算法的一个时间界限函数。

2.与此相关的因素有：

 依据算法选用何种策略；

 问题的规模；

 程序设计的语言；

 编译程序所产生的机器代码的质量；

 机器执行指令的速度；

撇开软硬件等有关部门因素，可以认为一个特定算法“运行工作量”的大小，只依赖于问题的规模（通常用n表示），或者说，它是问题规模的函数。

3. 算法中基本操作重复执行的次数是问题规模n的某个函数，其时间量度记作 T(n)=O(f(n))，称作算法的渐近时间复杂度(Asymptotic Time complexity)，简称时间复杂度。

常用最深层循环内的语句中的原操作的执行频度(重复执行的次数)来表示。

“O”的定义： 若f(n)是正整数n的一个函数，则 O(f(n))表示 M≥0 ，使得当n ≥ n 0 时，|f(n)| ≤M|f(n 0 )|。

表示时间复杂度的阶有：

O(1) ：常量时间阶

O (n)：线性时间阶

O(㏒n) ：对数时间阶

O(n㏒n) ：线性对数时间阶 O (nk)： k≥2 ，k次方时间阶