第一章 绪论

数据结构基本概念

• 数据：是信息的载体，描述客观事物属性的数、字符等能被计算机识别和处理的符号集合
• 数据元素：数据的基本单位，通常作为整体考虑，由若干数据项组成（是不可分割的最小单位）
• 数据对象：具有相同性质的数据元素的集合
• 数据类型：一个值的集合和在此集合上的一组操作
  • 原子类型：其值不可再分，如：int、bool
  • 结构类型：其值可以分为若干的成分数据类型，如：结构体
  • 抽象数据类型：ADT，使用数学化的语言定义数据的逻辑结构和运算，不定义实现（逻辑结构）
• 数据结构：互相存在关系的数据元素的集合
  • 逻辑结构：指数据结构间的逻辑结构，与数据的存储无关
    • 线性结构：数据元素间存在一对一的关系，存在唯一的前驱和后继
      • 线性表
      • 栈和队列
      • 数组
    • 非线性结构：
      • 集合：属于同一个集合，再无其他关系
      • 树：数据元素间存在一对多的关系
      • 网：数据元素间存在多对多的关系
  • 存储结构：又称物理结构，会影响数据的运算和存储空间的分配复杂度的不同
    • 顺序存储：逻辑上相邻的元素在物理上也连续存储
      • 优点：能够实现顺序存储
      • 缺点：只能使用连续的一块空间，存在外部碎片
    • 链式存储：使用指针来链接各个原数
      • 优点：不会出现碎片
      • 缺点：占用额外的空间，只能顺序存储
    • 索引存储：使用索引表
      • 优点：检索速度快
      • 缺点：占用额外的空间，需要额外的修改
    • 散列存储：又称哈希存储
      • 优点：检索、增加和删除的速度都很快
      • 缺点：可能出现数据单元的冲突
  • 数据运算：包括定义和实现，定义针对逻辑结构，实现针对物理结构

算法和评价

算法：针对特定问题的求解的步骤的一种描述，是指令的有限序列，每个指令表示一个或者多个操作

• 算法特征：
  • 有穷性：必须在有限步数内执行完毕，且每步必须在有限的时间内完成
  • 确定性：相同的输入必有相同的结果
  • 可行性：每步均可以使用已经实现的基本运算执行有限次来实现
  • 输入：有零个或者多个
  • 输出：有一个或者多个
• 算法评价：
  • 正确性：正确的解决问题
  • 可读性：具有良好的可读性
  • 健壮性：输入非法数据时能够处理
  • 高效率低存储：时间空间复杂度低
• 算法效率度量：
  • 时间复杂度：一个语句的频度指在算法中重复执行的次数，使用T(n)=O(f(n))来描述，f(n)指随深层循环语句的执行次数（浅层循环和顺序执行的代码不做考虑），通常填入表达式中将系数改为“1”的最高阶项，通常指最坏情况下的
    • 加法规则：O(f(n))+O(g(n))=O(max(f(n),g(n)))
    • 乘法规则：O(f(n))×O(g(n))=O(f(n)×g(n))
    • 常见复杂度：1<log2n<n<nlog2n<n^2<n^3<2^n<n!<n^n.
  • 空间复杂度：S(n)=O(g(n))，一个程序运行的时候需要的空间包括程序本身和计算所需要的辅助空间，算法的原地工作指算法所需的辅助空间的大小为零O(1)