跳到主要内容

第一章 绪论

1.1 数据结构的研究内容​

研究内容

  • 逻辑结构
  • 存储结构
  • 算法

例：​

学号姓名性别籍贯专业
240001张三男安徽计算机科学与技术
240002李四男北京计算机科学与技术
240003王五女上海软件工程
240004赵六女重庆通信技术

  • 操作对象：即若干行的数据记录(此表对应每位学生的信息(学号、姓名、性别、籍贯、专业))

  • 操作算法：插入、删除、修改、查询

  • 操作对象之间的关系：线性关系

  • 数据结构：线性数据结构、线性表

内容小结​

  • 描述非数值计算问题的数学模型不是数学方程，而是诸 如表、树和图之类的具有逻辑关系的数据
  • 数据结构是一门研究非数值计算的程序设计钟计算机的操作对象以及它们之间的关系和操作的学科

1.2 基本概念和术语​

数据​

  • 是能输入计算机且能被计算机处理的各种符号的集合
    • 信息的载体
    • 是对客观事物符号化的表示
    • 能够被计算机识别、存储和加工
  • 包括
    • 数值型数据：整数、实数等
    • 非数值型数据：文字、图像、图形、声音等

数据元素​

  • 是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理
  • 也简称为元素，或记录、结点或顶点
  • 例线性表内的某一行

数据项​

  • 构成数据元素的不可分割的最小单位

数据对象​

  • 是性质相同的数据元素的集合，是数据的一个子集
  • 例：整数数据对象是集合N={0, ±1, ±2, ...}、学籍表也可看作一个数据对象

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

  • 数据 > 数据元素 > 数据项
  • 例：学生表 > 个人纪录 > 学号、姓名...

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

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

1.2.2 数据结构​

数据结构​

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

数据结构包含以下三个方面的内容​

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

数据结构的两个层次​

  • 逻辑结构
    • 描述数据元素之间的逻辑关系
    • 与数据的存储无关，独立于计算机
    • 是从具体问题抽象出来的数学模型
  • 物理结构(存储结构)
    • 数据元素及其关系在计算机存储器中的结构(存储方式)
    • 是数据结构在计算机中的表示
  • 逻辑结构与存储结构的关系
    • 存储结构是逻辑关系的映象与元素本身的映象
    • 逻辑结构是数据结构的抽象，存储结构是数据结构的实现
    • 两者综合起来建立了数据元素之间的结构关系

逻辑结构的种类​

划分方法一：

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

划分方法二：

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

存储结构的种类​

四种基本的存储结构：

  • 顺序存储结构
    • 用一组连续的存储单元依次存储数据元素，数据元素之间的逻辑关系由元素的存储位置来表示
    • C语言中用数组来实现顺序存储结构
  • 链式存储结构
    • 用一组任意的存储单元存储数据元素，数据元素之间的逻辑关系用指针来表示
    • C语言中用指针来实现链式存储结构
  • 索引存储结构
    • 在存储结点信息的同时，还建立附加的索引表
    • 索引表中的每一项称为一个索引项
    • 索引项的一般形式是：(关键字，地址)
    • 关键字是能唯一标识一个结点的那些数据项
    • 若每个结点在索引表中都有一个索引项，则该索引表称之为稠密索引。若一组结点在索引表中只对应一个索引项，则该索引表称之为稀疏索引
  • 散列存储结构
    • 根据结点的关键字直接计算出该结点的存储地址

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

数据类型​

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

抽象数据类型​

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

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

抽象数据类型的形式定义​

抽象数据类型可用(D, S, P)三元组表示

  • D 是数据对象
  • S 是D上的关系集
  • P 是对D的基本操作集

抽象数据类型的定义格式​

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

其中数据对象、数据关系的定义用伪代码描述

  • 基本操作名(参数表)
    • 基本操作定义格式
      • 参数表：赋值参数，只为操作提供输入值。引用数据以&打头，除可提供输入值外，还将返回操作结果
      • 初始条件：描述操作执行之前数据结构和参数应满足的条件，若不满足，则操作失败，并返回相应出错信息。若初始条件为空，则省略
      • 操作结果：说明操作正常完成之后，数据结构的变化状态和应返回的结果
  • 初始条件:<初始条件描述>
  • 操作结果:<操作结果描述>

抽象数据类型(ADT)定义​

ADT 抽象数据类型名 {
	Data
		数据对象的定义
		数据元素之间逻辑关系的定义
	Operation
		操作1
			初始条件
			操作结果描述
        操作2
        	……
        操作n
        ……
} 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

抽象数据类型(ADT)定义举例：复数的定义​

