数据与结构算法课堂笔记

绪论（8月30日/2021）

1️⃣ 数据项

用于描述数据元素，他是数据的最小单位。

2️⃣ 数据元素

是数据（集合）中的一个个体，他是数据的基本单位。

3️⃣ 数据对象

具有相同性质的若干个数据元素的集合。

4️⃣ 数据结构

指带结构的元素的数据元素的集合

5️⃣ 元素之间的关系

相邻关系和不相邻关系**。

6️⃣ 逻辑结构（面向用户）

表格、二元组（表示为B=(D,R)D是数据元素的集合，R是数据关系集合）、图形

7️⃣ 序偶

<x,y>表示x,y是有向的，序偶(x,y)表示x,y是无向的                                                    序偶<x,y>  x为第一元素 y为第二元素 x为y的前驱元素 y为x的前驱元素 若某个元素没有前驱元素，则该元素被称为开始元素；若某个元素没有前驱元素，则该元素被称为终端元素

8️⃣ 存储结构（面向程序员）

1）结构体数组 特点

所有元素占用一整块内存空间 物理和逻辑相邻关系对应

2）链表 特点

一个逻辑元素用一个结点存储，每个结点单独分配，所有结点的地址不一定是连续的 用指针来表示逻辑关系

9️⃣ 同一逻辑结构可以对应多种存储结构

同样的运算，在不同的存储结构中，其实现过程是不同的

1️⃣0️⃣ 逻辑结构类型

1）集合

元素之间关系:无

2）线性结构

元素之间关系:一对一

3）树形结构

元素之间关系:一对多

4）图形结构

元素之间关系:多对多

1️⃣1️⃣ 存储结构类型

1）顺序存储结构的特点

所有元素占用一整块内存空间，逻辑上相邻的元素物理上也相邻。

2）链式存储结构的特点

一个逻辑元素，用一个节点存储，每个节点单独分配，所有节点的地址不一定是连续的，用指针来表示逻辑关系。

3）索引存储结构

4）哈希存储结构

1、 算法：通常把基于存储结构的运算实现的步骤或过程称为算法。
（1）算法的五个重要的特性
有穷性（2）确定性（3）可行性（4）有输入（5）有输出
2、 一个算法是由控制结构（顺序、分支、循环）和原操作（指固有数据类型的操作，如+、-、、/等）构成的。算法的执行时间取决于两者的综合效果。
3、 算法所有原操作的执行次数（也称为频度），他是问题规模n的函数，用T(N)表示。
算法执行时间大致=原操作所需要的时间T（n)。所以T(N）与算法的执行时间成正比。为此用T（n)表示算法的执行时间。
4、