数据结构核心知识

数据结构 朱全民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个字符和主串中的第i个字符对齐,此时模式中的头K-1个字符的子串肯定与主串中第i个字符之前的K-1个子串相等.怎样求KKMP示例求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,则说明在主串中第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:=nextkendPDNA病毒 科学家最近发现了某种病毒，通过对该病毒的分析，它的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)它左右子树分别为二叉排序树。查找 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:bitree;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.QlQSlSPPrF,令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(j=m)and not finish do if(jrj+1.key)then j:=j+1;If x=rj.key then finish:=true Else ri:=rj;i:=j;j:=2*I ri:=tendPPROC 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）,若经过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存储被标号的顶点 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 endPCar的旅行路线 又到暑假了，住在城市A的 Car想和朋友一起去城市B旅游。她知道每个城市都有四个飞机场，分别位于一个矩形的四个顶点上，同一个城市中两个机场之间有一条笔直的高速铁路，第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，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，按拓扑有序求其余各定点最早发生时间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);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(Has a cycle)else vl1.n:=ven;初始化最迟发生时间 while Not empty(top2)Do j:=pop(top2);k:=firstadj(dig,j);while k0 do if vlk-dut()vlj then vlj:=vlk-dut();k:=nextadj(dig,j,k);关键工程在大型工程的施工前，我们把整个工程划分为若干个子工程，并把这些子工程编号为1、2、N；这样划分之后，子工程之间就会有一些依赖关系，即一些子工程必须在某些子工程完成之后才能施工。由于子工程之间有相互依赖关系，因此有两个任务需要我们去完成：首先，我们需要计算整个工程最少的完成时间；同时，由于一些不可预测的客观因素会使某些子工程延期，因此我们必须知道哪些子工程的延期会影响整个工程的延期，我们把有这种特征的子工程称为关键子工程，因此第二个任务就是找出所有的关键子工程，以便集中精力管理好这些子工程，尽量避免这些子工程延期，达到用最快的速度完成整个工程。为了便于编程，现在我们假设：（1）根据预算，每一个子工程都有一个完成时间。（2）子工程之间的依赖关系是：部分子工程必须在一些子工程完成之后才开工。（3）只要满足子工程间的依赖关系，在任何时刻可以有任何多个子工程同时在施工，也既同时施工的子工程个数不受限制。（4）整个工程的完成是指：所有子工程的完成。示例1序号完成时间子工程1子工程2子工程3子工程4子工程5子工程150000子工程240000子工程3120000子工程471100子工程521111约束条件 输入：第1行为N，N是子工程的总个数，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）。