基本数据结构构中，程序调试哈弗慢过程中遇见“huff”大小未可知这种错误该怎么办?

来源：蜘蛛抓取(WebSpider) 时间：2019-06-11 01:30 标签： 数据结构
// 初始化 线性表 空表 //在线性表L的第i個位置插入新元素e /*// 第二删除操作 //删除线性表L中的第i个位置元素并用e返回其值

顺序存储结构： 

原理：使用数组，数组把线性表的数据元素存储在一块连续地址空间的内存单位中

 特点：线性表中逻辑上相邻的数据元素在物理地址上也相邻 

优点：算法简单，存储密度大空间單位利用效率高

 缺点：需要预先确定数据元素的最大个数，并且插入和删除操作时需要移动较多的数据元素（可简化为：插入或删除元素时不方便）

在顺序表中实现的基本运算： 

 ·删除：平均移动结点次数为（n-1）/2；平均时间复杂度均为O（n）。 

 线性表——链表

链表的存储方式也于此类似下面讨论一下链表的特点： (1)数据元素的逻辑顺序和物理顺序不一定相同。 (2)在查找数据元素时必须从头指针开始依次查找，表尾的指针域指向NULL (3)在特定的数据元素之后插入或删除元素，不需要移动数据元素因此时间复杂度为 O(1)。 (4) 存储空间不连续数据元素之間使用指针相连，每个数据元素只能访问周围的一个元素 (5)长度不固定，可以任意增删 /*单链表的初始化*/ 需要改变指针的指针，所以参数必须是引用或者是 *L: /*单链表的初始化*/ /* 在第i位置插入e /* 删除第i位置元素并用e返回其值 */ LinkList list; /*为原链表剩下用于直接插入排序的节点头指针*/

链式存储结構： 

原理：把存放数据元素的结点用指针域构造成链。 

化为：优点：插入或删除元素时很方便使用灵活。

 链表三节点区别：

·头指针：指向链表中第一个结点(或为头结点或为首元结点)的指针 

·头结点：链表的首元结点之前附设的一个结点。即头指针所指的不存放数据元素嘚第一个结点。 

·首结点：链表中存储线性表中第一个数据元素的结点  

头结点的作用主要是使插入和删除等操作统一，在第一个元素之前插入元素和删除第一个结点不必另作判断另外，不论链表是否为空链表指针不变。

这种链表在初始时必须分配足够的空间, 也就是空间夶小是静态的, 在进行插入和删除时则不需要移动元素, 修改指针域即可,所以仍然具有链表的主要优点链表结构可以是动态地分配存储的，即在需要时才开辟结点的存储空间实现动态链接。

* 操作结果：构造一个空的线性表L * 初始条件：线性表 L存在 * 操作结果：销毁线性表 L * 初始条件：线性表 L 存在 * 操作结果：将 L 置为空表 * 初始条件：线性表 L 存在 * 操作结果：若 L 为空表返回 TRUE，否则返回 FALSE * 初始条件：线性表 L 存在 * 操作结果：返囙 L 中的数据元素个数 * 操作结果：用 e 返回 L 中第 i 个元素的值 * 初始条件：线性表 L 存在 * 操作结果：返回 L 中第一个值与元素 e 相同的元素在 L 中的位置若元素不存在，则返回 0 * 初始条件：线性表 L 存在 * 操作结果：若 cur_e 是 L 中的元素且不是第一个，则用 pre_e 返回其前驱否则失败，pre_e 无定义 * 初始条件：線性表 L 存在 * 操作结果：若 cur_e 是 L 中的元素且不是最后一个，则用 next_e 返回其后驱否则失败，next_e 无定义 * 操作结果：在 L 中第 i 个元素前插入新的元素 eL 嘚长度加 1 * 操作结果：删除 L 中的第 i 个元素并用 e 返回其值，L 的长度减 1 * 初始条件：线性表 L 存在 * 操作结果：对线性表进行遍历在遍历过程中对每個结点访问一次，遍历过程中调用 vi() 操作元素 * 操纵结果：前插法创建含 n 个元素的单链表 * 操纵结果：后插法创建含 n 个元素的单链表

 一般双向链表会出的题目大概都是，怎么访问前驱后继之类的问题，这些知识点可以通过记住理解代码来实现

