常用算法及其實現(xiàn)

1、常用算法經典代碼（C+版） 一、快速排序void qsort(int x,int y) /待排序的數(shù)據(jù)存放在a1.an數(shù)組中  int h=x,r=y;   int m=a(x+y)>>1; /取中間的那個位置的值   while(h<r)while (ah<m) h+; /比中間那個位置的值小，循環(huán)直到找一個比中間那個值大的      while (ar>m) r-; /比中間那個位置的值大，循環(huán)直到找一個比中間那個值小的  

2、0;   if(h<=r)int temp=ah;/如果此時h<=r，交換ah和ar         ah=ar;         ar=temp;         h+;r-; /這兩句必不可少哦     if(r>x) qsort(x,r);/注意此處，尾指針跑到前半部分了&#

3、160;    if(h<y) qsort(h,y); /注意此處，頭指針跑到后半部分了調用：qsort(1,n)即可實現(xiàn)數(shù)組a中元素有序。適用于n比較大的排序 二、冒泡排序void paopao(void) /待排序的數(shù)據(jù)存放在a1.an數(shù)組中for(int i=1;i<n;i+)  /控制循環(huán)（冒泡）的次數(shù)，n個數(shù)，需要n-1次冒泡  for(int j=1;j<=n-i;j+) /相鄰的兩兩比較    if(aj<aj+1) int temp=aj;aj=aj+1;aj+1=

4、temp;或者void paopao(void) /待排序的數(shù)據(jù)存放在a1.an數(shù)組中for(int i=1;i<n;i+)  /控制循環(huán)（冒泡）的次數(shù)，n個數(shù)，需要n-1次冒泡  for(int j=n-i;j>=1;j-) /相鄰的兩兩比較    if(aj<aj+1) int temp=aj;aj=aj+1;aj+1=temp; 調用：paopao()，適用于n比較小的排序 三、桶排序void bucketsort(void)/a的取值范圍已知。如a<=cmax。 memset(ton

5、g,0,sizeof(tong);/桶初始化for(int i=1;i<=n;i+)/讀入n個數(shù)    int acin>>a;tonga+;/相應的桶號計數(shù)器加1  for(int i=1;i<=cmax;i+)  if(tongi>0) /當桶中裝的樹大于0，說明i出現(xiàn)過tongi次，否則沒出現(xiàn)過i     while (tongi!=0)       tongi-;cout<<i<< ;

6、 桶排序適用于那些待排序的關鍵字的值在已知范圍的排序。 四、合（歸）并排序void merge(int l,int m,int r)/合并l,m和m+1,r兩個已經有序的區(qū)間 int b101;/借助一個新的數(shù)組B，使兩個有序的子區(qū)間合并成一個有序的區(qū)間，b數(shù)組的大小要注意  int h,t,k;  k=0;/用于新數(shù)組B的指針  h=l;t=m+1;/讓h指向第一個區(qū)間的第一個元素，t指向第二個區(qū)間的第一個元素。  while(h<=m)&&(t<=r)/在指針h和t沒有到區(qū)間尾時，把兩個區(qū)間的元素抄在新

7、數(shù)組中    k+;       /新數(shù)組指針加1     if (ah<at)bk=ah;h+;       /抄第一個區(qū)間元素到新數(shù)組     elsebk=at;t+;   /抄第二個區(qū)間元素到新數(shù)組      while(h<=m)k+;bk=ah;h+;  /如果第一個區(qū)間沒有

8、抄結束，把剩下的抄在新數(shù)組中  while(t<=r)k+;bk=at;t+;   /如果第二個區(qū)間沒有抄結束，把剩下的抄在新數(shù)組中  for(int o=1;o<=k;o+)/把新數(shù)組中的元素，再抄回原來的區(qū)間，這兩個連續(xù)的區(qū)間變?yōu)橛行虻膮^(qū)間。al+o-1=bo;void mergesort(int x,int y)/對區(qū)間x,y進行二路歸并排序  int mid;  if(x>=y) return;  mid=(x+y)/2;/求x,y區(qū)間，中間的那個點mid,mid把x,y區(qū)間一分為二  m

9、ergesort(x,mid);/對前一段進行二路歸并  mergesort(mid+1,y);/對后一段進行二路歸并  merge(x,mid,y);/把已經有序的前后兩段進行合并 歸并排序應用了分治思想，把一個大問題，變成兩個小問題。二分是分治的思想。 五、二分查找int find(int x,int y,int m) /在x,y區(qū)間查找關鍵字等于m的元素下標 int head,tail,mid;  head=x;tail=y;mid=(x+y)/2);/取中間元素下標  if(amid=m) return mid;/如果中間元素

