由于考研，还没复习完高数就跑来专业课了。。。大体记录一下，方便复习。
后续，不考研了。

  • 基本概念和术语

    • 数据（集合）：描述客观事物属性的数、字符及所有，但是须得能输入到计算机中并被计算机程序识别和处理的符号的集合。其中，数据和信息的关系：数据是信息的形式，信息是数据的含义。
    • 数据元素（相对概念）：数据的基本单位，通常作为一个整体考虑。
    • 数据项：组成数据元素的不可分割的最小单位。（例如：学生记录是一个数据元素，其中，学号、性别等为数据项）
    • 数据对象（集合）：具有相同性质的数据元素的集合，是数据的一个子集。
    • 结构：数据元素之间的关系。
    • 数据结构：数据结构就是相互之间存在一种或者多种特定关系的数据元素的集合。
    • 数据类型：一个值的集合，以及定义在此集合上的一组操作的总称。有：原子类型、结构类型、抽象数据类型（ADT）。

  • 数据结构三要素：逻辑结构、存储结构、数据的运算

  • 逻辑结构

    • 线性结构：线性表（一般线性表、栈和队列、串、数组）
    • 非线性结构：层次结构（树），网状结构（图）

  • 存储结构

    • 顺序存储：把逻辑上相邻的元素存储在物理位置上也相邻的存储单元中。只存数据。申请一大块连续内存空间。
    • 链式存储：借助指针存储，存放数据+关系。
    • 索引存储：建立附加的存储表——索引表，索引表中的每项称为索引项。存放数据+关系。
    • 哈希存储：根据关键字直接计算出元素的存储（连续的）地址。（私以为是函数映射，就是找一个函数，输入元素为x，存储地址为y）。存放数据。申请一大块连续内存空间。

  • 数据运算：施加在数据上的运算，包括运算的定义和实现。其中，运算的定义针对逻辑结构，运算的实现针对存储结构。

小结：
数据结构+算法=程序，这一个式子可以解答数据结构和算法的重要性。

补充：

  1. 抽象数据类型ADT，，描述了数据的逻辑结构和抽象运算，通常用（数据对象，数据关系，基本操作集）这样的三元组来表示，从而形成一个完整的数据结构定义。
  2. 线性表属于逻辑结构，顺序表属于存储结构。
  3. 链式存储设计时，各个不同的结点的存储空间可以不连续，但是结点内的存储单元地址必须连续！