浙大数据结构课程学习笔记

本文共有10144个字，关键词：笔记

作为不是软件工程专业的渣渣，越来越觉得有必要自修一点专业的知识。虽然不可能完整和系统的学习到这些基础，但至少能拉近一下和专科的距离，多少能学到点东西吧。下面是在MOOC上修的一门浙大数据结构的笔记。

第一讲、基本概念

1.1 什么是数据结构
1.2 什么是算法
1.3 最大子列问题
给定N个整数的序列{A1,A2,A3,......,An}，求最大子列。
算法1：直接几个for循环，当出现最大的就更新。T(N)=O(N3)
算法2：在算法1的基础上，变为每次只在当前的结果累加一项。T(N)=O(N2)
算法2：分治法 T(N)=NlogN
算法4：在线处理，在每输入一个数据就马上处理，在任何地方停止都能即时给出当前解。T(N)=O(N)

第二讲、线性结构

2.1 什么是线性表

2.1.1 概念：由同类型数据元素构成有序序列的的线性结构

  • 表中元素个数称为线性表的长度。
  • 线性表没有元素时，称为空表。
  • 表起始位置称表头，表结束为止称表尾。
    2.1.2 线性表的表示
  • 用数组实现顺序存储。
  • 用链式存储。
    2.1.3 广义表
  • 是线性表的推广。
  • 对于线性表而言，n个元素都是基本的单元素。
  • 广义表中，这些元素不仅可以是单元素也可以是另一个广义表。
    2.1.4 多重链表
  • 多重链表中节点的指针域会有多个。
  • 但包含两个指针域的链表并不一定是多重链表。双向链表不是多重链表。
  • 多重链表有广泛的用途：基本上如树、图这样相对复杂的数据结构都可以采用多重链表方式实现存储。

2.2 堆栈

2.2.1 具有一定操作约束的线性表

  • 只在一端（栈顶）做插入、删除。
  • 插入数据，入栈。
  • 删除数据，出栈。
  • 后入先出。Last in first out（LIFO）
    2.2.2 栈的顺序存储结构实现

通常由一个数组和一个记录栈顶元素位置的变量组成。
2.2.3 栈的链式存储结构实现
单链表，叫做链栈。插入和删除只能在栈顶进行。
2.2.4 堆栈应用

  • 表达式求值：中缀表达式转化为后缀表达式
  • 函数调用及递归实现
  • 深度优先搜索
  • 回溯算法

2.3 队列

2.3.1 概念：具有一定操作约束的线性表

  • 只能在一端插入，而在另一端删除。
    2.3.2 队列的顺序存储实现

队列的顺序存储结构通常由一个一维数组和一个记录队列头元素位置的变量front以及一个记录队列尾元素位置的变量rear组成。
2.3.3 队列的链式存储实现
队列的链式存储结构也可以用一个单链表实现。插入和删除操作分别在链表的两头进行。

第三讲、树（上）

3.1 树与树的表示

3.1.1 定义：n（n>=0）个节点构成的有限集合。当n=0时，称为空树。对于任一棵非空树，它具备以下性质：

  • 树中有一个称为“根（Root）”的特殊节点，用r表示；
  • 其余节点可分为m（m>0）个互不相交的有限集T1，T2，...，Tm，其中每个集合本身又是一棵树，称为原来树的“子树（SubTree）”。
  • 子树是不相交的；
  • 除了根节点外，每个节点有且仅有一个父节点；
    一棵N个节点的树有N-1条边；

3.1.2 树的一些基本术语

  1. 结点的度（Degree）：结点的子树个数
  2. 树的度：树的所有结点中最大的度数
  3. 叶节点（Leaf）：度为0的结点
  4. 父节点（Parent）：有子树的结点是其子树的根节点的父节点
  5. 子结点（Child）：若A结点是B结点的父结点，则称B结点是A结点的子结点；子结点也成孩子结点
  6. 兄弟结点（Sibling）：具有同一父结点的各结点彼此是兄弟结点。
  7. 路径和路径长度：从结点n1到nk的路径为一个结点序列n1,n2,...,nk,ni是n(i+1)的父结点。路径所包含边的个数为路径长度。
  8. 祖先结点（Ancestor）：沿树根到某一结点路径上的所有结点都是这个结点的祖先结点。
  9. 子孙结点（Descendant）：某一结点的子树中的所有结点是这个结点的子孙。
  10. 结点的层次（Level）：规定根结点在1层，其他任一结点的层数是其父结点的层数加1。
  11. 树的深度（Depth）： 树中所有结点中的最大层次是这棵树的深度。
    3.1.3 树的标识