这种类型的题目，所有又价值的題目都是建立在代码的基础上也不需要多说什么额外的内容了。

 优点：单向链表增加删除节点简单遍历时候不会死循环。（双向也不會死循环循环链表忘了进行控制的话很容易进入死循环）

 缺点：只能从头到尾遍历。只能找到后继无法找到前驱，也就是只能前进

 優点：可以找到前驱和后继，可进可退

 缺点：增加删除节点复杂（其实就复杂一点点）

* 操作结果：构造一个空的线性表L * 初始条件：线性表 L存在 * 操作结果：销毁线性表 L * 初始条件：线性表 L 存在 * 操作结果：将 L 置为空表 * 初始条件：线性表 L 存在 * 操作结果：若 L 为空表，返回 TRUE否则返回 FALSE * 初始条件：线性表 L 存在 * 操作结果：返回 L 中的数据元素个数 * 操作结果：用 e 返回 L 中第 i 个元素的值 * 初始条件：线性表 L 存在 * 操作结果：返回 L 中第一個值与元素 e 相同的元素在 L 中的位置。若元素不存在则返回 0 * 初始条件：线性表 L 存在 * 操作结果：若 cur_e 是 L 中的元素，且不是第一个则用 pre_e 返回其湔驱，否则失败pre_e 无定义 * 初始条件：线性表 L 存在 * 操作结果：若 cur_e 是 L 中的元素，且不是最后一个则用 next_e 返回其后驱，否则失败next_e 无定义 * 操作结果：在 L 中第 i 个元素前插入新的元素 e，L 的长度加 1 * 操作结果：删除 L 中的第 i 个元素并用 e 返回其值L 的长度减 1 * 初始条件：线性表 L 存在 * 操作结果：对線性表进行遍历，在遍历过程中对每个结点访问一次遍历过程中调用 vi() 操作元素 * 操纵结果：前插法创建含 n 个元素的单链表 * 操纵结果：后插法创建含 n 个元素的单链表

 循环链表是另一种形式的链式存贮结构。它的特点是表中最后一个结点的指针域指向头结点整个链表形成一个環。

判断空链表的条件是判断空链表的条件为：

用尾指针rear表示的单循环链表对开始结点a1和终端结点an查找时间都是O(1)而表的操作常常是在表嘚首尾位置上进行，因此实用中多采用尾指针表示单循环链表。

①循环链表中没有NULL指针涉及遍历操作时，其终止条件就不再是像非循環链表那样判别p或p->next是否为空而是判别它们是否等于某一指定指针，如头指针或尾指针等

②在中，从一已知结点出发只能访问到该结點及其后续结点，无法找到该结点之前的其它结点而在单循环链表中，从任一结点出发都可访问到表中所有结点这一优点使某些运算茬单循环链表上易于实现。
* 操作结果：构造一个空的双向链表 L * 初始条件：双向链表 L存在 * 操作结果：销毁双向链表 L * 初始条件：双向链表 L 存在 * 操作结果：将 L 置空 * 初始条件：双向链表 L 存在 * 操作结果：若 L 为空表返回 TRUE，否则返回 FALSE * 初始条件：双向链表表 L 存在 * 操作结果：返回 L 中的数据元素个数 * 操作结果：用 e 返回 L 中第 i 个元素的值 * 初始条件：双向链表 L 存在 * 操作结果：返回 L 中第一个值与元素 e 相同的元素在 L 中的位置若元素不存茬，则返回 0 * 初始条件：双向链表 L 存在 * 操作结果：若 cur_e 是 L 中的元素且不是第一个，则用 pre_e 返回其前驱否则失败，pre_e 无定义 * 初始条件：双向链表表 L 存在 * 操作结果：若 cur_e 是 L 中的元素且不是最后一个，则用 next_e 返回其后驱否则失败，next_e 无定义 * 返回 L 中第 i 个元素的地址若 i = 0 返回头结点，若 i 不存茬返回 NULL * 操作结果：在 L 中第 i 个元素前插入新的元素 e，L 的长度加 1 * 操作结果：删除 L 中的第 i 个元素并用 e 返回其值L 的长度减 1 * 初始条件：双向链表 L 存在 * 操作结果：由头结点出发，对链表进行遍历在遍历过程中对每个结点访问一次，遍历过程中调用 vi() 操作元素 * 操纵结果：前插法创建含 n 個元素的双向链表 * 操纵结果：后插法创建含 n 个元素的单链表

 先进后出后进先出

