【数据结构】数据结构-拓冰建站

本文是基于中国MOOC平台上，华中科技大学的《数据结构》课程和浙江大学的《数据结构》课程所作的一篇课程笔记，便于后期讲行系统性查阅和复习。

从个人角度出发，两个课程的讲解都有点不太易懂，好在多处可以互补，搭配进行学习还可以。

一、基础概念

1.1 什么是数据结构

1.1.1 解决问题方法的效率，与什么有关？

解决问题方法的效率，跟数据的组织方式有关。

解决问题方法的效率，跟空间的利用效率有关。

解决问题方法的效率，跟算法的巧妙程度有关。

引入案例：如何在书架上摆放书架？

分析案例：图书的摆放要使得两个操作方便实行

1.新书怎么插入？

2.怎么找到某本指定的书？

算法一：随便放。

操作1有空就放，一步到位。操作2需要遍历书架，复杂度高。

算法二：按照书名的拼音字母顺序排放。

操作1每插入一本新书就要把后面的书进行调整，复杂度高。操作2二分查找。

算法三：分而治之法，书架按块放不同类别的书，每一类里按拼音字母顺序排放。

操作1先定类别，二分查找位置，移出空位。操作2先定类别，再二分查找。

对比之下，算法三更优。

优化：空间如何分配？类别应该分多细？

解决问题方法的效率，跟数据的组织方式有关。

引入案例：写程序实现一个函数PrintN，使得传入一个正整数为N的参数后，能顺序打印从1到N的全部正整数。

算法一：for循环
void PrintN(int N) {for (int i = 1; i < N + 1; i++) {printf("%d\n", i);}return;
}
算法二：递归函数
void PrintN(int N) {if (N) {PrintN(N - 1);printf("%d\n", N);}return;
}
实际上，在测试代码过程中，N的取值有10、100、1000、10000，而在10、100、1000时两种代码均能跑通。在10000时，递归函数出现了错误，原因是内存不足。

解决问题方法的效率，跟空间的利用效率有关。

引入案例：写程序计算给定多项式在给定点x处的值。

算法一：傻瓜法
double f(int n, double a[], double x) {int i;double p = a[0];for (i = 1; i <= n; i++) p += (a[i] * pow(x, i));return p;
}
算法二：秦久韶算法
double f(int n, double a[], double x) {int i;double p = a[n];for (i = n; i >0; i--) p = a[i - 1] + x * p;return p；
}
对比算法：算法二的运行时间更短。

解决问题方法的效率，跟算法的巧妙程度有关。

1.1.2 什么是数据结构？

数据结构是数据对象在计算机中的组织方式。

（数据对象的逻辑结构，数据对象在计算机中的物理存储结构）

•数据对象必定与一系列加在其上操作相关联

•实现这些操作所用的方法就是算法。

抽象数据类型

•抽象数据类型是对数据的逻辑描述，而数据结构是对数据的物理描述。抽象数据类型定义了数据的操作和语义，而数据结构实现了这些操作和语义。因此，可以说抽象数据类型是数据结构的一种实现方式。

•数据类型：数据对象集+数据集合相关联的操作集

•抽象：描述数据类型的方法不依赖于具体实现。

（与存放数据的机器无关，与数据存储的物理结构无关，与实现操作的算法编程语言无关）

（只描述数据对象集和相关操作集”是什么“，并不涉及”如何做到“的问题）

1.2 什么是算法

1.2.1 算法的定义

•算法

•一个有限指令集

•接收一些输入（有些情况不需要输入），产生输出

•有穷性：一定在有限步骤之后终止

•确定性：每一条指令必须有充分明确的目标，不可以有歧义

•可行性：每一条指令必须计算机能处理的范围之内

•伪代码：算法描述应不依赖于任何一种计算机语言以及具体的实现手段

1.2.2 什么是好的算法

•衡量好算法的指标：空间复杂度S(n)，时间复杂度T(n)。

•在分析一般算法的效率时，经常关注下面两种复杂度：

1.最坏情况复杂度： $T_{_{_{worst}}}(n)$

2.平均复杂度： $T_{_{avg}}(n)$

通常 $T_{avg}(n)\leq T_{worst}(n)$ ，我们更常用 $T_{_{_{worst}}}(n)$ 。

1.2.3 复杂度的渐进表示

•T(n)=O(f(n))最坏情况复杂度

表示存在常数C>0，n0>0，使得n>=n0时有 $T(n)\leq C*f(n)$

•T(n)=Ω(g(n))最好情况复杂度

表示存在常数C>0，n0>0，使得n>=n0时有 $T(n)\geq C*g(n)$

•T(n)=Θ(h(n))平均复杂度

表示同时有(n)=O(h(n))和T(n)=Ω(h(n))

复杂度分析小窍门

•若两段算法分别有复杂度 $T_{1}(n)=O(f_{1}(n))$ 和 $T_{2}(n)=O(f_{2}(n))$ ，则

算法相接： $T_{1}(n)+T_{2}(n)=max(O(f_{1}(n)),O(f_{2}(n)))$

算法嵌套： $T_{1}(n)\times T_{2}(n)=O(f_{1}(n)\times f_{2}(n))$

•若T(n)是关于n的k阶多项式，那么 $T(n)=\circleddash (n^{k})$

•一个for循环的时间复杂度=循环次数*循环体代码复杂度

•if-else语句的时间复杂度=max{if的条件判断复杂度，if分支的复杂度，else分支的复杂度}

1.3 应用实例

1.3.1 最大子列和问题

问题：给定N个整数的序列{ $A_{1},A_{2},...,A_{N}$ }，求函数f(i,j)=max{0, $\sum_{k=i}^{j}A_{k}$ }的最大值。

算法一：暴力破解（三个嵌套for循环，复杂度 $N^{3}$ ， $T(N)=O(N^{^{3}})$ ）
int MaxSubseqSum1(int A[], int N) {int ThisSum=0, MaxSum = 0;int i, j, k;for (i = 0; i < N; i++) {for (j = i; j < N; j++) {for (k = i; k <= j; k++) {ThisSum += A[k];}if (ThisSum > MaxSum) {MaxSum = ThisSum;}}}return MaxSum;
}
算法二：暴力破解改良版（两个嵌套for循环，复杂度 $N^{2}$ ， $T(N)=O(N^{^{2}})$ ）
int MaxSubseqSum1(int A[], int N) {int ThisSum=0, MaxSum = 0;int i, j, k;for (i = 0; i < N; i++) {for (j = i; j < N; j++) {ThisSum += A[j];if (ThisSum > MaxSum) {MaxSum = ThisSum;}}}return MaxSum;
}
算法三：分而治之（）

思想上，将大的问题划分为小的块，逐层划分到最小单位。行动上，从最小单位逐层解决问题，直到解决问题。