儿子-兄弟表示法。

3.2 二叉树及存储结构

3.2.1 二叉树的定义
二叉树T：一个有穷的结点集合。这个集合可以为空，若不为空，则它是由根节点和称为其左子树TL和右子树TR的两个不相交的二叉树组成。

  • 二叉树的五种基本形态：（1）空树；（2）只有根节点；（3）有根节点和左子树；（4）有根节点和右子树；（5）有根节点和左右子树。
  • 二叉树的子树有左右顺序之分。
    3.2.2 特殊二叉树
  • 斜二叉树（Skewed Binary Tree）。
  • 完美二叉树（Perfect Binary Tree）、满二叉树。
  • 完全二叉树（Complete Binary Tree）
    微信图片_20171128194432.png

3.2.3 二叉树几个重要性质

  • 一个二叉树第i层的最大结点数为：2^(i-1),i>=1。
  • 深度为k的二叉树有最大结点总数为：2^k -1,k>=1。
  • 对任何非空二叉树二叉树T，若n0表示叶结点的个数、n2是度为2的非叶结点的个数，那么两者满足关系n0=n2+1。
    3.2.4 二叉树的存储结构
  1. 顺序存储结构：适合完全二叉树，按从上至下、从左到右的顺序存储。一般的二叉树采用这种结构会造成空间浪费。
  2. 链表存储

3.3 二叉树的遍历

3.3.1 先序遍历
访问根结点->先序遍历其左子树->先序遍历其右子树。
3.3.2 中序遍历
中序遍历其左子树->访问根结点-> 终须遍历其右子树。
3.3.3 后序遍历
后序遍历其左子树-> 后序遍历其右子树-> 访问根结点。
微信图片_20171128195658.png
3.3.4 二叉树的非递归遍历
二叉树遍历的核心问题：二维结构的线性化。

  • 中序遍历非递归算法的基本思路：使用堆栈
  • 层序遍历：队列实现
  • 例子：由两种遍历序列确定二叉树：必须要已知中序遍历，然后可以任意知道一种后序和先序，才能确定。
    微信图片_20171128200148.png

第四讲、树（中）

4.1 二叉搜索树

二叉搜索树，也称二叉排序树或二叉查找树。
二叉搜索树：一棵二叉树，可以为空，若不为空，满足以下性质：

  • 非空左子树的所有键值小于其根结点的键值。
  • 非空右子树的所有键值大于其根结点的键值。
  • 左、右子树都是二叉搜索树。
    查找最大和最小元素：
  • 最大元素一定是在数的最右分枝的端结点上
  • 最小元素一定是在数的最左分枝的端结点上

4.2 平衡二叉树

平衡因子（Balanced Factor，简称BF）：BF（T）=hL-hR，其中hL和hR分别为T的左、右子树的高度。
平衡二叉树：空树，或者任一结点左、右子树的高度差的绝对值不超过1，即BF（T）<=1。

第五讲、树（下）

5.1 堆（heap）

优先队列：特殊的“队列”，取出元素的顺序是依照元素的优先权（关键字）大小，而不是元素进入队列的先后顺序。
堆的两个特性：

  • 结构性：用数组表示的完全二叉树。

  • 有序性：任一结点的关键字是其子树所有结点的最大值（或最小值）

    • “最大堆（MaxHeap）”，也称“大顶堆”：最大值
    • “最小堆（MinHeap）”，也称“小顶堆”：最小值

5.2 哈夫曼树与哈夫曼编码

