大二上数据结构学习笔记

1、算法的时间复杂度：一般情况下，算法中基本操作重复执行的次数是数 f(n)，则算法的时间复杂度为：规模 n 的某个函T(n) = O(f(n)它表示随着规模 n 的增大，算法执行时间的增长率和 f(n)的增长率相同。算法的空间复杂度：作为算法所需空间的量度S(n) = O(f(n)一个上机执行的程序消耗的空间用在了两个地方：1 寄存程序本身执行所用的指令、常数、变量和输入数据 2 对数据进行操作的工作单元和空间一些为实现计算所需信息的辅助线性表线性结构的特点：(1)唯一一个被称为“第一个”的数据元素(2)唯一一个被称为“最后一个”的数据元素(3) 除第一个之外，集合中每个数据元素均只有一个前驱(

2、4) 除最后一个之外，集合中每个元素均只有一个后继(a1,ai-1, ai, ai+1, , an)线性表的顺序表示：指的是用一组地址连续的单元依次线性表的数据结构。是一种随机存取的结构。LOC(ai+1)=LOC(ai)+LLOC(ai)=LOC(a1)+(i-1)*L线性表的链式表示：线性链表：节点数据域和指针域。n 个节点成一个链表即为线性表的链式结构。只包含一个指针域的链表称为线性链表或单链表。1 假设 L 是 LinkList 型变量，则 L 为单链表的头指针，它指向单链表的第一个节点2 有时在单链表第一个节点之前附设一个头结点3 单链表是非随机的结构，取得第 i 个数据元素必须从头

3、指针出发寻找静态链表：借助一维数组来描述线性链表。可以用在没有指针概念的高级语言中。定义中用cur 代替指针的概念假设 S 为 SlinkList 型的变量，则 S0.cur 指示第一个节点在数组中的位置，若设 I = S0.cur，则 Si.data 为性表中的第一个数据元素，Si.cur 指示第二个节点在数组中的位置。循环链表：特点是表中最后一个节点的指针域指向头结点。双向链表：特点，有两个指针域，一个指向直接后继，另一个指向直接前驱。栈定义：是限定仅在表尾进行种后进先出的线性表或删除操作的线性表。表尾称为栈顶，表头称为栈底。是一顺序栈：即栈的顺序结构是利用一组地址连续的单元依次存放自栈底

4、到栈顶的数据元素。栈顶指针 top=0 表示空栈。顺序栈的定义：其中，stacksize 为栈容量；base=top 时表示空栈；非空栈的栈顶指针始终在栈顶元素的下一个位置链栈：实现起来比顺序栈简单队列队列是一种先进先出的线性表。和线性表类似，队列也可以有两种结构。链队列：用链表表示的队列称为链队列。队列为空的头结点。条件是：Q.front=Q.rear,并都指向顺序队列：队列的顺序结构，用一组地址连续的单元依次存放队头到队尾的元素；附设两个指针 front 和 rear 分别指示队列头元素和队尾元素。初始化空队列时，front=rear=0；当新元素时队尾指针加 1，当删除队头元素时，头指针

5、增 1.循环队列：串串：也叫字符串，是由零个或多个字符组成的有限序列，记为s=a1a2an字符串的最小操作子集：串赋值、串比较、求串长、串连接、求子串。串的定长顺序：用一组地址连续的单元串值的字符序列。按照预定义的大小，为每个定义的串变量分配一个固定长度的区，则可用定长数组如下描述：串的堆分配:仍然以一组地址连续的单元存放串值字符序列，但是他们的空间是程序执行过动态分配的。在 C语言中，一种称之为“堆”的区，并由动态分配函数malloc()和free()来管理。串的块链表示：1 采用链式方式串值；2一个节点大小的：如下图下图为串的块链表示数据结构：串的模式匹配算法：KMP 算法实现的index

6、 函数：略，以后补充。数组和广义表数组的顺序：由于二维数组可看成一维数组的数组，在时两种：即以列序为主序和以行序为主序，C 语言中用的是行序为主序，即顺序为a00,a01a0n,a10,a11a1n,am0,am1,amn二维数组中元素aij位置的计算(以行序为主序)：假设每个数据元素占 L 个空间，则二维数组 A 中任意一元素aij 的位置为LOC(i,j)=LOC(0,0)+(b2*i+j)*L推广到n 维：LOC(j1,j2,jn)=LOC(0,0,0)+(b2*bn*j1+b3*bn*j2+bn*jn-1+jn)*L=LOC(0,0,0)+(*L可缩写成LOC(j1,j2,jn)=LO

7、C(0,0,0)+其中,1i=n矩阵的压缩：特殊矩阵和稀疏矩阵：指的是值相同的元素或者零元素在矩阵中的分布有一定的规律。反之则称为稀疏矩阵。n 阶对称阵：,1=i,j=n对于对称阵，可以为每一对对称元素分配一个空间，则可将个元压缩到 n(n+1)/2 个元空间中。假设用一维数组san(n+1)/2作为 n 阶对称矩阵 A 的结构，则 sak和矩阵元之间如下对于任意给定的一组下标(i,j)，均可在 sa 中找到矩阵元aij，反之，对于所有的k=0,1,2，,都能确定 sak中的元在矩阵中的位置(i,j)。称san(n+1)/2为 n 阶对称矩阵 A 的压缩矩阵。稀疏矩阵：直觉上讲就是零元素占绝大

8、部分，非零元素看起来比较稀疏的矩阵。=t/(m+n)称为稀疏因子。：三元组顺序表求三元组顺序表的转置矩阵：a将矩阵的行列值进行互换 bi，j 值互相交换将每个三元组的c重新排列三元组的顺序a 和 b 容易实现，如何实现 c？有两种实现：第一种：按照b.data 中三元组的次序依次在 a.data 中找到相应的三元组进行转置，即按照矩阵M 的列序进行转置。为了找到 M 的每一列中所有的非零元素，需要对其三元组表 a.data 从第一行起整个扫描一遍，具体算法如下：该算法只适用于tumu*nu 的情况，当tu 和mu*nu 同数量级时，时间复杂度为O(mu*nu2),虽然节省了空间，但是时间复杂度

9、提高了。求c 的第二种是：按照 a.data 中三元组的次序进行转置，并将转置后的三元组置入 b 中的恰当位置。在此 numcol表示矩阵M 中第 col 列中非零元的个数，cpotcol表示 M 中第 col 列的第一个非零元在b.data 中的恰当位置。cpot1=1;cpotcol=cpotcol-1+numcol-12=col=1）性质二：深度为 k 的二至多有 2k-1 个结点（k=1）性质三：对任何一二则 n0=n2+1T，如果其终端结点数为 n0，度为二的结点数为 n2，性质三的证明：结点总数 n=n0+n1+n2,从分支数考虑：除了根节点其余结点都有一个分支进入，设 B 为分支

10、总数，则n=B+1，B=n1+2n2，三式联立得之：一颗深度为 k，且有 2k-1 个结点的二满二称为满二完全二为 k 的满二：深度为 k 的有 n 个结点的二，当且仅当其每一个结点都与深度中编号从 1 到 n 的节点一一对应时，称之为完全二。如下图完全二的性质：n的深度为log2 +1性质 4：具有 n 个结点的完全二n(其深度为log2 +1)的结点按层序性质 5：如果对一颗有 n 个结点的完全二编号(从第 1 层到第log2n+1 层，每层从左到右)，则对任意一结点 i(1=i1，则双亲是i/2(2) 如果 2in,则结点 i 无(结点 i结点)；否则其是结点 2i(3) 如果 2i+1

11、n,则结点 i 无右孩子；否则其右孩子是结点 2i+1二的结构：顺序结构：用一组地址连续的单元依次自上而下、自左至右完全二上的节点，对于一般二对一般的二，用 0 表示不浪费了大量的的节点。这种空间。结构只适用于完全二。链式结构：至少包含一个数据元素和两个指针域，为了便于找到点的指针域。点还可以增加指向上图两种结构分别为二叉链表和三叉链表。容易证得含有 n 个节点的二叉链表中有 n+1 个空链域。二叉链表的定义：遍历二：先序(根)遍历、中序(根)遍历、后序(根)遍历先序遍历二叉链表的递归算法：仿照递归算法的执行过法。递归栈的状态变化状况，可直接写出相应的非递归算线索二：对二进行遍历实际上就是按照

12、一定的规则将二排列成一个线性序列。但是对于二叉链表，只能找到结点的左右孩子信息，如何解决这个问题捏？假象若结点有树，则其 lchild 域指示其，否则指示其前驱；若树，则其 rchild 域指示其右孩子，否则指示其后继，为避免结点，尚需增加两个标志域以这种结点结构的二叉链表叫做线索链表。，其中指向结点前驱和后继的指针叫做线索，加上线索的二叫做线索二，对二以某种次序遍历使其变为线索二的过程叫做线索化。树和森林：树的结构：1 双亲表示法：以一组连续的空间树的节点，同时在每一个结点中附设一个指示器指示其双亲结点在链表中的位置。2 孩子表示法：把每个节点的孩子结点排列起来，看成是一个线性表，且以单链表

13、作为结构，则 n 个结点有 n 个孩子链表(叶子的孩子链表为空表)。而 n 个头指针又组成一个线性表，为了便于查找，可采用顺序结构。孩子兄弟表示法：又称二表示法、二叉链表表示法。即以二叉链表作为树的结构。链表中结点的两个链域分别指向该节点的第一个孩子结点(firstchild 域)和下一个兄弟结点(nextsibling 域)。森林与二的转换：1 森林转换成二：如果 F=T1,T2,Tm是森林，则可按如下规则转换为一颗二B=(root,LB,RB).(1)若 F 为空，即 m=0，则 B 为空树；(2)若 F 非空，则B 的根 root 即为森林中第一颗树的根 ROOT(T1)；B 的树 LB

14、 是从 T1点的子树森林 F1=T11,T12,T1m1转换而成的二；其右子树 RB 是从森林F= T2,Tm 转换而成的二。2 二转换为森林：如果 B=(root,LB,RB)是一颗二，则可按照如下规则转换成森林 F= T1,T2,Tm 。(1)若 B 为空，则 F 为空；(2)若 B 非空，则 F 中第一棵树 T1 的根 ROOT(T1)即二B 的根 root；T1点的子树森林 F1 是由树 LB 转换而成的森林；F 中除 T1 之外其余树组成的森林 F= T2,Tm B 的是由 B 的右子树 RB 转换而成的森林。树和森林的遍历：树：先根遍历树、后根遍历树，例：先根遍历为：ABCDE后根

15、遍历为：BDCEA森林：先序遍历森林、中序遍历森林先序遍历森林：(1)森林中第一棵树的根节点(2) 先序遍历第一棵根节点的子树森林(3) 先序遍历除第一棵树之后剩余的树的森林中序遍历森林：(1) 中序遍历森林中第一棵根节点的子树森林(2)第一棵树的根节点(3) 中序遍历除第一棵树之后剩余的树的森林最优二(树)：路径：从一个结点到另一个结点之间的分支这两个结点之间的路径，路径上的分支数目称作路径长度。树的路径长度：树根到每个结点的路径长度之和。结点的带权路径长度：从该结点到树根之间的路径长度与结点上权的乘积。树的带权路径长度：所有叶子节点的带权路径长度之和，记为 WPL=。最优二结点的二或树：假

16、设有 n 个w1,w2,wn，试构造一颗有 n 个叶子wi，则其中带权路径长度 WPL 最小的二叉，每个叶子结点带树称作最优二或树。树的(算法)：w1,w2,wn构造(1) 根据给定的 n 个n 棵二的集合 F=T1,T2,Tn，其中每棵二Ti 中只有一个带wi 的根结点，其树均为空。(2) 在 F 中选取两棵根结点的最小的树作为树构造一棵新的二，且置新的二的根结点的为其树上根结点的之和。(3) 在 F 中删除这两棵树，同时将新得到的二加入 F 中。(4) 重复(2)和(3)，直到 F 只含一棵树为止。这棵树就是树。前缀编码：任一字符的编码都不是另一个字符的编码的前缀，这种编码称为前缀编码。假

17、设有一棵如图的二，则可以从根节点到叶子结点的路径上分支字符组成的字符串作为该叶子结点字符的编码，可以证明如此得到的必为二进制前缀编码。若 wi(字符出现的频率)为二叶子结点的权，li 为从根到叶子的路径长度，则最短的二所代表的编码即为编码。由此可见，设计电文总长最短的二进制前缀编码即为以 n种字符出现的频率作权，设计一颗树的，由此得到的二进制前缀编码称为编码。图：顶点有和无：有：弧、弧头、弧尾无：边G1=(V1,A1),其中 V1=v1,v2,v3,v4,上图中有A1=,无G2=(V2,E2),v2=v1,v2,v3,v4,v5,E2=(v1,v2),(v1,v4),(v2,v3),(v2,v

18、5),(v3,v4),(v3,v5)如果用 n 表示图中顶点数目，用 e 表示弧的数目，对于无，e 的取值范围是 0 到，对于有，e 的取值范围是 n(n-1)：完全图：有条边的无称为完全图。有向完全图：具有 n(n-1)条弧的有称为有向完全图。网：带权的图称为网。子图：假设有两个图，G=(V,E)和 G=(V,E)，如果 V含于 V，且 E含于 E，则称 G为 G 的子图。顶点的度：对无，顶点 v 的度是和 v 相关联边的个数，记为 TD(v)；对有向图顶点 v 的度为入度和出度之和，即 TD(v)=ID(v)+OD(v)G=(V，E)中顶点 v 到顶点 v的路径是一个顶点序列，如果 G 是

19、路径：无有向的，则路径也是有向的。回路或环：第一个顶点和最后一个顶点相同的路径称为回路或环。简单路径：序列中顶点不重复出现的路径。简单回路或简单环：如果顶点 v 和 v之间有路径，则称 v 和 v是连通的。连通：在无连通图：如果对于图中任意两个顶点都是连通的，则称为连通图。连通分量：无的极大连通子图G 中，如果对于每一对 vi，vj，从 vi 到 vj 和从 vj 到 vi 都有强连通图：在有路径，则 G 是强连通图。有极大强连通子图称作有的强连通分量。生成树：有足以通图的生成一个极小连通子图，它含有图中全部顶点，但只一棵树的 n-1 条边。一颗有 n 个顶点的生成且仅有 n-1 条边。如果一

20、个图有 n 个顶点和小于 n-1 条边，则是非连通图。如果它多于 n-1 条边，则一定有环。图的结构：常用的有数组表示法、邻接表、邻接多重表、十字链表数组表示法：用两个数组分别储顶点信息，二维数组 arcs顶点信息和弧的信息。一维数组 vexs 存弧的信息，称为邻接矩阵。例如，图 7.1 中 G1 和 G2 的邻接矩阵为：为对称阵，顶点 vi 的度是邻接矩阵中第 i 行(或 i 列)元对无和，即对于有，第 i 行元和为顶点vi 的出度，第 j 列元和为顶点vj 的入度。网的邻接矩阵可定义为：如下图示邻接表：一种链式结构。对图中每个顶点建立一个单链表，第 i 个单链表中的结点表示依附于顶点 vi

21、 的边(对有是以 vi 为尾的弧)。表结点：邻接点域(adjvex)指示与顶点 vi 邻接的点在图中的位置链域(nextarc)指示下一条弧的结点。数据域(info)和弧相关的信息，如。头结点：链域(firstarc)指向链表中第一个结点数据域(data)其他有关信息，顶点 vi 的度恰为第 i 个链表的结点数。而有，第 i 个链表中结无点的个数只是顶点 vi 的出度。为求入度，要遍历所有邻接表。逆邻接表：为了便于确定顶点的入度，可以建立有的逆邻接表，即对每个顶点 vi 建立一个以 vi 为头的弧的表。十字链表：是有的另一种链式结构。在十字链表中每一条弧有一个结点，每个顶点有一个结点在弧结点中

22、尾域(tailvex)和头域(headvex)分别指示弧尾和弧头这两个顶点在图中的位置，链域 hlink 指向弧头相同的下一条弧，链域 tlink 指向弧尾相同的下一条弧。Info 域指向该弧的相关信息。弧头相同的弧在同一链表上，弧尾相同的弧也在同一链表上。弧结点的头结点是顶点结点，两个链域 firstin 和 firstout，分别指向以该顶点为弧头或弧尾的第一个弧结点。邻接多重表：图的遍历：从图中某一定点出发次。图中其余顶点，且使每一个顶点仅被一深度优先搜索：类似于树的先根遍历。假定初始状态是图中所有顶点未曾过，则从某个顶点 v 出发，此顶点，然后依次从 v 的未被的邻接点出发深度到；若还

23、有尚未优先遍历图，直至图中所有和 v 有路径相通的顶点都被的顶点，则另选图中一个未曾被的顶点作起始点，重复上述过程，直到图中所有顶点都被到为止。广度优先搜索：类似于树的按层次遍历的过程。假设从图中某个顶点 v 出发，在了 v 之后依次v 的各个未曾过的邻接点，然后分别从这些邻接点出发依次他们的邻接点，并使“先被的顶点的邻接点”先于“后被顶点的邻接点”被，直至图中所有已被的顶点的邻接点都被到。若还有未被到的顶点，则另选图中一个未曾被的顶点作起始点，重复上述过程，直至图中所有顶点都被到为止。查找：查找表：是由同一类型的数据元素(或)的集合静态查找表：(1)某个特定的数据元素是否在查找表中。(2)检

24、索某个特定的数据元素的各种属性。若查找表只做上面两种操作，称为静态查找表。抽象数据类型静态查找表的定义：动态查找表：若在查找过找表同时进行和删除操作，此类查找表称为动态查查找：根据给定的某值，在查找表中确定一个其关键字等于给定值的元素。或数据静态查找表之顺序表的查找：顺序查找：从表中最后一个开始，逐个进行的关键字和给定值的比较，若某个的关键字和给定值相等，则查找。静态查找表之有序表的查找：折半查找：先确定待查下：所在范围，然后逐步缩小范围直到找到为止。算法如动态查找表之二叉排序树：1树上所有结点的值均小于它的根结点的值2 右子树上所有结点的值均大于它的根节点的值 3树也是二叉排序树当取二叉链表

25、作为二的结构时，查找算法为：二叉排序树的和删除操作：书中讲的图 9.8子？是否有错误？如果是45,24,53,45,12,24,52生成的树该是什么样平衡二：树和右子树都是平衡二，且树和右子树的深度之差的绝对值不超过 1表：知道关键字 key，通过函数 f(key)就能直接得到的位置，按这个思想建立的表称为表。函数的构造：(1)直接定址法：取关键字或关键字的某个线性函数为地址，即H(key)=key 或 H(key)=a*key+b(2)(3)(4)数字分析法：对关键字进行分析，取关键字的若干数位组成地址平方取中法：取关键字平方后的中间几位为地址折叠法(5)除留余数法(6)随机数法排序：分为内

26、部排序和外部排序内部排序：待排序存放在计算机随机器中进行的排序过程外部排序：待排序尚需对外存进行数量很大，以致内存一次不能够容纳全部的排序过程，在排序过直接排序：将一个到已排好序的有序表中，从而得到一个新的、记录数增 1 的有序表。如下所示，对顺序表作直接排序的算法，r0处不存放，作监视哨用，以防止在查找位置过数组下表出界(监视哨到底多大用处不清楚)排序，算法的时间复杂度为 o(n2),但是，当待排序序列为排序：对直接“正序”时，其时间复杂度可提高到 o(n)。由此若待排序序列是基本有序的，则排序效率就会大幅提高。排序的基本思想：先将整个待排序序列分割成为若干子序列分别进行直接排序，待整个序列中的基本有序时，再对全体进行一次直接插入排序。例子：首先分为 5 个子序列R1,R6,R2,R7,R5,R10,分别进行直接排：序 ； 得 到 一 趟 排 序 结 果 后R1,R4,R7,R10,R2,R5,R8,R3,R6,R9再进行第二趟排序冒泡排序：时间复杂度 o(n2)快速排序：是对冒泡排序的改进。它的基本思想是，通过一趟排序将待排序分割成的两部分，其中一部分的关键字均比另一部分的关键字小，则可