严蔚敏数据结构复习整理

1、1复杂性分析对各种操作的时间复杂性的分析。主要是链表，树，排序等简单一些的分析。 分析的时候，从简单的入手，学会方法。 后续的各种豆可能让你分析时间复杂度。线性链表（顺序表和单链表）链表q循环链表双向链表2线性结构q 队列（循环队列）栈链表主要操作：找某一个元素，插入一个（在哪个位置增加），删除一个（在哪个位置删除） 栈：查找，插入（位置固定），删除（位置固定）队列：查找，插入（位置固定），删除（位置固定）顺序表（可以视为一个数组）下标冠0A1B2C3D4E5F6G7H8 4 单链表:（删除）PO循环链表双向链表匸跖二和RT =L ;u “/弋hotid栈:队列(插入删除查找)循环队列的实现，

2、并不是像上面的图那样，实现了一个循环的样子。3二叉树基本概念二叉树是每个最多有两个子树的有序树。二叉树常被用于实现和。值得注意的是，二叉树不是树的特殊情形。二叉树是每个结点最多有两个子树的有序树。通常根的子树被称作“左子树” (leftsubtree)和“右子树” (right subtree)。二叉树常被用作和或是。二叉树的每个结点至多只 有二棵子树(不存在出度大于2的结点)，二叉树的子树有左右之分，次序不能颠倒。二叉树不是树的一种特殊情形，尽管其与树有许多相似之处，但树和二叉树有两个主要差别：1. 树中结点的最大度数没有限制，而二叉树结点的最大度数为2 ；2. 树的结点无左、右之分，而二叉

3、树的结点有左、右之分。0Z / jfLjfX0 0 67/ /O O 0 O二叉树是定义的，其结点有左右子树之分，逻辑上二叉树有五种基本形态:(1)空二叉树一一如图(a);只有一个根结点的二叉树如图(b)；只有左子树一一如图(c)；(4)只有右子树一一如图(d)；一一如图(e)注意：尽管二叉树与树有许多相似之处，但二叉树不是树的特殊情形(|)性质在非空二叉树中，第 i 层的结点总数不超过(2) 深度为h的二叉树最多有2Ah-1个结点(h=1)，最少有h个结点；(3) 对于任意一棵二叉树，如果其叶结点数为NO，而度数为2的结点总数为 N2，则N0=N2+1 ；(4)具有n个结点的的深度为(5)有

4、N个结点的各结点如果用顺序方式存储，则结点之间有如下关系：若I为结点编号则 如果11，则其父结点的编号为1/2 ；如果2*IN，则无左儿子；如果2*I+1N，则无右儿子。给定N个节点，能构成h(N)种不同的二叉树。h(N)为的第N项。h(n)=C(2*n , n)/(n+1)。(7)设有i个枝点，I为所有枝点的道路长度总和，J为叶的道路长度总和 J=I+2i存储结构顺序存储表示0123456二叉树可以用或线性表来存储，而且如果这是，这种方法不会浪费空间。用这种紧凑排 列，如果一个结点的索引为i,它的子结点能在索引2i+1和2i+2找到，并且它的父节点(如果有)能在索引floor(i-1)/2)

5、找到(假设根节点的索引为0)。这种方法更有利于紧凑存储和更好的，特别是在前序遍历中。然而，它需要连续的，这样在存储高度为 h的n个结点组成的一般普通树时将会浪费很多空间。一种最极坏的情况下如果深度为h的二叉树每个节点只有右孩子需要占用 2的h次幕减1,而实际却只有h个结点，空间的浪费太大，这是顺序 存储结构的一大缺点。/*二叉树的顺序存储表示*/#define MAX TREE SIZE 100 /* 二叉树的最大节点数 */typedef struct int level,order; /*positi on;节点的层，本层序号（按满二叉树计算）*/二叉链表存储表示/*二叉樹的二叉鏈表存儲表

