数据结构基本概念
数据结构基本概念
基本概念
- 数据是信息的载体，表现为能被计算机识别和处理的符号集合。
- 数据元素是数据的基本单位，用来描述个体。
- 数据项是构成数据元素的不可分割的最小单位。数据项可理解成个体的各项属性。
- 数据对象是相同性质数据元素的集合，即个体的集合。数据对象是数据的一个子集。
- 数据结构是相互之间存在一种或多种特定关系的数据元素的集合。
例如，要开发班级教务系统，则一个班级中的每个学生信息（个体）都是一个数据元素，每个学生信息包括学生的姓名、年龄等各种属性，这些属性是数据项。表示该班级的所有学生信息的集合即为数据对象。把这些数据对象组织起来并表示它们之间的关系，再加上相关的操作，即为数据结构。可以用一张表组织起来，或者用图表示，或者用树表示，等等。
综上所述，还能得到以下几点：
- 相同的数据元素，通过描述数据元素间不同的关系，可以组成不同的数据结构；
- 不同的数据元素，通过描述数据元素间相同的关系，可以组成相同的数据结构。
数据结构三要素
-
数据的逻辑结构
逻辑结构表示数据间的逻辑关系。包括：
- 集合 同属一个集合
- 线性结构 一对一
- 树形结构 一对多
- 图状结构 多对多
-
数据的物理结构（存储结构）
是数据结构在计算机中的表示。既要存储数据元素，又要存储它们之间的关系。
物理结构会影响存储空间分配的方便程度以及数据运算的速度。
物理结构包括：
-
顺序存储
连续存储，逻辑上相邻，物理上也相邻。
-
非顺序存储
- 链式存储
- 索引存储，建立索引表
- 散列存储，又称哈希存储
-
-
数据的运算
- 运算的定义是针对逻辑结构的
- 运算的实现是针对物理结构的
数据类型
数据类型是高级编程语言概念，是一个值的集合和定义在此集合上的一组操作的总称，如整型变量，实型变量，数组，结构体等。每个数据都属于某种数据类型。
抽象是抽取出实际问题的本质，抽象数据类型是由用户定义，表示具体的应用问题的模型，以及相应的操作的总称。
-
原子类型
如年龄，值不可再分；
-
结构类型
如设置学生结构体，分为姓名、年龄等等；
-
抽象数据类型
三元组（数据对象、数据关系、基本操作集）
特别地，抽象数据类型构成了一个完整的数据结构。
算法及评价
基本概念
算法是对特定问题求解步骤的一种描述，是指令的有限序列。
算法的重要特性（必要条件）：
- 有穷性
- 确定性
- 可行性
- 输入 0个以上
- 输出 1个以上
”好“的算法的目标：
- 正确性
- 可读性
- 健壮性
- 高效率与低存储量需求
算法度量
时间复杂度
加法公式： $$ T(n)=T_1(n)+T_2(n)=O(f(n))+O(g(n))=O(max(f(x),g(x))) $$ 乘法公式： $$ T(n)=T_1(n)\times T_2(n)=O(f(n))\times O(g(n))=O(f(x)\times g(x)) $$ 渐进时间复杂度：
从左至右依次为常数阶、对数阶、线性阶、线性对数阶、K次方阶、指数阶。 $$ O(1)<O(log_2n)<O(n)<O(nlog_2n)<O(n^2)<O(n^3)<O(2^n)<O(n!)<O(n^n) $$
空间复杂度
算法原地工作指的是辅助空间为常量，即$O(1)$。