ADT Complex {
	数据对象：D={r1,r2 | r1,r2均为实数}
	数据关系：R={<r1,r2> | r1是实部，r2是虚部}
	基本操作：
	assign(&C, v1, v2)
		初始条件：空的复数C已存在
		操作结果：构造复数C，r1，r2分别被赋以参数v1，v2的值
    destroy(&C)
    	初始条件：复数C已存在
    	操作结果：复数C被销毁
    getReal(Z, &realPart)
	    初始条件：复数已存在
	    操作结果：用realPart返回复数Z的实部值
    getImag(Z, &ImagPart)
	    初始条件：复数已存在
	    操作结果：用ImagPart返回复数Z的虚部值
    add(z1, z2, &sum)
    	初始条件：z1，z2是复数
    	操作结果：sum返回两个复数z1，z2的和
} ADT Complex

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

概念小结

用C语言真正实现抽象数据类型的定义(以复数为例)​

typedef struct {
    float realPart; //实部
    float imagPart; //虚部
} Complex //定义复数抽象类型
    
void assign (Complex *A, float real, float imag); //赋值
void add (Complex *A, float real, float imag); //A + B
void minus (Complex *A, float real, float imag); //A - B
void multiply (Complex *A, float real, float imag); //A * B
void divide (Complex *A, float real, float imag); //A / B

viod assign (Complex *A, float real, float imag) {
    A -> realPart = real; //实部赋值
    A -> imagPart = imag; //虚部赋值
}

void add (Complex *c, Complex A, Complex B) //c = A+B
    c -> realPart = A.realPart +B.realPart; //实部相加
    c -> imagPart= A.imagPar+B.imagPart; //虚部相加
}

抽象数据举例​

复数公式

complex z1, z2, z3, z4, z;
float RealPart, ImagPart;
assign (z1, 8.0, 6.0); //构造复数z1
assign (z2, 4.0, 3.0); //构造复数z2
add (z1, z2, z3); //两个复数相加
multiply (z1, z2, z4); //两个复数相乘
if (divide (z4, z3, z)) //两个复数相除
GetReal (z, RealPart);
GetImag (z, ImagPart);
} //if

1.4 算法和算法分析​

算法的定义​

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

算法的描述​

  • 自然语言：英语、中文
  • 流程图：传统流程图、NS流程图
  • 伪代码、类语言：类C语言
  • 程序代码：C语言程序、Java语言程序

算法与程序​

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

算法特性：一个算法必须具备以下五个重要特性​

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

算法设计的要求​

  • 正确性
  • 可读性
  • 健壮性
  • 高效性

算法效率​

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

算法时间效率的度量​

  • 算法时间效率可以依据该算法编制的程序在计算机上执行所消耗的时间来度量
  • 两种度量方法
    • 事后统计
      • 将算法实现，测算其时间和空间开销
      • 缺点：编写程序实现算法将花费较多的时间和精力，所得实验结果依赖于计算机的软硬件等环境因素，掩盖算法本身的优势
    • 事前分析
      • 对算法所消耗资源的一种估算方式

事前分析方法​

  • 一个算法的运行时间是指一个算法在计算机上运行所消耗的时间大致可以等于计算机执行一种简单的操作(如赋值、比较、移动等)所需的时间与算法中进行的简单操作次数乘积
  • 算法运行时间=一个简单操作所需时间×简单操作次数
  • 也即算法中每条语句的执行时间之和：算法运行时间=∑每条语句的执行次数(语句频度)×该语句执行一次所需的时间

例：两个n×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)为：T(n)=2n³+3n²+2n+1

算法时间复杂度的渐进表示法​

  • 为了便于比较不同算法的时间效率，我们仅比较它们的数量级
    • 例：两个不同算法，时间消耗分别为：T1(n)=10n²(更好) 与 T2(n)=5n³
  • 若有某个辅助函数f(n)，使得当n趋近于无穷大时，T(n)/f(n)的极限值为不等于零的常数，则称f(n)是T(n)的同数量级函数。记作T(n)=O(f(n))，称O(f(n))为算法的渐进时间复杂度(O是数量级的符号)，简称时间复杂度。
  • 对于求解矩阵相乘问题，算法耗费时间：T(n)=2n³+3n²+2n+1
    • n→∞时，T(n)/n³→2，这表示n充分大时，T(n)与n³是同阶或同数量级，引入大O记号，则T(n)可记作T(n)=O(n³)
  • 一般情况下，不必计算所有操作的执行次数，而只考虑算法中基本操作执行的次数，它是问题规模n的某个函数，用T(n)表示。

时间复杂度定义​

  • 算法中基本语句重复执行的次数是问题规模n的某个函数f(n)，算法的时间量度记作：T(n)=O(f(n))
  • 它表示随着n的增大，算法执行的时间的增长率和f(n)的增长率相同，称渐近时间复杂度
  • 以下n越大，算法执行时间越长
    • 排序：n为记录数
    • 矩阵：n为矩阵的阶数
    • 多项式：n为多项式的项数
    • 集合：n为元素个数
    • 树：n为树的结点个数
    • 图：n为图的顶点数或边数

分析算法时间复杂度的基本方法​

  • 找出语句频度最大的那条语句作为基本语句
  • 计算基本语句的频度得到问题规模n的某个函数f(n)
  • 取其数量级用符号“0”表示

[!TIP]

该篇未完结，后续内容待完善……