严蔚敏数据结构复习资料汇总整编完整编辑版_第1页
严蔚敏数据结构复习资料汇总整编完整编辑版_第2页
严蔚敏数据结构复习资料汇总整编完整编辑版_第3页
严蔚敏数据结构复习资料汇总整编完整编辑版_第4页
严蔚敏数据结构复习资料汇总整编完整编辑版_第5页
已阅读5页,还剩71页未读, 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

1.复杂性分析对各种操作的时间复杂性的分析。主要是链表,树,排序等简单一些的分析。分析的时候,从简单的入手,学会方法。后续的各种豆可能让你分析时间复杂度。线性链表(顺序表和单链表)(链表L循环链表双向链表队列(循环队列)栈链表主要操作:找某一个元素,插入一个(在哪个位置增加),删除一个(在哪个位置删除)。栈:查找,插入(位置固定),删除(位置固定)队列:查找,插入(位置固定),删除(位置固定)顺序表(可以视为一个数组)

下标7E®: 0A1B2C3D4E5F6G, 7H■AxsrzE-i单链表:(删除)(插入)倒置:(查找)循环链表双向链表栈:(插入删除查找)Push(B)PushpjP叩0 PopO吕怕ck的Pu由和P邛,遵循先进后出理则队列(插入删除查找)循环队列的实现,并不是像上面的图那样,实现了一个循环的样子。3.二叉树基本概念二叉树是每个节点最多有两个子树的有序树。二叉树常被用于实现二叉查找树和二叉堆。值得注意的是,二叉树不是树的特殊情形。二叉树是每个结点最多有两个子树的有序树。通常根的子树被称作"左子树"(leftsubtree)和“右子树"(rightsubtree)。二叉树常被用作二叉查找树和二叉堆或是二叉排序树。二叉树的每个结点至多只有二棵子树:不存在出度大于2的结点),二叉树的子树有左右之分,次序不能颠倒。二叉树不是树的一种特殊情形,尽管其与树有许多相似之处,但树和二叉树有两个主要差别:.树中结点的最大度数没有限制,而二叉树结点的最大度数为2;.树的结点无左、右之分,而二叉树的结点有左、右之分。二叉树是递归定义的,其结点有左右子树之分,逻辑上二叉树有五种基本形态:(1)空二叉树——如图(a);(2)只有一个根结点的二叉树一一如图(b);(3)只有左子树一一如图(c);(4)只有右子树一一如图(d);(5)完全二叉树一一如图(e)注意:尽管二叉树与树有许多相似之处,但二叉树不是树的特殊情形(Qi―一&) 履) S性质⑴在非空二叉树中,第i层的结点总数不超过,i>=1;(2)深度为h的二叉树最多有2^h-1个结点(h>=1),最少有h个结点;(3)对于任意一棵二叉树,如果其叶结点数为N0,而度数为2的结点总数为N2,则N0=N2+1;(4)具有n个结点的完全二叉树的深度为⑸有N个结点的完全二叉树各结点如果用顺序方式存储,则结点之间有如下关系:若I为结点编号则如果1>1,则其父结点的编号为I/2;如果2*I<=N,则其左儿子(即左子树的根结点)的编号为2*I;若2*I>N,则无左儿子;如果2*I+1<=N,则其右儿子的结点编号为2*I+1;若2*1+1小,则无右儿子。(6)给定N个节点,能构成h(N)种不同的二叉树。h(N)为卡特兰数的第N项。h(n)=C(2*n,n)/(n+1)。(7)设有i个枝点,I为所有枝点的道路长度总和,J为叶的道路长度总和J=I+2i存储结构顺序存储表示0 1 2 3 4 5 6二叉树可以用数组或线性表来存储,而且如果这是满二叉树,这种方法不会浪费空间。用这种紧凑排列,如果一个结点的索引为i,它的子结点能在索引2i+1和2i+2找到,并且它的父节点(如果有)能在索引floor((i-1)/2)找到(假设根节点的索引为0)。这种方法更有利于紧凑存储和更好的访问的局部性,特别是在前序遍历中。然而,它需要连续的存储空间,这样在存储高度为h的n个结点组成的一般普通树时将会浪费很多空间。一种最极坏的情况下如果深度为h的二叉树每个节点只有右孩子需要占用2的h次幕减1,而实际却只有h个结点,空间的浪费太大,这是顺序存储结构的一大缺点。/*二叉树的顺序存储表示*/#defineMAX_TREE_SIZE100/*二叉树的最大节点数*/typedefTElemTypeSqBiTree[MAX_TREE_SIZE];/*0号单元存储根节点*/typedefstruct(intlevel,order;/*节点的层,本层序号(按满二叉树计算)*/}position;二叉链表存储表示/*二叉榭的二叉金逋表存储表示*/typedefstructBiTNode(TElemTypedata;structBiTNode*lchild,*rchild;/*左右孩子指金十*/

}BiTNode,*BiTree;遍历算法二叉树的遍历三种方式,如下:(1)前序遍历(DLR),首先访问根结点,然后遍历左子树,最后遍历右子树。简记根-左-右。(2)中序遍历(LDR),首先遍历左子树,然后访问根结点,最后遍历右子树。简记左-根-右。(3)后序遍历(LRD),首先遍历左子树,然后遍历右子树,最后访问根结点。简记左-右-根。Z例1:如上图所示的二叉树,若按前序遍历,则其输出序列为 。若按中序遍历,则其输出序列为 。若按后序遍历,则其输出序列为 。

