[TOC] # 1.1 基本概论和术语 + 数据：信息的载体，它能被计算机识别、存储和加工处理 + 数据元素：数据的基本单位。有些情况下也被称为元素、节点、定点、记录。 + 数据结构：数据之间的相互关系。 + 逻辑结构：数据之间的逻辑关系 + 存储结构：数据元素及其关系上在计算机存储器内的表示 + 数据的运算：对数据施加的操作 数据的每一个**行**表示一个节点（记录） 对表中任意一个节点，与它相连且在他前面的节点（直接前趋）最多只有一个； 与表中任意一个节点相连且在他之后的节点（直接后继）也最多只有一个。 开始节点：第一个节点没有直接前趋，故称开始节点； 终端节点：最后一个节点没有直接后继，故称终端节点。  **马二**的直接前趋为**丁一**、直接后继为**张三**。 **数据的逻辑结构** + 线性结构 特征：若结构是非空集，则由且只有一个开始节点和终端节点，并且所有节点都最多只有一个直接前趋和直接后继。 + 非线性结构 特征：一个节点可能有多个直接前趋和直接后继。 **数据的存储结构** + 顺序存储方法、 逻辑上相连的节点存储在物理位置上相连的存储单元里，逻辑间的逻辑关系由存储单元邻接关系来体现。借助于**数组**来描述。 + 链接存储方法 不要求逻辑上相邻的节点在物理上亦相等，节点间的逻辑关系由附加的指针字段表示。通常借助**指针**来描述。 + 索引存储方法 存储节点信息的同时，还建立附加的索引表。 索引表中的每一项称为**索引项**。一般形式为：`(关键字,地址)`。 关键字：能唯一标识一个节点的那些数据项。 + 稀疏索引 一组节点在索引表中对应一个索引项，该索引表称为**稀疏索引** + 稠密索引 每个节点在索引表中都有一个索引项，该索引表称为**稠密索引** + 散列存储方法 基本思想：根据节点的关键字直接计算出该节点的存储位置。 # 1.2 学习数据结构的意义 # 1.3 算法的描述和分析 ~~~ #define N 100 // n阶 void MatrixMultiply(int A[N][N], int B[N][N], int C[N][N]){ int i, j, k; for(i=0; i<N; i++){ // n + 1， for(j=0; j<N; j++){ // n(n + 1) C[i][j] = 0; // n^2 for(k=0; k<N; k++){ // n^2(n + 1) C[i][j] = C[i][j]+A[i][k]*B[k][j]; // n^3 } } } } ~~~  **问题的规模（size）**：算法求解的输入量，用一个整数表示。 **时间复杂度**：算法的时间消耗，它是该算法所求解决问题规模 n 的函数。 渐近时间复杂度：当问题的规模 n 趋渐与无穷大时，我们把时间复杂度`T(n)`的数量级。 常规件的时间复杂度： + 常数阶（`O(1)`） + 对数阶（`O(log2 n)`） + 线性阶（`O(n)`） + 线性对数阶（`O(nlog2 n)`） + 平方阶（`O(n^2)`） + 立方阶（`O(n^3)`） + 。。。。 + k次方阶（`O(n^k)`） + 指数阶（`O(2^n)`）  **空间复杂度**：算法所消耗的存储空间，它也是问题规模 n 的函数。 算法的复杂度：时间复杂度、空间复杂度