数据结构理论复习

思维导图

---

---

绪论

数据结构的定义

• 数据是描述客观事物的数、字符以及所有能输入到计算机中并被计算机程序处理的符号的集合。
• 数据元素是数据的基本单位（例如，A班中的每个学生记录都是一个数据元素），也就是说数据元素是组成数据的、有一定意义的基本单位，在计算机中通常作为整体处理
• 数据项是具有独立含义的数据最小单位，也称为成员或域
• 数据对象是性质相同的有限个数据元素的集合，它是数据的一个子集。
• 数据结构是指所涉及的数据元素以及数据元素之间的关系，可以看作是相互之间存在着特定关系的数据元素的集合。
• 数据元素之间的逻辑关系 => 数据的逻辑结构
• 数据元素及其关系在计算机存储器中的存储方式 => 数据的存储结构（或物理结构）
• 施加在该数据上的操作 => 数据运算

算法及其描述

• 有穷性
• 确定性
• 可行性
• 输入性
• 输出性

算法时间性能分析

• 求和定理
• 求积定理

算法存储空间分析

• 在对算法进行存储空间分析时，只考察临时变量所占空间

线性表

顺序表

• 插入元素移动的平均次数为$\sum\limits_{i=0}^n p_i (n-i)=\frac{1}{n+1}\times \frac{n(n+1)}{2}=\frac{n}{2}$
• 删除元素移动的平均次数为$\sum\limits_{i=0}^{n-1} p_i (n-i-1)=\frac{1}{n}\times \frac{n(n-1)}{2}=\frac{n-1}{2}$

链表

• 插入s->next = p->next; p->next = s;
• 删除q = p->next; p->next = q->next; delete q;
• 头插法建表s->next = head->next; head->next = s;

栈和队列

栈

• 判断准则：输入序列为$1,2,…,n,(p_1,p_2,…,p_n)$是$1,2,…,n$的一种排列，利用一个栈得到输出序列$(p_1,p_2,…,p_n)$的充分必要条件是不存在这样的$i、j、k$满足$i<j<k$的同时也满足$p_j<p_k<p_i$。
• $1\sim n$共产生$\frac{1}{n+1} C_{2n}^n$种合法出栈序列

队列

顺序队列

• 队空条件：front == rear
• 队满（上溢出）条件：rear == MaxSize - 1

循环队列

• 元素出队：front = (front + 1) ％ MaxSize
• 元素e进队：rear = (rear + 1) ％ MaxSize
• 队空条件：front == rear
• 队满条件：(rear + 1) % MaxSize == front

链队

• 队空条件：front = rear = NULL

数组

数组的存储结构

一维数组

• $LOC(a_i)=LOC(a_0)+i×k \ \ \ \ (1≤i<n)$

二维数组

• 行优先：$LOC(a_{ij})=LOC(a_{00}) + (i×n + j)×k$
• 列优先：$LOC(a_{ij})=LOC(a_{00}) + (j×m + i)×k$

对称矩阵的压缩存储

• $k=\begin{cases}\frac{i(i+1)}{2}+j &i≥j时(下三角+主对角线的元素) \\ \frac{j(j+1)}{2}+i &当i<j时(a_{ij}=a_{ji})\end{cases}$

稀疏矩阵的三元组表示

• 行号、列号、元素值

递归

递归算法转换为非递归算法

迭代转换法

• 尾递归和单向递归是两种特殊类型的递归，可以采用迭代转换法将它们转换为非递归算法，即将其递归结构用循环结构来替代。
• 尾递归是递归调用语句只有一个，而且是处于算法的最后
• 单向递归是指执行过程总是朝着一个方向进行的，递归函数中虽然有一处以上的递归调用语句，但各次递归调用语句的参数只和主调用函数有关，参数相互之间无关

用栈模拟转换法

• 不能采用迭代转换法的递归算法执行中往往涉及回溯，可以采用栈来保存暂时不能执行的子问题，或者使用栈保存中间结果，称为用栈模拟转换法

  void nonrecursive(si)	//非递归算法框架
  {  将大问题状态si进栈;
     while (栈不为空)
     {  退栈一个元素s;
        if (s可以直接解决)
           直接求该问题解;
        else
        {  根据递归过程将s转换为若干个相似子问题的状态sj;
           将每个sj进栈;
        }
     }
  }

树和二叉树

树的基本术语

• 结点的度：树中每个结点具有的子树数或者后继结点数称为该结点的度
• 树的度：树中所有结点的度的最大值称之为树的度
• 分支结点：度大于0的结点称为分支结点或非终端结点。度为1的结点称为单分支结点，度为2的结点称为双分支结点，依次类推
• 叶子结点：度为零的结点称为叶子结点或终端结点
• 结点层次：树具有一种层次结构，根结点为第一层，其孩子结点为第二层，如此类推得到每个结点的层次
• 树的高度：树中结点的最大层次称为树的高度或深度