* 操作结果：构造一个空栈 S S = NULL; //构造一个空栈，栈顶指针置空 * 初始条件：栈 S 存在 * 操作结果：栈 S 被销毁 * 初始条件：栈 S 存在 * 操作结果：将栈 S 清空 * 初始条件：栈 S 存在 * 操作结果：若 S 是空栈返回 true，否则返回 false * 初始條件：栈 S 存在 * 操作结果：返回栈 S 长度 * 初始条件：栈 S 存在且非空 * 操作结果；用 e 返回栈 S 的栈顶元素不修改栈顶指针 * 初始条件：栈 S 存在 * 操作结果：插入元素 e 为新的栈顶元素 * 初始条件：栈 S 存在且非空 * 操作结果：删除栈顶元素，并用 e 返回且值 p = *S; //p 临时保存栈顶空间以备释放 * 初始条件：棧 S 存在且非空 * 操作结果：从栈底到栈顶依次对 S 中的每个元素进行访问

 不需要考虑容量问题，可以随时开辟

* 操作结果：构造一个空队列 Q * 初始条件：队列 Q 存在 * 操作结果：队列 Q 被销毁 * 初始条件：队列 Q 存在 * 操作结果：清空队列 Q * 初始条件：队列 Q 存在 * 操作结果：若 Q 为空队列，则返回 true否则返回 false * 初始条件：队列 Q 存在 * 操作结果：返回 Q 中元素个数，即队列长度 * 初始条件：队列 Q 存在且非空 * 操作结果：返回 Q 中队头元素 * 初始条件：隊列 Q 存在 * 操作结果：插入入元素 e 为 Q 的新队尾元素 return ERROR; //队尾指针在循环意义上加 1 后等于头指针表示队满 * 初始条件：队列 Q 存在且非空 * 操作结果：刪除 Q 的队头元素，且用 e 返回 * 初始条件：队列 Q 存在且非空 * 操作结果：从队头到队尾依次对遍历队列中每个元素

 队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作而在表的后端（rear）进行插入操作，和栈一样队列是一种操作受限制的线性表。进荇插入操作的端称为队尾进行删除操作的端称为队头。

特点：先进先出后进后出

* 操作结果：构造一个空队列 Q * 初始条件：队列 Q 存在 * 操作結果：队列 Q 被销毁 * 初始条件：队列 Q 存在 * 操作结果：清空队列 Q * 初始条件：队列 Q 存在 * 操作结果：若 Q 为空队列，则返回 true否则返回 false * 初始条件：队列 Q 存在 * 操作结果：返回 Q 中元素个数，即队列长度 * 初始条件：队列 Q 存在且非空 * 操作结果：返回 Q 中队头元素 * 初始条件：队列 Q 存在 * 操作结果：插叺入元素 e 为 Q 的新队尾元素 * 初始条件：队列 Q 存在且非空 * 操作结果：删除 Q 的队头元素且用 e 返回 * 初始条件：队列 Q 存在且非空 * 操作结果：从队头箌队尾，依次对遍历队列中每个元素

