数据结构核心知识.ppt

《数据结构核心知识.ppt》由会员分享，可在线阅读，更多相关《数据结构核心知识.ppt（30页珍藏版）》请在三一文库上搜索。

1、数据结构,朱全民,KMP算法,KMP的基本原理,假设主串为s1s2sn ,模式串为p1p2pm , 当模式串发生失配 (sipj)时,模式串”向右滑动”可行距离有多远? 假设此时应与模式中的第k (kj)个字符继续比较,则模式中的前k-1个字必须与主串的前k-1个字符相等,有 p1p2pk-1= s i-k+1si-k+2si-1 由已经得到的部分匹配结果可知 pj-k+1pj-k+2pj-1= s i-k+1si-k+2si-1 所以有 p1p2pk-1= pj-k+1pj-k+2pj-1 由上式可知,当主串第i个字符与模式串第j个字符不相等时候,仅需将模式串向右滑动到模式串中的第K个字符和

2、主串中的第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) 若pk pj ,则杂模式串中有 p1p2pk pj-k+1pj-k+2pj 则可将求next函数的问题看成整个模式串既是主串又是模式串的问题,应将模式串滑动到nextk个字符和主串的第j个字符相比较.若nextk=k,且pj=pk,则说

3、明在主串中第j+1个字符之前存在一个长度为k的最长子串,和模式串中从首字符起长度为k的子串相等,即 p1p2pk = pj-k+1pj-k+2pj 也就是说nextj+1=k+1=nextk+1,求NEXT算法,Proc get_next(t:strtp) next为全程变量 j:=1 ;k:=0;next1:=0; While jt.curlen do if (k=0) or (t.chj=t.chk) then j:=j+1;k:=k+1;nextj:=k else k:=nextk endP,DNA病毒,科学家最近发现了某种病毒，通过对该病毒的分析，它的DNA是是环状的，科学家为了方便研

4、究，将病毒DNA表示成由一些字母组成的字符串，现在科学家怀疑有人中了这种病毒，如何判断是否中了病毒呢？主要是看这种病毒代码是不是在人的DNA中出现过，如果出现过，则此人中了病毒，否则没有中病毒。例如，假设人的DNA代码为abcddcba，而病毒代码为ccdd，则abcddcba的下划线部分为病毒部分，该人中了毒。 科学家有一些任务，他们已找出了病毒的DNA和人的DNA，现在要你提供帮助，看看哪些是否中了毒。,约束,输入：DNA.in 第一行一个数n，表示有n个任务，（k=300）。 接下来的每个任务都包括两行，第2i行的字符串表示第i个人的DNA (长度=8000) ，第2i+1行的字符串，表

5、示第i个病毒的DNA。（长度=8000）。 （注意，人的DNA是线性的，而病毒DNA是环状的) 输出：DNA.out n行，每行一个词”YES”或者NO。分别所对应那个任务的判断情况。,样例,DNA.IN 2 bbab abb ababab Ab DNA.OUT YES YES,分析,扩展的kmp：即可以在(n+m)的时间内，求出模式s的每一个位置i可以和j匹配到哪儿。然后求出ai:s的每一个位置向后匹配与t开始向后匹配可以匹配到哪儿。 然后求出bi:从s的每一个位置向前匹配与t从后开始向前匹配可以匹配到哪儿。 如果ai+bi-1=length(T)就输出yes,否则是no.,二叉排序树,它或

6、者是一颗空树，或者是具有如下性质的二叉树：1)若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值2) 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值3)它左右子树分别为二叉排序树。,查找,FUNC bstsrch(t:bitreptr;K:keytype):bitree if (t=nil) or (t.key=K) then return(t) else if t.keyK then return(bstsrch(t.lchild,k) else return(bstsrch(t.rchild,k) endF,插入,PROC ins_bstree(var bst:bi

7、tree;k:keytype); new(s);s.key:=k;s.lchild:=nil;s.rchild:=nil; if bst=nil then bst:=s; else if Kfkey then f.lchild:=s; else f.rchild:=s endP,删除,分三种情况讨论 1)删除叶子节点不破坏树的结构,修改其双亲结点: f.lchild:=NIL 2)若只有左孩子Pl或者只有右孩子Pr,则只要令Pl或Pr直接为F的左孩子即可:f.lchild:=P.lchild;或者f.lchild:=P.rchild; 3)左右孩子都有,设中序遍历的序列为ClC.QlQSlSP