前序:根A,A的左子树B,B的左子树没有,看右子树,为D,所以A-B-D。再来看A的右子树,根C,左子树E,E的左子树F,E的右子树G,G的左子树为H,没有了结束。连起来为C-E-F-G-H,最后结果为ABDCEFGH中序:先访问根的左子树,B没有左子树,具有右子树D,D无左子树,下面访问树的根A,连起来是BDA。再访问根的右子树,C的左子树的左子树是F,F的根E,E的右子树有左子树是H,再从H出发找到G,到此C的左子树结束,找到根C,无右子树,结束。连起来是FEHGC,中序结果连起来是BDAFEHGC后序:B无左子树,有右子树D,再到根B。再看右子树,最下面的左子树是F.其根的右子树的左子树是H,再到H的根G,再到G的根E,E的根C无右子树了直接到C这时再和B找它们具有的根A所以连起来是DBFHGECA在深度优先中,我们希望从根结点访问最远的结点。和图的深度优先搜索不同的是,不需记住访问过的每一个结点,因为树中不会有环。■广度优先遍历和深度优先遍历不同,广度优先遍历会先访问离根节点最近的节点。完全二叉树,满二叉树飙)清一一反树(bj飙)清一一反树(bj完全二义树.满二叉树:一棵深度为k,且有 个节点称之为满二叉树.完全二叉树:深度为k,有n个节点的二叉树,当且仅当其每一个节点都与深度为k的满二叉树中,序号为1至n的节点对应时,称之为完全二叉树4.树基本概念树(tree)是包含n(n>0)个结点的有穷集,其中:(1)每个元素称为结点(node);(2)有一个特定的结点被称为根结点或树根(root)。(3)除根结点之外的其余数据元素被分为m(m>0)个互不相交的集合T1,T2,……Tm-1,其中每一个集合Ti(1<=i<=m)本身也是一棵树,被称作原树的子树(subtree)。树也可以这样定义:树是由根结点和若干颗子树构成的。树是由一个集合以及在该集合上定义的一种关系构成的。集合中的元素称为树的结点,所定义的关系称为父子关系。父子关系在树的结点之间建立了一个层次结构。在这种层次结构中有一个结点具有特殊的地位,这个结点称为该树的根结点,或称为树根。我们可以形式地给出树的递归定义如下:单个结点是一棵树,树根就是该结点本身。设T1,T2,..,Tk是树,它们的根结点分别为n1,n2,..,nk。用一个新结点n作为n1,n2,..,nk的父亲,则得到一棵新树,结点n就是新树的根。我们称n1,n2,..,nk为一组兄弟结点,它们都是结点n的子结点。我们还称T1,T2,..,Tk为结点n的子树。空集合也是树,称为空树。空树中没有结点。.节点的度:一个节点含有的子树的个数称为该节点的度;.树的度:一棵树中,最大的节点的度称为树的度;.叶节点或终端节点:度为零的节点;.非终端节点或分支节点:度不为零的节点;.父亲节点或父节点:若一个节点含有子节点,则这个节点称为其子节点的父节点;.孩子节点或子节点:一个节点含有的子树的根节点称为该节点的子节点;.兄弟节点:具有相同父节点的节点互称为兄弟节点;.节点的层次:从根开始定义起,根为第1层,根的子节点为第2层,以此类推;.树的高度或深度:树中节点的最大层次;.堂兄弟节点:父节点在同一层的节点互为堂兄弟;.节点的祖先:从根到该节点所经分支上的所有节点;.子孙:以某节点为根的子树中任一节点都称为该节点的子孙。.森林:由m(m>=0)棵互不相交的树的集合称为森林;存储父节点表示法/*树节点的定义*/#defineMAX_TREE_SIZE100typedefstruct{TElemTypedata;intparent;/*父节点位置域*/}PTNode;typedefstruct{PTNodenodes[MAX_TREE_SIZE];intn;/*节点数*/}PTree;孩子链表表示法/*树的孩子链表存储表示*/typedefstructCTNode{//孩子节点intchild;structCTNode*next;}*ChildPtr;typedefstruct{ElemTypedata;//节点的数据元素ChildPtrfirstchild;//孩子链表头指针}CTBox;typedefstruct{CTBoxnodes[MAX_TREE_SIZE];intn,r;//节点数和根节点的位置}CTree;6.森林■树与二叉树的转换将树转换为二叉榭树中每个结点最多只有一个最左边的孩子(长子)和一个右邻的兄弟。按照这种关系很自然地就能将树转换成相应的二叉树:①在所有兄弟结点之间加一连线;②对每个结点,除了保留与其长子的连线外,去掉该结点与其它孩子的连线。树招化点•下本树招化点•下本注意:由于树根没有兄弟,故树转化为二叉树后,二叉树的根结点的右子树必为空。2)将一个森林转换为二叉树具体方法是:①将森林中的每棵树变为二叉树②因为转换所得的二叉树的根结点的右子树均为空,故可将各二叉树的根结点视为兄弟从左至右连在一起,就形成了一棵二叉树。森林转化为:叉刺森林转化为:叉刺二叉树到树、森林的转换把二叉树转换到树和森林自然的方式是:若结点x是双亲y的左孩子,则把x的右孩子,右孩子的右孩子,…,都与y用连线连起来,最后去掉所有双亲到右孩子的连线。二元组的定义图G是一个有序二元组(V,E)其中丫称为顶集(VerticesSet),E称为边集(Edgesset),E与V不相交。它们亦可写成V(G)和E(G)。E的元素都是二元组,用(x,y)表示,其中x,y£V。三元组的定义图G是指一个三元组(V,E,I),其中V称为顶集,E称为边集,E与V不相交;I称为关联函数,1将E中的每一个元素映射到。如果e被映射到(u,v),那么称边e连接顶点u,v,而u,v则称作e的端点,u,v此时关于e相邻。同时,若两条边i,j有一个公共顶点u,则称i,j关于u相邻。有/无向如果给图的每条边规定一个方向,那么得到的图称为有向图。在有向图中,与个节点相关联的边有出边和入边之分。相反,边没有方向的图称为无向图。简单图一个图如果.没有两条边,它们所关联的两个点都相同(在有向图中,没有两条边的起点终点都分别相同);.每条边所关联的是两个不同的顶点则称为简单图(Simplegraph)。简单的有向图和无向图都可以使用以上的“二元组的定义〃,但形如的序对不能属于E。而无向图的边集必须是对称的,即如果基本术语阶(Order):图G中顶集V的大小称作图G的阶。子图(Sub-Graph):当图6'=(丫'旧)其中丫包含于V,E’包含于E,则G'称作图G=(V,E)的子图。每个图都是本身的子图。生成子图(SpanningSub-Gr叩h):指满足条件V(G')=V(G)KG的子图G。导出子图(InducedSubgraph):以图G的顶点集V的非空子集V1为顶点集,以两端点均在V1中的全体边为边集的G的子图,称为V1导出的导出子图;以图G的边集E的非空子集E1为边集,以E1中边关联的顶点的全体为顶点集的G的子图,称为E1导出的导出子图。度(Degree):一个顶点的度是指与该顶点相关联的边的条数,顶点v的度记作d(v)。入度(皿兄69侔6)和出度(Out-degree):对于有向图来说,一个顶点的度可细分为入度和出度。一个顶点的入度是指与其关联的各边之中,以其为终点的边数;出度则是相对的概念,指以该顶点为起点的边数。自环(Loop):若一条边的两个顶点为同一顶点,则此边称作自环。路径(Path):从u到v的一条路径是指一个序列v0,e1,v1,e2,v2,二6口匕其中ei的顶点为vi及vi-1,k称作路径的长度。如果它的起止顶点相同,该路径是〃闭〃的,反之,则称为〃开〃的。一条路径称为一简单路径simplepath),如果路径中除起始与终止顶点可以重合外,所有顶点两两不等。行迹(Trace):如果路径P(u,v)中的边各不相同,则该路径称为u到v的一条行迹。轨道(Track):如果路径P(u,v)中的顶点各不相同,则该路径称为u到v的一条轨道。闭的行迹称作回路(Circuit),闭的轨称作圈(Cycle)。(另一种定义是:walk对应上述的path,path对应上述的track。Trail对应trace。)桥(Bridge):若去掉一条边,便会使得整个图不连通,该边称为桥.数组(邻接矩阵)存储表示(有向或无向)typedefstruct{VR7ypeadj.;“顶点关系类型。对无权图,用丫是)或可否)表示相邻否;对带权图,贝U为权值In-foType*info;typedefstruct{VR7ypeadj.;“顶点关系类型。对无权图,用丫是)或可否)表示相邻否;对带权图,贝U为权值In-foType*info;“该弧相关信息的指针(可无)Pr^Cell^AdjMatrinEMAX_VERTEX_NLIM][MAX_VERTEX_NUM]i//二维数组structMGraph//顶点向里H邻接矩陌//图的当前顶点数和弧数"图的种类标志VertexTypetfeKS[MAX_VERTEX_MUM];GraphKindkind;AdjMatrixarcs;veKnunijarcnum;.邻接表存储表示邻接表是图的一种链式存储结构邻接表中,对图中每个顶点建立一个单链表,第i个单链表中的结点表示依附于顶点Vi的边(对有向图是以顶点《为尾的弧)。邻接表中的表结点和头结点结构:adjveHnewta:rinfodataf£rst-arcadjveHnewta:rinfodataf£rst-arc无向图的邻接表头纣点I।I表结点A3A有向图的邻接表和逆邻接表(一)在有向图的邻接表中,第i个单链表链接的边都是顶点i发出的边。(二)为了求第i个顶点的入度,需要遍历整个邻接表。因此可以建立逆邻接表。(三)在有向图的逆邻接表中,第i个单链表链接的边都是进入顶点i的边。出迫表 ,人边表口)邻接表 也}逆邻接表邻接表小结设图中有n个顶点,e条边,则用邻接表表示无向图时,需要n个顶点结点,2e个表结点;用邻接表表示有向图时,若不考虑逆邻接表,只需n个顶点结点,e个边结点。在无向图的邻接表中,顶点vi的度恰为第i个链表中的结点数。在有向图中,第i个链表中的结点个数只是顶点看的出度。在逆邻接表中的第i个链表中的结点个数为vi的入度。建立邻接表的时间复杂度为O(n+e)。3.有向图的十字链表存储表示

十字链表表示特点.针对弧结点,增加入弧链表结构和出弧链表结构;.容易求得任意顶点的出度和入度,专用于有向图的操作;3.结构实现比较复杂。基本数据结构L弧的数据结构typedefstructArcinttailvex;intheadvex;structOLGArc*hlink;structOLGArc^tlink;}OLGArc;.顶点结构typedefstructVexNodechardata;OLGArc^firstin;OLGArc泮firstout;}OLGVNode;,图的十字链表表示typedefstruct{OLGVNodexlist[MAX_VERTEX_NUM];intvexnum;intarcnum;jOLGraph;.无向图的邻接多重表存储表示邻接多重表(Adjacency”3节后日主要用于存储无向图。因为,如果用邻接表存储无向图,每条边的两个边结点分别在以该边所依附的两个顶点为头结点的链表中,这给图的某些操作带来不便。例如,对已访问过的边做标记,或者要删除图中某一条边等,都需要找到表示同一条边的两个结点。因此,在进行这一类操作的无向图的问题中采用邻接多重表作存储结构更为适宜。邻接多重表的存储结构和十字链表类似,也是由顶点表和边表组成,每一条边用一个结点表示,其顶点表结点结构和边表结点结构如图顶点值域 指针域vertex fiistc-dgc(i)邻接器重表顶点表结点结狗标记域顶点位置指针域顶点位置指针域 边上信息iiKirkivexiltiikjvexjlinkEllfo(b)邻接多重表边表结点结相其中,顶点表由两个域组成,vertex域存储和该顶点相关的信息firstedge域指示第一条依附于该顶点的边;边表结点由六个域组成,mark为标记域,可用以标记该条边是否被搜索过;ivex和jvex为该边依附的两个顶点在图中的位置;ilink指向下一条依附于顶点ivex的边;jlink指向下一条依附于顶点jvex的边,info为指向和边相关的各种信息的指针域。一个不带权图中若两点不相邻,邻接矩阵相应位置为0,对带权图(网),相应位置为8。一个图的邻接矩阵表示是唯一的,但其邻接表表示不唯一。在邻接表中,对图中每个顶点建立一个单链表(并按建立的次序编号),第i个单链表中的结点表示依附于顶点vi的边(对于有向图是以顶点vi为尾的弧)。每个结点由两个域组成:邻接点域(adjvex),用以指示与0邻接的点在图中的位置,链域(nextarc)用以指向依附于顶点vi的下一条边所对应的结点。如果用邻接表存放网(带权图)的信息,则还需要在结点中增加一个存放权值的域(info)。每个顶点的单链表中结点的个数即为该顶点的出度(与该顶点连接的边的总数)。无论是存储图或网,都需要在每个单链表前设一表头结点,这些表头结点的第一个域data用于存放结点vi的编号i,第二个域firstarc用于指向链表中第一个结点。在上面两个图结构中,一个是有向图,即每条边都有方向,另一个是无向图,即每条边都没有方向。在有向图中,通常将边称作弧,含箭头的一端称为弧头,另一端称为弧尾,记作<vi,vj>,它表示从顶点vi到顶点vj有一条边。若有向图中有n个顶点,则最多有n(n-1)条弧,我们又将具有n(n-1)条弧的有向图称作有向完全图。以顶点v为弧尾的弧的数目称作顶点▽的出度,以顶点v为弧头的弧的数目称作顶点▽的入度。在无向图中,边记作(vi,vj),它蕴涵着存在<vi,vj汴D<vj,vi>两条弧。若无向图中有n个顶点,则最多有n(n-1)/2条弧,我们又将具有n(n-1)/2条弧的无向图称作无向完全图。与顶点v相关的边的条数称作顶点v的度。路径长度是指路径上边或弧的数目。

若第一个顶点和最后一个顶点相同,则这条路径是一条回路。若路径中顶点没有重复出现,则称这条路径为简单路径。在无向图中,如果从顶点vi到顶点vj有路径,则称vi和vj连通。如果图中任意两个顶点之间都连通,则称该图为连通图,否则,将其中的极大连通子图称为连通分量。在有向图中,如果对于每一对顶点vi和vj,从vi到vj和从vj到vi都有路径,则称该图为强连通图;否则,将其中的极大连通子图称为强连通分量。的遍历的遍历图的遍历方法有深度优先搜索法和广度(宽度)优先搜索法深度优先搜索法是树的先根遍历的推广,它的基本思想是:从图G的某个顶点v0出发,访问v0,然后选择一个与v0相邻且没被访问过的顶点vi访问,再从vi出发选择一个与vi相邻且未被访问的顶点vj进行访问,依次继续。如果当前被访问过的顶点的所有邻接顶点都已被访问,则退回到已被访问的顶点序列中最后一个拥有未被访问的相邻顶点的顶点w,从w出发按同样的方法向前遍历,直到图中所有顶点都被访问。索是树的按层次遍历的推广,它的基本思想是:首先访问初始点vi,并将其标记为已访问过,接着访问vi的所有未被访问过的邻接点vi1,vi2,...,vit,并均标记已访问过,然后再按照vi1,vi2,...,vit的次序,访问每一个顶点的所有未被访问过的邻接点,并均标记为已访问过,依次类推,直到图中所有和初始点vi有路径相通的顶点都被访问过为止。图的连通性问题无向图的连通分量和生成树有向图的强连通分量最小生成树边赋以权值的图称为网或带权图,带权图的生成树也是带权的,生成树T各边的权值总和称为该树的权。最小生成树(MST):权值最小的生成树。生成树和最小生成树的应用:要连通n个城市需要n-1条边线路。可以把边上的权值解释为线路的造价。则最小生成树表示使其造价最小的生成树。构造网的最小生成树必须解决下面两个问题:1、尽可能选取权值小的边,但不能构成回路;2、选取n-1条恰当的边以连通n个顶点;MST性质:假设G=(V,E)是一个连通网,U是顶点V的一个非空子集。若(u,v)是一条具有最小权值的边,其中u£U,veV-U,则必存在一棵包含边(u,v)的最小生成树。l.prim算法基本思想:假设G=(V,E)是连通的,TE是G上最小生成树中边的集合。算法从U={uO}(uO£V)、TE={}开始。重复执行下列操作:在所有u£U,v£V-U的边(u,v)£E中找一条权值最小的边口0^0)并入集合TE中,同时vO并入U,直到V=U为止。此时,TE中必有n-1条边,T=(V,TE)为G的最小生成树。Prim算法的核心:始终保持TE中的边集构成一棵生成树。注意:prim算法适合稠密图,其时间复杂度为O(n八2),其时间复杂度与边得目有关,适合稀疏图。数目无关,而匕心卜分算法的时间复杂度为Keloge跟边的目有关,适合稀疏图。看了上面一大段文字是不是感觉有点晕啊,为了更好理解我在这里举一个例子,示例如下:

大家可能已经看出来了,kruskal算法寻找安全边的方式,就是在所有的边中找最小的表,只要两个节点是两个不相交集合,就加入到最小生成树中,直到所有的节点都连接起来。有向无环图关键路径最短路径迪杰斯特拉算法Dijkstra(迪杰斯特拉)算法是典型的最短路径路由算法,用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展,直到扩展到终点为止。Dijkstra算法能得出最短路径的最优解,但由于它遍历计算的节点很多,所以效率低。Dijkstra算法是很有代表性的最短路算法,在很多专业课程中都作为基本内容有详细的介绍,如数据结构,图论,运筹学等等。其基本思想是,设置顶点集合S并不断地作贪心选择来扩充这个集合。一个顶点属于集合S当且仅当从源到该顶点的最短路径长度已知。初始时,S中仅含有源。设u是G的某一个顶点,把从源到u且中间只经过S中顶点的路称为从源到u的特殊路径,并用数组dist记录当前每个顶点所对应的最短特殊路径长度。Dijkstra算法每次从V-S中取出具有最短特殊路长度的顶

点u,将u添加到S中,同时对数组dist作必要的修改。一旦S包含了所有V中顶点,dist就记录了从源到所有其它顶点之间的最短路径长度。例如,对下图中的有向图,应用Dijkstra算法计算从源顶点1到其它顶点间最短路径的过程列在下表中。w\i3/0^uTiati?5r.coiTiDijk前谓法的迭代过程;11151[2]dist⑶ai对口]1♦ 「T勒加U)10m7lnt曲1001也2J1060汕10&50效工2那J3J-JO50如604U2)\5]rw.wuTanQi.co先给出一个无向图用Dijkstra算法找出以A为起点的单源最短路径步骤如下宝集合中M霰合中1选此时上时最短.轻人一>萨口以A为中间点』从力开雌V-俎c.口、氏”aTd=gA—>C=3at其他tr中的顶点=8发现*->C=3极值为最短2选入C,此时£=女,C>止时最短踹钱支—公03->C=3以匕为中间点」从ATC4这条用短痘徒开始找3二<kD、E.F>k->C->F=5(比上面第一步的A—要短)此时到£㈱值为ATCTK=Sa—>C—>T=6A->C—E=TA->CT其悒U中的顶点hC3鬟现A->C->E-5权值为整短3选入E,止丽际&口B;此时最短路径A—>A-0>A—>03,Af-^8=5以B为中间点,从电->C—E=5逵森■最短路转开始找gaE、F>A->C->J—>D-10(比上面第二步的A—>C—>匹6要长)曲时到D树直更改为ATCT肝6ATCTBT其悒U中的项点=W发现4TCTD』权值为最短4选2,此时£="匚、民D>止时杲短躇役A->MQ…TC=箝A->C—B=5*A—>C—>D=6以B为中间点,从&TC—D逡条最短跳径开始找g&F>RTCTUTE邙(1;匕上面第二步的AfCfE=T要长]此时到E教值更改为C—E=TATCf—F=9置现ATCTE=7权值为最短S选人E,jktMS="C、屎,E>止时最短踣役A7*=0/A7C,B=5,4—>CTD=EA—CTE=7以E力中间点,从氏TCTE=7运重量如路密开蛤找U=<?>A->U->E—>F=1Ef比上面第四步的*—CTDfF=9要长川时到F极值更改为ATCTIDTF=9炭魂A-CfTF4权值为最短6孱人F,此时"5C、E、6E、F>止时最短跪接A->4=om,A—>C^B=5,A—>C—>D=6ATCTE:T,ATCTIjTF=9u集含已交,看我完毕*弗洛伊德算法1.定义概览Floyd-Warshall算法(Floyd-Warshallalgorithm)是解决任意两点间的最短路径的一种算法,可以正确处理有向图或负权的最短路径问题,同时也被用于计算有向图的传递闭包。Floyd-Warshall算法的时间复杂度为O(N»,空间复杂度为O(N*2.算法描述1)算法思想原理:Floyd算法是一个经典的动态规划算法。用通俗的语言来描述的话,首先我们的目标是寻找从点i到点j的最短路径。从动态规划的角度看问题,我们需要为这个目标重新做一个诠释(这个诠释正是动态规划最富创造力的精华所在)从任意节点i到任意节点j的最短路径不外乎2种可能,1是直接从i到j,2是从i经过若干个节点k到j。所以,我们假设Dis(i,j)为节点u到节点v的最短路径的距离,对于每一个节点k,我们检查Dis(i,k)+Dis(k,j)<Dis(i,j)是否成立,如果成立,证明从i到k再到j的路径比i直接到j的路径短,我们便设置Dis(i,j)=Dis(i,k)+Dis(k,j),这样一来,当我们遍历完所有节点k,Dis(i,j)中记录的便是i到j的最短路径的距离。2).算法描述:a.从任意一条单边路径开始。所有两点之间的距离是边的权,如果两点之间没有边相连,则权为无穷大。b.对于每一对顶点u和v,看看是否存在一个顶点w使得从u到w再到V比己知的路径更短。如果是更新它。因为迪杰特斯拉算法求的是一个顶点到所有顶点的最短路径,但弗洛伊德算法是求所有顶点到所有顶点的最短路径。弗洛伊德算法非常简洁优雅。为了能讲明白弗洛伊德算法的精妙所在,我们先来看最简单的案例:弗洛伊德算法D1[0][2]=min{D0[0][2],D0[0][1]+D[1][2]}

