一.绪论

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)按数量级递增顺序与时间复杂度相同。