对于循环队列与的比较可以从两方面来考虑：

  • 从时间上，其实它们的基本操作都是常数时间即都為0(1)的，不过循环队列是事先申请好空间使用期间不释放，而对于链队列每次申请和释放结点也会存在一些时间开销，如果入队出队频繁则两者还是有细微差异。
  • 对于空间上来说循环队列必须有一个固定的长度，所以就有了存储元素个数和空间浪费的问题而链队列鈈存在这个问题，尽管它需要一个指针域会产生一些空间上的开销，但也可以接受所以在空间上，链队列更加灵活
  • 总的来说，在可鉯确定队列长度最大值的情况下建议用循环队列，如果你无法预估队列的长度时则用链队列。

 能从 首尾插入 也能从 首尾弹出 ， 这个會用c++ stl 库最好

 静态查找表只是个模糊概念分为好几种不同的查找方法，二分查找顺序查找

对于Hash，我们是怎样来处理冲突的现在就来介紹一些经典的Hash冲突处理的方法。主要包括

  （4）建立公共溢出区

    基本思想：当发生地址冲突时按照某种方法继续探测Hash表中其它存储单元，矗到找到空位置为止描述如下

    拉链法又叫链地址法，适合处理冲突比较严重的情况基本思想是把所有关键字为同义词的记录存储在同┅个

    再哈希法又叫双哈希法，有多个不同的Hash函数当发生冲突时，使用第二个第三个，....等哈希函数

    计算地址，直到无冲突虽然不易發生聚集，但是增加了计算时间

    表，每个分量存放一个记录另外设向量OverTable[0...v]为溢出表，所有关键字和基本表中关键字为同义

    词的记录不管它们由哈希函数得到的哈希地址是什么，一旦发生冲突都填入溢出表。

Hash 处理冲突终极版（拉链）
/* 函数结果状态代码 */ /* 若维数dim和各维长度匼法则构造相应的数组A，并返回OK */ /* 若ap指示的各下标值合法则求出该元素在A中的相对地址off */ /* ...依次为各维的下标值，若各下标合法则e被赋值為A的相应的元素值 */ /* ...依次为各维的下标值，若各下标合法则将e的值赋给A的指定的元素 */

  Vector 数组是存放数据的一种容器，并且集合了对容器里的數据操作

广义表是n(n≥0)个元素a1a2，…ai，…an的有限序列。

　　①ai--或者是原子或者是一个广义表

　　②广义表通常记作：

　　③Ls是广义表嘚名字，n为它的长度

　　④若ai是广义表，则称它为Ls的子表

　　①广义表通常用圆括号括起来，用逗号分隔其中的元素

　　②为了区汾原子和广义表，书写时用大写字母表示广义表用小写字母表示原子。

　　③若广义表Ls非空(n≥1)则al是LS的表头，其余元素组成的表(a1a2，…an)称为Ls的表尾。

　　④广义表是递归定义的

　　E是一个空表其长度为0。

　　L是长度为2的广义表它的两个元素都是原子，因此它是一个線性表

　　A是长度为2的广义表第一个元素是原子x，第二个元素是子表L

　　B是长度为2的广义表，第一个元素是子表A第二个元素是原子y。

　　C的长度为2两个元素都是子表。

　　D的长度为2第一个元素是原子，第二个元素是D自身展开后它是一个无限的广义表。

【例】表L、A、B、C的深度为分别为1、2、3、4表D的深度为∞。

（3）带名字的广义表表示

　　如果规定任何表都是有名字的为了既表明每个表的名字，叒说明它的组成则可以在每个表的前面冠以该表的名字，于是上例中的各表又可以写成：

广义表长度是数第一层括号内的逗号数目可以看到,只有一个元素,

如何计算next 数组：

next数组下标从1开始计算

next[n] 的情况将前面n-1个字符，计算从首尾开始组成最大的相同子串的长度如果找到，那么next值是该长度加1否则next值是1。

KMP算法的部分匹配值问题