5.2.1
带权路径长度（WPL）：设二叉树有n个叶子结点，每个叶子结点带有权值Wk，从根结点到每个叶子结点的长度为lk,则每个叶子结点的带权路径长度纸盒就是：WPL=每个wk*lk的和；
最优二叉树或哈夫曼树：WPL最小的二叉树。
5.2.2 哈夫曼树的构造
每次把权值最小的两颗二叉树合并。
5.2.3 哈夫曼树的特点

  • 没有度为1的结点；
  • n个叶子结点的哈夫曼树共有2n-1个结点；
  • 哈夫曼树的任意非叶结点的左右子树交换后仍是哈夫曼树；
  • 对同一组权值{W1,W2,...,Wn},存在不同构的两棵哈夫曼树；
    5.2.4 哈夫曼编码
  • 给定一段字符串，如何对字符进行编码，可以使得该字符串的编码存储空间最少？

第六讲、图（上）

6.1 什么是图

6.1.1
微信图片_20171129105354.png
6.1.2 图的表示

  • 邻接矩阵
    微信图片_20171129105547.png

缺点：浪费空间，对稀疏图有大量无效元素，（对稠密图还是很合算的）；浪费时间，统计稀疏图中一共有多少条边。

  • 邻接表

6.2 图的遍历

6.2.1 深度优先搜索（DFS）
6.2.2 广度优先搜索（BFS）
6.2.3 术语

  • 连通：如果从V到W存在一条（无向）路径，则称V和W是连通的；
  • 路径：V到W的路径是一系列顶点的集合，其中任一对相邻的顶点间都有图中的边。路径的长度是路径中的边数（如果带权，则是所有边的权重和）。如果V到W之间的所有顶点都不同，则称简单路径。
  • 回路：七点等于终点的路径。
  • 连通图：途中任意两顶点均连通。

  • 连通分量：无向图的极大连通子图。

    极大顶点数：再加1个顶点就不连通了；
极大边数：包含子图中所有顶点项链的所有边；
  • 强连通：有向图中顶点V和W之间存在双向路径，则称V和W是强连通的；
  • 强连通图：有向图中任意两顶点均强连通；
  • 强连通分量：有向图的极大连通子图；

第七讲、图（中）

7.1 最短路径问题

7.1.1 在网路中，求两个不同顶点之间的所有路径中，边的权值之和最小的那一条路径。这条路径就是两点之间的最短路径（Shortest Path）

  • 第一个顶点为源点（Source）
  • 最后一个顶点为终点（Destination）
    7.1.2 问题分类
  • 单源最短路径问题：从某固定源点除非，求其到所有顶点的最短路径
  • 多源最短路径问题：求任意两顶点间的最短路径
    7.1.3 无权图的单源最短路算法
  • 按照递增（非递减）的顺序找出到各个顶点的最短路。BFS算法。
    7.1.4 有权图的单源最短路算法
  • Dijkstra算法
    微信图片_20171129230533.png

7.1.5 多源最短路算法

  • Floyd算法
    微信图片_20171129230726.png

第八讲、图（下）

8.1 最小生成树问题

8.1.1 什么是最小生成树

  • 是一棵树，无回路，V个顶点一定有V-1条边。
  • 是生成树，包含全部顶点，V-1条边都在图里。
  • 边的权重和最小。
    8.1.2 贪心算法--每一步都要最好的

8.1.3 Prim算法--让一棵小树长大
8.1.4 Kruskal算法--将森林合并成树

8.2 拓扑排序

8.2.1 拓扑序

  • 如果图中从V到W有一条有向路径，则V一定排在W之前。满足此条件的顶点序列称为一个拓扑序。
  • 获得一个拓扑序的过程就是拓扑排序。
  • AOV如果有合理的拓扑序，则必定是有向无环图（Directed Acyclic Graph，DAG）

第九讲、排序（上）

9.1 简单排序（冒泡、插入）

9.1.1 冒泡（Bubble）：大的在下面，小的在上面。

  • 最好情况：T(N)=O(N)，最坏情况：T(N)=O(N2)。
  • 稳定
  • 同时适用数组和链表的数据结构
    9.1.2 插入排序（Insertion）：摸牌的例子
  • 最好情况：T(N)=O(N)，最坏情况：T(N)=O(N2)。
  • 程序简单
  • T(N,I)=O(N+I)，I是逆序对的数量
    9.1.3 时间复杂度下界
  • 定理：任意N个不同元素组成的序列平均具有N(N-1)/4个逆序对。
  • 定理：任何仅以交换相邻两元素来排序的算法，其平均时间复杂度为Ω(N2)。
  • 这意味着：要提高算法的效率，必须：
  1. 每次消去不止1个逆序对。
  2. 每次交换相隔较远的2个元素。

