数据结构学习笔记准备篇（学习数据结构--第一章）

第一章：绪论

1.基本概念以及术语：

• 数据：信息的载体,是 描述客观事物 属性的数、字符及所有能输入到计算机中并被计算机程序识别和处理的 符号的集合
• 数据对象：具有相同性质的数据元素的集合,是数据的一个子集
• 数据元素：数据的基本单位 ,通常作为个整体进行考虑和处理
• 数据项：构成数据元素的不可分割的 最小单位

数据包含数据对象，数据元素构成数据对象。

所有人的身份信息就可以作为数据对象，每一个人的身份信息就可以作为数据元素，身份信息的姓名、编号就可以作为数据项。

1.1数据

数据类型（集合 操作）

• 原子类型：值集合 操作（int、char、float等）
• 结构类型：结构的集合 操作（list、map、set等）
• 抽象数据类型ADT：数据对象 数据关系 操作（所有可以抽象出的模型）

1.2结构

结构： 数据不是孤立存在的，他们存在着某种关系，这种相互关系我们叫做 结构 。

1.3数据结构

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

1.4数据结构三要素

• 逻辑结构
• 物理结构（存储结构）
• 数据的运算

1.5逻辑结构

在这里插入图片描述

1.6物理结构（存储结构）

在这里插入图片描述

1.7数据的运算

运算包括运算的 定义 和 实现 ，运算的定义针对 逻辑结构，运算的实现针对 存储结构 。

在这里插入图片描述

1.8本节回顾

在这里插入图片描述

2.算法&算法评价

2.1算法

算法： 对特定问题求解的一种描述，它是指令的有限序列，其中的每条指令表示一个或多个操作。

2.2算法特性

• 有穷性：一个算法必须在执行有穷步后结束，并且每步操作都在有穷时间内完成。
• 可行性：一个算法必须是可行的，算法中描述的操作是可以实现的。
• 确定性：算法中每一条指令、每一条语句都必须有确定的含义，同样的输入，必须要得到同样的输出。
• 输入：一个算法必须要有零个或者多个输入。
• 输出：一个算法必须要有零个或者多个输出。

2.2算法 VS 程序

算法（指导者）：解决问题的一个方法或者过程，考虑如何将输入转换成输出，一个问题可以有很多个算法。

程序（实施者）：程序是某种设计语言对算法的具体实现。

有穷性：算法必须是有穷的，程序可以是无穷的。

正确性：算法必须是正确的，程序可以是错误的。

描述方法：算法可以用伪代码、程序语言等描述，程序只能用程序语言编写并可以运行。

2.3算法效率的度量

//例如int sum=0;if(n!=0){ for(int i=1;i<=n;i ){ sum =i; }}如果n==0，T(n)=1=O(1),如果n!=0,T(n)=1 n=O(n)

在这里插入图片描述

基本运算频度：最深层循环所执行的时间复杂度。

常见时间复杂度

在这里插入图片描述

O(1)<O(log~2~^n^)<O(n)<O(nlog~2~^n^)<O(n^2^)<O(n^3^)<O(2^n^)<O(n!)<O(n^n^)

2.4本节回顾

关于数据结构的知识，持续更新中，欢迎关注公众号理木客

,