c常用經(jīng)典算法及其實(shí)現(xiàn)(完整版)
【正文】 if((pare(str1,str2))==0) for(i=1。i++) memset(b,0,sizeof(b))。 string str1,str2。 return 0。//取兩個(gè)字符串最大的長度i++)//數(shù)組的大小決定了計(jì)算的高精度最大位數(shù) return find(head,mid1)。 //如果m比中間元素大，在后半?yún)^(qū)間查找，返回后半?yún)^(qū)間查找結(jié)果tail=y。 merge(x,mid,y)。 if(x=y) return。 //如果第二個(gè)區(qū)間沒有抄結(jié)束，把剩下的抄在新數(shù)組中h++。}//讓h指向第一個(gè)區(qū)間的第一個(gè)元素，t指向第二個(gè)區(qū)間的第一個(gè)元素。四、合（歸）并排序void merge(int l,int m,int r)//合并[l,m]和[m+1,r]兩個(gè)已經(jīng)有序的區(qū)間{ int b[101]。i++)i++)//讀入n個(gè)數(shù)}} for(int j=ni。二、冒泡排序void paopao(void) //待排序的數(shù)據(jù)存放在a[1]..a[n]數(shù)組中{for(int i=1。if(rx) qsort(x,r)。 a[h]=a[r]。//如果此時(shí)h=r，交換a[h]和a[r] int m=a[(x+y)1]。 {int h=x,r=y。if(hy) qsort(h,y)。j=ni。in。 if(a[j]a[j+1]) {int temp=a[j]。{memset(tong,0,sizeof(tong))。}//相應(yīng)的桶號計(jì)數(shù)器加1 while (tong[i]!=0)}}}//用于新數(shù)組B的指針 }t++。}void mergesort(int x,int y)//對區(qū)間[x,y]進(jìn)行二路歸并排序{//對前一段進(jìn)行二路歸并五、二分查找int find(int x,int y,int m) //在[x,y]區(qū)間查找關(guān)鍵字等于m的元素下標(biāo){ int head,tail,mid。 if(headtail) return 0。 else //如果m比中間元素小，在前半?yún)^(qū)間查找，返回后前區(qū)間查找結(jié)果 int a[250],b[250],len。 memset(b,0,sizeof(b))。 //取得第一個(gè)字符串的長度039。i++) len=(a[0]b[0]?a[0]:b[0])。 //做按位加法，同時(shí)處理進(jìn)位 a[i+1]+=a[i]/10。 while((a[len]==0)amp。七、高精度減法includeiostreamusing namespace std。 b[i]=str2[b[0]i]39。 {a[i]=b[i]。a[i]+=10。39。 //做按位減，大的減小的 for(i=b[0]。}int pare(string s1,string s2) for(int i=0。 if(s1[i]s2[i]) return 0。 }int main(){ int i,j。 a[0]=()。039。i++)j++) //去掉最高位的0，然后輸出i=1。} //把str2從最低位開始，每4位存放在數(shù)組b中 c[i+j1]%=10000。 }amp。 coutc[i]。 int k=1,count=1。 for(int i=s[0]1。 if (count%4==3) s[k]+=(st1[i]‘0’)*100。memset(prim,0,sizeof(prim))。i++)十一、深度優(yōu)先搜索void dfs(int x)k=n。 bfs(void) //按廣度優(yōu)先非遞歸遍歷圖G，n個(gè)頂點(diǎn)，編號為1..n。 visited[v]=0；//標(biāo)記數(shù)組初始化 //隊(duì)頭元素出隊(duì)，并賦值給tmp preorder(a[x].rd)。 preorder(a[x].ld)。void reorder(int x)//二叉樹的后序遍歷十五、二叉排序樹 a[i].lchild=l。 //把l的父結(jié)點(diǎn)修改為i }}int fmin(int k)//在1到K中尋找最小的權(quán)值的編號 if((a[mins].daa[s].da)amp。 a[x].code=a[a[x].father].code+39。//遞歸生成左子樹:39。} x1=getfather(x)。edge為結(jié)構(gòu)體類型。j=n1。i++)}for(int i=1。 //虛擬一個(gè)最大的數(shù)big=99999999。j=n。 //用當(dāng)前找的結(jié)點(diǎn)更新未求結(jié)點(diǎn)到X的最短路徑二十、Kruscal算法void qsort(int x,int y)//對邊集數(shù)組進(jìn)行快速排序{int h=x,r=y,m=elist[(h+r)1].w。r。{if(x==father[x]) return x。 void merge(int x,int y)//合并x,y結(jié)點(diǎn)，在此題中的x,y為兩個(gè)根結(jié)點(diǎn)。i=t。merge(x1,x2)。二十一、Floyed算法void floyed(void)// a[i][j]表示結(jié)點(diǎn)i到結(jié)點(diǎn)j的最短路徑長度，初始時(shí)值為I,J的權(quán)值。有狀態(tài)轉(zhuǎn)移方程f[i][j]=max{f[i1][j],f[i1][jw[i]]+c[i]}。j=v。//輸出結(jié)果。j)//枚舉狀態(tài)，當(dāng)然此處也可寫成:for(int j=v。對比優(yōu)化前后，我們不難發(fā)現(xiàn)，優(yōu)化后的代碼實(shí)際上就是在原來基本的代碼基礎(chǔ)上，減少了階段這一維，同時(shí)在枚舉狀態(tài)時(shí)，為了保證結(jié)果的正確性，枚舉的順序只能是v到0，而不能是0到v。狀態(tài)轉(zhuǎn)移方程f[i][j]=max{f[i1][j],f[i1][jw[i]]+c[i]，f[i1][j2*w[i]]+2*c[i]，…，f[i1][jk*w[i]]+k*c[i]}。for(int j=0。//k=0的情況作為f[i][j]的初始值，然后在k=1,2,…,v/w[i]中找最大值//選第i個(gè)物品}coutf[n][v]endl。f[i]表示從第1個(gè)數(shù)開始，以第i個(gè)數(shù)結(jié)尾的最長遞增子序列。 max{f[i1][j],f[i][j1]}+1 狀態(tài)轉(zhuǎn)移方程：狀態(tài)轉(zhuǎn)移方程：f[i]=max{f[j]}+1 （1≤j≤i1，1≤i≤n，a[i]≥a[j]）臨界狀態(tài)：f[
試題試卷相關(guān)推薦
鄂ICP備17016276號-1