学习笔记 - 数据结构

前言

太菜了，复习恶补基础中。过了一遍《数据结构 C语言版》和《数据结构教程》记一些容易模糊的简单概念，其他的结构内容的图形表示、算法具体实现过程之类的就不必了，方便自己以后查看吧。

知识图

page1_1

绪论

数据是 客观事物的符号表示，在计算机科学中指所有能输入到计算机中并被计算机程序处理的符号的总称

数据元素 是 数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理

数据项 是 具有独立含义的数据最小单位，也称为字段或域

数据对象 是 性质相同的数据元素的集合，是数据的一个子集

数据结构 是 相互之间存在一种或多种特定关系的数据元素的集合

对于基本结构：

集合：数据元素之间除了“同属一个集合”的关系外，别无其他关系（同数学的集合概念）。
线性结构 ：数据元素之间存在一个对一个的关系。
树形结构 ：数据元素之间存在一个对多个的关系。
图状结构（网状结构） ：数据元素之间存在多个对多个的关系。

对于数据结构：

逻辑结构 ：由数据元素之间的逻辑关系构成，通常从求解问题中提炼出来。
存储结构 ：数据元素及其关系在计算机存储器中的存储表示，也称数据的 物理结构 ，也就是 逻辑结构 在计算机中的存储实现。
- 顺序存储结构（顺序映像） ：采用一组连续的存储单元存放所有的数据元素。
- 链式存储结构（非顺序映像） ：每个逻辑元素用一个内存结点存储，每个结点单独分配，所有的结点地址不一定是连续的（一般非首元元素地址由其直接前驱结点指针域给出）。
- 索引存储结构 ：存储数据元素信息的同时还建立附加的索引表，查找效率高，但索引表增加空间的开销。
- 哈希（散列）存储结构 ：根据元素是关键字通过哈希（散列）函数直接计算出一个值，并将这个值作为该元素的存储地址（哈希存储方法不存储元素之间的逻辑关系）。
运算：施加在该数据上的操作。

数据类型 是 一组性质相同的值的集合和定义在此集合上的一组操作的总称，是某种程序设计语言已实现的数据结构

抽象数据类型 是 从问题的数学模型中抽象出来的逻辑结构和逻辑结构上的运算（指一个数学模型以及定义在该模型上的一组操作）

对于抽象数据类型，一个包含其的软件模块，应包含定义表示实现部分，若按抽象数据类型的值的不同特性可分为：

原子类型 ：原子类型的遍历的值是不可分解的。
固定聚合类型 ：其值由确定数目的成分按某种结构组成。
可变聚合类型 ：与固定聚合类型相比较，值的成分的数目不确定。

多形数据类型 ：指其值的成分不确定的数据类型。

算法是 特定问题求解步骤的一种描述，是指令的有限序列，每一条指令表示一个或多个操作

有穷性 ：算法必须总是（对任何合法输入）在执行有穷步之后结束，且每一步都可在有穷时间内完成。
确定性 ：算法中每一条指令必须有确切含义，不会产生二义性；且在任何条件下，算法只有唯一的一条执行路径，对相同输入只能得到相同的输出。
可行性 ：算法是能行的，算法中描述的操作都是可以通过已经实现的基本运算执行有限次来实现的。
输入：算法有零个或多个输入，这些输入取自某个特定的对象的集合。
输出：算法有一个或多个输出，这些输出是同输入有着某种特定关系的量。

算法设计要求：

正确性 ：算法应当满足具体问题的需求。
可使用性（用户友好性） ：算法要能够很方便的使用。
可读性 ：算法主要是为了人的阅读与交流，其次才是机器执行。
健壮性 ：当输入数据非法时，算法也能适当地做出反应或进行处理，而不会产生奇怪的输出结果。
效率与低存储量需求 ：算法的执行时间，执行过程中所需要的最大存储空间尽量少。

对于算法效率度量：

事后统计方法
事前分析估算方法

对于算法时间度量，记作：T(n) = O(f(n)) ，其中，O 的形式定义为：若 f(n) 是正整数 n 的一个函数，则 Xn = O(f(n)) 表示存在一个正的常数 M ，使得当 n≥n0 时都满足 |Xn|≤M|f(n)| 。它表示随着问题规模 n 的增大，算法执行时间的增长率和 f(n) 增加率相同，称作算法的 渐进时间复杂度 ，简称 时间复杂度 。

对于算法时间复杂度有 常数阶，线性阶，平方阶，对数阶，指数阶 等等。

显然存在：O((2/3)^n) < O(2^100) < O(log2(log2(n))) < O(log2(n)) < O((log2(n))^2) < O(n^0.5) < O(n^(2/3)) < O(n/log2(n)) < O(n) < O(nlog2(n)) < O(n^(3/2)) < O((4/3)^n) < O((3/2)^n) < O(n^(log2(n))) < O(n!) < O(n^n)

一般的：O(1) < O(log2(n)) < O(n) < nlog2(n) < O(n^2) < O(2^n) < O(n!) < O(n^n)

另外：

求和定理 ：设 T1(n) 和 T2(n) 为程序段 P1 和 P2 的执行时间，并且 T1(n) = O(f(n)) ，T2(n) = O(g(n)) ，则 P1 和 P2 的总执行时间为 T1(n) + T2(n) = O(MAX{f(n),g(n)}) 。如并列循环。
求积定理 ：设 T1(n) 和 T2(n) 为程序段 P1 和 P2 的执行时间，并且 T1(n) = O(f(n)) ，T2(n) = O(g(n)) ，则 P1 和 P2 的总执行时间为 T1(n) x T2(n) = O(f(n) x g(n)) 。如多层嵌套循环。

频度是 语句重复执行的次数

算法空间复杂度 是 算法在运行过程中临时占用的存储空间大小的量度

对于算法空间复杂度，若为常数阶，称为 原地工作 或 就地工作 。

概念

线性表

线性表 是 n个数据元素的有限序列

对于线性结构的特点：

（在数据元素的非空有限集中）

存在唯一一个被称作为“第一个”的数据元素。
存在唯一的一个被称作“最后一个”的数据元素。
除第一个之外，集合中的每个数据元素均只有一个前驱。
除最后一个之外，集合中每个数据元素均只有一个后继。

顺序表 是 线性表的顺序存储结构

链表是 线性表的链式存储结构

对于链表：

单链表 ：结点中只设一个指针域用以指向直接后继元素的地址的链表。
双链表 ：结点中分别设有指向直接前驱元素的地址（头指针）和直接后继的元素的地址（尾指针）的指针域的链表。

存储密度 是 结点中数据元素本身所占的存储量和整个结点占用的存储量之比