树的性质

• 树中的结点数等于所有结点的度数加1
• 度为m的树中第i层上至多有$m^{i-1}$个结点，这里应有i≥1
• 高度为h的m次树至多有$\frac{m^h-1}{m-1}$个结点
• 具有n个结点的m次树的最小高度为$\log_m[n(m-1)+1]$

二叉树的定义

• 在含n个结点的二叉树中，所有结点的度小于等于2，通常用$n_0$表示叶子结点个数，$n_1$表示单分支结点个数，$n_2$表示双分支结点个数

满二叉树

• 即一棵高度为h且有$2^{h}-1$个结点的二叉树称为满二叉树，只有度为0和度为2的结点，
• 含n个结点的满二叉树的高度为$\log_2(n+1)$，叶子结点个数为$\lfloor n/2\rfloor +1$，度为2的结点个数为$\lfloor n/2 \rfloor$

完全二叉树的特点

• 叶子结点只可能出现在最下面两层中
• 对于最大层次中的叶子结点，都依次排列在该层最左边的位置上
• 如果有度为1的结点，只可能有一个，且该结点只有左孩子而无右孩子
• 按层序编号后，一旦出现某结点（其编号为i）为叶子结点或只有左孩子，则编号大于i的结点均为叶子结点
• 具有n个（n＞0）结点的完全二叉树的高度为$\lfloor \log_2(n+1)\rfloor$或$\lfloor\log_2n\rfloor+1$

二叉树性质

• 非空二叉树上叶结点数等于双分支结点数加1。即$n_0=n_2+1$
• 非空二叉树上第i层上至多有$2^{i-1}$个结点，(i≥1)。
• 高度为h的二叉树至多有$2^{h}-1$个结点（h≥1）
• $n_1$只能是0或1，当n为偶数时，$n_1=1$，当n为奇数时，$n_1=0$

哈夫曼树

• $WPL=\sum\limits_{i=1}^{n_0}w_i\times l_i$
• 哈夫曼树中没有单分支结点
• 对于具有$n_0$个叶子结点的哈夫曼树，共有$2n_0-1$个结点

哈夫曼编码

• 规定哈夫曼树中的左分支为0，右分支为1
• 从根结点到每个叶子结点所经过的分支对应的0和1组成的序列便为该结点对应字符的编码

树/森林与二叉树的转换及还原

一棵树到二叉树的转换

• 加线：在各兄弟结点之间加一连线，将其隐含的“兄－弟”关系以“双亲－右孩子”关系显示表示出来
• 抹线：对任意结点，除了其最左子树之外，抹掉该结点与其他子树之间的“双亲－孩子”关系
• 调整：以树的根结点作为二叉树的根结点，将树根与其最左子树之间的“双亲－孩子”关系改为“双亲－左孩子”关系，且将各结点按层次排列，形成二叉树

特点

• 根结点只有左子树而没有右子树
• 左分支不变（左分支为最左孩子），兄弟变成右分支（右分支实为双亲的兄弟）
• 树中分支结点个数为m，则二叉树中无右孩子的结点个数为m+1

一棵由树转换的二叉树还原为树

• 加线：在各结点的双亲与该结点右链上的每个结点之间加一连线，以“双亲－孩子”关系显示表示出来
• 抹线：抹掉二叉树中所有双亲结点与其右孩子之间的“双亲－右孩子”关系
• 调整：以二叉树的根结点作为树的根结点，将各结点按层次排列，形成树

特点

• 根结点不变
• 左分支不变（左分支为最左孩子），右分支变成兄弟

森林与二叉树的转换及还原

森林转换为二叉树

• 转换：将森林中的每一棵树转换成二叉树，设转换成的二叉树为$bt_1、bt_2、…、bt_m$
• 连接：将各棵转换后的二叉树的根结点相连
• 调整：以$bt_1$的根结点作为整个二叉树的根结点，将$bt_2$的根结点作为$bt_1$的根结点的右孩子，将$bt_3$的根结点作为$bt_2$的根结点的右孩子，…，如此这样得到一棵二叉树，即为该森林转换得到的二叉树

二叉树还原为森林

• 抹线：抹掉二叉树根结点右链上所有结点之间的“双亲－右孩子”关系，分成若干个以右链上的结点为根结点的二叉树，设这些二叉树为$bt_1、bt_2、…、bt_m$
• 转换：分别将$bt_1、bt_2、…、bt_m$二叉树各自还原成一棵树
• 调整：将转换好的树构成森林

图

图的存储结构

邻接矩阵

