ClancyCC

Walk in your own Time Zone 走在你自己的时区里 Now York is 3 hours ahead of California, 纽约时间比加州早三个小时, but it does not make California slow. 但加州并没有变慢。 Someone graduated at the age of 22, 有的人22岁就毕业了， but waited 5 years before securing a good job. 但等了五年才找到好的工作。 Someone became a CEO at 25, 有人25岁就当上了CEO， but died at 50. 却在50岁去世。 While another became a CEO at 50, 也有人直到50岁才当上CEO， and lived to 90. 然后活到90岁。 Someone is still single, 有些人依然单身， while someone else got married. 同时也有人已婚。 Obama retires at 55, 奥巴马55岁退休， b ...

所有的学习资料，欢迎评论！ https://drive.google.com/drive/folders/1EYcBGkrwLLOC-i3wcilVLOx-1zK5_Ys3?usp=sharing

8.1 基本概念 自然排序：输入数据越有序，排序的速度越快的排序方法。 内存排序：排序时只用到内存没有用到外存 串行排序：单个处理器，而非多个同时进行 比较排序：用比较的方法 8.2 插入排序 8.2.1 直接插入排序 8.2.2 二分插入排序 8.2.3 希尔排序：不稳定 8.3 交换排序 8.3.1 冒泡排序 n个记录，总共需要n-1趟 第m趟需要比较n-m次 小改进，如果某一趟没有发生交换，说明已经排序完毕。 8.3.2 快速排序 升级快速排序：不用单独开辟存放子表的空间，但是因为递归需要建立栈 ①每一趟的子表的形成是采用从两头向中间交替式逼近法; ②由于每趟中对各子表的操作都相似，可采用递归算法。 划分元素的选取是影响时间性能的关键 输入数据次序越乱，所选划分元素值的随机性越好，排序速度越快，快速排序不是自然排序方法。 改变划分元素的选取方法，至多只能改变算法平均情况的下的时间性能，无法改变最坏情况下的时间性能。即最坏情况下，快速排序的时间复杂性总是O(n2) 8.4 选择排序 如何从无序数列生成堆呢？ 单结点的二叉树是 ...

7.1 查找的基本概念 查找表是由同一类型的数据元素（或记录）构成的集合。由于“集合”中的数据元素之间存在着松散的关系，因此查找表是一种应用灵便的结构。 **查找：**根据给定的某个值，在查找表中确定一个其关键字等于给定值的数据元素或(记录) 7.2 线性表的查找 7.2.1 顺序查找 时间复杂度:O(n) 查找成功时的平均查找长度,设表中各记录查找概率相等ASL.(n)=(1+2+… +n)/n =(n+1)/2 空间复杂度:一个辅助空间——O(1); 1、记录的查找概率不相等时如何提高查找效率? 查找表存储记录原则——按查找概率高低存储: 1)查找概率越高，比较次数越少; 2)查找概率越低，比较次数较多。 2、记录的查找概率无法测定时如何提高查找效率? 方法——按查找概率动态调整记录顺序:1)在每个记录中设一个访问频度域; 2)始终保持记录按非递增有序的次序排列;3)每次查找后均将刚查到的记录直接移至表头。 优点:算法简单，逻辑次序无要求，且不同存储结构均适用。 缺点:ASL太长，时间效率太低。 7.2.2 折半查找，二分查找 折半查找优点:效率比顺序 ...

