数据结构核心知识

数据结构,朱全民,KMP算法,KMP的基本原理,假设主串为s1s2sn,模式串为p1p2pm,当模式串发生失配(sipj)时,模式串”向右滑动”可行距离有多远?假设此时应与模式中的第k(kj)个字符继续比较,则模式中的前k-1个字必须与主串的前k-1个字符相等,有p1p2pk-1=si-k+1si-k+2si-1由已经得到的部分匹配结果可知pj-k+1pj-k+2pj-1=si-k+1si-k+2si-1所以有p1p2pk-1=pj-k+1pj-k+2pj-1由上式可知,当主串第i个字符与模式串第j个字符不相等时候,仅需将模式串向右滑动到模式串中的第K个字符和主串中的第i个字符对齐,此时模式中的头K-1个字符的子串肯定与主串中第i个字符之前的K-1个子串相等.,怎样求K,KMP示例,求next函数,next1=0,设nextj=k,表明,p1p2pk-1=pj-k+1pj-k+2pj-1(1)若pk=pj,则在模式串中有p1p2pk=pj-k+1pj-k+2pj显然nextj+1=k+1(2)若pkpj,则杂模式串中有p1p2pkpj-k+1pj-k+2pj则可将求next函数的问题看成整个模式串既是主串又是模式串的问题,应将模式串滑动到nextk个字符和主串的第j个字符相比较.若nextk=k,且pj=pk,则说明在主串中第j+1个字符之前存在一个长度为k的最长子串,和模式串中从首字符起长度为k的子串相等,即p1p2pk=pj-k+1pj-k+2pj也就是说nextj+1=k+1=nextk+1,求NEXT算法,Procget_next(t:strtp)next为全程变量j:=1;k:=0;next1:=0;Whilejt.curlendoif(k=0)or(t.chj=t.chk)thenj:=j+1;k:=k+1;nextj:=kelsek:=nextkendP,DNA病毒,科学家最近发现了某种病毒，通过对该病毒的分析，它的DNA是是环状的，科学家为了方便研究，将病毒DNA表示成由一些字母组成的字符串，现在科学家怀疑有人中了这种病毒，如何判断是否中了病毒呢？主要是看这种病毒代码是不是在人的DNA中出现过，如果出现过，则此人中了病毒，否则没有中病毒。例如，假设人的DNA代码为abcddcba，而病毒代码为ccdd，则abcddcba的下划线部分为病毒部分，该人中了毒。科学家有一些任务，他们已找出了病毒的DNA和人的DNA，现在要你提供帮助，看看哪些是否中了毒。,约束,输入：DNA.in第一行一个数n，表示有n个任务，（k=300）。接下来的每个任务都包括两行，第2i行的字符串表示第i个人的DNA(长度=8000)，第2i+1行的字符串，表示第i个病毒的DNA。（长度=length(T)就输出yes,否则是no.,二叉排序树,它或者是一颗空树，或者是具有如下性质的二叉树：1)若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值2)若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值3)它左右子树分别为二叉排序树。,查找,FUNCbstsrch(t:bitreptr;K:keytype):bitreeif(t=nil)or(t.key=K)thenreturn(t)elseift.keyKthenreturn(bstsrch(t.lchild,k)elsereturn(bstsrch(t.rchild,k)endF,插入,PROCins_bstree(varbst:bitree;k:keytype);new(s);s.key:=k;s.lchild:=nil;s.rchild:=nil;ifbst=nilthenbst:=s;elseifKfkeythenf.lchild:=s;elsef.rchild:=sendP,删除,分三种情况讨论1)删除叶子节点不破坏树的结构,修改其双亲结点:f.lchild:=NIL2)若只有左孩子Pl或者只有右孩子Pr,则只要令Pl或Pr直接为F的左孩子即可:f.lchild:=P.lchild;或者f.lchild:=P.rchild;3)左右孩子都有,设中序遍历的序列为ClC.QlQSlSPPrF,令P的左孩子为F的右孩子,而P的右孩子为S的右孩子q:=p;s:=p.lchild;whilesrchildnildoq:=s;s:=s.rchildp.data:=s.data;ifqpthenq.rchild:=s.lchildelseq.lchild:=s.lchilddispose(s),堆,堆的建立,PROCshift(varr:listtype;k,m:integer);i:=k.j:=2*i;x:=rk.key;finish:=falset:=rk;while(jrj+1.key)thenj:=j+1;Ifx=rj.keythenfinish:=trueElseri:=rj;i:=j;j:=2*Iri:=tendPPROCheapsort(varr:listtype);Fori:=n/2downto1shift(r,I,n);Fori:=ndownto2dor1与ri交换;shift(r,1,i-1)endP,最短路经问题(Dijkstra算法),核心思想：按路径递增的次序产生最短路径的算法1)找到图中最短的路径，设为（v,vj）,将j设为已标号的点2)找下一条次短的路径，假设终点为k,将k设为已标号的点,那么要么是（v,vk）要么是（v,vj,vk）,若经过vj,将j设为已检查的点,放入集合.3)以次短路径出发找第三短的路径,类似第二步的方法.4)按上述方法一直到所有的顶点被检查过,则从v到其他顶点的最短路径求出.,PROCshort_DIJ(da:adjmatrix;v0:vtxptr)vardist:arrayvtxptrofweighttype;存储路径长度path:arrayvtxptrofset;存储路径fori:=1tovxtmundodisti:=da.costv0,i;ifdistimaxthenpathi:=v0+ielsepathi:=;s:=v0;s存储被标号的顶点fork:=1tov