邻接表

• 对图中每个顶点i建立一个单链表，将顶点i的所有邻接点链起来
• 每个单链表上添加一个表头结点（表示顶点信息）。并将所有表头结点构成一个数组，下标为i的元素表示顶点i的表头结点

特点

• 邻接表表示不唯一
• 对于有n个顶点和e条边的无向图，其邻接表有n个表头结点和2e个边结点；对于有n个顶点和e条边的有向图，其邻接表有n个表头结点和e个边结点
• 用邻接表存储图时，确定任意两个顶点之间是否有边相连的时间为$O(m)$

查找

查找的基本概念

• 静态查找表是只作查找操作的查找表，主要操作有查询某个“特定的”数据元素是否在查找表中，检索某个“特定的”数据元素及其属性
• 动态查找表是在查找过程中同时插入查找表中不存在的数据元素，或者从查找表中删除已经存在的某个数据元素

顺序查找

• $ASL_{成功}=\sum\limits_{i=0}^{n-1}p_ic_i=\frac{1}{n}\sum\limits_{i=0}^{n-1}(i+1)=\frac{1}{n}\times\frac{n(n+1)}{2}=\frac{n+1}{2}$
• $ASL_{不成功}=\sum\limits_{i=0}^{n-1}q_in=n$
• $ASL=ASL_{成功}+ASL_{不成功}\ \ \ \ (p+q=1)$

折半查找

• $ASL_{成功}=\sum\limits_{i=0}^{n-1}p_i\times level(k_i)$
• $ASL_{不成功}=\sum\limits_{i=-1}^{n-1}q_i\times (level(u_i)-1)$
• 满二叉树：$ASL_{成功}=\sum\limits_{i=0}^{n-1}p_ic_i=\frac{1}{n}\sum\limits_{j=1}^h2^{j-1}\times j=\frac{n+1}{n}\log_2(n+1)\approx\log_2(n+1)-1$

索引存储结构和分块查找

过程

• 查找索引表（有序）：可以顺序查找块，也可以二分查找块。
• 查找数据块（无序）：只能顺序查找块中元素。

性能（若有n个元素，每块中有s个元素（块数$b=\lceil n/s \rceil$））

• 折半：$ASL_{blk}=ASL_{bn}+ASL_{sq}=\log_2(b+1)-1+\frac{s+1}{2}\approx \log_2(\frac{n}{s}+1)+\frac{s}{2}$
• 顺序：$ASL^`_{blk}=ASL_{bn}+ASL_{sq}=\frac{b+1}{2}+\frac{s+1}{2}=\frac{1}{2}(\frac{n}{s}+s)+1$

二叉排序树

• 查找序列（$k_1，k_2，…，k_n$）的查找树画法是，每一层只有一个结点，首先k1为根结点，再依次画出其他结点，若$k_{i+1}<k_i$，则$k_{i+1}$的结点作为$k_i$结点的左孩子，否则作为右孩子

哈希表

• 对于两个不同的关键字$k_i$和$k_j$（$i≠j$）出现$h(k_i)=h(k_j)$，这种现象称为哈希冲突，同义词冲突

构造方法

• 直接定址法 $h(k)=k+c$
• 除留余数法 $h(k)=k\%p$
• 数字分析法

哈希冲突解决方法

• 装填因子α是指哈希表中已存入的元素数n与哈希地址空间大小m的比值，即$α=\frac{n}{m}$

开放定址法

• 线性探测法$d_0=h(k),\ d_i=(d_{i-1}+1)\% m \ \ \ \ (1≤i≤m-1)$
• 平方探测法$d_0=h(k),\ d_i=(d_0±i^2)\% m\ \ \ \ (1≤i≤m-1)$

拉链法

排序

希尔排序（不稳定）

• d=n/2
• 将排序序列分为d个组，在各组内进行直接插入排序
• 递减d=d/2，重复② ，直到d=0为止

快速排序（不稳定）

• 每趟使表的第1个元素放入适当位置（归位），将表一分为二，对子表按递归方式继续这种划分，直至划分的子表长为0或1（递归出口）

堆排序（不稳定）

• 大根堆：对应的完全二叉树中，任意一个结点的关键字都大于或等于它的孩子结点的关键字
• 最小关键字的元素一定是某个叶子结点
• 堆排序的关键是构造堆，这里采用筛选算法建堆
• 自顶向下筛选：从根结点R[low]开始向下依次查找较大的孩子结点
• 所有筛选的时间复杂度为$O(\log_2n)$

自底向上的二路归并排序

平衡归并

• 有清晰的趟数（同一趟产生的归并段优先归并）
• 归并树高度$h=\lfloor \log_2n\rfloor+1$
• 归并的趟数$h-1$