02142数据结构导论复习笔记

第一章 概论

• 概论⭐⭐
  • 数据结构：计算机组织数据和存储数据的方式。
  • 数据结构：指一组相互之间存在一种或多种特定关系的数据的组织方式和它们在计算机内的存储方式，以及定义在该组数据上的一组操作。
• 引言⭐⭐
  • 算法+数据结构=程序
• 数据、数据元素和数据项⭐⭐⭐
  • 数据：所有被计算机存储、处理的对象。
  • 数据元素：数据的基本单位，是运算的基本单位。常常又简称为元素。
  • 数据项：是数据的不可分割的最小标识单位。在数据库中数据项又称为字段。
  • 数据、数据元素、数据项之间的关系：从宏观上来看，数据、数据元素和数据项实际上反映了数据组织的三个层次，数据可由若干个数据元素组成，而数据元素又可由若干数据项组成。
  • 数据结构是相互之间存在一种或多种特定关系的数据元素的组合。它包括数据的逻辑结构、数据的存储结构和数据的基本运算。
• 数据的逻辑结构⭐⭐⭐
  • 集合：任意两个结点之间都没有邻接关系，组织形式松散。（一盘散沙）
  • 线性结构：结点按逻辑关系依次排列形成一条“链”，结点之间一个一个依次相邻接。
  • 树形结构：具有分支、层次特性，其形态像自然界中的树，上层的结点可以和下层多个结点相邻接，但下层结点只能和上层一个结点相邻接。
  • 图结构：最复杂，其中任何两个结点都可以相邻接。
• 数据的存储结构⭐⭐⭐
  • 顺序存储方式：指所有存储结点存放在一个连续的存储区里。利用结点在存储器中的相对位置来表示数据元素之间的逻辑关系。
  • 链式存储方式：指每个存储结点除了含有一个数据元素外，还包含指针，每个指针指向一个与本结点有逻辑关系的结点，用指针表示数据元素之间的逻辑关系。
  • 除了上述两种存储方式之外 ，还有索引存储方式和散列存储方式。但主要的存储方式是：顺序存储方式和链式存储方式。
• 运算⭐
  • 运算包括：建立、查找、读取、插入和删除等。
  • 线性表、栈和队列中的元素具有相同的逻辑结构（即线性结构），但有不同的运算集，它们是不同的数据结构。
• 评价算法好坏的因素⭐⭐⭐
  • 正确性：能正确地实现预定的功能，满足具体问题的需要。
  • 易读性：易于阅读、理解和交流，便于调试、修改和扩充。
  • 健壮性：即使输入非法数据，算法也能适当地做出反应或进行处理，不会产生预料不到的运行结果。
  • 时空性：指该算法的时间性能（或时间效率）和空间性能（或空间效率），前者是算法包含的计算量，后者是算法需要的存储量。
• 时间复杂度⭐⭐⭐
  • 常见的时间复杂度的比较：
    • O(1)<O(log₂n)<O(n)<O(nlog₂n)<O(n²)<O(n^c)<O(2ⁿ)
      • O(1) 无循环、无递归
      • O(log2n) 无循环、有递归
      • O(n) 一层循环
      • O(nlog2n) 一层循环+递归
      • O(n^2) 双层循环
      • O(n^c) c层循环
      • O(2^n) 实际不可计算的。
• 空间复杂度⭐
  • 是对一个算法在运行过程中临时占用存储空间大小的量度。存储空间量应包括：
    • 程序代码所占用的空间；
    • 输入数据所占用的空间
    • 辅助变量所占用的空间，估算时，一般只需要分析辅助变量所占用的空间。

第二章 线性表

• 线性表的基本概念⭐⭐
  • 概念：线性表是一种线性结构，由n(n≧0)个数据元素组成的有穷序列，数据元素又称结点。结点个数 n 称为表长。a1称为起始节点，an称为终端结点。
  • 基本特征：线性表中结点具有一对一的关系，如果结点数不为零，则：
    • 除起始结点没有直接前驱外，其他每个结点有且仅有一个直接前驱；
    • 除终端结点没有直接后继外，其他每个结点有且仅有一个直接后继。
• 顺序表实现算法的分析⭐⭐⭐
  • 
