小妮子乖乖81
第六章 树 树是n个结点的有限集合，非空时必须满足：只有一个称为根的结点；其余结点形成m个不相交的子集，并称根的子树。 根是开始结点；结点的子树数称度；度为0的结点称叶子（终端结点）；度不为0的结点称分支结点（非终端结点）；除根外的分支结点称内部结点； 有序树是子树有左，右之分的树；无序树是子树没有左，右之分的树；森林是m个互不相交的树的集合； 树的四种不同表示方法：·树形表示法；·嵌套集合表示法；·凹入表示法·广义表表示法。 二叉树的定义：是n≥0个结点的有限集，它是空集（n=0）或由一个根结点及两棵互不相交的分别称作这个根的左子树和右子树的二叉树组成。 二叉树不是树的特殊情形，与度数为2的有序树不同。 二叉树的4个重要性质： ·。二叉树上第i层上的结点数目最多为2^（i-1）（i≥1）。； ·深度为k的二叉树至多有（2^k）-1个结点（k≥1）； ·。在任意一棵二叉树中，若终端结点的个数为n0，度为2的结点数为n2，则n0=n2+1； ·。具有n个结点的完全二叉树的深度为int（log2n）+1. 满二叉树是一棵深度为k，结点数为（2^k）-1的二叉树；完全二叉树是满二叉树在最下层自右向左去处部分结点； 二叉树的顺序存储结构就是把二叉树的所有结点按照层次顺序存储到连续的存储单元中。（存储前先将其画成完全二叉树） 树的存储结构多用的是链式存储。BinTNode的结构为lchild|data|rchild，把所有BinTNode类型的结点，加上一个指向根结点的BinTree型头指针就构成了二叉树的链式存储结构，称为二叉链表。它就是由根指针root确定的。共有2n个指针域，n+1个空指针。 根据访问结点的次序不同可得三种遍历：先序遍历（前序遍历或先根遍历），中序遍历（或中根遍历）、后序遍历（或后根遍历）。时间复杂度为O（n）。 利用二叉链表中的n+1个空指针域来存放指向某种遍历次序下的前趋结点和后继结点的指针，这些附加的指针就称为“线索”，加上线索的二叉链表就称为线索链表。线索使得查找中序前趋和中序后继变得简单有效，但对于查找指定结点的前序前趋和后序后继并没有什么作用。 树和森林及二叉树的转换是对应的。 转换方法： ·树变二叉树：兄弟相连，保留长子的连线。 ·二叉树变树：结点的右孩子与其双亲连。 ·森林变二叉树：树变二叉树，各个树的根相连。 树的存储结构：·有双亲链表表示法：结点data | parent，对于求指定结点的双亲或祖先十分方便，但不适于求指定结点的孩子及后代。 ·孩子链表表示法：为树中每个结点data | next设置一个孩子链表firstchild，并将data | firstchild存放在一个向量中。 ·双亲孩子链表表示法：将双亲链表和孩子链表结合。 ·孩子兄弟链表表示法：结点结构leftmostchild |data | rightsibing，附加两个分别指向该结点的最左孩子和右邻兄弟的指针域。 树的前序遍历与相对应的二叉树的前序遍历一致；树的后序遍历与相对应的二叉树的中序遍历一致。 树的带权路径长度是树中所有叶结点的带权路径长度之和。树的带权路径长度最小的二叉树就称为二叉树（即哈夫曼树）。 在叶子的权值相同的二叉树中，完全二叉树的路径长度最短。 哈夫曼树有n个叶结点，共有2n-1个结点，没有度为1的结点，这类树又称为严格二叉树。 变长编码技术可以使频度高的字符编码短，而频度低的字符编码长，但是变长编码可能使解码产生二义性。如00、01、0001这三个码无法在解码时确定是哪一个，所以要求在字符编码时任一字符的编码都不是其他字符编码的前缀，这种码称为前缀码（其实是非前缀码）。 哈夫曼树的应用最广泛地是在编码技术上，它能够容易地求出给定字符集及其概率分布的前缀码。哈夫曼编码的构造很容易，只要画好了哈夫曼树，按分支情况在左路径上写代码0，右路径上写代码1，然后从上到下到叶结点的相应路径上的代码的序列就是该结点的前缀码。 第七章 图 图的逻辑结构特征就是其结点（顶点）的前趋和后继的个数都是没有限制的，即任意两个结点之间之间都可能相关。 图GraphG=（V，E），V是顶点的有穷非空集合，E是顶点偶对的有穷集。 有向图Digraph：每条边有方向；无向图Undigraph：每条边没有方向。 有向完全图：具有n*（n-1）条边的有向图；无向完全图：具有n*（n-1）/2条边的无向图； 有根图：有一个顶点有路径到达其它顶点的有向图；简单路径：是经过顶点不同的路径；简单回路是开始和终端重合的简单路径； 网络：是带权的图。 图的存储结构： ·邻接矩阵表示法：用一个n阶方阵来表示图的结构是的，适合稠密图。 ·无向图：邻接矩阵是对称的。 ·有向图：行是出度，列是入度。 建立邻接矩阵算法的时间是O（n+n^2+e），其时间复杂度为O（n^2） ·邻接表表示法：用顶点表和邻接表构成不是的，适合稀疏图。·顶点表结构 vertex | firstedge，指针域存放邻接表头指针。 ·邻接表：用头指针确定。 ·无向图称边表； ·有向图又分出边表和逆邻接表； ·邻接表结点结构为 adjvex | next， 时间复杂度为O（n+e）。，空间复杂度为O（n+e）。。 图的遍历： ·深度优先遍历：借助于邻接矩阵的列。使用栈保存已访问结点。 ·广度优先遍历：借助于邻接矩阵的行。使用队列保存已访问结点。 生成树的定义：若从图的某个顶点出发，可以系统地访问到图中所有顶点，则遍历时经过的边和图的所有顶点所构成的子图称作该图的生成树。 最小生成树：图的生成树不，从不同的顶点出发可得到不同的生成树，把权值最小的生成树称为最小生成树（MST）。 构造最小生成树的算法： ·Prim算法的时间复杂度为O（n^2）与边数无关适于稠密图。 ·Kruskal算法的时间复杂度为O（lge），主要取决于边数，较适合于稀疏图。 最短路径的算法：·Dijkstra算法，时间复杂度为O（n^2）。·类似于prim算法。 拓扑排序：是将有向无环图G中所有顶点排成一个线性序列，若 ∈E（G），则在线性序列u在v之前，这种线性序列称为拓扑序列。 拓扑排序也有两种方法：·无前趋的顶点优先，每次输出一个无前趋的结点并删去此结点及其出边，最后得到的序列即拓扑序列。 ·无后继的结点优先：每次输出一个无后继的结点并删去此结点及其入边，最后得到的序列是逆拓扑序列。 第八章 排序 记录中可用某一项来标识一个记录，则称为关键字项，该数据项的值称为关键字。 排序是使文件中的记录按关键字递增（或递减）次序排列起来。 ·基本操作：比较关键字大小；改变指向记录的指针或移动记录。 ·存储结构：顺序结构、链表结构、索引结构。 经过排序后这些具有相同关键字的记录之间的相对次序保持不变，则称这种排序方法是稳定的，否则排序算法是不稳定的。 排序过程中不涉及数据的内、外存交换则称之为“内部排序”（内排序），反之，若存在数据的内外存交换，则称之为外排序。 内部排序方法可分五类：插入排序、选择排序、交换排序、归并排序和分配排序。 评价排序算法好坏的标准主要有两条：执行时间和所需的辅助空间，另外算法的复杂程序也是要考虑的一个因素。 插入排序：·直接插入排序： ·逐个向前插入到合适位置。 ·哨兵（监视哨）有两个作用： ·作为临变量存放R[i] ·是在查找循环中用来监视下标变量j是否越界。 ·直接插入排序是就地的稳定排序。时间复杂度为O（n^2），比较次数为（n+2）（n-1）/2；移动次数为（n+4）（n-1）/2； ·希尔排序： ·等间隔的数据比较并按要求顺序排列，最后间隔为1. ·希尔排序是就地的不稳定排序。时间复杂度为O（n^1.25），比较次数为（n^1.25）；移动次数为（1.6n^1.25）； 交换排序：·冒泡排序：·自下向上确定最轻的一个。·自上向下确定最重的一个。·自下向上确定最轻的一个，后自上向下确定最重的一个。 ·冒泡排序是就地的稳定排序。时间复杂度为O（n^2），比较次数为n（n-1）/2；移动次数为3n（n-1）/2； ·快速排序：·以第一个元素为参考基准，设定、动两个指针，发生交换后指针交换位置，直到指针重合。重复直到排序完成。 ·快速排序是非就地的不稳定排序。时间复杂度为O（nlog2n），比较次数为n（n-1）/2； 选择排序：·直接选择排序： ·选择最小的放在比较区前。 ·直接选择排序就地的不稳定排序。时间复杂度为O（n^2）。比较次数为n（n-1）/2； ·堆排序 ·建堆：按层次将数据填入完全二叉树，从int（n/2）处向前逐个调整位置。 ·然后将树根与最后一个叶子交换值并断开与树的连接并重建堆，直到全断开。 ·堆排序是就地不稳定的排序，时间复杂度为O（nlog2n），不适宜于记录数较少的文件。 归并排序： ·先两个一组排序，形成（n+1）/2组，再将两组并一组，直到剩下一组为止。 ·归并排序是非就地稳定排序，时间复杂度是O（nlog2n）， 分配排序：·箱排序： ·按关键字的取值范围确定箱子数，按关键字投入箱子，链接所有非空箱。 ·箱排序的平均时间复杂度是线性的O（n）。 ·基数排序：·从低位到高位依次对关键字进行箱排序。 ·基数排序是非就稳定的排序，时间复杂度是O（d*n+d*rd）。 各种排序方法的比较和选择： ·。待排序的记录数目n；n较大的要用时间复杂度为O（nlog2n）的排序方法； ·记录的大小（规模）；记录大用链表作为存储结构，而快速排序和堆排序在链表上难于实现； ·关键字的结构及其初始状态； ·对稳定性的要求； ·语言工具的条件； ·存储结构； ·时间和辅助空间复杂度。 第九章 查找 查找的同时对表做修改操作（如插入或删除）则相应的表称之为动态查找表，否则称之为静态查找表。 衡量查找算法效率优劣的标准是在查找过程中对关键字需要执行的平均比较次数（即平均查找长度ASL）。 线性表查找的方法： ·顺序查找：逐个查找，ASL=（n+1）/2； ·二分查找：取中点int（n/2）比较，若小就比左区间，大就比右区间。用二叉判定树表示。ASL=（∑（每层结点数*层数））/N. ·分块查找。要求“分块有序”，将表分成若干块内部不一定有序，并抽取各块中的关键字及其位置建立有序索引表。 二叉排序树（BST）定义是：二叉排序树是空树或者满足如下性质的二叉树： ·若它的左子树非空，则左子树上所有结点的值均小于根结点的值； ·若它的右子树非空，则右子树上所有结点的值均大于根结点的值； ·左、右子树本身又是一棵二叉排序树。 二叉排序树的插入、建立、删除的算法平均时间性能是O（nlog2n）。 二叉排序树的删除操作可分三种情况进行处理： ·*P是叶子，则直接删除*P，即将*P的双亲*parent中指向*P的指针域置空即可。 ·*P只有一个孩子*child，此时只需将*child和*p的双亲直接连接就可删去*p. ·*p有两个孩子，则先将*p结点的中序后继结点的数据到*p，删除中序后继结点。 关于B-树（多路平衡查找树）。它适合在磁盘等直接存取设备上组织动态的查找表，是一种外查找算法。建立的方式是从下向上拱起。 散列技术：将结点按其关键字的散列地址存储到散列表的过程称为散列。散列函数的选择有两条标准：简单和均匀。 常见的散列函数构的造方法： ·。平方取中法：hash=int（（x^2）%100） ·。除余法：表长为m，hash=x%m ·。相乘取整法：hash=int（m*（x*A-int（x*A））；A=0.618 ·。随机数法：hash=random（x）。 处理冲突的方法：·开放定址法： ·一般形式为hi=（h（key）+di）%m1≤i≤m-1，开放定址法要求散列表的装填因子α≤1. ·开放定址法类型： ·线性探查法：address=（hash（x）+i）%m； ·二次探查法：address=（hash（x）+i^2）%m； ·双重散列法：address=（hash（x）+i*hash（y））%m； ·拉链法： ·是将所有关键字为同义词的结点链接在同一个单链表中。 ·拉链法的优点： ·拉链法处理冲突简单，且无堆积现象； ·链表上的结点空间是动态申请的适于无法确定表长的情况； ·拉链法中α可以大于1，结点较大时其指针域可忽略，因此节省空间； ·拉链法构造的散列表删除结点易实现。 ·拉链法也有缺点：当结点规模较小时，用拉链法中的指针域也要占用额外空间，还是开放定址法省空间。 第十章 文件 文件是性质相同的记录的集合。记录是文件中存取的基本单位，数据项是文件可使用的最小单位，数据项有时称字段或者属性。 文件·逻辑结构是一种线性结构。 ·操作有：检索和维护。并有实时和批量处理两种处理方式。 文件·存储结构是指文件在外存上的组织方式。 ·基本的组织方式有：顺序组织、索引组织、散列组织和链组织。 ·常用的文件组织方式：顺序文件、索引文件、散列文件和多关键字文件。 评价一个文件组织的效率，是执行文件操作所花费的时间和文件组织所需的存储空间。 检索功能的多寡和速度的快慢，是衡量文件操作质量的重要标志。 顺序文件是指按记录进入文件的先后顺序存放、其逻辑顺序和物理顺序一致的文件。主关键字有序称顺序有序文件，否则称顺序无序文件。 一切存储在顺序存储器（如磁带）上的文件都只能顺序文件，只能按顺序查找法存取。 顺序文件的插入、删除和修改只能通过复制整个文件实现。 索引文件的组织方式：通常是在主文件之外建立一张索引表指明逻辑记录和物理记录之间一一对应的关系，它和主文件一起构成索引文件。 索引非顺序文件中的索引表为稠密索引。索引顺序文件中的索引表为稀疏索引。 若记录很大使得索引表也很大时，可对索引表再建立索引，称为查找表。是一种静态索引。 索引顺序文件常用的有两种： ·ISAM索引顺序存取方法：是专为磁盘存取文件设计的，采用静态索引结构。 ·VSAM虚拟存储存取方法：采用B+树作为动态索引结构，由索引集、顺序集、数据集组成。 散列文件是利用散列存储方式组织的文件，亦称为直接存取文件。 散列文件 ·优点是：文件随机存放，记录不需要排序；插入删除方便；存取速度快；不需要索引区，节省存储空间。 ·缺点是：不能进行顺序存取，只能按关键字随机存取，且询问方式限地简单询问，需要重新组织文件。 多重表文件：对需要查询的次关键字建立相应的索引，对相同次关键字的记录建一个链表并将链表头指针、长度、次关键字作为索引表的索引项。 倒排表：次关键字索引表称倒排表，主文件和倒排表构成倒排文件。
晓柚崽崽！
1、继承不同
HashMap继承了AbstractMap，AbstractMap实现了Map接口
HashTable继承了Dictionary类
2、线程安全不同
HashMap不是线程安全的，HashTable是线程安全的
3、允许null值
HashMap允许key和value为空，而HashTable不允许
4、遍历方式实现不同
HashMap的迭代器是fail-fast迭代器，HashTable的enumerator迭代器不是fail-fast的
5、哈希值的使用不同
HashMap重新计算哈希值，HashTable直接使用对象的哈希值
6、初始容量和扩容方式不同
HashMap初始大小为16，扩容大小一定是2的指数
HashTable初始大小为11，扩容大小为old*2+1
7、hashmap新增红黑树结构
当碰撞链表过长时，就把链表转为红黑树
1、直接定址法
取关键字或关键字的某个线性函数值为散列地址
特点：关键字连续时较方便，但关键字不连续时将造成内存单元的大量浪费
2、数字分析法
取关键字中取值比较均匀的若干数位作为哈希值。
特点：适用于关键字全部已知，并要对关键字中每一位进行分析
3、平方取中法
取关键字平方后中间几位作为哈希地址
特点：因为平均值的中间部分跟关键字的每一位都有关，出现随机值的概率较大
4、分段叠加法
按哈希表地址位数将哈希表分为位数相等的几段（最后一段可以较短），然后将这几部分相加，舍弃最高位的进位得到哈希值。
具体分为：移位法与折叠法
移位法：将每部分低位对其相加
折叠法：从一段向另一端沿分割线来回折叠（奇数段为正序，偶数段为倒序）
例如关键字123603247112020,哈希表长度为1000，则应把关键字分成3位一段
移位法得到105，折叠法得到907
5、伪随机数法
采用伪随机函数作为哈希函数
6、除留余数法
用关键字除以某个不大于哈希表长度的数，取余数作为哈希值。
1、开放定址法
当关键字key的哈希值p=H（key）出现冲突时，以p为基础产生新的哈希值p1，如果p1仍冲突，则产生p2，以此类推。
函数形式如下：
Hi = (H(key) + di) % m
根据di的不同分为
（1）线性探测
di = 1， 2， 3， …… ，（m-1）
（2）平方探测
d i =1 2 ，-1 2 ，2 2 ，-2 2 ，…，k 2 ，-k 2 ( k<=m/2 )
（3）伪随机探测
di = 伪随机数序列
2、再哈希法
构造多个不同的哈希函数，当出现冲突时，使用新的哈希函数
3、链地址法
将散列到同一位置的冲突元素存入一个链表中
4、建立一个公共溢出区
将哈希表分为基本表和溢出表
左旋：
右旋
红黑树是一颗特殊的二叉查找树，除了二叉查找树的所有性质
1、若任意节点的左子树不为空，则左子树上所有节点的值均小于它的根节点的值
2、若任意节点的右子树不为空，则右子树上所有节点的值均大于它的根节点的值
3、任意节点的左右子树也为二叉查找树
4、没有键值相等的节点
还满足
1、每个节点要么是红的要么是黑的
2、根节点是黑的
3、每个叶节点（null节点）是黑的
4、如果一个节点是红的，那么它的两个儿子都是黑的
5、任意节点到叶节点（null节点）的每条路径都包含相同数目的黑节点
红黑树保证没有一条路径比另一条路径长出两倍，保证了自身是接近平衡的二叉树，能保证在最坏的情况下查找的时间复杂度为O（logN），而二叉查找树最坏为O（N）
红黑树牺牲了严格的高度平衡为代价，只要求部分达到部分平衡条件，降低了对旋转的要求，从而提高了性能。红黑树能够以O（logN）的时间复杂度进行添加，删除，查找。由于它的设计，任何不平衡都可以在三次旋转之内解决。
1、相比BST（二叉搜索树）
红黑树的最长路径不大于最短路径两倍，保证了最差搜索效率为O（logN）,而二叉搜索树最差效率会达到O（N）
2、相比AVL（平衡二叉树）
（1）红黑树的查询性能略逊于平衡二叉树，因为它比平衡二叉树会最多多一层。
（2）红黑树在插入删除上要优于平衡二叉树，红黑树使用非严格的高度平衡换取增删节点时旋转次数的减少，任何不平衡都会在三次旋转之内解决，但是平衡二叉树旋转次数有时会比红黑树要多。所以红黑树的插入删除效率更高。
沐小宁橙紫儿
线性表的结点按逻辑顺序依次存放在一组地址连续的存储单元里。是随机存取的顺序存储结构。顺序存储指内存地址是一块的，随机存取指访问时可以按下标随机访问，存储和存取是不一样的。
用一组任意的存储单元来依次存放线性表的结点，这组存储单元即可以是连续的，也可以是不连续的，甚至是零散分布在内存中的任意位置上的。链表中结点的逻辑次序和物理次序不一定相同。
队列(Queue)也是一种运算受限的线性表。它只允许在表的一端进行插入，而在另一端进行删除。允许删除的一端称为队头(front)，允许插入的一端称为队尾(rear)。先进先出。
串(String)是零个或多个字符组成的有限序列。长度为零的串称为空串(Empty String)，它不包含任何字符。通常将仅由一个或多个空格组成的串称为空白串(Blank String) 注意：空串和空白串的不同，例如“ ”和“”分别表示长度为1的空白串和长度为0的空串。
串的表示和实现
数组和广义表可看成是一种特殊的线性表，其特殊在于: 表中的元素本身也是一种线性表。内存连续。根据下标在O(1)时间读/写任何元素。 二维数组，多维数组，广义表，树，图都属于非线性结构
数组 数组的顺序存储：行优先顺序；列优先顺序。数组中的任一元素可以在相同的时间内存取，即顺序存储的数组是一个随机存取结构。
关联数组(Associative Array)，又称映射（Map）、字典（ Dictionary）是一个抽象的数据结构，它包含着类似于(键，值)的有序对。 不是线性表。
广义表 广义表（Lists，又称列表）是线性表的推广。广义表是n(n≥0)个元素a1,a2,a3,…,an的有限序列，其中ai或者是原子项，或者是一个广义表。若广义表LS（n>=1)非空，则a1是LS的表头，其余元素组成的表(a2,…an)称为LS的表尾。广义表的元素可以是广义表，也可以是原子，广义表的元素也可以为空。表尾是指除去表头后剩下的元素组成的表，表头可以为表或单元素值。所以表尾不可以是单个元素值。
三个结论
考点
一种非线性结构。树是递归结构，在树的定义中又用到了树的概念。
基本术语 1.树结点：包含一个数据元素及若干指向子树的分支； 2.孩子结点：结点的子树的根称为该结点的孩子； 3.双亲结点：B结点是A结点的孩子，则A结点是B结点的双亲； 4.兄弟结点：同一双亲的孩子结点； 5.堂兄结点：同一层上结点； 6.结点层次：根结点的层定义为1；根的孩子为第二层结点，依此类推； 7.树的高（深）度：树中最大的结点层 8.结点的度：结点子树的个数，就是有几个孩子 9.树的度： 树中最大的结点度。 10.叶子结点：也叫终端结点，是度为0的结点； 11.分枝结点：度不为0的结点（非终端结点）； 12.森林：互不相交的树集合； 13.有序树：子树有序的树，如：家族树； 14.无序树：不考虑子树的顺序；
二叉树 二叉树可以为空。二叉树结点的子树要区分左子树和右子树，即使只有一棵子树也要进行区分，说明它是左子树，还是右子树。这是二叉树与树的最主要的差别。 注意区分： 二叉树、二叉查找树/二叉排序树/二叉搜索树、二叉平衡(查找)树
二叉树遍历 先序遍历：根左右 中序遍历：左根右 后序遍历：左右根 层次遍历：一维数组存储二叉树，总是以层次遍历的顺序存储结点。层次遍历应该借助队列。
二叉树性质 1.在二叉树的第 i 层上至多有2的i次幂-1个结点 2.深度为 k 的二叉树上至多含 2的k次幂-1 个结点（k≥1） 3.树与转换后的二叉树的关系：转换后的二叉树的先序对应树的先序遍历；转换后的二叉树的中序对应树的后序遍历
一些概念 1.路径：从一个祖先结点到子孙结点之间的分支构成这两个结点间的路径； 2.路径长度：路径上的分支数目称为路径长度； 3.树的路径长度：从根到每个结点的路径长度之和。 4.结点的权：根据应用的需要可以给树的结点赋权值； 5.结点的带权路径长度：从根到该结点的路径长度与该结点权的乘积； 6.树的带权路径长度=树中所有叶子结点的带权路径之和；通常记作 WPL=∑wi×li 7.哈夫曼树：假设有n个权值(w1, w2, … , wn)，构造有n个叶子结点的二叉树，每个叶子结点有一个 wi作为它的权值。则带权路径长度最小的二叉树称为哈夫曼树。最优二叉树。
图搜索->形成搜索树 1.穷举法 2.贪心法。多步决策，每步选择使得构成一个问题的可能解，同时满足目标函数 3.回溯法，根据题意，选取度量标准，然后将可能的选择方法按度量标准所要求顺序排好，每次处理一个量，得到该意义下的最优解的分解处理
无向图 1.回路或环：第一个顶点和最后一个顶点相同的路径。 2.简单回路或简单环：除第一个顶点和最后一个顶点之外，其余顶点不重复出现的回路 3.连通：顶点v至v’ 之间有路径存在 4.连通图：无向图图 G 的任意两点之间都是连通的，则称G是连通图。 5.连通分量：极大连通子图，子图中包含的顶点个数极大 6.所有顶点度的和必须为偶数
有向图 1.回路或环：第一个顶点和最后一个顶点相同的路径。 2.简单回路或简单环：除第一个顶点和最后一个顶点之外，其余顶点不重复出现的回路。 3.连通：顶点v至v’之间有路径存在 4.强连通图：有向图G的任意两点之间都是连通的，则称G是强连通图。各个顶点间均可达。 5.强连通分量：极大连通子图 6.有向图顶点的度是顶点的入度与出度之和。邻接矩阵中第V行中的1的个数是V的出度 7.生成树：极小连通子图。包含图的所有n个结点，但只含图的n-1条边。在生成树中添加一条边之后，必定会形成回路或环。 8.完全图：有 n(n-1)/2 条边的无向图。其中n是结点个数。必定是连通图。 9.有向完全图：有n(n-1)条边的有向图。其中n是结点个数。每两个顶点之间都有两条方向相反的边连接的图。 10.一个无向图 G=(V,E) 是连通的，那么边的数目大于等于顶点的数目减一：|E|>=|V|-1，而反之不成立。如果 G=(V,E) 是有向图，那么它是强连通图的必要条件是边的数目大于等于顶点的数目：|E|>=|V|，而反之不成立。没有回路的无向图是连通的当且仅当它是树，即等价于：|E|=|V|-1。
图的邻接矩阵和邻接表
1.邻接矩阵和加权邻接矩阵
深度优先搜索利用栈 深度优先遍历类似于树的先序遍历，是树的先序遍历的推广
广度优先遍历 图的广度优先遍历就类似于树的层序遍历
每次遍历一个连通图将图的边分成遍历所经过的边和没有经过的边两部分，将遍历经过的边同图的顶点构成一个子图，该子图称为生成树。因此有DFS生成树和BFS生成树。
生成树是连通图的极小子图，有n个顶点的连通图的生成树必定有n-1条边,在生成树中任意增加一条边，必定产生回路。若砍去它的一条边，就会把生成树变成非连通子图
最小生成树：生成树中边的权值(代价)之和最小的树。最小生成树问题是构造连通网的最小代价生成树。
Kruskal算法 ：令最小生成树集合T初始状态为空，在有n个顶点的图中选取权值最小的边并从图中删去，若该边加到T中有回路则丢弃，否则留在T中；依次类推，知道T中有n-1条边为止
Prim算法： 它的基本思想是以顶点为主导地位，从起始顶点出发，通过选择当前可用的最小权值边把顶点加入到生成树当中来： 1.从连通网络N={V,E}中的某一顶点U0出发，选择与它关联的具有最小权值的边（U0,V）,将其顶点加入到生成树的顶点集合U中。 2.以后每一步从一个顶点在U中，而另一个顶点不在U中的各条边中选择权值最小的边(U,V),把它的顶点加入到集合U中。如此继续下去，直到网络中的所有顶点都加入到生成树顶点集合U中为止。
Prim算法，Kruskal算法和Dijkstra算法都属于贪心算法
Dijkstra算法适用于边权值为正的情况，如果边权值为负数就才用另一种最短路算法Bellman-Ford算法。该算法是指从单个源点到各个结点的最短路，该算法适用于有向图和无向图。复杂度O(n^2) Dijkstra算法图文详解
若从一个连通图中删去任何一个顶点及其相关联的边，它仍为一个连通图的话，则该连通图被称为 重（双）连通图。 若连通图中的某个顶点和其相关联的边被删去之后，该连通图被分割成两个或两个以上的连通分量，则称此顶点为 关节点。
没有关节点的连通图称为双连通图 1.生成树的根结点，有两个或两个以上的分支，则此顶点(生成树的根)必为关节点； 2.对生成树上的任意一个非叶“顶点”，若其某棵子树中的所有“顶点”没有和其祖先相通的回边，则该“顶点”必为关节点
拓扑排序。在用邻接表表示图时,对有n个顶点和e条弧的有向图而言时间复杂度为O(n+e)。一个有向图能被拓扑排序的充要条件就是它是一个有向无环图。
AOV网(Activity On Vertex)：用顶点表示活动，边表示活动的优先关系的有向图称为AOV网。AOV网中不允许有回路，这意味着某项活动以自己为先决条件。
拓扑有序序列：把AOV网络中各顶点按照它们相互之间的优先关系排列一个线性序列的过程。若vi是vj前驱，则vi一定在vj之前；对于没有优先关系的点，顺序任意。
拓扑排序：对AOV网络中顶点构造拓扑有序序列的过程。方法：
采用 深度优先搜索 或者 拓扑排序 算法可以判断出一个有向图中是否有环（回路）。 深度优先搜索只要在其中记录下搜索的节点数n，当n大于图中节点数时退出，并可以得出有回路。若有回路，则拓扑排序访问不到图中所有的节点，所以也可以得出回路。广度优先搜索过程中如果访问到一个已经访问过的节点，可能是多个节点指向这个节点，不一定是存在环。
拓扑算法描述 ：
AOE网：带权的有向无环图，其中顶点表示事件，弧表示活动，权表示活动持续时间。在工程上常用来表示工程进度计划。
常用哈希函数 1.直接定址法。 2.数字分析法。 3.平方取中法。 4.折叠法。 5.除留余数法。 6.随机数法。
冲突解决 1.开放定址法：当发生冲突时，形成一个探查序列，沿此序列逐个地址探查，知道找到一个空位置，将发生冲突的记录放到该地址中。即Hi=(H(key)+di) % m，i=1,2,……k(k<=m-1)，H(key)哈希函数，m哈希表长，di增量序列。
2.链地址法：将所有关键字为同义词的记录存储在一个单链表中，并用一维数组存放头指针。
3.设有n个关键字具有相同的Hash函数值，则用线性探测法把这n个关键字映射到Hash表中需要做n (n-1)/2次线性探测。如果使用二次探测再散列法将这n个关键字存入哈希表，至少要进行n (n+1)/2次探测 4.Hash查找效率：装填因子=表中记录数/表容量 5.开哈希表——链地址法；闭哈希表——开放地址法
B树的查找 时间复杂度O(logn)
B树的插入
例：用1，2，6，7，11，4，8，13，10，5，17，9，16，20，3，12，14，18，19，15构建5阶B树
因为构建5阶的B树，所以每个节点的关键字个数范围为[2,4]
插入11时，该节点的关键字个数超出范围，进行分裂
之后直接插入4，8，13
当插入10时，节点关键字个数再次超出范围
将子节点分裂
直接插入5，17，9，16，插入20
关键字个数超出范围，进行分裂
继续插入3
关键字个数超出范围，进行分裂
继续插入15
关键个数超出范围，进行分裂
这时候根节点关键字个数也超出范围，继续分裂
B+的优点 1.单一节点存储更多的元素，使得查询的IO次数更少。 2.所有查询都要查询叶到叶子节点，查询更加稳定 3.所有叶子节点形成有序链表，便于范围查询。
线性表的结点按逻辑顺序依次存放在一组地址连续的存储单元里。是随机存取的顺序存储结构。顺序存储指内存地址是一块的，随机存取指访问时可以按下标随机访问，存储和存取是
楼兰芥末姑娘 3人参与回答 2024-06-01 打这么一段话真是个浩大的工程－ －要应付期末考试最快捷的方法是找到本校历年试卷然后让班上学得比较好的同学给讲题，大概能搞懂三套题的话基本题型你也了解了，自己的话
Perfect颜 3人参与回答 2024-06-01 1、数据：所有能被计算机识别、存储和处理的符号的集合。 2、数据元素：是数据的基本单位，具有完整确定的实际意义。 3、数据对象：具有相同性质的数据元素的
扬州灰豆子 3人参与回答 2024-06-01 第六章 树 树是n个结点的有限集合，非空时必须满足：只有一个称为根的结点；其余结点形成m个不相交的子集，并称根的子树。 根是开始结点；结点的子树数称度；度
闪灯背后 3人参与回答 2024-05-31 队列(Queue)是一种运算受限的线性表 插入在表的一端进行 而删除在表的另一端进行 允许删除的一端称为队头(front) 允许插入的一端称为队尾(rear)
花花的老妈 3人参与回答 2024-05-31 