6.5 图的遍历 从已给的连通图中某一顶点出发，沿着一些边访遍图中所有的顶点，且使每个顶点仅被访问一次，就叫做图的遍历，它是图的基本运算。 6.5.1 深度优先遍历DFS：一条道走到黑，不行再退回 如果对非连通图进行深度优先遍历，只需要在遍历某一个连通分量后，在没有访问的结点任取一个开始遍历即可。 6.5.2 广度优先遍历BFS 利用一个队列，从起点开始，每次出队时，把出队元素所有未访问过的邻接点加入队列，直到队列为空。（其实DFS的递归也同样利用了栈） 6.6 图的应用 最小生成树Minimum Spanning Tree 最小生成树:给定一个无向网络在该网的所有生成树中，使得各边权值之和最小的那棵生成树称为该网的最小生成树，也叫最小代价生成树。 最短路径 一、单源最短路径—用Dijkstra(迪杰斯特拉）算法：一次性算出从起点到其他所有点的最短路径 二、所有顶点间的最短路径—用Floyd(弗洛伊德）算法 有向无环图 检测AOV网中是否存在环方法: 对有向图构造其顶点的拓扑有序序列，若网中所有顶点都在它的拓扑有序序列中，则该AO ...

6.1 图的定义和基本术语 **稀疏图:**有很少边或弧的图(e<nlogn) 。记为TD(v)稠密图:有较多边或弧的图。 **网:**边/弧带权的图。 **邻接:**有边/弧相连的两个顶点之间的关系。(圆括号表示无序，尖括号表示有序) 存在(v_i, v_j)，则称vi和vj互为邻接点; 存在<v_i; v_j>，则称vi邻接到vj,vj邻接于vi **关联(依附):**边/弧与顶点之间的关系。 存在(v, v)/，则称该边/弧关联于v,和vj 当有向图中仅1个顶点的入度为0,其余顶点的入度均为1，此时称其为有向树。 6.3 图的类型定义 6.4 图的存储结构 6.4.1 邻接矩阵表示法 分析1:无向图的邻接矩阵是对称的; 分析2:顶点i的度=第i行(列)中1的个数; 特别:完全图的邻接矩阵中，对角元素为0，其余1。 分析1:有向图的邻接矩阵可能是不对称的。 分析2:顶点的出度=第i行元素之和;顶点的入度=第i冽元素之和; 算法实现无向网： 邻接矩阵——有什么好处? 直观、简单、好理解 方便检查任意一对顶点间是否存在边 方 ...

5.6 树和森林 5.6.1 树的存储结构 结合起来： 5.6.2 树和二叉树的转换 由子树和二叉树都可以用二叉链表作存储结构，则以二叉链表作媒介可以导出树与二叉树之间的一个对应关系。给定一棵树，可以找到唯一的一棵二叉树与之对应。 5.6.3 森林和二叉树的转换 5.6.4 树和森林的遍历 5.7 哈夫曼树（最优二叉树）Huffman Tree 5.7.1 哈夫曼树的基本概念 满二叉树不一定是哈夫曼树 权值越大的叶子距离根节点越近 具有相同带权结点的哈夫曼树不唯一 5.7.2 哈夫曼树的构造算法 因为哈夫曼树中权越大的叶子离根越近，所以采用贪心算法，即构造时首先选择权值小的叶子节点 包含n个叶子结点的哈夫曼树共有2n-1个结点，因为包含n棵树的森林要经过n-1次合并才能幸成哈夫曼树，也就产生了n-1个新结点。 哈夫曼树的结点度数为0或2，没有度为1的结点。 算法实现： 5.7.3 哈夫曼编码 若将编码设计为长度不等的二进制编码，即让待传字符串中出现次数较多的字符采用尽可能短的编码，则转换的二进制字符串便可能减少。 关键:要设计长 ...

5.1 树形结构 为何要重点研究每结点最多只有两个“叉”的树? √二叉树的结构最简单，规律性最强; √可以证明，所有树都能转为唯一对应的二叉树，不失一般性。 二叉树是n (n≥0)个结点的有限集，它或者是空集(n = 0)，或者由一个根结点及两棵互不相交的分别称作这个根的左子树和右子树的二叉树组成。 特点： 1、每个结点最多有俩孩子(二叉树中不存在度大于2的结点)。 2、子树有左右之分，其次序不能颠倒。 3、二叉树可以是空集合，根订以有空的左子树或空的右子树。 二叉树不是树的特殊情况，二叉树结点的字数要区分左子树和右子树，即使只有一个子结点 5.2 案例引入 5.3 树和二叉树的抽象数据类型定义 5.4 二叉树的性质和存储结构 5.4.1 性质 在二叉树的第i层最多由2^(i-1)个结点，最少一个 深度为k的二叉树最多有2^k-1个结点，最少k个 对某一棵二叉树，如果其叶子树为n0，度为2的节点数为n2，则n0=n2+1; 证明：设总边数B，总结点数n，度为1的节点数为n1 从下往上看：B=n-1 从上往下看：B=n22+n11 又n=n0+n1+n2 可得n0= ...

4.1 串：内容受限的线性表 串（String）——零个或多个任意字符组成的有限序列 4.1.1串的顺序存储结构（更常用） 4.1.2串的链式存储结构——块链结构 4.1.4 串的模式匹配算法 目的：确定主串中所含子串第一次出现的位置 Brute—Force算法，亦称简单匹配算法：穷举 BF算法的时间复杂度 最好的情况是比较m次，最差为(n-m+1)*m次，效率低 KMP算法设计思想 此时主串的指针i不必回溯！ 假设某时刻已经比较到子串的前(j-1)位和主串第i位前面的(j-1)位已经相等了，但是i，j本身不相等； 此时寻找主串第i位前面有没有(k-1)位和子串从头开始的前(k-1)位正好相等； 如果没有，子串第一位和主串第i位继续往后比； 如果有，那么主串的第i位和子串的第k位继续往后比； 如此做直到找到或者主串比完了； 📌 第三步中，因为主串前(j-1)位已经和子串前(j-1)位相等了，所以要确定下一次从子串的哪一位开始继续比，只要看子串的前(k-1)位和第j位前的(k-1)位就可以了。则定义了next[j]这样一个函数处理子串 强调一下1<k& ...

3.1 栈和队列的定义和特点 栈和队列是限定插入和删除只能在表的端点进行的线性表，是线性表的子集 3.1.1 栈：Stack 栈就像手电筒装电池、手枪弹夹里装子弹：有**后进先出（Last In First Out）**的特性 栈是仅在表尾进行插入删除操作的线性表，简称LIFO结构 它与一般线性表的区别：仅在于运算规则不同 案例1：进制转换 括号匹配的检验 表达式求值 3.1.2 队列Queue 队列就像排队，有**先进先出（First In First Out）**的特性，插入仅在表尾，删除仅在表头 舞伴问题 3.3 栈的定义和实现：顺序栈和链栈 3.3.2 顺序栈的实现 上溢(overflow):栈已经满，又要压入元素，使问题的处理无法进行 下溢(underflow):栈已经空，还要弹出元素，只认为是一种结束条件 顺序栈的长度=S.top-S.base，这里可以对指针加减，他会自动除以元素长度 删除时，删除base对应空间，长度设为0，两个指针设为空 入栈：先判断是否上溢，满则报错(也可以加空间），否则压入元素并让top ...