華科算法實驗報告

1、 . .頁腳. 課課 程程 實實 驗驗 報報 告告 課程名稱：課程名稱： 算法設計與分析算法設計與分析 專業(yè)班級：專業(yè)班級：計算機科學與技術計算機科學與技術 13xx13xx 班班學學 號：號： 姓姓 名：名： 指導老師：指導老師： 報告日期：報告日期： 2015-11-292015-11-29 計算機科學與技術學院計算機科學與技術學院 . .頁腳. 目錄目錄一實驗一一實驗一 .3 31 1實驗題目實驗題目.3 32 2設計思路設計思路.3 33 3程序源代碼程序源代碼.4 44 4運行演示運行演示.7 7二實驗二二實驗二 .8 81 1實驗題目實驗題目.8 82 2設計思路設計思路.8 83

2、 3程序源代碼程序源代碼.9 94 4運行演示運行演示.1212 . .頁腳. 一實驗一實驗一一1 1實驗題目實驗題目單源最短路徑問題： 已知一個 n 結點有向圖 G=(V,E)和邊的權函數(shù) c(e)，求由 G 中某指定結點 v0 到其它各結點的最短路徑。假定邊的權值為正。2 2設計思路設計思路 貪心算法流程圖如圖 1：圖 1 生成最短路徑算法流程設計總方法：使用貪心算法求解。貪心方法：1) 度量標準生成的所有路徑長度之和作為度量標準。為了使這一量度達到最小，其單 . .頁腳. 獨的每一條路徑都必須具有最小長度。2) 算法按照路徑長度的非降次序生成這些路徑。首先，生成一條到最近結點的最短路徑，

3、然后，生成一條到第二近結點的最短路徑，等等。即只用求出從路徑 v0開始到 G 中其他所有結點的最短路徑長度。假定 G 中n 個結點被標記上 1 到 n,集合 S 作為一個數(shù)組存放，如果結點 i 不在 S 中，則Si=0，如果在 S 中，則 Si=1，若 COST（i,j）是（i,j）的權，則在邊（i，j）不在成本鄰接矩陣時，就被置某個大數(shù)，這里用 N 表示，當 i=j 時，COST（i,j）被置以 0。3 3程序源代碼程序源代碼#include #include #define N 1000void shortestPaths(int v,int *COST,int *DIST,int n);

4、/最短路徑生成函數(shù)void output2(int *arr,int row,int col);/輸出成本的鄰接矩陣void outArray1(int *arr,int n);/輸出更新后其它結點到起始結點的路徑長度int main() int COST77= 0,20,50,30, N, N, N, N, 0,25, N, N,70, N, N, N, 0,40,25,50, N, N, N, N, 0,55, N, N, N, N, N, N, 0,10,70, N, N, N, N, N, 0,50, N, N, N, N, N, N, 0 ; int DIST7; int v=0;

5、/* printf(成本鄰接矩陣：n); output2(&COST00,7,7); */ /生成 0 號結點到 1 至 6 號結點的最短路徑 shortestPaths(v,&COST00,DIST,7); return 0;void shortestPaths(int v,int *COST,int *DIST,int n)/G 是一個 n 結點有向圖，它由其成本鄰接矩陣 COSTnn表示，DISTj被置以結點 v到 /結點 j 的最短路徑長度，這里 1=j=n;DISTv被置成 0 int Sn; . .頁腳. int pren;/pw記錄起始結點到結點 w 的最短路徑中

6、的 w 前一結點 int u,num,i,w; int tv,td=0; /初始化：結點 v 以外的結點未被選中，并更新路徑長度為 v 到其它結點的初始成本 for(i=0;in;i+) Si=0; *(DIST+i)=*(COST+v*n+i); prei=0; Sv=1; DISTv=0; /更新路徑長度 for(num=1;numn;num+) /選擇距離結點 v 最近的結點 w for(w=1;wn;w+) if(Sw=0) td=DISTw; tv=w; break; for(w+;wDISTw) td=DISTw; tv=w; u=tv; Su=1; DISTu=td; /更新路徑

