数据结构算法集锦.txt

数据结构算法集锦：包括大量常用算法

                【数据结构】算法集锦 

                        一、数论算法
                        1．求两数的最大公约数
                        function  gcd(a,b:integer):integer;
                         begin 
                           if b=0 then gcd:=a
                             else gcd:=gcd (b,a mod b);
                         end ;
                        2．求两数的最小公倍数
                        function  lcm(a,b:integer):integer;
                         begin
                           if a<b then swap(a,b);
                           lcm:=a;
                           while lcm mod b>0 do inc(lcm,a);
                         end;
                        3．素数的求法
                        A.小范围内判断一个数是否为质数：
                         function prime (n: integer): Boolean;
                           var I: integer;
                           begin
                             for I:=2 to trunc(sqrt(n)) do
                               if n mod I=0 then begin 
                          prime:=false; exit;
                        end;
                             prime:=true;
                           end;
                        B.判断longint范围内的数是否为素数（包含求50000以内的素数表）：
                           procedure getprime;
                             var 
                               i,j:longint;
                               p:array[1..50000] of boolean;
                              begin
                                fillchar(p,sizeof(p),true);
                         p[1]:=false;
                         i:=2;
                         while i<50000 do begin
                           if p[i] then begin
                             j:=i*2;
                             while j<50000 do begin
                               p[j]:=false;
                               inc(j,i);
                             end;
                            end;
                            inc(i);
                          end;
                          l:=0;
                          for i:=1 to 50000 do
                            if p[i] then begin
                              inc(l);pr[l]:=i;
                           end;
                        end;{getprime}
                           
                            function prime(x:longint):integer;
                              var i:integer;
                              begin
                                prime:=false;
                         for i:=1 to l do
                           if pr[i]>=x then break
                             else if x mod pr[i]=0 then exit;
                         prime:=true;
                              end;{prime}

                        二、图论算法
                        1．最小生成树
                         A.Prim算法：
                            procedure prim(v0:integer);
                              var
                                lowcost,closest:array[1..maxn] of integer;
                         i,j,k,min:integer;
                              begin
                                for i:=1 to n do begin
                           lowcost[i]:=cost[v0,i];
                           closest[i]:=v0;
                          end;
                         for i:=1 to n-1 do begin
                           {寻找离生成树最近的未加入顶点k}
                           min:=maxlongint;
                           for j:=1 to n do
                             if (lowcost[j]<min) and (lowcost[j]<>0) then begin
                               min:=lowcost[j];
                               k:=j;
                             end;
                           lowcost[k]:=0; {将顶点k加入生成树}
                              {生成树中增加一条新的边k到closest[k]}
                           {修正各点的lowcost和closest值}
                           for j:=1 to n do
                             if  cost[k,j]<lwocost[j] then begin
                               lowcost[j]:=cost[k,j];
                               closest[j]:=k;
                             end;
                           end;
                        end;{prim}
                        B.Kruskal算法：(贪心)
                         按权值递增顺序删去图中的边，若不形成回路则将此边加入最小生成树。
                        function find(v:integer):integer; {返回顶点v所在的集合}
                         var i:integer;
                         begin
                           i:=1;
                           while (i<=n) and (not v in vset[i]) do inc(i);
                           if i<=n then find:=i else find:=0;
                         end;
                        procedure kruskal;
                         var
                           tot,i,j:integer;
                         begin
                           for i:=1 to n do 