弗洛第德茸法原理弗洛伊德算法查找(包括各种查找方法的性能分析平均查找长度)顺序表的查找顺序表的存储typedefstruct{ElemType*elem;〃定义了顺序表中元素类型的数组指针指向顺序表存储空间的基址intlength; //顺序表的长度(也即元素个数)intlistsize; 〃当前分配给顺序表的存储容量}SqList;顺序查找顺序表可以看做第一部分的单链表和顺序表,这样的话查找问题就可以解决了。主要是:平均查找长度的计算有序表的查找(理解有序表和顺序表的不同)有序表就是因为存储的数据是有续的,所以可以进行折半查找。顺序表可以是单链表存储和顺序表存储。而有序表的存储必须是顺序表存储。这样才能找到中点。折半查找索引顺序表的查找二叉排序树定义二叉排序树(BinarySortTree)又称二叉查找树(BinarySearchTree),亦称二叉搜索树。它或者是一棵空树;或者是具有下列性质的二叉树:(1)若左子树不空,则左子树上所有结点的值均小于它的根结点的值;(2)若右子树不空,则右子树上所有结点的值均大于它的根结点的值;(3)左、右子树也分别为二叉排序树;查找步骤:若根结点的关键字值等于查找的关键字,成功。否则,若小于根结点的关键字值,递归查左子树。若大于根结点的关键字值,递归查右子树。若子树为空,查找不成功。*插入二叉排序树是一种动态树表。其特点是:树的结构通常不是一次生成的,而是在查找过程中,当树中不存在关键字等于给定值的节点时再进行插入。新插入的结点一定是一个新添加的叶子节点,并且是查找不成功时查找路径上访问的最后一个结点的左孩子或右孩子结点。首先执行查找算法,找出被插结点的父亲结点。判断被插结点是其父亲结点的左、右儿子。将被插结点作为叶子结点插入。若二叉树为空。则首先单独生成根结点。删除在二叉排序树删去一个结点,分三种情况讨论:.若*p结点为叶子结点,即PL(左子树)和PR(右子树)均为空树。由于删去叶子结点不破坏整棵树的结构,则只需修改其双亲结点的指针即可。.若*p结点只有左子树PL或右子树PR,此时只要令PL或PR直接成为其双亲结点*f的左子树(当*p是左子树)或右子树(当*p是右子树)即可,作此修改也不破坏二叉排序树的特性。.若*p结点的左子树和右子树均不空。在删去*p之后,为保持其它元素之间的相对位置不变,可按中序遍历保持有序进行调整,可以有两种做法:其一是令*p的左子树为*f的左/右(依*p是*f的左子树还是右子树而定)子树,*s为*p左子树的最右下的结点,而*p的右子树为*s的右子树;其二是令*p的直接前驱(或直接后继)替代*p,然后再从二叉排序树中删去它的直接前驱(或直接后继)-即让*f的左子树(如果有的话)成为*p左子树的最左下结点(如果有的话),再让*f成为*p的左右结点的父结点。性能分析每个结点的C(i)为该结点的层次数。最坏情况下,当先后插入的关键字有序时,构成的二叉排序树蜕变为单支树,树的深度为,其平均查找长度为(n+1)/2(和顺序查找相同),最好的情况是二叉排序树的形态和折半查找的判定树相同,其平均查找长度和10g2(n)成正比平衡二叉树

定义平衡二叉树(BalancedBinaryTree)又被称为AVL树(有别于AVL算法),且具有以下性质:它是一棵空树或它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一棵平衡二叉树。在AVL中任何节点的两个儿子子树的高度最大差别为一,所以它也被称为高度平衡树。查找、插入和删除在平均和最坏情况下都是O(1ogn)。增加和删除可能需要通过一次或多次树旋转来重新平衡这个树。查找和二叉排序树的查找是一样的。插入若向平衡二叉树中插入一个新结点后破坏了平衡二叉树的平衡性。首先要找出插入新结点后失去平衡的最小子树根结点的指针。然后再调整这个子树中有关结点之间的链接关系,使之成为新的平衡子树。当失去平衡的最小子树被调整为平衡子树后,原有其他所有不平衡子树无需调整,整个二叉排序树就又成为一棵平衡二叉树。失去平衡的最小子树是指以离插入结点最近,且平衡因子绝对值大于1的结点作为根的子树。假设用A表示失去平衡的最小子树的根结点,则调整该子树的操作可归纳为下列四种情况。(1)LL型平衡旋转法由于在A的左孩子B的左子树上插入结点F,使A的平衡因子由1增至2而失去平衡。故需进行一次顺时针旋转操作。即将A的左孩子B向右上旋转代替A作为根结点,A向右下旋转成为B的右子树的根结点。而原来B的右子树则变成A的左子树。(2)RR型平衡旋转法由于在A的右孩子C的右子树上插入结点F,使A的平衡因子由-1减至-2而失去平衡。故需进行一次逆时针旋转操作。即将A的右孩子C向左上旋转代替A作为根结点,A向左下旋转成为C的左子树的根结点。而原来C的左子树则变成A的右子树。

插入前调整后插入后(3)LR插入前调整后插入后(3)LR型平衡旋转法由于在A的左孩子B的右子数上插入结点F,使A的平衡因子由1增至2而失去平衡。故需进行两次旋转操作(先逆时针,后顺时针)。即先将A结点的左孩子B的右子树的根结点D向左上旋转提升到B结点的位置,然后再把该D结点向右上旋转提升到A结点的位置。即先使之成为LL型,再按LL型处理如图中所示,即先将圆圈部分先调整为平衡树,然后将其以根结点接到A的左子树上,此时成为LL型,再按LL型处理成平衡型。(4)RL型平衡旋转法由于在A的右孩子C的左子树上插入结点F,使A的平衡因子由-1减至-2而失去平衡。故需进行两次旋转操作(先顺时针,后逆时针),即先将A结点的右孩子C的左子树的根结点D向右上旋转提升到C结点的位置,然后再把该D结点向左上旋转提升到D结点向左上旋转提升到A结点的位置。即先使之成为RR型,再按RR型处理。插入的插入后调整后如图中所示,即先将圆圈部分先调整为平衡树,然后将其以根结点接到A的左子树上,此时成为RR型,再按RR型处理成平衡型。平衡化靠的是旋转。参与旋转的是3个节点(其中一个可能是外部节点NULL),旋转就是把这3个节点转个位置。注意的是,左旋的时候p->right一定不为空,右旋的时候p->left一定不为空,这是显而易见的。如果从空树开始建立,并时刻保持平衡,那么不平衡只会发生在插入删除操作上,而不平衡的标志就是出现bf==2或者bf==-2的节点。删除虽然平衡二叉树的节点删除操作的代码比较复杂,代码量也比较大,但是其删除过程只有以下3种情况:[注:只要牢牢把握住以下3点,理解平衡二叉树的删除操作不是太难]①被删的节点是叶子节点处理思路:将该节点直接从树中删除,并利用递归的特点和高度的变化,反向推算其父节点和祖先节点是否失衡。如果失衡,则判断是那种类型的失衡(LL、LR、RR、RL),再对失衡节点进行旋转处理,直到根节点或高度不再变化。②被删的节点只有左子树或只有右子树处理思路:将左子树(右子树)替代原有节点的位置,并利用递归的特点和高度的变化,反向推算父节点和祖先节点是否失衡。如果失衡,则判断是那种类型的失衡(LL、LR、RR、RL),再对失衡节点进行旋转处理,直到根节点或高度不再发生变化。③被删的节点既有左子树又有右子树处理思路:找到被删节点的左子树的最右端的节点rnode,将rnode的值赋给node,再把rnode的左孩子替换rnode的位置,在把rnode释放掉,并利用递归特点,反向推断rnode的父节点和祖父节点是否失衡。如果失衡,则判断是哪种类型的失衡(LL、LR、RR、RL),再对失衡的节点进行旋转处理,直到根节点或高度不再发生变化。LOG现象1LOG*如果q新的平衡因子bf(q)=O,意味着删除前bf(q)=1或者bf(q)=・3只有单子树。此时高度减1,需改变父节点和其他某些祖先节点的平衡因子。如果q新的平衡因子bf(q)=l或-L意味着删除前bf(q)=0,左右子树高度一样。此时高度不变,需改变父节点和其他某些祖先节删除15LOG删除15。如果删除15。如果q新的平衡因子bf(q)=-2或2,意味着删除前:bf(q)-1或L左右子树高度不同小此时树在q节点是不平衡的,需要平衡化处理现象3B-树和B+树定义和分析,算法要求程度不高。哈希表定义构造方法处理冲突的方法查找直接插入排序r插入排序后出<尔排序简单选择排序使用内存-归并排序-基数排序简单选择排序使用内存-归并排序-基数排序交拔排序A-堆排序-冒泡排序

一快速排序内存和外村结合使用外部排序排序插入排序直接插入排序1,直接插入排序的基本思想[^^海(Insertion5。|1)的基本思想是:每次将一个待排序的记录,按其关键字大4瞩入到前面已经排卷序的子序列中的适当位置,直到全部记录插入完成为止。设数组为a[0…n-1]。1.初始时,2[0]自成1个有序区,无序区为a[1..n-1]。令i=12.将分川并入当前的有序区2[0・/-1]中形成2[0・・用的有序区间。3"+并重复第二步3"+并重复第二步到》==门-1。排序完成。折半插入排序算法的基本过程:1)计算0〜i-1的中间点,用i索引处的元素与中间值进行比较,如果i索引处的元素大,说明要插入的这个元素应该在中间值和刚加入i索引之间,反之,就是在刚开始的位置到中间值的位置,这样很简单的完成了折半;2)在相应的半个范围里面找插入的位置时,不断的用(1)步骤缩小范围,不停的折半,范围依次缩小为1/21/41/8.……快速的确定出第i个元素要插在什么地方;3)确定位置之后,将整个序列后移,并将元素插入到相应位置。2一路插入排序表插入排序希尔排序该方法的基本思想是:先将整个待排元素序列分割成若干个子序列(由相隔某个〃增量〃的元素组成的)分别进行直接插入排序,然后依次缩减增量再进行排序,待整个序列中的元素基本有序(增量足够小)时,再对全体元素进行一次直接插入排序。因为直接插入排序在元素基本有序的情况下(接近最好情况),效率是很高的,因此希尔排序在时间效率上比前两种方法有较大提高。