7、 for(w=1;w(DISTu+*(COST+u*n+w) . .頁腳. DISTw=(DISTu+*(COST+u*n+w); prew=u;/更新結點 w 最短路徑并記錄 w 結點的上一結點 /輸出第 num 次更新后的路徑長度 printf(n 第%d 次路徑:,num); output1(DIST,n); printf(nn); /輸出路徑 for(i=1;in;i+) printf(從 0 到%d,最短的路徑是：n,i); w=i; printf(%d-,w); while(prew!=v) w=prew; printf(%d-,w); printf(%dn,v); void ou

8、tput2(int *a,int row,int col) int i,j; for(i=0;irow;i+) for(j=0;jcol;j+) if(*(a+i*row)+j)=N) printf( Nt); else printf(%3dt,*(a+i*row)+j); puts(n); void output1(int *arr,int n) int i; for(i=0;in;i+) . .頁腳. if(*(arr+i)=N) printf( Nt); else printf(%3dt,*(arr+i); 4 4運行演示運行演示我用了書上的一個例子，它的成本鄰接矩陣已直接存入程序中，它

9、的帶權有向圖如下： 圖 2 帶權有向圖運行結果如下所示：V0V1V2V3V5V6V4207025503040555025105070 . .頁腳. 圖 3 運行結果圖二實驗二二實驗二1 1實驗題目實驗題目k 路歸并：每次同時歸并 k 個文件且使移動次數(shù)最少。2 2設計思路設計思路1、流程圖總流程圖如圖 1 所示。 . .頁腳. 圖 1 歸并文件流程圖2、設計方法貪心算法3、度量標準每次選出 k 個最小的文件歸并，將歸并后的結果作為新的文件加入待歸并的文件序列中，直到歸并完成。值得注意的是，由于所有的內部點的度數(shù)必須為 k，因此，對于 n 取某些值，就不和 k 元歸并樹相對應。所以有必要引進一定

10、量的虛結點，每個虛結點賦值 0，這個虛結點的虛值，不會影響所產(chǎn)生度數(shù)為 k 的帶權外部路徑長度。3 3程序源代碼程序源代碼#include#include . .頁腳. #include#include#define MAX 100typedef int ElemType;typedef struct Table ElemType elem; struct Table *next;T;void outTable(T *head);void func(T *head,int k);int main() int num,k,r; T *head,*cur; head=(T *)malloc(siz

11、eof(T); head-elem=0; /獲取文件數(shù) do printf(請輸入文件的個數(shù)(1):); scanf(%d,&num); while(num1,=%d):,num); scanf(%d,&k); while(knum); /生成隨機序列 srand(time(NULL); cur=(T *)malloc(sizeof(T); head-next=cur; head-elem+; cur-elem=(rand()%MAX+1); while(head-elemnext=(T *)malloc(sizeof(T); cur=cur-next; cur-elem=(r

12、and()%MAX+1); head-elem+; printf(隨機生成的文件序列為：); . .頁腳. outTable(head); /補充虛結點 r=(k-1)-(num-1)%(k-1)%(k-1); while(head-elemelem=0; cur-next=head-next; head-next=cur; head-elem+; if(r=0) printf(不用補充虛結點n); else printf(補充%d 個虛結點:,r); outTable(head); /歸并 func(head,k); return 0;void func(T *head,int k) T *

13、mink,*mpre,*cur,*cpre; int i=0,j=1,times=(head-elem-1)/(k-1),t=times; while(times-0)/當 K 小于等于待歸并文件數(shù)時，取 K 個最小的文件歸并 if(kelem) i=-1; /取 k 個最小的文件 while(+inext; j=0; while(jelem) if(mini-elemcur-elem) mpre=cpre; mini=cur; . .頁腳. cpre=cur; cur=cur-next; j+; mpre-next=mini-next; head-elem-; /輸出歸并的 K 個文件的大小

14、 printf(第%d 次歸并:,t-times); i=0; while(ielem); i+; i=1; /歸并 K 個文件 while(ielem+=mini-elem; free(minj); i+; /將歸并 K 個文件得到的新文件加入節(jié)點中 min0-next=head-next; head-next=min0; head-elem+; /輸出歸并后的文件 printf(t 歸并后的文件為：); cur=head-next; i=head-elem; while(i-0) printf(%4d,cur-elem); cur=cur-next; printf(n); void outTable(T *h