[数据结构与算法]数据结构与算法 | 数据结构与算法概述

数据结构的基本概念

• 数据、数据元素、数据项、数据对象

  • 数据：要处理的所有信息的集合（所有学生的信息）
  • 数据元素：依实际问题而定的处理的基本单位（单个学生的所有相关信息）
  • 数据项：依实际问题而定的处理的最小单位（单个学生的姓名、性别等单个字段的信息）
  • 数据对象：依实际问题而定的数据元素的集合（1班学生的所有信息）

  官方定义：

  • 数据

    • 是能输入计算机并被计算机处理的各种符号的集合
    • 数据是信息的载体，是客观事物的符号化表示，能够被计算机识别、存储和加工
    • 包括是数值型数据和非数值型数据（区分依据是能否进行数值运算）

  • 数据元素

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

  • 数据项

    • 构成数据元素的不可分割的最小单位
    • 数据、数据元素、数据项三者之间的关系：数据 > 数据元素 > 数据项

  • 数据对象

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

  • 数据元素与数据对象

    • 数据元素——组成数据的基本单位

      与数据的关系：是集合的个体

    • 数据对象——性质相同的数据元素的集合

      与教据的关系是：集合的子集

• 数据结构：数据 + 结构（结构即数据元素之间的关系）

  • 这里的关系包括逻辑结构和物理结构
  • 逻辑结构即数据元素之间逻辑上的关系
  • 物理结构即在存储器中的存储的数据元素之间物理位置上的关系

  官方定义：

  • 数据结构

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

  • 数据结构包括以下三个方面的内容

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

  • 逻辑结构

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

  • 物理结构（存储结构）

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

    • 是数据结构在许算机中的表示

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

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

• 逻辑结构的种类

  数据元素是结构的基本组成单元，在结构中抽象成一个结点

  前驱即父结点，后继即子结点

  • 划分方法一

    • 线性结构：结点像串珠子一样串在一起

      有且仅有一个开始和一个终端结点，并且所有结点都最多只有一个直接前趋和一个直接后继

      例如：线性表、栈、队列、串

    • 非线性结构：不是线性结构的就是非线性结构

      一个结点可能有多个直援前趋和直接后继

      例如：树、图

  • 划分方法二

    • 集合：一堆结点，毫无逻辑连线
    • 线性：结点像串珠子一样串在一起
    • 树形：结点像树状图一样分布
    • 图状/网状：结点像网一样分布

    集合结构：结构中的数据元素之间除了同属于一个集合的关系外，无任何其它关系。

    线性结构：结构中的数据元素之间存在着一对一的线性关系。

    树形结构：结构中的数据元素之间存在着一对多的层次关系。

    图状结构或网状结构：结构中的数据元素之间存在着多对多的任意关系。

• 物理结构的种类

  • 顺序存储结构：一个结点紧挨着一个结点存储

    用一组连续的存储单元依次存储数据元素，数据元素之间的逻辑关系由元素的存储位置来表示
    C语言中用数组来实现顺序存储结构

  • 链式存储结构：每个结点都指向下一个结点

    用一组任意的存储单元存储数据元素，数据元素之间的逻辑关系用指针来表示。
    C语言中用指针来实现链式存储结构

  • 索引存储结构：建立索引表

  • 散列存储结构：根据关键字计算存储地址

• 数据结构与算法的研究内容 = 数据结构 + 算法 = 逻辑结构 + 物理结构 + 运算

数据类型和抽象数据类型

• 数据类型：数据类型包含了数据的取值范围以及数据能够进行的操作，有“类”的意味在里面

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