• 单链表的类型定义⭐⭐⭐
  • 结点结构
    • 数据域（data），用于存储线性表的一个数据元素。
    • 指针域或链域（next），用于存放一个指针，该指针指向本结点所含数据元素的直接后继结点。
  • 单链表：所有结点通过指针链接形成链表。
    • 头指针：head称为头指针变量，该变量的值是指向单链表的第一个结点的指针。
    • 首结点：链表中第一个数据元素称为链表的首结点。
    • 尾结点：链表中最后一个数据元素结点称为尾结点或终端结点。尾结点指针域的值NULL称为空指针，它不指向任何结点，表示链表结束。
  • 带头结点的单链表：在单链表的第一个结点之前增设一个类型相同的结点，称为头结点。
• 线性表的基本运算在单链表上的实现⭐⭐⭐
  • 插入：插入p指向新结点的操作
    • ① p->next=q->next; ② q->next=p;
  • 删除：删除*p结点的操作
    • q->next=p->next;
• 循环链表⭐⭐
  • 在单链表中，如果让最后一个结点的指针域指向第一个结点可以构成循环链表。
    • 判断p所指结点的尾结点的条件：p->next==head;
    • 判断指针p所指结点为首结点的条件：p==rear->next->next;
    • 判断链表是否为空的条件：head->next==head;
• 双向循环链表⭐⭐⭐
  • 每个结点有两个指针，next指针指向直接后继结点；prior指针指向直接前驱结点。
  • 带头结点的双向循环链表L为空的条件：(L->next==L) && (L->prior==L)
  • 删除
    • 设p指向待删结点，删除*p的操作：
      • p->prior->next=p->next;
      • p->next->prior=p->prior;
      • free§
      • 以上前两条语句顺序可颠倒。
  • 插入
    • 在p所指结点的后面插入一个新结点 *t 的操作：
      • t->prior=p;
      • t->next=p->next;
      • p->next->prior=t;
      • p->next=t;
• 顺序实现与链接实现的比较⭐
  • 

第三章 栈、队列和数组

• 栈、队列和数组⭐⭐

  • 栈和队列可看作是特殊的线性表。它们是运算受限的线性表。栈和队列也同样有两种存储结构（顺序存储结构和链式存储结构）。

• 栈的基本概念⭐⭐⭐

  • 栈：这种线性表上的插入和删除运算限定在表的某一端进行。允许进行插入和删除的一端称为栈顶，另一端称为栈底。不含任何数据元素的栈称为空栈。
  • 栈的修改原则：后进先出，栈又称为后进先出线性表，简称后进先出表。
  • 栈的基本运算：
    • 初始化 InitStack(S)：构建一个空栈S;
    • 判栈空 EmptyStack(S)：若栈S为空栈，则结果为1，否则结果为0；
    • 进栈 Push(S, x)：将元素 x 插入到栈S中，使x成为栈S的栈顶元素；
    • 出栈 Pop(S)：删除栈顶元素；
    • 取栈顶 GetTop(S)：返回栈顶元素。

• 栈的顺序实现⭐⭐

  • 下溢：当空栈，栈顶下标值 top=0，如果此时做出栈运算，则产生“下溢”。
  • 上溢：当栈中的数据元素已经填满了，如果再进行进栈操作，会发生“上溢”。
  • 初始化：
  • 判栈空：
  • 进栈：
  • 出栈：
  • 取栈顶元素：

• 队列的基本概念⭐⭐⭐

  • 是一种先进先出的线性表，新加入的数据元素插在队列尾端，出队列的数据元素在队列首部被删除。

• 队列的顺序实现⭐⭐⭐

  • 循环队列：为了避免元素的移动，将存储队列元素的一维数组首尾相接，形成一个环状。
  • 入队列操作语句：SQ.rear=(SQ.rear+1) % maxsize; SQ.data[SQ.rear]=x;
  • 出队列赋值语句：SQ.fronts(SQ.front+1) % maxsize;
  • 循环队列满：((CQ.rear +1) % maxsize == CQ.front) 成立
  • 队列空条件：(CQ.rear==CQ.front) 成立
  • 队列中元素个数公式：数组Q[n] 表示一个循环队列，设 f 为队列中第一个元素的位置，r 为队列中实际队尾的位置加1，则队列中元素的个数公式：(r-f+n) %n

