数据结构 C++语言版 清华大学第三版 学习笔记

本文主要是介绍数据结构 C++语言版 清华大学第三版 学习笔记，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

绪论

绪论一道冒泡排序拍懵我了，我以为$O(n^2)$ 复杂度的经典冒泡排序没有优化空间了，结果一个bool标识打脸，可以提前终止冒泡，如果已经是按顺序了的数组的话：

 void bubblesort1A(int A[], int n) { //起泡排序算法（版本1A）：0 <= n bool sorted = false; //整体排序标志，首先假定尚未排序 while (!sorted) { //在尚未确认已排序之前，逐行扫描交换 sorted = true; //假定已经排序 for (int i = 1; i < n; i++) { //自左向右逐对检查弼前范围A[0, n)内癿各相邻元素 if (A[i - 1] > A[i]) { //一旦A[i - 1]不A[i]逆序，则 swap(A[i - 1], A[i]); //交换 sorted = false; //因整体排序不能保证，需要清除排序标志 } } n--; //至此末元素必然就位，故可以缩短待排序序列癿有效长度 } } //布尔型标志位sorted，可及时提前退出，而不致总是蛮力地做n - 1趟扫描交换 

看来数据结构，路漫漫其修远兮，吾将上下而求索

算法具备的要素：

1. 输入与输出
2. 基本操作、确定性与可行性
3. 有穷性与正确性
4. 退化与鲁邦性
5. 重用性（便捷的用于其他场合，如冒泡可推广至float和char）

1.4 递归

以下将从递归的基本模式入手，循序渐进地介绍如何选择和应用（线性递归、二分递归和多分支递归等）不同的递归形式，以实现（遍历、分治等）算法策略，以及如何利用递归跟踪和递
推方程等方法分析递归算法的复杂度。

1.4.1 线性递归

算法sum()可能朝着更深一层进行自我调用，且每一递归实例对自身的调用至多一次。于是，
每一层次上至多只有一个实例，且它们构成一个线性的次序关系。此类递归模式因而称作“线性递归”（linear recursion），它也是递归的最基本形式。

  int sum(int A[], int n) { //数组求和算法（线性递归版） if (1 > n) //平凡情况，递归基 return 0; //直接（非逑弻式）计算 else //一般情冴 return sum(A, n - 1) + A[n - 1]; //递归：前n - 1顷和，再累计第n - 1顷 } //O(1)递归深度 = O(1)*(n + 1) = O(n) 

1.4.2 递归分析

整个sum()算法的运行时间为：
(n + 1) X O(3) = O(n)
sum()算法的空间复杂度又是多少呢？在创建了最后一个递归实例（即到达递归基）时，占用的空间量达到最大。准确地说，等于所有递归实例各自所占空间量的总和。
这里每一递归实例所需存放的数据，无非是调用参数（数组A的起始地址和长度n）以及用于累加总和的临时变量。这些数据各自只需常数规模的空间，其总量也应为常数。故此可知，sum()算法的空间复杂度线性正比于其递归的深度，亦即O(n)。

求解$power(2,n)=2^n$
power2(n) = 1 n==0
power2(b) = 2*power2(n-1) else
每层只有一个实例，这是一个线性递归， O(n)的空间复杂度，时间复杂度

优化：
power2(n) =
1　　　　　　　　　　　　n==0
power2(n/2)^2 * 2　　　　　n奇数
power2(n/2) *2　　　　　 　n偶数
（n/2后按二进制展开）
还是线性递归，因为二者只选一条路。但是O(logn)的复杂度

1.4.4递归消除

空间成本 由于递归深度，空间占用往往较大；系统创建、销毁实例需要时间；因而往往写成等价的非递归版本（一般是利用栈结构）

尾递归及消除 线性递归算法中恰好以最后一步操作的形式出现（即所有实例都会终止在这一个递归调用）。称作尾递归tail recursion,这类均可转换为迭代

1.4.5 二分递归

分而治之。

        int mi = (lo + hi) >> 1; //以居中单元为界，将原区间一分为二 return sum(A, lo, mi) + sum(A, mi + 1, hi); //递归对各子数组求和，然后合计 

算法启动后经连续m = log 2 n次递归调用，每一刻活跃的实例不会超过m+1个，m为深度3，到达2^k的任一个递归实例之前，已执行的递归调用总比递归返回多m-k次
因此任意时刻实例总数不会超过m+1，是常数，空间复杂度O(m)即O(logn)，比线性少。
每一次递归中非递归时间是常数，递归实例共2n-1,时间复杂度O(2n-1)即O(n)

必须保证子问题相互独立，可独立求解。否则就会变成递归的斐波那契数列。
$O(2^n)$ 的时间复杂度

1. 借助辅助空间，子问题求解够记录下来（制表策略）
2. 从递归基触发向上推（动态规划）

__int64 fibI(int n){__int64 f=0 , g=1;while(0 < n--){g +=f ; f = g-f;}return f;
}

1.5 抽象数据类型abstract data type , ADT

数据集合和对应操作超脱于具体程序设计语言，催生了面向对象程序设计语言

数据结构大致分为线性结构，半线性结构、非线性结构
线性结构中，按逻辑词语与物理存储地址的对应，区分
向量： 物理存放位置与逻辑次序吻合，逻辑次序也叫秩rank
列表： 采用间接定址的方式通过封装后的位置相互引用
数组，严格对应A0 A1 A2

向量

vector 容量：私有变量_capacity确定，当前实际规模由_size指示
向量中秩为r的元素，对应于内部数组中的_elem[r]，其物理地址为_elem + r

若以复制形式copyFrom()初始化，则采用双倍现有容量来申请空间，O(n)时间（因为要一个一个的复制过去）（共有好几种构造函数方式可选）

需强调的是，由于向量内部含有动态分配的空间，默认的运算符"="不足以支持向量之间的
直接赋值。

（只允许有一种析构函数）O(1)时间
向量中元素可能不是程序语言直接支持的基本类型。所以，向量析构之前应当释放各元素所指的对象，这个由上层调用者负责

动态空间管理

2.4.2 可扩充向量extendable vector

申请更大的B，把A复制过来，再删除A

分摊复杂度，分摊运行时间 与平均运行时间不同，后者称为期望运行时间。前者，比较复杂，具体问题再看。

最坏情况下，考虑不断连续insert，插入到很大很大的n时，共做过log2n次扩容，累计时间2N+4N+…+capacity(n) < 2*n = O(n)
平摊到n次操作，单次操作分摊运行时间O(1)，令人满意

2.4.5缩容

_size/_capacity < 0.25时缩小一半，同上，单次运行确实是O(n)，但是平摊之后变成O(1)。当然，阈值，策略有需求时可以改。

向量重载了A[i]的取值方式， return _elem[i] (其中0<=i < _size) ,取代了get()这种不方便的方式

这篇关于数据结构 C++语言版 清华大学第三版 学习笔记的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---