第一章 数据结构绪论 第二章 算法

基本概念和术语

数据：是客观描述事物的符号，是计算机中可操作的对象。是可以被计算机识别，并可以输入计算机处理的符号集合。数据可以包括整型、实体型、声音、图像、视频等。

数据元素：是组成数据的，具有一定意义的基本单位。
举个例子：在人类中，人就是数据元素。 在车类中，svn，小轿车就是车类的数据元素。

数据项：一个数据元素可以由多个数据项组成。比如车这个数据元素，其中的轮胎，方向盘，发动机这些数据项。数据项是数据不可分割的最小部分。

数据对象:是性质相同的数据元素的集合。是数据的子集。

数据结构:是相互之间存在一种或者多种特定关系的数据元素的集合。

由大到小：

数据 ---> 数据对象 ---> 数据元素 ---> 数据项

逻辑结构与物理结构

逻辑结构：指的是数据对象中数据元素之间相互关系

1. 集合结构：该结构中的数据元素同属于一个集合，各个数据元素之间关系都是平等的。
2. 线性结构：该结构中的数据元素关系是一对一的。
3. 树形结构：该结构中的数据元素存在一种一对多的层次关系。
4. 图形结构：该结构中的数据元素是多对多的关系。

物理结构：指的是逻辑结构在计算机中的存储形式

1. 顺序存储结构
2. 链接存储结构

算法

设计算法要尽量满足时间效率高和存储量第的需求

算法的时间复杂度

1. 常数阶 O{1}

int i = 10; //执行一次
int j = i + 1; //执行一次

2. 线性阶 O{n}

int i ;
for (i=0 ;i<n;i++){
        //时间复杂度为O{1}的步骤序列
}

3. 平方阶 O{n ² }
4. 对数阶 O{logn}
5. nlogn阶 O{nlogn}
6. 立方阶O{n³ }
7. 指数阶 O{2ⁿ}

常用的时间复杂度所耗费的时间从小到大依次是：

O{1} < O{logn} < O{n} < O{nlogn} < O{n ² } < O{n³ } < O{2ⁿ}