• 队列的链接实现⭐

  • 由于链接实现需要动态申请空间，故链队列在一定范围内不会出现队列满的情况。
  • 队列判空：当 (LQ.front==LQ.rear) 成立时，队列中无数据元素，此时队列为空。
  • 在实现队列的链表结构中，仅设置尾指针的单循环链表的时间复杂度最优。

• 数组的存储结构⭐⭐⭐

  • 数据元素的存储位置是下标的线性函数：对于二维数组 a[m][n]，如果每个元素占 k 个存储单元，以行为主序为例，讨论数组元素 a[i][j]位置与下标的关系：
    • 由于下标从0开始，元素a[i][j]之前已经有 i 行元素，每行有n个元素，在第 i 行，有 j+1 个元素，总共有 n*i+j+1 个元素，第一个元素与 a[i][j] 相差 n*i+j+1-1 个位置，故a[i][j] 的位置为：loc[i, j]=loc[0, 0]+(n*i+j)*k。

• 矩阵的压缩存储⭐⭐⭐

  • 为了节省存储空间，对这类矩阵采用多个值相同的元素只分配一个存储空间，零元素不存储的策略，这一方法称为矩阵的压缩存储。
  • 特殊矩阵：如果值相同的元素或者零元素在矩阵中的分布有一定规律，称此类矩阵为特殊矩阵。
    • 对称矩阵：若一个 n 阶方阵A中的元素满足下述条件：则称A为对称矩阵。
      • 对称矩阵有近一半的元素可以通过其对称元素获得，为每一对对称元素只分配一个存储单元，则可将n²个元素压缩存储到含有n(n+1)/2个元素的一维数组中。
    • 三角矩阵：以主对角线为界的上（下）半部分是一个固定的值c或零，这样的矩阵叫做下（上）三角矩阵。（哪边不为c或0就是该方向的三角矩阵）
    • 稀疏矩阵：非零元素很少的矩阵。
    • 三元组表示法：用三个项来表示稀疏矩阵中的非零元素a_ij，即(i, j, a_ij)，其中 i 表示行序号，j 表示列序号，a_ij 是非零元素的值，通常称为三元组。

第四章 树和二叉树

• 树的概念⭐

  • 树是n（n≥0）个结点的有限集合，一棵树满足以下两个条件：
    • 当n=0时，称为空树；
    • 当n>0时，有且仅有一个称为根的结点，除根结点外，其余结点分 m（m≥0）个互不相交的非空集合 T1, T2, …, T_m，这些集合中的每一个都是一棵树，称为根的子树。

• 树的相关术语⭐⭐⭐

  • 结点的度：树上任一结点所拥有的子树的数目称为该结点的度。
  • 叶子：度为0的结点称为叶子或终端结点。
  • 树的度：一棵树中所有结点的度的最大值称为该树的度。
  • 一个结点的子树的根称为该结点的孩子（或称子结点）。相应地该结点称为孩子的双亲（也称父结点）。父结点相同的结点互称为兄弟。
  • 结点的层次：从根开始算起，根的层次为1，其余结点的层次为其双亲的层次加1。
  • 树的高度：一棵树中所有结点层次数的最大值称为该树的高度或深度。
  • 对于任一个树都有：结点数=分支树+1

• 二叉树的基本概念⭐

  • 二叉树是n(n≥0)个元素的有限集合，该集合或者为空，或者由一个根及两棵互不相交的左子树和右子树组成，其中左子树和右子树也均为二叉树。
  • 注意：左右子树次序不可换，都可为空。

• 二叉树的性质⭐⭐⭐

  • 满二叉树：深度为 k（k≥1）且有2k-1个结点的二叉树称为满二叉树。由性质2知，满二叉树上的结点数已达到了二叉树可以容纳的最大值。
  • 完全二叉树：如果对满二叉树按从上到下，从左到右的顺序编号，并在最下一层删去部分结点（删后最后一层仍有结点），如果删除的这些结点的编号是连续的且删除的结点中含有最大编号的结点，那么这棵二叉树就是完全二叉树。
  • 

• 二叉树的顺序存储结构⭐

  • 二叉树的顺序存储结构可以用一维数组来实现。
  • 如果需要顺序存储的非完全二叉树，首先必须用某种方法将其转化为完全二叉树，为些可增设若干个虚拟结点。会造成空间的浪费。

