一.绪论
1.数据结构基本概念
1.基本术语:
数据元素:数据基本单位。
数据项:众多数据项组成一个数据元素,不可分割的最小单位。
数据对象:具有相同性质的数据元素集合。
数据结构:相互之间存在一种或多种特定关系的数据元素集合。
2.数据类型:一个值的集合和定义在此集合上的一组操作的总和。
原子类型:其值不可再分的数据类型(bool,int...)
结构类型:其值可以在分解为若干成分的数据类型(结构体)
抽象数据结构(ADT):只关心逻辑结构
2.数据结构三要素(重点)
1.数据的逻辑结构分类:(重点,图背过)
线性结构:一对一。
树形结构:一对多。
网状结构:多对多。
2.数据的物理结构:
顺序结构:逻辑地址相邻元素存储在的物理地址相邻的位置。(数组)
链式结构:逻辑位置相邻物理地址用指针链接在一起。(链表)
索引结构:创立一张索引表,其中每项称为索引项,索引项形式关键字、地址。
散列结构:哈希存储。(后面会解释)
关于上述四种物理结构理解点:
(1 顺序存储各元素物理上必须连续,非顺序存储各元素物理上可以不连续。
(2 数据的存储结构会影响存储空间分配的方便程度。
(3 数据的存储结构会影响数据的运算速度。
3.数据运算:
数据运算的定义是针对逻辑结构,指出运算功能;数据运算的实现是针对存储结构,指出运算的具体步骤。
3.算法及算法评价
1.基础概念
算法五大特征:有穷性,确定性,可行性,输入,输出。
算法四个目标:正确性,可读性,健壮性,高效率和低存储量需求。
2.算法度量
时间复杂度:(考试会考常见的插入和排序算法的时间复杂度,只需要背过即可)
最好,最坏,平均。(一般衡量算法看最坏)
一般看最高阶来确定。
时间复杂度T(n)按数量级递增顺序为:
常数阶 | 对数阶 | 线性阶 | 线性对数阶 | 平方阶 | 立方阶 | K次方阶 | 指数阶 | 阶乘阶 |
|
O(1) | O(log2n) | O(n) | O(nlog2n) | O(n2) | O(n3) | O(nk) | O(2n) | O(n!) | O(n的n次方) |
空间复杂度:
只分析辅助空间。
O(1)表示辅助空间为常量。
空间复杂度T(n)按数量级递增顺序与时间复杂度相同。