數據結構算法集錦

　　一數論算法

　　求兩數的最大公約數

　　function gcd(ab:integer):integer;

　　begin

　　if b= then gcd:=a

　　else gcd:=gcd (ba mod b);

　　end ;

　　求兩數的最小公倍數

　　function lcm(ab:integer):integer;

　　begin

　　if a

　　lcm:=a;

　　while lcm mod b> do inc(lcma);

　　end;

　　素數的求法

　　A小范圍內判斷一個數是否為質數

　　function prime (n: integer): Boolean;

　　var I: integer;

　　begin

　　for I:= to trunc(sqrt(n)) do

　　if n mod I= then begin

　　prime:=false; exit;

　　end;

　　prime:=true;

　　end;

　　B判斷longint范圍內的數是否為素數(包含求以內的素數表)

　　procedure getprime;

　　var

　　ij:longint;

　　p:array[] of boolean;

　　begin

　　fillchar(psizeof(p)true);

　　p[]:=false;

　　i:=;

　　while i< do begin

　　if p[i] then begin

　　j:=i*;

　　while j< do begin

　　p[j]:=false;

　　inc(ji);

　　end;

　　end;

　　inc(i);

　　end;

　　l:=;

　　for i:= to 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:= to l do

　　if pr[i]>=x then break

　　else if x mod pr[i]= then exit;

　　prime:=true;

　　end;{prime}

　　二圖論算法

　　最小生成樹

　　APrim算法

　　procedure prim(v:integer);

　　var

　　lowcostclosest:array[maxn] of integer;

　　ijkmin:integer;

　　begin

　　for i:= to n do begin

　　lowcost[i]:=cost[vi];

　　closest[i]:=v;

　　end;

　　for i:= to n do begin

　　{尋找離生成樹最近的未加入頂點k}

　　min:=maxlongint;

　　for j:= to n do

　　if (lowcost[j]) then begin

　　min:=lowcost[j];

　　k:=j;

　　end;

　　lowcost[k]:=; {將頂點k加入生成樹}

　　{生成樹中增加一條新的邊k到closest[k]}

　　{修正各點的lowcost和closest值}

　　for j:= to n do

　　if cost[kj]

　　lowcost[j]:=cost[kj];

　　closest[j]:=k;

　　end;

　　end;

　　end;{prim}

　　BKruskal算法(貪心)

　　按權值遞增順序刪去圖中的邊若不形成回路則將此邊加入最小生成樹

　　function find(v:integer):integer; {返回頂點v所在的集合}

　　var i:integer;

　　begin

　　i:=;

　　while (i<=n) and (not v in vset[i]) do inc(i);

　　if i<=n then find:=i else find:=;

　　end;

　　procedure kruskal;

　　var

　　totij:integer;

　　begin

　　for i:= to n do vset[i]:=[i];{初始化定義n個集合第I個集合包含一個元素I}

　　p:=n; q:=; tot:=; {p為尚待加入的邊數q為邊集指針}

　　sort;

　　{對所有邊按權值遞增排序存於e[I]中e[I]v與e[I]v為邊I所連接的兩個頂點的序號e[I]len為第I條邊的長度}

　　while p> do begin

　　i:=find(e[q]v);j:=find(e[q]v);

　　if i<>j then begin

　　inc(tote[q]len);

　　vset[i]:=vset[i]+vset[j];vset[j]:=[];

　　dec(p);

　　end;

　　inc(q);

　　end;

　　writeln(tot);

　　end;

　　最短路徑

　　A標號法求解單源點最短路徑

　　var

　　a:array[maxnmaxn] of integer;

　　b:array[maxn] of integer; {b[i]指頂點i到源點的最短路徑}

　　mark:array[maxn] of boolean;

　　procedure bhf;

　　var

　　bestbest_j:integer;

　　begin

　　fillchar(marksizeof(mark)false);

　　mark[]:=true; b[]:=;{為源點}

　　repeat

　　best:=;

　　for i:= to n do

　　If mark[i] then {對每一個已計算出最短路徑的點}

　　for j:= to n do

　　if (not mark[j]) and (a[ij]>) then

