ACM常用算法打印版

ACM小組內(nèi)部預(yù)定函數(shù)Ver2.0byIcyFenix1.精度計(jì)算——大數(shù)階乘2.精度計(jì)算——乘法(大數(shù)乘小數(shù))3.精度計(jì)算——乘法(大數(shù)乘大數(shù))4.精度計(jì)算——加法5.精度計(jì)算——減法6.任意進(jìn)制轉(zhuǎn)換7.最大公約數(shù)、最小公倍數(shù)8.組合序列9.快速傅立葉變換(FFT)10.Ronberg算法計(jì)算積分11.行列式計(jì)算12.求排列組合數(shù)1.字符串替換2.字符串查找3.字符串截取1.叉乘法求任意多邊形面積2.求三角形面積3.兩矢量間角度4.兩點(diǎn)距離(2D、3D)5.射向法判斷點(diǎn)是否在多邊形內(nèi)部6.判斷點(diǎn)是否在線段上7.判斷兩線段是否相交8.判斷線段與直線是否相交9.點(diǎn)到線段最短距離10.求兩直線的交點(diǎn)11.判斷一個封閉圖形是凹集還是凸集12.Graham掃描法尋找凸包1.x的二進(jìn)制長度3.模取冪運(yùn)算4.求解模線性方程5.求解模線性方程組(中國余數(shù)定理)6.篩法素數(shù)產(chǎn)生器7.判斷一個數(shù)是否素數(shù)1.Prim算法求最小生成樹2.Dijkstra算法求單源最短路徑3.Bellman-ford算法求單源最短路徑4.Floyd算法求每對節(jié)點(diǎn)間最短路徑.快速排序2.希爾排序3.選擇法排序4.二分查找數(shù)據(jù)結(jié)構(gòu)：.順序隊(duì)列2.順序棧3.鏈表4.鏈棧5.二叉樹一、數(shù)學(xué)問題1.精度計(jì)算——大數(shù)階乘本程序直接輸出n!的結(jié)果，需要返回結(jié)果請保留ga需要math.hintfactorial(intn){longa[10000];inti,j,l,c,m=0,w;a[0]=1;for(i=1;i<=n;i++){for(j=0;j<=m;j++){a[j]=a[j]*i+c;a[j]=a[j]%10000;}if(c>0){m++;a[m]=c;}}w=m*4+log10(a[m])+1;printf("\n%ld",a[m]);for(i=m-1;i>=0;i--)printf("%4.4ld",a[i]);}2.精度計(jì)算——乘法(大數(shù)乘小數(shù))mt[]：結(jié)果，用字符串表示需要string.h1/22voidmult(charc[],chart[],intm){inti,l,k,flag,add=0;chars[100];encfor(i=0;i<l;i++)s[l-i-1]=c[i]-'0';for(i=0;i<l;i++){ksi]*m+add;if(k>=10){s[i]=k%10;add=k/10;flag=1;}else{s[i]=k;flag=0;add=0;}}if(flag){l=i+1;s[i]=add;}elsel=i;for(i=0;i<l;i++)t[l-1-i]=s[i]+'0';t[l]='\0';}3.精度計(jì)算——乘法(大數(shù)乘大數(shù))t[]：結(jié)果，用字符串表示空間復(fù)雜度為o(n^2)需要string.hvoidmult(chara[],charb[],chars[]){inti,j,k=0,alen,blen,sum=0,res[65][65]={0},flag=0;charresult[65];alen=strlen(a);blen=strlen(b);for(i=0;i<alen;i++)for(j=0;j<blen;j++)res[i][j]=(a[i]-'0')*(b[j]-'0');for(i=alen-1;i>=0;i--){for(j=blen-1;j>=0;j--)sum=sum+res[i+blen-j-1][j];result[k]=sum%10;}for(i=blen-2;i>=0;i--){for(j=0;j<=i;j++)sum=sum+res[i-j][j];result[k]=sum%10;}if(sum!=0){result[k]=sum;k=k+1;}for(i=0;i<k;i++)result[i]+='0';for(i=k-1;i>=0;i--)s[i]=result[k-1-i];sk]='\0';while(1){if(strlen(s)!=strlen(a)&&s[0]=='0')strcpy(s,s+1);}}4.精度計(jì)算——加法t[]：結(jié)果，用字符串表示空間復(fù)雜度為o(n^2)需要string.hvoidadd(chara[],charb[],charback[]){yzlchar*c;if(strlen(a)>strlen(b))l=strlen(a)+2;l=strlen(b)+2;c=(char*)malloc(l*sizeof(char));i=strlen(a)-1;j=strlen(b)-1;{if(i<0)x='0';elsex=a[i];if(j<0)y='0';elsey=b[j];zx0'+y-'0';ifup)z+=1;if(z>9){up=1;z%=10;}elseup=0;c[k++]=z+'0';ij-;}if(up)c[k++]='1';2/22ck='\0';for(k-=1;k>=0;k--)back[i++]=c[k];backi';}5.精度計(jì)算——減法t[]：結(jié)果，用字符串表示需要string.hvoidsub(chars1[],chars2[],chart[]){intillkl2=strlen(s2);l1=strlen(s1);t[l1]='\0';l1--;for(i=l2-1;i>=0;i--,l1--){if(s1[l1]-s2[i]>=0)t[l1]=s1[l1]-s2[i]+'0';{t[l1]=10+s1[l1]-s2[i]+'0';s1[l1-1]=s1[l1-1]-1;}}while(s1[k]<0){s1[k]+=10;s1[k-1]-=1;k--;}while(l1>=0){t[l1]=s1[l1];l1--;}if(t[0]=='0'){lstrlens;for(i=0;i<l1-1;i++)t[i]=t[i+1];t[l1-1]='\0';gotoloop;}if(strlen(t)==0){t[0]='0';t[1]='\0';}}6.任意進(jìn)制轉(zhuǎn)換s原進(jìn)制數(shù)字，用字符串表示轉(zhuǎn)換結(jié)果，用字符串表示原進(jìn)制數(shù)需要轉(zhuǎn)換到的進(jìn)制數(shù)高于9的位數(shù)用大寫'A'~'Z'表示，2~16位進(jìn)制通過驗(yàn)證voidconversion(chars[],chars2[],longd1,longd2){gijtnumcharc;for(i=0;s[i]!='\0';i++){if(s[i]<='9'&&s[i]>='0')t=s[i]-'0';elset=s[i]-'A'+10;num=num*d1+t;}while(1){t=num%d2;if(t<=9)s2[i]=t+'0';elses2[i]=t+'A'-10;dif(num==0)break;}forjji/2;j++){c=s2[j];s2[j]=s[i-j];s2[i-j]=c;}s2[i+1]='\0';}7.最大公約數(shù)、最小公倍數(shù)返回值：返回最大公約數(shù)(hcf)或最小公倍數(shù)(lcd)lcd需要連同hcf使用inthcf(inta,intb){while(b!=0){3/22}a}uintvinth{return(u*v/h);}8.組合序列*a：1~n的整數(shù)序列數(shù)組*a需要自行產(chǎn)生voidm_of_n(intm,intn1,intm1,int*a,inthead){if(m1<0||m1>n1)return;ifm==n1){for(i=0;i<m;i++)cout<<a[i]<<'';//輸出序列cout<<'\n';}m_of_n(m,n1-1,m1,a,head);//遞歸調(diào)用t=a[head];a[head]=a[n1-1+head];a[n1-1+head]=t;m_of_n(m,n1-1,m1-1,a,head+1);//再次遞歸調(diào)用t=a[head];a[head]=a[n1-1+head];a[n1-1+head]=t;}9.快速傅立葉變換(FFT)fr[],doublefi[],intl,intil);需要math.hvoidkkfftprpinkfrfililintn,k,l,il;doublepr[],pi[],fr[],fi[];{vlublepqsvrvipoddrpoddifor(it=0;it<=n-1;it++){mitis;for(i=0;i<=k-1;i++){j=m/2;is=2*is+(m-2*j);m=j;}fr[it]=pr[is];fi[it]=pi[is];}pr[0]=1.0;pi[0]=0.0;pn);pr[1]=cos(p);pi[1]=-sin(p);if(l!=0)pi[1]=-pi[1];for(i=2;i<=n-1;i++){p=pr[i-1]*pr[1];q=pi[i-1]*pi[1];s=(pr[i-1]+pi[i-1])*(pr[1]+pi[1]);pr[i]=p-q;pi[i]=s-p-q;}for(it=0;it<=n-2;it=it+2){vr=fr[it];vi=fi[it];fr[it]=vr+fr[it+1];fi[it]=vi+fi[it+1];fr[it+1]=vr-fr[it+1];fi[it+1]=vi-fi[it+1];}for(l0=k-2;l0>=0;l0--){for(it=0;it<=(m-1)*nv;it=it+nv)forj=0;j<=(nv/2)-1;j++){rmjfritjnvqpimjfi[it+j+nv/2];s=pr[m*j]+pi[m*j];poddr=p-q;poddi=s-p-q;fr[it+j+nv/2]=fr[it+j]-poddr;fi[it+j+nv/2]=fi[it+j]-poddi;4/22fr[it+j]=fr[it+j]+poddr;fi[it+j]=fi[it+j]+poddi;}}flfor(i=0;i<=n-1;i++){fr[i]=fr[i]/(1.0*n);fi[i]=fi[i]/(1.0*n);}ifil=0)for(i=0;i<=n-1;i++){pr[i]=sqrt(fr[i]*fr[i]+fi[i]*fi[i]);if(fabs(fr[i])<0.000001*fabs(fi[i])){if((fi[i]*fr[i])>0)pi[i]=90.0;elsepi[i]=-90.0;}pi[i]=atan(fi[i]/fr[i])*360.0/6.283185306;}}10.Ronberg算法計(jì)算積分返回值：f在(a,b)之間的積分值functionf(x)需要自行修改，程序中用的是sina(x)/x需要math.hdoublef(doublex){returnsin(x)/x;//在這里插入被積函數(shù)}doubleintegral(doublea,doubleb){doubleh=b-a;doublet1=(1+f(b))*h/2.0;doubler1,r2,s1,s2,c1,c2,t2;doubles=0.0;ahwhile(x<b){s+=f(x);x+=h;}tths;{k++;h/=2.0;t1=t2;s1=s2;gotoloop;}csss1)/15.0;ifkc1=c2;k++;h/=2.0;t1=t2;s1=s2;gotoloop;}ifkr1=r2;c1=c2;k++;t1=t2;s1=s2;gotoloop;}whilefabs(1-r1/r2)>1e-5){r1=r2;c1=c2;k++;t1=t2;s1=s2;gotoloop;}rnr}11.行列式計(jì)算nN行列式維度，需自行定義ntjssnints[][N],n;{5/22intb[N][N];/*b[N][N]用于存放，在矩陣s[N][N]中元{for(z=0;z<n;z++){for(j=0;j<n-1;j++)for(k=0;k<n-1;k++)if(k>=z)b[j][k]=s[j+1][k+1];elseb[j][k]=s[j+1][k];if(z%2==0)r=s[0][z]*js(b,n-1);/*遞歸調(diào)用elser=(-1)*s[0][z]*js(b,n-1);total=total+r;}}elseif(n==2)total=s[0][0]*s[1][1]-s[0][1]*s[1][0];tal}12.求排列組合數(shù)longP(longn,longm){ongpwhile(m!=0){p*=n;n--;m--;}np}longC(longn,longm){gicwhile(i!=0){c*=n;n--;i--;}while(m!=0){c/=m;m--;}}二、字符串處理1.字符串替換需要string.hvoidreplace(charstr[],charkey[],charswap[]){intl1,l2,l3,i,j,flag;chartmp[1000];lenstrystrlenswapfor(i=0;i<=l1-l2;i++){flag=1;for(j=0;j<l2;j++)if(str[i+j]!=key[j]){flag=0;break;}ag{strcpy(tmp,str);strcpy(&tmp[i],swap);strcpy(&tmp[i+l3],&str[i+l2]);pil3-1;lenstr}}}2.字符串查找出現(xiàn)的位置，否則返回-1需要string.hintstrfind(charstr[],charkey[])6/22{intl1,l2,i,j,flag;lenstryfor(i=0;i<=l1-l2;i++){flag=1;for(j=0;j<l2;j++)if(str[i+j]!=key[j]){flag=0;break;}if(flag)returni;}return1;}3.字符串截取符符需要string.hintmid(charstr[],intstart,intlen,charstrback[]){tliknstrif(start+len>l)return0;for(i=start;i<start+len;i++)strback[k++]=str[i];strback[k]='\0';eturn}三、計(jì)算幾何1.叉乘法求任意多邊形面積支持任意多邊形，凹、凸皆可多邊形頂點(diǎn)輸入時按順時針順序排列typedefstruct{doublex,y;doublepolygonarea(Point*polygon,intN){doublearea=0;for(i=0;i<N;i++){j=(i+1)%N;area+=polygon[i].x*polygon[j].y;area-=polygon[i].y*polygon[j].x;}area/=2;return(area<0?-area:area);}2.求三角形面積resultareafloatx1,floaty1,floatx2,floaty2,floatx3,floaty3);需要math.hfloatarea3(floatx1,floaty1,floatx2,floaty2,floatx3,floaty3){floata,b,c,p,s;a=sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));b=sqrt((x1-x3)*(x1-x3)+(y1-y3)*(y1-y3));c=sqrt((x3-x2)*(x3-x2)+(y3-y2)*(y3-y2));s=sqrt(p*(p-a)*(p-b)*(p-c));s}3.兩矢量間角度語法：result=angle(doublex1,doubley1,doublex2,doubley2);返回角度為弧度制，并且以逆時針方向?yàn)檎较蛐枰猰ath.h7/22#definePI3.1415926doubleangle(doublex1,doubley1,doublex2,doubley2){doubledtheta,theta1,theta2;theta1=atan2(y1,x1);theta2=atan2(y2,x2);dtheta=theta2-theta1;while(dtheta>PI)dtheta-=PI*2;while(dtheta<-PI)dtheta+=PI*2;urndtheta}4.兩點(diǎn)距離(2D、3D)語法：result=distance_2d(floatx1,floatx2,floaty1,floaty2);需要math.hfloatdistance_2d(floatx1,floatx2,floaty1,floaty2){return(sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2)));}floatdistance_3d(floatx1,floatx2,floaty1,floaty2,floatz1,floatz2){return(sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2)+(z1-z2)*(z1-z2}5.射向法判斷點(diǎn)是否在多邊形內(nèi)部另行判斷需要math.h#defineMIN(x,y)(x<y?x:y)#defineMAX(x,y)(x>y?x:y)typedefstruct{doublex,y;intinsidepolygon(Point*polygon,intN,Pointp){intcounter0;doublexinters;p=polygon[0];for(i=1;i<=N;i++){p2=polygon[i%N];yMINpypyifpyMAXpypy{if(p.x<=MAX(p1.x,p2.x)){ifpy=p2.y){xinters=pypypx-p1.x)/(p2.y-p1.y)+p1.x;if(p1.x==p2.x||p.x<=xinters)counter;}}}}}if(counter%2==0)return(OUTSIDE);returnINSIDE);}6.判斷點(diǎn)是否在線段上需要math.h#defineMIN(x,y)(x<y?x:y)#defineMAX(x,y)(x>y?x:y)typedefstruct{doublex,y;intFC(doublex1,doublex2){8/22if(x1-x2<0.000002&&x1-x2>-0.000002)return1;else}intPointonline(Pointp1,Pointp2,Pointp){doublex1,y1,x2,y2;x1=p.x-p1.x;x2=p2.x-p1.x;pyif(FC(x1*y2-x2*y1,0)==0)return0;if((MIN(p1.x,p2.x)<=p.x&&p.x<=MAX(p1.x,p2.x))&&Xpypyreturn1;elsereturn0;}7.判斷兩線段是否相交ectintersectPointpPointpPointpPointp;p1~4：兩條線段的四個端點(diǎn)線段首尾相接p1!=p2;p3!=p4;#defineMIN(x,y)(x<y?x:y)#defineMAX(x,y)(x>y?x:y)typedefstruct{doublex,y;intlineintersect(Pointp1,Pointp2,Pointp3,Pointp4){pxpxpypypxpxp1.y==p4.y)|rn//快速排斥試驗(yàn)((MIN(p1.x,p2.x)<p3.x&&p3.x<MAX(p1.x,p2.x)&&MIN(p1.(MIN(p1.x,p2.x)<p4.x&&p3.x<MAX(p1.x,p2.x)&&MIN(p1.y,;elsereturn0;//跨立試驗(yàn)tp1.x=p1.x-p3.x;tp2.x=p4.x-p3.x;tp3.x=p2.x-p3.x;((tp1.x*tp2.y-tp1.y*tp2.x)*(tp2.x*tp3.y-tp2.y*tp3.x)>=0)return1;elsereturn0;}8.判斷線段與直線是否相交線段的兩個端點(diǎn)直線上的兩個點(diǎn)如線段在直線上，返回1typedefstruct{doublex,y;intlineintersect(Pointp1,Pointp2,Pointp3,Pointp4){tp1.x=p1.x-p3.x;tp2.x=p4.x-p3.x;tp3.x=p2.x-p3.x;((tp1.x*tp2.y-tp1.y*tp2.x)*(tp2.x*tp3.y-tp2.y*tp3.x)>=0)return1;elsereturn0;}9.點(diǎn)到線段最短距離需要math.h#defineMIN(x,y)(x<y?x:y)9/22#defineMAX(x,y)(x>y?x:y)typedefstruct{doublex,y;doublemindistance(Pointp1,Pointp2,Pointq){flagdoublek;if(p1.x==p2.x){s.x=p1.x;s.y=q.y;flag=0;}if(p1.y==p2.y){s.x=q.x;s.y=p1.y;flag=0;}ag{kpypypxpx);s.x=(k*k*p1.x+k*(q.y-p1.y)+q.x)/(k*k+1);syksxp1.x)+p1.y;}if(MIN(p1.x,p2.x)<=s.x&&s.x<=MAX(p1.x,p2.x))returnsqrtqxsxqxsxq.y-s.y)*(q.y-s.y));MIN(sqrt((q.x-p1.x)*(q.x-p1.x)+(q.y-p1.y)*(q.y-p1.y)),sqrt((qxpx*(q.x-p2.x)+(q.y-p2.y)*(q.y-p2.y)));}10.求兩直線的交點(diǎn)p1~p4：直線上不相同的兩點(diǎn)的值是否在0~1之間，用在0~1之間的那個求交點(diǎn)typedefstruct{doublex,y;intlinecorss(Pointp1,Pointp2,Pointp3,Pointp4,Point*p){doublek;//同一直線if((p4.x-p3.x)*(p1.y-p3.y)-(p4.y-p3.y)*(p1.x-p3.x)==0&&(p2.x-p1.x)*(p1.y-p3.y)-(p2.y-p1.y)*(p1.x-p3.x)==0)return//平行，不同一直線if((p4.y-p3.y)*(p2.x-p1.x)-(p4.x-p3.x)*(p2.y-p1.y)==0)kpxp3.x)*(p1.y-p3.y)-(p4.y-p3.y)*(p1.x-p3.x))/((p4.y-p3.y)*(p2.x-p1.x)-(p4.x-p3.x)*(p2.y-p1.y));//k1=((p2.x-p1.x)*(p1.y-p3.y)-(p2.y-p1.y)*(p1.x-p3.x))/((p4.y-p3.y)*(p2.x-p1.x)-(p4.x-p3.x)*(p2.y-p1.y));(*p).x=p1.x+k*(p2.x-p1.x);yreturn1;//有交點(diǎn)}11.判斷一個封閉圖形是凹集還是凸集無法計(jì)算默認(rèn)曲線為簡單曲線：無交叉、無圈typedefstruct{doublex,y;intconvex(Point*p,intn){intflag0;doublez;ifn<3)for(i=0;i<n;i++){j=(i+1)%n;k=(i+2)%n;z=(p[j].x-p[i].x)*(p[k].y-p[j].y);z-=(p[j].y-p[i].y)*(p[k].x-p[j].x);ifz0)flag|=1;elseif(z>0)flag|=2;if(flag==3)return－1;//CONCAVE}if(flag!=0)return1;//CONVEX}12.Graham掃描法尋找凸包GrahamscanPointPointSet[],Pointch[],intn,int&len);10/22structPoint{floatx,y;floatmultiply(Pointp1,Pointp2,Pointp0){return((p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y));}floatdistance(Pointp1,Pointp2){return(sqrt((p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y)}voidGraham_scan(PointPointSet[],Pointch[],intn,int&len){intijk0,top=2;for(i=1;i<n;i++)Setky)&&(PointSet[i].x<PointSet[k].x)))tmp=PointSet[0];PointSetPointSetkintSetktmpfor(i=1;i<n-1;i++){for(j=i+1;j<n;j++)((multiply(PointSet[j],PointSet[k],PointSet[0])>0)||((multiply(PointSet[j],PointSet[k],PointSet[0])==0)&&(distance(PointSet[0],PointSet[j])<distance(PointSet[0],PointSetk)tmp=PointSet[i];tSetiPointSetkSetktmp}ch[0]=PointSet[0];ch[1]=PointSet[1];ch[2]=PointSet[2];for(i=3;i<n;i++){while(multiply(PointSet[i],ch[top],ch[top-1])>=0)top--;ch[++top]=PointSet[i];}p}1.x的二進(jìn)制長度intBitLength(intx){tdwhile(x>0){x>>=1;}}最低位為第一位intBitAt(intx,inti){return(x&(1<<(i-1)));}3.模取冪運(yùn)算11/22intModular_Expoent(inta,intb,intn){yfor(i=BitLength(b);i>0;i--){y=(y*y)%n;if(BitAt(b,i)>0)y=(y*a)%n;}}4.求解模線性方程intext_euclid(inta,intb,int&x,int&y)//求gcd(a,b)=ax+by{if(b==0){x=1;y=0;returna;}d=ext_euclid(b,a%b,x,y);tx;x=y;y=t-a/b*y;}voidmodular_equation(inta,intb,intn){d=ext_euclid(a,n,x,y);ifbd0)printf("Noanswer!\n");{e=(x*(b/d))%n;for(i=0;i<d;i++)%dther%dtheris:%ld\n",i+1,(e+i*(n/d))%n);}}5.求解模線性方程組(中國余數(shù)定理)intext_euclid(inta,intb,int&x,int&y)//求gcd(a,b)=ax+by{if(b==0){x=1;y=0;returna;}d=ext_euclid(b,a%b,x,y);tx;x=y;y=t-a/b*y;}intChina(intB[],intW[],intk){intdxyamn;for(i=0;i<k;i++)for(i=0;i<k;i++){mnWid=ext_euclid(W[i],m,x,y);a=(a+y*m*B[i])%n;}if(a>0)returna;elsereturn(a+n);}6.篩法素數(shù)產(chǎn)生器intprime(inta[],intn){inti,j,k,x,num,*b;12/22b=(int*)malloc(sizeof(int)*(n+1)*2);a[0]=2;a[1]=3;num=2;for(i=1;i<=2*n;i++)for(i=3;i<=n;i+=3)for(j=0;j<2;j++){x=2*(i+j)-1;while(b[x]==0){a[num++]=x;for(k=x;k<=2*n;k+=x)}}urnnum}7.判斷一個數(shù)是否素數(shù)intcomp(intn){intiflag1;for(i=2;i<=sqrt(n);i++)if(n%i==0){flag=0;break;}if(flag==1)return1;elsereturn0;}五、圖論1.Prim算法求最小生成樹用來記錄每個節(jié)點(diǎn)的父節(jié)點(diǎn)#defineinfinity1000000#definemax_vertexes5typedefintGraph[max_vertexes][max_vertexes];voidprim(GraphG,intvcount,intfather[]){lowcost[max_vertexes],closeset[max_vertexes],used[max_vertexes];for(i=0;i<vcount;i++){lowcostiG][i];closeset[i]=0;ifather[i]=-1;}usedfor(i=1;i<vcount;i++){j=0;while(used[j])j++;for(k=0;k<vcount;k++)if((!used[k])&&(lowcost[k]<lowcost[j]))j=k;father[j]=closeset[j];for(k=0;k<vcount;k++)if(!used[k]&&(G[j][k]<lowcost[k])){lowcost[k]=G[j][k];closeset[k]=j;}}}2.Dijkstra算法求單源最短路徑輸入的圖的權(quán)必須非負(fù)while(i!=s){printf("%d<--",i+1);}printf("%d\n",s+1);13/22intDijkstra(GraphG,intn,ints,intt,intpath[]){intijwmincdmaxvertexesmarkmax_vertexes];for(i=0;i<n;i++)mark[i]=0;for(i=0;i<n;i++){d[i]=G[s][i];path[i]=s;}mark[s]=1;path[s]=0;d[s]=0;for(i=1;i<n;i++){mincinfinity;w0;for(j=0;j<n;j++)((mark[((mark[j]==0)&&(minc>=d[j])){minc=d[j];w=j;}markw;for(j=0;j<n;j++)((mark[j]==0)&&(G[w][j]!=infinity)&&(d[j]>d[w]+G[w][j])){d[j]=d[w]+G[w][j];path[j]=w;}}rndt}3.Bellman-ford算法求單源最短路徑語法：result=Bellman_ford(GraphG,intn,ints,intt,intpath],intsuccess);while(i!=s){printf("%d<--",i+1);}printf("%d\n",s+1);intBellman_ford(GraphG,intn,ints,intt,intpath],intsuccess){ntijkdmaxvertexesfor(i=0;i<n;i++){d[i]=infinity;path[i]=0;}dsfor(k=1;k<n;k++)for(i=0;i<n;i++)for(j=0;j<n;j++)(d[(d[j]>d[i]+G[i][j]){d[j]=d[i]+G[i][j];path[j]=i;}success=0;for(i=0;i<n;i++)for(j=0;j<n;j++)if(d[j]>d[i]+G[i][j])return0;success=1;rndt}4.Floyd-Warshall算法求每對節(jié)點(diǎn)間最短路徑voidFloyd_Washall(GraphG,intn,GraphD,GraphP){for(i=0;i<n;i++)for(j=0;j<n;j++){D[i][j]=G[i][j];P[i][j]=i;}for(i=0;i<n;i++){D[i][i]=0;P[i][i]=0;}for(k=0;k<n;k++)for(i=0;i<n;i++)for(j=0;j<n;j++)if(D[i][j]>D[i][k]+D[k][j]){D[i][j]=D[i][k]+D[k][j];P[i][j]=P[k][j];}}六、排序/查找.快速排序b14/22輸出升序序列voidquicksort(intl,intr,intb[]){ifl>=r)return;j=r;x=b[i];while(i!=j){while(b[j]>x&&j>i)j--;{}while(b[i]<x&&j>i)i++;{j--;}}quicksort(l,j-1,b);rtirb}2.希爾排序n輸出升序序列voidshellsort(inta[],intn){kwhile(g!=0){for(i=g+1;i<=n;i++){temp=a[i];j=i-g;while(j>0){if(a[j]<=a[k])j=0;{temp=a[j];a[j]=a[k];a[k]=temp;}j=j-g;}}}}3.選擇法排序輸出升序序列小規(guī)模排序用voidsort(intt[],intn){tempfor(i=0;i<n;i++){for(j=i;j<n;j++)if(t[j]<t[k])k=j;temp=t[i];t[i]=t[k];t[k]=temp;}}4.二分查找輸出－1要求查找數(shù)組是有序升序序列15/22intsearch_bin(int*t,intk){intlow=1,high=10,mid;while(low<=high){if(k==t[mid])returnmid;elseif(k<t[mid])high=mid-1;elselow=mid+1;}return1;}七、數(shù)據(jù)結(jié)構(gòu).順序隊(duì)列#definemaxsize100typedefstruct{tamaxsize}sueue;intsqinit(sueue*p)//隊(duì)列初始化{eturn}intenqueue(sueue*q,inte)//入隊(duì){if((q->rear+1)%maxsize==q->front)q->data[q->rear]=e;q->rear=(q->rear+1)%maxsize;eturn}intdequeue(sueue*q)//出隊(duì){if(q->front==q->rear)e=q->data[q->front];q->front=(q->front+1)%maxsize;}intempty(sueue*q)//判空{(diào)if(q->front==q->rear)v=1;v=0;}intgethead(sueue*q)//取得頭元素{if(q->front==q->rear)e=-1;e=q->data[q->front];}voiddisplay(sueue*q)//顯示所有元素{s=q->front;printf("thesequeueisdisplay:\n");if(q->front==q->rear)printf("thesequeueisempty!");{while(s<q->rear){printf("->%d",q->data[s]);s=(s+1)%maxsize;}rintfn}}main(sueue*head)//函數(shù)使用樣例{xyselectxqprintf("createaemptysequeue\n");sqinit(head);printf("pleaseinputthesequeuelength:\n");scanf("%d",&n);for(i=0;i<n;i++){printf("pleaseinputasequeuevalue:\n");scanf("%d",&m);enqueue(head,m);}printf("head->rear:%d\n",head->rear);printf("head->front:%d\n",head->front);display(head);16/22printf("select1****enqueue()\n");printf("select2****dequeue()\n");printf("select3****empty()\n");printf("select4****gethead()\n");printf("select5****display()\n");printf("pleaseselect(1--5):");scanf("%d",&select);switch(select){case1:{printf("pleaseinputavalue:\n");scanf("%d",&x);enqueue(head,x);displayhead}case{dequeue(head);displayhead}case{ifemptyhead))printf("thesequeueisempty");printf("thesequeueisfull");}e{y=gethead(head);printf("outputheadvalue:%d\n",y);}case{displayhead}}}}2.順序棧#definem100typedefstruct{ackmkstruinit(stackstru*s)/*裝入棧*/{s->top=0;eturn}intpush(stackstru*s,intx)/*入棧操作*/{if(s->top==m)printf("thestackisoverflow!\n");{s->top=s->top+1;s->stack[s->top]=x;}}voiddisplay(stackstru*s)/*顯示棧所有數(shù)據(jù)*/{if(s->top==0)printf("thestackisempty!\n");{while(s->top!=0){printf("%d->",s->stack[s->top]);s->top=s->top-1;}}}intpop(stackstru*s)/*出棧操作并返回被刪除的那個記/{if(s->top==0)printf("thestackisempty!\n");{y=s->stack[s->top];s->top=s->top-1;}}intgettop(stackstru*s)/*得到棧頂數(shù)*/{17/22if(s->top==0)e=s->stack[s->top];}main(stackstru*p)//函數(shù)使用演示{intn,i,k,h,x1,x2,select;printf("createaemptystack!\n");printf("inputastacklength:\n");scanf("%d",&n);for(i=0;i<n;i++){printf("inputastackvalue:\n");scanf("%d",&k);pk}printf("select1:display()\n");printf("select2:push()\n");printf("select3:pop()\n");printf("select4:gettop()\n");printf("inputayourselect(1-4):\n");scanf("%d",&select);switch(select){case1:{displayp;}case{printf("inputapushavalue:\n");scanf("%d",&h);hphdisplayp;}case{x1=pop(p);printf("x1->%d\n",x1);displayp;}e{x2=gettop(p);printf("x2->%d",x2);}}}3.鏈表#definenull0typedefcharElemType;/*字符型數(shù)據(jù)*/typedefstructLNode{structLNode*next;setnull(structLNode**p);intlength(structLNode**p);ElemTypeget(structLNode**p,inti);voidinsert(structLNode**p,ElemTypex,inti);intdelete(structLNode**p,inti);voiddisplay(structLNode**p);{structLNode*head,*q;/*定義靜態(tài)變量*/intselect,x1,x2,x3,x4;chare,y;head=setnull(&head);/*建議鏈表并設(shè)置為空表*/printf("請輸入數(shù)據(jù)長度:");scanf("%d",&n);for(i=1;i<n;i++);{printf("將數(shù)據(jù)插入到單鏈表中:");scanf("%d",&y);insert(&head,y,i);}/*插入數(shù)據(jù)到鏈表*/display(&head);/*顯示鏈表所有數(shù)據(jù)*/printf("select1求長度length()\n");printf("select2取結(jié)點(diǎn)get()\n");printf("select3求值查找locate()\n");printf("select4刪除結(jié)點(diǎn)delete()\n");printf("inputyourselect:");scanf("%d",&select);18/22switch(select){case1:{x1=length(&head);printf("輸出單鏈表的長度%d",x1);display(&head);case{printf("請輸入要取得結(jié)點(diǎn):");scanf("%d",&m);x2=get(&head,m);display(&head);case{printf("請輸入要查找的數(shù)據(jù):");scanf("%d",&e);x3=locate(&head,e);display(&head);e{printf("請輸入要刪除的結(jié)點(diǎn):");scanf("%d",&g);x4=delete(&head,g);display(&head);}}}setnull(structLNode**p){}intlength(structLNode**p){structLNode*q=*p;while(q!=null){q=q->next;}n}ElemTypeget(structLNode**p,inti){structLNode*q=*p;while(j<i&&q!=null){q=q->next;j++;}fqnullreturnqdata);printf("位置參數(shù)不正確!\n");}intlocate(structLNode**p,ElemTypex){structLNode*q=*p;while(q!=null&&q->data!=x){q=q->next;}ifqnullreturn);returnn;}voidinsert(structLNode**p,ElemTypex,inti){structLNode*s,*q;s=(structLNode*)malloc(sizeof(structLNode));s->data=x;p{s->next=q;}{while(j<i-1&&q->next!=null){q=q->next;j++;}19/22fji{s->next=q->next;q>next=s;}printf("位置參數(shù)不正確!\n");}}intdelete(structLNode**p,inti){structLNode*q=*p,*t;{tq;pqnext}{while(j<i-1&&q->next!=null){q=q->next;j++;}if(q->next!=null&&j==i-1){t=q->next;q->next=t->next;}printf("位置參數(shù)不正確!\n");}ftnullfree(t);}voiddisplay(structLNode**p){structLNode*q;pprintf("單鏈表顯示:");ifqnullprintf("鏈表為空!");elseif(q->next==null)printf("%c\n",q->data);{while(q->next!=null){printf("%c->",q->data);q=q->next;}printf("%c",q->data);}rintfn}4.鏈棧#definenull0typedefstructstacknode{structstacknode*next;tacklinktypedefstruct{stacklink*top;initlink(stackk*s){s->top=(stacklink*)malloc(sizeof(stacklink));s->top->data=0;s->top->next=null;}intpoplink(stackk*s){stackk*p;intv;if(s->top->next==null)printf("thestackisempty\n");{v=s->top->next-