8、PrF,令P的左孩子为F的右孩子,而P的右孩子为S的右孩子 q:=p;s:=p.lchild; while srchildnil do q:=s;s:=s.rchild p.data:=s.data; if qp then q.rchild :=s.lchild else q.lchild :=s.lchild dispose(s),堆,堆的建立,PROC shift (var r:listtype; k,m:integer); i:=k.j:=2*i; x:=rk.key;finish:=false t:=rk; while (jrj+1.key) then j:=j+1; If x=rj.

9、key then finish:=true Else ri:=rj; i:=j; j:=2*I ri:=t endP PROC heapsort(var r:listtype); For i:=n/2 downto 1 shift(r,I,n); For i:=n downto 2 do r1与ri交换; shift(r,1,i-1) endP,最短路经问题(Dijkstra算法),核心思想：按路径递增的次序产生最短路径的算法 1)找到图中最短的路径，设为（v,vj）,将j设为已标号的点 2)找下一条次短的路径，假设终点为k,将k设为已标号的点,那么要么是（v,vk）要么是（v,vj,vk）,

10、若经过vj ,将j设为已检查的点,放入集合. 3)以次短路径出发找第三短的路径,类似第二步的方法. 4)按上述方法一直到所有的顶点被检查过,则从v到其他顶点的最短路径求出.,PROC short_DIJ(da:adjmatrix;v0:vtxptr) var dist:arrayvtxptr of weighttype; 存储路径长度 path:arrayvtxptr of set; 存储路径 for i:=1 to vxtmun do disti:=da.costv0,i; if distimax then pathi:=v0+i else pathi:=; s:=v0; s存储被标号的顶点

11、 for k:=1 tovtxnum-1 do wm:=max; j:=v0; for i:=1 to vtxnum do if not (i in s) and (distiwm) then j:=i;wm:=disti s:=s+j for i:=1 to vtxnum do if not (i in s) and (distj+da.costj,iwm then disti:=distj+da.costj,i; pathi:=pathj+pathi endP,Car的旅行路线,又到暑假了，住在城市A的 Car想和朋友一起去城市B旅游。她知道每个城市都有四个飞机场，分别位于一个矩形的四个顶

12、点上，同一个城市中两个机场之间有一条笔直的高速铁路，第i个城市中高速铁路的单位里程价格为Ti，任意两个不同城市的机场之间均有航线，所有航线单位里程的价格均为t。 那么Car应如何安排到城市B的路线才能尽可能的节省花费昵？她发现这并不是一个简单的问题，于是她来向你请教。,约束条件,输入 第一行为一个正整数n(0n10)，表示有n组测试数据。 每组的第一行有四个正整数s，t，A，B。 s（0S100）表示城市的个数，t表示飞机单位里程的价格，A，B分别为城市A，B的序号，（1A，BS）。 接下来有s行，其中第i行均有7个正整数xi1，yi1，xi2，yi2，xi3，yi3，Ti，这当中的(xi1，

13、yi1)，(xi2，yi2)，(xi3，yi3)分别是第I个城市中任意三个机场的坐标，Ti为第i个城市高速铁路单位里程的价格。 输出 共有n行，每行一个数据对应测试数据。,分析,1、计算两点间的欧氏距离 2、计算每个机场的坐标序列 3、使用Dijkstra算法计算最小费用a,求有向图的关键路径,算法,思想：求事件的最早开始时间vei和最迟开始时间vli。 从ve(1)=0开始往前递推 ve(j)=Maxve(i)+dut() 从vl(n)=ve(n)开始往后递推 vl(i)=Minvl(j)-dut() 算法步骤： 1)输入e条弧建立AOE-网的存储结构 2)从源点V1出发,令ve1=0，按拓

