?? 數(shù)據(jù)結(jié)構(gòu)算法集錦.txt
字號:
end;
5．高精度除以低精度
procedure devide(a:hp;b:longint; var c:hp; var
d:longint);
{c:=a div b; d:= a mod b}
var i,len:integer;
begin
fillchar(c,sizeof(c),0);
len:=a[0]; d:=0;
for i:=len downto 1 do begin
d:=d*10+a[i];
c[i]:=d div b;
d:=d mod b;
end;
while (len>1) and (c[len]=0) then dec(len);
c[0]:=len;
end;
6．高精度除以高精度
procedure high_devide(a,b:hp; var c,d:hp);
var
i,len:integer;
begin
fillchar(c,sizeof(c),0);
fillchar(d,sizeof(d),0);
len:=a[0];d[0]:=1;
for i:=len downto 1 do begin
multiply(d,10,d);
d[1]:=a[i];
while(compare(d,b)>=0) do {即d>=b}
begin
Subtract(d,b,d);
inc(c[i]);
end;
end;
while(len>1)and(c.s[len]=0) do dec(len);
c.len:=len;
end;
六、 樹的遍歷
1．已知前序中序求后序
procedure Solve(pre,mid:string);
var i:integer;
begin
if (pre='''') or (mid='''') then exit;
i:=pos(pre[1],mid);
solve(copy(pre,2,i),copy(mid,1,i-1));
solve(copy(pre,i+1,length(pre)-i),copy(mid,i+1,length(mid)-i));
post:=post+pre[1]; {加上根，遞歸結(jié)束后post即為后序遍歷}
end;
2．已知中序后序求前序
procedure Solve(mid,post:string);
var i:integer;
begin
if (mid='''') or (post='''') then exit;
i:=pos(post[length(post)],mid);
pre:=pre+post[length(post)]; {加上根，遞歸結(jié)束后pre即為前序遍歷}
solve(copy(mid,1,I-1),copy(post,1,I-1));
solve(copy(mid,I+1,length(mid)-I),copy(post,I,length(post)-i));
end;
3．已知前序后序求中序的一種
function ok(s1,s2:string):boolean;
var i,l:integer; p:boolean;
begin
ok:=true;
l:=length(s1);
for i:=1 to l do begin
p:=false;
for j:=1 to l do
if s1[i]=s2[j] then p:=true;
if not p then begin ok:=false;exit;end;
end;
procedure solve(pre,post:string);
var i:integer;
begin
if (pre='''') or (post='''') then exit;
i:=0;
repeat
inc(i);
until ok(copy(pre,2,i),copy(post,1,i));
solve(copy(pre,2,i),copy(post,1,i));
midstr:=midstr+pre[1];
solve(copy(pre,i+2,length(pre)-i-1),copy(post,i+1,length(post)-i-1));
end;
七 進(jìn)制轉(zhuǎn)換
1.任意正整數(shù)進(jìn)制間的互化
除n取余
2.實(shí)數(shù)任意正整數(shù)進(jìn)制間的互化
乘n取整
3.負(fù)數(shù)進(jìn)制：
設(shè)計(jì)一個(gè)程序，讀入一個(gè)十進(jìn)制數(shù)的基數(shù)和一個(gè)負(fù)進(jìn)制數(shù)的基數(shù)，并將此十進(jìn)制數(shù)轉(zhuǎn)換為此負(fù)
進(jìn)制下的數(shù)：-R∈{-2，-3，-4,....-20}
八 全排列與組合的生成
1.排列的生成：（1..n）
procedure solve(dep:integer);
var
i:integer;
begin
if dep=n+1 then begin writeln(s);exit; end;
for i:=1 to n do
if not used[i] then begin
s:=s+chr(i+ord(''0''));used[i]:=true;
solve(dep+1);
s:=copy(s,1,length(s)-1); used[i]:=false;
end;
end;
2.組合的生成(1..n中選取k個(gè)數(shù)的所有方案)
procedure solve(dep,pre:integer);
var
i:integer;
begin
if dep=k+1 then begin writeln(s);exit; end;
for i:=1 to n do
if (not used[i]) and (i>pre) then begin
s:=s+chr(i+ord(''0''));used[i]:=true;
solve(dep+1,i);
s:=copy(s,1,length(s)-1); used[i]:=false;
end;
end;
九.查找算法
1.折半查找
function binsearch(k:keytype):integer;
var low,hig,mid:integer;
begin
low:=1;hig:=n;
mid:=(low+hig) div 2;
while (a[mid].key<>k) and (low<=hig) do begin
if a[mid].key>k then hig:=mid-1
else low:=mid+1;
mid:=(low+hig) div 2;
end;
if low>hig then mid:=0;
binsearch:=mid;
end;
2.樹形查找
二叉排序樹：每個(gè)結(jié)點(diǎn)的值都大于其左子樹任一結(jié)點(diǎn)的值而小于其右子樹任一結(jié)點(diǎn)的值。
查找
function treesrh(k:keytype):pointer;
var q:pointer;
begin
q:=root;
while (q<>nil) and (q^.key<>k) do
if k<q^.key then q:=q^.left
else q:=q^.right;
treesrh:=q;
end;
十、貪心
*會(huì)議問題
（1） n個(gè)活動(dòng)每個(gè)活動(dòng)有一個(gè)開始時(shí)間和一個(gè)結(jié)束時(shí)間，任一時(shí)刻僅一項(xiàng)活動(dòng)進(jìn)行，求滿足活動(dòng)數(shù)最多的情況。
解：按每項(xiàng)活動(dòng)的結(jié)束時(shí)間進(jìn)行排序，排在前面的優(yōu)先滿足。
（2）會(huì)議室空閑時(shí)間最少。
（3）每個(gè)客戶有一個(gè)愿付的租金，求最大利潤。
（4）共R間會(huì)議室，第i個(gè)客戶需使用i間會(huì)議室，費(fèi)用相同，求最大利潤。
十一、回溯法框架
1. n皇后問題
procedure try(i:byte);
var j:byte;
begin
if i=n+1 then begin print;exit;end;
for j:=1 to n do
if a[i] and b[j+i] and c[j-i] then begin
x[i]:=j;
a[j]:=false; b[j+i]:=false; c[j-i]:=false;
try(i+1);
a[j]:=true; b[i+j]:=true; c[j-i]:=true;
end;
end;
2.Hanoi Tower 漢諾塔
h(n)=2*h(n-1)+1
h(1)=1
初始所有銅片都在a柱上
procedure hanoi(n,a,b,c:byte); {將第n塊銅片從a柱通過b柱移到c柱上}
begin
if n=0 then exit;
hanoi(n-1,a,c,b); {將上面的n-1塊從a柱通過c柱移到b柱上}
write(n,’moved from’,a,’to’,c);
hanoi(n-1,b,a,c);{ 將b上的n-1塊從b柱通過a柱移到c柱上
end;
初始銅片分布在3個(gè)柱上，給定目標(biāo)柱goal
h[1..3,0..n]存放三個(gè)柱的狀態(tài)，now與nowp存最大的不到位的銅片的柱號和編號,h[I,0]存第I個(gè)柱上的個(gè)數(shù)。
Procedure move(k,goal:integer); {將最大不到位的k移到目標(biāo)柱goal上}
Begin
If k=0 then exit;
For I:=1 to 3 do
For j:=1 to han[I,0] do
If h[I,j]=k then begin now:=I;nowp:=j; end; {找到k的位置}
If now<>goal then begin {若未移到目標(biāo)}
Move(k-1,6-now-goal); {剩下的先移到?jīng)]用的柱上}
Writeln(k moved from now to goal);
H[goal,h[goal,0]+1]:=h[now,nowp]; h[now,nowp]:=0;
Inc(h[goal,0]); dec(h[now,0]);
Move(k-1,goal); {剩下的移到目標(biāo)上}
End;
十二、DFS框架
NOIP2001 數(shù)的劃分
procedure work(dep,pre,s:longint); {入口為work(1,1,n)}
{dep為當(dāng)前試放的第dep個(gè)數(shù),pre為前一次試放的數(shù),s為當(dāng)前剩余可分的總數(shù)}
var j:longint;
begin
if dep=n then begin
if s>=pre then inc(r); exit;
end;
for j:=pre to s div 2 do work(dep+1,j,s-j);
end;
類似：
procedure try(dep:integer);
var i:integer;
begin
if dep=k then begin
if tot>=a[dep-1] then inc(sum);
exit; end;
for i:=a[dep-1] to tot div 2 do begin
a[dep]:=i; dec(tot,i);
try(dep+1);
inc(tot,i);
end;
end;{try}
十三、BFS框架
IOI94 房間問題
head:=1; tail:=0;
while tail<head do begin
inc(tail);
for k:=1 to n do
if k方向可擴(kuò)展 then begin
inc(head);
list[head].x:=list[tail].x+dx[k];
{擴(kuò)展出新結(jié)點(diǎn)list[head]}
list[head].y:=list[tail].y+dy[k];
處理新結(jié)點(diǎn)list[head];
end;
end;
十五、數(shù)據(jù)結(jié)構(gòu)相關(guān)算法
1．鏈表的定位函數(shù)
loc(I:integer):pointer; {尋找鏈表中的第I個(gè)結(jié)點(diǎn)的指針}
procedure loc(L:linklist; I:integer):pointer;
var p:pointer;
j:integer;
begin
p:=L.head; j:=0;
if (I>=1) and (I<=L.len) then
while j<I do begin p:=p^.next; inc(j); end;
loc:=p;
end;
2．單鏈表的插入操作
procedure insert(L:linklist; I:integer; x:datatype);
var p,q:pointer;
begin
p:=loc(L,I);
new(q);
q^.data:=x;
q^.next:=p^.next;
p^.next:=q;
inc(L.len);
end;
3．單鏈表的刪除操作
procedure delete(L:linklist; I:integer);
var p,q:pointer;
begin
p:=loc(L,I-1);
q:=p^.next;
p^.next:=q^.next;
dispose(q);
dec(L.len);
end;
4．雙鏈表的插入操作（插入新結(jié)點(diǎn)q）
p:=loc(L,I);
new(q);
q^.data:=x;
q^.pre:=p;
q^.next:=p^.next;
p^.next:=q;
q^.next^.pre:=q;
5．雙鏈表的刪除操作
p:=loc(L,I); {p為要?jiǎng)h除的結(jié)點(diǎn)}
p^.pre^.next:=p^.next;
p^.next^.pre:=p^.pre;
dispose(p);
?? 快捷鍵說明
復(fù)制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -