数据结构 1 绪论

凭借一句话获得图灵奖的Pascal语言之父——Nicklaus Wirth，让他获得图灵奖的这句话就是他提出的著名公式： \[ 程序 = 数据结构 + 算法 \]

基本概念和术语

知识结构图： 数据 ——> 数据元素 ——> 数据项 ——> 数据对象

数据：是对客观事物的符号表示

数据元素(data element)：是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。一个数据元素往往由若干数据项组成。

数据项(Data Item)：是组成数据元素的、有独立含义的、不可分割的最小单位

数据对象(data object)：是性质相同的数据元素的集合

数据结构(Data Structure)：是相互之间存在一种或多种特定关系的数据元素的集合。换句话说，数据结构是带”结构＂的数据元素的集合，“结构”就是指数据元素之间存在的关系。

逻辑结构和物理结构

逻辑结构：数据的逻辑结构是从逻辑关系上描述数据，它与数据的存储无关，是独立于计算机的。因此，数据的逻辑结构可以看作是从具体问题抽象出来的数学模型。数据的逻辑结构有两个要素：一是数据元素；二是关系。

四类基本逻辑结构

• 集合
• 松散结构线性结构：一对一的关系
• 树形结构：一对多关系
• 图状结构：多对多关系

物理结构/存储结构

物理结构：数据的逻辑结构在计算机中(内存)的存储形式。

分为顺序存储结构、链式存储结构、索引存储结构、散列存储结构。

数据类型

数据类型是一个值的集合和定义在值集上的一组操作的总称。

在使用高级程序设计语言编写程序时，必须对程序中出现的每个变量、常量或表达式、C语言中函数的参数、返回值，明确说明它们所属的数据类型。

C语言中：提供int,char,float,double等基本数据类型；数组、结构、共用体、枚举等构造数据类型；还有指针、空（void)类型，用户也可用typedef自己定义数据类型。而另一些常用的数据结构，如栈、队列、树、图等，不能直接用数据类型来表示。

在C语言中，数据类型可以分为两类：

• 原子类型：是不可以再分解的基本类型，包括整型、实型、字符型等
• 结构类型：由若干个类型组合而成，是可以再分解的。例如，整型姿型数据组成的数组。

抽象数据类型(ADT)

是指一个数据模型以及定义在该模型上的一组操作。和数据类型实质上是一个概念

形式化定义: (D, S, P)

• D是数据对象
• S是D上的关系集
• P是对D的基本操作

定义格式
      ADT 抽象数据类型名 {
             数据对象: <数据对象的定义>
             数据关系: <数据关系的定义>
             基本操作: <基本操作的定义>
      } ADT 抽象数据类型  

对图形进行一个缩放n倍scale(G(被操作的图形),n)对图形进行缩放，它当然也会返回一个图形 G'=scale(G,n)返回值要赋值给G 写成scale（&G,n）引用参数以"&"打头，除可提供输入值外，还将返回操作结果。

算法和算法分析

算法

算法定义：解决问题的方法和步骤。在计算机中表现为指令的有限序列。其中每条指令表示一个或多个操作。

算法的描述

自然语言；流程图【NS图、框图】；伪代码(类C语言)；程序设计(C、Java...)

程序与算法

• 程序=数据结构+算法
• 数据结构通过算法来实现操作
• 算法根据数据结构设计程序

算法的特性(确定、有穷、可行、输入、输出)

1. 有穷性：算法在执行有限步骤之后，自动结束而不会出现无限循环，并且每一个步骤都在可接受的时间范围内完成。当然这里的有穷并不是纯数学意义的，而是在实际应用中合理的、可以接受的“边界”。
2. 确定性：算法的每一个步骤都有确定的含义，不会出现二义性(不会有歧义)。
3. 可行性：算法中的所有操作都可以通过已经实现的基本操作运算执行有限次来实现。
4. 输入：一个算法有零个或多个输入。当用函数描述算法时，输入往往是通过形参表示的，在它们被调用时，从主调函数获得输入值。
5. 输出：一个算法有一个或多个输出，它们是算法进行信息加工后得到的结果，无输出的算法没有任何意义。当用函数描述算法时，输出多用返回值或引用类型的形参表示。

算法的设计要求

好的算法应该具有正确性、可读性、健壮性、时间效率高和存储量低的特征。

1. 正确性(Correctness)：能正确的反映问题的需求，能得到正确的答案。

   分以下四个层次：

   • 算法程序没有语法错误；

   • 算法程序对n组输入产生正确的结果；

   • 算法程序对典型、苛刻、有刁难性的几组输入可以产生正确的结果；

   • 算法程序对所有输入产生正确的结果；

   但我们不可能逐一的验证所有的输入，因此算法的正确性在大多数情况下都不可能用程序证明，而是用数学方法证明。所以一般情况下我们把层次3作为算法是否正确的标准。

2. 可读性(Readability)：算法，首先应便于人们理解和相互交流，其次才是机器可执行性。可读性强的算法有助于人们对算法的理解，而难懂的算法易于隐藏错误，且难于调试和修改。

3. 健壮性(Robustness)：当输入的数据非法时，好的算法能适当地做出正确反应或进行相应处理，而不会产生一些莫名其妙的输出结果。【健壮性又名鲁棒性即使用棒子粗鲁地对待他也能做出正确反应或进行相应处理】

4. (高效性)时间效率高和存储量低

算法分析

