1.1 数据结构的研究内容

 

1.2 基本概念和术语

1.2.1 术语

• 数据（Data）
• 数据元素（Data Element）
• 数据项（Data Item）
• 数据对象（Data Object）

 

数据

定义：

• 是能输入计算机且能被计算机处理的各种符号的集合
• 信息的载体
• 是对客观事物符号化的表示
• 能够被计算机识别、存储和加工

 

包括：

• 数值型的数据：整数、实数等
• 非数值型的数据：文字、图像、图形、声音等

 

数据元素

• 是数据的基本单位，在计算机程序种通常作为一个整体进行考虑和处理
• 也简称为：元素、记录、结点、定点
• 一个数据元素可由若干个数据项组成（Data Item）

例如二维表中每一个元组（记录）

 

数据项

• 构成数据元素的不可分割的最小单位 （原子性）
• 可理解为二维表中的属性（字段）

 

数据、数据元素、数据项三者之间的关系：

数据 > 数据元素 > 数据项

例：学生表 > 个人记录 > 学号、姓名

 

数据对象

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

例如：

• 整数数据对象是集合N={0，±1，±2，±3，……}
• 字母字符数据对象是集合C={‘A’，’B’，……，’Z’}
• 学籍表也可看做一个数据对象

 

数据元素与数据对象的区别：

• 数据元素：组成数据的基本单位
• • 与数据的关系：是集合的个体
• 数据对象：性质相同的数据元素的集合
• • 与数据的关系：集合的子集

 

1.2.2 数据结构

• 数据结构不是独立存在的，它们之间存在某种关系，数据元素相互之间的关系称为结构（Structure）
• 是指相互之间存在一种或多种特定关系的数据元素的集合
• 或者说，数据结构是带结构的数据元素的集合

 

包括以下三个方面的内容：

1. 数据元素之间的逻辑关系，也成为逻辑结构
2. 数据元素及其关系在计算机内存中的表示（又称为映像），称为数据的物理结构或数据的存储结构
3. 数据的运算和实现，即对数据元素可以施加的操作以及这些操作在相应的存储结构上的实现

 

逻辑结构

• 描述数据元素之间的逻辑关系
• 与数据的存储无关，独立于计算机
• 是从具体问题抽象出来的数学模型

 

划分方法一

• 线性结构：有且仅有一个开始和一个终端结点，并且所有结点都最多只有一个直接前趋和一个直接后继
• • 例如：线性表、栈、队列、串
• 非线性结构：一个结点可能有多个直接前趋和直接后继
• • 例如：树、图

 

划分方法二

• 集合结构：结构中的数据元素之间除了同属于一个集合的关系外，无任何其它关系
• 线性结构：结构中的数据元素之间存在着一对一的线性关系
• 树形结构：结构中的数据元素之间存在着一对多的层次关系
• 图状结构或网状结构：结构中的数据元素之间存在着多对多的任意关系

 

物理结构

• 数据元素及其关系在计算机存储器中的结构（存储方式）
• 是逻辑结构在计算机中的表示

 

四种基本的存储结构：

• 顺序存储结构：用一组连续的存储单元依次存储数据元素，数据元素之间的逻辑关系由元素的存储位置来表示
  • C语言中用数组来实现顺序存储结构
• 链式存储结构：用一组任意的存储单元存储数据元素，数据元素之间的逻辑关系用指针来表示
  • C语言中用指针来实现链式存储结构
• 索引存储结构：在存储结点信息的同时，还建立附加的索引表
• 散列存储结构：根据结点的关键字直接计算出该结点的存储地址

 

逻辑结构与存储结构的关系：

• 存储结构是逻辑关系的映像与元素本身的映像
• 逻辑结构是数据结构的抽象，存储结构是数据结构的实现
• 两者综合起来建立了数据元素之间的结构关系

 

1.2.3 数据类型和抽象数据类型

数据类型

在使用高级程序设计语言编写程序时，必须对程序中出现的每个变量、常量或表达式，明确说明它们所属的数据类型

例如，C语言中：