6、示*/ typedef struct BiTNodeTEIemType data;左右孩子指針*/struct BiTNode *lchild,*rchild; /*BiTNode,*BiTree;遍历算法二叉树的遍历三种方式，如下：（1）前序遍历（DLR），首先访问根结点，然后遍历左子树，最后遍历右 子树。简记根-左-右。（2）中序遍历（LDR），首先遍历左子树，然后访问根结点，最后遍历右 子树。简记左-根-右。（3）后序遍历（LRD ），首先遍历左子树，然后遍历右子树，最后访问根 结点。简记左-右-根。例1:如上图所示的二叉树，若按前序遍历，则其输出序列为。若按中序遍历，则其输出序列为。若

7、按后序遍历，则其输出序列为。前序：根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。再看右子

8、树，最下面的左子树 是F,其根的右子树的左子树是 H，再到H的根G,再到G的根E, E的根C 无右子树了，直接到C,这时再和B找它们其有的根A，所以连起来是DBFHGECA深度优先遍历在深度优先中，我们希望从根结点访问最远的结点。和图的不同的是，不需 记住访问过的每一个结点，因为树中不会有环。广度优先遍历和深度优先遍历不同，广度优先遍历会先访问离根节点最近的节点GO藕XHe】左全二叉掲1. 满二叉树：一棵深度为 k,且有个节点称之为满二叉树2. 完全二叉树：深度为k,有n个节点的二叉树，当且仅当其每一个节点都与深度为k的满二叉树中，序号为 1至n的节点对应时，称之为完全二叉树4树基本概念树（t

9、ree）是包含n （n0）个结点的有穷集，其中：（1）每个元素称为结点（n ode）;（2）有一个特定的结点被称为根结点或树根（ root ）。（3） 除根结点之外的其余数据元素被分为m （m0）个互不相交的集合 T1, T2,Tm-1 ,其中每一个集合 Ti （1=i=0)棵互不相交的树的集合称为森林；存储父节点表示法/* 树节点的定义 */#define MAX_TREE_SIZE 100typedef struct TEIemType data;in t pare nt; /* 父节点位置域 */ PTNode;typedef struct PTNode no desMAX_TREE_S

10、IZE;int n; /* 节点数 */ PTree;孩子链表表示法/*树的孩子链表存储表示*/typedef struct CTNode /孩子节点int child;struct CTNode *n ext; *ChildPtr;typedef struct ElemType data ; / 节点的数据元素ChildPtr firstchild ; / 孩子链表头指针 CTBox;typedef struct CTBox no desMAX_TREE_SIZE；int n, r ； / 节点数和根节点的位置 CTree;5. 森林6. 森林、树与二叉树的转换将树转换为二叉树树中每个结点最

11、多只有一个最左边的孩子（长子）和一个右邻的兄弟。 按照这种关系很自然地就能将树转换成相应的二叉树： 在所有兄弟结点之间加一连线； 对每个结点，除了保留与其长子的连线外，去掉该结点与其它孩子的连线。(a)(b)(c)树转化虚-足鞫注意:由于树根没有兄弟，故树转化为二叉树后，二叉树的根结点的右子树必为空。2）将一个森林转换为二叉树具体方法是： 将森林中的每棵树变为二叉树 因为转换所得的二叉树的根结点的右子树均为空，故可将各二叉树的根结点视 为兄弟从左至右连在一起，就形成了一棵二叉树。二叉树到树、森林的转换把二叉树转换到树和森林自然的方式是：若结点x是双亲y的左孩子，则把x的右孩子,右孩子的右孩子，

12、都与 y用连线连起来，最后去掉所有双亲到右孩子的连线。二元组的定义图G是一个有序二元组(V,E)，其中V称为顶集(Vertices Set)疋称为边集(Edges set) , E与V不相交。它们亦可写成 V(G)和E(G)。E的元素都是二元组，用(x,y)表示，其中x,y V。三元组的定义图G是指一个三元组(V,E,I)，其中V称为顶集，E称为边集，E与V不相交；I 称为关联函数，I将E中的每一个元素映射到VxV。如果e被映射到(u,v)，那么称边e连接顶点u,v，而u,v贝U称作e的端点， u,v此时关于e相邻。同时，若两条边i,j有一个公共顶点u，则称i,j关于u 相邻。有/无向图如果给

13、图的每条边规定一个方向， 那么得到的图称为有向图。在有向图中，与 个节点相关联的边有出边和入边之分。相反，边没有方向的图称为无向图。简单图一个图如果1. 没有两条边，它们所关联的两个点都相同(在 有向图 中，没有两条边的起点终点都 分别相同)；2. 每条边所关联的是两个不同的顶点则称为简单图( Simple graph )。简单的有向图和无向图都可以使用以上的“二元组的定义” ，但形如 的 序 对 不能 属 于 E。 而无 向 图的 边 集必 须 是对称 的， 即 如果那么基本术语阶(Order):图G中顶集V的大小称作图G的阶。子图(Sub-Graph):当图G=(V,E) 其中V 包含于V

14、, E 包含于E,贝U G称 作图G=(V,E)的子图。每个图都是本身的子图。生成子图(Spanning Sub-Graph ):指满足条件 V(G) = V(G)的G的子图G 导出子图(Induced Subgraph ):以图G的顶点集V的非空子集V1为顶点集， 以两端点均在V1中的全体边为边集的G的子图，称为V1导出的导出子图；以图 G的边集E的非空子集E1为边集，以E1中边关联的顶点的全体为顶点集的G的子图，称为 E1 导出的导出子图。度(Degree): 个顶点的度是指与该顶点相关联的边的条数，顶点v的度记作d(v) 。入度（In-degree ）和出度（Out-degree ）:对