以n=1。的一个数组49.38,65,97,26,13.27,49,55,4为例第一次9即=10/2=5I4938659726132749554TOC\o"1-5"\h\z1A 1B2A 2B3A 3B4A 4B5A 5B1A,1B,2A,2B等为分组标记,数字相同的表示在同一组,大写字母表示是该组第几个元素,每次对同一组的数据进行直接插入排序。即分成了五组9,13)(38,27)(65,49)(97,55)(26,4)这样每组排序后就变成了13,49)(27,38)(49,65)(55,97)(4,26),下同。第二次= 第二次= =2排序后1327495541A1B1C2A2B第三次gap=2/21B1C1D1E49336597261D1E2C2D2E49495597651F1G1IH11 11J第四次gap=1/2=0排序完成得到数组;4132627384949556597快速排序冒泡排序冒泡排序算法的运作如下:(从后往前)比较相邻的元素。如果第一个比第二个大,就交换他们两个。对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对。在这一点,最后的元素应该会是最大的数。针对所有的元素重复以上的步骤,除了最后一个。持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较。快速排序是对冒泡排序的一种改进快速排序由于排序效率在同为O(N*logN)的几种排序方法中效率较高,因此经常被采用,再加上快速排序思想----分治法也确实实用,因此很多软件公司的笔试面试,包括像腾讯,微软等知名IT公司都喜欢考这个,还有大大小的程序方面的考试如软考,考研中也常常出现快速排序的身影。总的说来,要直接默写出快速排序还是有一定难度的,因为本人就自己的理解对快速排序作了下白话解释,希望对大家理解有帮助,达到快速排序,快速搞定。快速排序是C.RAHoare于1962年提出的一种划分交换排序。它采用了一种分治的策略,通常称其为分治法(Divide-and-ConquerMethod)。该方法的基本思想是:.先从数列中取出一个数作为基准数。.分区过程,将比这个数大的数全放到它的右边,小于或等于它的数全放到它的左边。.再对左右区间重复第二步,直到各区间只有一个数。以一个数组作为示例,取区间第一个数为基准数.初始时,i=0;j=9;X=a[i]=72初始时,i=0;j=9;X=a[i]=72由于已经将a[0]中的数保存到X中,可以理解成在数组3[0]上挖了个坑,可以将其它数据填充到这来。从j开始向前找一个比X小或等于X的数。当j=8,符合条件,将a[8]挖出再填到上一个坑a[0]中。a[0]=a[8];i++;这样一个坑a[0]就被搞定了,但又形成了一个新坑a[8],这怎么办了?简单,再找数字来填a[8]这个坑。这次从i开始向后找一个大于X的数,当i=3,符合条件,将a[3]挖出再填到上一个坑中a[8]=a[3];j--;数组变为再重复上面的步骤,先从后向前找,再从前向后找。从j开始向前找,当j=5,符合条件,将a[5]挖出填到上一个坑中,a[3]=a[5];i++;从i开始向后找,当i=5时,由于i二可退出。此时,i=j=5,而a[5]刚好又是上次挖的坑,因此将乂填入3[5]。数组变为可以看出a[5]前面的数字都小于它,a[5]后面的数字都大于它。因此再对a[0…4]和a[6…9]这二个子区间重复上述步骤就可以了。对挖坑填数进行总结.i=L;j=R;将基准数挖出形成第一个坑a[i]。.j--由后向前找比它小的数,找到后挖出此数填前一个坑a[i]中。3.i++由前向后找比它大的数,找到后也挖出此数填到前一个坑a[j]中。4.再重复执行2,3二步,直到i二刁,将基准数填入3口]中。选择排序简单选择排序设所排序序列的记录个数为n。i取1,2,…,n-1,从所有n-i+1个记录(Ri,Ri+1,…,Rn)中找出排序码最小的记录,与第1个记录交换。执行n-1趟后就完成了记录序列的排序。最坏情况下,即待排序记录初始状态是按逆序排列的,则需要移动记录的次数最多为3(n-1)。简单选择排序过程中需要进行的比较次数与初始状态下待排序的记录序列的排列情况无关。当i=1时,需进行n-1次比较;当i=2时,需进行n-2次比较;依次类推,共需要进行的比较次数是(n-1)+(n-2)+…+2+1=n(n-1)/2,即进行比较操作的时间复杂度为0(22),进行移动操作的时间复杂度为0(n)。简单选择排序是不稳定排序。树形选择排序堆排序.堆堆实际上是一棵完全二叉树,其任何一非叶节点满足性质:Key[i]<=key[2i+1]&&Key[i]<=key[2i+2]或者Key[i]>=Key[2i+1]&&key>=key[2i+2]即任何一非叶节点的关键字不大于或者不小于其左右孩子节点的关键字。堆分为大顶堆和小顶堆,满足Key[i]>=Key[2i+1]&&key>=key[2i+2]称为大顶堆,满足Key[i]<=key[2i+1]&&Key[i]<=key[2i+2]称为小顶堆。由上述性质可知大顶堆的堆顶的关键字肯定是所有关键字中最大的,小顶堆的堆顶的关键字是所有关键字中最小的。.堆排序的思想利用大顶堆(小顶堆)堆顶记录的是最大关键字(最小关键字)这一特性,使得每次从无序中选择最大记录(最小记录)变得简单。其基本思想为(大顶堆):1)将初始待排序关键字序列(R1,R2....Rn)构建成大顶堆,此堆为初始的无序区;2)将堆顶元素R[1]与最后一个元素R[n]交换,此时得到新的无序区(R1,R2,……Rn-1)和新的有序区(Rn),且满足R[1,2...n-1]<=R[n];3)由于交换后新的堆顶R[1]可能违反堆的性质,因此需要对当前无序区(R1,R2,……Rn-1)调整为新堆,然后再次将R[1]与无序区最后一个元素交换,得到新的无序区(R1,R2....Rn-2)和新的有序区(Rn-1,Rn)。

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论