• 提供int，char，float，double 等基本数据类型
• 数组、结构、共用体、枚举等构造数据类型
• 还有指针、空（void）类型
• 使用typedef自定义数据类型

一些最基本的数据结构可以用数据类型来实现，如数组、字符串等；而另一些常用的数据结构，如栈、队列、树、图等，不能直接用数据类型表示

 

数据类型的作用

• 约束变量或常量的取值范围
• 约束变量或常量的操作

 

定义：数据类型是一组性质相同的值的集合以及定义于这个值集合上的一组操作的总称

数据类型 = 值的集合 + 值集合上的一组操作

 

抽象数据类型

定义

Abstract Data Type：是指一个数学模型以及定义在此数学模型上的一组操作

• 由用户定义，从问题抽象出数据模型（逻辑结构）
• 还包括定义在数据模型上的一组抽象运算（相关操作）
• 不考虑计算机内的具体存储结构与运算的具体实现算法

 

形式定义

抽象数据类型可用（D，S，P）三元组表示

其中：D是数据类型

S是D上的关系集

P是对D的基本操作集

 

一个抽象数据类型的定义格式如下：

ADT 抽象数据类型名{
    数据对象: <数据对象的定义>
    数据关系: <数据关系的定义>
    基本操作: <基本操作的定义>
}ADT 抽象数据类型名

其中：

• 数据对象、数据关系的定义用伪代码描述
• 基本操作的定义格式为：
  • 基本操作名（参数表）
  • 初始条件：<初始条件描述>
  • 操作结果：<操作结果描述>

 

举例：Circle的定义

ADT Circle{
    数据对象: D={r，x，y|r，x，y均为实数}
    数据关系: R={<r，x，y>|r是半径，<x，y>是圆心坐标}
    基本操作: 
	Circle(&C, r, x, y)
        	操作结果：构造一个圆
	double Area(C)
        	初始条件：圆已存在
        	操作结果：计算面积
	double Circumference(C)
        	初始条件：圆已存在
        	操作结果：计算周长
    	......
}ADT Circle

 

1.3 抽象数据类型的表示与实现

概念小结

 

实现

即利用处理器中已存在的数据类型来说明新的结构，用已经实现的操作来组合新的操作

 

在本门课程中，我们使用类C语言（介于伪代码和C语言之间）作为描述工具，但是代码都是C语言版

 

1.4 算法和算法分析

算法的定义

对特定问题求解方法和步骤的一种描述，它是指令的有限序列。其中每个指令表示一个或多个操作。简而言之，算法就是解决问题的方法和步骤

 

算法的描述

• 自然语言：英语、中文
• 流程图：传统流程图、NS盒图
• 伪代码
• 程序设计语言

 

算法与程序

• 算法是解决问题的一种方法或一个过程，考虑如何将输入转换成输出，一个问题可以有多种算法
• 程序是用某种程序设计语言对算法的具体实现

 

程序 = 数据结构 + 算法

• 数据结构通过算法实现操作
• 算法根据数据结构设计程序

 

算法特性

• 有穷性：一个算法必须总在执行有穷步之后结束，且每一步都在有穷时间内完成
• 确定性：算法中的每一条指令必须有确切的含义，没有二义性，在任何条件下，只有唯一的一条执行路径，即对于相同的输入只能得到相同的输出
• 可行性：算法是CPU可执行的，算法描述的操作可以通过已经实现的基本操作执行有限次来实现
• 可以没有输入，但至少有一个输出

 

算法设计的要求

• 正确性：算法满足问题要求，能正确解决问题
• 可读性：应该易于人的理解
• 健壮性：输入非法数据时，算法做出恰当反应，而不是产生莫名奇妙的结果
• 高效性：要求尽量少的时间和尽量低的存储要求

 

算法分析

一个好的算法首先要具备正确性，然后是健壮性，可读性，在几个方面都满足的情况下，主要考虑算法的效率，通过算法的效率高低来评判不同算法的优劣程度。通常从这两方面：时间复杂度、空间复杂度