vset[i]:=[i];{初始化定义n个集合，第I个集合包含一个元素I}
                        p:=n-1; q:=1; tot:=0; {p为尚待加入的边数，q为边集指针}
                        sort;
                        {对所有边按权值递增排序，存于e[I]中，e[I].v1与e[I].v2为边I所连接的两个顶点的序号，e[I].len为第I条边的长度}
                           while p>0 do begin
                             i:=find(e[q].v1);j:=find(e[q].v2);
                             if i<>j then begin
                               inc(tot,e[q].len);
                               vset[i]:=vset[i]+vset[j];vset[j]:=[];
                               dec(p);
                             end;
                             inc(q);
                           end;
                           writeln(tot);
                         end;
                        2.最短路径
                         A.标号法求解单源点最短路径：
                           var
                             a:array[1..maxn,1..maxn] of integer;
                             b:array[1..maxn] of integer; {b[i]指顶点i到源点的最短路径}
                             mark:array[1..maxn] of boolean;
                           procedure bhf;
                             var
                               best,best_j:integer;
                             begin
                               fillchar(mark,sizeof(mark),false);
                            mark[1]:=true; b[1]:=0;{1为源点}
                            repeat
                              best:=0;
                                for i:=1 to n do
                                 If mark[i] then {对每一个已计算出最短路径的点}
                                  for j:=1 to n do
                                    if (not mark[j]) and (a[i,j]>0) then 
                                   if (best=0) or (b[i]+a[i,j]<best) then begin
                                     best:=b[i]+a[i,j];  best_j:=j;
                                  end;
                               if best>0 then begin
                                 b[best_j]:=best；mark[best_j]:=true;
                               end;
                             until best=0;
                             end;{bhf}
                          B.Floyed算法求解所有顶点对之间的最短路径：
                             procedure floyed;
                               begin
                        for I:=1 to n do
                         for j:=1 to n do
                         if a[I,j]>0 then p[I,j]:=I else p[I,j]:=0; 
                        {p[I,j]表示I到j的最短路径上j的前驱结点}
                          for k:=1 to n do {枚举中间结点}
                            for i:=1 to n do
                              for j:=1 to n do
                                if a[i,k]+a[j,k]<a[i,j] then begin
                               a[i,j]:=a[i,k]+a[k,j];
                                     p[I,j]:=p[k,j];
                             end;
                              end;
                        C. Dijkstra 算法：
                        var
                             a:array[1..maxn,1..maxn] of integer;
                             b,pre:array[1..maxn] of integer; 
                        {pre[i]指最短路径上I的前驱结点}
                             mark:array[1..maxn] of boolean;
                        procedure dijkstra(v0:integer);
                         begin
                           fillchar(mark,sizeof(mark),false);
                           for i:=1 to n do begin
                             d[i]:=a[v0,i];
                             if d[i]<>0 then pre[i]:=v0 else pre[i]:=0;
                           end;
                           mark[v0]:=true;
                           repeat   {每循环一次加入一个离1集合最近的结点并调整其他结点的参数}
                             min:=maxint; u:=0; {u记录离1集合最近的结点}
                             for i:=1 to n do
                               if (not mark[i]) and (d[i]<min) then begin
                                 u:=i; min:=d[i];
                             end;
                             if u<>0 then begin
                               mark[u]:=true; 
                               for i:=1 to n do
                                if (not mark[i]) and (a[u,i]+d[u]<d[i]) then 
                        begin
                                  d[i]:=a[u,i]+d[u];
                                  pre[i]:=u;
                               end;
                             end;
                           until u=0;
                         end;
                        3.计算图的传递闭包
                        Procedure Longlink;
                         Var
                        T:array[1..maxn,1..maxn] of boolean;
                         Begin
                        Fillchar(t,sizeof(t),false);
                        For k:=1 to n do
                         For I:=1 to n do
                           For j:=1 to n do T[I,j]:=t[I,j] or (t[I,k] and 
                        t[k,j]);
                         End;

                        4．无向图的连通分量
                        A.深度优先
                         procedure dfs ( now,color: integer);
                            begin
                              for i:=1 to n do
                               if a[now,i] and c[i]=0 then begin {对结点I染色}
                                 c[i]:=color;
                                 dfs(I,color);
                               end;
                        end;
                        B 宽度优先（种子染色法）

                        5．关键路径
                        几个定义： 顶点1为源点，n为汇点。
                        a. 顶点事件最早发生时间Ve[j], Ve [j] = max{ Ve [j] + w[I,j] },其中Ve 
                        (1) = 0;
                        b. 顶点事件最晚发生时间 Vl[j], Vl [j] = min{ Vl[j] – w[I,j] },其中 
                        Vl(n) = Ve(n);
                        c. 边活动最早开始时间 Ee[I], 若边I由<j,k>表示，则Ee[I] = Ve[j];
                        d. 边活动最晚开始时间 El[I], 若边I由<j,k>表示，则El[I] = Vl[k] – w[j,k];
                        若 Ee[j] = El[j] ，则活动j为关键活动，由关键活动组成的路径为关键路径。
                        求解方法：
                        a. 从源点起topsort,判断是否有回路并计算Ve;
                        b. 从汇点起topsort,求Vl;
                        c. 算Ee 和 El;

                        6．拓扑排序
                        找入度为0的点，删去与其相连的所有边，不断重复这一过程。
                        例  寻找一数列，其中任意连续p项之和为正，任意q 项之和为负，若不存在则输出NO.

                        7.回路问题
                        Euler回路(DFS)
                        定义：经过图的每条边仅一次的回路。（充要条件：图连同且无奇点）
                        Hamilton回路
                        定义：经过图的每个顶点仅一次的回路。
                        一笔画
                        充要条件：图连通且奇点个数为0个或2个。
                        9．判断图中是否有负权回路 Bellman-ford 算法
                         x[I],y[I],t[I]分别表示第I条边的起点，终点和权。共n个结点和m条边。
                          procedure bellman-ford
                           begin
                        for I:=0 to n-1 do d[I]:=+infinitive;
                        d[0]:=0;
                        for I:=1 to n-1 do
                         for j:=1 to m do {枚举每一条边}
                           if d[x[j]]+t[j]<d[y[j]] then d[y[j]]:=d[x[j]]+t[j];
                        for I:=1 to m do
                         if d[x[j]]+t[j]<d[y[j]] then return false else return 
                        true;
                           end;
                        10．第n最短路径问题
                        *第二最短路径：每举最短路径上的每条边，每次删除一条，然后求新图的最短路径，取这些路径中最短的一条即为第二最短路径。
                        *同理，第n最短路径可在求解第n-1最短路径的基础上求解。
                        [color=#0000FF]三、背包问题[/color]
                        *部分背包问题可有贪心法求解：计算Pi/Wi
                          数据结构：
                            w[i]:第i个背包的重量；
                            p[i]:第i个背包的价值；
                        1．0-1背包： 每个背包只能使用一次或有限次(可转化为一次)：
                        A.求最多可放入的重量。
                        NOIP2001 装箱问题 
                           有一个箱子容量为v(正整数，o≤v≤20000)，同时有n个物品(o≤n≤30)，每个物品有一个体积 
                        (正整数)。要求从 n 个物品中，任取若千个装入箱内，使箱子的剩余空间为最小。
                        l 搜索方法
                           procedure search(k,v:integer); {搜索第k个物品，剩余空间为v}
                           var i,j:integer;
                           begin
                             if v<best then best:=v;
                             if v-(s[n]-s[k-1])>=best then exit; 
{s[n]为前n个物品的重量和}
                             if k<=n then begin
                               if v>w[k] then search(k+1,v-w[k]);
                               search(k+1,v);
                             end;
                           end;
                        l DP
                        F[I,j]为前i个物品中选择若干个放入使其体积正好为j的标志，为布尔型。
                        实现:将最优化问题转化为判定性问题
                        f [I, j] = f [ i-1, j-w[i] ] (w[I]<=j<=v)