14、扑有序求其余各定点最早发生时间vei。如果得到拓扑有序序列中顶点个数小于网中顶点数n，则说明网中存在环，不能求关键路径，算法中止；否则执行步骤3 3)从汇点Vn出发，令vln=ven，按逆拓扑有序求其余各定点的最迟发生时间vli 4)根据各定点的ve和vl的值求每条弧的最早开始时间e(s)和最迟开始时间l(s)。若满足e(s)=l(s),则该活动为关键活动,FUNC toporder(var dig:adjlisttp):boolean; init(top2); m:=0; ve1.n:=0 while Not empty(top1) do j:=pop(top1); push(top2,j)

15、; m:=m+1; k:=firstadj(dig,j); while k0 do 入度(k):=入度(k)-1; if 入度(k)=0 then push(top1,k); if vej+dut()vek then vek:=vej+dut(); k:=nextadj(dig,j,k) if mn then return(false) else return(true); endF;,求拓扑序列,求关键路径,PROC critical_path(Var dig:adjlisttp); crt_adjlist(dig); if not toporder(dig) then writeln(Ha

16、s a cycle) else vl1.n:=ven; 初始化最迟发生时间 while Not empty(top2) Do j:=pop(top2); k:= firstadj(dig,j); while k0 do if vlk-dut(); k:=nextadj(dig,j,k); ,关键工程,在大型工程的施工前，我们把整个工程划分为若干个子工程，并把这些子工程编号为1、2、N；这样划分之后，子工程之间就会有一些依赖关系，即一些子工程必须在某些子工程完成之后才能施工。由于子工程之间有相互依赖关系，因此有两个任务需要我们去完成：首先，我们需要计算整个工程最少的完成时间；同时，由于一些不可预

17、测的客观因素会使某些子工程延期，因此我们必须知道哪些子工程的延期会影响整个工程的延期，我们把有这种特征的子工程称为关键子工程，因此第二个任务就是找出所有的关键子工程，以便集中精力管理好这些子工程，尽量避免这些子工程延期，达到用最快的速度完成整个工程。为了便于编程，现在我们假设： （1）根据预算，每一个子工程都有一个完成时间。 （2）子工程之间的依赖关系是：部分子工程必须在一些子工程完成之后才开工。 （3）只要满足子工程间的依赖关系，在任何时刻可以有任何多个子工程同时在施工，也既同时施工的子工程个数不受限制。 （4）整个工程的完成是指：所有子工程的完成。,示例1,约束条件,输入：第1行为N，N是

18、子工程的总个数，N200。 第2行为N个正整数，分别代表子工程1、2、N的完成时间。 第3行到N+2行，每行有N-1个0或1。其中的第I+2行的这些0，1，分别表示“子工程I”与子工程1、2、I-1、I+1、N的依赖关系，（I=1、2、N）。每行数据之间均用空格分开。 输出：如子工程划分不合理，则输出-1；如子工程划分合理，则用两行输出：第1行为整个工程最少的完成时间。第2行为按由小到大顺序输出所有关键子工程的编号。,分析,（1）根据的得到邻接矩阵对子工程进行拓扑排序。如果该图能够进行拓扑排序的话，证明有解，反之则无解。 （2）根据的得到拓扑序列进行动态规划求解，得到工程所需的完成时间。动态规划方程：FI=MAXFJ+COSTI AI，J 0，第I子工程必须在子工程J之后完工 FI表示完成子工程I所需的最早时间，COSTI表示完成子工程I所需的时间。 （3）根据的得到的F序列和拓扑序列，查找关键工程。 如果FI=FJ-COSTJ（AJ，I 0）的话且第I个子工程为关键工程，那么第J个子工程也是关键工程。初始时，最后完成的一个或多个工程为关键工程。 这一道试题的时间复杂度大致为O（N2）。,