10、值為m返回中間元素下標mid  if(head>tail) return 0;/如果x>y，查找失敗，返回0  if(m>amid)  /如果m比中間元素大，在后半區(qū)間查找，返回后半區(qū)間查找結果    return find(mid+1,tail);  else /如果m比中間元素小，在前半區(qū)間查找，返回后前區(qū)間查找結果    return find(head,mid-1);六、高精度加法#include<iostream>#include<cstring&g

11、t;using namespace std;int main()  string str1,str2;  int a250,b250,len;   /數(shù)組的大小決定了計算的高精度最大位數(shù)  int i;  memset(a,0,sizeof(a);  memset(b,0,sizeof(b);  cin>>str1>>str2;   /輸入兩個字符串  a0=str1.length();  /取得第一個字符串的長度  for(i=1;i<

12、;=a0;i+)  /把第一個字符串轉換為整數(shù)，存放在數(shù)組a中    ai=str1a0-i-'0'  b0=str2.length();   /取得第二個字符串長度  for(i=1;i<=b0;i+)   /把第二個字符串中的每一位轉換為整數(shù)，存放在數(shù)組B中    bi=str2b0-i-'0'  len=(a0>b0?a0:b0);   /取兩個字符串最大的長度  for(i=

13、1;i<=len;i+)   /做按位加法，同時處理進位      ai+=bi;    ai+1+=ai/10;    ai%=10;       len+;    /下面是去掉最高位的0，然后輸出。  while(alen=0)&&(len>1) len-;  for(i=len;i>=1;i-)    cou

14、t<<ai;  return 0;  注意：兩個數(shù)相加，結果的位數(shù)，應該比兩個數(shù)中大的那個數(shù)多一位。 七、高精度減法#include<iostream>using namespace std;int compare(string s1,string s2);int main()  string str1,str2;  int a250,b250,len;  int i;  memset(a,0,sizeof(a);  memset(b,0,sizeof(b);  cin&

15、gt;>str1>>str2;  a0=str1.length();  for(i=1;i<=a0;i+)    ai=str1a0-i-'0'  b0=str2.length();  for(i=1;i<=b0;i+)    bi=str2b0-i-'0'  if(compare(str1,str2)=0)  /大于等于，做按位減，并處理借位。      for(i=1;i

16、<=a0;i+)      ai-=bi;       if (ai<0) ai+1-;ai+=10;          a0+;    while(aa0=0)&&(a0>1) a0-;    for(i=a0;i>=1;i-)      cout<&

17、lt;ai;    cout<<endl;                               else      cout<<'-'  /小于就輸出負號   

18、for(i=1;i<=b0;i+)  /做按位減，大的減小的      bi-=ai;       if (bi<0) bi+1-;bi+=10;          b0+;    while(bb0=0)&&(b0>1) b0-;    for(i=b0;i>=1;i-)  &

19、#160;   cout<<bi;    cout<<endl;            return 0; int compare(string s1,string s2)  /比較字符串（兩個數(shù)）數(shù)字的大小，大于等于返回0，小于返回1。  if(s1.length()>s2.length() return 0;  /先比較長度，哪個字符串長，對應的那個數(shù)就大  if

20、(s1.length()<s2.length() return 1;  for(int i=0;i<=s1.length();i+)  /長度相同時，就一位一位比較。      if(s1i>s2i) return 0;    if(s1i<s2i) return 1;                  

21、            return 0;   /如果長度相同，每一位也一樣，就返回0，說明相等 做減法時，首先要判斷兩個字符串的大小，決定是否輸出負號，然后就是按位減法，注意處理借位。 八、高精度乘法#include<iostream>#include<cstring>using namespace std;int main()  string str1,str2;  int a250,b250,c500,le

22、n;    /250位以內的兩個數(shù)相乘  int i,j;  memset(a,0,sizeof(a);  memset(b,0,sizeof(b);  cin>>str1>>str2;  a0=str1.length();  for(i=1;i<=a0;i+)    ai=str1a0-i-'0'  b0=str2.length();  for(i=1;i<=b0;i+)  

23、0; bi=str2b0-i-'0'  memset(c,0,sizeof(c);  for(i=1;i<=a0;i+)   /做按位乘法同時處理進位，注意循環(huán)內語句的寫法。    for(j=1;j<=b0;j+)        ci+j-1+=ai*bj;    ci+j+=ci+j-1/10;    ci+j-1%=10;    &#

24、160;    len=a0+b0+1;  /去掉最高位的0，然后輸出  while(clen=0)&&(len>1) len-;   /為什么此處要len>1?  for(i=len;i>=1;i-)    cout<<ci;  return 0;  注意：兩個數(shù)相乘，結果的位數(shù)應該是這兩個數(shù)的位數(shù)和減1。優(yōu)化：萬進制#include<iostream>#include<cstring>usin

25、g namespace std;void num1(int s,string st1);int a2501,b2501,c5002;/此處可以進行2500位萬進制乘法，即10000位十進制乘法。Int main()      string str1,str2;    int len;    cin>>str1>>str2;    memset(a,0,sizeof(a);    memset(b,0,s

26、izeof(b);    memset(c,0,sizeof(c);    num1(a,str1); /把str1從最低位開始，每4位存放在數(shù)組a中    num1(b,str2); /把str2從最低位開始，每4位存放在數(shù)組b中    for(int i=1;i<=a0;i+) /作按位乘法并處理進位，此處是萬進制進位      for(int j=1;j<=b0;j+)   &#

27、160;              ci+j-1+=ai*bj;          ci+j+=ci+j-1/10000;          ci+j-1%=10000;            len

28、=a0+b0;/a0和b0存放的是每個數(shù)按4位處理的位數(shù)    while (clen=0)&&(len>1) len-;/去掉高位的0，并輸出最高位      cout<<clen;    for(int i=len-1;i>=1;i-)/把剩下來的每一位還原成4位輸出              if (ci<1000)

29、 cout<<0;        if (ci<100) cout<<0;        if (ci<10) cout<<0;                cout<<ci;       

30、0;  cout<<endl;    return 0;void num1(int s,string st1)/此函數(shù)的作用就是把字符串st1，按4位一組存放在數(shù)組s中   int k=1,count=1;    s0=st1.length();/存放st1的長度，省去一長度變量    for(int i=s0-1;i>=0;i-) /從最低位開始，處理每一位    if (count%4=0) sk+=(st1i-0)*100

31、0; if(i!=0) k+;      if (count%4=1) sk=(st1i-0);      if (count%4=2) sk+=(st1i-0)*10;      if (count%4=3) sk+=(st1i-0)*100;      count+;        s0=k; /存放數(shù)組的位數(shù)，就是按4位處理后的萬進

32、制數(shù)的位數(shù)。      Return; 九、高精度除法（沒講） 十、篩選法建立素數(shù)表void maketable(int x)/建立X以內的素數(shù)表prim，primi為0，表示i為素數(shù)，為1表示不是質數(shù) memset(prim,0,sizeof(prim);/初始化質數(shù)表 prim0=1;prim1=1;prim2=0;/用篩選法求X以內的質數(shù)表 for(int i=2;i<=x;i+)    if (primi=0)   

33、60; int j=2*i;      while(j<=x)       primj=1;j=j+i; 對于那些算法中，經常要判斷素數(shù)的問題，建立一個素數(shù)表，可以達到一勞永逸的目的。 十一、深度優(yōu)先搜索void dfs(int x)  以圖的深度優(yōu)先遍歷為例。           cout<<x<< ; 訪問x頂點  

34、;    visitedx=1; 作已訪問的標記      for(int k=1;k<=n;k+) 對與頂點x相鄰而又沒訪問過的結點k進行深度優(yōu)先搜索。        if(axk=1)&&(visitedk=0)         dfs(k);    十二、廣度優(yōu)先搜索void  bfs(void) /

35、按廣度優(yōu)先非遞歸遍歷圖G，n個頂點，編號為1.n。注：圖不一定是連通的/使用輔助隊列Q和訪問標記數(shù)組visited。    for(v=1;v<=n;v+)  visitedv=0；/標記數(shù)組初始化    for(v=1; v<=n; v+)      if(visitedv=0 )         /v尚未訪問       

36、  int h=1,r=1;    /置空的輔助隊列q         visitedv=1；/頂點v,作訪問標記         cout<<v<< ; /訪問頂點v         qr=v；    /v入隊列    &#

37、160;    while(h<=r) /當隊列非空時循環(huán)              int tmp=qh;  /隊頭元素出隊，并賦值給tmp             for(int j=1;j<=n;j+)       

38、60;       if(visitedj=0)&&(atmpj=1)/j為tmp的尚未訪問的鄰接頂點                    visitedj=1;  對j作訪問標記            

39、;        cout<<j<< ; 訪問j                    r+; /隊尾指針加1qr=j; /j入隊  /end-if             h+;

40、60;          /end -while十三、二叉樹的前序、中序和后序遍歷void preorder(int x)/二叉樹的先序遍歷    if(x=0) return;   cout<<x;/先訪問根   preorder(ax.ld);/再先序遍歷根的左子樹   preorder(ax.rd);/最后先序遍歷根的右子樹 void inorder(int x)/二叉樹的中序遍歷

41、0;   if(x=0) return;   preorder(ax.ld);/先中序遍歷根的左子樹   cout<<x;/再訪問根   preorder(ax.rd);/最后中序遍歷根的右子樹 void reorder(int x)/二叉樹的后序遍歷    if(x=0) return;   preorder(ax.ld);/先后序遍歷根的左子樹   preorder(ax.rd);/再后序遍歷根的右子樹 

42、60; cout<<x;/最后訪問根  十四、樹轉換為二叉樹算法 十五、二叉排序樹 十六、哈夫曼樹void haff(void) /構建哈夫曼樹   for(int i=n+1;i<=2*n-1;i+) /依次生成n-1個結點     int l=fmin(i-1); /查找權值最小的結點的編號l       ai.lchild=l; /把l作為結點i的左孩子     

43、  al.father=i; /把l的父結點修改為i       int r=fmin(i-1); /查找次小權值的編號r       ai.rchild=r; /把l作為結點i的右孩子       ar.father=i; /把r的父結點修改為i       ai.da=al.da+ar.da; /合并l,j結點，生成新結點i 

44、0;   int fmin(int k)/在1到K中尋找最小的權值的編號                int mins=0;         for(int s=1;s<=k;s+)           if(amins.da>as.da)&&(as.fath

45、er=0) /as.father=0,說明這個結點還不是別個結點mins=s;                           /的孩子，不等于0說明這個結點已經用過。         return mins;    

46、0;  void inorder(int x)/遞歸生成哈夫曼編碼  if(ax.father=0) ax.code=”“;/根結點  if(aax.father.lchild=x)  ax.code=aax.father.code+'0'  if(aax.father.rchild=x)  ax.code=aax.father.code+'1'  if(ax.lchild!=0) inorder(ax.lchild);/遞歸生成左子樹  if(ax.lchild=0)&&a

47、mp;(ax.rchild=0)/輸出葉子結點     cout<<ax.da<<':'<<ax.code<<endl;  if(ax.rchild!=0) inorder(ax.rchild);/遞歸生成右子樹十七、并查集int getfather(int x)/非遞歸求X結點的根結點的編號while(x!=fatherx)  x=fatherx; return x; int getfather(int x)/遞歸求X結點的根結點的編號if(x=fa

48、therx) return x; else return getfather(fatherx);  int getfather(int x)/非遞歸求X結點的根結點編號同時進行路徑壓縮int p=x;while(p!=fatherp)/循環(huán)結束后，P即為根結點   p=fatherp; while(x!=fatherx)/從X結點沿X的父結點進行路徑壓縮   int temp=fatherx;/暫存X沒有修改前的父結點fatherx=p;/把X的父結點指向Px=temp;    ret

49、urn p; int getfather(int x)/遞歸求X結點的根結點編號同時進行路徑壓縮if(x=fatherx) return x; else        int temp=getfather(fatherx);       fatherx=temp;       return temp; void merge(int x,int y)/合并x,y兩個結點 int

50、x1,x2;  x1=getfather(x);/取得X的父結點  x2=getfather(y);/取得Y的父結點  if(x1!=x2) fatherx1=x2; /兩個父結點不同的話就合并，注意：合并的是X，Y兩個結點的根。 十八、Prime算法void prime(void) /prim算法求最小生成樹，elisti是邊集數(shù)組，aij為<I,j>的權值。edge為結構體類型。for (int i=1;i<=n-1;i+)/初始化結點1到其它n-1個結點形成的邊集   elisti.from=1;elisti.

51、to=i+1;elisti.w=a1i+1;    for (int i=1;i<=n-1;i+)/依次確定n-1條邊  int m=i;   for(int j=i+1;j<=n-1;j+)/確定第i條邊時，依次在i+1至n-1條邊中找最小的那條邊     if(elistj.w<elistm.w) m=j;   if(m!=i) /如果最小的邊不是第i條邊就交換edge tmp=elisti;elisti=elistm;elistm=tmp; 

52、  for(int j=i+1;j<=n-1;j+)/更新第i+1至n-1條邊的最小距離。     if(elistj.w>aelisti.toelistj.to) elistj.w=aelisti.toelistj.to;                          &

53、#160; for(int i=1;i<=n-1;i+)/求最小生成樹的值ans=ans+elisti.w;                        如果要求出哪些邊構成最小生成樹，在更新第i+1至n-1條邊到已經生成的樹中最小距離時(上面代碼中加粗的部分)，還要加上elistj.from=elisti.to;語句，即在更新權值時，還應該更新起點

54、。Prime算法適用于頂點不是太多的稠密圖，如果對于頂點數(shù)較多的稀疏圖，就不太適用了。 十九、Dijkstra算法void dijkstra(int x)  /求結點x到各個結點的最短路徑memset(vis,0,sizeof(vis); /初始化，visi0表示源點到結點i未求，否則已求visx=1;prex=0; /初始化源點。for(int i=1;i<=n;i+)   /對其它各點初始化。    if(i!=x)disi=gxi;prei=x;for(int i=1;i<=n-1;i+) 

55、60; /對于n個結點的圖，要求x到其它n-1個結點的最短距離    int m=big; /虛擬一個最大的數(shù)big=99999999;int k=x;      for(int j=1;j<=n;j+)   /在未求出的結點中找一個源點到其距離最小的點        if(visj=0&&m>disj)m=disj;k=j;      visk=1

56、;   /思考：如果k=X說明什么？說明后面的點，無解。      for(int j=1;j<=n;j+)   /用當前找的結點更新未求結點到X的最短路徑      if(visj=0)&&(disk+gkj<disj)                   &

57、#160;disj=disk+gkj;  /更新         prej=k;  /保存前趨結點，以便后面求路徑            說明：disi表示x到i的最短距離，prei表示i結點的前趨結點。二十、Kruscal算法void qsort(int x,int y)/對邊集數(shù)組進行快速排序int h=x,r=y,m=elist(h+r)>>1.w; while(h&l

58、t;r)  while(elisth.w<m) h+;   while(elistr.w>m) r-;   if(h<=r)    edge tmp=elisth;elisth=elistr;elistr=tmp;h+;r-;   if(x<r) qsort(x,r); if(h<y) qsort(h,y); int getfather(int x)/找根結點，并壓縮路徑，此處用遞歸實現(xiàn)的。if(x=fatherx) return x; 

59、;else         int f=getfather(fatherx);        fatherx=f;        return f;       void merge(int x,int y)/合并x,y結點，在此題中的x,y為兩個根結點。fatherx=y; void kruscal(void)int

60、 sum=0,ans=0;qsort(1,t);/對t條邊按權值大小按從小到大的次序進行快速排序   for(int i=1;i<=t;i+)     int x1=getfather(elisti.from);/取第i條邊的起點所在的樹的根int x2=getfather(elisti.to);/ 取第i條邊的終點所在的樹的根if(x1!=x2)sum+;merge(x1,x2);ans+=elisti.w;/不在同一個集合，合并，即第i條邊可以選取。if(sum>n-1)break;/已經確定了n-1條邊了，最小生成樹

61、已經生成了，可以提前退出循環(huán)了   if(sum<n-1)cout<<"Impossible"<<endl; /從t條邊中無法確定n-1條邊，說明無法生成最小生成樹   else  cout<<ans<<endl;   克魯斯卡爾算法，只用了邊集數(shù)組，沒有用到圖的鄰接矩陣，因此當圖的結點數(shù)比較多的時候，輸入數(shù)據(jù)又是邊的信息時，就要考慮用Kruscal算法。對于島國問題，我們就要選擇此算法，如果用Prim算法，還要開一個二維的數(shù)組來表示圖的鄰接矩陣，對于

62、10000個點的數(shù)據(jù)，顯然在空間上是無法容忍的。 二十一、Floyed算法void floyed(void)/ aij表示結點i到結點j的最短路徑長度，初始時值為<I,J>的權值。for(int k=1;k<=n;k+) /枚舉中間加入的結點不超過K時fij最短路徑長度，K相當DP中的階段        for(int i=1;i<=n;i+) /i，j是結點i到結點J，相當于DP中的狀態(tài)for(int j=1;j<=n;j+)      if (aij>aik+akj) aij=aik+akj;/這是決策，加和不加中間點，