数据结构1：基本概念

数据结构基本概念

• 基本概念

  • 数据

    ：数据是信息的载体，是描述客观事物属性的数、字符及所有能输入到计算机中并被计算机程序识别和处理的符号的集合。数据是计算机程序加工的原料。

  • 数据元素、数据项

    ：数据元素是数据的基本单位，通常作为一个整体进行考虑和处理。一个数据元素可由若干数据项组成，数据项是构成数据元素的不可分割的最小单位。要按不同场景进行确定。

  

  数据元素与数据项

  • 数据结构、数据对象

    ：数据结构是相互之间存在一种或多种特定关系的数据元素的集合。数据对象是具有相同性质的数据元素的集合，是数据的一个子集。

  • 数据类型

    ：数据类型是一个值的集合和定义在此集合上的一组操作的总称，如int、float类型等。

    原子类型：其值不可再分的数据类型。

    结构类型：其值可以再分解成若干成分的数据类型。

  • 抽象数据类型（ADT）

    ：是抽象数据组织及与之相关的操作。ADT用数学化的语言定义数据的逻辑结构、运算，且不关注具体实现。
• 三要素

  • 逻辑结构

    ：数据元素之间的逻辑关系。集合、线性结构、树形结构、图结构。

  • 物理结构

    ：数据元素的逻辑关系在计算机中的表示。顺序存储、链式存储、索引存储、散列存储。

    顺序存储：把逻辑上相邻的元素存储在物理位置上也相邻的存储单元中，元素之间的关系由存储单元的邻接关系来体现。

    链式存储：逻辑上相邻的元素在物理位置上可以不相邻，借助指示元素存储地址的指针来表示元素之间的逻辑关系。

    索引存储：在存储元素信息的同时，还建立附加的索引表。索引表中的每一项称为索引项，索引项的一般形式是（关键字，地址）

    散列存储：根据元素的关键字直接计算出该元素的存储地址，又称哈希存储。

    

    索引存储

  • 数据的运算

    ：施加在数据上的运算包括运算的定义和实现。运算的定义是针对逻辑结构，指出运算的功能；运算的实现是针对存储结构的，指出运算的具体操作步骤。

    例如，对于一个队列（线性结构）来说，我们需要他能够队头元素出列、新元素进入尾部，等需求，这些都是对运算的定义，这些定义是根据逻辑结构来决定的，但是逻辑结构的实现可以有很多种物理结构，针对这些不同的物理结构它们对运算的实现也不一样，故实现是针对存储结构的。

算法基本概念

• 什么是算法
  • 程序=数据结构+算法
  • 数据结构是要处理的信息，算法是处理信息的步骤
• 算法的五个特性
  • 有穷性：有穷时间内可以执行完（算法是有穷的，程序可以是无穷的）。
  • 确定性：相同输入只会产生相同输出。
  • 可行性：可以用已有的基本操作实现算法。
  • 输入：给算法处理的数据。
  • 输出：算法处理的结果。
• 好算法的特质
  • 正确性：能正确解决问题。
  • 可读性：对算法的描述要让其他人也看得懂。
  • 健壮性：算法能处理一些异常状况。
  • 高效率与低存储量需求：算法执行省时省内存；算法时间复杂度低、空间复杂度低。

算法的时间复杂度

• 如何计算
  1. 找到以一个基本操作（最深层循环）
  2. 分析该基本操作的执行次数x与问题规模n的关系x = f(n)
  3. x的数量级O(x)就是算法复杂度
• 常用技巧
  • 加法规则：O(f(n)) + O(g(n)) = O(max(f(n),g(n)))
  • 乘法规则：O(f(n)) × O(g(n)) = O(f(n) × g(n))
  • O(1) < O(log2n) < O(n) < O(nlog2n) < O(n2) < O(n3) < O(2n) < O(n!) < O(nn)
• 三种复杂度
  • 最坏时间复杂度
  • 平均时间复杂度
  • 最好时间复杂度

算法的空间复杂度

• 普通程序计算
  • 找到所占空间大小与问题规模相关的变量
  • 分析所占空间x与问题规模n的关系 x = f(n)
  • x的数量级O(x)就是算法空间复杂度
• 递归程序计算
  • 找到递归调用的深度x与问题规模n的关系x = f(n)
  • x的数量级O(x)就是算法空间复杂度