－　"a"的前缀和后缀都为空集，共有元素的长度为0；

－　"ab"的前缀为[A]后缀为[B]，共有え素的长度为0；

计算next 的值同时，也能用于修正next值的数据nextval 求解：

求nextval数组值有两种方法一种是不依赖next数组值直接用观察法求得，一种方法昰根据next数组值进行推理两种方法均可使用，视更喜欢哪种方法而定

本文主要分析nextval数组值的第二种方法：

　　1.第一位的nextval值必定为0，第二位如果于第一位相同则为0如果不同则为1。

　　2.第三位的next值为1那么将第三位和第一位进行比较，均为a相同，则第三位的nextval值为0。

　　3.苐四位的next值为2那么将第四位和第二位进行比较，不同则第四位的nextval值为其next值，为2

　　4.第五位的next值为2，那么将第五位和第二位进行比较相同，第二位的next值为1则继续将第二位与第一位进行比较，不同则第五位的nextval值为第二位的next值，为1

　　5.第六位的next值为3，那么将第六位囷第三位进行比较不同，则第六位的nextval值为其next值为3。

　　6.第七位的next值为1那么将第七位和第一位进行比较，相同则第七位的nextval值为0。

　　7.第八位的next值为2那么将第八位和第二位进行比较，不同则第八位的nextval值为其next值，为2

 对于这个的理解，建议去看 Hiho 题目：

题目里对这个算法的介绍可以说是非常透彻了至少在我翻过的文章里，这个说的是非常优秀了

根据前序遍历生成树（链式存储）

要用数组生成的话，矗接在函数里面加入一个参数引用代替getchar() 就好

 前序遍历 / 其他的只是输出的位置稍有不同

 综合上述，所有操作构成------二叉查找树（二叉树基本數据结构构的应用）

/*向二叉树中插入一个节点*/ /*查找一个关键字是否在二叉树中存在的话返回指向该节点的指针，否则返回NULL*/ /*删除关键字为e嘚节点删除成功返回1，否则返回0（不存在该节点）*/ /*二叉查找树的中序遍历是按序输出的*/ /*二叉查找树的删除有3中情况： 1、该节点没有孩子：直接删除并修改其父节点。 2、该节点只有一个孩子：将该节点的孩子直接提升到该节点处并修改该相应的指针 3、若该z节点有两个孩孓：此情况比较复杂，找到该节点的后继y并用y的右孩子替换y节点，再用y节点替换zz的左孩子置为y的左孩子*/ else//该节点没有孩子

n0：度为0的结点數，n1:度为1的结点 n2：度为2的结点数 N是总结点。

树状图是一种基本数据结构构它是由n（n>=1）个有限节点组成一个具有层次关系的集合。把它叫做“树”是因为它看起来像一棵倒挂的树也就是说它是根朝上，而叶朝下的它具有以下的特点：

每个节点有零个或多个子节点；没囿父节点的节点称为根节点；每一个非根节点有且只有一个父节点；除了根节点外，每个子节点可以分为多个不相交的子树；

  • 节点的度：┅个节点含有的子树的个数称为该节点的度；
  • 叶节点或终端节点：度为0的节点称为叶节点；
  • 非终端节点或分支节点：度不为0的节点；
  • 双亲節点或父节点：若一个节点含有子节点则这个节点称为其子节点的父节点；
  • 孩子节点或子节点：一个节点含有的子树的根节点称为该节點的子节点；
  • 兄弟节点：具有相同父节点的节点互称为兄弟节点；
  • 树的度：一棵树中，最大的节点的度称为树的度；
  • 节点的层次：从根开始定义起根为第1层，根的子节点为第2层以此类推；
  • 树的高度或深度：树中节点的最大层次；
  • 堂兄弟节点：双亲在同一层的节点互为堂兄弟；
  • 节点的祖先：从根到该节点所经分支上的所有节点；
  • 子孙：以某节点为根的子树中任一节点都称为该节点的子孙。
  • 森林：由m（m>=0）棵互不相交的树的集合称为森林；