• 二叉树的链式存储结构⭐⭐⭐

  • 二叉树有不同的链式存储结构，其中最常用的是二叉链表或三叉链表。其结点形式如下：
  • 二叉链表：具有n个结点的二叉树中，共有2n个指针域，其中只有 n-1 个用来指向结点的左、右孩子（因为没有指向根结点的指针域），其余的 n+1 个指针域为 NULL。

• 二叉树遍历的递归实现⭐⭐⭐

  • 

• 应用举例⭐

  • 由一个二叉树的后序序列和中序序列，可以唯一确定一棵二叉树。
  • 由一个二叉树的先序序列和中序序列，也可以唯一确定一棵二叉树。
  • 注意：必须要有中序序列。

• 树的存储结构⭐

  • 孩子链表表示法：树上的一个结点 X 以及该结点的所有孩子结点组成一个带头结点的单链表。
    • 头结点含有两个域：数据域和指针域。其中，数据域用于存储结点 X 中的数据元素，指针域用于存储指向 X 第一个孩子结点的指针。
    • 表结点也含两个域：孩子域（child）和指针域（next），孩子域存储其中一个孩子的序号，指针域指向其下一个孩子的结点。
  • 孩子兄弟链表表示法：存储时每个结点除了数据域外，还有指向该结点的第一个孩子和下一个兄弟结点的指针。
    • 注意：孩子兄弟链表的结构形式与二叉链表完全相同，但结点中指针的含义不同。二叉链表中结点的左、右指针分别指向左、右孩子；而孩子兄弟链表中结点的两个指针分别指向孩子和兄弟。
  • 双亲表示法：由一个一维数组构成。数据的每个分量包含两个域：数据域和双亲域。
    • 数据域用于存储树上一个结点中的数据元素，双亲域用于存储本结点的双亲结点在数组中的序号值（下标值）。

• 树、森林与二叉树的关系⭐

  • 树转换成二叉树
    • 将所有兄弟结点连接起来；
    • 保留第一个兄弟结点与父结点的连接，断开其他兄弟结点与父结点的连接
    • 然后以根结点为轴心按顺时针的方向旋转45⁰ 角。
  • 森林转换成二叉树
    • 将每棵树转换成相应的二叉树；
    • 将上边得到的各棵二叉树的根结点看作是兄弟连接起来。
  • 二叉树转换成森林
    • 在待转换的二叉树中，断开根结点与右孩子的连线，得到两棵二叉树，其中一棵是以二叉树B的根结点为根的二叉树，另一棵是以根结点的右孩子E 为根结点的二叉树。

• 森林的遍历⭐⭐

  • 

• 分类与判定树⭐

  • 分类：一种常用运算，其作用是将输入数据按预定的标准划分成不同的种类。
  • 判定树：用于描述分类过程的二叉树。

• 哈夫曼(Huffman)树与哈夫曼算法⭐⭐⭐

  • 哈夫曼树：给定一组值 p1 …, pk，如何构造一棵有 k 个叶子且分别以这些值为树的判定树，使得其平均比较次数（WPL）最小。满足上述条件的判定树称为哈夫曼树。其中P_i 是第 i 个结点的权值，l_i 是第 i 个结点的比较次数。
  • 哈夫曼算法：哈夫曼给出的一个求哈夫曼树的简单而有效的方法，称为哈夫曼算法。具体方法如下：
    • ①由给定的值{p1, …, pk} 构造森林 F={T1, …, Tk}，其中每个Ti为一棵只有根结点且其权为p_i的二叉树。
    • ②从F中选取根结点的权最小的两棵二叉树T_i、T_j，构造一棵分别以T_i 和T_j 为左、右子树的新的二叉树T_h，置T_h根结点的权为T_i 和 T_j 根结点的树值之和。
    • ③从F中删去T_i 、T_j，并将T_h 加入F。若F中仍多于一棵二叉树，则返回②，直到F中只含一棵二叉树为止，这棵二叉树就是哈夫曼树。
    • 结论：最终求得的哈夫曼树中共有结点总数：2n-1 个。其中，n个叶结点是初始森林中的n个结点，合并 n-1 次共产生 n-1 个新结点，且哈夫曼树中没有度数为1的分支结点。

第五章 图