对于链表的 头节点 的优点：

使得在首结点的插入和删除操作与其他结点一致。
无论是否为空都有一个头结点，统一了空表和非空表的处理过程。

循环链表 是 最后一个结点的指针域指向头节点，整个链表形成一个环

有序表 是 所有元素以递增或递减的方式有序排列的线性表

栈和队列

栈是 限定仅在表尾进行插入或删除操作的线性表

又称作 后进先出 的线性表。

对于栈：

栈顶：表尾端。
栈底：表头端。

顺序栈 是 采用顺序存储结构的栈

链栈是 采用链式存储结构的栈

共享栈 是 两个栈共用同一段内存空间

队列是 限定仅在表的一端进行插入，另一端进行删除的线性表

又称作 先进先出 的线性表。

对于队列：

队尾：允许插入的一端。
队头：允许删除的一端。

双端队列 是 限定插入和删除操作在表的两端进行的线性表

链队列 是 采用链式存储结构的队列

循环队列 是 类似循环链表，以便更好利用空间

串

串是 由零个或多个字符组成的有限序列

对于串：

长度：串中字符的数目。
空串：零个字符的串。
子串：一个串中任意个连续字符组成的序列。
相等：当且仅当这两个串的长度相等并且各对应位置上的字符都相同。
空格串 ：由一个或多个空格组成的串。
模式串 ：对串中子串的定位操作中的子串。

顺序串 是 采用顺序存储结构的串

链串是 采用链式存储结构的串

对串的模式匹配：

BF算法
KMP算法

递归

递归是 定义一个过程或函数时出现调用本过程或本函数的成分称为递归，其中，直接调用自身，称为 直接递归 ，若过程或函数 p 调用过程或函数 q ，而 q 又调用 p ，称为 间接递归 。

在算法设计中，任何 间接递归 都可转换为 直接递归 。

对于与递归有关：

递归数列 ：由递归关系所确定的数列。
递归过程 ：直接或间接调用自身的过程。
递归算法 ：包含递归过程的算法。
递归程序 ：直接或间接调用自身的程序。
递归方法 ：一种在有限步骤内根据特定的法则或公式对一个或多个前面的元素进行运算，以确定一系列的元素（如数或函数）的方法。

尾递归 是 递归过程或递归函数中递归调用的语句是最后一条执行的语句

一般来说，能够递归解决的问题满足：

需要解决的问题可以转换为一个或多个子问题来解，而子问题的求解问题与原问题完全相同，只是数量上的不同。
递归调用的次数必须是有限的。
必须有结束递归的条件来终止递归。

递归优点 是 结构简单、清晰，易于阅读，方便正确性证明

递归缺点 是 算法执行中占用的内存空间较多，执行效率低，不容易优化

对于递归的使用，以下情况一般使用递归：

定义是递归的 ：如阶乘，斐波那契数列等。
数据结构是递归的 ：如链表，广义表，整数，实数等。
问题求解的方法是递归的 ：如汉诺塔问题等。

递归模型 是 递归算法的抽象，反映一个递归问题的递归结构

递归出口 ：确定递归到何时结束。
递归体 ：确定递归求解的递推关系。

对于与数学归纳法的联系，数学归纳法 是一种论证方法，而递归是算法和程序设计的一种实现技术，数学归纳法 是递归求解问题的 理论基础 。一般情况下， 尾递归 算法可以通过循环或者迭代方式转换成等价非递归算法，对于不是 尾递归 的复杂递归算法，可以用栈来模拟递归执行的过程。

数组和广义表

数组是 具有相同类型的数据元素的有限序列

（在程序设计中数组是 由固定多个类型相同，具有一定次序关系的元素组成的复合数据 ）

对于数组，通常只有两种操作：

读操作 ：给定一组下标，读取相应是数组元素。
写操作 ：给定一组下标，存储或修改相应的数组元素。

对于数组的存储：

行优先存储
列优先存储

压缩存储 是 在矩阵中为多个值相同的元只分配一个存储空间；对零元不分配空间

假若值相同的元素或者零元素在矩阵中分布有一定的规律，则称为 特殊矩阵 ；反之，称为 稀疏矩阵 ，通常来说 稀疏因子 ≤ 0.05 为 系数矩阵 。

广义表 是 线性表的推广（元素可以是广义表（子表）或原子的线性表），是有限个元素的序列

对于广义表，具有以下特征：

数据元素是有相对次序的。
长度定义为最外层包含元素的个数。
深度定义为所含括弧的重数，其中原子深度为0，空表深度为1。
广义表可以被其他广义表共享，这种共享的广义表称为 再入表 。
广义表可以是自己的子表，这种广义表称为 递归表 ，递归表 的深度是 无穷值 ，长度是 有限值 。

树和二叉树

树是 由n个结点（或元素）组成的有限集合 ，其中，若 n = 0 则称为空树，若 n > 0 ，则有且仅有一个节点作为树的 根节点 。

对于树的表示法：

树形表示法
文氏图表示法
凹入表表示法
括号表示法

对于树：

结点的度/树的度 ：
- 结点的度 是 树中某个结点的子树的个数
- 树的度 是 树中所有结点的度中的最大值
分支结点/叶子结点 ：
- 分支结点 是 树中度不为零的结点
  - 单分支结点 ：度为1的分支结点。
  - n分支结点 ：度为n(n>0)的分支结点。
- 叶子结点 是 树中度为零的结点
路径/路径长度 ：
- 路径是对树中任意两个结点i和j，若存在一个结点序列（i,a,b,…,j) 且除i以外，任意结点都是其在序列中的前一个结点的直接后继结点，则称该结点序列为i到j的一条路径
- 路径长度 是 路径所通过的结点数目（序列长度）减1
结点：
- 孩子节点 是 某个结点的直接后继结点
- 双亲结点 是 某个后继结点为该结点的结点
- 兄弟结点 是 具有同一双亲结点的孩子结点
- 子孙结点 是 某个结点子树中的所有结点
- 祖先结点 是 从根节点到某个结点（除该结点外）的所有结点
层次/高度 ：根节点 层次为1，根节点 的孩子层次为2，根节点 的孩子的孩子层次为3，依次类推；树中 最大层次 称为 树的高度 。
有序/无序树 ：若树中各结点的子树按照一定次序从左向右安排，且相对次序不能随意变换，则称为 有序树 ，否则称为 无序树 。
森林：n(n>0)个互不相交的树的集合。

对于树的性质如下：

