前言

在数据结构课程结课之后，我打算重开之前一直搁置的数据结构教程书写，一方面为加深数据结构的学习印象，另一方面为以后复习做一个参考。

本教程编程语言采用 JAVA ,文章框架参考自 HUST数据结构PPT ,源码内容参考自 尚硅谷 JAVA 数据结构教程 。

绪论部分主要以定义介绍为主，掌握概念即可，复杂度方面将具体对复杂度进行分析,其中具体对时间复杂度进行分析

数据结构的定义

  1. 数据结构本身概念的基本定义：
    数据结构是计算机中存储、组织数据的方式。
  2. 数据结构这门学科的基本定义：
    数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等相关问题的学科。

基本概念和术语

  1. 数据(data)：所有能输入到计算机中并被计算机程序加工、处理的符号的总称。
    如：整数、实数、字符、声音、图象、图形等。
  2. 数据元素(data element):数据的基本单位。（元素、记录、结点、顶点）在计算机程序中通常作为一个整体进行考虑和处理。
  3. 数据项(data item):是数据的不可分割的最小单位。如：姓名、年龄等。一个数据元素可由一个或多个数据项组成。
    如: (姓名、年龄)
  4. 数据对象(data object): 由性质相同(类型相同)的数据元素组成的集合。

    数据对象是数据的一个子集。

  5. 数据结构(data structure):数据结构就是相互之间存在一种或多种特定关系的数据元素的集合。

    在任何问题中，数据元素都不是孤立存在的，而是在它们之间存在着某种关系，这种数据元素相互之间的关系称为结构(Structure)。
    按照研究角度来分，数据结构可分为：

    • 逻辑结构：面向数据之间的逻辑概念的关系。
    • 物理结构：面向数据之间的物理储存等面向计算机方面的关系。

    逻辑结构：
    数据之间的相互关系称为逻辑结构，即从逻辑关系上描述数据，与数据的存储无关，是独立于计算机的。通常分为四类基本结构：

    • 集合
    • 线性结构
    • 树形结构
    • 图（网）状结构

    物理结构：
    物理结构亦称存储结构，是数据的逻辑结构在计算机存储器内的表示（或映像），依赖于计算机。存储结构可以分为四大类：

    1. 顺序存储结构(向量,一维数组)
    2. 非顺序存储结构(链接表、链式存储结构）
    3. 索引存储结构
    4. 哈希（Hash）存储结构
    6. 数据类型（data type)：是一个值的集合和定义在这个值上的一组操作的总称。数据类型可分为两类：
  • 原子类型(如：int,char,float 等)
  • 结构类型(如：数组,结构,联合体等)
  1. 抽象数据类型(Abstract Data Type)：与计算机的实现无关的数据类型。

抽象数据类型

抽象数据类型（Abstract Data Type，ADT）是电脑科学中具有类似行为的特定类别的数据结构的数学模型；或者具有类似语义的一种或多种程序设计语言的数据类型。抽象数据类型是间接定义的，通过其上的可执行的操作以及这些操作的效果的数学约束（与可能的代价）。
例如，抽象的堆栈（stack）由 3 个操作定义：推入 push，弹出 pop（接受约束：每次弹出返回的是最新被推入且没有被弹出的数据，也就是后进先出），查看堆栈顶端数据 peek。当分析使用堆栈算法的效率，所有这 3 个操作用时相同，无论堆栈中包含多少项数据；并且对每项数据栈使用了常量大小的存储。
抽象数据类型（ADT）是纯粹理论实体，用于简化描述抽象算法，分类与评价数据结构，形式描述程序设计语言的类型系统。一个 ADT 可以用特定数据类型或数据结构实现，在许多程序设计语言中有许多种实现方式；或者用形式规范语言描述。ADT 常实现为模块（module）：模块的接口声明了对应于 ADT 操作的例程（procedure），有时用注释描述了约束。