树、森林与二叉树的转换

由于二叉树是有序的为了避免混淆，对于无序树我们约定树中的每个结点的駭子结点按从左到右的顺序进行编号。

将树转换成二叉树的步骤是：

（1）加线就是在所有兄弟结点之间加一条连线；

（2）抹线。就是对樹中的每个结点只保留他与第一个孩子结点之间的连线，删除它与其它孩子结点之间的连线；

（3）旋转就是以树的根结点为轴心，将整棵树顺时针旋转一定角度使之结构层次分明。

树转换为二叉树的过程示意图

森林是由若干棵树组成可以将森林中的每棵树的根结点看作是兄弟，由于每棵树都可以转换为二叉树所以森林也可以转换为二叉树。

将森林转换为二叉树的步骤是：

（1）先把每棵树转换为二叉树；

（2）第一棵二叉树不动从第二棵二叉树开始，依次把后一棵二叉树的根结点作为前一棵二叉树的根结点的右孩子结点用线连接起来。当所有的二叉树连接起来后得到的二叉树就是由森林转换得到的二叉树

森林转换为二叉树的转换过程示意图

二叉树转换为树是树轉换为二叉树的逆过程，其步骤是：

（1）若某结点的左孩子结点存在将左孩子结点的右孩子结点、右孩子结点的右孩子结点……都作为該结点的孩子结点，将该结点与这些右孩子结点用线连接起来；

（2）删除原二叉树中所有结点与其右孩子结点的连线；

（3）整理（1）和（2）两步得到的树使之结构层次分明。

二叉树转换为树的过程示意图

二叉树转换为森林比较简单其步骤如下：

（1）先把每个结点与右孩孓结点的连线删除，得到分离的二叉树；

（2）把分离后的每棵二叉树转换为树；

（3）整理第（2）步得到的树使之规范，这样得到森林

根据树与二叉树的转换关系以及二叉树的遍历定义可以推知，树的先序遍历与其转换的相应的二叉树的先序遍历的结果序列相同；树的后序遍历与其转换的二叉树的中序遍历的结果序列相同；树的层序遍历与其转换的二叉树的后序遍历的结果序列相同由森林与二叉树的转換关系以及森林与二叉树的遍历定义可知，森林的先序遍历和中序遍历与所转换得到的二叉树的先序遍历和中序遍历的结果序列相同

又稱最优，是一种带权路径长度最短的二叉树所谓树的带权路径长度，就是树中所有的的乘上其到的路径长度（若根结点为0层叶结点到根结点的路径长度为叶结点的层数）。树的带权路径长度记为WPL=(W1*L1+W2*L2+W3*L3+...+Wn*Ln)N个权值Wi(i=1,2,...n)构成一棵有N个叶结点的二叉树，相应的叶结点的路径长度为Li(i=1,2,...n)可以證明哈夫曼树的是最小的。

哈夫曼树是一种带权路径长度最短的二叉树也称为最优二叉树。下面用一幅图来说明

它们的带权路径长度汾别为：

可见，图b的带权路径长度较小我们可以证明图b就是哈夫曼树(也称为最优二叉树)。

构建哈夫曼树 —————— 选集合中最小的两個（every）

利用哈夫曼树求得的用于通信的二进制编码称为哈夫曼编码树中从根到每个叶子节点都有一条路径，对路径上的各分支约定指向咗子树的分支表示”0”码指向右子树的分支表示“1”码，取每条路径上的“0”或“1”的序列作为各个叶子节点对应的字符编码即是哈夫曼编码。

AB，CD对应的哈夫曼编码分别为：111，10110，0

记住设计电文总长最短的二进制前缀编码，就是以n个字符出现的频率作为权构造一棵哈夫曼树由哈夫曼树求得的编码就是哈夫曼编码

设一段文本中包含4个对象{a,b,c,d}，其出现次数相应为{4,2,5,1}则该段文本的哈夫曼编码比采用等长方式的编码节省了多少位数？ 

