军队文职-计算机类计算机类-数据结构与算法知识点总结.docx

精品名师归纳总结数据结构学问点总结内容概要：基本概念 线性表 栈与队列 树与二叉树 图查找算法 排序算法可编辑资料 - - - 欢迎下载精品名师归纳总结一、基本概念1 、数据元素是数据的基本单位。2 、数据项是数据不行分割的最小单位。3 、数据结构的规律结构（抽象的,与实现无关）物理结构（储备结构）次序映像（次序储备结构）位置“相邻”非次序映像（链式储备结构）指针表示关系4 、算法特性：算法具有正确性、有穷性,确定性,（可行性）、输入,输出正确性：能按设计要求解决详细问题,并得到正确的结果。有穷性：任何一条指令都只能执行有限次,即算法必需在执行有限步后终止。确定性：算法中每条指令的含义必需明确,不答应由二义性可行性：算法中待执行的操作都非常基本,算法应当在有限时间内执行完毕。输入：一个算法的输入可以包含零个或多个数据。可编辑资料 - - - 欢迎下载精品名师归纳总结输出：算法有一个或多个输出5 、算法设计的要求：（ 1）正确 性：算法应能满意设定的功能和要求。（ 2）可读 性：思路清楚、层次分明、易读易懂。（ 3）健壮 性：输入非法数据时应能作适当的反应和处理。（ 4）高效 性（时间复杂度） ：解决问题时间越短,算法的效率就越高。（ 5）低储备量（空间复杂度） ：完成同一功能,占用储备空间应尽可能少。二、线性表1 、线性表List：最常用且最简洁的数据结构。含有大量记录的线性表称为文件。2 、线性表是 n 个数据元素的有限序列。线性结构的特点：“第一个”“最终一个”前驱 后继。3 、次序表 线性表的次序储备结构特点可编辑资料 - - - 欢迎下载精品名师归纳总结a) 规律上相邻的元素在物理位置上相邻。b) 随机拜访。1) typedef structDataType elemMAXSIZE;01L.elem.MAXSIZE-1L.length=0可编辑资料 - - - 欢迎下载精品名师归纳总结int length; SqList;L.elemL.elemL.length=MAXSIZE 0<L.length<MAXSIZE可编辑资料 - - - 欢迎下载精品名师归纳总结2) 表长为 n 时,线性表进行插入和删除操作的时间复杂度为O（ n）插入一个元素时大约移动表中的一半元素。删除一个元素时大约移动表中的（n-1 ）2 4 、线性表的链式储备结构1) 类型定义简而言之, “数据+ 指针”。typedef struct LNode 可编辑资料 - - - 欢迎下载精品名师归纳总结DataType data;struct LNode *next; LNode, *LinkList;2) 不带头结点的空表判定为L= =null带头结点的空表判定为L->next= =null 循环单链表为空的判定条件为L.next= =L 线性链表的最终一个结点的指针为NULL头结点的数据域为空,指针域指向第一个元素的指针。5 、次序表和单链表的比较datanext可编辑资料 - - - 欢迎下载精品名师归纳总结次序表单链表的址相邻表示关系指针表示关系机拜访,取元素 O1序拜访,取元素On入、删除需要移动元素On入、删除不用移动元素On用于查找位置 6 、次序储备：优点：储备密度大,可随机储备缺点：大小固定。不利于增减节点;储备空间不能充分利用。容量难扩充可编辑资料 - - - 欢迎下载精品名师归纳总结链式储备：优点：易于插入删除。可动态申请空间。表容量仅受内存空间限制缺点：增加了储备空间的开销。不行以随机储备元素可编辑资料 - - - 欢迎下载精品名师归纳总结三、栈与队列1 、栈栈：限定仅在表尾进行插入或删除操作的线性表。栈顶：表尾端栈底：表头栈是先进后出的线性表。插入栈顶元素称为入栈,删除栈顶元素称为出栈。2 、栈分为链栈和次序栈·链栈用不带头结点的单链表实现。·次序栈类似于次序表,插入和删除操作固定于表尾。Sanan-1.a1/可编辑资料 - - - 欢迎下载精品名师归纳总结可编辑资料 - - - 欢迎下载精品名师归纳总结进栈: 进栈运算是在栈顶位置插入一个新x元。素算法思想：(a) 判栈是否为满,如栈满,作溢出处理,并0。返回 b如栈未满,栈顶指t针op加1。 c将新元素x送入栈顶,并返1回。算法实现：int Push SeqSta*cs,k datatypex if （s->top= =MAXLE1N）出栈: 出栈运算是指取出栈顶元素,赋给某一个指x定。变量算法步骤：(a) 判栈是否为空,如栈空,作下溢处理,并0。返回(b) 如栈非空,将栈顶元素赋给变x。量(c) 指针top减1,并返回1。算法实现：可编辑资料 - - - 欢迎下载精品名师归纳总结return 。0 else s->top。+/ 栈满不能入栈,且返0回datatypePop（SeqStac*ks）datatypxe;可编辑资料 - - - 欢迎下载精品名师归纳总结s->datas->top。=/x/ 栈不满,就压入元x素if SEmptys 可编辑资料 - - - 欢迎下载精品名师归纳总结return 。1 / 进栈胜利,返回1return 。0/ 如栈空不能出栈,且返回0可编辑资料 - - - 欢迎下载精品名师归纳总结else x=s->datas-。>top/ 栈不空就栈顶元素存*入xs->top-。-可编辑资料 - - - 欢迎下载精品名师归纳总结return 。x/ 出栈胜利,返回1可编辑资料 - - - 欢迎下载精品名师归纳总结3 、队列先进先出的线性表。队尾入队 对头出队答应插入的一端叫做队尾答应删除的一端叫做对头4 、链队列可编辑资料 - - - 欢迎下载精品名师归纳总结typedef struct queuenodedatatypedata;structqueuenode*next;queuenode;/ 链队结点的类型datatypetypedefstructqueuenodelinkqueue;front*front,*rear;/ 将头指针、尾指针封装在一起的链队ABJprear·图4-6链队列示意图5 、 循环队列typedef struct DataType elemMAXSIZE;int front, rear;/队头、队尾位置 SqQueue;·循环队列判定队空的条件为front=rear循环队列判定队满的条件为（rear+1） %m=front在一个循环队列中删除元素时,第一需要后移队首指针。6 、栈与队列比较： 都是线形结构,栈的操作LIFO（后进先出） ,队列操作 FIFO（先进先出） 。四、树和二叉树可编辑资料 - - - 欢迎下载精品名师归纳总结1. 树的定义树（ Tree ）：是 n （ n 0）个有限数据元素的集合。在任意一棵非空树T 中：（ 1）有且仅有一个特定的称为树根（Root）的结点,根结点无前趋结点。（ 2）当 n>1 时,除根结点之外的其余结点被分成mm>0个互不相交的集合T1, T2, Tm,其中每一个集合 Ti （ 1 i m）本身又是一棵树,并且称为根的子树。2. 基本术语：结点的度数：结点的非空子树（即后缀）个数叫作结点的度数树叶、分支结点：左（右）子树均为空二叉树的结点称作树叶否就称作分支结点。结点的层数：规定根的层数是0,其余结点的层数等于其父结点的层数加1孩子和双亲： 树的深度：树的度数：树中度数最大的结点度数叫作树的度数树林：是由零个或多个不相交的树所组成的集合。3. 二叉树性质：1) 二叉树的第 i 层上至多有 2i-1 个结点。k2) 深度为 k 的二叉树至多有 2k-1 个结点。满二叉树 ：深度为 k,有 2 -1 个结点。完全二叉树 ：给满二叉树的结点编号,从上至下,从左至右,n 个结点的完全二叉树中结点在对应满二叉树中的编号正好是从1 到 n。3) 叶子结点 n0,度为 2 的结点为 n2,就 n0 = n2+1。考虑结点个数： n = n0 + n1 + n2考虑分支个数： n-1 = 2n 2 + n1可得 n 0 = n2+1可编辑资料 - - - 欢迎下载精品名师归纳总结4) n 个结点的完全二叉树深度为log n1 。可编辑资料 - - - 欢迎下载精品名师归纳总结5n 个结点的完全二叉树,结点按层次编号有：i 的双亲是n / 2 ,假如 i = 1 时为根（无双亲） 。i 的左孩子是 2i,假如 2i>n,就无左孩子。i 的右孩子是 2i + 1,假如 2i + 1>n 就无右孩子。4.二叉树的储备结构·次序储备结构用数组、编号 i 的结点存放在 i-1 处。适合于储备完全二叉树。·链式储备结构二叉链表：typedef struct BTNode DataType data;struct BTNode *lchild, *rchild; BTNode, *BinTree;三叉链表：typedef struct BTNode DataType data;struct BTNode *lchild, *rchild, *parent; BTNode, *BinTree;lchilddatarchildlchilddataparentrchild在链式储备结构中,含有 n 个结点的二叉链表有 n+1 个空链域。5. 遍历二叉树 （先序 DLR、中序 LDR、后序 LRD）方法与 C语言描述由二叉树的递归定义可知,一棵二叉树由根结点（ D）、根结点的左子树（ L）和根结点的右子树（ R）三部分组成。因此,只要依次遍历这三部分,就可以遍历整个二叉树。一般有三种方法：先序 前序 遍历 DLR（根左右）、中序遍历 LDR（左根右）、 后序遍历 LRD（左右根） 。可编辑资料 - - - 欢迎下载精品名师归纳总结1 先序遍历（DLR ）的递归过程void PreorderBT*T/ 先序遍历二叉树BT if T= =NULL return;/ 递归调用的终止条件 printfT->data;/ 输出结点的数据域PreorderT->lchild;/ 先序递归遍历左子树PreorderT->rchild;/ 先序递归遍历右子树2 中序遍历（L DR）的递归过程void InorderBT*T/ 中序遍历二叉树BT if T= =NULL return;/ 递归调用的终止条件 InorderT->lchild;/中序递归遍历左子树printfT->data;/ 输出结点的数据域InorderT->rchild;/ 中序递归遍历右子树可编辑资料 - - - 欢迎下载精品名师归纳总结3 后序遍历（ L RD）的递归过程可编辑资料 - - - 欢迎下载精品名师归纳总结void PostorderBT*T/后序遍历二叉树BT if T= =NULL return;/ 递归调用的终止条件 PostorderT->lchild;/ 后序递归遍历左子树PostorderT->rchild;/ 后序递归遍历右子树printfT->data;/输出结点的数据域6. 线索二叉树n 个结点的二叉链表中有n+1 个空指针,可以利用其指向前驱或后继结点,叫线索 ,同时需附加一个标志, 区分是子树仍是线索。lchild ltagdatartag rchild 0/10/1lchild有左子树,就指向左子树,标志ltag = 0。没有左子树,可作为前驱线索,标志ltag = 1。rchild有右子树,就指向右子树,标志rtag = 0。没有右子树,可作为后继线索,标志rtag = 1。7. 树和森林树的储备结构双亲表示法 , 孩子表示法 , 孩子兄弟表示法 。特点：双亲表示法简洁求得双亲,但不简洁求得孩子。孩子表示法简洁求得孩子,但求双亲麻烦。两者可以结合起来使用。孩子兄弟表示法,简洁求得孩子和兄弟,求双亲麻烦,也可以增加指向双亲的指针来解决。树与二叉树的转换表 错误！文档中没有指定样式的文字。.1 树和二叉树的对应关系树对应的二叉树可编辑资料 - - - 欢迎下载精品名师归纳总结一个孩子孩子一个兄弟孩子树的遍历树的结构：根,根的子树。先根遍历：。例：ABCDEFGHIJ。K后根遍历：。例：CEDFBHGJKI。A遍历森林森林的结构：第一棵树的根,第一棵树的根的子树森林,其余树 除第一棵外 组成的森林。先序遍历：。例：ABCDEFGHI。J中序遍历：。例：BDCEAGFIJH。注：先序遍历森林,相当于依次先根遍历每一棵树。中根遍历森林相当于后根遍历每一棵树。AAFH可编辑资料 - - - 欢迎下载精品名师归纳总结BGIBCEGIJ可编辑资料 - - - 欢迎下载精品名师归纳总结CDFHJKDE树的结构划森林的结构划分遍历树、森林与遍历二叉树的关系遍历树、森林和二叉树的关系树森林二叉树根遍历序遍历序遍历根遍历序遍历序遍历8. 哈夫曼树：叶子结点带有权值的最小带权路径长度的最优二叉树构造赫夫曼树每次取两个最小的树组成二叉树赫夫曼编码 前缀码 向左分支为 0,向右分支为 1,从根到叶子的路径构成叶子的前缀编码。五、图可编辑资料 - - - 欢迎下载精品名师归纳总结1 完全图：有 12 nn-1 条变得无向图有向完全图：具有n（ n-1）条弧的有向图。权：与图的边或弧相关的数。顶点 v 的度：和 v 相关联的边的数目。入度：以顶点 v 为头的弧的数目出度：以顶点 v 为尾的弧的数目回路或环：第一个顶点和最终一个顶点相同的路径。简洁路径：序列中顶点不重复显现的路径。2. 图的储备结构·邻接矩阵：A01100B00110C00010D10000E10010·邻接表：typedef struct ArcNode /弧结点intadjvex;/邻接点struct ArcNode *nextarc;/下一个邻接点 ArcNode;typedef struct VexNode /顶点结点VertexTypedata;/顶点信息ArcNode *firstarc;/第一个邻接点 VexNode;const int MAX_VERTEX =最大顶点个数 ;typedef struct Graph /图VexNodevexsMAX_VERTEX;/顶点向量int Graph;vexnum, arcnum;/顶点和弧的个数边弧多就需要储备空间多。0A12/1B23/2C3/3D0/4E03/·十字链表：十字链表是有向图的另一种链式储备结构。可以看成是将有向图的邻接表和逆邻接表结合起来的一种链表。在十字链表中,对应于有向图中每一条弧有一个结点,对应于每个顶点有一个结点。可编辑资料 - - - 欢迎下载精品名师归纳总结·邻接多重表3. 图的遍历1) 深度优先（ DFS）搜寻拜访方式：从图中某顶点v 动身：a） 拜访顶点 v。b） 从 v 的未被拜访的邻接点动身,连续对图进行深度优先遍历,如从某点动身全部邻接点都已拜访过,退回前一个点连续上述过程,如退回开头点,终止。2) 广度（宽度, BFS）优先搜寻a）拜访顶点 v 。b） 拜访同 v 相邻的全部未被拜访的邻接点w 1,w2 ,kw。c） 依次从这些邻接点动身, 拜访它们的全部未被拜访的邻接点; 依此类推, 直到图中全部拜访过的顶点的邻接点都被拜访。4. 生成树和最小生成树每次遍历一个连通图将图的边分成遍历所经过的边和没有经过的边两部分,将遍历经过的边同图的顶点构成一个子图,该子图称为生成树。因此有DFS生成树和 BFS生成树。1最小生成树· Kruskal算法一句话,“不构成环的情形下,每次选取最小边”。5A325A325A32B3E6DB3E6DB3E6D13C7a13C7b13C7c5A 325A 325A 32B3E6DB3E6DB3E6D13C7d13C7e13C7f· 普里姆算法记 V 是连通网的顶点集, U 是求得生成树的顶点集,TE是求得生成树的边集。普里姆算法：(a) 开头时, U=v0, TE=。(b) 运算 U 到其余顶点 V-U 的最小代价,将该顶点纳入U,边纳入 TE。(c) 重复 b 直到 U=V。普里姆算法和克鲁斯卡尔算法的比较法里姆算法鲁斯卡尔算法间复杂度loge点与顶点个数 n 有关边的数目 e 无关与边的数目 e 有关顶点个数 n 无关用于稠密图用于稀疏图可编辑资料 - - - 欢迎下载精品名师归纳总结5. AOV- 网用顶点表示活动,边表示活动的优先关系的有向图称为AOV 网。拓扑排序：对 AOV 网络中顶点构造拓扑有序序列的过程。拓扑排序的方法(1) 在有向图中选一个没有前驱的顶点且输出之(2) 从图中删除该顶点和全部以它为尾的弧6. 关键路径AOE 网,关键路径AOE 网Activity On Edge带权的有向无环图,其中顶点表示大事,弧表示活动,权表示活动连续时间。在工程上常用来表示工程进度方案。关键路径：从源点到汇点的最长的一条路径,或者全部由关键活动构成的路径。7. 最短路径(1) 迪杰斯特拉算法求一个顶点到其他各顶点的最短路径。算法： a 初始化：用起点 v 到该顶点 w 的直接边 弧初始化最短路径,否就设为。(b) 从未求得最短路径的终点中挑选路径长度最小的终点u：即求得 v 到 u 的最短路径。可编辑资料 - - - 欢迎下载精品名师归纳总结(c) 修改最短路径：运算u 的邻接点的最短路径,如v, ,u+u,w<v,(d) 重复 b-c,直到求得 v 到其余全部顶点的最短路径。特点：总是依据从小到大的次序求得最短路径。,就以,wv, ,u,代w替。可编辑资料 - - - 欢迎下载精品名师归纳总结可编辑资料 - - - 欢迎下载精品名师归纳总结(2) 弗洛伊德算法求每对顶点之间的最短路径。i,j=minA依次运算 A0, A1, , An。A0为邻接矩阵,运算Ak时, Akk-1i,j, Ak-1i,k+Ak-1k,j。可编辑资料 - - - 欢迎下载精品名师归纳总结技巧： 运算 Ak的技巧。 第 k 行、第 k 列、对角线的元素保持不变, 对其余元素, 考查 Ai,j与 Ai,k+Ak,j （“行+列”）,假如后者更小就替换Ai,j,同时修改路径。六、查找1. 查找分为：静态查找表、动态查找表、哈希查找表2. 静态查找表：对查找表只作查找操作的查找表。动态查找表：查找过程中同时插入表中不含的元素,或者删除查找表中已有的元素的操作的查找表。3. 次序查找：次序查找又称线性查找,是最基本的查找方法之一。次序查找既适用于次序表,也适用于链表。4. 二分法（折半）查找：是一种效率较高的查找方法,但前提是表中元素必需按关键字有序（按关键字递可编辑资料 - - - 欢迎下载精品名师归纳总结增或递减）排列。5. 索引次序表查找又称分块查找。分块查找：块内无序、块间有序、如何分块效率最高6. 动态查找表：二叉排序树查找：二叉排序树的生成二叉排序树 二叉查找树 ：或者是一颗空树。或者如下1 如它的左子树不空,就左子树上全部的结点的值均小于他的根结点的值。2 如右子树不空,就右子树全部结点的值均大于她得根结点的值。3 左右子树也分别为二叉排序树。7. 哈希表：哈希函数构造：直接定址法、除留余数法、平方取中法,随机数法,数字分析法冲突解决方法：开放定址法、拉链法、公共溢出区法七、排序1. 插入类排序：·直接插入排序每次将一个待排序的数据元素,插入到前面已经排好序的数列中的适当位置,使数列依旧有序。直到待排序数据元素全部插入完为止。·折半插入排序·希尔排序基本思想：先将整个待排序记录序列分成为如干个子序列分别进行直接插入排序,待整个序列中的记录基本有序时在对全体序列进行一次直接插入排序,子序列的构成不是简洁的逐段分割,而是将像个某个增量的记录组成一个子序列。2. 交换类排序·起泡排序也称冒泡法,每相邻两个记录关键字比大小, 大的记录往下沉（也可以小的往上浮）。每一遍把最终一个下沉的位置登记,下一遍只需检查比较到此为止。到全部记录都不发生下沉时,整个过程终止（每交换一次,记录削减一个反序数） 。·快速排序在当前无序区 R1.H 中任取一个数据元素作为比较的"基准 " 不妨记为 X,用此基准将当前无序区划分为左右两个较小的无序区：R1.I-1 和 RI+1.H ,且左边的无序子区中数据元素均小于等于基准元素,右边的无序 子 区 中 数 据 元 素 均 大 于 等 于 基 准 元 素 , 而 基 准 X就 位 于 最 终 排 序 的 位 置 上 , 即R1.I- 1 X.Key RI+1.H1,I 当HR1.I-1 和 RI+1.H 均非空时,分别对它们进行上述的划分过程,直至全部无序子区中的数据元素均已排序为止。3. 挑选类排序·简洁挑选排序每一趟从待排序的数据元素中选出最小（或最大）的一个元素,次序放在已排好序的数列的最终,直到全部待排序的数据元素排完。·堆排序堆排序是一树形挑选排序,在排序过程中,将R1.N 看成是一颗完全二叉树的次序储备结构,利用完全二叉树中双亲结点和孩子结点之间的内在关系来挑选最小的元素。4. 归并类排序·二路归并排序可编辑资料 - - - 欢迎下载精品名师归纳总结5. 基数类排序·基数排序主要特点不需要进行关键字间的比较。多关键字排序：最高为优先（ MSD 法）从主关键字开头排序,再从次高位排序,一次类推,最终将全部子序列依次连接在一起成为一个有序序列。最低位优先（ LSD法）从最次位关键字开头排序,在对高一位的进行排序,直到成为一个有序序列。排序方法稳固性平均时间最坏情形帮助储备直接插入排序稳固O（ n*n ）O（n*n ）O（ 1）快速排序不稳固O（ nlbn ）O（n*n ）O（ lbn ）归并排序稳固OnlbnO（ nlbn ）O（ n）简洁挑选排序稳固O（ n*n ）O（n*n ）O（ 1）堆排序不稳固O（ nlbn ）O（ nlbn ）O1基数排序稳固O（ d（ n+rd ）O（d（ n+rd ）O（ rd）选取排序方法需要考虑的因素：(1) 待排序的元素数目n。(2) 元素本身信息量的大小。(3) 关键字的结构及其分布情形。(4) 语言工具的条件,帮助空间的大小等。小结：(1) 如 n 较小 n <= 50 ,就可以采纳直接插入排序或直接挑选排序。由于直接插入排序所需的记录移动操作较直接挑选排序多,因而当记录本身信息量较大时,用直接挑选排序较好。(2) 如文件的初始状态已按关键字基本有序,就选用直接插入或冒泡排序为宜。(3) 如 n 较大,就应采纳时间复杂度为Onlog2n 的排序方法：快速排序、堆排序或归并排序。快速排序是目前基于比较的内部排序法中被认为是最好的方法。(4) 在基于比较排序方法中,每次比较两个关键字的大小之后,仅仅显现两种可能的转移,因此可以用一棵二叉树来描述比较判定过程,由此可以证明：当文件的n 个关键字随机分布时,任何借助于"比较 "的排序算法,至少需要Onlog2n 的时间。算法分析学问点总结算法概述1、算法的五个性质： 有穷性、确定性、能行性、输入、输出。2、算法的复杂性取决于： （1）求解问题的规模（ N） ,（ 2）详细的输入数据（ I）,（ 3）算法本身的设计（ A）, C=FN,I,A。3、算法的时间复杂度的上界记号O,下界记号 记为 fN =gN。即算法的实际运行时间至少需要gn的某个常数倍时间,同阶记号 ： fN= gN表示 fN和 gN同阶 。即算法的实际运行时间大约为gn的某个常数倍时间。低阶记号 o：fN=ogN 表示 fN 比 gN低阶。可编辑资料 - - - 欢迎下载精品名师归纳总结多项式算法时间：O1<Ologn<On<Onlogn<On2<On3商定 logn 表示以 2 为底的对数。指数时间算法时间： O2n<On.<Onn4、常用算法的设计技术：分治法、动态规划法、贪心法、回溯法和分支界限法。5、常用的几种数据结构：线性表、树、图。6、算法 :是指解决某一问题的运算序列递归与分治1、递归算法的思想： 将对较大规模的对象的操作归结为对较小规模的对象实施同样的操作。递归的时间复杂性可归结为递归方程：其中, a 是子问题的个数,b 是递减的步长,表示递减方式, Dn是合成子问题的开销。递归元的递减方式 有两种： 1、减法,即 n b,的形式。 2、除法,即 n / b ,的形式。2、递减方式为减法设 Dn为常数,就有 Tn = Oan。p这里都是针对递减方式为除法的哦Dn为常数 c： 这时, Tn = On 。Dn为线形函数 cn：Dn为幂函数 nx：考虑以下递归方程： T1 = 1Tn = 4Tn/2 +n Tn = 4Tn/2 +n 2 Tn = 4Tn/2 +n 3解：方程中均为 a = 4, b = 2,其齐次解为 n2。可编辑资料 - - - 欢迎下载精品名师归纳总结对, a > b1 Dn = n2Tn = On 。可编辑资料 - - - 欢迎下载精品名师归纳总结对, a = b2 Dn = n2 Tn = On2log n。 对, a < b3 Dn = n3 Tn = On3。证明一个算法的正确性需要证明两点：1、算法的部分正确性。2、算法的终止性。3、汉诺塔问题：void Hanoiint n, int Fr, int To, int As可编辑资料 - - - 欢迎下载精品名师归纳总结ifn > 0 Hanoin 1, A, C, B; MoveA, B;Hanoin 1, C, B, A4、二分查找代码可编辑资料 - - - 欢迎下载精品名师归纳总结贪心算法 （旅行商问题、单源最短路径问题）以下两种算法都是为了查找最小生成树问题的算法：1、Prim 算法的基本思想：在保证连通的前提下依次选出权重较小的（在实现中表达为n 个顶点的挑选） 。G=V, E为无向连通带权图,令V=1, 2, , n。设置一个集合 S ,初始化 S = 1, T = 。贪心策略：假如 V S 中的顶点 j 与 S 中的某个点 i 连接且 i, j入 S,并将 i, j 加入 T 中 。重复执行贪心策略,直至V S 为空。=证= 明最小生成树必定包含最小权值边如 G 的任何最小生成树都不包含e1。设 T 为 G 的最小生成树, e1n 1 条边。的权重最小,于是就挑选j 将 j 加=T。于是 T+e1 是一个有回路的图且该回路中包含e1。该回路中必有条不是e 的边 ei。令 T=T+1eei 。T也是 G 的生成树。又 cT = cT+ ce1 ce i, ce1 cie,从而 cT ,cTT是 G 的最小生成树且含有边e1。冲突。故必定有图G的最小生成树包含了e1 。=2、Kruskal算法的基本思想： 基本思想：在保证无回路的前提下依次选出权重较小的n 1 条边。假如i, j是 E 中尚未被选中的边中权重最小的,并且i, j不会与已经挑选的边构成回路,于是就挑选i, j 。详细做法 :先把全部 n 个点画出来。不画边。然后把权值最小的那条边画上去。然后再把当前权值最小的边 不算画了的边 画上去。假如构成回路就舍弃这条边。然后始终直到画了n-1 条边3、 Prim 与 Kruskal两算法的复杂性：2Prim 算法为两重循环,外层循环为n 次,内层循环为On ,因此其复杂性为On 。Kruskal 算法中,设边数为 e,就边排序的时间为Oeloge,最多对 e 条边各扫描一次,每次确定边的时间为 Ologe,所以整个时间复杂性为Oeloge。当 e =2n时, Kruska