　　if (best=) or (b[i]+a[ij]

　　best:=b[i]+a[ij]; best_j:=j;

　　end;

　　if best> then begin

　　b[best_j]:=best;mark[best_j]:=true;

　　end;

　　until best=;

　　end;{bhf}

　　BFloyed算法求解所有頂點對之間的最短路徑

　　procedure floyed;

　　begin

　　for I:= to n do

　　for j:= to n do

　　if a[Ij]> then p[Ij]:=I else p[Ij]:=; {p[Ij]表示I到j的最短路徑上j的前驅結點}

　　for k:= to n do {枚舉中間結點}

　　for i:= to n do

　　for j:= to n do

　　if a[ik]+a[jk]

　　a[ij]:=a[ik]+a[kj];

　　p[Ij]:=p[kj];

　　end;

　　end;

　　C Dijkstra 算法

　　var

　　a:array[maxnmaxn] of integer;

　　bpre:array[maxn] of integer; {pre[i]指最短路徑上I的前驅結點}

　　mark:array[maxn] of boolean;

　　procedure dijkstra(v:integer);

　　begin

　　fillchar(marksizeof(mark)false);

　　for i:= to n do begin

　　d[i]:=a[vi];

　　if d[i]<> then pre[i]:=v else pre[i]:=;

　　end;

　　mark[v]:=true;

　　repeat {每循環一次加入一個離集合最近的結點並調整其他結點的參數}

　　min:=maxint; u:=; {u記錄離集合最近的結點}

　　for i:= to n do

　　if (not mark[i]) and (d[i]

　　u:=i; min:=d[i];

　　end;

　　if u<> then begin

　　mark[u]:=true;

　　for i:= to n do

　　if (not mark[i]) and (a[ui]+d[u]

　　d[i]:=a[ui]+d[u];

　　pre[i]:=u;

　　end;

　　end;

　　until u=;

　　end;

　　計算圖的傳遞閉包

　　Procedure Longlink;

　　Var

　　T:array[maxnmaxn] of boolean;

　　Begin

　　Fillchar(tsizeof(t)false);

　　For k:= to n do

　　For I:= to n do

　　For j:= to n do T[Ij]:=t[Ij] or (t[Ik] and t[kj]);

　　End;

　　無向圖的連通分量

　　A深度優先

　　procedure dfs ( nowcolor: integer);

　　begin

　　for i:= to n do

　　if a[nowi] and c[i]= then begin {對結點I染色}

　　c[i]:=color;

　　dfs(Icolor);

　　end;

　　end;

　　B 寬度優先(種子染色法)

　　關鍵路徑

　　幾個定義 頂點為源點n為匯點

　　a 頂點事件最早發生時間Ve[j] Ve [j] = max{ Ve [j] + w[Ij] }其中Ve () = ;

　　b 頂點事件最晚發生時間 Vl[j] Vl [j] = min{ Vl[j] – w[Ij] }其中 Vl(n) = Ve(n);

　　c 邊活動最早開始時間 Ee[I] 若邊I由表示則Ee[I] = Ve[j];

　　d 邊活動最晚開始時間 El[I] 若邊I由表示則El[I] = Vl[k] – w[jk];

　　若 Ee[j] = El[j] 則活動j為關鍵活動由關鍵活動組成的路徑為關鍵路徑

　　求解方法

　　a 從源點起topsort判斷是否有回路並計算Ve;

　　b 從匯點起topsort求Vl;

　　c 算Ee 和 El;

　　拓撲排序

　　找入度為的點刪去與其相連的所有邊不斷重復這一過程

　　例 尋找一數列其中任意連續p項之和為正任意q 項之和為負若不存在則輸出NO

　　回路問題

　　Euler回路(DFS)

　　定義經過圖的每條邊僅一次的回路(充要條件圖連同且無奇點)

　　Hamilton回路

　　定義經過圖的每個頂點僅一次的回路

　　一筆畫

　　充要條件圖連通且奇點個數為個或個

　　判斷圖中是否有負權回路 Bellmanford 算法

　　x[I]y[I]t[I]分別表示第I條邊的起點終點和權共n個結點和m條邊

　　procedure bellmanford

　　begin

From:http://tw.wingwit.com/Article/program/sjjg/201311/23620.html