• 图的定义和术语⭐⭐
  • 无向完全图：任何两点之间都有边的无向图称为无向完全图。一个具有n个顶点的无向完全图的边数为 n(n-1) /2。
  • 有向完全图：任何两点之间都有弧的有向图称为有向完全图。一个具有n个顶点的有向完全图的弧数为 n(n-1)。（有向图的边称为弧）
  • 度：
    • 无向图的度：无向图中顶点v的度是与该顶点相关联的边的数目，记为 D(v)。
    • 有向图的入度：有向图中以顶点v为终点的弧的数目称为v的入度，记为 ID(v)。
    • 有向图的出度：有向图中以顶点v为始点的弧的数目称为v的出度，记为 OD(v)。
    • 有向图的度：有向图中顶点v的度为入度和出度之和，即 D(v)=ID(v)+OD(v)。
  • 连通：在无向图中，如果从顶点v到顶点v’ 有路径，则称v和v’ 是连通的。
  • 连通图：如果图中的任意两个顶点v_i和v_j都是连通的，则称G为连通图。
  • 连通分量：是无向图中的极大连通子图。
  • 强连通图：对于有向图来说，如果图中任意一对顶点v_i和v_j（其中i≠j）都有顶点v_i 到顶点 v_j的路径，也有从v_j 到v_i 的路径，即两个顶点间双向连通。
  • 强连通分量：有向图的极大强连通子图。
  • 生成树：一个连通图的生成树，是含有该连通图的全部顶点的一个极小连通子图。
• 邻接矩阵⭐⭐⭐
  • 用矩阵来描述图中顶点之间的关联关系，用二维数组来实现矩阵。设G=(V, E)是一个图，其中V={v₀, v₁, …, v_n-1}，那么G的邻接矩阵A定义为如下n阶方阵：
  • 无向图的邻接矩阵是一个对称矩阵。
  • 有向图
    • 顶点v_i的出度 OD(v_i) 是邻接矩阵中第 i 行元素之和。
    • 顶点v_i的入度 ID(v_i) 是邻接矩阵中第 i 列元素之和。
• 邻接表⭐
  • 邻接表是顺序存储与链式存储相结合的存储方法。
• 图的遍历⭐⭐⭐
  • 深度优先搜索
    • 类似于树的先序遍历。
    • 基本思想：假定以图中某个顶点v_i 为出发点，首先访问出发点 v_i，然后任选一个v_i 的未访问过的邻接点 v_j，以v_j 为新的出发点继续进行深度优先搜索，依此类推，直至图中所有顶点都被访问过。深度优先搜索遍历类似于树的先序遍历。图的深度优先搜索可以看成一个递归过程。
    • 注意两点：
      • 1、搜索到达某个顶点时（图中仍有顶点未被访问），如果这个顶点的所有邻接点都被访问过，那么搜索就要回到前一个被访问过的顶点，再从该顶点的下一未被访问的领接点开始深度优先搜索；
      • 2、深度搜索的顶点的访问序列不是唯一的。
    • 时间复杂度
      • 采用邻接矩阵作为存储结构的图的时间复杂度：O(n²)，其中n 为图的顶点数。
      • 采用邻接表作为存储结构的图的时间复杂度：O(n+e)，其中n 为图的顶点数，e为图的边数。
  • 广度优先搜索
    • 类似于树的按层次遍历的过程。
    • 基本思想：从图中某个顶点v_i 出发，在访问了v_i 之后依次访问v_i 的所有邻接点，然后依次从这些邻接点出发按广度优先搜索方法遍历图的其他顶点，重复这一过程，直至所有顶点都被访问到。类似于树的按层次遍历的过程。
• 最小生成树⭐⭐
  • 一个图的最小生成树是图所有生成树中权总和最小的生成树。
  • 最小生成树的算法有：Prim算法 和 克鲁斯卡尔(Kruskal)算法
  • 求单源最短路径——迪杰斯特拉（Dijkstra）算法
• 拓扑排序⭐⭐
  • AOV网：如果以图中的顶点来表示活动，有向边表示活动之间的优先关系，这种用顶点表示活动的有向图称为 AOV网。AOV网中的弧表示了活动之间存在着的制约关系。
  • 拓扑排序：拓扑排序的算法的时间复杂度为O(n+e)，n是图的顶点个数，e是图的弧的数目。

第六章 查找

