【数据结构】算法集锦.txt

数据结构算法集锦

                           c[0]:=len;
                         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]; {加上根，递归结束后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)]; {加上根，递归结束后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;
                         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;

                        七 进制转换
                        1.任意正整数进制间的互化
                         除n取余
                        2.实数任意正整数进制间的互化
                        乘n取整
                        3.负数进制：
                            设计一个程序，读入一个十进制数的基数和一个负进制数的基数，并将此十进制数转换为此负 
                        进制下的数：-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个数的所有方案)
                        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.树形查找
                        二叉排序树：每个结点的值都大于其左子树任一结点的值而小于其右子树任一结点的值。
                        查找
                        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;

                        十、贪心
                        *会议问题
                        （1） n个活动每个活动有一个开始时间和一个结束时间，任一时刻仅一项活动进行，求满足活动数最多的情况。
                        解：按每项活动的结束时间进行排序，排在前面的优先满足。
                        （2）会议室空闲时间最少。
                        （3）每个客户有一个愿付的租金，求最大利润。
                        （4）共R间会议室，第i个客户需使用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个柱上，给定目标柱goal
                         
                        h[1..3,0..n]存放三个柱的状态，now与nowp存最大的不到位的铜片的柱号和编号,h[I,0]存第I个柱上的个数。
                         Procedure move(k,goal:integer); {将最大不到位的k移到目标柱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  {若未移到目标}
                           Move(k-1,6-now-goal);  {剩下的先移到没用的柱上}
                           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); {剩下的移到目标上}
                         End;
                        十二、DFS框架
                        NOIP2001 数的划分
                        procedure work(dep,pre,s:longint); {入口为work(1,1,n)}
                        {dep为当前试放的第dep个数,pre为前一次试放的数,s为当前剩余可分的总数}
                         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方向可扩展 then begin
                             inc(head);
                             list[head].x:=list[tail].x+dx[k];  
                        {扩展出新结点list[head]}
                             list[head].y:=list[tail].y+dy[k];
                             处理新结点list[head];
                           end;
                        end;

                        十五、数据结构相关算法
                        1．链表的定位函数
                        loc(I:integer):pointer; {寻找链表中的第I个结点的指针}
                        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．双链表的插入操作（插入新结点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为要删除的结点}
                        p^.pre^.next:=p^.next;
                        p^.next^.pre:=p^.pre;
                        dispose(p);