数据结构学习笔记

算法的时间复杂度：一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数f(n)，则算法的时间复杂度为：T(n)=O(f(n))它表示随着问题规模n的增大，算法执行时间的增长率和f(n)的增长率相同。算法的空间复杂度：作为算法所需存储空间的量度S(n)=O(f(n))一个上机执行的程序消耗的存储空间用在了两个地方：1寄存程序本身执行所用的指令、常数、变量和输入数据2对数据进行操作的工作单元和存储一些为实现计算所需信息的辅助空间线性表线性结构的特点：(1)存在唯一一个被称为“第一个”的数据元素(2)存在唯一一个被称为“最后一个”的数据元素(3)除第一个之外，集合中每个数据元素均只有一个前驱(4)除最后一个之外，集合中每个元素均只有一个后继(a1,…ai-1,ai,ai+1,…,an)线性表的顺序表示：指的是用一组地址连续的存储单元依次存储线性表的数据结构。是一种随机存取的存储结构。LOC(ai+1)=LOC(ai)+LLOC(ai)=LOC(a1)+(i-1)*L线性表的链式表示：线性链表：节点包括数据域和指针域。n个节点链接成一个链表即为线性表的链式存储结构。只包含一个指针域的链表称为线性链表或单链表。eq\o\ac(○,1)假设L是LinkList型变量，则L为单链表的头指针，它指向单链表的第一个节点eq\o\ac(○,2)有时在单链表第一个节点之前附设一个头结点eq\o\ac(○,3)单链表是非随机存储的存储结构，取得第i个数据元素必须从头指针出发寻找静态链表：借助一维数组来描述线性链表。可以用在没有指针概念的高级语言中。定义中用cur代替指针的概念假设S为SlinkList型的变量，则S[0].cur指示第一个节点在数组中的位置，若设I=S[0].cur，则S[i].data为存储在线性表中的第一个数据元素，S[i].cur指示第二个节点在数组中的位置。循环链表：特点是表中最后一个节点的指针域指向头结点。双向链表：特点，有两个指针域，一个指向直接后继，另一个指向直接前驱。栈定义：是限定仅在表尾进行插入或删除操作的线性表。表尾称为栈顶，表头称为栈底。是一种后进先出的线性表顺序栈：即栈的顺序存储结构是利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素。栈顶指针top=0表示空栈。顺序栈的定义：其中，stacksize为栈容量；base=top时表示空栈；非空栈的栈顶指针始终在栈顶元素的下一个位置链栈：实现起来比顺序栈简单队列队列是一种先进先出的线性表。和线性表类似，队列也可以有两种存储结构。链队列：用链表表示的队列称为链队列。队列为空的判断条件是：Q.front=Q.rear,并都指向头结点。顺序队列：队列的顺序存储结构，用一组地址连续的存储单元依次存放队头到队尾的元素；附设两个指针front和rear分别指示队列头元素和队尾元素。初始化空队列时，front=rear=0；当插入新元素时队尾指针加1，当删除队头元素时，头指针增1.循环队列：串串：也叫字符串，是由零个或多个字符组成的有限序列，记为s=’a1a2…an’字符串的最小操作子集：串赋值、串比较、求串长、串连接、求子串。串的定长顺序存储：用一组地址连续的存储单元存储串值的字符序列。按照预定义的大小，为每个定义的串变量分配一个固定长度的存储区，则可用定长数组如下描述：串的堆分配存储:仍然以一组地址连续的存储单元存放串值字符序列，但是他们的存储空间是程序执行过程中动态分配的。在C语言中，存在一种称之为“堆”的自由存储区，并由动态分配函数malloc()和free()来管理。串的块链存储表示：1采用链式方式存储串值；2存在一个节点大小的问题：如下图下图为串的块链存储表示数据结构：串的模式匹配算法：KMP算法实现的index函数：略，以后补充。数组和广义表数组的顺序存储：由于二维数组可看成一维数组的数组，在存储时存在两种存储方法：即以列序为主序和以行序为主序，C语言中用的是行序为主序，即存储顺序为[a00,a01…a0n,a10,a11…a1n,…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)=LOC(0,0,…,0)+其中,,1<i<=n矩阵的压缩存储：特殊矩阵和稀疏矩阵：指的是值相同的元素或者零元素在矩阵中的分布有一定的规律。反之则称为稀疏矩阵。n阶对称阵：,1<=i,j<=n对于对称阵，可以为每一对对称元素分配一个存储空间，则可将个元压缩存储到n(n+1)/2个元空间中。假设用一维数组sa[n(n+1)/2]作为n阶对称矩阵A的存储结构，则sa[k]和矩阵元之间存在如下关系对于任意给定的一组下标(i,j)，均可在sa中找到矩阵元aij，反之，对于所有的k=0,1,2，…,都能确定sa[k]中的元在矩阵中的位置(i,j)。称sa[n(n+1)/2]为n阶对称矩阵A的压缩矩阵。稀疏矩阵：直觉上讲就是零元素占绝大部分，非零元素看起来比较稀疏的矩阵。δ=t/(m+n)称为稀疏因子。存储方法：三元组顺序表求三元组顺序表的转置矩阵：a将矩阵的行列值进行互换b将每个三元组的i，j值互相交换c重新排列三元组的顺序a和b容易实现，如何实现c？有两种实现方法：第一种：按照b.data中三元组的次序依次在a.data中找到相应的三元组进行转置，即按照矩阵M的列序进行转置。为了找到M的每一列中所有的非零元素，需要对其三元组表a.data从第一行起整个扫描一遍，具体算法如下：该算法只适用于tu<<mu*nu的情况，当tu和mu*nu同数量级时，时间复杂度为O(mu*nu2),虽然节省了存储空间，但是时间复杂度提高了。求c的第二种方法是：按照a.data中三元组的次序进行转置，并将转置后的三元组置入b中的恰当位置。在此num[col]表示矩阵M中第col列中非零元的个数，cpot[col]表示M中第col列的第一个非零元在b.data中的恰当位置。cpot[1]=1;cpot[col]=cpot[col-1]+num[col-1]2<=col<=a.nu行逻辑链接的顺序表：为了便于随机存取任意一行的非零元，则需要知道每一行的第一个非零元在三元组表中的位置。可将辅助数组cpot固定在稀疏矩阵的存储结构中，以指示行信息。十字链表：当矩阵的非零元个数和位置在操作过程中变化较大时，就不宜采用顺序结构来表示三元组的线性表。有时采用链式存储结构更为合适。当采用链式存储时，每个非零元可用含5个域的节点表示，其中i、j和e这三个域分别表示行、列和值，向右域right链接同一行中下一个非零元，向下域down用以链接同一列中下一个非零元。同一行的非零元通过right域链接成一个线性链表，同一列的非零元通过down域链接成一个线性链表，每一个非零元既是某个行链表中的一个节点，又是某个列链表中的一个节点，整个矩阵构成一个十字交叉的链表，故称十字链表。可用两个分别存储行链表的头指针和列链表的头指针的一维数组表示。如图：广义表：是线性表的推广，也叫列表，定义如下广义表一般记为：LS=(α1,α2,…,αn),αi可以是单个元素，也可以是广义表，分别称为广义表的原子和子表，习惯上大写字母表示广义表名称，小写字母表示原子。当广义表非空时，称第一个元素α1为LS的表头，称其余元素组成的表(α2,…,αn)为表尾。广义表的存储结构：由于列表中的数据元素可能为原子或者列表，由此需要两种结构的节点表结点和原子结点。表结点可由三个域组成：标志域、指示表头的指针域、指示表尾的指针域。原子结点由两部分组成：标志域、值域。存储结构示例：树和二叉树二叉树：每个节点至多只有两颗子树，且子树有左右之分，其顺序不能任意颠倒。二叉树的性质： 性质一：在二叉树的第i层上至多有2i-1个结点（i>=1） 性质二：深度为k的二叉树至多有2k-1个结点（k>=1）性质三：对任何一二叉树T，如果其终端结点数为n0，度为二的结点数为n2，则n0=n2+1性质三的证明：结点总数n=n0+n1+n2,从分支数考虑：除了根节点其余结点都有一个分支进入，设B为分支总数，则n=B+1，B=n1+2n2，三式联立得之满二叉树：一颗深度为k，且有2k-1个结点的二叉树称为满二叉树完全二叉树：深度为k的有n个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树中编号从1到n的节点一一对应时，称之为完全二叉树。如下图完全二叉树的性质：性质4：具有n个结点的完全二叉树的深度为[log2n]+1性质5：如果对一颗有n个结点的完全二叉树(其深度为[log2n]+1)的结点按层序编号(从第1层到第[log2n]+1层，每层从左到右)，则对任意一结点i(1<=i<=n)，有：如果i=1，则结点i是二叉树的根，无双亲；如果i>1，则双亲是[i/2]如果2i>n,则结点i无左孩子(结点i为叶子结点)；否则其左孩子是结点2i如果2i+1>n,则结点i无右孩子；否则其右孩子是结点2i+1二叉树的存储结构：顺序存储结构：用一组地址连续的存储单元依次自上而下、自左至右存储完全二叉树上的节点，对于一般二叉树，用0表示不存在的节点。这种存储结构只适用于完全二叉树。对一般的二叉树浪费了大量的存储空间。链式存储结构：至少包含一个数据元素和两个指针域，为了便于找到父节点还可以增加指向父节点的指针域。上图两种存储结构分别为二叉链表和三叉链表。容易证得含有n个节点的二叉链表中有n+1个空链域。二叉链表的定义：遍历二叉树：先序(根)遍历、中序(根)遍历、后序(根)遍历先序遍历二叉链表的递归算法：仿照递归算法的执行过程中递归栈的状态变化状况，可直接写出相应的非递归算法。线索二叉树：对二叉树进行遍历实际上就是按照一定的规则将二叉树排列成一个线性序列。但是对于二叉链表，只能找到结点的左右孩子信息，如何解决这个问题捏？假象若结点有左子树，则其lchild域指示其左孩子，否则指示其前驱；若结点有右子树，则其rchild域指示其右孩子，否则指示其后继，为避免混淆，尚需增加两个标志域以这种结点结构构成的二叉链表叫做线索链表。，其中指向结点前驱和后继的指针叫做线索，加上线索的二叉树叫做线索二叉树，对二叉树以某种次序遍历使其变为线索二叉树的过程叫做线索化。树和森林：树的存储结构：1双亲表示法：以一组连续的空间存储树的节点，同时在每一个结点中附设一个指示器指示其双亲结点在链表中的位置。2孩子表示法：把每个节点的孩子结点排列起来，看成是一个线性表，且以单链表作为存储结构，则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是从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是由B的左子树LB转换而成的森林；F中除T1之外其余树组成的森林F‘={T2,…,Tm}是由B的右子树RB转换而成的森林。树和森林的遍历：树：先根遍历树、后根遍历树，例：先根遍历为：ABCDE后根遍历为：BDCEA森林：先序遍历森林、中序遍历森林先序遍历森林：访问森林中第一棵树的根节点先序遍历第一棵树中根节点的子树森林先序遍历除第一棵树之后剩余的树构成的森林中序遍历森林：中序遍历森林中第一棵树中根节点的子树森林访问第一棵树的根节点中序遍历除第一棵树之后剩余的树构成的森林最优二叉树(赫夫曼树)：路径：从树中一个结点到另一个结点之间的分支构成这两个结点之间的路径，路径上的分支数目称作路径长度。树的路径长度：树根到每个结点的路径长度之和。结点的带权路径长度：从该结点到树根之间的路径长度与结点上权的乘积。树的带权路径长度：树中所有叶子节点的带权路径长度之和，记为WPL=。最优二叉树或赫夫曼树：假设有n个权值{w1,w2,…wn}，试构造一颗有n个叶子结点的二叉树，每个叶子结点带权为wi，则其中带权路径长度WPL最小的二叉树称作最优二叉树或赫夫曼树。构造赫夫曼树的方法(赫夫曼算法)：根据给定的n个权值{w1,w2,…wn}构成n棵二叉树的集合F={T1,T2,…,Tn}，其中每棵二叉树Ti中只有一个带权为wi的根结点，其左右子树均为空。在F中选取两棵根结点的权值最小的树作为左右子树构造一棵新的二叉树，且置新的二叉树的根结点的权值为其左右子树上根结点的权值之和。在F中删除这两棵树，同时将新得到的二叉树加入F中。重复(2)和(3)，直到F只含一棵树为止。这棵树就是赫夫曼树。前缀编码：任一字符的编码都不是另一个字符的编码的前缀，这种编码称为前缀编码。 假设有一棵如图的二叉树，则可以从根节点到叶子结点的路径上分支字符组成的字符串作为该叶子结点字符的编码，可以证明如此得到的必为二进制前缀编码。若wi(字符出现的频率)为二叉树叶子结点的权，li为从根到叶子的路径长度，则最短的二叉树所代表的编码即为赫夫曼编码。由此可见，设计电文总长最短的二进制前缀编码即为以n种字符出现的频率作权，设计一颗赫夫曼树的问题，由此得到的二进制前缀编码称为赫夫曼编码。图：顶点有向图和无向图：有向图：弧、弧头、弧尾无向图：边上图中有向图G1=(V1,{A1}),其中V1={v1,v2,v3,v4},A1={<v1,v2>,<v1,v3>,<v3,v4>,<v4,v1>}无向图G2=(V2,{E2}),v2={v1,v2,v3,v4,v5},E2={(v1,v2),(v1,v4),(v2,v3),(v2,v5),(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是有向的，则路径也是有向的。回路或环：第一个顶点和最后一个顶点相同的路径称为回路或环。简单路径：序列中顶点不重复出现的路径。简单回路或简单环：连通：在无向图中如果顶点v和v‘之间有路径，则称v和v’是连通的。连通图：如果对于图中任意两个顶点都是连通的，则称为连通图。连通分量：无向图中的极大连通子图强连通图：在有向图G中，如果对于每一对vi，vj，从vi到vj和从vj到vi都有路径，则G是强连通图。有向图中极大强连通子图称作有向图的强连通分量。生成树：一个连通图的生成树是一个极小连通子图，它含有图中全部顶点，但只有足以构成一棵树的n-1条边。一颗有n个顶点的生成树有且仅有n-1条边。如果一个图有n个顶点和小于n-1条边，则是非连通图。如果它多于n-1条边，则一定有环。图的存储结构：常用的有数组表示法、邻接表、邻接多重表、十字链表数组表示法：用两个数组分别存储顶点信息和边或弧的信息。一维数组vexs存储顶点信息，二维数组arcs存储边或弧的信息，称为邻接矩阵。例如，图7.1中G1和G2的邻接矩阵为：对无向图为对称阵，顶点vi的度是邻接矩阵中第i行(或i列)元素之和，即对于有向图，第i行元素之和为顶点vi的出度，第j列元素之和为顶点vj的入度。网的邻接矩阵可定义为：如下图示邻接表：一种链式存储结构。对图中每个顶点建立一个单链表，第i个单链表中的结点表示依附于顶点vi的边(对有向图是以vi为尾的弧)。表结点：邻接点域(adjvex)指示与顶点vi邻接的点在图中的位置链域(nextarc)指示下一条边或弧的结点。数据域(info)存储和边或弧相关的信息，如权值。头结点：链域(firstarc)指向链表中第一个结点数据域(data)存储其他有关信息无向图中，顶点vi的度恰为第i个链表的结点数。而有向图中，第i个链表中结点的个数只是顶点vi的出度。为求入度，要遍历所有邻接表。逆邻接表：为了便于确定顶点的入度，可以建立有向图的逆邻接表，即对每个顶点vi建立一个链接以vi为头的弧的表。十字链表：是有向图的另一种链式存储结构。在十字链表中每一条弧有一个结点，每个顶点有一个结点在弧结点中尾域(tailvex)和头域(headvex)分别指示弧尾和弧头这两个顶点在图中的位置，链域hlink指向弧头相同的下一条弧，链域tlink指向弧尾相同的下一条弧。Info域指向该弧的相关信息。弧头相同的弧在同一链表上，弧尾相同的弧也在同一链表上。弧结点的头结点是顶点结点，两个链域firstin和firstout，分别指向以该顶点为弧头或弧尾的第一个弧结点。邻接多重表：图的遍历：从图中某一定点出发访问图中其余顶点，且使每一个顶点仅被访问一次。深度优先搜索：类似于树的先根遍历。假定初始状态是图中所有顶点未曾访问过，则从某个顶点v出发，访问此顶点，然后依次从v的未被访问的邻接点出发深度优先遍历图，直至图中所有和v有路径相通的顶点都被访问到；若还有尚未访问的顶点，则另选图中一个未曾被访问的顶点作起始点，重复上述过程，直到图中所有顶点都被访问到为止。广度优先搜索：类似于树的按层次遍历的过程。假设从图中某个顶点v出发，在访问了v之后依次访问v的各个未曾访问过的邻接点，然后分别从这些邻接点出发依次访问他们的邻接点，并使“先被访问的顶点的邻接点”先于“后被访问顶点的邻接点”被访问，直至图中所有已被访问的顶点的邻接点都被访问到。若还有未被访问到的顶点，则另选图中一个未曾被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。查找：查找表：是由同一类型的数据元素(或记录)构成的集合静态查找表：(1)查询某个特定的数据元素是否在查找表中。(2)检索某个特定的数据元素的各种属性。若查找表只做上面两种操作，称为静态查找表。抽象数据类型静态查找表的定义：动态查找表：若在查找过程中同时进行插入和删除操作，此类查找表称为动态查找表查找：根据给定的某值，在查找表中确定一个其关键字等于给定值的记录或数据元素。静态查找表之顺序表的查找：顺序查找：从表中最后一个记录开始，逐个进行记录的关键字和给定值的比较，若某个记录的关键字和给定值相等，则查找成功。静态查找表之有序表的查找：折半查找：先确定待查记录所在范围，然后逐步缩小范围直到找到为止。算法如下：动态查找表之二叉排序树：1左子树上所有结点的值均小于它的根结点的值2右子树上所有结点的值均大于它的根节点的值3左右子树也是二叉排序树当取二叉链表作为二叉树的存储结构时，查找算法为：二叉排序树的插入和删除操作：书中讲的图9.8是否有错误？如果是{45,24,53,45,12,24,52}生成的树该是什么样子？平衡二叉树：左子树和右子树都是平衡二叉树，且左子树和右子树的深度之差的绝对值不超过1哈希表：知道关键字key，通过哈希函数f(key)就能直接得到记录的存储位置，按这个思想建立的表称为哈希表。哈希函数的构造方法：直接定址法：取关键字或关键字的某个线性函数为哈希地址，即H(key)=key或H(key)=a*key+b数字分析法：对关键字进行分析，取关键字的若干数位组成哈希地址平方取中法：取关键字平方后的中间几位为哈希地址折叠法除留余数法随机数法排序：分为内部排序和外部排序内部排序：待排序记录存放在计算机随机存储器中进行的排序过程外部排序：待排序记录数量很大，以致内存一次不能够容纳全部记录，在排序过程中尚需对外存进行访问的排序过程直接插入排序：将一个记录插入到已排好序的有序表中，从而得到一个新的、记录数增1的有序表。如下所示，对顺序表作直接插入排序的算法，r[0]处不存放记录，作监视哨用，以防止在查找插入位置过程中数组下表出界(监视哨到底多大用处不清楚)希尔排序：对直接插入排序，算法的时间复杂度为o(n2),但是，当待排序序列为“正序”时，其时间复杂度可提高到o(n)。由此若待排序序列是基本有序的，则插入排序效率就会大幅提高。希尔排序的基本思想：先将整个待排序记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录基本有序时，再对全体记录进行一次直接插入排序。例子：首先分为5个子序列{R1,R6},{R2,R7}…,{R5,R10},分别进行直接插入排序；得到一趟排序结果后再进行第二趟希尔排序：{R1,R4,R7,R10},{R2,R5,R8},{R3,R6,R9}冒泡排序：时间复杂度o(n2)快速排序：是对冒泡