算法与算法分析

  1. 算法定义：是对特定问题求解步骤的一种描述，算法是指令的有限序列，其中每一条指令表示一个或多个操作。
  2. 算法的五个特征：
    • 有穷性：在有限步(或有限时间)之后算法终止。
    • 确定性：无二义性。
    • 可行性：算法中的操作都是已经实现的基本运算执行有限次来实现的。
    • 输入：有 0 或多个输入量。
    • 输出：至少有一个输出量。

  3. 算法设计要求：

    1. 正确性：

      • 无语法错误
      • 对 n 组输入产生正确结果
      • 对特殊输入产生正确结果
      • 对所有输入产生正确结果

    2. 可读性：“算法主要是为了人的阅读与交流”

    3. 高效率与低存储量

  4. 算法效率的度量：

    • 事后统计： 收集此算法的执行时间和实际占用空间的统计资料
    • 事先分析： 求出该算法的时间复杂度
    • 将一个算法转换成程序并在计算机上执行时，其运行所需要的时间取决于下列因素：
      1. 硬件的速度。
      2. 书写程序的语言。
      3. 编译程序所生成目标代码的质量。
      4. 问题的规模。

在各种因素都不能确定的情况下，很难比较出算法的执行时间。因此，使用执行算法的绝对时间来衡量算法的效率是不合适的。为此，将上述各种与计算机相关的软、硬件因素都确定下来，这样一个特定算法的运行工作量的大小就只依赖于问题的规模（通常用正整数 n 表示），或者说它是问题规模的函数。

  1. 算法的时间复杂度：

    1. 时间频度：一个算法中的原操作执行次数称为语句频度频度，记为 f(n)
    2. 时间复杂度：
      • T(n) = O(f(n)) 称O(f(n))为算法的渐近时间复杂度，简称时间复杂度。大O（Order 的缩写，意指数量级）表示随问题规模 n 的增大，算法执行时间的增长率和f(n)的增长率相同。
      • 大 O 操作的本质是求f(n)的同阶无穷大。当 n 趋近于无穷大时，f(n)/g(n)的极限值为不等于零的常数，则称g(n)是f(n)的同数量级函数。

  2. 算法的空间复杂度:
    一个算法在计算机存储器上所占用的存储空间，包括:

    1. 存储算法本身所占用的存储空间
    2. 算法的输入输出数据所占用的存储空间
    3. 算法在运行过程中临时占用的存储空间

算法时间复杂度具体实例分析

  1. 常量阶

    1
    2
    3
    int s = 0;
s++;
System.out.println(s);
    1. 语句频度: f(n)=3
    2. 时间复杂度为：T(n)=O(f(n))=O(3)=O(1)
    3. O(1)称成为常量阶/常量数量级

  2. 线性阶

    1
    2
    3
    4
    5
    6
    7
    void sum(int a[], int n) {
  int s=0,i; // 1次
  for(i=0；i<n；i++){ // n次
  s = s + a[i]; // n次
  printf("%d",s);// 1次
  }
}
    1. 语句频度: f(n)=1+n+n+1
    2. 时间复杂度为：T(n)=O(f(n))=O(2n+2)=O(n）
    3. O(n)称成为线性阶/线性数量级
    3. 平方阶 
    1
    2
    3
    4
    5
    6
    7
    8
    9
    void sum(int n) {
  int i, j, s = 0; // 1次
  for(i = 1;i <= n; i++){ // n次
    for(j=1;j<=i;j++){ // n(n+1)/2 次
        s++; // n(n+1)/2次
    }
    System.out.println(s); // n次
  }
}
    1. 语句频度: $ f(n)=1+n+n(n+1)+n = n^2+3n+1 $
    2. 时间复杂度为：$ T(n)=O(f(n))=O(n^2) $
    3. $ O(n^2) $ 称成为线性阶/线性数量级

  3. 复杂度比较

常数阶 对数阶 线性阶 线性对数阶 平方阶 立方阶 … k 次方阶 指数阶
$ O(1) $ $ O(log_2 n) $ $ O(n) $ $ O(nlog_2 n) $ $ O(n^2) $ $ O(n^3) $ … $ O(n^k) $ $ O(2^n) $

平均时间复杂度与最坏时间复杂度

  1. 平均时间复杂度
    指所有可能的输入实例 均以等概率出现 的情况下，该算法的运行时间
  2. 最坏时间复杂度
    最坏情况下的世界复杂度称为最坏时间复杂度。

    一般讨论的时间复杂度均是最坏情况下的时间复杂度，因为：最坏情况下的时间复杂度是算法在 任何输入实例上运行时间的界限，这就保证了算法的运行时间不会比最坏情况更长