0X2A

848数据结构(一) 基本概念和术语

848数据结构(一) 基本概念和术语
2020-09-01 · 3 min read

基本概念和术语

一些概念

数据元素

数据元素是数据的基本单位.
这里需要注意的是, 数据元素可能包含多个数据项. 比如一本书作为一个数据元素, 它可以由书名, 作者名等数据项组成. 而数据项不再可分.

数据对象

数据对象是性质相同的数据元素的集合, 是数据的子集.
比如, 英文字母可以组成一个数据对象, 所有的整数可能组成一个数据对象.

数据结构

相互之间存在一种或多种特定关系的数据元素集合.
数据结构包含三方面:

  1. 逻辑结构
    强调的是数据的逻辑关系, 和数据如何存储在计算机内部无关.
    常见的逻辑结构包含: 线性结构以及非线性结构
    线性结构主要指线性表(栈 队列 等)
    非线性结构包括:集合、树、图
  2. 存储结构
    指在计算机内部存储的结构, 又称为物理结构.
    常见的存储结构: 顺序存储, 链式存储, 索引存储以及散列存储.
  3. 数据的运算

数据类型

  1. 原子类型
    指值不可再分的数据类型.
  2. 结构类型
    其值可以再分解成若干类型
  3. 抽象数据类型
    ADT. 抽象数据组织以及操作.

算法设计的基本要求

算法重要特征

  1. 有穷性
    算法必须在有穷个步骤内完成
  2. 确定性
    同一个输入 会有相同的输出
  3. 可行性
  4. 输入
    可以有零个或多个输入
  5. 输出

语句的频度和估算时间复杂度

时间复杂度

空间复杂度

易错点

  1. 链式存储不同节点存储空间不一定连续, 但是节点内存储空间肯定是连续的(这不是废话吗 读题啊啊啊)
  2. 像顺序表 哈希表 单链表属于数据结构 同时包含了逻辑结构 物理结构以及运算, 不能单说他是逻辑结构或者物理结构
  3. 逻辑结构可以独立于存储结构, 而存储结构是逻辑结构在计算机上的映射, 所以不能独立于逻辑结构.