9.2 希尔排序（by Donald Shell）

定义增量序列（递减的序列），比如5间隔排序，到3间隔，最后1间隔。

  • 原始希尔序列：每次减半N/2，最坏情况是T=Θ（N2）
  • Hibbard增量序列：Dk=（2的k次方）-1.最坏情况是T=O（N的3/2次方），猜想的平均T=O(N的5/4次方)
  • Sedgewidk增量序列：{1,5,19,41,109...}。猜想的最坏情况是T=O（N的4/3次方），猜想的平均T=O(N的7/6次方)

9.3 堆排序

9.3.1 选择排序（Selection）
每次找一个最小元，交换一下。无论如何：T=Θ（N2）
9.3.2 堆排序是选择排序的改进

  • 定理：堆排序处理N个不同元素的随机排列的平均比较次数是2NlogN-O(Nlog logN)。
  • 虽然堆排序给出最佳平均时间复杂度，但实际效果不如用Sedgewick增量序列的希尔排序。

9.4 归并排序

核心：有序子列的归并

  • 递归算法：分治法 任何情况下都是T(N)=O（N logN），该算法稳定。
  • 非递归算法：稳定
  • 归并排序在外排序中非常有用，不好的是需要额外的空间。

第十讲、排序（下）

10.1 快速排序

  • 分而治之
  • 先找一个主元，然后剩余的分成2个独立的子集，递归分治。
  • 最好的情况，主元每次正好中分，T=O（NlogN）
  • 选主元的方法：1.选第一个；2.中位数，如三个数取中间的数，然后把这个数放到最右边再进行排序。
  • 快速排序需要用到递归，当数据规模充分小，则最好使用简单排序（如插入排序）

10.2 表排序

属于间接排序：定义一个指针数组作为“表”（不移动数据，只是移动指向数据的指针）。
物理排序：在表排序后，把实际数据进行排序。N个数字的排列由若干个底力的环组成。

10.3 基数排序

10.3.1 桶排序（Bucket_Sort）
新建一个与要排的数等长的数组，然后把数组的值之间插入到对应的下标中。T(N)=O（M+N），M是声明的数组长度。当M>>N时，在线性时间内排序不划算。
10.3.2 基数排序

  • 次位优先（如从个位到十位）：T(N)=O（P(N+B)），B是桶的个数，P是排序次数
  • 多关键字排序，主位优先
    10.3.3 排序比较

微信图片_20171124233853.png

第十一讲、散列查找

11.1 散列表

11.1.1

  • 查找的本质：已知对象找位置。1.有序安排对象：全序、半序。2.直接“算出”对象位置。

  • 散列查找法的两项基本工作：

    1. 计算位置：构造散列函数确定关键词存储位置
    2. 解决冲突：应用某种策略解决多个关键词位置相同的问题。
  • 时间复杂度几乎是常量：O(1)，即查找时间与问题规模无关。
    11.1.2 散列表（哈希表）
  • 装填因子：设散列空间大小为m，填入表中元素个数是n，则称a=n/m为散列表的装填因子。
  • 散列的基本思想是：
    （1） 以关键字key为自变量，通过一个确定的函数h（散列函数），计算出对应的函数值h(key)，作为数据对象的存储地址。
    （2） 可能不同的关键字会映射到同一个散列地址上，即h(key1)=h(key2)(当key1不等于key2)，称为“冲突（Collision）”。---需要某种冲突解决策略。

11.2 散列函数的构造方法

