数据结构与算法（1）

一：文章总体结构内容解读

二：绪论

1.1研究：

1.范围

数据结构是一门研究非数值计算的程序设计中计算机的操作对象以及它们之间的关系和操作的学科；

2.计算机解决问题步骤：

1.2基本概念和术语：

1.数据、数据元素、数据项和数据对象

例：

【注意】：

数据元素与数据关系：是集合的个体；
数据对象与数据关系：集合的子集；

2.数据结构：

<1>带结构的数据元素集合:

数据元素不是孤立存在的，它们之间存在某种关系，数据元素相互之间的关系称为结构；
是指相互之间存在一种或多种特定关系的数据元素集合；

<2>包括三方面内容：

数据元素之间的逻辑关系，也称逻辑结构；
数据元素及其关系在计算机内存中的表示（又称映像），称为数据结构的物理结构或数据的存储结构；
数据的运算和实现，即对数据元素可以施加的操作以及这些操作在相应的存储结构上实现；

<3>逻辑结构与物理结构：

(1)逻辑结构：

概念
- 描述数据元素之间的逻辑关系；
- 与数据的存储无关，独立于计算机；
- 是从具体问题抽象出来的数学模型；
分类：

(2)物理结构（存储结构）：

概念：数据元素及其关系在计算机存储器中的结构（存储方式）
两者关系：
- 存储结构是逻辑关系的映像与元素本身的映像；
- 逻辑结构是数据结构的抽象，存储结构是数据结构的实现；
- 两者综合起来建立数据元素之间的结构关系；
分类:

3.数据类型和抽象数据类型;

<1>数据类型

（1）定义：是一组性质相同的值的集合以及定义于这个值集合上的一组操作总称。

数据类型=值的集合+值集合上的一组操作；

（2）作用：

约束变量或常量的取值范围；
约束变量或常量的操作。

<2>抽象数据类型（ADT）

（1）概念：指一个数学模型以及定义在此数学模型上一组操作。

（2）形式定义：

（3）基本操作定义的格式：

基本操作名（参数表）
初始条件：<初始条件描述>
操作结果：<操作结果描述>

【说明】

参数表：赋值参数只为操作提供输入值。

引用参数以&打头，除可提供输入值外，还将返回操作结果。

初始条件：操作执行之前数据结构和参数应满足的条件。（不满足返回相应错误信息；为空则省略）

（4）抽象数据类型=数据的逻辑结构+抽象运算（运算功能描述）

（5）Circle例：

1.3 算法和算法分析：

<1>算法：

（1）定义：对特定问题求解方法和步骤的一种描述，它是指令的有限序列。其中每个指令表示一个或多个操作。

（2）描述：

（3）算法与程序：

算法：解决问题的一种方法或一个过程，考虑如何将输入转换成输出，一个问题可以有多种算法；
程序：是用某种程序设计语言对算法的具体实现；
两者关系：程序=数据结构+算法
- 数据结构通过算法实现操作；
- 算法根据数据结构设计程序；

（4）五大特性：

有穷性：一个算法必须总是在执行有限步骤后结束，且每一步都在有限时间内完成；
确定性：算法中每一条指令必须有确切的含义，无二义性，在任何条件下，只有唯一一条路径，即对于相同的输入只能得到相同的输出；
可行性：算法是可执行的，算法描述的操作可以通过已经实现的基本操作执行有限次实现；
输入/出:零个或多个输入/一个或多个输出；

（5）设计要求：

正确性
可读性
健壮性（鲁棒性）：
- 输入非法数据时，算法恰当的做出反应或进行相应处理；
- 出错时，返回一个表示错误或错误性质值；
高效性

<2>算法分析：

（1）算法效率：

时间效率：算法所消耗的时间；
空间效率：算法执行过程中耗费的存储空间；

【注意】时间效率与空间效率有时候是矛盾的；

（2）算法时间复杂度：

最坏时间复杂度：最坏情况下，算法时间复杂度；
平均时间复杂度：所有可能输入实例在等概率出现的情况下，算法的期望运行时间；
最好时间复杂度：指最好情况下，算法时间复杂度；

【注】一般总是考虑最坏情况下时间复杂度，以保证算法的运行时间不会比它更长；

加法与乘法法则：
- 意义：对于复杂算法，可以分成几个容易的估算部分，利用大O加法法则和乘法法则，计算时间复杂度；
- 加法法则：
  
  T(n)=T1(n)+T2(n)=O(f(n))+O(g(n))=O(max(f(n),g(n)))
- 乘法法则：
  
  T(n)=T1(n)*T2(n)=O(f(n)) * O(g(n))=O(f(n)*g(n))

（3）渐进时间复杂度：

算法运行时间=∑ 每条语句的执行次数（或语句频度） X 该语句执行一次所需的时间；
渐进时间复杂度【T(n)=O(f(n))】意义：随着n增大，算法执行时间的增长率和f（n）增长率相同；
例：

for(i=1;i<=n;i++)   //执行n次，但得多判断一次              //n+1次for(j=1;j<=n;j++){                                 //n(n+1)c[i][j]=0;                                     //n*nfor(k=0;k<n;k++)                               //n*n*(n+1)c[i][j]=c[i][j]+a[i]                       //n*n*n}

所以所耗费时间：算法的渐进时间复杂度T（n）=O（n^3）