性质1 ：树中的节点数等于所有结点度数之和加 1。
性质2 ：度为 m 的树中第i层上至多有 m^(i-1) 个结点。
性质3 ：高度为 h 的 m 次树至多有 (m^h-1)/(m-1) 个结点（等比数列和取负）。
性质4 ：具有n 个结点的 m 次树的最小高度为 [logm(n(m-1)+1)]（[]为向上取整）。
性质5 ：度为 k 的树若仅有度为 k 和度为 0 的结点，则满足 n0=(k-1)nk+1 。

树的遍历分为：

先根遍历
后根遍历
层次遍历

树的存储结构为：

双亲存储结构
孩子链存储结构
孩子兄弟链存储结构

二叉树 是 一个有限的结点的集合，整个集合或为空，或由一个根结点和两棵互不相交的称为左子树和右子树的二叉树组成

对于 二叉树 和 二次树 ：

二次树 中至少由一个结点的度为2，而 二叉树 没有这种要求。
二次树 不区分左、右子树，而 二叉树 严格区分左、右子树。

满二叉树 是 在二叉树中所有的分支结点都有左孩子结点和右孩子结点，并且叶子结点都集中在二叉树的最下一层

对于满二叉树有：

叶子结点都在最下一层。
只有度为0和度为2的结点。

完全二叉树 是 在二叉树中至多只有最下面两层结点的度可以小于2，并且最下面一层的叶子结点都依次排列在该层左边的位置上

（满二叉树 是 完全二叉树 的特例）

对于完全二叉树有：

叶子结点只可能在最下面两层出现。
对于最大层次中的叶子结点，都依次排列在该层最左边位置上。
如果有度为1的结点，只可能有一个，且该节点只有左孩子无右孩子。
按层序编号时，一旦出现编号为i的结点是叶子结点或只有左孩子，则编号大于i的结点均为叶子结点。
当节点总数为奇数时，度为1的分支结点为0；当结点总数为偶数时，度为1的分支结点为1。

对于二叉树的性质：

性质1 ：非空二叉树的叶子结点数等于双分支结点树加 1。
性质2 ：非空二叉树的第 i 层上最多有 2^(i-1) 个结点。
性质3 ：高度为 h 的二叉树至多有 2^h-1 个结点。
性质4 ：对于完全二叉树中层序编号为 i 的结点 (1≤i≤n,n≥1,n为结点数) 存在：
1. 若 i≤ [n/2] （向下取整），则编号为 i 的结点为分支结点，否则为叶子结点。
2. 若 n 为奇数，则每个分支结点有既有左孩子结点，又有右孩子结点。
3. 若编号为 i 的结点有左孩子，则左孩子结点的编号为 2i ；若有右孩子，则右孩子结点编号为 2i+1 。
4. 除根节点外，若一个结点编号为 i ，则它的双亲结点编号为 [i/2] （向下取整）。
性质5 ：具有 n 个结点的完全二叉树高度为 [log2(n+1)] （向上取整），或 [log2(n)]+1 （向下取整）。

含有 n 个结点的不相似的二叉树有 1/(n+1)C(n 2n) 棵。

对于二叉树与树、森林之间的转换：

树 => 二叉树
- 树中所有相邻兄弟之间加上连线。
- 树中每个结点只保留它与长子（最左孩子）之间的连线，删除与其他孩子之间的连线。
- 以树的根节点为轴心，顺时针转动45°。
森林 => 二叉树
- 将森林中每棵树转换成相应的二叉树。
- 第一颗二叉树不懂，从第二课开始，依次把最后一棵二叉树的根节点作为前一颗二叉树根结点的右孩子。
二叉树 => 树
若某结点是其双亲的左孩子，则把该结点的右孩子、右孩子的右孩子等都与该结点的双亲结点用连线连起来。
删除原二叉树所有双亲结点与右孩子结点直接的连线。
以树的根结点为轴心，逆时针转动45°。
二叉树 => 森林
- 抹掉二叉树根结点右链上的所有结点之间”双亲-右孩子“关系，将其分成若干个以右链上的结点为根结点的二叉树。
- 分别将分成的树各自还原成一棵树。

对于二叉树的遍历有:

先序遍历
中序遍历
后序遍历
层次遍历

对于二叉树的构造有：

定理1 ：任何n(n≥0)个不同结点的二叉树，都可以由它的 中序序列 和 先序序列 唯一确定。
定理2 ：任何n(n≥0)个不同结点的二叉树，都可以由它的 中序序列 和 后序序列 唯一确定。

线索二叉树 是 若结点有左子树，则其left指向其左孩子，否则指向其前驱；若结点右孩子，则其right指向其右孩子，否则指向其后继 ，其中指向结点前驱或后继的指针称为线索，创建线索的过程称为 线索化 ；经过 线索化 的二叉树称为 线索二叉树。

对于线索二叉树可分为：

先序线索树
中序线索树
后序线索树

赫夫曼树 是 带权长度最短的树，又称最优树，树的 带权路径长度 为树中所有叶子结点的带权路径长度之和（WPL）。

并查集 是 支持查找一个元素所属的集合以及两个元素各自所属集合的合并等运算 ，用树来解决集合的查找和合并称为 并查集树

图

图是 由两个集合V和E组成，其中V为顶点有限集合，E是连接V中两个不同顶点的边的有限集合

对于图：

端点/邻接点 ：
- 无向图 ：在一个无向图中，若存在一条边 (i,j) 称顶点 i 和顶点 j 为该边的两个端点，并称它们互为 邻接点 。
- 有向图 ：在一个有向图中，若存在一条有向边（弧） <i,j> ，则称该边是顶点 i 的一条出边，同时也是顶点 j 的一条入边，其中 i 为 初始端点（起点） ，j 为 终止端点（终点） ，顶点 j 是顶点 i 的 出边邻接点 ，顶点 i 是顶点 j 的 入边邻接点 。
度：
- 无向图 ：一个顶点所关联的边的数目称为该顶点的度。
- 有向图 ：以顶点 j 为终点的边的数目称为顶点 j 的入度，以顶点 i 为起点的边的数目称为顶点 i 的出度，一个顶点的入度和出度之和为该顶点的度。
其中，一个图所有顶点的度之和等于边数的两倍。
完全图 ：
- 无向图 ：每两个顶点之间都存在一条边，总边数为 n(n-1)/2 。
- 有向图 ：每两个顶点之间都存在着方向相反的两条边，总边数为 n(n-1) 。
稠密图/稀疏图 ：
- 稠密图 ：接近完全图的图。
- 稀疏图 ：含有较少的边数（如 e<nlog2(n)）。
子图：对于两个图 G=(V,E) 和 G1=(V1,E1) ，若 V1 是 V 的子集，且 E1 也是 E 的字节，称 G1 是 G 的子图。
路径/路径长度 ：
- 路径：即从顶点 i 到顶点 j 所经过的顶点序列。
  - 无向图 ：(i,a)(a,b)(...,...)(u,j)
  - 有向图 ：<i,a><a,b><...,...><u,j>
