数据结构基本概念
基本概念和术语
- 数据：信息的载体，描述客观事物属性，如数字、字符、所有能输入计算机中识别处理的符号集合
- 数据元素：数据基本单位（数据表中的一行），由数据项组成
- 数据项：数据元素不可分割的最小单位（理解成属性）
- 数据对象：数据元素的集合，数据的子集
- 数据类型：值的集合和定义在此集合上的一组操作的总称
- 原子类型：值不可再分
- 结构类型：值可以再分
- 抽象数据类型：抽象数据组织和操作（即结构和运算）
- 数据结构：存在关系的数据元素的集合
- 数据指数据元素
- 结构指数据元素之间的关系
- 定义数据结构需要数据对象、结构关系、操作运算
数据结构的三要素
- 逻辑结构：独立于计算机（物理存储），从逻辑上描述数据的关系，分为线性结构和非线性结构
- 线性结构（一对一的关系）
- 一般线性表
- 受限线性表：栈、队列、串
- 线性表推广：数组
- 非线性结构
- 集合（属于同集合的关系）
- 树形结构（一对多的关系）：一般树、二叉树
- 图状结构（多对多的关系）：有向图、无向图
- 线性结构（一对一的关系）
- 存储结构：计算机中对数据和关系的表示
- 顺序存储：逻辑相邻的元素在物理上也相邻存储
- 优点：可随机存取、节约空间
- 缺点：只能使用相邻的整块存储单元，容易产生碎片
- 链式存储：逻辑相邻的元素在物理上可不相邻
- 优点：不会出现碎片，充分利用所有存储单元
- 缺点：引入额外指针空间开销、只能顺序存取
- 索引存储：存储信息的同时，维护一个索引表（表的每个索引项包含关键字和地址）
- 优点：搜索速度快
- 缺点：索引表占用额外的存储空间，增删元素时维护索引表需要额外的开销
- 散列存储：根据关键字直接算出存储地址，又叫哈希(Hash)存储
- 优点：检索增删操作快
- 缺点：如果散列函数不好，可能出现大量的冲突，从而增加时间空间开销
- 顺序存储：逻辑相邻的元素在物理上也相邻存储
- 数据元素：包括运算定义和运算实现
- 定义：针对逻辑结构，指出运算的功能效果
- 实现：针对存储结构，指出运算的操作步骤