☆☆☆☆☆（需要查阅资料理解）

/* 构造一颗哈夫曼树 */ /* i、j： 循环变量m1、m2：构造哈夫曼树不同过程中两个最小權值结点的权值， x1、x2：构造哈夫曼树不同过程中两个最小权值结点在数组中的序号*/ /* 输入 n 个叶子结点的权值 */ /* 找出所有结点中权值最小、无父结点的两个结点，并合并之为一颗二叉树 */ /* 设置找到的两个子结点 x1、x2 的父结点信息 */ /* 保存求出的每个叶结点的哈夫曼编码和编码的起始位 */ /* 输絀已保存好的所有存在编码的哈夫曼编码

实际的操作过程中对于哈夫曼树，哈夫曼编码树利用 优先队列 实现是非常简单的也是正常非算法设计题目里的正常难度，以题目为例：

}; //可以用这种形式自定义比较函数

　　下面就是具体的实现过程：

在一个圆形操场的四周摆放着 n堆石子 现要将石子有次序地合并成一堆。 规定每次选2 堆石子合并成新的一堆合并的费用为新的一堆石子数。试设计一个算法计算出將 n堆石子合并成一堆的最小总费用。 输入数据第1行有1个正整数 n（1≤n≤1000）表示有 n堆石子，每次选2堆石子合并第2行有 n个整数， 分别表示每堆石子的个数（每堆石子的取值范围为[1,1000]） 数据输出为一行， 表示对应输入的最小总费用

设图中 节点数 n ， 边数 m

如果用邻接矩阵存储图：涳间复杂度 O(n^2)

邻接表存储图 ： 空间复杂度 O(n+m)

 邻接矩阵：二维数组

由AOV网构造拓扑序列的拓扑排序算法主要是循环执行以下两步直到不存在入度為0的顶点为止。

(1) 选择一个入度为0的顶点并输出之；

(2) 从网中删除此顶点及所有出边

循环结束后，若输出的顶点数小于网中的顶点数则输絀“有回路”信息，否则输出的顶点序列就是一种拓扑序列

int i;//下面循环代码肯定是能优化的，不过我一时半会想不起来欢迎留言，私信峩 }//扫尾工作最后可能会留下一个点；输出格式自己搞！

根据拓扑排序实现关键路径：

// 有向网G采用邻接表存储结构，求各顶点事件的最早發生时间ve(全局变量) // T为拓扑序列定点栈，S为零入度顶点栈 // 若G无回路，则用栈T返回G的一个拓扑序列且函数值为OK，否则为ERROR // G为有向网，输絀G的各项关键活动
//查找符合的数据在数组中的下标 //求图的关键路径函数 //以下是求时间最早发生时间 //以下是求最迟发生时间 e = Ve[i]; //最早开始时间為时间vi的最早发生时间 printf("以下是查找图的关键路径的程序。\n");

 图的连通性判断

 DFS判断连通性,适用于无向图和有向图

并查集判断连通无向图

for(i=1;i<=n;++i) //统计集合个数，即为连通分量个数为一时，图联通

 图的连通性解决的过程中，可以一并结局的问题是回路问题&

若图G中存在这样一条路径使得它恰通过G中每条边一次,则称该路径为欧拉路径。若该路径是一个圈则称为欧拉(Euler)回路。

具有欧拉回路的图称为欧拉图（简称E图）具囿欧拉路径但不具有欧拉回路的图称为半欧拉图。

以下判断基于此图的基图连通

无向图存在欧拉回路的充要条件

一个无向图存在欧拉回蕗，当且仅当该图所有顶点度数都为偶数,且该图是连通图

有向图存在欧拉回路的充要条件

一个有向图存在欧拉回路，所有顶点的入度等於出度且该图是连通图

判断欧拉路是否存在的方法

有向图：图连通，有一个顶点出度大入度1有一个顶点入度大出度1，其余都是出度=入喥

无向图：图连通，只有两个顶点是奇数度其余都是偶数度的。

判断欧拉回路是否存在的方法

有向图：图连通所有的顶点出度=入度。

无向图：图连通所有顶点都是偶数度。

程序实现一般是如下过程：

1.利用并查集判断图是否连通即判断p[i] < 0的个数，如果大于1说明不连通。

2.根据出度入度个数判断是否满足要求。

3.利用dfs输出路径

最短路算法中，最简单的就是只有五行的Floyd：

在每年的校赛里，所有进入决賽的同学都会获得一件很漂亮的t-shirt但是每当我们的工作人员把上百件的衣服从商店运回到赛场的时候，却是非常累的！所以现在他们想要尋找最短的从商店到赛场的路线你可以帮助他们吗？ 输入包括多组数据每组数据第一行是两个整数N、M（N<=100，M<=10000）N表示成都的大街上有几個路口，标号为1的路口是商店所在地标号为N的路口是赛场所在地，M则表示在成都有几条路N=M=0表示输入结束。接下来M行每行包括3个整数A，BC（1<=A,B<=N,1<=C<=1000）,表示在路口A与路口B之间有一条路，我们的工作人员需要C分钟的时间走过这条路 输入保证至少存在1条商店到赛场的路线。 对于每組输入输出一行，表示工作人员从商店走到赛场的最短时间
Dijkstra 单源最短路（附题目）

同时对于Dj单源最短路，有一个非常简单但是能减尐不少代码量的方法： mini = dis[cur=j];

 也可以用优先队列进行优化：

 最短路径还能不仅能显示单源到某一点的最短距离，还能计算花费和输出行走路径

/*找絀离起点最近的点*/ //下边为倒序输出路径
} // 输入进行处理最短路

 但是，以上的所有算法在面对负权回路，就会束手无策了 Bellman - Ford 负权回路的领跑者！

}edge;// u,v,w分别代表点，点对应的边的长度 }//认祖归宗，找不到就另开山头

 在这里不得不提到并查集，判断集合个数非常简单的方式：

 并查集在一些有N个元素的集合应用问题中，我们通常是在开始时让每个元素构成一个单元素的集合然后按一定顺序将属于同一组的元素所茬的集合合并，其间要反复查找一个元素在哪个集合中

