栈和队列、最短路

栈和队列队列六种基本操作：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。3abcabcfrontrearrearfront(c)a出队后(d)b,c出队，队空frontabcfrontrear(a)队列初始为空rear(b)a,b,c入队后顺序队列出入队列示意图front指向表头第一个有效位置，rear指向表尾第一个空位置当头、尾指针相等时队列为空：front==rear时，队列为空，如上图（a）和（d）。(1)队列初始化voidiniqueue(int*q){front=rear=0;}rearfront0123(2)进队voidenqueue(int*q,intx){if(isfull(q)==1)printf(”overflow”);else{q[rear]=x;rear=(rear+1)%maxsize;}}abcfrontrear0123abfrontrear0123(3)出队intdlqueue(int*q){if(isempty(q)==1){printf(”empty”);return0;}else{intx=q[front];front=(front+1)%maxsize;returnx;}}abcfrontrear0123abcfrontrear0123(4)取队头元素intgethead(int*q){if((isempty(q)==1){printf(”empty”);returnNULL;}elsereturnq[front];}abcfrontrear0123(5)判队列空否intisempty(int*q){if(rear==front)reurn1;elsereturn0;}(6)判队列满否intisfull(int*q){if((rear+1)%maxsize==front)return1;elsereturn0;}abcfrontrear0123frontrear0123abcrearfront0123abcdrearfront0123空空满非空非满队列练习•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。顺序栈示意图a1a2a3sa4(栈底)(栈顶)99...3210pp指向栈顶元素(1)栈初始化voidinistack(int*s){p=-1;}s(栈底)(栈顶)99...3210-1p(2)进栈voidpush(int*s,intx){if((isfull(s)==1)printf(”overflow”);else{p++;s[p]=x;}}a1a2a3sa4(栈底)(栈顶)99...3210-1p(3)出栈intpop(int*s){if((isempty(s)==1){printf(”empty”);returnNULL;}else{intx=s[p];p--;returnx;}}a1a2a3sa4(栈底)(栈顶)99...3210-1p(4)取栈顶元素intgettop(int*s){if((isempty(s)==1){printf(”empty”);returnNULL;}elsereturns[p];}a1a2a3sa4(栈底)(栈顶)99...3210-1p(5)判队列空否intisempty(int*s){if(p==-1)reurn1;elsereturn0;}(6)判队列满否intisfull(int*s){if(p+1maxsize-1)reurn1;elsereturn0;}a1a2a3sa4(栈底)(栈顶)99...3210-1p迪杰斯特拉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}，据此建立邻接矩阵f1.初始时令S={V0}，T=V-S={其余顶点}，数组dis保存各顶点最短路径长度，其中dis[V0]=0；若存在V0,Vi，dis[i]=V0,Vi弧上的权值；若不存在V0,Vi，dis[i]=∞2.从T中选取dis值最小的顶点k，加入到S中：S=SUk，T=T-k3.对其余T中顶点j的距离值进行修改：若图中有边k,j且dis(j)dis(k)+f(k,j)，则dis(j)=dis(k)+f(k,j)4.重复上述步骤2、3，直到S中包含所有顶点，即T为空迪杰斯特拉Dijkstra算法1.memset(s,0,sizeof(s));2.s[v0]=1;3.dis[v0]=0;4.for(i=0;in;i++)5.if(f[v0][i]!=-1)6.dis[i]=f[v0][i];7.else8.dis[i]=MAX;9.for(i=0;in-1;i++)10.{11.min=MAX;12.k=-1;13.for(j=0;jn;j++)14.if(s[j]==0&&dis[j]min)15.{16.min=dis[j];17.k=j;18.}19.s[k]=1;20.for(j=0;jn;j++)21.if(s[j]==0&&f[k][j]!=-1&&dis[j]dis[k]+f[k][j])22.dis[j]=dis[k]+f[k][j];23.}迪杰斯特拉Dijkstra算法时间复杂度T=O(n+n*(n+n))=O(n2)迪杰斯特拉Dijkstra算法已知G={V,E}，据此建立邻接矩阵f1.初始时令S={V0}，T=V-S={其余顶点}，数组dis保存各顶点最短路径长度，其中dis[V0]=0；若存在V0,Vi，dis[i]=V0,Vi弧上的权值；若不存在V0,Vi，dis[i]=∞2.从T中选取dis值最小的顶点k，加入到S中：S=SUk，T=T-k3.对其余T中顶点j的距离值进行修改：若图中有边k,j且dis(j)dis(k)+f(k,j)，则dis(j)=dis(k)+f(k,j)4.重复上述步骤2、3，直到S中包含所有顶点，即T为空图中有负权边，情况如何？弗洛伊德floyd算法for(k=1;k=n;k++)for(i=1;i=n;i++)for(j=1;j=n;j++)if(f[i][j]f[i][k]+f[k][j])if(f[i][j]f[i][k]+f[k][j])图中有负权回路，情况如何？时间复杂度T=O(n3)贝尔曼-福特Bellman-Ford算法算法描述1.初始化：将除源点s外的所有顶点的最短距离估计为dis[v]=+∞，dis[s]=0;2.迭代求解：反复对边集E中的每条边进行松弛操作，使得顶点集V中的每个顶点v的最短距离估计值逐步逼近其最短距离真实值；（运行|v|-1次）3.检验负权回路：判断边集E中的每一条边的两个端点是否收敛。如果存在未收敛的顶点，则算法返回0，表明问题无解；否则算法返回1，并且从源点s可达的顶点v的最短距离保存在dis[v]中。贝尔曼-福特Bellman-Ford算法证明1.任意一条最短路径既不能包含负权回路，也不会包含正权回路，因此它最多包含|v|-1条边。2.从源点s可达的所有顶点如果存在最短路径，则这些最短路径构成一个以s为根的最短路径树。算法的迭代松弛操作，实际上就是按每个点实际的最短路径[虽然我们还不知道，但它一定存在]的层次，逐层生成这棵最短路径树的过程。3.我们在第[v]次更新中若没有新的松弛，则输出结果1，若依然存在松弛，则输出0表示无解。贝尔曼-福特Bellman-Ford算法intBellman-Ford(G,f,s){foreachvertexv∈V(G)dis[v]=+∞;dis[s]=0;for(inti=1;i|v|;i++)foreachedge(u,v)∈E(G)if(dis[v]dis[u]+f(u,v))dis[v]=dis[u]+f(u,v);foreachedge(u,v)∈E(G)if(d[v]d[u]+f(u,v))return0;return1;}时间复杂度T=O(V+V*E+E)=O(VE)贝尔曼-福特Bellman-Ford算法1.intBellman_Ford(G,f,s)2.{3.for(inti=1;i=nodenum;++i)4.dist[i]=maxint;5.dist[source]=0;6.for(inti=1;i=nodenum-1;++i)7.for(intj=1;j=edgenum;++j)8.relax(edge[j].u,edge[j].v,edge[j].weight);9.for(inti=1;i=edgenum;++i)10.if(dist[edge[i].v]dist[edge[i].u]+edge[i].weight)11.return0;12.return1;13.}structEdge{intu,v;//起点，终点intweight;//边的权值}Edge;Edgeedge[maxnum];//保存边的值intdist[maxnum];//结点到源点最小距离intnodenum,edgenum,source;//结点数，边数，源点#includestdio.h#definemaxnum=100#definemaxint=99999structEdge{intu,v;//起点，终点intweight;//边的权值}Edge;Edgeedge[maxnum];//保存边的值intdist[maxnum];//结点到源点最小距离intnodenum,edgenum,source;//结点数，边数，源点//初始化图voidinit(){//输入结点数，边数，源点scanf(%d%d%d,&nodenum,&edgenum,&source);for(inti=1;i=nodenum;++i)dist[i]=maxint;dist[source]=0;for(inti=1;i=edgenum;++i){scanf(%d%d%d,&(edge[i].u),&(edge[i].v),&(edge[i].weight);if(edge[i].u==source)//注意这里设置初始情况dist[edge[i].v]=edge[i].weight;}}//松弛计算voidrelax(intu,intv,intweight){if(dist[v]dist[u]+weight)dist[v]=dist[u]+weight;}intBellman_Ford(){for(inti=