浙江理工大学数据结构复习整理

复杂性分析对各种操作的时间复杂性的分析。主要是链表，树，排序等简单一些的分析。分析的时候，从简单的入手，学会方法。后续的各种豆可能让你分析时间复杂度。线性链表（顺序表和单链表）链表 循环链双向链线性结构 队列（循环队列）栈（在哪个位置增加（在哪个位置删除。栈：查找，插入（位置固定），删除（位置固定）队列：查找，插入（位置固定），删除（位置固定）顺序表（可以视为一个数组）单链表：（删除）（插入）倒置：（查找）循环链表双向链表栈：（插入删除查找）队列（插入删除查找）循环队列的实现，并不是像上面的图那样，实现了一个循环的样子。二叉树基本概念二叉树是每个节点最多有两个子树的有序树。二叉树常被用于实现二叉查找树和二叉堆。值得注意的是，二叉树不是树的特殊情形。二叉树是每个结点最多有两个子树的有序树。通常根的子树被称作“左子树”（leftsubtree）subtree）二叉查找树和二叉堆或是二叉排序(2的结点2；树的结点无左、右之分，而二叉树的结点有左、右之分。二叉树是递归定义的，其结点有左右子树之分，逻辑上二叉树有五种基本形态：空二叉树——如图(a)；只有一个根结点的二叉树——如图(b)；(3)只有左子树——如图(c)；只有右子树——如图(d)；完全二叉树——如图(e)注意：尽管二叉树与树有许多相似之处，但二叉树不是树的特殊情形性质在非空二叉树中，第i层的结点总数不超过,i>=1；h2^h-1个结点(h>=1)h个结点；对于任意一棵二叉树，如果其叶结点数为N02N2N0=N2+1；n个结点的完全二叉树的深度为N个结点的完全二叉树各结点如果用顺序方式存储，则结点之间有如下关系：II>1I/2；即左子树的根结点2*I+1<=N2*I+12*I+1>N，则无右儿子。Nh(N)h(N)为卡特兰数Nh(n)=C(2*n，n)/(n+1)。（7）设有i个枝点，I为所有枝点的道路长度总和，J为叶的道路长度总和J=I+2i存储结构顺序存储表示二叉树可以用数组或线性表来存储，而且如果这是满二叉树，这种方法不会浪费空间。i2i+12i+2找到，并且它的父节点（如果有）floor((i-1)/2)找到（0）。这种方法更有利于紧凑存储和更好的访问的局部性存储空hnh2h个结点，空间的浪费太大，这是顺序存储结构的一大缺点。/*二叉树的顺序存储表示*/#defineMAX_TREE_SIZE100/*二叉树的最大节点数*/typedefTElemTypeSqBiTree[MAX_TREE_SIZE];/*0号单元存储根节点*/typedefstruct{intlevel,order;/*节点的层，本层序号(按满二叉树计算)*/}position;二叉链表存储表示/*二叉樹的二叉鏈表存儲表示*/typedefstructBiTNode{TElemTypedata;structBiTNode*lchild,*rchild;/*左右孩子指針*/}BiTNode,*BiTree;遍历算法二叉树的遍历三种方式，如下：前序遍历（DLR），子树。简记根-左-右。中序遍历（LDR），子树。简记左-根-右。后序遍历（LRD），结点。简记左-右-根。例1：如上图所示的二叉树，若按前序遍历，则其输出序列为 。若按序遍历，则其输出序列为 。若按后序遍历，则其输出序列为 。A-B-D。ACE，EF，EG，G的左子HC-E-F-G-H,最ABDCEFGH,BABDA。HHGCC，无右子树，结FEHGC,BDAFEHGC后序：BDB。再看右子树，最下面的左子树FHHGGE，ECCB找它们其有的根FCA深度优先遍历在深度优先中，我们希望从根结点访问最远的结点。和图的深度优先搜索不同的是，不需记住访问过的每一个结点，因为树中不会有环。广度优先遍历和深度优先遍历不同，广度优先遍历会先访问离根节点最近的节点。完全二叉树，满二叉树满二叉树：一棵深度为k，且有个节点称之为满二叉树nk的满二叉树中，序号为1至n的节点对应时，称之为完全二叉树树

基本概念树（tree）是包含n（n>0）个结点的有穷集，其中：每个元素称为结点（node）；有一个特定的结点被称为根结点或树根（root）。个互不相交的集合Ti（1<=i<=m）本身也是一棵树，被称作原树的子树（subtree）。树也可以这样定义：树是由根结点和若干颗子树构成的。树是由一个集合以及在该集合上定我们可以形式地给出树的递归定义如下:单个结点是一棵树，树根就是该结点本身。T1,T2,..,Tkn1,n2,..,nknn1,n2,..,nk的父nn1,n2,..,nknT1,T2,..,Tkn的子树。空集合也是树，称为空树。空树中没有结点。术语节点的度：一个节点含有的子树的个数称为该节点的度；树的度：一棵树中，最大的节点的度称为树的度；叶节点或终端节点：度为零的节点；非终端节点或分支节点：度不为零的节点；父亲节点或父节点：若一个节点含有子节点，则这个节点称为其子节点的父节点；孩子节点或子节点：一个节点含有的子树的根节点称为该节点的子节点；兄弟节点：具有相同父节点的节点互称为兄弟节点；节点的层次12层，以此类推；树的高度或深度：树中节点的最大层次；堂兄弟节点：父节点在同一层的节点互为堂兄弟；节点的祖先：从根到该节点所经分支上的所有节点；子孙：以某节点为根的子树中任一节点都称为该节点的子孙。森林m（m>=0）棵互不相交的树的集合称为森林；存储父节点表示法/*树节点的定义*/#defineMAX_TREE_SIZE100typedefstruct{TElemTypedata;intparent;/*父节点位置域*/}PTNode;typedefPTNodenodes[MAX_TREE_SIZE];intn;/*节点数*/}PTree;孩子链表表示法/*树的孩子链表存储表示*/typedefstructCTNode{//孩子节点intchild;structCTNode*next;}*ChildPtr;typedefstruct{ElemTypedata；//节点的数据元素ChildPtrfirstchild；//孩子链表头指针}CTBox;typedefstruct{CTBoxnodes[MAX_TREE_SIZE]；intn,r；//节点数和根节点的位置}CTree;森林将树转换为二叉树①在所有兄弟结点之间加一连线；②对每个结点，除了保留与其长子的连线外，去掉该结点与其它孩子的连线。注意：由于树根没有兄弟，故树转化为二叉树后，二叉树的根结点的右子树必为空。2）将一个森林转换为二叉树具体方法是：①将森林中的每棵树变为二叉树②因为转换所得的二叉树的根结点的右子树均为空，故可将各二叉树的根结点视为兄弟从左至右连在一起，就形成了一棵二叉树。二叉树到树、森林的转换xyxy。图二元组的定义图G(V,E)V(VerticesSet)Eset)，EVV(G)E(G)。E的元素都是二元组，用(x,y)表示，其中x,y∈V。三元组的定义G(V,E,I)，V，E，EV称为关联函数，IEe(u,v)，eu,v，u,veu,vei,ju，i,j相邻。有/无向图个节点相关联的边有出边和入边之分。相反，边没有方向的图称为无向图。简单图一个图如果没有两条边，它们所关联的两个点都相同（中，没有两条边的起点终点都分别相同）；每条边所关联的是两个不同的顶点（Simplegraph）的“二元组的定义”，但形如的序对不能属于E。而无向图的边必须是对称的，即如果，那么。基本术语阶（Order）：图G中顶集V的大小称作图G的阶。（Sub-Graph）：G'=(V',E')V‘V，E’G'G=(V,E)的子图。每个图都是本身的子图。生成子图（SpanningSub-Graph）：V(G')=V(G)GG。导出子图（InducedSubgraph）：GVV1V1GV1GEE1E1GE1vd(v)。入度（In-degree）和出度（Out-degree）：对于有向图来说，一个顶点的度可数；出度则是相对的概念，指以该顶点为起点的边数。自环（Loop）：若一条边的两个顶点为同一顶点，则此边称作自环。路径（Path）：uvv0,e1,v1,e2,v2,...ek,vk，eivivi1，kP(u,v)uv行迹。P(u,v)uv条轨道。闭的行迹称作回路（Circuit），闭的轨称作圈（Cycle）。（另一种定义是：walkpath，pathtrack。Trailtrace。）桥（Bridge）：若去掉一条边，便会使得整个图不连通，该边称为桥。图的存储表示数组（邻接矩阵）存储表示（有向或无向）邻接表存储表示邻接表是图的一种链式存储结构。邻接表中，对图中每个顶点建立一个单链表，第i个单链表中的结点表示依附于顶点Vi的边（对有向图是以顶点Vi为尾的弧）。邻接表中的表结点和头结点结构：有向图的邻接表和逆邻接表（一）在有向图的邻接表中，第i个单链表链接的边都是顶点i发出的边。（二i（三）在有向图的逆邻接表中，第i个单链表链接的边都是进入顶点i的边。邻接表小结n个顶点，en个顶点结点，2ene个边结点。vii个链表中的结点数。iviivi的入度。O(n+e)。有向图的十字链表存储表示十字链表表示特点针对弧结点，增加入弧链表结构和出弧链表结构；3.结构实现比较复杂。4.无向图的邻接多重表存储表示邻接多重表(AdjacencyMultilist)主要用于存储无向图。因为，如果用邻接表表中，这给图的某些操作带来不便。例如，对已访问过的边做标记，或者要删操作的无向图的问题中采用邻接多重表作存储结构更为适宜。一个结点表示，其顶点表结点结构和边表结点结构如图firstedge指示第一条依附于该顶点的边；边表结点由六个域组成，mark为标记域，可用以标记该条边是否被搜索过；ivexjvex为该边依附的两个顶点在图中的位ilink指向下一条依附于顶点ivex;jlink指向下一条依附于顶点的边，info为指向和边相关的各种信息的指针域。对图中每个顶点建立一个单链表（并按建立的次序编号），i链表中的vi（vivividatavii，firstarc每条边都没有方向。在有向图中，通常将边称作弧，含箭头的一端称为弧头，另一端称为弧尾，记作<vi,vj>，它表示从顶点vi到顶点vj有一条边。nn(n-1)n(n-1)条弧的有vv出度v(vi,vj)，它蕴涵着存在<vi,vj>和<vj,vi>nn(n-1)/2条弧n(n-1)/2vv路径长度是指路径上边或弧的数目。若第一个顶点和最后一个顶点相同，则这条路径是一条回路。若路径中顶点没有重复出现，则称这条路径为简单路径。vivjvivj连通分量。vivivjvjvi则称该图为强连通图；否则，将其中的极大连通子图称为强连通分量。图的遍历图的遍历方法有深度优先搜索法和广度（宽度）优先搜索法。深度优先搜索法G的某个顶点v0v0vivivj进行访问，依次继续。如果当前被访问过的顶点的所有邻接顶点都已被访问，则退回到已被访问的顶点序列中w直到图中所有顶点都被访问。广度优先搜索vivi1,vi2,…,vit，vi1,vi2,…,vitvi图的连通性问题无向图的连通分量和生成树有向图的强连通分量最小生成树T边的权值总和称为该树的权。最小生成树（MST）：权值最小的生成树。nn－1上的权值解释为线路的造价。则最小生成树表示使其造价最小的生成树。构造网的最小生成树必须解决下面两个问题：1、尽可能选取权值小的边，但不能构成回路；2、选取n－1条恰当的边以连通n个顶点；MSTG＝(V,E)UVu∈U，v∈V－U，则必存在一棵包含边(u,v)的最小生成树。1.primGU＝{u0}（u0∈V）、TE＝{}开始。重复执行下列操作：u∈U，v∈V－U(u0,v0TEv0U，V＝U此时，TEn-1，T=(V，TE)GPrimTE注意：primO(n^2)，看了上面一大段文字是不是感觉有点晕啊，为了更好理解我在这里举一个例子，示例如下：--＿＠例：＝＝大家可能已经看出来了，kruskal算法寻找安全边的方式，就是在所有的边中找的节点都连接起来。关键路径最短路径迪杰斯特拉算法Dijkstra(终点为止。Dijkstra能得出最短路径的最优解，但由于它遍历计算的节点很多，所以效率低。Dijkstra算法是很有代表性的最短路算法，在很多专业课程中都作为基本内容有详细的介绍，如数据结构，图论，运筹学等等。SS当且仅当从源到该顶点的最短路径长度已知。初始时，SuGuSudist记录当前每个顶点所对应的最短特殊路径长度。DijkstraV-SuuSdistSV中顶点，dist就记录了从源到所有其它顶点之间的最短路径长度。Dijkstra算法1路径的过程列在下表中。先给出一个无向图用Dijkstra算法找出以A为起点的单源最短路径步骤如下弗洛伊德算法定义概览Floyd-Warshall算法（Floyd-Warshallalgorithm）是解决任意两点间的最短路径向图的传递闭包。Floyd-WarshallO(N3)，空间复杂度为O(N2)。算法描述1)算法思想原理：Floyd算法是一个经典的动态规划算法ij的最短路径。从动态规划的角度看问题，我们需要为这个目标重新做一个诠释（这个诠释正是动态规划最富创造力的精华所在）ij2iikjDis(i,j)uv的最短Dis(i,k)Dis(k,j)Dis(i,j)是否成立，ikjijDis(i,j)Dis(i,k)Dis(k,j)k，Dis(i,j)中记录的便是ij的最短路径的距离。算法描述：没有边相连，则权为无穷大。对于每一对顶点u和vw使得从u到w再到v比己知的路径更短。如果是更新它。因为迪杰特斯拉算法求的是一个顶点到所有顶点的最短路径，但弗洛伊德算法是求所有顶点到所有顶点的最短路径。弗洛伊德算法非常简洁优雅。为了能讲明白弗洛伊德算法的精妙所在，我们先来看最简单的案例：弗洛伊德算法D1[0][2]=min{D0[0][2],D0[0][1]+D[1][2]}弗洛伊德算法原理\\＼/Vl V6＼/vo/ 尸 \勹\V8兮V2一弗洛伊德算法一

7'-.:V5

9"--I/4//4/5四m m m m m m li.lmmmmmmmll!nII0 1 S O O O O O ＿1 0 3 7 5 OO0 中 OO＿5 3 0 o 1 7 OO0 0OO 7 OO 0 2 OO 3 OO OO＿loo 5 1 2 0 3 6 9 oo＿国 OO OO 7 oo 3O OO 5, OOOO00 00 3 6000 2OOOO OO OO 9 5 2 0 4OO OO0 中 OO 7 4 0

6 7 82 3 4 5 6 7 ：2 3 4 5 6 7 8：2 3 4 5 6 7 81 2 3 4 5 6 7 81 2 3 4 5 6 7 8。1 2 3 4 s 6 7 8。。1 2 3 4 5 6 7 8。1 2 3 4 5 6 7 8查找（包括各种查找方法的性能分析平均查找长度）顺序表的查找顺序表的存储typedefstruct{ElemType*elem; //序表存储空间的基址intlength; //顺序表的长度(也即元素个数intlistsize; //当前分配给顺序表的存储容量}SqList;顺序查找顺序表可以看做第一部分的单链表和顺序表，这样的话查找问题就可以解决了。主要是：平均查找长度的计算有序表的查找（理解有序表和顺序表的不同）有序表就是因为存储的数据是有续的，所以可以进行折半查找。顺序表可以是单链表存储和顺序表存储。而有序表的存储必须是顺序表存储。这样才能找到中点。折半查找索引顺序表的查找二叉排序树定义二叉排序树（BinarySortTree）又称二叉查找树（BinarySearchTree），称二叉搜索树。它或者是一棵空树；或者是具有下列性质的二叉树：（1）若根结别为二叉排序树；查找步骤：若根结点的关键字值等于查找的关键字，成功。否则，若小于根结点的关键字值，递归若大于根结点的关键字值，递归查右子树。若子树为空，查找不成功。插入当树中不存在关键字等于给定值的节点点一定是一个新添加的叶子节点路径个结点的左孩子或右孩子结点。首先执行查找算法，找出被插结点的父亲结点。判断被插结点是其父亲结点的左、右儿子。将被插结点作为叶子结点插入。若二叉树为空。则首先单独生成根结点。删除在二叉排序树删去一个结点，分三种情况讨论：若*pPL(PR(结点不破坏整棵树的结构，则只需修改其双亲结点的指针即可。若*pPLPLPR点*f（当*p当*p不破坏二叉排序树的特性。若*p*p相对位置不变，可按中序遍历保持有序进行调整，可以有两种做法：其一是令*p的左子树为*f的左/右(依*p是*f的左子树还是右子树而定)子树，*s为*p左子树的最右下的结点，而*p的右子树为*s的右子树；其二是令*p（或直接后继）替代*p，然后再从二叉排序树中删去它的直接前驱（或直接后继）－即让*f*p左下结点(如果有的话)，再让*f*p性能分析C(i)构成的二叉排序树蜕变为单支树，树的深度为，其平均查找长度为(n+1)/2(和顺序查找相同log2(n)成正比平衡二叉树定义平衡二叉树（BalancedBinaryTree）AVL（AVL），且AVLO（logn）。增加和删除可能需要通过一次或多次树旋转来重新平衡这个树。查找和二叉排序树的查找是一样的。插入若向平衡二叉树中插入一个新结点后破坏了平衡二叉树的平衡性。首先要关结点之间的链接关系，使之成为新的平衡子树。当失去平衡的最小子树被调一棵平衡二叉树。1A表示失去平衡的最小子树的根结点，则调整该子树的操作可归纳为下列四种情况。LL型平衡旋转法ABFA12一次顺时针旋转AB向右上旋转A作为根结点，A向右下旋转BB的右子树A的左子树。RR型平衡旋转法ACA的平衡因子由-1减至而失去平衡。故需进行一次逆时针旋转AC向左上旋转代A作为根结点，A向左下旋转CC的左子树A的右子树。LR型平衡旋转法由于在A的左孩子B的右子数上插入结点F，使A的平衡因子由1增至2而失去平衡。故需进行两次旋转操作（先逆时针，后顺时针）。即先将A结点的左孩子B的右子树的根结点D向左上旋转提升到B结点的位置，然后再把该D结点向右上旋转提升到A结点的位置。即先使之成为LL型，再按LL型处理。如图中所示，即先将圆圈部分先调整为平衡树，然后将其以根结点接到A的左子树上，此时成为LL型，再按LL型处理成平衡型。RL型平衡旋转法ACA的平衡因子由-1减至-2而失去平衡。故需进行两次旋转操作（先顺时针，后逆时针）A结点CD向右上旋转C结点向左上旋转ARRRR如图中所示，即先将圆圈部分先调整为平衡树，然后将其以根结点接到A的左子树上，此时成为RR型，再按RR型处理成平衡型。平衡化靠的是旋转。3个节点（其中一个可能是外部节点NULL），3p->left一定不为空，这是显而易见的。bf2bf2的节点。删除33①被删的节点是叶子节点算其父节点和祖先节点是否失衡。如果失衡，则判断是那种类型的失衡（LL、LR、RR、RL），再对失衡节点进行旋转处理，直到根节点或高度不再变化。②被删的节点只有左子树或只有右子树（右子树失衡（LL、LR、RR、RL），再对失衡节点进行旋转处理，直到根节点或高度不再发生变化。③被删的节点既有左子树又有右子树nodenode的值赋给rnodernodernode释放掉，并利用递归特点，rnode♦如果qb(q，删除前bf(q)=1bf(q)=-1此时1的平衡因子删除25删除25匾：：． 如新的平因bf(q)l—l,. 意味删除前bf(q)=O，左右子树高度一样此时，需点的平衡因子删15 -1B-树和B+树定义和分析，算法要求程度不高。哈希表定义构造方法处理冲突的方法查找排序直接插入排序1．直接插入排序的基本思想

插入排序直接插入排序(InsertionSort)的基本思想是：每次将一个待排序的记录，按其关键字大小插入到前面已经排好序的子序列中的适当位置，直到全部记录插入完成为止。设数组为a[0…n-1]。初始时，a[01a[1..n-1i=1a[ia[0…i-1a[0…i]的有序区间。ii==n-1折半插入排序算法的基本过程：计算 0 ~ i-1 的中间点用 i 索引处的元素与中间值进行比较如果 i 索引处的元素大，说明要插入的这个元素应该在中间值和刚加入i索引之间，反之，就是在刚开始的位置到中间值的位置，这样很简单的完成了折半；在相应的半个范围里面找插入的位置时不断的步骤缩小范围不停的折半，范围依次缩小为 1/2 1/4 1/8 快速的确定出第 i 个元素要插在什么地方；确定位置之后，将整个序列后移，并将元素插入到相应位置。2—路插入排序表插入排序希尔排序该方法的基本思想是：先将整个待排元素序列分割成若干个子序列（由相隔某个“增量”的元素组成的）分别进行直接插入排序，然后依次缩减增量再进行排（增量足够小接插入排序。因为直接插入排序在元素基本有序的情况下（接近最好情况），效率是很高的，因此希尔排序在时间效率上比前两种方法有较大提高。快速排序冒泡排序冒泡排序算法的运作如下：（从后往前）比较相邻的元素。如果第一个比第二个大，就交换他们两个。对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。针对所有的元素重复以上的步骤，除了最后一个。持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。快速排序是对冒泡排序的一种改进快速排序由于排序效率在同为O(N*logN)的几种排序方法中效率较高因此经被采用，再加上快速排序思想 分治法也确实实用，因此很多软件公司的笔IT面的考试如软考，考研中也常常出现快速排序的身影。C.R.A.Hoare1962治的策略，通常称其为分治法(Divide-and-ConquerMethod)。该方法的基本思想是：先从数列中取出一个数作为基准数。的左边。再对左右区间重复第二步，直到各区间只有一个数。初始时，i=0;j=9; X=a[i]=72a[0]Xa[0]jXXa[8]挖出再填到上一个坑a[0]中。a[0]=a[8i++;a[0]a[8]，这怎么办a[8]iXi=3，符合a[3]a[8]=a[3j--;再重复上面的步骤，先从后向前找，再从前向后找。从j开始向前找，当j=5，符合条件，将a[5]挖出填到上一个坑中，a[3]=a[5];i++;从i开始向后找，当i=5时，由于i==j退出。此时，i=j=5，而a[5]刚好又是上次挖的坑，因此将X填入a[5]。可以看出a[5]前面的数字都小于它，a[5]后面的数字都大于它。因此再对a[0…4]和a[6…9]这二个子区间重复上述步骤就可以了。对挖坑填数进行总结1．i=L;j=R;将基准数挖出形成第一个坑a[i]。2．j--由后向前找比它小的数，找到后挖出此数填前一个坑a[i]中。i++a[j]中。2，3i==ja[i]中。简单选择排序

选择排序设所排序序列的记录个数为n。i取1,2,…,n-1,从所有n-i+1个记录（Ri,Ri+1,…,Rn1n-1就完成了记录序列的排序。3（n-1）。简单选择排序过程中需要进行的比较次数与初始状态下待排序的记录i=1n-1i=2n-2(n-1)+(n-2)+…+2+1=n(n-1)/2，即进行比较操作的时间复杂度O(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]称为小顶堆。由上述性质可知大顶堆的堆顶的关键字肯定是所有关键字中最大的，小顶堆的堆顶的关键字是所有关键字中最小的。堆排序的思想利用大顶堆(小顶堆)堆顶记录的是最大关键字(最小关键字)这一特性，使得每次从无序中选择最大记录(最小记录)变得简单。其基本思想为(大顶堆)：将初始待排序关键字序列(R1,R2 Rn)构建