栈和队列、最短路

栈和队列,队列六种基本操作：1队列初始化voidiniqueue(int*q)将队列Q设置成一个空队列。2入队voidenqueue(int*q,x)将元素X插入到队尾中，也称“进队”，“插入”。3出队intdlqueue(int*q)将队列Q的队头元素删除并返回。4取队头元素intgethead(int*q)得到队列Q的队头元素之值。5判队空intisempty(int*q)判断队列Q是否为空，若为空返回1，否则返回0。6.判队满intisfull(int*q)判断队列Q是否为满，若为满返回1，否则返回0。,3,frontrear,rear,front,(c)a出队后,(d)b,c出队，队空,front,frontrear,(a)队列初始为空,rear,(b)a,b,c入队后,顺序队列出入队列示意图,front指向表头第一个有效位置，rear指向表尾第一个空位置,当头、尾指针相等时队列为空：front=rear时，队列为空，如上图（a）和（d）。,(1)队列初始化voidiniqueue(int*q)front=rear=0;,rear,front,0123,(2)进队voidenqueue(int*q,intx)if(isfull(q)=1)printf(”overflow”);elseqrear=x;rear=(rear+1)%maxsize;,frontrear,0123,frontrear,0123,(3)出队intdlqueue(int*q)if(isempty(q)=1)printf(”empty”);return0;elseintx=qfront;front=(front+1)%maxsize;returnx;,frontrear,0123,frontrear,0123,(4)取队头元素intgethead(int*q)if(isempty(q)=1)printf(”empty”);returnNULL;elsereturnqfront;,frontrear,0123,(5)判队列空否intisempty(int*q)if(rear=front)reurn1;elsereturn0;(6)判队列满否intisfull(int*q)if(rear+1)%maxsize=front)return1;elsereturn0;,frontrear,0123,front,rear,0123,rear,front,0123,rearfront,0123,空,空,满,非空非满,队列练习,HDU1276,栈六种基本操作：1栈初始化voidinistack(int*s)将栈S设置成一个空栈。2入栈voidpush(int*s,x)将元素X插入到栈S的栈顶3出栈inttop(int*s)将栈S的栈顶元素删除并返回。4取栈顶元素intgettop(int*s)得到栈S的栈顶元素之值。5判栈空intisempty(int*s)判断栈S是否为空，若为空返回1，否则返回0。6.判栈满intisfull(int*s)判断栈S是否为满，若为满返回1，否则返回0。,顺序栈示意图,p指向栈顶元素,(1)栈初始化voidinistack(int*s)p=-1;,(2)进栈voidpush(int*s,intx)if(isfull(s)=1)printf(”overflow”);elsep+;sp=x;,(3)出栈intpop(int*s)if(isempty(s)=1)printf(”empty”);returnNULL;elseintx=sp;p-;returnx;,(4)取栈顶元素intgettop(int*s)if(isempty(s)=1)printf(”empty”);returnNULL;elsereturnsp;,(5)判队列空否intisempty(int*s)if(p=-1)reurn1;elsereturn0;(6)判队列满否intisfull(int*s)if(p+1maxsize-1)reurn1;elsereturn0;,迪杰斯特拉Dijkstra算法,算法原理：dis(v0,v)=dis(v0,u)+edge(u,v)1、把顶点集合V分成两组：(1)S：已求出最短路径(长度)的顶点集合(初始时只含有源点V0)(2)T=V-S：尚未确定最短路径(长度)的顶点集合2、将T中顶点按距离递增的次序加入到S中，保证：(1)从源点V0到S中各顶点的长度都不大于从V0到T中任何顶点的路径长度(2)每个顶点对应一个距离值说明：(1)V为顶点全集(2)V0为源点(3)S为已求出V0到其最短路径的顶点集合(4)T为尚未求出最短路径的顶点集合,迪杰斯特拉Dijkstra算法,算法流程：已知G=V,E，据此建立邻接矩阵f初始时令S=V0，T=V-S=其余顶点，数组dis保存各顶点最短路径长度，其中disV0=0；若存在，disi=弧上的权值；若不存在，disi=从T中选取dis值最小的顶点k，加入到S中：S=SUk，T=T-k对其余T中顶点j的距离值进行修改：若图中有边且dis(j)dis(k)+f(k,j)，则dis(j)=dis(k)+f(k,j)重复上述步骤2、3，直到S中包含所有顶点，即T为空,迪杰斯特拉Dijkstra算法,memset(s,0,sizeof(s);sv0=1;disv0=0;for(i=0;idis(k)+f(k,j)，则dis(j)=dis(k)+f(k,j)重复上述步骤2、3，直到S中包含所有顶点，即T为空,图中有负权边，情况如何？,弗洛伊德floyd算法,for(k=1;kfik+fkj)if(fijfik+fkj),图中有负权回路，情况如何？,时间复杂度T=O(n3),贝尔曼-福特Bellman-Ford算法,算法描述初始化：将除源点s外的所有顶点的最短距离估计为disv=+，diss=0;迭代求解：反复对边集E中的每条边进行松弛操作，使得顶点集V中的每个顶点v的最短距离估计值逐步逼近其最短距离真实值；（运行|v|-1次）检验负权回路：判断边集E中的每一条边的两个端点是否收敛。如果存在未收敛的顶点，则算法返回0，表明问题无解；否则算法返回1，并且从源点s可达的顶点v的最短距离保存在disv中。,贝尔曼-福特Bellman-Ford算法,证明任意一条最短路径既不能包含负权回路，也不会包含正权回路，因此它最多包含|v|-1条边。从源点s可达的所有顶点如果存在最短路径，则这些最短路径构成一个以s为根的最短路径树。算法的迭代松弛操作，实际上就是按每个点实际的最短路径虽然我们还不知道，但它一定存在的层次，逐层生成这棵最短路径树的过程。我们在第v次更新中若没有新的松弛，则输出结果1，若依然存在松弛，则输出0表示无解。,贝尔曼-福特Bellman-Ford算法,intBellman-Ford(G,f,s)foreachvertexvV(G)disv=+;diss=0;for(inti=1;idisu+f(u,v)disv=disu+f(u,v);foreachedge(u,v)E(G)if(dvdu+f(u,v)return0;return1;,时间复杂度T=O(V+V*E+E)=O(VE),贝尔曼-福特Bellman-Ford算法,intBellman_Ford(G,f,s)for(inti=1;idistedgei.u+edgei.weight)return0;return1;,structEdgeintu,v;/起点，终点intweight;/边的权值Edge;Edgeedgemaxnum;/保存边的值intdistmaxnum;/结点到源点最小距离intnodenum,edgenum,source;/结点数，边数，源点,#include#definemaxnum=100#definemaxint=99999structEdgeintu,v;/起点，终点intweight;/边的权值Edge;Edgeedgemaxnum;/保存边的值intdistmaxnum;/结点到源点最小距离intnodenum,edgenum,source;/结点数，边数，源点/初始化图voidinit()/输入结点数，边数，源点scanf(%d%d%d,SPFA算法,建立一个队列，初始时队列里只有起始点，再建立一个数组记录源点到所有点的最短路径(数组初始值要赋为极大值，源点到自身的路径长度赋为0)。然后执行松弛操作：从队列弹出点u，用u去刷新u可达的所有点如v的最短路，如果刷新成功且v不在队列中则点v入队。重复执行直到队列为空。,！算法运行过程中对每一个点入队次数进行统计，超过N次的，证明图中有负权环路-正常一条无环路径最长N-1条边。,SPFA算法,push(q,s);visiteds=1;Diss=0;while(0=isempty(q)/队列非空u=dlqueue(q);visitedu=0;for(i=pu;i;i=ei.next)/刷新由u出发的边，编号为iv=ei.to;/第i条边另一端点是vif(DisvDisu+ei.w)Disv=Disu+ei.w;if(visitedv=0)push(q,v);vis