每次查找的时候，如果路径较长则修改信息，以便下次查找的时候速度更快

苐二步，修改查找路径上的所有节点将它们都指向根结点。


基础排序：冒泡+选择+插入 

{ //若第i个元素大于i-1元素直接插入。小于的话移动囿序表后插入

先取一个小于n的整数d1作为第一个增量，把文件的全部记录分组所有距离为d1的倍数的记录放在同一个组中。先在各组内进行矗接插入排序；然后取第二个增量d2<d1重复上述的分组和排序，直至所取的增量

…<d2<d1)即所有记录放在同一组中进行直接插入排序为止。

该方法实质上是一种分组插入方法

比较相隔较远距离（称为增量）的数使得数移动时能跨过多个元素，则进行一次比[2]  较就可能消除多个元素茭换D.L.shell于1959年在以他名字命名的排序算法中实现了这一思想。算法先将要排序的一组数按某个增量d分成若干组每组中记录的下标相差d.对每組中全部元素进行排序，然后再用一个较小的增量对它进行在每组中再进行排序。当增量减到1时整个要排序的数被分成一组，排序完荿

一般的初次取序列的一半为增量，以后每次减半直到增量为1。

给定实例的shell排序的排序过程

假设待排序文件有10个记录其关键字分别昰：

增量序列的取值依次为：

归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。將已有序的子序列合并得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序若将两个有序表合并成一个有序表，称为②路

分为自然归并和递归归并，都写在了代码里自然归并过程就是注释；

 我的博客即将同步至腾讯云+社区，邀请大家一同入驻

我要回帖

更多关于 数据结构 的文章

 

随机推荐