数据结构的基本概念

“数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。数据结构反映数据的内部构成，即数据由那部分构成。

数据结构的基本概念

• 相关术语
  • 数据
    • 能够被计算机存储、加工的对象
  • 数据对象
    • 性质相同的数据元素的集合，类似于数组
  • 数据元素、数据项
    • 数据元素是基本单位，数据项是最小单位
    • 数据元素是数据的个体，其关系为集合关系
  • 数据类型
    • 隐含于数据元素之中
    • 是一个值的集合和定义在这个集合上一组运算的总称
    • 例如：C中的int数据类型由-32768~32767的整数和运算符构成
  • 抽象数据类型(ADT)
    • 数据对象+数据关系+数据操作-->可构成一个完整的数据结构定义
    • 与计算机内部表示和实现无关
• 数据结构
  • 定义
    • 在任何问题中，数据元素都不是孤立存在的，而是在它们之间存在着某种关系，这种数据元素相互之间的关系称为结构（Structure）。数据结构是相互之间存在一种或多种特定关系的数据元素的集合。数据结构包括三方面的内容：逻辑结构、存储结构和数据的运算。
    • 对于两个数据结构，三要素中有一个不同就属于不同的数据结构，例如二叉树与二叉排序树，逻辑结构与物理结构相同，但运算(查找等)不同，所以就属于不同数据结构
  • 逻辑结构
    • 逻辑结构是指数据元素之间的逻辑关系，数据的组织形式它与数据的存储无关，是独立于计算机的
    • 数据的逻辑结构分为线性结构和非线性结构
      • 集合 结构中的数据元素之间除了“同属于一个集合”的关系外，别无其他关系。 类似于数学上的集合
      • 线性结构 结构中的数据元素之间只存在一对一的关系。比如排队
      • 树形结构 结构中的数据元素之间存在一对多的关系。比如家族族谱
      • 图状结构或网状结构 结构中的数据元素之间存在多对多的关系。 比如地图
      • 广义表是线性表推广，本身并不是线性结构而数组是线性结构，二维及多维数组则是非线性结构
    • 常见的逻辑结构：有序表、线性表、栈、队列、串、广义表、非线性表、集合、树、一般树、二叉树、哈夫曼树、平衡二叉树、图、有向图、无向图
    • 常见的数据结构：顺序表、数组、链表、单链表、双链表、循环链表、静态链表、索引表、哈希表、线索二叉树
  • 物理结构
    • 存储结构是指数据结构在计算机中的表示（又称映像），也称物理结构。它包括数据元素的表示和关系的表示。数据的存储结构是逻辑结构用计算机语言的实现，它依赖于计算机语言。数据的存储结构主要有：顺序存储、链式存储、索引存储和散列存储。
      • 顺序存储：存储的物理位置相邻。（p.s. 物理位置即信息在计算机中的位置。）
        • 例子
          • 数组
        • 优点
          • 可以实现随机存取，每个元素占用最少的存储空间
        • 缺点
          • 只能使用相邻的一整块存储单元，因此可能产生较多的外部碎片
      • 随机存储
        • 链接存储：存储的物理位置未必相邻，通过记录相邻元素的指针来找到相邻元素。
          • 例子
            • 链表
          • 优点
            • 不会出现碎片现象，能充分利用所有存储单元
          • 缺点
            • 每个元素因存储指针而占用额外的存储空间，且只能实现顺序存取
        • 索引存储：在存储元素信息的同时，还建立附加的索引表。
          • 例子
            • 索引表
          • 优点
            • 检索速度快
          • 缺点
            • 附加的索引表额外占用存储空间
        • 散列存储：通过关键字直接计算出元素的物理地址
          • 例子
            • 哈希表
          • 优点
            • 检索、增加和删除结点的操作都很快
          • 缺点
            • 若散列函数不好，则可能出现元素存储单元的冲突，而解决冲突会增加时间和空间开销
    • 存取方式
      • 随机存取
        • 随机存取（直接存取,Random Access）指的是当存储器中的数据被读取或写入时，所需要的时间与该数据所在的物理地址无关。
          • 数组
          • 顺序存储结构采用随机存取
          • 随机存取存储器(RAM:Random Access Memory)
      • 顺序存取
        • 顺序存取(Sequential Access)是一种按记录的逻辑顺序进行读、写操作的存取方法，所需要的时间与该数据所在的物理地址有关。
          • 链表
          • 录音磁带、光盘、机械硬盘里面的磁盘
  • 数据的运算
    • 增加
    • 插入
    • 删除
    • 修改
    • 查找
    • 排序
  • 逻辑结构、存储结构和运算之间的关系
    • 数据的逻辑结构反映数据元素之间的逻辑关系，数据的存储结构是数据结构在计算机中的表示，包括数据元素的表示及其关系的表示。数据的运算是对数据定义的一组操作，运算是定义在逻辑结构上的，和存储结构无关，而运算的实现则依赖于存储结构。
    • 数据的逻辑结构和存储结构是密不可分的两个方面，一个算法的设计取决于所选定的逻辑结构，而算法的实现依赖于所采用的存储结构。
    • 逻辑结构相同但存储结构不同，则为不同的数据结构如：线性表--->顺序表、链表
    • 逻辑结构相同存储结构相同，运算集合不同，则为不同的数据结构如：栈和队列
