数据结构——概论
基本概念和术语
数据是信息的载体
数据元素是数据的基本单位
数据结构指的是数据之间的相互关系，即数据的组织形式
逻辑结构
- 数据元素之间的逻辑关系
-
- 集合
- 线性结构
- 树结构
- 图结构
物理结构
- 数据结构在计算机中的表示及存储方式
-
- 顺序存储方式
-
-
- 物理位置相邻
-
-
- 链式存储方式
-
-
- 指针指示逻辑关系
-
-
- 索引存储方式
-
-
- 除保存数据元素外，还要建立索引表
-
-
- 散列存储方式
-
-
- 根据关键字计算物理存储位置
-
算法和算法分析
算法的基本概念
算法必须满足如下5个重要特征
- 输入：有0或多个输入值
- 输出：有1或多个输出值
- 有穷性：一个算法必须在执行又穷步骤之后结束
- 确定性：算法的每一个步骤必须是有确切含义的
- 可行性：算法中要做的运算都是相当基本的、能够精确进行的
- 算法可以没有输入，单必须要有输出，通常输出的是算法的执行结果。实现算法的程序的运行时间是有限的，算法的每个执行步骤不能有歧义，且必须是能够执行的。
算法的评估和复杂性度量
正确性是评判算法的首要指标
- 时间复杂度
- 空间复杂度
- 只有当一个算法需要的额外空间数量依赖于问题规模时，才考虑他的空间复杂度