- 路径长度 ：一条路径上经过的边的数目。
若一条路径上除了起点和终点可以相同外，其余顶点均 不相同 ，则称该路径为 简单路径 。
回路（环） ：若一条路径上的起点和终点为同一顶点，则此路径称为回路或环。

同 简单路径 ，也有对应的 简单回路 或 简单环 。
连通/连通分量 ：在无向图中，若从顶点 i 到顶点 j 有路径，则称顶点 i 到顶点 j 是连通的，若任意两个顶点都是连通的，则称该图为 连通图 ，否则为 非连通图。

无向图的 最大连通子图 称为 连通分量 。
强连通/强连通分量 ：在有向图中，若任意两个顶点都连通，则称该图为 强连通图 。

有向图的 最大连通子图 称为 强连通分量 。
权/网 ：边上带有权的图称为 带权图 ，也称作网。

对于连通分量，显然对 连通图 只有一个 连通分量 ；对 强连通图 仅有一个 强连通分量 。

在 非强连通图 中找强连通分量的方法：

在图中找有向环。
扩展该有向环，若某个顶点到该环中任一顶点有路径，并且该环中人一顶点到这个顶点也有路径，则加入这个顶点。

（另一种方法是设有三个集合 Z ，S 和 D ，其中集合 D 为所有顶点 D={a,b,c,d,...} ；将任意一个顶点（不失一般性可以先取 a ）加入至集合 S={a} 中，然后对顶点 a 采用 深度优先遍历 ，并将遍历得到的顶点加入 Z 中，可得 Z={c,e,g,...,v} ；在集合 Z 中从最后一个顶点（如取 v ），并对顶点 v 采用 深度优先遍历 ，若在遍历过程中可到达集合 S 中的任一结点，则加入 S ，直至集合 Z={空} ，此时 S={a,e,g...} 即可得到一个 强连通分量 ；接着求集合 D 与集合 S 的差集，并将集合 S 清空，以此类推重复做上述直至 D={空} 。）

图的存储结构为：

邻接矩阵
邻接表/逆邻接表
十字链表（有向图）
邻接多重表（无向图）

图的遍历为：

深度优先遍历
广度优先遍历

最小生成树 是 图的所有生成树具有边上的权值之和最小的树

深度优先生成树 ：由深度优先遍历得到的生成树。
广度优先生成树 ：由广度优先遍历得到的生成树。

对于最小生成树准则：

必须只是用该图中的边来构造最小生成树。
必须使用且仅使用 n-1 条边来连接图中的 n 个顶点。
不能使用产生回路的边。

生成森林 是 对于非连通图，每个连通分量中的顶点集和遍历时走过的边一起构成的一棵生成树，各个连通分量的生成树组成非连通图的生成森林

最小生成树算法：

普利姆算法（对顶点，与边无关，适合稠密图）
克鲁斯卡尔算法（对边，与顶点无关，适合稀疏图）

最短路径算法（只能用以计算权值＞0的图（网））：

狄克斯特拉算法（顶点对其余各顶点）
弗洛伊德算法（各对顶点之间）

拓扑排序 是 在一个有向图中找一个拓扑排序的过程

对于拓扑排序，方法如下

从有向图中选择一个没有前驱（入度为0）的顶点并且输出它。
从图中删去该顶点，并且删去从该顶点发出的全部有向边。
重复上述两步，直到剩余的图中不再存在没有前驱的顶点为止。

若图中全部顶点被输出，则说明该图不存在回路，否则至少存在一条回路。

若以 有向无环图 描述工程的预计进度，以顶点表示事件，以有向边表示活动，边的权表示完成活动时间，则入度为0的顶点表示 开始事件 ，出度为0的顶点表示 结束事件 ，这样的图称为表示活动的网，即 AOE 网。

在 AOE 网中，通常只有一个入度为0的点（否则可设一个虚点将多个入度为0的点通过权为0的边连接），称为源点，和一个出度为0的点，称为汇点。

关键路径 是 在AOE网中，从源点到汇点的所有路径中具有最大路径长度的路径

查找

查找表 是 同一类型数据元素（记录）构成的集合

对于查找操作：

查询某个特定的数据元素（记录）是否在查找表中。
检索某个特定的数据元素（记录）的各种属性。
在查找表中插入一个数据元素（记录）。
在查找表中删除一个数据元素（记录）。

其中，动态查找表 只能进行 1 和 2 统称为”查找“的操作，而 动态查找表 不仅能进行 1 和 2 操作，还能在查找表中插入、删除元素。

关键字 是 数据元素（记录）中某个数据项的值，用它可以标识（识别）一个数据元素（记录）

主关键字 ：可以唯一的标识一个记录（对不同记录，其主关键字均不同）。
次关键字 ：用以标识若干记录的关键字。

查找是 根据给定的某个值，在查找表中确定一个其关键字等于给定值的记录或数据元素

查找成功 ：表中存在这样的一个记录。
查找失败 ：表中不存在这样的一个记录。

对于查找表：

静态查找表 ：
- 顺序查找 ：从后往前找，平均查找长度为 (n+1)/2 。
- 折半查找 ：需关键字有序，l=1,h=n;m=(l+h)/2 依次减半，直到 m=k 或 l>h 未找到，平均查找长度为 (n+1)/nlog2(n+1)-1 近似于 log2(n+1)-1 。
- 索引顺序查找 ：设查找表中共有 n 个数据元素，将所查找关键字分为 b 块，每块 s 个数据元素，且用 {块首数据元素开始索引，块最大数据元素值} 作为索引表，确保每块数据元素尽量有序，以块为单位必须有序（左块最大数据元素小于右块最小数据元素）。
  - 若对 索引表 采用 顺序查找 ：平均查找长度为 (b+1)/2+(s+1)/2 ，若块长 s=√n（数据元素总数的平方根），则平均查找长度为 √n+1 。
  - 若对 索引表 采用 折半查找 ：平均查找长度 ≈log2((n/s)+1)+(s/2) 。