• 算法
  • 算法（Algorithm)是对特定问题求解步骤的一种描述，是指令的有限集合，其中的每一条指令表示一个或者多个操作。
  • 程序=数据结构+算法
    • 程序设计：设计一个好的数据结构，一个好的算法
  • 独立于具体的程序设计语言，与具体的计算机无关
  • 算法的五个特征
    • 1，有穷性：有限步之后结束
    • 2，确定性：不存在二义性，即没有歧义
    • 3，可行性：比如受限于计算机的计算能力，有些算法虽然理论上可行，但实际上无法完成。
    • 4，输入：能被计算机处理的各种类型数据，如数字，音频，图像等等。
    • 5，输出：一至多个程序输出结果。
    • 可以没输入，不可没输出
  • 算法的复杂度
    • 时间复杂度：
      • • 它用来衡量算法随着问题规模增大，算法执行时间增长的快慢；
      • • 是问题规模的函数：T(n)是时间规模函数 时间复杂度主要分析T(n)的数量级
      • • T(n)=O(f(n)) f(n)是算法中基本运算的频度 一般我们考虑最坏情况下的时间复杂度
      • 取决于问题的规模(默认为n)+待处理数据的初态
      • 时间复杂度为O(n)，表明该算法的执行时间与n成正比
    • 空间复杂度：
      • • 它用来衡量算法随着问题规模增大，算法所需空间的快慢；
      • • 是问题规模的函数：S(n)=O(g(n)) ；算法所需空间的增长率和g(n)的增长率相同。
      • 算法原地工作指辅助空间为常数，并不是不需要任何额外的辅助空间
    • 复杂度计算为重点
      • 常用的时间复杂度大小关系：
      • 复杂度如何计算
        • 时间复杂度计算（单个循环体）
          • 直接关注循环体的执行次数，设为k
        • 时间复杂度计算（多个循环体）
          • 两个运算规则：乘法规则，加法规则。
  • 算法设计的目标评价一个好算法
    • 正确性
    • 易读性
    • 健壮性
    • 好的时空性能
• 数据
  • 数据对象
    • 数据元素
      • 数据项
      • 数据项
    • 数据元素
      • 数据项
      • 数据项
  • 数据对象
    • 数据元素
      • 数据项
      • 数据项
    • 数据元素
      • 数据项
      • 数据项
  • 相互之间的关系
• 有序表
  • 指表中所有数据元素的数值以递增或递减方式排序，是数据元素的数值的有序性
  • 有序表只描述元素之间的逻辑关系，故为逻辑结构，因此有序表既可以顺序存储又可以链式存储
• 堆
  • 是元素的序列，存在一维数组中，可看作是线性结构