数据结构 基本算法.doc

基本算法c语言版一、数论算法1、求两个数的最大公约数原理：欧几里德算法又称辗转相除法，用于计算两个整数a,b的最大公约数。其计算原理依赖于下面的定理： 定理：gcd(a,b) = gcd(b,a mod b) 证明：a可以表示成a = kb + r，则r = a mod b 假设d是a,b的一个公约数，则有 d|a, d|b，而r = a - kb，因此d|r 因此d是(b,a mod b)的公约数 假设d 是(b,a mod b)的公约数，则 d | b , d |r ，但是a = kb +r 因此d也是(a,b)的公约数 因此(a,b)和(b,a mod b)的公约数是一样的，其最大公约数也必然相等，得证参考代码：int gcb(int a,int b)if(b=0) return a; else return gcb(b,a %b); 2、求最小公倍数int lcm(int a,int b) int t,p; if(ba)t=a;a=b;b=t; p=a; while(p%b)!=0)p=p+a; return p; 3、求素数1）小范围内判断一个数是否为质数int primc(int a) int i,p; p=sqrt(a); for(i=2;i=p;i+) if(a%i=0) break; if(i=p) return 0; else return 1; 2）判断 longint范围内的数是否为素数（包含求50000以内的素数表） int prc50000,prim50000;void getprimc() long int i,j; for(i=2;i50000;i+) prci=1; prc1=0; i=2; while(i50000) if(prci) j=i*2; while(j50000) prcj=0; j=j+i; i+; j=0; for(i=2;i50000;i+) if(prci) j+;primj=i; prim0=j; /* for(i=1;i=j;i+) printf(%ld ,primi); if(i%1000=0) printf(n);getch(); /7759 15193 34603 */ int primc2(long int a) long int i,p; getprimc(); p=prim0; printf(pnum=%ldn,p); for(i=1;ip;i+) if(primi=a) return 1; else if(a%primi=0)|(aprimi) return 0; 二、高精度计算1、高精度加法与乘法#include #include char str130,str230;int a50,b50,c100,len1,len2,len;/高精度加法int gjdplus() int i,k,len; len1=strlen(str1); len2=strlen(str2); k=0; for (i=len1;i=0;i-) ak=str1i-1-48; k=k+1; k=0; for (i=len2;i=0;i-) bk=str2i-1-48; k=k+1; if (len1len2) for (i=len1;ilen2;i+)ai=0; else for (i=len2;ilen2) k=len1;else k=len2; int f=0; for (i=0;i=10) f=ai / 10;else f=0; ai=ai % 10; len=k-1; if (f!=0) ak=f;len=k; printf(%d,ak); return len;/高精度乘法 int multiply() int i,j,k; len1=strlen(str1); len2=strlen(str2); k=0; for (i=len1-1;i=0;i-) ak=str1i-0; k=k+1; for (i=0;i=0;i-) bk=str2i-0; k=k+1; for (i=0;ilen2;i+)printf(%d,bi); printf(%n); for (i=0;ilen1+len2;i+) ci=0; int f; for (i=0;ilen1;i+) f=0; for (j=0;j0 ;i-) printf(%d,ai); printf(%dn,a0); */ k=multiply(); for (i=k;i0 ;i-) printf(%d,ci); printf(%dn,c0); getch(); 2、n!/无压缩#include #include #include int n,len;int c30;int nn(int n) int e,f1,f2,i,j,k;e=1; c1=1; for(i=1;i=n;i+) f1=0;f2=0; for (j=1;j0;i-) printf(%d,ci); printf(n); getch(); /有压缩#include #include #include int n,len; int c30; int nn(int n) int e,f1,f2,i,j,k;e=1; c1=1; for(i=1;i=n;i+) f1=0;f2=0; for (j=1;j0;i-) printf(%d%d%d%d,ci/1000,ci/100 % 10,ci/10 %10,ci%10); printf(n); getch(); 三、排序算法int n,data100;/数据定义/插入排序 void insertsort() int i,j,temp; for(i=1;itemp)&(j=0) dataj+1=dataj;j-; dataj+1=temp; /冒泡排序 void bubblesort() int i,j,temp; for (i=n-1;i0;i-) for (j=0;jdataj+1) temp=dataj;dataj=dataj+1;dataj+1=temp; /选择排序 int choisesort() int i,j,k,temp; for (i=0;in;i+) k=i; for (j=i+1;jn;j+) if (datajdatak) k=j; if (k!=i) temp=datai; datai=datak;datak=temp; /合并排序 void merge(int h,int mid,int r) int n1,n2,i,j,k,b20; n1=mid-h+1; n2=r-mid+1; i=h;j=mid+1; k=h; while(i=mid)&(j=r) if(dataidataj) bk=datai;i+; else bk=dataj;j+; k+; if(i=mid) while(i=mid)bk=datai;i+;k+; if(j=r) while(j=r)bk=dataj;j+;k+; for(i=h;i=r;i+) datai=bi; void hsort(int h,int r) int mid; mid=(h+r)/2; if(midr) hsort(mid+1,r); if(hmid) hsort(h,mid); merge(h,mid,r); /快排void quickst(int low,int hig) int i,j,temp; i=low;j=hig;temp=datai; while (ii)&(dataj=temp) j-; if (ji) datai=dataj;i+; while(ji)&(dataii) dataj=datai;j-; datai=temp; if(i-1low) quickst(low,i-1); if (i+1hig) quickst(i+1,hig); main() int i,j; scanf(%d,&n); for(i=0;i0) quickst(0,n-1); for(i=0;in;i+) printf(%d ,datai); printf(n); getch(); 堆排序：include #include /堆排序 int data40;int n;void shaixuan(int t1,int h1)/筛选 int i,j,temp; i=t1;j=2*t1; while (j=h1) if (j+1h1)&(dataj=dataj+1) j+; if (datai0;i-) shaixuan(i,h); void duipai(int t,int h) /堆排序 /jiandui(1,n); int i,j,t1,h1,temp; i=t;j=h; while(ij) temp=datai;datai=dataj;dataj=temp; j-; shaixuan(i,j); main() int i; scanf(%d n,&n); for (i=1;i=n;i+) scanf(%d,&datai); jiandui(1,n); duipai(1,n); for (i=1;i=n;i+) printf(%d ,datai); printf(n); getch(); 以下内容为p实现，有c代码的同学可以补充四、图论算法1最小生成树 A.Prim算法： procedure prim(v0:integer); var lowcost,closest:array1.maxn of integer;i,j,k,min:integer; begin for i:=1 to n do begin lowcosti:=costv0,i; closesti:=v0;end;for i:=1 to n-1 do begin 寻找离生成树最近的未加入顶点k min:=maxlongint; for j:=1 to n do if (lowcostjmin) and (lowcostj0) then begin min:=lowcostj; k:=j; end; lowcostk:=0; 将顶点k加入生成树 生成树中增加一条新的边k到closestk 修正各点的lowcost和closest值 for j:=1 to n do if costk,jlwocostj then begin lowcostj:=costk,j; closestj:=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 vseti) do inc(i); if i0 do begin i:=find(eq.v1);j:=find(eq.v2); if ij then begin inc(tot,eq.len); vseti:=vseti+vsetj;vsetj:=; dec(p); end; inc(q); end; writeln(tot);end; 2.最短路径 A.标号法求解单源点最短路径： var a:array1.maxn,1.maxn of integer; b:array1.maxn of integer; bi指顶点i到源点的最短路径 mark:array1.maxn of boolean; procedure bhf; var best,best_j:integer; begin fillchar(mark,sizeof(mark),false); mark1:=true; b1:=0;1为源点 repeat best:=0; for i:=1 to n do If marki then 对每一个已计算出最短路径的点 for j:=1 to n do if (not markj) and (ai,j0) then if (best=0) or (bi+ai,j0 then begin bbest_j:=best；markbest_j:=true; end; until best=0; end;bhf B.Floyed算法求解所有顶点对之间的最短路径： procedure floyed; beginfor I:=1 to n dofor j:=1 to n doif aI,j0 then pI,j:=I else pI,j:=0; pI,j表示I到j的最短路径上j的前驱结点for k:=1 to n do 枚举中间结点 for i:=1 to n do for j:=1 to n do if ai,k+aj,kai,j then begin ai,j:=ai,k+ak,j; pI,j:=pk,j; end; end; C. Dijkstra 算法： var a:array1.maxn,1.maxn of integer; b,pre:array1.maxn of integer; prei指最短路径上I的前驱结点 mark:array1.maxn of boolean;procedure dijkstra(v0:integer);begin fillchar(mark,sizeof(mark),false); for i:=1 to n do begin di:=av0,i; if di0 then prei:=v0 else prei:=0; end; markv0:=true; repeat 每循环一次加入一个离1集合最近的结点并调整其他结点的参数 min:=maxint; u:=0; u记录离1集合最近的结点 for i:=1 to n do if (not marki) and (dimin) then begin u:=i; min:=di; end; if u0 then begin marku:=true; for i:=1 to n do if (not marki) and (au,i+dudi) then begin di:=au,i+du; prei:=u; end; end; until u=0;end; D、最短路径SPFAProcedure spfa; BeginFront:=0;rear:=1;Q1:=s;hashs:=1;While frontrear do Begin X:=q(front+1) mod maxn; If startvx0 then For i:=startvx to endvx do Begin Y:=linei.y;w:=linei.w; If disxdisy+w then Begin Disx:=disy+w; If hashy=0 then Begin Hashy:=1; Rear:=(rear+1) mod maxn; Qrear:=y; End; End; End; Front:=(front+1) mod maxn; Hashx:=0; End; End;3.计算图的传递闭包 Procedure Longlink;VarT:array1.maxn,1.maxn of boolean;BeginFillchar(t,sizeof(t),false);For k:=1 to n doFor I:=1 to n do For j:=1 to n do TI,j:=tI,j or (tI,k and tk,j);End; 4无向图的连通分量 A.深度优先procedure dfs ( now,color: integer); begin for i:=1 to n do if anow,i and ci=0 then begin 对结点I染色 ci:=color; dfs(I,color); end;end; B 宽度优先（种子染色法）（缺）5关键路径 几个定义： 顶点1为源点，n为汇点。a. 顶点事件最早发生时间Vej, Ve j = max Ve j + wI,j ,其中Ve (1) = 0;b. 顶点事件最晚发生时间 Vlj, Vl j = min Vlj wI,j ,其中 Vl(n) = Ve(n);c. 边活动最早开始时间 EeI, 若边I由表示，则EeI = Vej;d. 边活动最晚开始时间 ElI, 若边I由表示，则ElI = Vlk wj,k;若 Eej = Elj ，则活动j为关键活动，由关键活动组成的路径为关键路径。求解方法：a. 从源点起topsort,判断是否有回路并计算Ve;b. 从汇点起topsort,求Vl;c. 算Ee 和 El; AOE网Procedure AOE;Beginline1:=line;front:=1;rear:=0;for i:=1 to n do if indegreei=0 then begin inc(rear); qrear:=i; earlyi:=0; end; while front=rear do begin x:=qfront; if startvx0 then for i:=startvx to endvx do begin y:=linei.y; w:=linei.w; dec(indegy); if indegy=0 then begin inc(rear); qrear:=y; end; if earlyyearlyx+w then earlyy:=earlyx+w; end; inc(front); end; line:=line1;for i:=1 to n do lasti:=maxint; lastqrear:=earlyqrear; for i:=rear-1 downto 1 do begin x:=qi; if startvx0 then for j:=startvx to endvx do if lastxlastlinej.y-linej.w then lastx:=lastlinej.y-linej.w; end;end;6拓扑排序 找入度为0的点，删去与其相连的所有边，不断重复这一过程。例 寻找一数列，其中任意连续p项之和为正，任意q 项之和为负，若不存在则输出NO. AOV网(topo_sort)Procedure topo_sort; BeginFront:=1;rear:=0; for i:=1 to n do If indegreei=0 then Begin Inc(rear); Qrear:=I; End;While front=rear do Begin X:=qfront; For i:=1 to n do If gx,i0 then Begin Dec(indegreei); If indegreei=0 then Begin Inc(rear); Qrear:=I; End; End Inc(front); End; End;7.回路问题 Euler回路(DFS)定义：经过图的每条边仅一次的回路。（充要条件：图连同且无奇点） Hamilton回路定义：经过图的每个顶点仅一次的回路。 一笔画充要条件：图连通且奇点个数为0个或2个。 Euler图Procedure find(x:longint); Var I:longint; BeginIf outdegreex=0 then Begin Inc(sum); Cntsum:=x; EndElse Begin For i:=1 to n do If gx,i0 then Begin Gx,i:=0; Dec(outdegreex); Find(i); End; Inc(sum); Cntsum:=x; End; End;Procedure euler; Begin Sum:=0;For i:=1 to n do If odd(outdegreei) then begin find(i);exit;end;Find(1); End;9判断图中是否有负权回路 Bellman-ford 算法 xI,yI,tI分别表示第I条边的起点，终点和权。共n个结点和m条边。procedure bellman-ford beginfor I:=0 to n-1 do dI:=+infinitive;d0:=0;for I:=1 to n-1 dofor j:=1 to m do 枚举每一条边 if dxj+tjdyj then dyj:=dxj+tj;for I:=1 to m doif dxj+tjdyj then return false else return true; end; 10第n最短路径问题 （缺）*第二最短路径：每举最短路径上的每条边，每次删除一条，然后求新图的最短路径，取这些路径中最短的一条即为第二最短路径。*同理，第n最短路径可在求解第n-1最短路径的基础上求解。附：树结构排序二叉树BSTProcedure insert(x:longint); Var p,q,s:point; BeginNew(p);p:=root;new(q);q:=nil;New(s);s.data:=x;s.left:=nil;s.right:=nil;Flag:=true;While flag and (pnil) do Begin Q:=p; If p.datas.data then p:=p.left Else If p.dataq.data then q.right:=s else q.left:=s;Dispose(p);dispose(q); End;Procedure bst; BeginNew(root);Root.left:=nil;root.right:=nil;Read(x);Root.data:=x;For i:=2 to n-1 do Begin Read(x); Insert(x); End; End;二叉堆HeapProcedure insert(x:longint); Var I,j:longint; BeginInc(heapn);He