数据结构概述

一张图带你了解数据结构。数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。通常情况下，精心选择的数据结构可以带来更高的运行或者存储效率。该导图是数据结构与算法第一章，还没有很完整，会继续补充，喜欢的小伙伴可以点个赞哦！

数据结构概述

• 数据结构的概念
  • 数据元素（数据节点），简称结点：是数据的基本单位
    • 一个数据结点由用来描述一个独立事物的名称、数量、特征、性质的一组相关信息组成。
    • 一个结点含有多个数据项，每个数据项是结点的一个域，能够用来唯一标识的域称为关键字域。
      • 数据项是最小单位
    • 一个结点只含有一个数据项，即单值结点
  • 一个有穷的结点集合D,以及该集合中各结点之间的关系R,组成一个数据结构，B=(D,R)
    • D和R是对客观事物的抽象描述，R标识结点之间的逻辑关系，所以（D,R)指的是数据的逻辑结构
    • D是有穷的结点集合，R是D中结点间的有穷关系集合
  • 数据结构在计算机内的存储形式称为存储结构（物理结构）
    • 用来存储一个数据结点，并在必要时存储该结点与其他结点之间关系的一组存储单元称为一个存储结点
    • 当前尚未存储数据结点的存储结点叫空白结点或空结点、自由结点
  • 数据结构的种类
    • 表结构
      • 表是树的特性
      • 线性
    • 树结构
    • 图结构
      • 树和散是图的特性
    • 非线性
    • 散结构
      • 仅同属一个集合
• 抽象数据类型
  • 含义：简称ADT，是将“数据“连同对其的”处理操作“（即运算）封装在一起而形成的复合体
  • ADT=（D,R,P)
    • D是数据对象
    • R是D 上的关系表
    • P是D上的操作集
      • InitList（&L) 构造一个空的有序表L
      • InsertElem（&L,e) 在有序表中插入新元素e，使表仍有序
      • DeleteElem（&L,e) 在有序表中删除元素e
      • ListTraverse（L) 输出表中的元素
      • ListSearch（L,e) 在表中查找值为e的元素
      • ListLength（L) 返回表中元素的个数
      • ListEmpty（L) 测试表空否
    • 封装法、半封装法、分散法
• 算法的概念
  • 算法是有穷规则的集合，二规则规定来解决某一特定问题的运算序列，是对特定问题求解步骤的一种描述，是指令的有限序列，遵循指令流可以完成特定的功能
  • 算法的表现形式
    • 描述形式
      • 算法的原始形式
    • 程序形式
      • 算法的实现形式
  • 算法的描述
    • 自然语言
      • 简单易懂，易产生二义性
    • 流程图
      • 比较清晰、只管、易于理解，易产生二义性
    • 微程序或伪代码
      • 可以有效避免二义性
  • 评价标准（算法分析）
    • 正确性
      • 通常要用数学归纳法去证明
      • 算法程序没有语法错误
      • 对合法输入产生满足要求的输出
      • 对非法输入产生满足要求的输出
      • 对故意刁难的测试输入有满足要求的输出结果
    • 有效性
    • 健壮性
      • 对非法操作和非法输入数据能否做出恰当的反应，并进行适当的处理，不会出现系统瘫痪和产生莫名其妙的结果
    • 易读性和易维护性
  • 时间复杂度
    • 算法的有效性值算法的运行效率
    • 算法对时间的需求称为算法的时间复杂度，或时间复杂度
    • 最坏情况下的时间复杂度用Tw(n)表示，w指的是最坏情况
    • 平均情况（期望情况）用TE（n）表示，E表示平均情况
    • 计算的一般方法（事前事后分析法）
      • 支配性语句度量法
      • 分段计算法
      • 分层计算法
      • 递推式方法
        • 间第二章度二分查找算法的时间分析
      • 数学模型法
  • 空间复杂度
  • 算法选用原则（能满足客观要求）
    • 算法实现的难易程度
    • 算法使用的次数
    • 算法运行环境