• 时间效率：指的是算法所耗费的时间
• 空间效率：指的是算法执行过程中所耗费的存储空间

时间效率和空间效率有时候是矛盾的

 

时间复杂度

算法时间效率可以用该算法编制的程序在计算机上执行所消耗的时间来度量

两种度量方法

• 事后统计：将算法实现，测算其时间和空间开销
  • 缺点：花费较多的时间和精力；所得实验结果依赖于计算机得软硬件等环境因素，掩盖算法本身的优劣
• 事前分析：对算法所消耗资源的一种估算方法

 

事前分析方法

一个算法的运行时间是指一个算法在计算机上运行所耗费的时间大致可以等于计算机执行一种简单的操作（如赋值、比较、移动等）所需的时间与算法中进行的简单操作次数乘积

算法运行时间 = 一个简单操作所需的时间 x 简单操作次数

也可记为： 算法运行时间 =

 

每一条语句执行依次所需的时间，一般是随机器而异的。所以我们可假设执行每条语句所需的时间均为单位时间

这样：算法运行时间 =

 

例如：两个 n x n矩阵相乘的算法可描述为

for(i=1; i<=n; i++){									// n+1 次
    for(j=1; j<=n; j++){								// n(n+1)次
        c[i][j] = 0;									// n*n次
        for(k=0; k<n; k++){								// n*n*(n+1)次
            c[i][j] = c[i][j] + a[i][k] * b[k][j];		// n*n*n次
        }
    }
}

则上述算法的时间消耗 T(n) = 2n^3 + 3n^2 +2n +1 时间复杂度为O(n^3)

 

为了便于比较不同算法的时间效率，我们仅比较它们的数量级

例如：两个不同的算法，时间消耗分别是：T1(n) = 10n^2 T2(n) = 5n^3

只看最高次幂的那一项并可以把系数去掉，所以T1好，T1的时间复杂度为 O(n^3)

 

定义：算法中基本语句重复执行的次数是问题规模n的某个函数f(n)，算法的时间量度记作： T(n) = O(f(n))

基本语句：

• 算法中重复执行次数和算法的执行时间成正比的语句
• 对算法运行时间的贡献最大
• 执行次数最多

 

n越大算法的执行时间越长

• 排序：n为记录数
• 矩阵：n为矩阵的阶数、
• 多项式：n为多项式的项数
• 集合：n为元素个数
• 树：n为树的结点个数
• 图：n为图的顶点数或边数

 

举例：

i = 1;
while(i <= n)
    i = i * 2;

设语句 i = i * 2; 执行次数为 x 次，由循环条件 i <= n 所以 2^x <= n

则 x <= log(2, n) 所以时间复杂度为 O(log(2, n))，称这种为：对数级 可直接称为 log n，忽略底数

 

注意：有的情况下，算法中基本操作重复执行的次数还随问题的输入数据集不同而不同

// 顺序查找，在数组a[i]中查找等于 e 的元素，返回其所在位置
for(i=0;i<n;i++){
    if(a[i]==e)
        return i+1;
}

return 0;

最好情况：1次 最坏情况：n次 平均时间复杂度：O(n)

一般总是考虑在最坏时间复杂度

 

时间复杂度T(n)按数量级递增顺序为：

 

空间复杂度

算法所需存储空间的度量，记为：S(n)=O(f(n))，其中n为问题的规模（或大小）

算法要占据的空间：

• 算法本身要占据的空间：输入/输出，指令、常数、变量等
• 算法要使用的辅助空间

 

例：将一维数组a中的n个数逆序存放到原数组中

算法1：S(n) = O(1) 原地工作

算法2：S(n) = O(n)

 

1.5 总结

• 抽象数据类型 = 数据的逻辑结构 + 抽象运算（运算的功能描述）
• 数据的逻辑结构可以采取不同的存储结构
• 基于不同的存储结构可以有不同的算法，比如基于顺序存储结构的算法A、基于链式存储结构的算法B
• 对不同的算法进行算法分析，比对时间复杂度和空间复杂度，选择较优的算法