算法分析的目的是看算法实际是否可行，并在同一问题存在多个算法时可进行性能上的比较，以便从中挑选出比较优的算法。

(时间效率)运行时间的长短、(空间效率)占用内存空间的大小是衡量算法好坏的重要因素。

衡量算法时间效率的方法主要有两类：事后统计法和事前分析估算法。

事后统计法需要先将算法实现，然后测算其时间和空间开销。这种方法的缺陷很显然，

一是必须把算法转换成可执行的程序，

二是时空开销的测算结果依赖于计算机的软硬件等环境因素，这容易掩盖算法本身的优劣。

三是算法的测试数据设计困难，并且程序的运行时间往往还与测试数据的规模有很大关系，效率高的算法在小的测试数据面前往往得不到体现。比如10个数字的排序，不管用什么算法，差异几乎是零。而如果有一百万个随机数字排序，那不同算法的差异就非常大了。那么我们为了比较算法，到底用多少数据来测试，这是很难判断的问题。

所以我们通常采用事前分析估算法。

一个算法的执行时间大致上等于其所有语句执行时间的总和，而语句的执行时间则为该条语句的重复执行次数和执行一次所需时间的乘积。

一条语句的重复执行次数称作语句频度(FrequencyCount)。

语句的执行要由源程序经编译程序翻译成目标代码，目标代码经装配再执行，因此语句执行一次实际所需的具体时间是与机器的软、硬件环境（如机器速度、编译程序质量等）密切相关的。

设每条语句执行一次所需的时间均是单位时间，则一个算法的执行时间可用该算法中所有语句频度之和来度量。所谓的算法分析并非精确统计算法实际执行所需时间，而是针对算法中语句的执行次数做出估计，从中得到算法执行时间的信息。

for(int i = 0 ; i < n ; i++)     //<- 从 0 到 n，执行 n+1 次
{
    a++;                         //<- 从 0 到 n-1，执行 n 次
}
/*可以看到，这段程序中仅有 2 行代码，其中：
for 循环从 i 的值为 0 一直逐增至 n（注意，循环退出的时候 i 值为 n），因此 for 循环语句执行了 n+1 次；
而循环内部仅有一条语句，a++ 从 i 的值为 0 就开始执行，i 的值每增 1 该语句就执行一次，一直到 i 的值为 n-1，因此，a++ 语句一共执行了 n 次。
因此，整段代码中所有语句共执行了 (n+1)+n 次，即 2n+1 次。数据结构中，每条语句的执行次数，又被称为该语句的频度。整段代码的总执行次数，即整段代码的频度。
*/

渐进时间复杂度

对于稍微复杂一些的算法，计算出算法中所有语句的频度通常是比较困难的。通常，算法的执行时间是随问题规模增长而增长的，因此对算法的评价通常只需考虑其随问题规模增长的趋势。

这种情况下，我们只需要考虑当问题规模充分大时，算法中基本语句的执行次数在渐近意义下的阶。

image-20231117170354264

分析算法时间复杂度的基本方法

1. 找出语句频度最大的那条语句作为基本语句；

2. 计算基本语句的频度，得到问题规模n的某一个函数；

3. 取其数量级用O表示

//例子
i = 1;
while(i<=n)
    i = i*2;

时间复杂度：\(O(log_2n)\)

最好、最坏和平均时间复杂度

最坏时间复杂度是指在最坏情况下算法的的复杂度；

最好时间复杂度是指在最好情况下算法的的复杂度；

平均时间复杂度是指算法在所有可能情况下，按照输入实例以等概率出现时，算法计算量的加权平均值。

通常考虑最坏和平均，但有时平均比较难计算，所以只考虑最坏时间复杂度，最坏情况运行时间是一种保证，那就是运行时间不会再坏了。

image-20231117171824861

算法的空间复杂度

和时间复杂度类似，一个算法的空间复杂度，也常用大 O 记法表示。

要知道每一个算法所编写的程序，运行过程中都需要占用大小不等的存储空间，例如：

• 程序代码本身所占用的存储空间；
• 程序中如果需要输入输出数据，也会占用一定的存储空间；
• 程序在运行过程中，可能还需要临时申请更多的存储空间。

首先，程序自身所占用的存储空间取决于其包含的代码量，如果要压缩这部分存储空间，就要求我们在实现功能的同时，尽可能编写足够短的代码。

程序运行过程中输入输出的数据，往往由要解决的问题而定，即便所用算法不同，程序输入输出所占用的存储空间也是相近的。

事实上，对算法的空间复杂度影响最大的，往往是程序运行过程中所申请的临时存储空间。不同的算法所编写出的程序，其运行时申请的临时存储空间通常会有较大不同。

如果程序所占用的存储空间和输入值无关，则该程序的空间复杂度就为 O(1)；反之，如果有关，则需要进一步判断它们之间的关系：

• 如果随着输入值 n 的增大，程序申请的临时空间成线性增长，则程序的空间复杂度用 O(n) 表示;
• 如果随着输入值 n 的增大，程序申请的临时空间成 n2 关系增长，则程序的空间复杂度用 O(n2) 表示；
• 如果随着输入值 n 的增大，程序申请的临时空间成 n3 关系增长，则程序的空间复杂度用 O(n3) 表示；
• 等等。

在多数场景中，一个好的算法往往更注重的是时间复杂度的比较，而空间复杂度只要在一个合理的范围内就可以。