数据结构绪论

数据结构的基本概念

基本概念和术语

• 数据：是信息的载体，是对客观事物的符号表示的集合
• 数据元素(节点)：数据的基本单位，在程序中通常作为一个整体进行考虑和处理。一个数据元素可以由若干个数据项^[1]组成。(数据项是构成数据元素最小单元)
• 数据对象：是具有相同性质的数据元素的集合，是数据的子集。 (一个数组就是数据对象）
• 数据类型：一个值的集合和定义在此集合上的一组操作的总称。是语言对数据结构的实现，其明显或隐含地规定了数据的取值范围、存储方式及允许进行的运算。
  • 原子类型：int、char、double等
  • 结构类型：结构体
  • 抽象数据结构：线性表、树、图等
• 数据结构：相互之间存在一种或多种特定关系的数据元素的集合

按某种逻辑关系组成的数据元素，按一定的存储方式存储于计算机中，并在其上定义了一个运算的集合，称为一个数据结构。

数据结构=数据的逻辑结构+数据的存储结构+数据的运算(算法)

数据结构三要素

• 数据的逻辑结构：数据元素之间的逻辑关系，与数据的存储无关。
  • 线性结构：一般线性表、受限线性表（栈 队列 串）、线性表的推广（数组）
  • 非线性结构：集合、树形结构（一般树 二叉树）、图状结构（有向图 无向图）
• 数据的存储结构(物理结构)：数据结构在计算机中的表示，包括存储各节点的数值和存储结点与结点之间的逻辑关系
  • 顺序存储：逻辑上相邻的元素存储在物理上相邻的存储单元，其元素之间的逻辑关系由存储单元地址间的关系隐含表示。随机存取，但用相邻的一片存储空间产生外部碎片
  • 链式存储：结点增加指针字段，用于存放临近结点的存储地址，只能顺序存取
  • 索引存储：在存储结点的同时，增加索引表，索引表的索引项为：（关键字，地址），关键字标识结点，地址为结点的指针。各结点的地址在索引表中是依次排列的。
  • 散列存储（哈希hash）：根据结点的值确定结点的存储地址。以结点作为自变量，通过散列函数算出结果i，再把i作为结点的存储地址。
• 数据的运算
  • 运算的定义
  • 运算的实现

算法和算法的评价

算法的基本概念

• ：algorithm,是对特定问题求解步骤的描述，是指令的有限序列，每条指令包含一个或多个操作。

• 重要特征

  • 有穷性:有限的步骤和有限的时间内完成
  • 确定性:每个指令有确定的含义
  • 可行性:算法是可以实现的
  • 输入:0个或多个输入
  • 输出:一个或多个输出

• “好算法”的标准

  • 正确性:正确地解决问题
  • 可读性：
  • 健壮性:输入非法数据，能够做出反应
  • 效率与低存储量需求

算法效率的度量

• 时间复杂度：当n（问题规模）趋于无穷大时，T(n)的数量级。记作T(n)=O(f(n)), O的含义是T(n)的数量级。
  • 频度：某语句在算法中被执行的次数
  • T(n)：所有语句的频度之和，n为问题规模
  • O(1) < O(log₂n) < O(n) < O(n²) < O(n³) < O(2ⁿ) < O(n!) < O(nⁿ)
• 空间复杂度: 指该算法所耗费的存储空间。计算公式计作：S(n) = O(f(n))。其中 n 也为数据的规模，f(n) 在这里指的是 n 所占存储空间的函数。
• 算法原地工作：算法所需的辅助空间为常数O(1)

时间复杂度的计算

• 渐进时间复杂度:（asymptotic time complexity）就是当n趋于无穷大的时候，f(n) 得到的极限值。