- 插入查找 ：i=(k-[最小关键字)/([最大关键字]-[最小关键字])*([最大关键字]-[最小关键字]+1) ，进行 key 和 i 比较查找。
- 斐波那契查找 ：查找表长度为 F[u]-1 ，F 为斐波那契数列其中一项，取 F[u-1] 与 k 比较，若 k<F[u-1] 取 1->F[u-1]-1 依个比较，若 k>F[u-1]，则取 F[u-1]+1->F[u]-1 依个比较（相当于用前 n 个相邻斐波那契数列值相加或相减求出差值部分的可能值），平均性能比折半查找好，但最坏情况比折半查找差。
- 次优查找树（静态树表）查找 ：近似生成带权路径长度之和最小值的二叉树，靠 P[i]=|Σ[i+1 -> h] - Σ[l -> i-1]| ，取 P[i]=min{P[i∈[l,h]]} ，其中 l≤i≤h，h-l=[当前段关键字数量] ，可得到大值上浮，小值下沉，且 左<根 ，右>根 的二叉树，平均查找长度为 Kln(n)（与 log(n) 成正比）。
动态查找表 ：
- 二叉排序树 ：或空树；或左子树不为空，则左子树上所有结点值均<根结点的值，右子树不为空，则右子树所有结点的值均>根节点的值，其左、右子树也为二叉排序树（中序遍历得到关于树结点值的升序序列）。
- 平衡二叉树 ：或空树；或左、右子树都是平衡二叉树，左、右子树深度之差绝对值≤1（ 平衡因子=(-1[左子树层深],0[左、右子树同层],1[右子树层深]) ）
  
  平衡二叉树的构造：
  - (LL) 根的左子树的左子树插入结点导致根的 平衡因子 由 1 变 2 ；处理方法 是 根的左边接根的左子树的右子树，根的左子树的右边接根（单向右旋）。
  - (RR) 根的右子树的右子树插入结点导致根的 平衡因子 由 -1 变 -2 ；处理方法 是 根的右边接根的右子树的左子树，根的右子树的左边接根（单向左旋） 。
  - (LR) ：根的左子树的右子树插入结点导致根的平衡因子由 1 变 2 ；处理方法 是先单向左旋，后单向右旋，根的左子树的右边接根的左子树的右子树的左子树，根的左边接根的左子树的右子树的右子树，根的左子树的右子树的左边接根的左子树，根的左子树的右子树的右边接根。
  - (RL) ：根的右子树的左子树插入结点导致根的 平衡因子 由 -1 变 -2；处理方法 是先单向右旋，后单向左旋，根的右子树的左边接根的右子树的左子树的右子树，根的右边接根的右子树的左子树的左子树，根的右子树的左子树的左边接根，根的右子树的左子树右边接根的右子树。
- B-树：或空树；或一颗 m 阶树满足：
  - 树中每个分支结点最多有 m 棵子树。
  - 若根结点不是叶子结点，至少 2 棵子树。
  - 除根外所有非终端节点至少 [m/2]（向上取整）棵子树。
  - 所有非终端结点包含：(n,A[0],K[1],A[1],K[2],A[2],...,K[n],A[n]) ，其中 K[1->n] 为关键字，A[0->n] 为指向子树根结点的指针域，且 A[i] 所指子树所有根结点关键字均小于 K[i] ，A[i+1] 所指子树所有根节点关键字均大于 K[i] 。
  - 每个结点关键字不少于 [m/2]（向上取整），但不大于 m-1 。
  - 每个结点子树为其关键字数量加 1 。
- B+树：或空树；或一颗 m 阶树满足：
  - 每个分支结点最多有 m 棵子树。
  - 根结点或者没有子树，或者最少有 2 棵子树。
  - 除根结点外，其他每个分支结点最少有 [m/2] （向上取整）棵子树。
  - 有 n 棵子树的结点有 n 个关键字。
  - 所有叶子结点包含全部关键字及指向相应记录的指针，而且叶子结点按关键字大小顺序链接（B+树实际是更高级的索引顺序查找模式）。
  - 所有分支结点中仅包含它的各个子结点中最大的关键字以及指向子结点的指针（用作索引项）。
- 键树：又称数字查找树，度≥2的树，每个结点包含有组成关键字的符号。
  - 存储结构1 ：孩子兄弟链（双链树），3 个域，标志域 存放关键字一个字符，first域 指向第一棵子树结点（叶子结点存储指向该关键字记录的指针），next域 指向有兄弟指针。
  - 存储结构2 ：又称作tire树，每个结点有 d 个指针域，d 为关键字不重复的字符数量，如纯数字为 11 ，纯小写字母为27 ；分支节点有 d 个指针域和 d 个指针域中非空指针个数的整数域，叶子结点含有关键字域和指向记录的指针域。

对于 m 阶 B-树 和 B+树 区别在于：

在 B+树 中，具有 n 个关键字的结点有 n 棵子树，即每个关键字对应一棵子树；而在 B- 树中，具有 n 个关键字的结点含有 n+1 棵子树。
在 B+树中 ，除根结点外，每个结点中的关键字个数 n 的取值范围是 [m/2]（向上取整）≤ n ≤ m ，根结点 n 的取值范围是 2 ≤ n ≤ m ；而在 B- 树中，除根结点外，其他所有非叶子结点的关键字个数 n 有 [m/2]-1 （向上取整）≤ n ≤ m-1 ，根结点 n 的取值范围是 1 ≤ n ≤ m-1 。
在 B+树 中，所有叶子结点包含了全部关键字，即其他非叶子结点中的关键字包含在叶子结点中；而在 B- 树中，关键字是不重复的。
在 B+树 中，所有非叶子结点仅起到索引的作用，即结点中的每个索引项只含有对应子树最大关键字和指向该子树的指针，不含有该关键字对应记录的存储地址；而在 B- 树中，每个关键字对应一个记录的存储地址。
在 B+树 中，通常有两个头指针，一个指向根结点，一个指向关键字最小的叶子结点，所有叶子结点链接成一个不定长的有序线性链表。因此在 B+树 中可以进行 随即查找 和 顺序查找；而在 B- 树中，只能进行 随机查找。

哈希表 是 设定一个哈希函数和处理冲突的方法将一组关键字映像到一个有限连续的地址集上，并以关键字在地址集上的像作为记录在表中的存储位置

设定一个哈希函数和处理冲突的方法，将一组关键字映像到地址集上的过程称为 哈希造表 ，或散列，所得存储位置称为 哈希地址 ，或 散列地址 。

不同关键字可能得到同一哈希地址，称为冲突，冲突可以 尽可能的少 ，但 不可避免 。具有相同哈希值的关键字称为 同义词 。

哈希函数构造方法：

直接定址法 ：取关键字或关键字的线性函数（又称自身函数）。
数字分析法 ：需知道可能出现的关键字，取不会出现的关键字的组合。
平方取中法 ：取关键字平方的中间几位。
折叠法 ：将关键字分割成位数相同的及部分，取这几部分叠加和（舍去进位，分为 移位叠加 [最低位对齐叠加] ， 间界叠加 [从一端到另一端沿分割界来回叠加,如 abc-qwe-zxc -> abc+ewq+zxc ]）。
除留余数法 ：直接模质数（通常≤表长），或不含 20 以内质因子的合数。
随机函数法 ：选定随机函数得到的随机值。

处理冲突方法：

开放定址法：
- 线性探测再散列 ：若发生冲突则+1并模表长度，易发生“二次聚合”（后一次哈希值和前一次线性再散列的值一致的冲突），必能填满。
- 二次探测再散列 ：若发生冲突则 ×1,×-1,×2,×-2... 等，需表长为形如 4j+3 （j为整数）的素数时才有可能填满。
- 随机探测再散列 ：若发生冲突则通过随机函数再分配哈希值，不一定能填满，取决于伪随机数列。
再哈希法 ：若发生冲突则用另一个哈希函数进行计算，再发生冲突则用第二个哈希函数进行计算…以此类推，不易产生二次聚合。
链地址法 ：类似图的邻接表，哈希值作为图顶点，同义的关键字作为接在哈希值后面的尾巴的链表。
建立公共溢出区 ：若发生冲突则将冲突内容放到另一个表中。

排序

排序是 将一个数据元素（记录）的任意序列，重新排列成一个按关键字有序的序列

内部排序 ：待排序记录存放在计算机随机存储器中进行的排序过程。
外部排序 ：待排序记录数量很大，以致内存一次不能容纳全部记录，在排序过程中尚需对外存进行访问的排序过程。

若在一次排序前序列中值相同的两个数据的相对位置（领先或落后）在排序后没有发生改变，则该排序方法是 稳定的 ，否则是 不稳定的 。

排序方法可分为：

插入排序 ：直接插入排序，希尔排序。
交换排序 ：起泡排序，快速排序。
选择排序 ：简单选择排序，堆排序。
归并排序 ：二路归并排序。
基数排序 ：对字符或数字等。

对于排序过程工作量可分为：

简单排序方法 ：时间复杂度为 O(n^2) 。
先进排序方法 ：时间复杂度为 O(nlogn) 。
基数排序 ：时间复杂度为 O(d×n) 。

各种排序方法性能：

排序方法	平均情况	最坏情况	最好情况	空间复杂度	稳定性	复杂性
直接插入排序	O(n^2)	O(n^2)	O(n)	O(1)	稳定	简单
折半插入排序	O(n^2)	O(n^2)	O(n)	O(1)	稳定	简单
希尔排序	O(n^1.3)			O(1)	不稳定	较复杂
起泡冒起	O(n^2)	O(n^2)	O(n)	O(1)	稳定	简单
快速排序	O(nlog2(n))	O(n^2)	O(nlog2(n))	O(log2(n))	不稳定	较复杂
简单选择排序	O(n^2)	O(n^2)	O(n^2)	O(1)	不稳定	简单
堆排序	O(nlog2(n))	O(nlog2(n))	O(nlog2(n))	O(1)	不稳定	较复杂
二路归并排序	O(nlog2(n))	O(nlog2(n))	O(nlog2(n))	O(n)	稳定	较复杂
基数排序	O(d(n+rd))	O(d(n+rd))	O(d(n+rd))	O(rd)	稳定	较复杂

磁带是 顺序存取设备，通过读写头读写数据

磁盘是 直接存取的外存设备，不仅能够进行顺序存取，而且能直接存取任何记录，存取速度比磁带快

对于磁带，读写一块信息所需时间由两部分组成：

延迟时间 ：读写头到达传输信息所在物理块起始位置所需时间。
传输时间 ：传输字符的时间。

对于磁盘，读写一块信息所需时间由三部分组成：

寻查时间 ：读写头定位的时间。
等待时间 ：等待信息块的初始位置旋转到读写头下的时间。
传输时间 ：传输字符的时间。

外部排序 的基本方法是 归并排序 ，分为以下两个步骤：

生成若干初始归并段（顺串） ：将一个文件（含待排序的数据）中的数据分段读入内存，在内存中对其进行内排序，并将经过排序的数据段（有序段）写到多个外存文件上。
多路归并 ：对这些初始归并段进行多遍归并，使得有序的归并段逐渐扩大，最后在外存上形成整个文件的单一归并段，也就完成了外排序。

外部排序所需的 总时间 为 内部排序（产生初始归并段）所需的时间 + 外部信息读写时间 + 内部归并所需的时间 。

败者树 是 树形选择排序的一种变型，即逐步淘汰出最小值

对于 败者树 和堆区别：败者树 是由 n 个叶子组成的完全二叉树；而堆可看作 n 个结点的完全二叉树。

在属性选择排序的基础上得来的 置换-选择排序 ，其特点是 在整个排序（得到所有初始归并段）的过程中，选择最小（或最大）关键字和输入、输出交叉或平行进行 。

对于多路平衡归并，以 二路平衡归并 为例，显然每一趟可以从 m 个归并段中得到 [m/2] （向上取整）个归并段，那么这样的归并树就有 [log2(m)]+1（向上取整）层。相应的，对 k 路归并，也就有 [logk(m)]+1（向上取整）层。而最佳归并树，对应的应该为 k 阶的赫夫曼树。

对于 k 阶赫夫曼树（最佳归并树），仅存在度为 0 或为 k 的结点，因而若需要生成相应的赫夫曼树，可能得附加 k - [(m-1) mod (k-1) + 1] 个虚段。

在 磁带排序 中，若进行 k 路归并则需要 k+1 台磁带。

附录

以下是个人对结构的一些书写习惯，假设数据元素的类型为 int 。

1	typedef int entry;

排序算法

对一些排序算法的实现：

1，插入排序

直接插入排序

void insert_sort(entry a[], int n){
    
    entry p;
    int i;
    
    for(int u = 1;u < n;u++){
        if(a[u] < a[u-1]){
            p = a[u];
            i = u - 1;
            while(i >= 0 && a[i] > p){
                a[i + 1] = a[i];
                i--;
            }
            a[i + 1] = p;
        }
    }
    
}

折半插入排序

void insert_sort2(entry a[], int n){
    
	entry p;
    int l,h,m;
    
    for(int u = 1;u < n;u++){
        l = 0, h = u;
        p = a[u];
        while(l < h){
            m = (l + h)/2;
            if(a[m] >= p){
                h = m - 1;
            }else{
                l = m + 1;
            }
        }
        for(int i = u;i > h + 1;i--){
            a[i] = a[i - 1];
        }
        a[h + 1] = p;
    }
    
}

希尔排序

void shell_sort(entry a[], int n){
    
	entry p;
    int i;
    
    for(int d = n/2; d > 0; d/=2){
        for(int u = d;u < n;u++){
            p = a[u];
            i = u - d;
            while(i >= 0 && a[i] > p){
                a[i + d] = a[i];
                i = i - d;
            }
            a[i + d] = p;
        }
    }
    
}

2，选择排序

简单选择排序

void select_sort(entry a[], int n){
    
	int m;
    entry p;
    
    for(int u = 0;u<n - 1;u++){
        m = u;
        for(int i = u + 1;i < n;i++){
            if(a[i] > a[m]){
                m = i;
            }
        }
        if(m != u){
            p = a[m];
            a[m] = a[u];
            a[u] = p;
        }
    }
    
}

堆排序

void heap_adjust(entry a[],int k, int n){
    
	entry p = a[k - 1];
    
	for(int s = k*2;s <= n;s *= 2){
		if(s + 1 <= n && a[s] > a[s - 1])
			s++;
		if(p >= a[s - 1]){
            break;
        }
            a[k - 1] = a[s - 1];
            k = s;
	}
    a[k - 1] = p;
    
}
void heap_sort(entry a[], int n){
    
    entry p;
    
    for(int i = n/2;i >= 1;i--){
        heap_adjust(a,i,n);
    }
    
    while(n > 2){
        p = a[0];
        a[0] = a[n - 1];
        a[n - 1] = p;
        heap_adjust(a,1,--n);
    }
    
}

3，交换排序

起泡排序

void bubbling_sort(entry a[], int n){
    
	bool exchange;
    entry p;
    int i = n;
    
    while(i-- > 1){
        exchange = false;
        for(int u = 0;u < n-1; u++){
            if(a[u] > a[u + 1]){
                p = a[u];
                a[u] = a[u + 1];
                a[u + 1] = p;
                exchange = true;
            }
        }
        if(!exchange){
            break;
        }
    }
    
}

快速排序

void quick_sort(entry a[],int l, int h){
    
    if(l < h){
        entry p = a[l];
        int i = l,k = h;
        while(i < k){
            while(i < k && a[k] >= p){
                k--;
            }
            a[i] = a[k];
            while(i < k && a[i] <= p){
                i++;
            }
            a[k] = a[i];
        }
        a[i] = p;
        quick_sort(a,l,i - 1);
        quick_sort(a,i + 1,h);
    }
    
}

快速排序（非递归）

struct pos{
    int l,h;
};
void quick_sort2(entry a[], int n){
    
	pos *st = (pos*)malloc(sizeof(pos)*n); // 理论上只需要log2(n)大小
    pos ps;
    entry p;
    int i,k;
    int sp = -1;
    
    st[++sp] = {0,n - 1};
    while(sp != -1){
        ps = st[sp--];
        i = ps.l,k = ps.h;
        p = a[i];
        while(i < k){
            while(i < k && a[k] >= p){
                k--;
            }
            a[i] = a[k];
            while(i < k && a[i] <= p){
                i++;
            }
            a[k] = a[i];
        }
        a[i] = p;
        if(i - 1 - ps.l > 0){
            st[++sp] = {ps.l,i - 1};
        }
        if(ps.h - (i + 1) > 0){
            st[++sp] = {i + 1,ps.h};
        }
    }
    free(st);
    
}

4，归并排序

二路归并排序

void merge_invoke(entry a[], entry d[], int l, int h){
	
    if(h <= l)
        return;
    
    int s1,e1,m,s2,e2;
    int k = 0;
    m = (l + h)/2;
    s1 = l,e1 = m;
    s2 = m+1,e2 = h;
    
    merge_invoke(a,d,s1,e1);
    merge_invoke(a,d,s2,e2);
    
    while(s1 <= e1 && s2 <= e2){
        d[k++] = a[s1] < a[s2] ? a[s1++] : a[s2++];
    }
    while(s1 <= e1){
        d[k++] = a[s1++];
    }
    while(s2 <= e2){
        d[k++] = a[s2++];
    }
    while(--k >= 0){
        a[l + k] = d[k];
    }
    
}

void merge_sort(entry a[], int n){
    
    entry *d = (entry*)malloc(sizeof(entry)*n);
   	
    merge_invoke(a,d,0,n - 1);  	
    free(d);
    
}

二路归并排序（非递归）

void merge_sort2(entry a[], int n){

	entry *d = (entry*)malloc(sizeof(entry)*n);
	int s1,e1,m,s2,e2,len;
	int k;
    
    for(int b = 1;b <= n;b *= 2){
        len = b*2 - 1;
        for(int i = 0; i < n - 1; i += len + 1){
			s1 = i, e2 = i + len;
			if(e2 >= n){
				e2 = n - 1;
			}
			m = i + (len - 1)/2;
			e1 = m,s2 = m + 1;
            k = 0;
            
            while(s1 <= e1 && s2 <= e2){
                d[k++] = a[s1] < a[s2] ? a[s1++] : a[s2++];
            }
            while(s1 <= e1){
                d[k++] = a[s1++];
            }
            while(s2 <= e2){
                d[k++] = a[s2++];
            }
            
            while(--k >= 0){
                a[i + k] = d[k];
            }
        }
    }
    
    free(d);
    
}

5，基数排序

字符排序

#define LEN 26 // a b c ... z

struct pos{
    char *d;
    int next;
};

void allocation(pos ps[], int f[], int t[], int k){
    
    int index;
    
    for(int i = 0;i < LEN;i++){
        f[i] = t[i] = 0;
    }
    
    for(int i = ps[0].next;i != 0;i = ps[i].next){
        index = ps[i].d[k] - 'a';
        if(f[index] == 0){
            f[index] = i;
        }else{
            ps[t[index]].next = i;
        }
        t[index] = i;
    }
    
    ps[t[index]].next = 0;
    
    
}

void collection(pos ps[], int f[], int t[], int n){
    
    int k = 0;
    while(f[k] == 0){
        k++;
    }
    ps[0].next = f[k];
    
    for(int i = k + 1;i < LEN;i++){
        if(f[i] != 0){
            ps[t[k]].next = f[i];
            k = i;
        }
    }
    
    ps[t[k]].next = 0;
    
}

void base_sort(char *a[], int n, int len){
    
    pos *ps = (pos*)malloc(sizeof(pos)*(n + 1));
    int *f = (int*)malloc(sizeof(int)*LEN);
    int *t = (int*)malloc(sizeof(int)*LEN);
    
    for(int i = 1;i <= n;i++){
        ps[i] = {a[i-1],i + 1};
    }
    ps[n].next = 0;
    ps[0].next = 1;
    
    for(int i = len - 1;i >= 0;i--){
        allocation(ps,f,t,i);
        collection(ps,f,t,n);
    }
    
    for(int i = ps[0].next;i != 0;i = ps[i].next){
        printf("%s\n",ps[i].d);
    }
    
    
}

6，k路置换-选择排序

#define MAX 10000
#define MIN (-10000)
struct pos{
	entry w;
	int l;
};

void adjust(pos L[], int R[], int i, int k){
    int t = (i + k)/2;
    int p;
    while(t > 0){
        if(L[i].l > L[R[t]].l || (L[i].l == L[R[t]].l && L[i].w > L[R[t]].w)){
            p = i;
            i = R[t];
            R[t] = p;
        }
        t /= 2;
    }
    R[0] = i;
}

void init(pos L[], int R[], int k){
    
    L[k] = {MIN,-1};
    for(int i = 0;i < k;i++){
        R[i] = k;
    }
    for(int i = k - 1;i >= 0;i--){
        adjust(L,R,i,k);
    }
    
}

void run(entry a[], int k){
    
    pos *L = (pos*)malloc(sizeof(pos)*(k + 1));
    int *R = (int*)malloc(sizeof(int)*k);
    int u,q,w,l,h;
    
    u = h = 0;
    
    for(int i = 0;i < k;i++){
        L[i] = {a[u++],0};
    }
    
    init(L,R,k);
    
    while((w = L[R[0]].w) != MAX){
        q = R[0],l = L[q].l;
        if(l > h){
            printf("\n");
            h = l;
        }
        printf(" %d ",w);
        
        L[q] = {a[u],a[u] < w ? l + 1 : l};
        adjust(L,R,q,k);
        u++;
    }
    
    free(L);
    free(R);
    
}

基本结构

一些基本的结构：

1，线性表

顺序表示：

#define MAX 10000
struct line{
	entry d[MAX];
    int len;
};

链式表示：

struct link{
    entry d;
 	link *n;	   
};

2，栈

顺序栈表示：

#define MAX 10000
struct st{
	entry d[MAX];
	int sp;
};

链栈表示：

struct lst{
	entry d;
    lst *n;
};

共享栈表示：

#define MAX 10000
struct sst{
	entry d[MAX];
    int sp,dp;
};

3，队列

顺序队表示：

#define MAX 10000
struct qs{
	entry d[MAX];
	int f,r;
};

链队表示：

struct lqs{
	entry d;
	lqs *f,*r;
}

4，串

顺序串表示：

1 2	#define LEN 1000 typedef char str[LEN + 1];

堆串表示：

struct hstr{
	char *d;
	int len;
};

块串表示：

#define BLOCK 100
struct bstr{
	char d[BLOCK];
    bstr *n;
};
struct hbstr{
    bstr *h,*t;
    int *len;
};

5，广义表

矩阵三元组：

#define M 100
struct point{
	entry w;
    int r,c;
};
struct tg{
    point d[M];
    int r,c;
    int n;
};

稀疏矩阵的十字链表表示：

struct point{
	entry w;
	int r,c;
	point *down, *right;
};
struct vtv{
    point *rh, *ch;
    int r,c;
    int n;
};

广义表头尾链表示：

struct gt{
	int tag;
	union{
		entry d;
		struct{
			gt *down, *right;
		}p;
	};
};

广义表扩展性链表表示：

struct gt{
	int tag;
    union{
  		entry d;
        gt *down;
    }
    gt *right;
};

6，树

双亲表示法：

#define MAX 10000
struct pt{
	entry d;
	int p;
};
struct ptr{
	ptl d[MAX];
	int r,n;
};

孩子表示法：

#define MAX 10000
struct ctl{
	int i;
	cbtl *n;
};
struct ct{
	entry d;
	cbtl *h;
};
struct ctr{
    cbt d[MAX];
    int r,n;
};

孩子-兄弟表示法：

struct cbt{
	entry d;
    cbt *down, *right;
};

二叉树：

struct bt{
	entry d;
	bt *left, *right;
};

线索二叉树：

struct tbt{
	int ltag, rtag;
	entry d;
	tbt *left, *right;
};

并查集树：

struct at{
	int p;
	int l;
};

7，图

邻接矩阵：

#define M 100
struct vp{
	int w;
};
struct GV{
    vp d[MAX];
    int n,e;
};

邻接表：

struct gnode{
	int i;
	int w;
	gnode *n;
};
struct hgnode{
	int no;
	gnode *n;
};
struct G{
	hgnode *d;
	int n,e;
};

十字链表：

struct vnode{
	int in,out;
	int w;
	vnode *f,*t;
}
struct hvnode{
	int no;
	vnode *in, *out;
};
struct GT{
    hvnode *d;
    int n,e;
};

邻接多重表：

struct dnode{
	int in,out;
	int w;
	dnode *a, *b;
};
struct hdnode{
	int no;
	dnode *arc;
};
struct GD{
	hdnode *d;
	int n,e;
};

8，B-树

#define M 5
struct Bat{
	int keynum;
	Bat *parent;
	int key[M + 1];
	Bat *down[M + 1];
	entry *recod[M + 1];
};
struct Result{
	bool found;
    int index;
    Bat *p;
};

9，B+树

#define M 5
struct Bdt{
	int tag;
	int keynum;
	Bdt *parent;
	int key[M];
	union{
		Bdt *down[M];
		struct {
			entry *record[M];
			Bdt *n;
		}L;
	}
};
struct Result{
	bool found;
	int index;
	Bdt *p;
};

10，键树

孩子兄弟链表示：

#define LEN 30
struct key{
	char d[LEN];
	int len;
};
struct Kt{
    int tag;
	char symbol;
	union{
		entry *record;
		Kt *down;
	}
	Kt *right;
};

Tire树：

#define LEN 26 // a,b,c,...,z
struct Tt{
    int tag;
    union{
        struct {
            Tt *down[LEN];
            int num;
        }bh;
        struct {
            int key;
            entry *record;
        }lf;
    };
};

11，哈希表

开放定址法：

struct ht{
	int *key;
    int *find;
    int p,n;
};

链地址法：

struct lnode{
	int key;
    lnode *n;
}
struct ht{
  	lnode *h;
};

后话

从3月21号开始，摸了一个月多，这玩意应该是唯一能感受到ak快感的正式课了（笑）。往后继续。另外，~~小审判是我的！~~。

如果您喜欢此博客或发现它对您有用，则欢迎对此发表评论。也欢迎您共享此博客，以便更多人可以参与。如果博客中使用的图像侵犯了您的版权，请与作者联系以将其删除。谢谢！

学习笔记 - 数据结构

学习笔记 - 数据结构

前言

知识图

绪论

概念

线性表

栈和队列

串

递归

数组和广义表

树和二叉树

图

查找

排序

附录

排序算法

基本结构

后话

标签

朋友们