• 抽象数据类型：抽象数据类型就是基本数据类型之外的，由程序员自己定义的数据类型

  由用户定义，从问题抽象出数据模型（逻辑结构）

  还包括定义在数据模型上的一组抽象运算（相关操作）

  不考虑计算机内的具体存储结构与运算的具体实现算法

  • 抽象数据类型的形式定义：可以用(D, S, P)三元组表示

    D(数据对象)、S(D上的关系集)、P(对D的基本操作集)

    ADT 抽象数据类型名{
    	数据对象的定义;
    	数据关系的定义;
    	基本操作的定义（操作名 + 参数表、初始条件、操作结果）;
    }ADT 抽象数据类型名
    

    • 参数表

      • 赋值参数：传值，只为操作提供输入值
      • 引用参数：传址，除提供输入值之外，还将接收返回结果

    • 初始条件：描述操作执行之前数据结构和参数应满足的条件，若不满足，则操作失败，并返回相应出错信息。若初始条件为空，则省略之。

    • 操作结果：说明操作正常完成之后，数据结构的变化状况和应返回的结果。

    圆的例子

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

    复数的例子

    • C语言实现

    #include<stdio.h>
    // 定义复数类型
    typedef struct{
    	float realpart;	// 实部
    	float imagpart;	// 虚部
    }Complex;
    
    // 赋值
    void assign(Complex* C, float realpart, float imagpart) {
    	C->realpart = realpart;
    	C->imagpart = imagpart;
    }
    
    // 加
    void add(Complex* C, Complex C1, Complex C2) {
    	C->realpart = C1.realpart + C2.realpart;
    	C->imagpart = C1.imagpart + C2.imagpart;
    }
    
    // 减
    void minus(Complex* C, Complex C1, Complex C2) {
    	C->realpart = C1.realpart - C2.realpart;
    	C->imagpart = C1.imagpart - C2.imagpart;
    }
    
    // 乘
    void multiply(Complex* C, Complex C1, Complex C2) {
    	...
    }
    
    // 除
    void divide(Complex* C, Complex C1, Complex C2) {
    	...
    }
    

    #include<stdio.h>
    #include"Complex.h"
    /**
     * 试计算z = (8+6i)(4+3i)/((8+6i)+(4+3i))
    */
    int main() {
    	Complex C1, C2, C3, C4;
    	assign(&C1, 8, 6);
    	assign(&C2, 4, 3);
    	multiply(&C3, C1, C2);
    	add(&C4, C1, C2);
    	divide(&C1, C3, C4)
    	printf("%f + %fi",C1.realpart, C1.imagpart);
    	return 0;
    }
    

    • Java实现

    public class Complex {
    	float realpart;
    	float imagpart;
    		
    	public Complex() {
    		this(0, 0);
    	}
    
    	public Complex(float realpart, float imagpart) {
    		this.realpart = realpart;
    		this.imagpart = imagpart;
    	}
    	
    	public static Complex add(Complex C1, Complex C2) {
    		Complex C = new Complex();
    		C.realpart = C1.realpart + C2.realpart;
    		C.imagpart = C1.imagpart + C2.imagpart;
    		return C;
    	}
    
    	public static Complex minus(Complex C1, Complex C2) {
    		Complex C = new Complex();
    		C.realpart = C1.realpart - C2.realpart;
    		C.imagpart = C1.imagpart - C2.imagpart;
    		return C;
    	}
    	
    	public static Complex multiply(Complex C1, Complex C2) {
    		...
    	}
    
    	public static Complex divide(Complex C1, Complex C2) {
    		...
    	}
    }
    

    /**
    * 试计算z = (8+6i)(4+3i)/((8+6i)+(4+3i))
    */
    
    public ComplexTest {
    
    	public static void main(String[] args) {
    		Complex C1 = new Complex(8, 6);
    		Complex C2 = new Complex(4, 3);
    		Complex C3 = new Complex();
    		Complex C4 = new Complex();
    		C3 = multiply(C1, C2);
    		C4 = add(C1, C2);
    		C1 = divide(C3, C4);
    		System.out.println(C1);
    }
    

算法的基本概念

• 算法：为求解某个问题，对数据元素的一顿操作、运算

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

• 算法的描述：自然语言、流程图、伪代码、程序代码

• 算法与程序

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

• 算法的五个特性

  • 有穷性：算法一定有结束的时候，不能无限循环

    一个算法必须总是在执行有穷步之后结束，且每一步都在有穷时间内完成。

  • 确定性：不能含糊，不能歧义

    算法中的每一条指令必须有确切的含义，没有二义性，在任何条件下，只有唯一的一条执行路径，即对于相同的输入只能得到相同的输出。

  • 可行性

    算法是可执行的，算法描述的操作可以通过已经实现的基本操作执行有限次来实现。

  • 输入：一个算法有零个或多个输入

  • 输出：一个算法有一个或多个输出

• 算法设计的要求

  • 正确性：没有语法错误；合法输入能够得到合意输出（特别是刁难性的合法输入）
  • 可读性：不要晦涩难懂
  • 健壮性：面对非法输入能够做出相应处理，而不是抛出异常或者返回奇怪的结果
  • 高效性：尽量少的时间，尽量小的存储需求

时间复杂度与空间复杂度

• 时间复杂度与空间复杂度是用来干什么的？

  是算法高效性的衡量指标，即评价同一问题的不同算法孰优孰劣的指标（当然前提是这些算法已经满足正确性、健壮性和可读性）

• 时间复杂度指的是算法的时间效率，空间复杂度指的是算法的空间效率

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

• 衡量时间效率

  • 事后统计：将算法实现，统计运行时间

    缺点：编写程序实现算法将花费较多的时间和精力；所得实验结果依赖于计算机的软硬件等环境因素，掩盖算法本身的优劣

  • 事前分析：

    算法运行时间 = 基操时间 × 基操次数（语句频度）

    基操时间由运行环境决定，与算法无关，所以可以把时间效率直接定为语句频度

    例子：

    for(i = 1; i <= n; i++) {	// 执行n+1次（循环n次，出循环判断1次）
    	for(j = 1; j <= n; j++) {	// 执行n(n+1)次（循环n次，出循环判断1次，同时在n次循环体中）
    		c[i][j] = 0;	// 执行n*n次（循环n次，同时在n次循环体中）
    		for(k = 0; k < n; k++) { // 执行n*n*(n+1)次（循环n次，出循环判断1次，同时在n*n次循环体中）
    			c[i][j] = c[i][j] + a[i][k]*b[k][j]; //执行n*n*n次（循环n次，同时在n*n次循环体中）
    		}
    	}
    }
    

    把所有语句频度加在一起，得到总的语句频度：
    $$T(n)=2n^3+3n^2+2n+1$$
    为方便比较，我们只比较其数量级（抓大），得到算法的渐进时间复杂度，简称为时间复杂度
    $$T(n)=O(f(n))，其中\underset{n\to \infty }{\lim }\frac{T(n)}{f(n)}=C，C是常数$$
    所以以上程序的时间复杂度为O(n³)

• 时间复杂度的定义：

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

  问题规模n越大算法的执行时间越长，不同问题中n表示的含义也不同

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

• 分析时间复杂度的方法

  • 找出执行次数最多的基本语句（嵌套最多循环体的）
  • 计算该基本语句的执行次数（忽略常数，取数量级，可以看成级数求和来算）

• 算法时间复杂度与输入集有关时

  • 最坏时间复杂度：指在最坏情况下，算法的时间复杂度。

  • 平均时间复杂度：指在所有可能输入实例在等概率出现的情况下，算法的期望时间复杂度

  • 最好时间复杂度：指在最好情况下，算法的时间复杂度。

    一般只考虑最坏和平均，平均难算时考虑最坏

• 时间复杂度的比较

  常数阶O(1) < 对数阶O(log₂n) < 线性阶O(n) < 线性对数阶O(nlog₂n) < k次方阶O(n^k) < 指数阶O(2ⁿ)