c常用經(jīng)典算法及其實(shí)現(xiàn)(文件)
【正文】 d) //按廣度優(yōu)先非遞歸遍歷圖G，n個(gè)頂點(diǎn)，編號(hào)為1..n。 visited[v]=0；//標(biāo)記數(shù)組初始化 v=n。 //隊(duì)頭元素出隊(duì)，并賦值給tmp for(int j=1。 if((visited[j]==0)amp。 //j入隊(duì)} }//end while}十三、二叉樹的前序、中序和后序遍歷void preorder(int x)//二叉樹的先序遍歷 preorder(a[x].rd)。 preorder(a[x].ld)。//再訪問根void reorder(int x)//二叉樹的后序遍歷 coutx。十五、二叉排序樹i=2*n1。 a[i].lchild=l。 //把l的父結(jié)點(diǎn)修改為i a[r].father=i。 //合并l,j結(jié)點(diǎn)，生成新結(jié)點(diǎn)i }}int fmin(int k)//在1到K中尋找最小的權(quán)值的編號(hào) if((a[mins].daa[s].da)amp。 }void inorder(int x)//遞歸生成哈夫曼編碼{ a[x].code=a[a[x].father].code+39。 a[x].code=a[a[x].father].code+39。//遞歸生成左子樹:39。//遞歸生成右子樹}十七、并查集int getfather(int x)//非遞歸求X結(jié)點(diǎn)的根結(jié)點(diǎn)的編號(hào){while(x!=father[x])}} father[x]=temp。}} x1=getfather(x)。 if(x1!=x2) father[x1]=x2。edge為結(jié)構(gòu)體類型。i=n1。elist[m]=tmp。j=n1。i=n1。pre[x]=0。i++)}for(int i=1。 //對(duì)于n個(gè)結(jié)點(diǎn)的圖，要求x到其它n1個(gè)結(jié)點(diǎn)的最短距離 //虛擬一個(gè)最大的數(shù)big=99999999。 j=n。mdis[j]){m=dis[j]。 for(int j=1。 //用當(dāng)前找的結(jié)點(diǎn)更新未求結(jié)點(diǎn)到X的最短路徑}二十、Kruscal算法void qsort(int x,int y)//對(duì)邊集數(shù)組進(jìn)行快速排序{int h=x,r=y,m=elist[(h+r)1].w。 {edge tmp=elist[h]。r。{if(x==father[x]) return x。 void merge(int x,int y)//合并x,y結(jié)點(diǎn)，在此題中的x,y為兩個(gè)根結(jié)點(diǎn)。qsort(1,t)。i=t。merge(x1,x2)。//已經(jīng)確定了n1條邊了，最小生成樹已經(jīng)生成了，可以提前退出循環(huán)了} }二十一、Floyed算法void floyed(void)// a[i][j]表示結(jié)點(diǎn)i到結(jié)點(diǎn)j的最短路徑長(zhǎng)度，初始時(shí)值為I,J的權(quán)值。 i++) //i，j是結(jié)點(diǎn)i到結(jié)點(diǎn)J，相當(dāng)于DP中的狀態(tài)for(int j=1。//這是決策，加和不加中間點(diǎn)，取最小的值}有狀態(tài)轉(zhuǎn)移方程f[i][j]=max{f[i1][j],f[i1][jw[i]]+c[i]}。for(int i=1。j=v。//輸出結(jié)果。i=n。j)//枚舉狀態(tài)，當(dāng)然此處也可寫成:for(int j=v。 {f[j]=f[j]。(f[j]f[jw[i]]+c[i])) f[j]=f[jw[i]]+c[i]。對(duì)比優(yōu)化前后，我們不難發(fā)現(xiàn)，優(yōu)化后的代碼實(shí)際上就是在原來基本的代碼基礎(chǔ)上，減少了階段這一維，同時(shí)在枚舉狀態(tài)時(shí)，為了保證結(jié)果的正確性，枚舉的順序只能是v到0，而不能是0到v。j=w[i]。狀態(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]}。邊界條件為f[0][s]=0,s=0,1,…,v。for(int j=0。j)//k=0的情況作為f[i][j]的初始值，然后在k=1,2,…,v/w[i]中找最大值k=v/w[i]。//選第i個(gè)物品}coutf[n][v]endl。二十五、多背包問題f[i]表示從第1個(gè)數(shù)開始，以第i個(gè)數(shù)結(jié)尾的最長(zhǎng)遞增子序列。二十七、最長(zhǎng)公共子序列問題 (若a[i]≠b[j]) 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[1]=1。j++)//枚舉狀態(tài)，當(dāng)然此處也可寫成:for(int j=v。i=n。f[i][j]表示前i個(gè)物品，在背包載重為j時(shí)獲得的最大價(jià)值。//輸出結(jié)果。 if((jw[i])amp。j)for(int j=v。優(yōu)化：用一維數(shù)組實(shí)現(xiàn)，把第i1階段和第i階段數(shù)據(jù)存在一塊。//不選第i個(gè)物品if(f[i][j]f[i1][jw[i]]+c[i]) f[i][j]=f[i1][jw[i]]+c[i]。j=0。i++)//枚舉階段顯然f[n][v]即為所求。j++)for(int i=1。k=n。對(duì)于島國(guó)問題，我們就要選擇此算法，如果用Prim算法，還要開一個(gè)二維的數(shù)組來表示圖的鄰接矩陣，對(duì)于10000個(gè)點(diǎn)的數(shù)據(jù)，顯然在空間上是無法容忍的。coutansendl。 if(sumn1)coutImpossibleendl。}//不在同一個(gè)集合，合并，即第i條邊可以選取。//取第i條邊的起點(diǎn)所在的樹的根int x2=getfather(elist[i].to)。}else {} }elist[r]=tmp。 while(elist[r].wm) r。while(hr){amp。j++) //思考：如果k=X說明什么？說明后面的點(diǎn)，無解。}if(vis[j]==0amp。i++) if(i!=x){dis[i]=g[x][i]。 //對(duì)其它各點(diǎn)初始化。for(int i=1。 //求結(jié)點(diǎn)x到各個(gè)結(jié)點(diǎn)的最短路徑{memset(vis,0,sizeof(vis))。語句，即在更新權(quán)值時(shí)，還應(yīng)該更新起點(diǎn)。} {if(elist[j].wa[elist[i].to][elist[j].to]) elist[j].w=a[el
試題試卷相關(guān)推薦
鄂ICP備17016276號(hào)-1