• 基本概念⭐⭐
  • 查找表（Search Table）是由同一类型的数据元素构成的集合，它是一种以查找为“核心”，同时包括其他运算的非常灵活的数据结构。其分类有：
    • 静态查找表：建表、查找 、读表中元素
    • 动态查找表：初始化、查找、读表中元素、插入、删除
• 顺序表上的查找⭐⭐
  • 静态查找表最简单的实现方法是以顺序表作为存储结构，即链式存储结构。
  • 查找成功时的平均查找长度，记为ASL：，其中，P_i为查找第i个元素（即给定值key与顺序表中第i个元素的键值相等）的概率，且，C_i 表示在找到第 i 个元素时，与给定值已进行比较的键值个数。
• 有序表上的查找⭐⭐⭐
  • 有序表：如果顺序表中数据元素是按照键值大小的顺序排列的，则称为有序表。适用于二分查找。
  • 二分查找：用给定值key与处在中间位置的数据元素T.elem[mid]的键值T.elem[mid].key 进行比较，可根据三种比较结果区分三种情况：
    • key=T.elem[mid].key，查找成功，T.elem[mid]即为待查元素；
    • key<T.elem[mid].key，说明若待查元素在表中，则一定排在T.elem[mid] 之前；
    • key>T.elem[mid].key，说明若待查元素在表中，则一定排在T.elem[mid] 之后。
  • 平均查找长度：二分查找的平均查找长度为
  • 二分查找算法平均时间复杂度：O(log₂n)
• 二叉排序树⭐⭐
  • 定义：一棵二叉排序树（又称二叉查找树）或者是一棵空二叉树，或者是具有下列性质的二叉树：
    • 若它的左子树不空，则左子树上所有结点的键值均小于它的根结点键值；
    • 若它的右子树不空，则右子树上所有结点的键值均大于它的根结点键值；
    • 根的左、右子树也分别为二叉排序树。
  • 二叉排序树上平均查找长度是介于**O(n)和O(log₂n)**之间的。
• 散列表⭐
  • 数据元素的键值和存储位置之间建立的对应关系 H 称为散列函数，用键值通过散列函数获取存储位置的这种存储方式构造的存储结构称为散列表。
  • 设有散列函数 H 和键值 k1、k2（k≠k2），若 H(k1)=H(k2)，则这种现象称为“冲突”，且称键值 k1 和 k2 互为同义词。
• 常用散列法⭐⭐
  • 数字分析法：又称数据选择法，其方法是收集所有可能出现的键值，排列在一起，对键值的每一位进行分析，选择分布较均匀的苦干位组成散列地址。所取的位数取决于散列表的表长，见表长100，则取2位即可。
  • 除留余数法：是一种简单有效且最常用的构造方法，其方法是选择一个不大于散列表长n的正整数p，以键值除以p所得的余数作为散列地址，即H(key)=key mod p (p≤n)，注意：通常选p为小于散列表长度n的素数。
  • 平方取中法：以键值平方的中间几位作为散列地址。通常在选定散列函数时不一定能知道键值的分布情况。所得散列地址比较均匀。
  • 基数转换法：将键值看成另一种进制的数再转换成原来进制的数，然后选其中几位作为散列地址。
• 散列表的实现⭐⭐
  • 线性探测法：对任何键值key，设H(key)=d，设散列表的容量为m，则线性探测法生成的后继散列地址序列为 d+1，d+2, …, m-1, 0, 1, …, d-1
  • 二次探测法：生成的后继散列地址不是连续的，而是跳跃式的，以便为后续数据元素留下空间从而减少堆积。按照二次探测法，键值key的散列地址序列为d₀=H(key); d₁=(d₀+i) mod m。其中，m为散列表的表长，i=1²，-1²，2²，-2²，…，$\pm$ k²(k≤m/2)。

第七章 排序

• 概述⭐⭐
  • n个记录的序列为{R₁, R₂, …, R_n}，其相应的键值序列为{k₁, k₂, …, k_n}，假设k_i=k_j，若在排序前的序列中R_i在R_j之前，即 i<j，经过排序后，R_i 仍在R_j 之前，则称所用的排序方法是稳定的；反之，则称所用的排序方法是不稳定的。
  • 稳定性是排序方法本身的特性，与数据无关。
• 4种排序方法⭐⭐⭐
  •