开个新坑, 这里是高中信息技术的笔记, 这个分类目前放选择性必修一的一些笔记, 同时由于最近在学数据结构与算法分析这门课程, 对于高中笔记的补充会放在分割线后.

根据事物之间的关系确定合理的数据结构, 并借助其来组织数据, 设计算法.

数据

事物的多样性, 复杂性

数字 由阿拉伯数字或其他含义相同的符号表示.

  • 数字本身没有意义, 没有量的含义.

数值 由数字, 符号组成的, 具有量的意义的, 可以进行算术运算的数据.
数据 多指用计算机进行处理的符号表示的总称.

  • 其他表现形式 数字, 文字 → 图形, 图像, 视频, 音频等.
  • 数据促进了人类社会的发展.
  • 大数据推动人类进入一个崭新的时代.

数据的组织

算法 + 数据结构 = 程序

数据元素(Data Element) 数据的基本单位.

  • 别称: 元素, 节点, 顶点, 记录.

数据类型(Data Type) 具有相同性质的计算机数据的集合以及在这个数据集合上的一组操作.

  • 基本数据类型(原子数据类型) 计算机编程环境提供.
  • 结构数据类型 在程序设计中由基本数据类型构造出的, 复合的数据类型.

数据结构(Data Structure) 数据元素之间的相互关系. (数据的组织形式)

  • 数据的逻辑结构
  • 数据的存储结构
  • 数据的运算
  • 目的:
    • i. 确保数据处理的正确性.
    • ii. 提高编程实现和数据处理的效率.

数组 描述数据对象本身, 数据所处位置, 数据前后关系.

  • 遍历 根据数据间的逻辑关系, 遵循一定顺序, 依次对所有数据做一次且仅做一次访问.

链表 不关心数据的具体位置, 只知道相互的链接顺序.

  • 单向, 双向, 循环链表
  • 指针(Pointer) 指示一个数据存储地址的变量.

栈 后进先出(Last In First Out, LIFO)
队列 先进先出(First In First Out, FIFO)
树 一个元素上面只有一个元素, 而下面由多个元素相邻.
线性表 0个或多个元素组成的有限序列.

补充术语

数据对象 数据元素及其关系的集合, 是数据的一个子集.
抽象数据类型(Abstract Data Type, ADT) 一般是指由用户定义的, 表示应用问题的数学模型, 以及定义在这个模型商店一组操作的总称. (p.s. 这个在后续"树"的那一章的高中部分提到)

1
2
3
4
5
ADT ADTClassName {
    DataObject: // Definition for DataObject
    DataRelationship: // Definition for DataRelaionship
    Operation: // Definition for Operation
} ADT ADTClassName;

其中, 基本操作的定义用:

1
2
3
Operation(ParameterList)
    InitCond: // Description of initial conditions
    OperationRes: // Description of results

算法的定义及特性

p.s. 事实上, 这个部分是高中技术必修一的内容()

5个重要特性

  • 有穷性
  • 确定性
  • 可行性
  • 输入 0个或多个输入
  • 输出 1个或多个输出

时间复杂度的数学定义

若 T(n)T(n) 和 f(n)f(n) 是定义在正整数集合上的两个函数, 则 T(n)=O(f(n))T(n) = O(f(n)) 当且仅当存在正常数 CC 和 n0n_0, 当 n≥n0n \ge n_0 时, 有 T(n)≤Cf(n)T(n) \le Cf(n).