15、于有向图来说，一个顶点的度可 细分为入度和出度。一个顶点的入度是指与其关联的各边之中，以其为终点的边数；出度则是相对的概念，指以该顶点为起点的边数。自环（Loop）:若一条边的两个顶点为同一顶点，则此边称作自环。路径（Path）:从u到v的一条路径是指一个序列 v0,e1,v1,e2,v2,ek,vk ，其 中ei的顶点为vi及vi - 1, k称作路径的长度。如果它的起止顶点相同，该路 径是“闭”的，反之，则称为“开”的。一条路径称为一简单路径（simple path）， 如果路径中除起始与终止可以重合外，所有顶点两两不等。行迹（Trace）:如果路径P（u,v）中的边各不相同，则该路径称为

16、 u到v的一条 行迹。轨道（Track）:如果路径P（u,v）中的顶点各不相同，则该路径称为 u到v的一 条轨道。闭的行迹称作回路（Circuit ），闭的轨称作圈（Cycle）。（另一种定义是：walk对应上述的path， path对应上述的track 。Trail对应 trace。）桥（Bridge ）：若去掉一条边，便会使得整个图不连通，该边称为。图的存储表示1.数组（邻接矩阵）存储表示（有向或无向）typedef structVRType adj; /顶点关系类型。对无权圏*用1（是）或趴否）表示相邻否i对带权图，刊为权值 InfaType/该弧拒美信息的指针（可无）JArcCell,

17、 MatrxMAX_VERTEX_MUlMMAX_VERTEX_NUIM;.-/ 二维数组struct rGraphA f弐A03AV 中的顼Q CO境规占枚荷肯最短2选人G此时0=弧c*側播趣SS橙ATy殴C为申闹点，从k-C=3这熹帑趣SS径开 站找V=D、E. Fa -c t耐c比上面眾一歩的 r 聪要短） 就时列B抚值为A TU -S=5A -C T XEA -C ETA T瞪T直催V中的顶点二加爲观* TQ -B=5衩偉为餐短Z选入此时鈴匚、止时疑短S&径 斗社0*九一03,A TU 以E为中间点从去TC TE再这条杲短X狐 H FA贞一CTETD =10（比;面第二歩的AD=6要长