11.2.1

  • 一个好的散列函数一般考虑两个因素：

    1. 计算简单，以便提高转换速度；
    2. 关键词对应的地址空间分布均匀，以尽量减少冲突。

  • 数字关键字的散列函数构造

    1. 直接定址法：取关键词的某个线性函数值为散列地址，即h(key)=a*key+b(a、b为常数)
    2. 除留余数法：h(key)=key mod p ,p=表的大小，一般p为素数。
    3. 数字分析法：分析数字关键字在各位上的变化情况，取比较随机的位作为散列地址，如11位手机号码key的后4位作为地址，18位身份证号取特定的区县，出身日等字段。
    4. 折叠法：把关键词分割成位数相同的几个部分，然后叠加。
    5. 平方取中法
      11.2.2

  • 字符关键词的散列函数构造

    1. ASCLL码加和法：h(key)=(key的字符和) mod TableSize，冲突严重（a3、b2、c1；eat、tea）
    2. 改进ASCLL，前3个字符移位法：h(key)=(key[0]27^2+key[1]27+key[2]) mod TableSize,仍然冲突（string、street、strong等，空间浪费3000/26^3=30%）
    3. 移位法：h(key)=((每个key*32^i)的和) mod TableSize

11.3 冲突处理方法

11.3.1 常用处理冲突的思路

  1. 换个位置：开放地址法
    若发生了第i次冲突，试探的下一个地址将增加di，基本公式是：h(key)=(h(key)+di) mod TableSize (1<=i<TableSize);

di决定了不同的解决冲突方案：

a. 线性探测：以增量序列1,2,....,(TableSize-1)循环试探下一个存储地址。di=i。

  • 缺点：会产生聚集现象。

    1. 平方探测（二次探测）：di=+-i^2
  • 解决了聚集现象，但可能会造成找不到空间的现象

  • 如果散列表长度TableSize是某个4k+3（k是正整数）形式的素数时，平方探测法就可以探查到整个散列表空间。

    1. 双散列:di=i*h2(key)，对任意的key，h2(key)!=0。探测序列还应该保证所有的散列存储单元都应该能够被探测到。经验证明这样的散列比较好：h2(key)=p-(key mod p)
    2. 再散列（Rehashing）。当散列表元素太多（即装填因子a太大）时，查找效率会下降。实用最大装填因子一般取0.5<=a<=0.85。当装填因子过大时，解决的方法是加倍扩大散列表，这个过程叫做“再散列”。

  1. 同一位置的冲突对象组织在一起：链地址法

    1. 分离链接法（Separate Chaining）：将形影位置上冲突的所有关键词存储在同一个单链表中。
  2. 几种方法的性能分析
  • 成功平均查找长度（ASLs）：成功的key冲突次数+1 的和除以成功的key个数。
  • 不成功平均查找长度（ASLu）：一般方法：将不在散列表中的关键词分若干类，如根据h(key)的值分类。
  1. 线性探测
    微信图片_20171128102213.png
  2. 双散列探测
    微信图片_20171128102236.png
  3. 比较
    微信图片_20171128102426.png
  4. 分离链接法
    微信图片_20171128102642.png

11.4 散列表的性能分析

  • 选择合适的h(key)，散列的查找效率期望是常数，它几乎与关键字的空间大小n无关，也适合于关键字直接比较计算量打的问题。
  • 它是以较小的a为前提。因此，散列方法是一个以空间换时间的方法。
  • 散列方法的存储对关键字是随机的，不便于顺序查找关键字，也不适合于范围查找或最大值最小值查找。
  1. 开放地址法：散列表是一个数组，存储效率高，随机查找。散列表有“聚集”现象。
  2. 分离链法：（1）散列表是瞬时存储和链式存储的结合，链表部分的存储效率和查找效率都比较低。（2）关键字删除不需要“懒惰删除”法，从而没有存储“垃圾”。（3）太小的a可能导致空间浪费，大的a又将付出更多的时间代价。不均匀的链表长度导致时间效率的严重下降。

11.5 应用实例：词频统计

「一键投喂 软糖/蛋糕/布丁/牛奶/冰阔乐！」

fengxianqi

(๑＞ڡ＜)☆谢谢老板~

使用微信扫描二维码完成支付

版权声明：本文为作者原创，如需转载须联系作者本人同意，未经作者本人同意不得擅自转载。
 Webpack学习笔记 按所给的时间格式输出指定的时间 
添加新评论
暂无评论