18、J 就时到D取值更改为A -C TD翡人C TE T菖池U中的顶点=oa览现atctm权傥为杲短4ift人九a c,比 &止阳最短罐往F S3.A TC B-5 * C D=&削D为申词点,从盘T C TD这条席短路径 另赠找11= ATCTDTE =3( tt面箫二歩的 ATCTE b 要*; 时到E权值更改育ATCTE可ATCTJtTF W爲观aTCTE =t权值加蹇短SiSAif比也狀时暑短握径A TWO * fc-C=3*C TD=3ATCTE =7以E为中何丸从A-C-I =7谨条理逻 理住开始找x A TC T E TF =12 C馆上面算E3步的& TC T D TF羽 賽长）此

19、时劉FtSUS更改麹ATCTDTF =9 蔑规ATCTDTP勻权值力堆短6选入F此时丹S匚、氛比E、F 肠接祖銘径AT口玄TC -B=S A C TD=& aTCTE =T 丸 TCTDF Sfl弗洛伊德算法1.定义概览Floyd-Warshall算法（Floyd-Warshall algorithm ）是解决任意两点间的最短路径 的一种算法，可以正确处理有向图或负权的最短路径问题，同时也被用于计算有 向图的传递闭包。Floyd-Warshall算法的时间复杂度为0（N，空间复杂度为 0（N2）。2.算法描述1）算法思想原理：Floyd算法是一个经典的动态规划算法。用通俗的语言来描述的话，首先

20、我们 的目标是寻找从点i到点j的最短路径。从动态规划的角度看问题，我们需要为 这个目标重新做一个诠释（这个诠释正是动态规划最富创造力的精华所在）从任意节点i到任意节点j的最短路径不外乎2种可能，1是直接从i至叮,2 是从i经过若干个节点k至叮。所以，我们假设Dis(i,j)为节点u到节点v的最短 路径的距离，对于每一个节点 k,我们检查Dis(i,k) + Dis(k,j) right 一定不为空，右旋的时候p-left 定不为空，这是显而易见的。如果从空树开始建立，并时刻保持平衡，那么不平衡只会发生在插入删除操删除 虽然平衡二叉树的节点删除操作的代码比较复杂， 代码量也比较大， 但是其删除

21、过程只有以下 3 种情况： 注：只要牢牢把握住以下 3 点，理解平衡二叉树的删 除操作不是太难 被删的节点是叶子节点处理思路： 将该节点直接从树中删除， 并利用递归的特点和高度的变化， 反向推 算其父节点和祖先节点是否失衡。如果失衡，则判断是那种类型的失衡（LL 、LR、RR、RL），再对失衡节点进行旋转处理，直到根节点或高度不再变化。 被删的节点只有左子树或只有右子树 处理思路：将左子树（右子树）替代原有节点的位置，并利用递归的特点和高度 的变化，反向推算父节点和祖先节点是否失衡。 如果失衡， 则判断是那种类型的 失衡（LL、LR、RR、RL），再对失衡节点进行旋转处理，直到根节点或高度 不

22、再发生变化。 被删的节点既有左子树又有右子树 处理思路：找到被删节点的左子树的最右端的节点 rnode,将rnode的值赋给node, 再把rnode的左孩子替换rnode的位置，在把rnode释放掉，并利用递归特点， 反向推断rnode的父节点和祖父节点是否失衡。如果失衡，则判断是哪种类型的 失衡（LL、LR、RR、RL），再对失衡的节点进行旋转处理，直到根节点或高 度不再发生变化。LOG寺如果q新的平衡因子bf(q)=0,意味着删除前bf(q)=1或者bf(q)=-1,只有单子树心此时高度减仁需改变父节点和其他某些祖先节点 的平衡因子现象2:如果q新的平衡因子bf(q)=l或-1,意味着删

23、除前bf (q)=0,左右子树高度一样:此时高度不变，需改变父节点和其他某些祖先节 点的平衡因子铮如果q新的平衡因子bf(q)= 2或2,意味着删除前 bf(q)二-1或1,左右子树高度不同昏此时树在q节点是不平衡的，需要平衡化处理B-树和B+树定义和分析，算法要求程度不高。哈希表定义构造方法处理冲突的方法 查找_直接播入排常 厂插人排序黑尔排库使用内存内部排序广简单选择排序 r选择排序堆排序冒泡排序快速排序排序交换排序.-.-归并排序L基数排序内存和外村结台使用外部排序排序插入排序直接插入排序1. 直接插入排序的基本思想 直接插入排序（Insertion Sort）的基本思想是：每次将一个待

24、排序的记录，按其关键字大小插入到前面已经排好序的子序列中的适当位置，直到全部记录插 入完成为止。设数组为a0n-1。1. 初始时，a0自成1个有序区，无序区为a1.n-1。令i=12. 将ai并入当前的有序区a0 i-1中形成a0i的有序区间。 3.i+并重复第二步直到i=n-1。排序完成。折半插入排序 算法的基本过程：1） 计算0 i-1 的中间点，用i索引处的元素与中间值进行比较， 如果i索引处的元素大，说明要插入的这个元素应该在中间值和刚加入i索引之间，反之，就是在刚开始的位置至帅间值的位置，这样很简单的完成了折半；2）在相应的半个范围里面找插入的位置时，不断的用（1）步骤缩小范围，不停

25、的折半，范围依次缩小为1/21/41/8 .快速的确定出第i个元素要插在什么地方；3）确定位置之后，将整个序列后移，并将元素插入到相应位置。2路插入排序表插入排序希尔排序该方法的基本思想是：先将整个待排元素序列分割成若干个子序列(由相隔某个 “增量”的元素组 成的)分别进行直接插入排序，然后依次缩减增量再进行排 序，待整个序列中的元素基本有序(增量足够小)时，再对全体元素进行一次直 接插入排序。因为直接插 入排序在元素基本有序的情况下(接近最好情况)， 效率是很高的，因此希尔排序在时间效率上比前两种方法有较大提高。以NO的一个数组49, 38? 65, 97, 26,13, 27, 49, 5

26、5, 4为例第一次 gap =10/2 = 549 38 65 97 26 13 27 49 55 41A1B2A2B3A3B4A4B5A5B1A,1B，2A,2B等为分组标记，数字相同的表示在同一组，大写字母表示是该组 的第几个元素， 每 次对同一组的数据进行直接插入排序。即分成了五组 (49, 13) (38, 27) (65, 49)(97, 55)(26,4)这样每组排序后就变成了 (13, 49) (27, 38) (49, 65) (55, 97) (4, 26)，下同。第二次 gap = 5f2 = 2排序后1327495541A1B1C2A2B第 afcgap = 2/2 = 14 26 13 27 381A 1B 1C 1D 1E49386597261D1E2C2D2E49495597651F1G1Hii1J第四次gap = 1/2 = 0排序完成得到数组；4 13 26 27 3849 49 5565 97快速排序冒泡排序 冒泡排序算法的运作如下：(从后往前)比较相邻的元素。如果第一个比第二个大，就交换他们两个。对每一